Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-06-12
2001-07-10
Geckil, Mehmet B. (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S238000
Reexamination Certificate
active
06260072
ABSTRACT:
The invention concerns adaptive routing in packet networks, in order to reduce network congestion, and to optimize selected parameters, such as throughput and end-to-end packet delays.
BACKGROUND OF THE INVENTION
A simplified network will be explained, in order to provide background regarding basic concepts and terminology.
FIG. 1
illustrates a network containing nodes A-F and links L
1
-L
9
. The nodes are physical stations, which contain one, or more, computers, and associated equipment. For example, a university's computer system may act as a node. The nodes receive data from other nodes, or from external sources (not shown). The nodes may process the data, but in the present context, their most important function is to store the data temporarily, and forward the data to other nodes.
Links are data transmission channels, used to carry data between nodes. For example, a common telephone line represents one exampletype of link; a satellite communication link and an optical fiber link represents two others.
A common characteristic of networks is that every node is not necessarily connected to every other node. For example, in
FIG. 1
, node A is not connected to node F. If these two nodes wish to transmit data to each other, they must find a path, such as the combination of links L
1
+L
7
or the combination of links L
2
+L
6
.
However, not all paths are equally desirable. One reason is that each link imposes a time delay, and these time delays are not uniform.
FIG. 2A
provides an example of time delays for the network of
FIG. 1
, and indicates that the combination L
1
+L
7
, mentioned in the previous paragraph, represents a time delay of 6 units, while the combination of L
2
+L
6
represents a longer time delay of 7 units.
In many cases, it is preferred to utilize the path imposing the smallest overall time delay. Well-known algorithms, such as the Dijkstra algortithm, are available for ascertaining these shortest-time paths, for all pairs of nodes in a given network.
FIG. 2B
provides an example of a table of shortest-time paths for the network of FIG.
1
. Some spaces are left blank because they represent redundancy: for example, the time from B to C is the same as that from C to B.
One mode of utilizing such tables resides in “next-hop” routing. In next-hop routing, each node does not refer to the entire contents of the shortest-path table, but, instead, utilizes an abbreviated table, termed a “routing table,” which is derived from the shortest-path table.
FIG. 3
illustrates the next-hop routing table 2 used by node F. If node F wishes to transmit data to node A, node F routes the data to node B, as indicated. Node B, according to its own next-hop routing table (not shown), then routes the data to node A. The indirect path is F-to-B-to-A, using the link pair L
7
+L
1
of
FIG. 2A
, consistent with the shortest-path table of
FIG. 2B
, for the node-pair (F, A).
One problem with next-hop routing, as just described, is that, as a matter of probability, the links having the shortest delay times are those most likely to appear in the shortest-time table of
FIG. 2B
, and thus most likely to be used in the routing tables. Consequently, under conditions of high data traffic, the nodes at the ends of these links can become congested. When congestion occurs, data traffic at these nodes can become stalled temporarily.
The congestion, in effect, causes the transit times shown in
FIG. 2A
to increase. However, the nodes continue to route their packets along the same paths, despite these increases, because the routing tables do not change: they are static. Static routing tables do not accommodate network congestion well, because they do not take into account the variable nature of network traffic.
SUMMARY OF THE INVENTION
In one form of the invention, data packets are routed in a network according to next-hop routing tables, which are derived based on measured packet delays and link utilization between nodes. The tables are updated as the delays or utilization change.
REFERENCES:
patent: 4556972 (1985-12-01), Chan et al.
patent: 5121383 (1992-06-01), Golestani
patent: 5253248 (1993-10-01), Dravida et al.
patent: 5313454 (1994-05-01), Liron et al.
patent: 5377327 (1994-12-01), Jain et al.
patent: 5412654 (1995-05-01), Perkins
patent: 5467345 (1995-11-01), Cutler, Jr. et al.
patent: 5491801 (1996-02-01), Jain et al.
patent: 5495479 (1996-02-01), Gallaand et al.
patent: 5506847 (1996-04-01), Shobatake
patent: 5557607 (1996-09-01), Holden
patent: 5570346 (1996-10-01), Shur
patent: 5583861 (1996-12-01), Holden
patent: 5583862 (1996-12-01), Callon
patent: 5594734 (1997-01-01), Worsley et al.
patent: 5600630 (1997-02-01), Takano et al.
patent: 5666360 (1997-09-01), Chen et al.
patent: 5671222 (1997-09-01), Chen et al.
patent: 5671445 (1997-09-01), Gluyas et al.
patent: 5699361 (1997-12-01), Ding et al.
patent: 5740164 (1998-04-01), Liron
patent: 5790536 (1998-08-01), Mahany et al.
patent: 5802278 (1998-09-01), Isfeld et al.
patent: 5805816 (1998-09-01), Picazo, Jr. et al.
patent: 5812526 (1998-09-01), Chang et al.
patent: 5828844 (1998-10-01), Civanlar et al.
patent: 5844887 (1998-12-01), Oren et al.
patent: 5905712 (1999-05-01), Cresswell et al.
patent: 5910942 (1999-06-01), Grenot et al.
patent: 5920566 (1999-07-01), Hendel et al.
patent: 5920568 (1999-07-01), Kurita et al.
patent: 5930254 (1999-07-01), Liron et al.
patent: 5940372 (1999-08-01), Bertin et al.
patent: 5963546 (1999-10-01), Shoji
patent: 5970232 (1999-10-01), Passint et al.
patent: 5996021 (1999-11-01), Civanlar et al.
patent: 6016306 (2000-01-01), Le Boudec et al.
Carter et al., Measuring Bottleneck Link Speed in Packet-Switched Networks, Computer Science Department, Boston University, Mar. 1996.*
J. Moy., Network Working Group, RFC 1583, OSPF Version 2, Proteon, Inc., Mar. 1994.
Geckil Mehmet B.
Lucent Technologies Inc
Vaughn, Jr. William C.
Welte Gregory A.
LandOfFree
Method and apparatus for adaptive routing in packet networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for adaptive routing in packet networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for adaptive routing in packet networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531609