Method and apparatus for managing virtual circuits and routing packets in a network/subnetwork environment

• US 5,854,899 A
• Filed: 05/09/1996
• Issued: 12/29/1998
• Est. Priority Date: 05/09/1996
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Waldfogel, Asher, Smith, Andrew H., Salkewicz, William M., Callon, Ross W.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): VU, VIET DUY
• Application Number:
  US08/647,295
• Time in Patent Office: 964 Days
• Field of Search: 395/200.5, 395/200.53, 395/200.54, 395/200.6, 395/200.61, 395/200.62, 395/200.68, 395/200.65, 395/200.69, 395/200.72, 370/229, 370/235, 370/237, 370/352, 370/396, 370/398, 370/400, 370/404
• US Class Current: 709/238
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5631 Resource management and allocation
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/22 Alternate routing

Abstract

A system for managing virtual circuits and determining proper routing of packets in a network environment. The network includes a connection-oriented subnetwork and an arrangement of routers coupled to the connection-oriented subnetwork. The system determines paths to each exit router by considering all possible paths through the connection-oriented subnetwork. The system also determines paths to each exit router by considering existing virutal circuits through the connection-oriented subnetwork. Finally, the system determines and establishes a most beneficial new virtual circuit for the network. Additionally, the rate at which new virtual circuits are established may be regulated by the system.

Claims

1. A method for managing virtual circuits in a network having a connection-oriented subnetwork, said method comprising the steps of:

determining existing paths to an exit router;

determining existing path qualities associated with each of said paths to said exit router;

determining an optimal path quality associated with an optimal path to said exit router; and

determining a benefit and a cost associated with rerouting an existing virtual circuit; and

rerouting said existing virtual circuit if said optimal path quality exceeds said existing path qualities and said benefit exceeds said cost associated with modifying an existing virtual circuit.

2. The method of claim 1 wherein said routers and said connection-oriented subnetwork utilize a single link state routing protocol.

3. The method of claim 1 wherein the step of rerouting an existing virtual circuit includes establishing a new virtual circuit to said exit router.

4. A method for man aging the establishment of new virtual circuits in a network having a connection-oriented subnetwork, said method comprising the steps of:

determining a number of outstanding virtual circuit setup requests;

determining a number of existing virtual circuits in said network;

comparing said number of outstanding virtual circuit requests and said number of existing virtual circuits with a maximum value; and

establishing a new virtual circuit if said maximum value is less than said number of outstanding virtual circuit requests and said number of existing virtual circuits.

5. The method of claim 4 wherein said method for managing the establishment of new virtual circuits is performed as a background process.

6. The method of claim 4 wherein the step of establishing a new virtual circuit is performed in response to receiving a virtual circuit setup request.

7. The method of claim 4 wherein the step of establishing a new virtual circuit includes determining and establishing a highest priority virtual circuit.

8. The method of claim 4 wherein a first maximum value is associated with said number of outstanding virtual circuit setup requests and a second maximum value is associated with a sum of said outstanding virtual circuit setup requests and said number of existing virtual circuits.

9. The method of claim 4 further including the step of detecting a failure of the attempt to establish a new virtual circuit.

10. A method for determining whether to establish a new virtual circuit in a network having a connection-oriented subnetwork, said method comprising the steps of:

determining a benefit associated with establishing the new virtual circuit;

determining a cost associated with establishing the new virtual circuit;

comparing said benefit of the new virtual circuit with said cost of the new virtual circuit; and

establishing the new virtual circuit if said benefit exceeds said cost.

11. The method of claim 10 wherein the step of establishing the new virtual circuit utilizes a timer for controlling a frequency at which new virtual circuits are established.

12. The method of claim 10 wherein the step of establishing the new virtual circuit includes:

determining a current value of a virtual circuit setup timer;

determining a timer threshold value; and

establishing the new virtual circuit if said current value of said virtual circuit setup timer exceeds said timer threshold value.

13. The method of claim 10 wherein said benefit is calculated by determining a reduction in cost to each router and a traffic level at each router.

14. The method of claim 10 further including the step of detecting a failure of the attempt to establish a new virtual circuit.

15. An apparatus for managing the establishment of new virtual circuits in a network having a connection-oriented subnetwork, said apparatus comprising:

a determination mechanism configured to determine a number of outstanding virtual circuit setup requests, and wherein the determination mechanism is further configured to determine a number of existing virtual circuits in said network;

a comparison mechanism configured to compare said number of outstanding virtual circuit requests and said number of existing virtual circuits with a maximum value; and

a virtual circuit establishment mechanism configured to establish a new virtual circuit if said maximum value is less than said number of outstanding virtual circuit requests and said number of existing virtual circuits.