Multiplex communications – Wide area network – Packet switching
Patent
1992-03-18
1993-11-23
Safourer, Benedict V.
Multiplex communications
Wide area network
Packet switching
370 943, H04L 1256
Patent
active
052650928
ABSTRACT:
A method of providing loop free and shortest path routing of data packets in a network having a plurality of switches, routing messages for communicating network topology information between the switches, a plurality of links connecting the switches and a plurality of channels connecting the switches to the links. The loop free routing of data packets is achieved through modifications to known link state packet (LSP) routing protocols and permits each switch to inform adjacent switches in the network of the information in the switch's database used to compute forwarding tables. A switch uses a received LSP to compute a forwarding table and informs neighboring switches on attached links of the routing change. The switch discards any subsequent data packets whose path would be affected by the changed routing information. The discarding of data packets continues until the switch receives notification from each adjacent switch affected by the changed routing information that all affected routing paths have been recalculated and the forwarding table of each affected switch has been updated. Thus, while adjacent switches temporarily contain inconsistent LSP databases and possibly inconsistent forwarding tables, the looping of data packets is prevented. Shortest path routing for data packets from a source endnode to a destination endnode is achieved by assuring that the first switch to forward the packet is on the shortest path to the packet's destination endnode. A source endnode transmits a data packet with an appropriate destination header and the determination of the actual routing path is performed transparently to endnodes. A data packet reaches its destination endnode by following the shortest path possible based on the network topology as represented in the database of the first switch that forwards it.
REFERENCES:
patent: 4320500 (1982-03-01), Barberis et al.
patent: 4399531 (1983-08-01), Grande et al.
patent: 4463445 (1984-07-01), Grimes
patent: 4577313 (1986-03-01), Sy
patent: 4644532 (1987-02-01), George et al.
patent: 4679189 (1987-07-01), Olson et al.
patent: 4736363 (1988-04-01), Aubin et al.
patent: 4771424 (1988-09-01), Suzuki
patent: 4780873 (1988-10-01), Mattheyeses
patent: 4799215 (1989-01-01), Suzuki
patent: 4825206 (1989-04-01), Brice, Jr. et al.
patent: 4956841 (1990-09-01), Judeinstein et al.
patent: 5018133 (1991-05-01), Tsukakoshi et al.
S. G. Finn, Resynch Procedures and a Fail-Safe Network Protocol, IEEE Transactions on Communications, vol. COM-27, No. 6, pp. 840-845 Jun. 1979.
P. A. Humblet and S. R. Soloway, A Fail-Safe Layer for Distributed Network Algorithms and Changing Topologies, submitted for publication.
W. D. Sincoskie and C. J. Cotton, Extended Bridge Algorithms for Large Networks, Bell Communications Research.
J. M. McQuillan, I. Richer and E. C. Rosen, An Overview of the New Routing Algorithm for the ARPANET.
R. Perlman, An Algorithm for Distributed Computation of a Spanning Tree in an Extended LAN. Digital Equipment Corp. 1985 ACM.
R. Perlman, Fault-Tolerant Broadcast of Routing Information, 1983 Elsevier Science Publishers B. V. (North-Holland).
Lauck Anthony G.
Soloway Stuart R.
Varghese George
Digital Equipment Corporation
Safourer Benedict V.
LandOfFree
Synchronization mechanism for link state packet 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 Synchronization mechanism for link state packet routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Synchronization mechanism for link state packet routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1855414