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

• US 5,491,690 A
• Filed: 07/22/1994
• Issued: 02/13/1996
• Est. Priority Date: 07/30/1993
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Alfonsi, Jean-Pierre, Lebizay, Gerald, Maurel, Olivier, Galand, Claude
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Patel, Ajit
• Application Number:
  US08/279,373
• Time in Patent Office: 571 Days
• Field of Search: 370/54, 370/58.1, 370/60, 370/60.1, 370/79, 370/84, 370/94.1, 370/94.3, 340/825.03, 340/827, 364/300, 364/200, 364/282.1
• US Class Current: 370/404
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

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.

Claims

1. A network access node (300) for a packet switching communication network (200) having a plurality of nodes (201 . . . 208) interconnected with transmission links (209), said network access node including:

means for receiving and transmitting data packets (301, 302,

     304),

a network topology database manager for storing and updating data representing the characteristics and attributes of nodes and transmission links, said data forming a topology database defining the network configuration (306),

link selection means responsive to data contained in said topology database for identifying usable links for forming data paths with a destination node located in the network, said link selection means further including means for identifying each link in the network as either a backbone link or a local link, means for selecting as usable for a path determination all backbone links, means for selecting as usable for a path determination all local links attached to the network access node and to the destination node, and means for discarding as not usable for a path determination all other links, and means for storing link identifiers identifying selected links in the topology database; and

means for determining, for a connection request to the destination node, an optimal routing path from said access node to the destination node using only said identified selected links.

2. A network access node according to claim 1 wherein said routing path determination further includes means for implementing a modified Bellmann-Ford algorithm in making the optimal routing path determination.

3. A method for selecting a routing path in a packet communication network (200) comprising a plurality of nodes (201 . . . 208) interconnected with transmission links (209), said method being performed in a network access node and including the steps of:

storing and updating data in a network topology database, said data representing characteristics and attributes of the nodes and transmission links and defining the network configuration,

selecting links usable for forming data paths between the network access node and a destination node in the network, said selecting step including the further steps of using data stored in the network topology database to identify each link in the network as either a backbone link or a local link, selecting as usable for a path determination all backbone links, selecting as usable all local links attached to the network access node and to the destination node, discarding as not usable for a path determination all other links, and storing in the topology database link identifiers identifying all selected links,

determining, for a connection request to the destination node, an optimal routing path from said access node to the destination node using only the identified selected links.

4. A method for selecting a routing path according to claim 3 wherein said routing path determining step includes the further step of determining the optimal routing path through application of a modified Bellman-Ford algorithm.