Abstract:
Distributed approach for determining a path connecting adjacent network nodes, for probabilistically or deterministically transporting an entity, with entity characteristic μ from a source node to a destination node. Each node i is directly connected to an arbitrary number J(μ) of nodes, labeled or numbered j=j 1 , j 2 , . . . , jJ(μ). In a deterministic version, a J(μ)-component baseline proportion vector p(i;μ) is associated with node i. A J(μ)-component applied proportion vector p*(i;μ) is determined from p(i;μ) to preclude an entity visiting a node more than once. Third and fourth J(μ)-component vectors, with components iteratively determined by Target(i;n(μ);μ) j =α(μ)·Target(i;n(μ)−1;μ) j +β(μ)·p*(i;μ) j  and Actual(i;n(μ);μ) j =α(μ)·Actual(i;n(μ)−1;μ) j +β(μ)·Sent(i;j′(μ);n(μ)−1;μ) j , are computed, where n(μ) is an entity sequence index and α(μ) and β(μ) are selected numbers. In one embodiment, at each node i, the node j=j′(μ) with the largest vector component difference, Target(i;n(μ);μ) j ′−Actual (i;n(μ);μ) j ′, is chosen for the next link for entity transport, except in special “gap” circumstances, where the same link is optionally used for transporting consecutively arriving entities. The network nodes may be computer-controlled routers that switch collections of packets, frames, cells or other information units. Alternatively, the nodes may be waypoints for movement of physical items in a network or for transformation of a physical item. The nodes may be states of an entity undergoing state transitions, where allowed transitions are specified by the network and/or the destination node.

Description:
ORIGIN OF THE INVENTION 
     The invention described herein was made by an employee of the United States Government and may be manufactured and used by or for the Government for government purposes without payment of any royalties thereon or therefor. 
     TECHNICAL FIELD OF THE INVENTION 
     This invention relates to routing of entities, such as information packets or physically transportable items, from a source to a destination in a network. 
     DISCUSSION OF THE PRIOR ART 
     Many networks share as a component one or more instances of a “routing procedure” by which, in response to a “routing request” that a particular entity be transported from a first node “A” to eventually arrive at a second node “B” in the network, one or more “links” from a path that connects node A and node B are selected. 
     As an example, at the network layer  3  in a digital computer or telecom network, these nodes may be data switching routers, and each associated link may be a direct connection between two neighboring routers. The entity to be transported may be a small as a single packet, frame, cell, flow control signal, etc. (collectively referred to herein as “packets”) or as large as a set of packets in a selected format (delineated by time, by a sequence number or running count of packets routed through a node, by an originating source and/or ultimate destination, by the time the entity was transported from the source node). A particular instance occurs when the routing procedure is resident on a single router or switch, and the procedure is used only to select the next link for the entity to follow on the path to the entity&#39;s ultimate destination B. After the procedure is completed, the entity is transported along the chosen link, and the procedure is repeated at the node at the other end of the chosen link. 
     Alternatively, the entity may be the contents of a temporally open circuit for which the procedure selects an ordered set of consecutive links from node A to node B. Alternatively, the procedure may be used as part of an intermediate scheme, as in flow control or in an ATM-switched network. Well known routing algorithms include distance vector (Bellman-Ford), RIP, link state, ISIS and OSPF, and are discussed in some detail in Radia Perlman, Interconnections: Bridges and Routers, Addison Wesley Publishing, Reading, Mass., 1992, Chapters 9 and 10. 
     As another example, the entity may be a physical item to be transported, such as an aircraft or other vehicle, along a path from one waypoint to the next waypoint. More generally, the entity can be any item (data, physical object, etc.) that is to be transported from a source node to a destination node in a network, using a path including one or more links that connect nodes in the network. 
     More generally, the nodes can be states of the entity, the links are allowed transitions of the entity, and the procedure is used to schedule transitions of entities so that the entities attain their ultimate states. In particular, the invention may be appropriate when it is preferred that no entity visit the same state twice. As a particular example that need not involve transport of the entities, the entities may be physical goods being manufactured or otherwise transformed at one or more nodes, the nodes may represent states of these goods, an ultimate entity destination may be the state of a completed good, and the routing procedure may be a dynamic scheduling algorithm controlling a production schedule or chain for these goods. 
     A routing procedure can involve techniques from the established field of reinforcement learning, as discussed by R. S. Sutton and A. G. Barto in Reinforcement Learning: An Introduction, MIT Press, Cambridge, Mass., 1998. In a simple instance of this, the routing procedure can be provided with numerical “reward signals” from the environment periodically, with the reward signals reflecting values of a cost function. The procedure uses these reward signals together with other received information to statistically determine at run time how, if at all, to modify its response to a given routing request in order to increase the expected value(s) of the reward signals the procedure will receive in the future. A choice by a system&#39;s designer as to how to select or implement the reward signals to be provided to the routing procedure may be determined by what behavior(s) the designer wishes to promote or to discriminate against, among other things. If, for example, the designer wishes to maximize global traffic throughput, a value of throughput, averaged over a selected time interval, may be used to determine the reward signal(s) for the routing procedure. 
     Routing of entities on a network often relies on a routing procedure from a source A to a destination B that may be characterized as “all-or-nothing”: if the value of a given cost function associated with following one possible path connecting node A and node B is estimated to be lower than the value of the cost function for any other path considered that connects A and B, only links from the first path are selected, until such time as new cost estimates are available. Adoption of this all-or-nothing approach has several disagreeable consequences. 
     First, by always selecting links that are part of the same path, the value of the cost function associated with the selected links is likely to increase significantly. For example, this overloading may increase network congestion and/or transportation failure (entity loss or misdelivery) on the chosen link(s). Second, because the value of the cost function associated with the selected links increases so substantially and abruptly, it is likely that the selected links will promptly be de-selected as part of a chosen path, thus producing some instability in the behavior of the network. 
     Third, the network has no opportunity to make a graceful transition from a first set of links to a second set of links, for example, when one or more links in the first set becomes increasingly costly (or inoperative). Fourth, adoption of an all-or-nothing routing procedure requires “hard-edged” use of a cost criterion that allows little or no provision for uncertainty in modeling of the network processes. In particular, discrepancies between estimated and actual values of the cost function may be magnified using such a procedure, due to associated instabilities in the network, and, simultaneously, degradation in the network&#39;s performance associated with any particular discrepancy level may be increased (system “brittleness”). 
     What is needed is a routing procedure that selects links from a collection of two or more A-B paths on a network in a manner that does not always choose the same link(s), even for two instances of the procedure that have identical estimated values of the associated cost functions. Preferably, this procedure should permit a graceful transition from one set of links to another set of links (either partly overlapping or completely non-overlapping) as the circumstances of network operation change with time. Preferably, this procedure should be adaptable to separately optimize different portions of the network. Preferably, this procedure should permit compensation for probabilities that a network will behave in one way or another, at a given time or over a succession of times. Preferably, this procedure should be usable in networks where some of the routing decisions are made by different procedures (i.e., two or more independent routing procedures are used), without requiring substantial changes in the underlying protocols and/or formats associated with the entities being transported, and with at most modest increases in communications regarding network status. Preferably, this procedure will not lead to “cycles”, in which an entity visits the same node twice. Preferably, this procedure can be modified so that separate entities moving from node A to node B do not arrive out of order. 
     SUMMARY OF THE INVENTION 
     These needs are met by the invention, which provides an approach that accounts for link/path traffic and/or link/path costs on a network with N nodes (N≧2). Consider a particular node i in the network that is directly connected to J other nodes, labeled or numbered j=j 1 , j 2 , . . . , jJ. A “baseline proportion vector” p(i;μ), having J components, is associated with node i, where p(i;μ) is used to determine how to transport an entity, having a characteristic or set of characteristics designated by μ, from node i. Examples of such characteristics g include the originating source, the ultimate destination, the routing priority, and the time the entity was last transported from the source node. 
     In one embodiment of the invention, a J(μ)-component “applied proportion vector” p*(i;μ) is determined from p(i;μ) so that no entity is ever transported from the node i to a connected node j if the jth component p*(i;μ) j =0. With this determination employed for all link selections for an entity, that entity will not visit any node more than once before the entity reaches its destination node. In one embodiment of the invention, two more J(μ)-component vectors, Target(i;n(μ);μ) and Actual(i;n(μ);μ) are computed and used, where n=n(μ) is a sequence number or count at the node i that may depend upon one or more of the characteristics μ of the entity being transported and the associated routing request. At each node i for an entity with characteristic μ, for selected values of n(μ), a new determination is made of the i-to-j link, j=j′(μ), with the largest value of the difference Target(i;n(μ);μ)−Actual(i;n(μ);μ). The entity is transported along the i-to-j′(μ) link. The vectors Target(i;n(μ);μ) and Actual(i;n(μ);μ)) are computed iteratively from the relations Target(i;n(μ);μ)=α(μ)·Target(i;n(μ)−1;μ)+β(μ)·p*(i;μ) and Actual(i;n(μ)+1;μ)=α(μ)·Actual(i;n(μ);μ)+β(μ)·Sent(i;j′(μ);n(μ);μ). Here, α(μ) and β(μ) are selected real number and Sent(i;j′(μ);n(μ);μ) is a J(μ)-component vector with component j=j′(μ) having the value 1 and all other components having the value 0. The number J(μ) of nodes directly connected to node i, the originating source node A and/or the ultimate destination node B can vary with the characteristic μ. 
     The objective of the invention is to optimize some measure of network performance, such as overall entity throughput, amount of discarded entities, entity errors, misdelivered entities, minimum bandwidth or other corresponding effort required, financial cost of transporting an entity, average or minimum or maximum time delay for entity delivery, priority level for an entity, or some other measure of quality of service (QOS) on the network. Currently, many such measures have associated procedures that are used in actual networks. However, most existing procedures do not provide an optimal performance according to the associated measures. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates operation of the invention in one embodiment. 
     FIG. 2 is a flow chart of a procedure for practicing the invention. 
     FIGS. 3 and 4 illustrate generalizations of the invention beyond single link-to-link connections. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     FIG. 1 illustrates a plurality of nodes A(μ), B(μ), i, jq (q=1, 2, . . . , J(μ); J(μ)≧2), where node A(μ) (e.g., a computer network router) is an ultimate source of an entity (e.g., a packet or a physical good) to be transported on a network and node B(μ) is an ultimate destination of the entity. Each entity has one or more associated characteristics, indicated collectively by the entity characteristic symbol μ. The node i, which may but need not coincide with the node A(μ), is directly connected to each of J=J(μ) distinct intermediate nodes, numbered or labeled j=j1, j2, . . . , jJ(μ), along links i-j that are capable of transporting an entity from node i to node j, and each of these connected nodes j is directly or indirectly connected to the node B(μ) across the network NW. 
     A set of routing procedures collectively determines how each entity is being routed within the network at a given time, with each routing request to a particular node being handled by a single associated routing procedure. A routing procedure that controls node i uses “proportional routing” if, even absent any explicit communication to induce the routing procedure to do so, the procedure will from time to time select different links for two successive identical entities (e.g., at sequence counts n(μ) and n(μ)+1 ) that are requested to be routed through node i in identical fashions. Proportional routing associates with a node and a characteristic μ a non-negative, numerical-valued, (baseline or applied) proportion vector, having one component for each of the J(μ) i-to-j links available to the routing procedure at that node. Preferably, but not necessarily, each component of each (renormalized) proportion vector has a value between 0.0 and 1.0, and the sum of these values at a given node is 1.0. Different nodes&#39; routing procedures may have the same number or a different number of link choices, depending, for example, on the number of links that directly connect that node with other nodes that are constituents of paths that lead from that node to the ultimate destination node B(μ). 
     Where the procedure implements “probabilistic proportional routing”, in response to each routing request, the procedure randomly or pseudo-randomly chooses one of its J(μ) available links, with a probability that is proportional to (or equal to) a component, j=j*(μ), of an applied proportion vector, discussed in the following, whose component values are non-negative and represent a measure of probabilities that the routing procedure will choose to transport the entity along the i-to-j link. Where the procedure implements “deterministic proportional routing”, in response to each routing request, the procedure chooses one of its allowed routing options, according to a set pattern, based on its previous routing choices and on the applied proportion vector components for that node. The entity is transported on the i-to-j*(μ) link. 
     In a first deterministic routing procedure, referred to as “hard-masked proportional routing”, a node i and entity characteristic μ have associated therewith a baseline proportion vector p(i;μ), having J(μ) components, a value z(i;μ), and a value z(j;μ) for each node j that is directly connected to the node i, where μ refers to the characteristic(s) associated with the entity to be transported through the node i. In the simplest situation, the presence of the characteristic μ may be ignored and all entities transported through the node i may be treated in the same manner. 
     For example, z(i;μ) (and, similarly, z(j;μ)) may represent a cost function value for transport of an entity from the node i to the ultimate destination node B. In particular, where the network is a computer network, z(i;μ) (and, similarly, z(j;μ)) may represent an estimated minimum time or average time or maximum time required for an entity to move from node i to the destination node B(μ). 
     More than one baseline proportion vector p(i;μ) may be associated with the node i, with the particular baseline vector used at a particular time being determined by many factors. These factors may include characteristics of the entity itself, as reflected in the characteristic μ (e.g., its originating source node and/or its ultimate destination node), time, sequence count, etc. Similarly, more than one value z(i;μ) (and similarly z(j;μ)) may be associated with the node i at any one time, with each value z(i;μ) being determined, for example, by one or more characteristics of the entity itself. 
     The components p(i;μ) j  of the baseline proportion vector p(i;μ) may be chosen in many ways. As an example, each node-to-node link i-j (j=j 1 , j 2 , . . . , jJ(μ)) may have a J(μ)-component associated current entity traffic value vector T(i;μ), having components T(i;j;μ) that are a measure of traffic, and/or a J(μ)-component associated current cost value vector C(i;μ), having components C(i,j;μ) that are a measure of cost of entity transport, from node i to node j, or from node i to node j to the destination node B(μ). 
     One or both of the vectors T(i;μ) and C(i;μ) can be used to determine the baseline proportion vector p(i;μ). As an example, with each link L=L(i,j) in a path from the node i to the ultimate destination B(μ), the jth component of a baseline proportion vector p(i;μ) corresponding to choice of that link is associated that reflects one or more environmental conditions. For example, the jth component of the baseline vector p(i;μ) may be given by the value of a jth component F j (T(i;μ)) of a vector-valued function of the entity traffic value T(i;μ) observed or measured or estimated or calculated, where the function F j (T(i;μ)) has certain desired properties, such as boundedness (e.g., 0≦F j (T(i;μ))≦1) and/or monotonicity. For example, if an overall goal of the procedure is to balance the amount of traffic on each link or each path, the function F j (T(i;μ)) may be chosen to be monotonically decreasing for increasing values of the traffic value T(i;j;μ) when all other components T(i;j;μ) (j≠j′(μ)) are unchanged. 
     As another example, the jth component of the baseline vector p(i;μ) may be given by the value of a jth component G j (C(i;μ)) of a vector-valued function of the cost C(i;μ) observed or measured or estimated or calculated. This cost, referenced to a particular i-to-j link, may be the maximum or minimum or average bandwidth available (if the entity is to be transported along that link, and if the entity is information expressed in an electronic format), the time delay associated with use of that link, the entity discard rate (at current usage of that link), the entity error rate, the entity misdelivery rate, a financial cost associated with use of that link to transport an entity, priority level of an entity, or some other suitable measure of cost of using the particular link. Again, the function G j (C(i;μ)) is preferably monotonically decreasing for increasing values of the cost value C(i;j;μ) when all components C(i,j;μ) (j≠j′(μ)) are unchanged. 
     As an alternative, these components of the baseline proportion vector (in a hard-masked approach and a soft-masked approach discussed in the following) may be set by a human being overseeing the network or may be taken to be an automatically calculated estimate of the cost assessed, or time required, for transport of an entity from the node i along the i-to-j link to the destination node B(μ). The baseline proportion vector components can also be determined as a result of a reinforcement learning process. 
     A J(μ)-component applied proportion vector (APV) p′(i;μ) is constructed from the baseline proportion vector p(i;μ) as follows. For each node j that is directly linked to the node i, each vector component p′(i;μ) j  for which z(j;μ)≧z(i;μ) is set equal to 0, unless z(j;μ)≧z(i;μ) for all j; for each node j that is directly linked to the node i, each vector component p′(i;μ) j  for which z(j;μ)&lt;z(i;μ) is set equal to p(i;μ) j . If z(j;μ)≧z(i;μ) for all j, set p′(i;μ) j ″=ρ(i;μ) j ″ (a selected positive constant, for example, ρ(i;μ) j ″=1) for all nodes j″ for which z(j″;μ)=min 1≦j≦J(μ)  {z(j;μ)} and p′(i;μ) j =0 for all other nodes j. 
     If, for all nodes i in the network, no entity is ever transported along a link j for which p′(i;μ) j =0, and it is true that for all nodes j directly connected to node i, z(j;μ)≧z(i;μ), then no cycle of nodes is possible for which an entity can visit a node twice. The applied proportion vector p′(i;μ) j  is modified to a re-normalized applied proportion vector (RAPV) with components p″(i;μ) j =p′(i;μ) j /R, where the real number R is chosen so that the sum of the component values p″(i;μ) j  is 1.0. 
     In a second deterministic routing procedure, referred to as “soft-masked proportional routing”, a node i first calculates an applied proportion vector with components p′(i;μ) j  as in hard-masked proportional routing. Each non-zero component p′(i;μ) j  is multiplied by a coefficient |z(i;μ)−z(j;μ)| m , to produce a component p′″(i;μ) j , where m=m(i,j;μ) is a selected real number (preferably, but not necessarily, non-negative), such as m=0.25 or m=1.0. The number m(i,j;μ) may be set as a result of a learning process and/or may depend upon the node numbers i and/or j and/or entity characteristic μ. In one version, m(i,j;μ) is the same constant for all nodes i and j and all characteristics μ. This multiplication produces a modified applied proportion vector (MAPV), p′″(i;μ), for transport of an entity from node i, with at least one non-zero component. Note that the choice m=0 reproduces the hard-masked routing procedure for z(i;μ)≠z(j;μ). 
     A re-normalized modified applied proportion vector (RMAPV) with components p″″(i;μ) j =p′″(i;μ) j /R′ is calculated, where the real number R′ is chosen so that the sum of the component values P″″(i;μ) j  is 1.0. If the exponent m(i,j;μ) is the same for all nodes j, the form |z(i;μ)−z(j;μ)| m  is the unique multiplicative factor that is invariant under translation and/or resealing of the vectors z(i;μ) and z(j;μ). Thus, for example, if the values z(i;μ) and z(j;μ) measure time duration, neither the units in which they measure time nor the units in which these values are initialized will affect the RMAPV. 
     In a probabilistic approach, the component values p*(i;μ) j  (hard-masked or soft-masked) are interpreted as probabilities, and one link L(i;j) is randomly chosen according to these component values. In a deterministic approach, the link L(i,j) chosen for the routing is uniquely determined, based on the component values p*(i;μ) j  (preferably renormalized) and other information available to the routing procedure. 
     In one embodiment of the invention for deterministic routing, computation of a response to a routing request proceeds as indicated in the flow chart in FIG.  2 . In step  21 , a node i possesses (or receives) an entity (with associated characteristic μ) to be transported and an associated routing request for the first time and determines, or is provided with, the number J(μ) of links to the node i, as discussed in the preceding. In step  23 , the J(μ)-component applied proportion vector p″(i;μ) (hard-masked) or p″″(i;μ) (soft-masked), again referred to collectively herein as p*(i;μ), is computed. 
     In step  25 , two J(μ)-component vectors with all components equal to 0, referred to as Target(i;−1;μ) and Actual(i;0;μ), are provided. A sequence index n=n(μ) (=0, 1, 2, . . . ; initially 0) corresponds to the nth time at which an entity with characteristic μ and associated routing request is received at, or possessed by, the node i. In step  27 , the system determines, for all μ, whether an entity with a characteristic μ has been received at node i. If the answer to the question in step  27  is “no”, the system continues to recycle through step  27 . If the answer to the question in step  27  is “yes” for some characteristic μ, the system calculates a new Target vector in step  29 , 
     
       
         Target( i;n (μ);μ)=α(μ)·Target( i;n (μ)−1;μ)+β(μ)· p *( i ;μ),  (1) 
       
     
     where Target(i;n(μ)−1;μ) typically (but not necessarily) represents the Target vector for the preceding entity with characteristic μ processed at node i and α(μ) and β(μ) are selected numbers. Except when special (“gap”) circumstances are set for the characteristic μ, the system determines and stores a vector component j=j′(μ) that has a maximum difference 
     
       
         Δ TA   j =Target( i;n (μ);μ) j −Actual( i;n (μ);μ) j ,  (2) 
       
     
     in step  31 . In step  33 , the system modifies all the components j of the vector Actual(i;n(μ)+1;μ), using the selected real numbers α and β: 
     
       
         Actual( i;n (μ)+1;μ) j =α(μ)·Actual( i;n (μ);μ) j +β(μ)·Sent( i;j ′(μ); n (μ);μ) j ,  (3) 
       
     
     where Sent(i,j′(μ);n(μ);μ) is a J(μ)-component vector with a value 1 for the j=j′(μ) component and a value 0 for all other components. 
     In step  35 , the routing procedure at node i chooses a selected link j=j′(μ) in response to the present routing request, stores the value j=j′(μ) and associated entity characteristic μ, optionally modifies the entity, and transports the entity along the i-to-j′(μ) link. In step  37 , the routing procedure increments n(μ) (n(μ)→n(μ)+1) and (optionally) returns to step  27 . Note that several different sequence indices n(μ) may be used here, one for each different entity characteristic μ, but only one sequence index n(μ) is processed in steps  29 - 37  for each entity that arrives at node i. 
     Note that the number of links directly connected to the new node j=j′(μ) may be the same as, or different from, the number of links directly connected to the node i. Other deterministic routing procedures may also be combined with the construction of the baseline proportion vector and applied proportion vector to determine the i-to-j link to be used. 
     Special (“gap”) circumstances allow entities with the same characteristic μ to be assuredly transported by the same path, to preserve order in arrival of the entities at a single destination. Where an i-to-j′(μ) link has been selected, a gap circumstance may be extant until a reset instruction or command is received for the entity or entities with characteristic μ being routed, throughout a selected temporal interval, or throughout a consecutive sequence of routing requests received at node i. A gap circumstance may be extant for none, one or many entities with a particular characteristic μ and may be initiated by receipt of a gap activation signal, which may be contained in a packet header or otherwise associated with an entity that arrives at node i. 
     When gap circumstances such as these occur, step  31  in the flow chart in FIG. 2 is skipped and the most recently stored value of the selected link j=j′(μ) for the entity characteristic μ, rather than the most recently calculated value j=j′(μ), is used to specify the link to be used to transport the entity. A gap circumstance, during which step  31  is skipped, may be interleaved with situations where all of the steps  21 - 37 , including step  31 , are performed. 
     A gap circumstance can be terminated by any of several occurrences, including: (1) passage of a time interval having at least a selected threshold length since a selected number of one or more entities with the same characteristic μ was transported from the source node, (2) transport of a selected number of one or more entities with the same characteristic μ from the node i, (3) passage of a time interval having at least a selected threshold length since a selected number of one or more entities with the same characteristic μ was transported from the node i, (4) arrival of a selected number of one or more entities with the same characteristic μ at the destination node, and (5) reception at the node i of a selected gap inactivation signal. 
     When one or more selected events occurs, the values Target(i;n(μ);μ) and/or Actual(i;n(μ);μ) may be “reset”, by replacing these vectors by their initial values, Target(i;−1;μ) and/or Actual(i;0;μ), before restarting computation of their values by successive iterations. For example, the specified reset event may occur: (1) when the entity received at node i has been transformed in some manner at node i or at a preceding node in a path from source node A(μ) to destination node B(μ), (2) when the character of part or all of the network changes, or (3) when a reset activation signal is received or provided at node i. This change in part or all of the network character might arise, for example, from a change in the topology of the network, from a substantial change in network traffic, from a transition of one or more processing nodes from an “up” condition to a “down” condition, or from a transition of one or more processing nodes from a “down” condition to an “up” condition. Reset may also occur in response to receipt at node i of a reset message in a “header” or other message associated with an entity received at node i. 
     The preceding development identifies the i-to-j′(μ) link for entity transport, using a maximum difference of two J(μ)-component vectors, Target and Actual, that are determined iteratively. This development may be generalized to determination of the component j=j′(μ) that provides an extremum value (maximum or minimum) of a function H(u,v) that depends upon the component differences, u j −v j , of two J(μ)-component vectors u and v, where 
     
       
           u   j =Target( i;n (μ);μ) j ,  (4) 
       
     
     
       
           v   j =α(μ)·Actual( i;n (μ);μ) j +β(μ)·Sent( i;j ′(μ); n (μ);μ) j ,  (5) 
       
     
     and where Sent(i,j′(μ);n(μ);μ) is a J(μ)-component vector with a value 1 for the j=j′(μ) component and a value 0 for all other components. For example, the function H(u,v) may be any of the following relationships, or similar relationships involving formation of an extremum (maximum or minimum) with respect to choice of the component j=j′(μ):                  H        (     u   ,   v     )       =     max        {         a   1          (       u   1     -     v   1       )       ,       a   2          (       v   2     -     v   2       )       ,   …              ,       a     J        (   μ   )              (       u     J        (   μ   )         -     v     J        (   μ   )           )         }         ,           (6A)                   H        (     u   ,   v     )       =     min        {         a   1          (       u   1     -     v   1       )       ,       a   2          (       v   2     -     v   2       )       ,   …              ,       a     J        (   μ   )              (       u     J        (   μ   )         -     v     J        (   μ   )           )         }         ,           (6B)                 H        (     u   ,   v     )       =       ∑     j   =   1       J        (   μ   )                  a   j          (       u   j     -     v   j       )       2               (6C)                   H        (     u   ,   v     )       =       ∑     j   =   1       J        (   μ   )                f   j          (       u   j     -     v   j       )           ,           (6D)                                
     where the coefficients a j  are selected non-negative numbers and f j  is a monotonically increasing function of the indicated variables. In the relationships ( 6 A), ( 6 B), ( 6 C) and ( 6 D), the node number, j=j′(μ), that provides an extremum value (maximum or minimum, as the context requires) is chosen as the node for entity transport. Many functions, H(u,v), in addition to those set forth in ( 6 A)-( 6 D), can be used to determine a node, j=j′(μ), for entity transport. 
     The preceding development has explicitly restricted itself to single links directly connecting node i to other nodes j. This development extends to a situation where one or more of the connections from node i consists of a collection of two or more consecutive links, joined end-to-end between a first node i 1  and a-second node i 2 , as illustrated in FIG.  3 . In this extended situation, the collection of links shown in FIG. 3 is treated as a single super-link. In a new network, including such super-links joining nodes in the original network, the previously developed routing procedure is applied to select a new super-link in the same manner used to select a link in the flow chart in FIG.  2 . 
     The development can be further generalized by replacing consideration of individual nodes between which an entity is to be transported, with consideration of entity states between which the entity is to be transformed. In this generalization, the underlying network provides a graph of allowed state transitions of the entity, where two entities may have the same source but different destinations or the same destination, as illustrated in FIG.  4 . The ultimate destination node now specifies the desired terminal state of the entity. Hard or soft masking can be used to ensure that no entity revisits the same state twice. Proportional routing can be used to manage interference effects between multiple entities that undergo transformations, especially effects that arise when two or more entities share the same state or state transition. The originally described single link embodiment is recovered by associating the state of an entity with a node that possesses or receives the entity. 
     The routing procedure developed here provides at least four types of benefits. First, computational speed is increased, because the procedure uses primarily sums and multiplications for next link selection and because use of a weight α satisfying 0&lt;α&lt;1 assigns progressively less weight to past values of a variable such as the Target vector. Second, flexibility is improved, because of avoidance of cycling between nodes, because of provision for “gap” circumstances to preserve order of entity arrival, because of provision for reset of routing variable values, and because of provision for a choice of hard or soft masking. Third, recovery from a shut-down or error event is improved through provision of reset and similar sub-procedures. Fourth, flexibility is also improved through provision for entity transformation and/or change of entity characteristics at a node.