Method of caching routes in asynchronous transfer mode PNNI networks

• US 6,192,043 B1
• Filed: 05/01/1998
• Issued: 02/20/2001
• Est. Priority Date: 05/01/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Rochberger, Haim
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/071,067
• Time in Patent Office: 1,026 Days
• Field of Search: 370/216, 370/217, 370/218, 370/230, 370/237, 370/238, 370/244, 370/254, 370/255, 370/351, 370/355, 370/389, 370/390, 370/392, 370/395, 370/396-401, 709/238, 709/239, 709/241, 709/242, 709/243
• US Class Current: 370/351
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A caching method to greatly reduce the time to calculate routes based on the well known Dijkstra routing algorithm. A first embodiment is suitable for use in applications where only a single class of call is in use. A second embodiment is suitable for use where multiple classes of calls are is simultaneous use. A sequential number field and a global variable holding a sequential count are maintained by each node. When a node is put on the PATH list, the global sequential count variable is copied to the sequential number field for that particular node descriptor. Subsequently, when a route to destination node is to be calculated, for each node marked as a destination, the global sequential count variable and the node descriptor sequential number field are checked if they are equal. If they are, it means that a route has already been calculated to the destination which was already determined to be optimum.

Claims

1. In a network based on the Private Network to Network Interface (PNNI) standard and consisting of a plurality of nodes, a method of caching routes generated using the Dijkstra algorithm into a cache maintained on each node, said Dijkstra algorithm utilizing a PATH list in the calculation of routes, said method supporting a single class of call, said method comprising the steps of:

maintaining a cache sequence number on each node;

maintaining a global cache sequence count on each node;

setting said cache sequence number equal to said cache sequence count when the node is placed onto said PATH list; and

constructing a routing list directly from parent pointers, defining a route from a destination node to a local node, if said cache sequence number equals said cache sequence count.

2. The method according to claim 1, further comprising the step of clearing said cache.

3. The method according to claim 2, wherein the step of clearing said cache comprises the step of incrementing said global cache sequence count.

4. The method according to claim 1, further comprising the step of clearing said cache, comprising the steps of:

incrementing said global cache sequence count;

setting said global cache sequence count to one when it reaches its maximum count; and

setting said cache sequence number on each node to zero when said global cache sequence reaches its maximum count.

5. The method according to claim 1, further comprising the steps of:

initializing said cache sequence number in each node to zero; and

initializing said global cache sequence count to one.

6. In a network based on the Private Network to Network Interface (PNNI) standard and consisting of a plurality of nodes, a method of caching routes generated using the Dijkstra algorithm into a plurality of caches maintained on each node, each cache supporting a different class of call, said Dijkstra algorithm utilizing a PATH list in the calculation of routes, said method comprising the steps of:

maintaining N sets of variables consisting of a cache sequence number, a parent pointer and a global cache sequence count for each node wherein each set of variables is associated with a single class of call to be supported;

setting said cache sequence number, within a particular set of variables corresponding to a particular class of call, equal to said cache sequence count when the node is placed onto said PATH list; and

constructing a routing list directly from parent pointers, defining a route from a destination node to a local node, if said cache sequence number, within a particular set of variables corresponding to a particular class of call, equals said cache sequence count within the set of variables thereof.

7. The method according to claim 6, further comprising the step of clearing said plurality of caches.

8. The method according to claim 7, wherein the step of clearing said cache comprises the step of incrementing the global cache sequence counts within all N sets of variables.

9. The method according to claim 6, further comprising the step of selectively clearing one of said plurality of caches associated with a particular class of call.

10. The method according to claim 9, wherein the step of clearing said cache comprises the step of selectively clearing the cache for a particular class of call by incrementing the global cache sequence count associated with the set of variables for that particular class of call.

11. The method according to claim 6, further comprising the step of clearing each of said plurality of caches, comprising the steps of:

incrementing the global cache sequence count within the set of variables associated with each class of call;

setting said global cache sequence count within the set of variables associated with each class of call to one when it reaches its maximum count; and

setting said cache sequence number within the set of variables associated with each class of call on each node to zero when said global cache sequence reaches its maximum count.

12. The method according to claim 6, further comprising the step of clearing one of said plurality of caches, comprising the steps of:

incrementing the global cache sequence count associated with one selected class of call;

setting said global cache sequence count associated with one selected class of call to one when it reaches its maximum count; and

setting said cache sequence number associated with one selected class of call on each node to zero when said global cache sequence reaches its maximum count.

13. The method according to claim 6, further comprising the steps of:

initializing the cache sequence number associated with one class of call in each node to zero; and

initializing the global cache sequence count associated with one class of call to one.

14. The method according to claim 6, further comprising the steps of:

initializing the cache sequence number associated with all classes of calls in each node to zero; and

initializing the global cache sequence count associated with all classes of calls to one.