Masked proportional routing is an improved procedure for choosing links between adjacent nodes of a network for the purpose of transporting an entity from a source node (“A”) to a destination node (“B”). The entity could be, for example, a physical object to be shipped, in which case the nodes would represent waypoints and the links would represent roads or other paths between waypoints. For another example, the entity could be a message or packet of data to be transmitted from A to B, in which case the nodes could be computer-controlled switching stations and the links could be communication channels between the stations. In yet another example, an entity could represent a workpiece while links and nodes could represent, respectively, manufacturing processes and stages in the progress of the workpiece towards a finished product. More generally, the nodes could represent states of an entity and the links could represent allowed transitions of the entity.
The purpose of masked proportional routing and of related prior routing procedures is to schedule transitions of entities from their initial states (“A”) to their final states (“B”) in such a manner as to minimize a cost or to attain some other measure of optimality or efficiency. Masked proportional routing follows a distributed (in the sense of decentralized) approach to probabilistically or deterministically choosing the links. It was developed to satisfy a need for a routing procedure that
- Does not always choose the same link(s), even for two instances characterized by identical estimated values of associated cost functions;
- Enables a graceful transition from one set of links to another set of links as the circumstances of operation of the network change over time;
- Is preferably amenable to separate optimization of different portions of the network;
- Is preferably usable in a network in which some of the routing decisions are made by one or more other procedure(s);
- Preferably does not cause an entity to visit the same node twice; and
- Preferably can be modified so that separate entities moving from A to B do not arrive out of order.
Definitions of several terms are prerequisite to even a brief summary of the mathematical nature of masked proportional routing. Consider a network of N nodes (N ≥ 2) including a source node A and destination node B (see figure). Node i is directly connected to an arbitrary number J(µ) of nodes, which are labeled j = j1, j2, ..., jJ(µ). The term µ represents a characteristic or a set of characteristics of an entity that one seeks to transport from node i to one of the connected nodes j along the route from A to B. The characteristics represented by µ could include the source and/or destination node(s), the routing priority, and/or the time elapsed since leaving the source node. Associated with node i is a J(µ)-component vector, denoted a baseline proportion vector, p(i;µ).
In a deterministic version of masked proportional routing, p(i;µ) is used to compute a J(µ)-component vector, denoted an applied proportion vector, p*(i;µ), that prevents the entity from visiting the same node more than once. In this case, if k is a node that has already been visited, then the jth component of p*(i;µ) is made zero; that is, p*(i;µ)k=0.
In another version of masked proportional routing, there are computed (as described below) two other J(µ)-component vectors, denoted Target(i;n(µ);µ) and Actual(i;n(µ);µ), where n(µ) is a sequence number or a count at node i that may depend on one or more component(s) of µ. Except as described in the last sentence of this paragraph, the link from node i to node j'(µ) is selected as being the one that yields the largest difference between Target(i;n(µ);µ) and Actual(i;n(µ);µ). The entity is then transported along the i-to-j'(µ) link. The vectors Target(i;n(µ);µ) and Actual(i;n(µ);µ) are computed iteratively as follows:
Target(i;n(µ);µ) = α(µ)Target(i;n(µ)–1;µ) + ß(µ)p*(i;µ)
Actual(i;n(µ)+1;µ) = α(µ)Actual(i;n(µ);µ) + ß(µ)Sent(i;j'(µ);n(µ);µ),
where α(µ) and ß(µ) are selected real numbers and Sent(i;j'(µ);n(µ);µ) is a J(µ)-component vector, the j'(µ)th component of which is 1 and all other components of which are 0. The exception mentioned above applies in special circumstances in which the same link is optionally used to transport consecutively arriving entities.
This work was done by David Wolpert of Ames Research Center. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category. Inquiries concerning rights for the commercial use of this invention should be addressed to
the Patent Counsel
Ames Research Center
Refer to ARC-14366-1