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

• US 6,934,249 B1
• Filed: 05/30/2002
• Issued: 08/23/2005
• Est. Priority Date: 04/01/1997
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bertin, Olivier, Galand, Claude, Nicolas, Laurent, Brun, Gerard, Maurel, Olivier
• Primary Examiner(s): TON, DANG T
• Application Number:
  US10/158,624
• Time in Patent Office: 1,181 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.1, 370/407, 370/408, 370/394, 370/225, 370/224, 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 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/746 Reaction triggered by a failure
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/829 Topology based

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. Due to high dynamicity of the traffic on transmission links, it is important to select a routing path according to a fully up-to-date information on all network resources. The simpler approach is to calculate a new path for each new connection request. This solution may be very time consuming because there are as many path selection operations as connection set up operations. On another hand, the calculation of paths based on an exhaustive exploration of the network topology, is a complex operation which may also take an inordinate amount of resources in large networks. Many of connections originated from a network node flow to the same destination network node. It is therefore possible to take a serious benefit in reusing the same already calculated paths for several connections towards the same node. The 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 in a computer network comprising:

storing in a routing database possible pre-calculated connection paths;

responding to a connection request by determining whether said routing database contains a stored connection path 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; and

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

2. The method as in claim 1 further comprising:

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.

3. The method as in claim 2 further comprising:

calculating the alternative path so that at least one of the links is not in an associated existing path.

4. The method as in claim 2 further comprising:

creating the alternative path from a set of links excluding the links in an associated existing path.

5. The method as in claim 1 further comprising:

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.

6. The method as in claim 1 further comprising:

responding to a failure of a path used to establish a connection by retrieving an alternative path associated with the failed path from the routing database and re-establishing the connection using the retrieved alternative path.

7. 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.

8. Electromagnetic signals traveling over a computer network comprising:

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

9. A node in a computer network comprising:

a route controller adapted to

store in a routing database possible pre-calculated connection paths;

respond to a connection request by determining whether said routing database contains a stored connection path satisfying requirements of the connection request;

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

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

a “

time-to-live”

counter to periodically initiate recalculation of pre-calculated connection paths stored in the routing database.

10. The apparatus of claim 9 further comprising:

for each connection path stored in the routing database, said route controller calculates at least one alternative connection path having transmission links and storing said alternative path in the routing database for possible future use.

11. The apparatus of claim 10 further comprising:

at least one of the links on the alternative path is not included in an associated existing path.

12. The apparatus of claim 10 further comprising:

the alternative path is created from a set of links excluding the links in an associated existing connecting path.

13. The apparatus as in claim 9 further comprising:

said route controller is further adapted to

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

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

remove 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.

14. The apparatus of claim 12 further comprising:

said route controller is further adapted to respond to a failure of a path used to establish a connection by retrieving an alternative path associated with the failed path from the routing database and re-establishing the connection using the retrieved alternative path.

15. A node in a computer network comprising:

means for storing in a routing database possible pre-calculated connection paths;

means for responding to a connection request by determining whether said routing database contains a stored connection path satisfying requirements of the connection request;

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

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

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

16. The apparatus of claim 15 further comprising:

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

17. The apparatus of claim 16 further comprising:

at least one of the links on the alternative path is not included in an associated existing path.

18. The apparatus of claim 16 further comprising:

the alternative path is created from a set of links excluding the links in an associated existing connecting path.

19. The apparatus as in claim 15 further comprising:

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

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

means for 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 pre-determined period of time, and (ii) when the network configuration and traffic configurations change.

20. The apparatus of claim 18 further comprising:

means for responding to a failure of a path used to establish a connection by retrieving an alternative path associated with the failed path from the routing database and re-establishing the connection using the retrieved alternative path.