Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2007-04-10
2007-04-10
To, Doris H. (Department: 2616)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
09975556
ABSTRACT:
A method is described for routing network traffic based on distance information to provide multiple paths that need not have equal costs. The routing algorithm MPATH of the present method provide loop-free routing at every instant, without the need of internodal synchronization which spans more than a single hop. Paths are computed using shortest distances and predecessor information in the routing computation. The use of multiple-successors allows for load-balancing within the network. The algorithm is both distributed and scalable to large networks due to its use of only one-hop synchronization. A number of procedures are described by way of example, including path computation, main table updating, neighbor table updating, and a multipath (MPATH) algorithm.
REFERENCES:
patent: 5850537 (1998-12-01), Selvidge et al.
Dijkstra, Edsger W., Scholten, C.S.; Termination Detection for Diffusing Compuations, Information Processing Letters, vol. 11, No. 1, pp. 1 thru 4, Aug. 29, 1980.
Farinachi, D.; Introduction to Enhanced IGRP (EIGRP), Cisco Systems, Inc., pp. 1 thru 5, http://www.cisco.com/warp/public/103/1.html, Jul. 1993 (Sep. 21, 2001).
Garcia-Luna-Aceves, J.J.; “Loop-Free Routing Using Diffusing Computations,” IEEE/ACM Transactions on Networking, vol. 1, No. 1, pp. 130-141, Feb. 1993.
Garcia-Luna-Aceves, J.J., Behrens, J.; “Distributed, Scalable Routing Based on Vectors of Link States,” IEEE Journal on Selectred Areas in Communications, pp. 1-13, Oct. 1995.
Garcia-Luna-Aceves, J.J., Murthy, S.; “A Path-Finding Algorithm for Loop-Free Routing,” IEEE/ACM Transactions Networking, pp. 1-22, Feb. 1997.
Garcia-Luna-Aceves, J.J., Spohn, M.; “Scalable Link-State Internet Routing,” Proceedings International Conference on Network Protocols, pp. 1-10, Oct. 1998.
Hedrick, C.; Routing Information Protocol, Network Working Group, Request for Comments 1058, pp. 1-4, Jun. 1988.
Humblet, Pierre A., “Another Adaptive Distributed Shortest Path Algorithm,” IEEE Transactions on Communications, vol. 39, No. 6, pp. 995-1003, Jun. 1991.
Jaffe, Jeffrey M., Moss, Franklin H.; “A Responsive Distributed Routing Algorithm for Computer Networks,” IEEE Transactions on Communication, vol. COM-30, No. 7, pp. 1758-1762, Jul. 1982.
Merlin, Philip M., Segall, Adrian; “A Failsafe Distributed Routing Protocol,” IEEE Transactions on Communications, vol. COM-27, No. 9, pp. 1280-1287, Sep. 1979.
Moy, J.; “OSPF Version 2,” Network Working Group, Request for Comments: 2178, obsoletes RFC: 1583, pp. 1-5, 209-211, Jul. 1997.
Rajagopalan, Balasubramanian and Faiman, Michael; “A New Responsive Distributed Shortest-Path Routing Algorithm,” Reference pages pp. ii and 9, from Internetworking: Research and Experience, vol. 2, pp. 51-69, Mar. 1991.
Segall, Adrian: “Optimal Distributed Routing for Virtual Line-Switched Data Networks,” IEEE Transactions on Communications, vol. COM-27, No. 1, pp. 201-208, Jan. 1979.
Spinelli, John M. and Gallager, Robert G.; “Event Driven Topology Broadcast Without Sequence Numbers,” IEEE Transactions on Communications, vol. 27, No. 5, pp. 468-474, May 1989.
Vutukury, Srinivas, Garcia-Luna-Aceves, J.J.; “A Simple Approximation to Minimum-Delay Routing,” Proceedings of ACM SIGCOMM, pp. 1-12, (1999).
Zaumen, William T. and Garcia-Luna-Aceves, J.J.; “Loop-Free Multipath Routing Using Generalized Diffusing Computations,” Proceedings IEEE INFOCOM, pp. 1-10, Mar. 1998.
Garcia-Luna-Aceves Jose Joaquin
Vutukury Srinivas
O'Banion John P.
The Regents of the University of California
To Doris H.
Wilson Robert W.
LandOfFree
Method for loop-free multipath routing using predecessor... 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 for loop-free multipath routing using predecessor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for loop-free multipath routing using predecessor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3804293