Masked proportional routing

Abstract

Distributed approach for determining a path connecting adjacent network nodes, for probabilistically or deterministically transporting an entity, with entity characteristic &mgr; from a source node to a destination node. Each node i is directly connected to an arbitrary number J(&mgr;) of nodes, labeled or numbered j=j , j , . . . , jJ(&mgr;). In a deterministic version, a J(&mgr;)-component baseline proportion vector p(i;&mgr;) is associated with node i. A J(&mgr;)-component applied proportion vector p*(i;&mgr;) is determined from p(i;&mgr;) to preclude an entity visiting a node more than once. Third and fourth J(&mgr;)-component vectors, with components iteratively determined by Target(i;n(&mgr;);&mgr;) =&agr;(&mgr;)·Target(i;n(&mgr;)−1;&mgr;) +&bgr;(&mgr;)·p*(i;&mgr;) and Actual(i;n(&mgr;);&mgr;) =&agr;(&mgr;)·Actual(i;n(&mgr;)−1;&mgr;) +&bgr;(&mgr;)·Sent(i;j′(&mgr;);n(&mgr;)−1;&mgr;) , are computed, where n(&mgr;) is an entity sequence index and &agr;(&mgr;) and &bgr;(&mgr;) are selected numbers. In one embodiment, at each node i, the node j=j′(&mgr;) with the largest vector component difference, Target(i;n(&mgr;);&mgr;) ′−Actual (i;n(&mgr;);&mgr;) ′, 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.