Dynamically controlled routing using dynamic management of intra-link traffic to virtual destination nodes

• US 6,091,720 A
• Filed: 04/24/1997
• Issued: 07/18/2000
• Est. Priority Date: 10/26/1994
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Nortel Networks Corporation
• Inventors: Caron, France, Bedard, Fran.cedilla.ois, Regnier, Jean
• Primary Examiner(s): Horabik, Michael
• Assistant Examiner(s): PHAN, MAN U
• Application Number:
  US08/817,786
• Time in Patent Office: 1,181 Days
• Field of Search: 370/238, 370/254, 370/255, 370/357, 370/400, 370/401, 370/389, 370/392, 370/396, 370/397, 379/221, 379/224, 379/225, 379/220, 379/207
• US Class Current: 370/351
• CPC Class Codes: H04Q 2213/13097 Numbering, addressing
• CPC Class Codes: H04Q 2213/13098 Mobile subscriber
• CPC Class Codes: H04Q 2213/13102 Common translator
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13104 Central control, computer control
• CPC Class Codes: H04Q 2213/13164 Traffic (registration, measurement,...)
• CPC Class Codes: H04Q 2213/13176 Common channel signaling, CCS7
• CPC Class Codes: H04Q 2213/13345 Intelligent networks, SCP
• CPC Class Codes: H04Q 3/002 Details
• CPC Class Codes: H04Q 3/0025 Provisions for signalling
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A DCR telecommunications network comprises a plurality of network switching elements interconnected by circuit groups for carrying calls, and a network processor communicating with the network elements. If it cannot use a direct route to a neighbouring network element, the switching element may access a routing table containing alternate routes which are updated periodically by the network controller. The network functions as a group of nodes interconnected by links. Routing takes place on a node-to-node basis. At least one of the nodes is a virtual destination node, vis. a logical entity corresponding to a group of two or more components which are network elements. A link to the virtual destination node is a set of circuit groups connecting to its components. Final destinations outside the network can be associated with the virtual destination node as an intermediate destination node, thereby allowing a call to exit the DCR network via any of the components rather than via only one Unique Exit Gateway. Where a link to the virtual destination node comprises a plurality of circuit groups, the associated switching element stores proportions for those circuit groups. When attempting to route a call via the link to the virtual destination node, the switching element attempts the circuit groups in dependence upon the proportions. The proportions may be fixed, i.e. computed off-line and stored. Alternatively, the proportions may be updated by the network processor based upon call completion information it receives periodically from the switching elements.

Claims

1. A telecommunications network (31A) comprising:

a plurality of network nodes (A,B,C,O,T,V) and links (A-B,A-O,A-T,B-A,B-O,B-T, . . . ), the network nodes comprising origin nodes (A,B,C,O,T), each comprising a switching element (a,b,c,o,t) capable of routing calls within the network, and destination nodes (A,B,C,O,T,V) serving as destinations for such calls, some of said network nodes being transit nodes (A,B,C,O,T), each transit node being both a destination node and an origin node;

each link interconnecting directly an origin node and a destination node and comprising one or more circuit groups (a-b,o-a,o-b,o-c, . . . ),

each of the switching elements having storage means for routing information, the routing information comprising

(i) a listing of destination nodes;

(ii) associated with each destination node, a corresponding link, where such a link exists;

(iii) for each link, a corresponding group of one or more circuit groups outgoing from the switching element; and

(iv) associated with each destination node, a list of zero or more transit nodes;

each switching element comprising means for translating address data of a call to determine a destination node for the call and

(i) where a link to the destination node exists, attempting to route the call to the destination node via a circuit group that is in the link;

(ii) where a link to the destination node is not available, accessing its routing information to select a transit node and attempting to route the call via a circuit group that is in the link to the transit node;

wherein said listing of destination nodes of at least one of said switching elements, said one of said switching elements being at one of said origin nodes, comprises a virtual destination node (V) representing a group of two or more components (a,b,c), each component being a distinct physical network element, there being one or more distinct circuit groups associated with each component, and the link from said one of said origin nodes to the virtual destination node is a set of circuit groups from the switching element at that one of said origin nodes to the two or more components of the virtual destination node;

said link from said one of said origin nodes to the virtual destination node comprises a plurality of circuit groups, the storage means of said one of said switching elements includes a specified proportion for each of those circuit groups and, when attempting to route a call via said link from said one of said origin nodes to the virtual destination node, said one of said switching elements attempts the circuit groups in dependence upon the specified proportions; and

said one of said switching elements is arranged, in attempting to route a call via said link to the virtual destination node, to;

(i) determine the set S of all circuit groups with a non-zero proportion in said plurality of circuit groups;

(ii) determine whether or not the set S is empty;

(iii) cause the call to overflow if the set is empty;

(iv) if the set is not empty, make a weighted random selection of one of the circuit groups of the set S, and attempt to route the call via such circuit group;

(v) if the selected circuit group does not have a circuit idle, remove the selected circuit group from the set S; and

(vi) repeat steps (ii) through (v) until the call is carried or all circuit groups in the set have been exhausted and the call overflowed.

2. A network as claimed in claim 1, further comprising network processor means (25A) for updating the routing information, the network processor means being coupled to all of said switching elements by a data communications network (24A) whereby, periodically, each of said switching elements communicates to the network processor means information about network conditions local to the switching element and receives from the network processor means alternate routing information including recommended transit nodes, the network processor means computing alternate routing information in dependence upon the information communicated thereto by all of the switching elements and periodically updating the information identifying transit nodes.

3. A network as claimed in claim 2, wherein, when computing alternate route recommendations, the network processor means takes into account full availability of all of the links and, where a link comprises a plurality of circuit groups, takes into account all of the circuit groups of that link.

4. A network as claimed in claim 3, wherein the network processor means is arranged to determine safe idle circuits for said links by:

(i) storing for each link a protective allowance previously computed for that link, the protective allowance preserving capacity in the link for direct traffic;

(ii) computing, from these protective allowances and from current link utilization, a reservation value for each circuit group of each link;

(iii) computing, from these reservation values and from the number of idle circuits reported by switching elements of origin nodes, the number of unreserved (safe) idle circuits on each link;

and further arranged to compute, based on these numbers of safe idle circuits, transit node recommendations for each pair of an origin node and a destination node connected directly by a link from the origin node to the destination node.

5. A network as claimed in claim 4, wherein said link from said one of said origin nodes to the virtual destination node comprises a plurality of circuit groups and the respective storage means of said switching elements each include a specified proportion for each of said circuit groups within each link and, when attempting to route a call via one of such links, the switching element attempts the circuit groups of the link in dependence upon the specified proportions, and wherein the network processor means is arranged to:

(i) distribute the protective allowances of the links that contain circuit group g among their circuit groups such that the reservation RSV_g on circuit group g is equal to ##EQU18## producing a total reservation level RSV₁ for link l equal to;

##EQU19## and;

(ii) compute the number of idle circuits IC₁ as ##EQU20## and the number of safe idle circuits SIC₁ link l as;

space="preserve" listing-type="equation">SIC.sub.1 =IC.sub.1 -RSV.sub.1

where

G₁ is the set of circuit groups of link l;

IC_g is the reported number of idle circuits on circuit group g;

L_g is the set of the links that contain circuit group g;

P_l,g is said proportion used for intra-link traffic distribution for circuit group g of link l;

PA₁ is the protective allowance value for link l, serving to preserve capacity for direct traffic.

6. A network as claimed in claim 4, wherein the network processor means is arranged to:

(i) store the current reservation RSV_l,g for each circuit group of each link; and

(ii) when computing the safe idle circuits;

(A) when the current RSV_l,g is 0, adjust such reservation RSV_l,g to become;

##EQU21## (B) compute the requested reservation RRSV_l,g using the formula;

##EQU22## (C) compute the new reservation RSV_l,g on circuit group g for link l as;

##EQU23## (D) compute the reservation RSV_g on circuit group g as;

##EQU24## (E) compute the number of idle circuits IC₁ for each link l as;

##EQU25## (F) compute the number of safe idle circuits SIC₁ for link l as equal to;

space="preserve" listing-type="equation">SIC.sub.1 =IC.sub.1 -RSV.sub.1

where;

G₁ is the set of circuit groups of link l;

#G₁ is the number of circuit groups in link l;

IC_g is the reported number of idle circuits on circuit group g;

L_g is the set of the links that contain circuit group g; and

PA₁ is the protective allowance value for link l, serving to preserve capacity for direct traffic.

7. A network as claimed in claim 1, further comprising means for updating the proportions automatically to take account of current link utilization and current ability of said components of said virtual destination node to complete calls to the final destinations served by that virtual destination node.

8. A network as claimed in claim 1, further comprising network processor means (25A) coupled to all of said switching elements by a data communications network (24A) whereby, periodically, each of said switching elements communicates to the network processor means information about network conditions local to the switching element and receives from the network processor means alternate routing information including recommended transit nodes, the network processor means computing alternate routing information in dependence upon the information communicated thereto by all of the switching elements and periodically updating the information identifying transit nodes, the network processor means further comprising means for updating the proportions automatically to take account of current link utilization and current ability of said components of said virtual destination node to complete calls to the final destinations served by that virtual destination node, wherein each of said components of said virtual destination node is arranged to report to the network processor means call completion capability information related to its ability to complete calls to the final destinations served by that virtual destination node, and the network processor means is arranged to compute a proportion for each circuit group of said link to said virtual destination node based upon such call completion information, and upon said network conditions reported by said switching elements, and to supply those proportions to the switching element at the origin node connected to said virtual destination node by said link.

9. A network as claimed in claim 8, wherein the call completion capability information communicated to the network processor means is rendered in a similar form and treated in a similar manner by the network processor means regardless of differences between the components, characteristics of calls handled, and final destinations served by those components.

10. A network as claimed in claim 8, wherein the network processor is arranged to determine the proportions such that traffic is distributed among the plurality of circuit groups of said link to the virtual destination node in accordance with idle capacity of the circuit groups of said link and call completion capability of said components of said virtual destination node.

11. A network as claimed in claim 10, wherein the network processor is arranged to compute, for each circuit group of said link to said virtual destination node, a first weight based on its number of idle circuits, and a second weight based on the completion capability of the components of the dynamic virtual destination node, to combine the first and second weights, to transform the combined weights into proportions, to combine the proportions resulting from such transformation with corresponding proportions used previously, and to send to said switching element at said one of said origin nodes the proportions resulting from such combination, said switching element being arranged to update its said storage means with the newly-computed proportions for subsequent use in distributing calls among the circuit groups of said link to said virtual destination node.

12. A network as claimed in claim 11, wherein the network processor means is arranged to compute:

the first weight W1_g for circuit group g as;

##EQU26## the second weight W2_l,g for circuit group g of link l as;

##EQU27## the combined weight W_l,g for circuit group g of link l as;

##EQU28## the proportion WP_l,g for circuit group g of link l as;

##EQU29## and;

the combined proportion P_l,g for circuit group g of link l, combining the instant proportion and the previous proportion, as;

space="preserve" listing-type="equation">P.sub.l,g =WP.sub.l,g ·

PWF+P'"'"'.sub.l,g ·

(1-PWF),

where

CC_o is the completion capability reported by component c;

C_l,g is the component of a dynamic virtual destination node to which circuit group g in link l goes;

G₁ is the set of the circuit groups of link l;

#G₁ is the number of circuit groups in link l;

IC₈ is the reported number of idle circuits on circuit group g;

#L_g is the number of links that contain circuit group g;

P'"'"'_l,g is the previous proportion for circuit group g in link l; and

PWF is the weighting factor used for the computation of the proportions.

13. A network as claimed in claim 7, wherein each switching element derives call completion rate information for its calls to said virtual destination node and updates its proportions independence thereupon.

14. A network as claimed in claim 13, wherein said switching element, when attempting to route a call using said link to said virtual destination node, derives said call completion information by monitoring circuit group overflows and Release With Cause signalling messages attributable to factors remediable by the network.

15. A network as claimed in claim 14, wherein said one of said switching elements keeps for said link to said virtual destination node the variables:

N;

the number of circuit groups in the link (2 or more).

LASTCG;

the index in the link of the last circuit group that had an overflow or Release With Cause message (1 to N).

LASTOVF;

the number of overflows and/or Release With Cause messages in a row for the circuit group with index LASTCG (1 or more).

CGCTR;

the index in the link of the last circuit group that had its proportion updated (1 to N); and

when an attempt by said one of said switching elements to route a call using a circuit group CG in said link to said virtual destination node results in an overflow or a Release With Cause message specifying one of a predetermined set of causes, the switching element modifies the proportions for that link as follows;

1. If the index of circuit group CG is LASTCG then add 1 to LASTOVF;

otherwise set LASTCG to the index of circuit group CG and set LASTOVF to 1.

16. If the update is due to an overflow then:

(a) Set MAXDEC to the minimum of LASTOVF% and the current proportion of circuit group CG.

Otherwise (the update is due to a Release With Cause message);

(b) Set MAXDEC to the minimum of (LASTOVF% multiplied by N) and the current proportion of circuit group CG.

3. Subtract MAXDEC from the current proportion of circuit group CG.

4. Repeat MAXDEC times;

(a) Add 1 to CGCTR;

if CGCTR>

N then set CGCTR to 1.

(b) if CGCTR=LASTCG then go back to step 4a.

(c) Add 1% to the current proportion of the circuit group with index CGCTR.

18. A method as claimed in claim 16, said network further comprising network processor means (25A) for updating said routing information and coupled to all of said switching elements by a data communications network (24A), wherein, periodically, via the data communications network, each of said switching elements communicates to the network processor means information about network conditions local to the switching element and receives from the network processor means alternate routing information including recommended transit nodes, and the network processor means computes alternate routing information in dependence upon the information communicated thereto by all of the switching elements and periodically updates the information identifying transit nodes.

20. A method as claimed in claim 18, wherein, at the network processor means, safe idle circuits for said link are determined by:

(i) storing, for each link a protective allowance previously computed for that link, the protective allowance preserving capacity in the link for direct traffic;

(ii) computing, from these protective allowances and from current link utilization, a reservation value for each circuit group of each link;

(iii) computing, from these reservation values and from the number of idle circuits reported by switching elements of origin nodes, the number of unreserved (safe) idle circuits on each link;

and further comprising, based on these numbers of safe idle circuits, transit node recommendations for each pair of an origin node and a destination node connected directly by a link from the origin node to the destination node.

23. A method as claimed in claim 16, further comprising the step of updating the proportions automatically to take account of current link utilization and current ability of said components of said virtual destination node to complete calls to the final destinations served by that virtual destination node.

24. A method as claimed in claim 16, said network further comprising network processor means (25A) for updating the routing information and updating the proportions automatically to take account of current link utilization and current ability of said components of said virtual destination node to complete to the final destinations served by that virtual destination node, the network processor being coupled to all of said switching elements by a data communications network (24A), whereby, periodically, each of said switching elements communicates to the network processor means information about network conditions local to the switching element and receives from the network processor means alternate routing information including recommended transit nodes, and the network processor means, computes alternate routing information in dependence upon the information communicated thereto by all of the switching elements and periodically updates the information identifying transit nodes, and wherein each of said components of said virtual destination node reports to the network processor means call completion capability information related to its ability to complete calls to the final destinations served by that virtual destination node, and the network processor means computes a proportion for each circuit group of said link to said virtual destination node based upon such call completion information, and upon said network conditions reported by said switching elements, and supplies those proportions to the switching element at the origin node connected to said virtual destination node by said link.

25. A method as claimed in claim 23, wherein the call completion capability information communicated to the network processor means is rendered in a similar form and treated in a similar manner by the network processor means regardless of differences between the components, characteristics of calls handled, and final destinations served by those components.

26. A method as claimed in claim 23, wherein the proportions are determined by the network processor such that traffic is distributed among the plurality of circuit groups of said link to the virtual destination node in accordance with idle capacity of the circuit groups of said link and call completion capability of said components of said virtual destination node.

27. A method as claimed in claim 25, wherein the network processor computes, for each circuit group of said link to said virtual destination node, a first weight based on its number of idle circuits, and a second weight based on the completion capability of the components of the dynamic virtual destination node, combines the first and second weights, transforms the combined weights in to proportions, combines the proportions resulting from such transformation with corresponding proportions used previously, and sends to said switching element at said one of said origin nodes the proportions resulting from such combination, said switching element updating its said storage means with the newly-computed proportions for subsequent use in distributing calls among the circuit groups of said link to said virtual destination node.

28. A method as claimed in claim 26, wherein the network processor means computes:

the first weight W1_g for circuit group g as;

##EQU38## the second weight W2_l,g for circuit group g of link l as;

##EQU39## the combined weight W_l,g for circuit group g of link l as;

##EQU40## the proportion WP_l,g for circuit group g of link l as;

##EQU41## and the combined proportion P_l,g for circuit group g of link l, combining the instant proportion and the previous proportion, as;

space="preserve" listing-type="equation">P.sub.l,g =WP.sub.l,g ·

PWF+P'"'"'.sub.l,g ·

(1-PWF),

where;

CC_c is the completion capability reported by component c;

C_l,g is the component of a dynamic virtual destination node to which circuit group g in link l goes;

G₁ is the set of the circuit groups of link l;

#G₁ is the number of circuit groups in link l;

IC_g is the reported number of idle circuits on circuit group g;

#L_g is the number of links that contain circuit group g;

P'"'"'_l,g is the previous proportion for circuit group g in link l; and

PWF is the weighting factor used for the computation of the proportions.

30. A method as claimed in claim 28, wherein said switching element, when attempting to route a call using said link to said virtual destination node, derives said call completion information by monitoring circuit group overflows and Release With Cause signalling messages attributable to factors remediable by the network.

17. A method of routing calls in a telecommunications network (31A) such network comprising:

a plurality of network nodes (A,B,C,O,T,V) and links (A-B,A-O,A-T,B-A,B-O,B-T, . . . ), the network nodes comprising origin nodes (A,B,C,O,T), each comprising a switching element (a,b,c,o,t) capable of routing calls within the network, and destination nodes (A,B,C,O,T,V) serving as destinations for such calls, some of said network nodes being transit nodes (A,B,C,O,T), each transit node being both a destination node and an origin node;

each link interconnecting directly an origin node and a destination node and comprising one or more circuit groups (a-b,o-a,o-b,o-c, . . . ),

each of the switching elements having storage means for routing information, the routing information comprising

(i) a listing of destination nodes;

(ii) associated with each destination node, a corresponding link, where such a link exists;

(iii) for each link, a corresponding group of one or more circuit groups outgoing from the switching element; and

(iv) associated with each destination node, a list of zero or more transit nodes;

said listing of destination nodes of at least one of said switching elements that is at one of said origin nodes comprising a virtual destination node (V) representing a group of two or more components (a,b,c), each component being a distinct physical network element, there being one or more distinct circuit groups associated with each component, the link from said one of said origin nodes to the virtual destination node being a set of circuit groups from said one of said switching elements to the two or more components of the virtual destination node, and the storage means of said one of said switching elements including a specified proportion for each of those circuit groups;

each switching element comprising means for translating address data of a call to determine a destination node for the call;

the method comprising the steps of, at each switching element at an origin node;

(i) where a link to the destination node exists, attempting to route the call to the destination node via a circuit group that is in the link;

(ii) where a link to the destination node is not available, accessing the routing information to select a transit node and attempting to route the call via a circuit group that is in the link to the transit node;

when attempting to route a call to said virtual destination node via the link from said one of said origin nodes to the virtual destination node, attempting to route the call using one of said set of circuit groups, in dependence upon the specified proportions, wherein said one of said switching elements

(i) determines the set S of all circuit groups with a non-zero proportion in said plurality of circuit groups;

(ii) determines whether or not the set S is empty;

(iii) causes the call to overflow if the set is empty;

(iv) if the set is not empty, makes a weighted random selection of one of the circuit groups of the set S, and attempts to route the call via such circuit group;

(v) if the selected circuit group does not have a circuit idle, removes the selected circuit group from the set S; and

(vi) repeats steps (ii) through (v) until the call is carried or all circuit groups in the set have been exhausted and the call overflowed.

19. A method as claimed in claim 17, wherein the step of computing alternate route recommendations, by the network processor means, takes into account full availability of all of the links and, where a link comprises a plurality of circuit groups, takes into account all of the circuit groups of that link.

21. A method as claimed in claim 19, in a said network in which said link from said one of said origin nodes to the virtual destination node comprises a plurality of circuit groups and the storage means of said switching elements include a specified proportion for each of said circuit groups within each of said links, the method further comprising, at said switching elements, the step of, when attempting to route a call via one of these links, attempting the circuit groups of the link in dependence upon the specified proportions;

and at the network processor means, the steps of;

(i) distributing the protective allowances of the links that contain circuit group g among their circuit groups such that the reservation RSV_g on circuit group g is equal to ##EQU30## producing a total reservation level RSV₁ for link l equal to;

##EQU31## and;

(ii) computing the number of idle circuits IC₁ as ##EQU32## and the number of safe idle circuits SIC₁ for link l as;

space="preserve" listing-type="equation">SIC.sub.1 =IC.sub.1 -RSV.sub.1

where

G₁ is the set of circuit groups of link l;

IC_g is the reported number of idle circuits on circuit group g;

L_g is the set of the links that contain circuit group g;

P_l,g is said proportion used for intra-link traffic distribution, for circuit group g of link l;

PA₁ is the protective allowance value for link l, serving to preserve capacity for direct traffic.

22. A method as claimed in claim 19, further comprising, at the network processor means, the steps of:

(i) storing the current reservation RSV_l,g for each circuit group of each link; and

(ii) when computing the safe idle circuits;

(A) when the current RSV_l,g is 0, adjusting such reservation RSV_l,g to become;

##EQU33## (B) computing the requested reservation RRSV_l,g using the formula;

##EQU34## (C) computing the new reservation RSV_l,g on circuit group g for link l as;

##EQU35## (D) computing the reservation RSV_g on circuit group g as;

##EQU36## (E) computing the number of idle circuits IC₁ for each link l as;

##EQU37## and;

(F) computing the number of safe idle circuits SIC₁ for link l as equal to;

space="preserve" listing-type="equation">SIC.sub.1 =IC.sub.1 -RSV.sub.1

where;

G₁ is the set of circuit groups of link l;

#G₁ is the number of circuit groups in link l;

IC_g is the reported number of idle circuits on circuit group g;

I_g is the set of the links that contain circuit group g; and

PA₁ is the protective allowance value for link l, serving to preserve capacity for direct traffic.

29. A method as claimed in claim 22, wherein said one of said switching elements derives call completion rate information for its calls to said virtual destination node and updates its proportions in dependence thereupon.

31. A method as claimed in claim 29, wherein said one of said switching elements keeps, for said link to said virtual destination node, the variables:

N;

the number of circuit groups in the link (2 or more).

LASTCG;

the index in the link of the last circuit group that had an overflow or Release With Cause message (1 to N).

LASTOVF;

the number of overflows and/or Release With Cause messages in a row for the circuit group with index LASTCG (1 or more).

CGCTR;

the index in the link of the last circuit group that had its proportion updated (1 to N); and

when an attempt by said one of said switching elements to route a call using a circuit group CG in said link to said virtual destination node results in an overflow or a Release With Cause message specifying one of a predetermined set of causes, the switching element modifies the proportions for that link as follows;

1. If the index of circuit group CG is LASTCG then add 1 to LASTOVF;

otherwise set LASTCG to the index of circuit group CG and set LASTOVF to 1.

32. If the update is due to an overflow then:

(a) Set MAXDEX to the minimum of LASTOVF% and the current proportion of circuit group CG.

Otherwise (the update is due to a Release With Cause message);

(b) Set MAXDEC to the minimum of (LASTOVF% multiplied by N) and the current proportion of circuit group CG.

3. Subtract MAXDEC from the current proportion of circuit group CG.

4. Repeat MAXDEC times;

(a) Add 1 to CGCTR;

if CGCTR>

N then set CGCTR to 1.

(b) If CGCTR=LASTCG then go back to step 4a.

(c) Add 1% to the current proportion of the circuit group with index CGCTR.