Method and apparatus to speed up the path selection in a packet

Details Method and apparatus to speed up the path selection in a packet Method and apparatus to speed up the path selection in a packet

1994-07-22

1996-02-13

Chin, Wellington

Multiplex communications

Wide area network

Packet switching

370 943, H04L 1256

Patent

active

054916909

ABSTRACT:
Currently, routing algorithms compute all the available paths in the network, from a source node to a destination node before selecting the optimal route. The route computation is often time and resource consuming. Some paths are not acceptable due to the particular geographical configuration of the network. In the real world, large transport networks are not fully meshed. The present invention is based on the observation that networks are usually built around a hierarchical structure. A set of nodes, interconnected by high throughput lines, are used to build a `Backbone` (401) with a high degree of meshing to allow the redundancy and reliability required by the user. The other nodes or `local` nodes (404) are attached to one or several backbone nodes. It is the network designer responsibility, at the configuration time to define for each node what is its attribution: backbone (402) or local node (404). The list of the node attributions appears in the topology table (306) and is updated each time a node is added to or dropped from the network. The routing algorithm can take advantage of the particular network topology to drastically reduce the complexity of paths computation. For a given connection, only a limited number of nodes are eligible and are taken in account by the algorithm in the optimal route search. The object of the invention is to split the network into backbone and local nodes to speed up the path selection.

REFERENCES:
patent: 4827411 (1989-05-01), Arrowood et al.
patent: 5081620 (1992-01-01), Girard et al.
patent: 5115433 (1992-05-01), Baran et al.
patent: 5142531 (1992-08-01), Kirby
patent: 5216591 (1993-06-01), Nemirovsky et al.
patent: 5233604 (1993-08-01), Ahmadi et al.
patent: 5265092 (1993-11-01), Soloway et al.
Computer Networks, vol. 1, 1977, Amsterdam NL pp. 155-174 L. Kleinrock et al.
"Hierarchical Routing for Large Networks" paragraphs 1 and 2 IEEE Transactions on Computers, vol. 38, No. 8, Aug. 1989, New York, US pp. 1059-1074 XP47576.
W. T. Tsai et al "An Adaptive Hierarchical Routing Protocol" paragraphs I & II.A IEEE Jounral on Selected Areas in Communication, vol. 7, No. 8 Oct. 1989, New York US pp. 1243-1252 XP126342.
V. R. Sakensa "Topological Analysis of Packet Networks" Paragraphs I, II, and III.

Affiliated with

Also associated with

Rating

Method and apparatus to speed up the path selection in a packet 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 to speed up the path selection in a packet , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to speed up the path selection in a packet will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-244947