Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Alternate path routing
Patent
1997-02-19
2000-04-04
Harrell, Robert B.
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Alternate path routing
G06F 1300
Patent
active
060473312
ABSTRACT:
A method and apparatus for generating first and second tree topologies for any source node in a network which can be represented as a node or an edge redundant graph, such that any node in the graph remains connected to the source node via at least one tree even after the failure of a node or an edge. This technique provides a recovery mechanism upon detection of a failure in a network.
REFERENCES:
patent: 4527012 (1985-07-01), Caplan et al.
patent: 5210871 (1993-05-01), Lala et al.
patent: 5243704 (1993-09-01), Bary et al.
patent: 5271014 (1993-12-01), Bruck et al.
patent: 5327427 (1994-07-01), Sandesara
patent: 5333130 (1994-07-01), Weissmann et al.
patent: 5408462 (1995-04-01), Opoczynski
patent: 5515367 (1996-05-01), Cox, Jr. et al.
patent: 5544330 (1996-08-01), Bither et al.
patent: 5550805 (1996-08-01), Takotori et al.
patent: 5572513 (1996-11-01), Yamamoto et al.
patent: 5680546 (1997-10-01), Chiaretti et al.
Information and Computation 79, 43-59 (1988), "The Multi-Tree Approach to Reliability in Distributed Networks", Alon Itai and Michael Rodeh.
"A Quick Method for Finding Shortest Pairs of Disjoint Paths", Suurballe, et al., Networks, vol. 14 (1984) 325-336, 1984.
"Dynamics of Distributed Shortest-Path Routing Algorithms", Zaumon, et al., SRI International, 333 Ravenswood Avenue, Menlo Park, CA 94025, 1991 ACM 0-89791-444-9/91/0008/0031, pp. 31-43.
"Edge-Disjoint Branchng in directed Multigraphs", Shiloach, Computer Science Department, Stanford University, Standord, CA 94305, vol. 8, No. 1, Jan. 1979, pp. 24-27.
"Design and Performance of Convergence Routing on Multiple Spanning Trees", Yener, et al., 1994 IEEE, pp. 169-175.
"Optimal Routing in Circuit Switched Communication Networks", Gersht, et al., IEEE, vol. 37, No. 11 Nov. 1989, pp. 1203-1211.
"A Linear-Time Algorithm for Finding a Sparse .kappa.-Connected Spanning Subgraph of a .kappa.-Connected Graph.sup.1 ", Nagamochi.sup.2, et al., Algorithmica (1992) 7: 583-596.
"On Algorithms for Enumerating All Circuits of A Graph", Mareri, et al. SIAM J. Comput., vol. 5, No. 1, Mar. 1976, pp. 90-99.
"Finding Maximal Link Disjoint Paths in a Multigraph", Whalen, et al., Tellabs, Inc. Research Center, 3702 N. Main Bldg. 2, Mishawaka, IN 46545, 1990 IEEE, pp. 403.6.1-403.6.5.
"Disjoint Paths in a Network", Suurballe, Netowrks, 4: 125-145, 1974 by John Wiley & Sons, Inc.
"An Optimal Spare-Capacity Assignment Model for Survivable Netowrks with Hop Limits", Herzberg, et al., Telecom Australia Research Laboratories, 770 Blackburn Rd., Clayton vic. 3168, Australia, Globecom '94, vol. 3, pp. 1601-1606.
"Implementation of Self-Healing Function in ATM Networks", Kawamura, et al., Journal of Network & Systems Management, vol. 3, No. 3, 1995, pp. 243-265.
"Feasibility Study of a High-Speed SONET Self-Healing Ring Architecture in Future Interoffice Networks", Wu. et al. Nov. 1990, IEEE Communications Magazine, vol. 28, No. 11, pp. 33-51.
"Dimensioning of Self-Healing Rings and Their Interconnections", Shi, et al., School of Engineering & Computer Science, University of Texas at Dallas, EC 33, 2601 North Floyd Rd, Richardson, TX 75080, 1993 IEEE, pp. 1579-1583.
"An Algorithm for Designing Rings for Survivable Fiber Networks", Wasem, IEEE Transactions on Reliability, vol. 40, No. 4, Oct. 1991, pp. 428-432.
"A Capacity Comparison for SONET Self-Healing Ring Networks". Shyur, et al., Telecommunication Labs. DGT Taiwan R.O.C., 6F No. 16, Chinan Road. Sec. 2, Taipei 100, 1993 IEEE, pp. 1574-1578.
"Virtual Path Routing for Survivable ATM Networks", Murakami, IEEE/ACM Transactions on Networking, vol. 4, No. 1 Feb. 1996. pp. 22-39.
"Multicast Tree Generation in Networks With Asymmetric Links", Ramanathan, IEE/ACN Transactions on Networking, vol. 4, No. 4, Aug. 1996, pp. 558-568.
"Address Management and Connection Control for Multicast Communication Applications", Eleftheriadis, et al., Department of Electrical Engineering & Center for Telecommunications Research Columbia University, New York, NY 10027, pp. 386-393.
"Adaptive Multicast Routing in Single Rate Loss Networks", Hwang, Department of Computer Sciences & Information Engineering National Chung Cheng University, Chia-Yi, Taiwan, R.O.C., 1995 IEEE, pp. 571-578.
"Steiner Tree Problems", Hwang et al., Networks, vol. 22 (1992) 55-89.
"Steiner's problem in graphs: heuristic methods", Stefan Voss, Discrete Applied Mathematics 40 (1992) 45-72 North-Holland.
"A Good Algorithm for Edge-Disjoint Branching", Tarjan, Information Processing Letters, vol. 3, No. 2, Nov. 1974, pp. 51-53.
"Steiner Problem in Networks: A Survey", Winter, Networks, vol. 17 (1987) 129-167.
"Dynamic Steiner Tree Problem*", Imase et al., SIAM J. Disc. Math., vol. 4, No. 3. pp. 369-284, Aug. 1991.
"Path-Distance Heuristics for the Steiner Problem in Undirected Networks", Winter et al., Algorithmica (1992) 309-327.
"Routing of Multipoint Connections", Waxman, IEEE Journal on Selected Areas in Communications, vol. 6. No. 9, Dec. 1988.
"Routing to Multiple Destinations in Computer Networks", Bharath-Kumar et al., IEEE Transactions on Communications. vol. Com-31, No. 3, Mar. 1983.
"ARIES: A Rearrangeable Inexpensive Edge-based On-line Steiner Algorithm", Bauer et al., Computer Engineering Department University of California, Santa Cruz, CA 95064.IEEE, 1996.
"An SST-Based Algorithm for the Steiner Problem in Graphs", Beasely, Networks, vol. 19 (1989) 1-16.
"Design of Survivable Communications Networks under Performance Constraints", Newport, et al., IEEE Transactions on Reliability, vol. 40, No. 4, Oct. 1991.
"Forests, Frames, and Games: Algorithms for Matroid Sums and Applications.sup.1 ", Gabow, et al. Algorithmica, (1992) 7: 465-497.
"Routing Multipoint SONET Connections Using Virtual Paths in an ATM Network", Ammar, et al.,College of Computing, Georgia Institute of Technology, Aatlanta, Georgia 30332, 1993, IEEE, pp. 1c.4.1-1c.4.8.
"Broadband in the Local Loop", Phillips, Nov. 1994, pp. 37-42.
"Near Optimal Spare Capacity Planning in a Mesh Restorable Network", Grover, et al., Globecom '91, Phoenix, Arizona, Dec. 2-5, 1991, pp. 2007-2012.
Autonet: A High-Speed, Self-Configuring Local Area Network Using Point-to-Point Links, Schroeder, et al., IEEE Journal on Selected Areas in Communications, vol. 9, No. 8, Oct. 1991.
"Case Studies of Survivable Ring, Mesh and Mesh-Arc Hybrid Networks", Grover, Globecom '92, pp. 633-638.
"Decreasing Survivable Fiber network Cost Using Optical Switches", Wu, et al., IEEE Global Telecommunications Conference & Exhibition, Hollywood, Florida, Nov. 28-Dec. 1, 1988, vol. 1 of 3.
"Survivable Network Architectures of Broad-Band Fiber Optic Networks: Model and Performance Comparison", Wu. et al., Journal of Lightwave Technology, vol. 6. No. 11, Nov. 1988.
"Strategies and Technologies for Planning a Cost-Effective Survivable Fiber Network Architecture Using Optical Switches", Wu, et al., Journal of Lightwave Technology, vol. 8, No. 2, Feb. 1990.
"Graph Theoretic Models for Multicast Communications", North-Holland, Computer Networks and ISDN Systems 20 (1990) 95-99.
"Multicasting for Multimedia Applications", Kompella, Computer Sysems Laboratory Department of Computer Science and Engineering University of California, San Diego, La Jolla, CA 92093-0114.
"Greedy Algorithms for the On-Line Steiner Tree and Generalized Steiner Problems", Westbrook et al., Dept. of Computer Science, Yale University, New Haven, CT 06520-2158, Department of Operations Research, Yale University, New Haven, CT 06520-0162, pp. 622-633.
"Comparison of Dynamic Multicast Routing Algorithms for Wide-Area Packet Switched (Asynchronous Transfer Mode) Networks", Kadirire et al., University College London, Computer Science Department, Gower Street, London WC1E 6BT.
"Distributed Algorithms for Multicast Path Setup in Data Networks", Bauer et al., Computer Engineering Department University of CA, Santa Cruz, CA 95064, 1995 IEEE.
"Degree-Constrained Multicasting in Point-to-Point Networks", Bauer et al., Computer Engineering Department University of California, Santa Cruz, CA 95064, 1995 IEEE.
"Distributed Algorithms for Multicast Path Set
Barry Richard A.
Finn Steven G.
Gallager Robert G.
Medard Muriel
Daly Christopher S.
Harrell Robert B.
Massachusetts Institute of Technology
LandOfFree
Method and apparatus for automatic protection switching 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 automatic protection switching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for automatic protection switching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-374568