Masked proportional routing

Details Masked proportional routing Masked proportional routing

1999-08-05

2003-06-10

Ton, Dang (Department: 2666)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S231000, C370S395210, C370S401000, C709S241000, C709S241000

Reexamination Certificate

active

06577601

ABSTRACT:

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'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'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'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

Affiliated with

Also associated with

Rating

Masked proportional routing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Masked proportional routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Masked proportional routing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3100944