US5491690A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus to speed up the path selection in a packet switching network
Assignee: Cisco Technology Inc
•
Filing: 1994-07-22
•
Granted: 1996-02-13
•
Expires: 2014-07-22
Abstract
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.
Inventors
- 👤 Jean-Pierre Alfonsi
- 👤 Claude Galand
- 👤 Gerald Lebizay
- 👤 Olivier Maurel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 23:40
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/04
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
215 words
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.
Claim 2
Dependent Claim
215 words
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.
Claim 3
Dependent Claim
29 words
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.
Claim 4
Independent Claim
196 words
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.
Claim 5
Independent Claim
196 words
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.
Claim 6
Dependent Claim
34 words
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.
References Cited (Backward Citations)
US4827411A
Cited
US5081620A
Cited
US5142531A
Cited
US5115433A
Cited
US5216591A
Cited
US5265092A
Cited
US5233604A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-02-12 | 1999-08-14 | 2000-02-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-12 | 2003-08-14 | 2004-02-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-12 | 2007-08-14 | 2008-02-13 | $7700.00 | Window Closed / Lapsed |