Method and system for minimizing the connection set up time in high speed packet switching networks

• US 6,400,681 B1
• Filed: 04/01/1997
• Issued: 06/04/2002
• Est. Priority Date: 06/20/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bertin, Olivier, Galand, Claude, Maurel, Olivier, Nicolas, Laurent, Brun, Gerard
• Primary Examiner(s): RAO, SEEMA SRINIVAS
• Application Number:
  US08/834,679
• Time in Patent Office: 1,890 Days
• Field of Search: 370/254, 370/392, 370/396, 370/397, 370/351, 370/255, 370/400, 370/401, 370/410, 370/238, 370/256, 370/395, 370/407, 370/408, 370/394, 370/235, 370/229, 370/237, 370/352, 370/252, 370/395.2, 370/218, 370/395.32, 709/238, 709/239, 709/241, 709/242
• US Class Current: 370/218
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/206 Real Time traffic
• CPC Class Codes: H04L 49/253 using establishment or release of connections between ports
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element

Abstract

The present invention is directed to a high speed packet switching network and, in particular to a method and system for minimizing the time to establish a connection between an origin and a destination node. A path calculated at the time the connection is requested is recorded in a Routing Database and updated each time a modification occurs in the network. Furthermore, alternate paths for supporting non-disruptive path switch on failure or preemption, and new paths towards potential destination nodes can be calculated and stored when the connection set up process is idle. These last operations are executed in background with a low processing priority and in absence of connection request.

Claims

1. A method for establishing a connection between an origin node and a destination node in a packet switching communication network comprising a plurality of nodes interconnected by transmission links, said method comprising the steps of:

storing in a routing database possible pre-calculated connection paths in the form of stored connection paths with their characteristics;

responding to a connection request by determining whether said routing database contains a stored connection path in the routing data base satisfying requirements of the connection request;

if a satisfactory stored connection path is found in the routing database, establishing a connection using the stored satisfactory connection path;

if a satisfactory stored connection path is not found in the routing database, calculating a new connection path, establishing a connection using the new connection path and storing the new connection path in the routing database;

for each connection path stored in the routing database, calculating at least one alternative connection path having transmission links and storing said alternative path in the routing database for possible future use; and

periodically recalculating pre-calculated connection paths stored in the routing database.

2. A method as set forth in claim 1 wherein at least one of the transmission links on the alternative connection path is not included in the associated stored path, wherein each node includes an adapter for receiving and transmitting data packets.

3. A method as set forth in claim 1 where the alternative path is created from a set of links excluding the links in the associated stored connecting path adjacent the origin node and the destination node.

4. A method as set forth in any one of claims 1 through 3 further including the steps of:

maintaining a topology database for storing network configuration and traffic characteristics;

maintaining a record of when each path stored in the routing database was last used; and

removing a path from the routing database in response to one of (i) when the maintained record shows that the path has not been used for at least a predetermined period of time, and (ii) when the network configuration and traffic configurations change.

5. A method as set forth in claim 3 further including a step of responding to a failure of a path used to establish a connection by retrieving the alternative path associated with the failed path from the routing database and re-establishing the connection using the retrieved alternative path.

20. A node for carrying out the method according to claim 1 or claim 5 or claim 12.

21. A packet switching communication network comprising at least one node according to claim 20.

22. A computer-readable medium comprising:

instructions and data written thereon, said instructions and data containing information for execution in a node for the practice of the method of claim 1 or claim 5 or claim 12.

23. Electromagnetic signals travelling over a computer network comprising:

said electromagnetic signals carrying information for execution in a node for the practice of the method of claim 1 or claim 5 or claim 12.

6. For use in a node in a packet switching communication network having a plurality of nodes interconnected by transmission links, each node having an adapter for receiving and transmitting data packets, a connection setup system for establishing a connection between an origin node and a destination node, said connection setup system comprising:

a routing database for storing previously established paths between different ones of said nodes including characteristics of the previously established connection paths;

a path selection subsystem responsive to a connection request for determining whether said routing database contains a previously established stored connection path which is suited to cater requirements of the connection request, said path selection subsystem being responsive to a determination that a suitable path exists in said routing database to establish the requested connection using the previously established connection path, said path selection subsystem being responsive to a determination that no suitable path exists in said routing database to calculate a new connection path, minimizing connection setup delay and suited to the connection requirements, to establish the requested connection using the new path and to store the new path in the routing database to create a stored connection path, said path selection subsystem also being responsive to the existence of a stored connection path to calculate and store at least one alternative connection path associated with each stored connection path in the routing database; and

a path recomputation subsystem for periodically recalculating stored connection paths stored in the routing database.

7. A connection setup subsystem as set forth in claim 6 wherein the path selection subsystem further includes link selection logic for establishing the alternative path using a set of links excluding one or more of the links making up the associated stored path.

8. A connection setup subsystem as set forth in claim 7 wherein the set of links used for establishing the alternative path excludes the links in the associated stored path adjacent the origin node and the destination node.

9. A system for a packet switching communication network having a plurality of nodes interconnected by transmission links, said system including a connection setup system for establishing a connection between an origin node and a destination node, comprising:

a routing database for storing previously established paths between different ones of said nodes;

a path selection subsystem responsive to a connection request for determining whether said routing database contains a previously established stored path satisfying the requirements of the connection request, said path selection subsystem being responsive to a determination that a suitable path exists in said routing database to establish the requested connection using the previously established path, said path selection subsystem being responsive to a determination that no suitable path exists in said routing database to calculate a new path minimizing connection setup delay and satisfying the connection requirements, to establish the requested connection using the new path and to store the new path in the routing database, said path selection subsystem also being responsive to the existence of a stored path to calculate and store an alternative path associated with each stored path in the routing database; and

periodically recalculating the paths stored in the routing database.

10. A system as set forth in claim 9 wherein the path selection subsystem of said connection setup system further includes link selection logic for establishing the alternative path using a set of links excluding one or more of the links making up the associated stored path.

11. A system as set forth in claim 10 wherein the set of links used for establishing the alternative path excludes the links in the associated stored path adjacent the origin node and the destination node.

12. A method of determining an optimal path between an origin node and a destination node in a packet switching communication network comprising a plurality of nodes interconnected with transmission links, said method involving the steps of:

for each connection request, selecting a pre-calculated path satisfying said connection request in the routing database;

if no pre-calculated path satisfying the connection request is already stored in the routing database, calculating a path satisfying said connection request and storing said path within the routing database;

recalculating the paths stored in the routing database periodically; and

recalculating the paths stored in the routing database in response to at least one pre-determined event in the network.

13. The method according to claim 12 wherein said at least one pre-determined event in the network is selected from a group consisting of routing requests, traffic variations, and network configuration changes.

14. The method according to claim 12 further comprising the step of calculating, for each pre-calculated path stored in the routing database, at least one alternate path with the same origin node and the same destination node.

15. The method according to claim 13 further comprising the step of calculating, for each pre-calculated path stored in the routing database, at least one alternate path with the same origin node and the same destination node.

16. The method according to claim 13 wherein a pre-calculated path is removed from the routing database after a predetermined period of time without being selected.

17. The method according to claim 13 wherein the steps of:

re-calculating the paths stored in the routing database in response to at least one pre-determined event in the network;

calculating, for each pre-calculated path stored in the routing database, at least one alternate path with the same origin and destination nodes;

calculating paths between the origin node and all possible destination nodes; and

removing pre-calculated paths, are executed in the absence of said connection request.

18. The method according to claim 12 wherein a pre-calculated path is removed from the routing database after a predetermined period of time without being selected.

19. The method according to claim 12 wherein the steps of:

re-calculating the paths stored in the routing database in response to at least one pre-determined event in the network;

calculating, for each pre-calculated path stored in the routing database, at least one alternate path with the same origin and destination nodes;

calculating paths between the origin node and all possible destination nodes; and

removing pre-calculated paths, are executed in absence of said connection request.