Method of admission control and routing of virtual circuits

• US 6,175,870 B1
• Filed: 11/30/1995
• Issued: 01/16/2001
• Est. Priority Date: 11/30/1995
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Plotkin, Serge, Kamath, Anil P., Gawlick, Rainer, Ramakrishnan, Kajamalai Gopalaswamy
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US08/565,737
• Time in Patent Office: 1,874 Days
• Field of Search: 395/200.15, 395/200.1, 709/200, 709/227, 709/238, 370/351, 370/408, 370/409, 379/219, 379/901, 710/100
• US Class Current: 709/227
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5629 Admission control
• CPC Class Codes: H04L 2012/563 Signalling, e.g. protocols, reference model
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method of admitting and routing switched virtual circuit requests in a network first finds a set of routing paths on which a requested VC may be routed by using a two step process. The method uses a cost function based on a parameter related to the number of hops in a subset of VC connections previously made in the network to determine potential routing paths on which the VC can be routed at a cost below a specified threshold. The method next checks to determine which potential routing paths comprise links and nodes with sufficient resources to accommodate the request. Paths satisfying both steps are output as a set of routing paths and then a second criterion is used to select a path from the set on which to route the request. In a distributed routing system, the inventive method uses a local network state to determine the cost function and the set of routing paths. The method further updates local state information at nodes along a path selected from the set and permits other paths from the set to be selected for routing a requested VC if the previously selected path has insufficient resources to accommodate the request.

Claims

1. In a network comprising a set of nodes connected by a set of links, said network characterized by a network state, wherein a set of virtual circuits has been previously routed through said network, a method for operating said network comprising the steps of:

receiving a request to route a virtual circuit on a path through said network between an origination node and a destination node,

determining the load on each link in a subset of said set of links in said network due to said request, and

determining a respective cost for routing said request over possible paths between said origination and said destination nodes, said cost a function of the network state wherein;

the possible paths comprise links in said subset of said set of links; and

the step of determining a routing cost for each possible path comprises;

(a) obtaining a number L which is derived, in part, by counting the links in at least some of the virtual circuits that have already been routed,

(b) using L to determine the value of a link-cost parameter μ

; and

(c) evaluating a respective cost factor for each link of the current path, wherein said cost factor is a function of μ

.

2. The method of claim 1 wherein each node in said set of nodes and each link in said set of links has associated resources and further comprising the steps of:

selecting as potential paths in a set of potential routing paths, those possible paths having respective costs below a threshold, and

selecting as routing paths in a set of routing paths those potential routing paths comprising nodes and links having sufficient associated resources for routing said request.

3. The method of claim 2 further comprising the step of:

selecting a path from said set of routing paths according to a criterion.

4. The method of claim 3 wherein said criterion is a minimum hop routing criterion.

5. The method of claim 3 wherein said network is a centralized network.

6. The method of claim 3 wherein said request is received at a request processor.

7. The method of claim 3 further comprising the steps of:

routing said request on the selected path, and

updating said network state based on the routed selected path.

8. The method of claim 3 wherein said request is received at said origination node, wherein said network state is a local network state at said origination node and wherein said network is a decentralized network.

9. The method of claim 8 further comprising the step of:

determining if sufficient resources are available at nodes and links of the selected path to route said request, wherein the determining is based on local state information at nodes along said selected path.

10. The method of claim 9 further comprising the step of:

updating local state information at said origination node based on local information at nodes along said selected path.

11. The method of claim 9 further comprising the step of:

updating local state information at a node along said selected path based on local information at other nodes along said selected path.

12. The method of claim 9 further comprising the steps of:

routing said request on said selected path if sufficient resources are available, and

determining another set of routing paths if sufficient resources are not available.

13. The method of claim 9 further comprising the steps of:

routing said request on said selected path if sufficient resources are available, and

selecting a different routing path from said set of routing paths if sufficient resources are not available.

14. The method of claim 1 wherein said request for a virtual circuit is a request for a switched virtual circuit and wherein said request specifies a holding time for the requested virtual circuit.

15. The method of claim 14 wherein said cost function is a function of the holding time for said requested virtual circuit.

16. A method for operating a network of the kind that comprises a set of nodes connected by a set of links, and that in operation can be characterized by a network state, and wherein there are resources associated with each of said nodes and links, the method comprising, after a set of virtual circuits has been previously routed through the network, the steps of:

receiving a request to route a virtual circuit on a path through the network between an origination node and a destination node;

determining the load that fulfillment of the request would place on each link in a subset of the link set; and

determining a respective cost for routing the request over possible paths between the origination and destination nodes, wherein;

the possible paths comprise links in the link subset;

the cost is a function of the network state;

for each possible path, the cost includes a component for each link of said path, wherein each said cost component is a nonlinear function of the network state and of a parameter related to the number of hops for a subset of the previously-routed virtual-circuit set; and

the method further comprises;

selecting as potential paths in a set of potential routing paths, those possible paths having respective costs below a threshold, and

selecting as routing paths in a set of routing paths those potential routing paths comprising nodes and links having sufficient associated resources for routing said request,

selecting a path from said set of routing paths according to a criterion, and

routing said request on the selected path.

17. The method of claim 16 wherein said criterion is a minimum hop routing criterion.

18. The method of claim 16 further comprising the step of:

updating said network state based on the routed selected path.

19. A method of routing a request for a virtual circuit through a network, comprising:

at an origination node, selecting a path from a set of routing paths, wherein;

the selected path comprises nodes and links, the path-selection is carried out in response to a virtual-circuit request, and the path-selection is responsive to incomplete state information;

attempting to route the virtual circuit on at least a portion of the selected path;

while attempting to route the virtual circuit, collecting local state information from a node or nodes on at least one said portion, thereby to evaluate resources available at least at some nodes and links of the selected path; and

if sufficient resources are found to be available, completing the routing of the virtual circuit on the selected path.

20. The method of claim 19, further comprising the step of determining another set of routing paths if sufficient resources are not available to route said request.

21. The method of claim 19, further comprising the step of selecting a different routing path from said set of routing paths if sufficient resources are not available to route said request.

22. The method of claim 19, wherein the request for a virtual circuit is first received at an origination node, and the method further comprises the step of sending the collected local state information to the origination node.

23. The method of claim 19 wherein said selected path comprises an origination node and further comprising the step of:

updating local state information at said origination node along said selected path.

24. The method of claim 23 wherein said network is a decentralized network.