System and method for call-by-call source routing with rule-based fallbacks

• US 5,402,478 A
• Filed: 07/27/1992
• Issued: 03/28/1995
• Est. Priority Date: 07/27/1992
• Status: Expired due to Term

• Current Assignee: Motorola Mobility, Inc. (Lenovo Group Ltd.)
• Original Assignee: Codex Corporation
• Inventors: Lee, Whay C., Hluchyj, Michael G., Humblet, Pierre A.
• Primary Examiner(s): Dwyer, James L.
• Assistant Examiner(s): Hunter, Daniel S.
• Application Number:
  US07/919,682
• Time in Patent Office: 974 Days
• Field of Search: 379/219, 379/220, 379/221, 370/16, 370/60.1
• US Class Current: 379/221.01
• CPC Class Codes: H04Q 2213/13054 Expert system
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13146 Rerouting upon blocking/overload, rearrangement
• CPC Class Codes: H04Q 2213/13167 Redundant apparatus
• CPC Class Codes: H04Q 2213/13343 Neural networks
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A fallback strategy for a system (700) and method (200) is provided for rerouting a call that fails to be established utilizing a first set of constraints in a communication network system. This strategy enables the communication network system to utilize a look-around-first type of preemption that avoids unnecessary preemption and provides alternate routing for a call according to predetermined constraints selected by a user.

Claims

1. A method for source based call-by-call routing of a call in a communication network, comprising the steps of:

1A) selecting a constrained routing for the call;

1B) determining an optimal feasible path, and, where the optimal feasible path is available, the network'"'"'s implementing the optimal feasible path;

1C) implementing a fallback strategy upon one of;

1C1) determining that the optimal feasible path is unavailable under the selected constraints, or

1C2) the network'"'"'s being unsuccessful in implementing the optimal feasible path for routing the call

where fallback routing allows accommodation of preferential resource constraints and look-around-first call preemption and where routing without preemption is attempted before preemption.

2. The method of claim 1 wherein the constrained routing comprises a routing in accordance with at least one of:

path constraints and/Or network constraints.

3. The method of claim 1 wherein the communication network is an integrated traffic-type communication network subject to diverse quality-of-service requirements.

4. The method of claim 3 wherein the quality-of-service requirements are ranked according to a predetermined level of importance of the path and/or network constraints.

5. The method of claim 1 wherein the constrained routing is determined in accordance with a predetermined routing policy and a predetermined quality-of-service.

6. The method of claim 5 wherein the predetermined routing policy and the predetermined quality-of-service include at least three elements:

link constraint(s), path constraint(s), and objective function(s).

7. The method of claim 6 wherein the objective function is one of:

delay or cost.

8. The method of claim 6 wherein, for determining an optimal feasible path,

8A) where network resources, NR, for a path of the call are indicated to be available and all path constraints are satisfied, the path is feasible;

8B) among all feasible paths, a feasible path that minimizes a selected objective function is the optimal feasible path.

9. The method of claim 6 wherein, for multiple objective functions, routing criteria are ranked according to a predetermined level of importance, and ordered routing criteria are utilized for determining the constrained routing.

10. The method of claim 1 wherein the constrained routing is determined by a connection state and at least a first quality-of-service requirement for the call.

11. The method of claim 10, further including that available connection states include:

a connection establishment state operably coupled to a data transfer state, the data transfer state being operably coupled to a connection reestablishment state and to a connection release state, such that steps for permitting call preemption include;

11A) assigning a priority number to each call in accordance with a connection state of the call; and

11B) where the priority number of a preempting call is higher than a priority of a call to be preempted, allowing the preempting call to preempt the preempted call, wherein at least one of;

11B1) for preemption to provide path determination, a preempted call is in the data transfer state and the preempting call is in one of;

the connection establishment state and the connection reestablishment state, or

11B2) for preemption due to resource contention while resources are being allocated to a new connection, the preempted call is in any one of the connection states.

12. The method of claim 1 wherein determining the optimal feasible path, and, where the optimal feasible path is available, the network'"'"'s implementing the optimal feasible path, includes:

12A) determining network resources (NR) required for the optimal feasible path from a source to a destination for the call in the communication network;

12B) determining the availability for implementing the call using the NR; and

12C) where available, allocating the NR for routing the call.

13. The method of claim 1 wherein the fallback routing strategy includes:

utilizing information derived from determining the optimal feasible path to determine fallback routing availability such that,

13A) where fallback routing is available, recycling to selecting a constrained routing for the call (step 1A); and

13B) where fallback routing is unavailable, blocking the call.

14. A method for source based call-by-call routing of a call in a communication network, the method comprising the steps of:

14A) selecting a constrained routing for the call;

14B) determining an optimal feasible path and, where available, implementing the optimal feasible path for the call;

14C) where the optimal feasible path is unavailable, determining whether fallback routing is available for the call

14C1) where fallback routing is available, selecting a fallback routing and recycling to the step of choosing a constrained routing for the call (step 14A);

14C2) where fallback routing is unavailable, blocking transmission of the call;

14D) where the optimal feasible path is available, the network'"'"'s attempting to allocate network resources along the optimal feasible path;

14E) where the resource allocation attempt is unsuccessful, blocking transmission of the call;

14F) where the resource allocation attempt is successful, establishing the call

where fallback routing allows accommodation of preferential resource constraints and look-around-first call preemption and where routing without preemption is attempted before preemption.

15. The method of claim 14 wherein the constrained routing comprises a routing in accordance with at least one of:

path constraints and/or network constraints.

16. The method of claim 14 wherein the communication network is an integrated traffic-type communication network subject to diverse quality-of-service requirements.

17. The method of claim 16 wherein the quality-of-service requirements are ranked according to a predetermined level of importance of the oath and/or network constraints.

18. The method of claim 14 wherein the constrained routing is determined in accordance with a predetermined routing policy and a predetermined quality-of-service.

19. The method of claim 18 wherein the predetermined routing policy and the predetermined quality-of-service include at least three elements:

link constraint(s), path constraint(s), and objective function(s).

20. The method of claim 19 wherein the objective function is one of:

delay or cost.

21. The method of claim 19 wherein:

21A) where NR for a path of the call are indicated to be available and all path constraints are satisfied, the path is feasible;

21B) among all feasible paths, a feasible path that minimizes a selected objective function is the optimal feasible path.

22. The method of claim 19 wherein, for multiple objective functions, routing criteria are ranked according to a predetermined level of importance, and ordered routing criteria are utilized for determining the constrained routing.

23. The method of claim 14 wherein the constrained routing is determined by a connection state and at least a first quality-of-service requirement for the call.

24. The method of claim 23, further including that available connection states include:

a connection establishment state operably coupled to a data transfer state, the data transfer state being operably coupled to a connection reestablishment state and to a connection release state, such that steps for permitting call preemption include;

24A) assigning a priority number to each call in accordance with a connection state of the call; and

24B) where the priority number of a preempting call is higher than a priority of a call to be preempted, allowing the preempting call to preempt the preempted call, wherein at least one of;

24B1) for preemption to provide path determination, a preempted call is in the data transfer state and the preempting call is in one of;

the connection establishment state and the connection reestablishment state, and/or

24B2) for preemption due to resource contention while resources are being allocated to a new connection, the preempted call is in any one of the connection states.

25. The method of claim 14 wherein determining an optimal feasible path, and, where available, implementing the optimal feasible path for the call includes:

25A) determining an optimal feasible path from a source to a destination for the call in the communication network; and

25B) determining availability of network resources along the optimal feasible path.

26. The method of claim 14 wherein selecting a fallback routing includes utilizing information derived from determining the optimal feasible path to determine the fallback routing.

27. A system for source based call-by-call routing of a call in a communication network, comprising:

27A) routing means for selecting a constrained routing for the call;

27B) optimal feasible path determining means, operably coupled to the routing means, for determining an optimal feasible path, availability of implementing the optimal feasible path, and, where available, for sending a signal to a network means, thereby causing the network means to implement the optimal feasible path; and

27C) fallback strategy means, operably coupled to the optimal feasible path determining means and the network means, for implementing a fallback strategy where one of;

27C1) the optimal feasible path is unavailable, and/or

27C2) the network is unsuccessful in implementing the optimal

feasible path for routing the call where fallback routing allows accommodation Of preferential resource constraints and look-around-first call preemption and where routing without preemption is attempted before preemption.

28. The system of claim 27 wherein the constrained routing comprises a routing in accordance with at least one of:

path constraints and/Or network constraints.

29. The system of claim 27 wherein the communication network is an integrated traffic-type communication network subject to diverse quality-of-service requirements.

30. The system of claim 29 wherein the quality-of-service requirements are ranked according to a predetermined level of importance of the path and/or network constraints.

31. The system of claim 27 wherein the constrained routing is in accordance with a predetermined routing policy and a predetermined quality-of-service.

32. The system of claim 31 wherein the predetermined routing policy and the predetermined quality-of-service include at least three elements:

link constraint(s), path constraint(s), and objective function(s).

33. The system of claim 32 wherein the objective function is one of:

delay and cost.

34. The system of claim 32 wherein the optimal feasible path determining means provides:

34A) where NR for a path of the call are indicated to be available and all path constraints are satisfied, the path ,is feasible;

34B) among all feasible paths, a feasible path that minimizes a selected objective function is the optimal feasible path.

35. The system of claim 32 wherein, for multiple objective functions, the routing criteria are ranked according to a predetermined level of importance, and the ordered routing criteria are utilized for determining the constrained routing.

36. The system of claim 27 wherein the constrained routing is determined by a connection state and at least a first quality-of-service requirement for the call.

37. The system of claim 36, wherein the fallback strategy means further selects between available connection states that include:

a connection establishment state operably coupled to a data transfer state, the data transfer state being operably coupled to a connection reestablishment state and to a connection release state, and further permits;

37A) assigning a priority number to each call in accordance with a connection state of the call; and

37B) where the priority number of a preempting call is higher than a priority of a call to be preempted, allowing the preempting call to preempt the preempted call, including at least one of;

37B1) preempting to provide path determination where a preempted call is in the data transfer state and the preempting call is in one of;

the connection establishment state and the connection reestablishment state, and

37B2) preempting due to resource contention while resources are being allocated to a new connection where the preempted call is in any one of the connection states.

38. The system of claim 27 wherein the fallback strategy means further provides for determining an optimal feasible path, availability of implementing the optimal feasible path, and, where available, provides for implementing the optimal feasible path including:

38A) determining network resources (NR) required for the optimal feasible path from the source to the destination for the call in the communication network;

38B) determining availability for implementing the optimal feasible path; and

38C) routing the call using the NR.

39. The system of claim 27 wherein the means for implementing the fallback routing strategy includes:

means for utilizing information derived from determining the optimal feasible path to determine fallback routing availability and,

39A) where fallback routing is available, means for recycling to means for selecting a constrained routing for the call (27A); and

39B) where fallback routing is unavailable, blocking means for blocking the call.

40. The system of claim 27 wherein, where the network means is unsuccessful in utilizing the optimal feasible path for routing the call, the network means sends a signal to the fallback strategy means to cause the fallback strategy means to implement a fallback strategy.

41. A communication network system for routing an integrated traffic-type call in a communication network, comprising:

41A) a requested resource constraint determiner, operably coupled to receive a call, for providing at least one of;

a first output and a second output, wherein the first output is a reoptimized call and the second output is an established call, for implementing requested resource constraints with non-preemptiveness and minimized cost for the call to provide the established/reoptimized call,

41B) a first acceptable resource constraint determiner, operably coupled to receive the call, to receive the second output (established call) of the requested resource constraint determiner, for, where one of;

establishing the call is unsuccessful or reestablishing/appending the call is required, implementing acceptable resource constraints with non-preemptiveness and minimized cost to provide a non-preemptive output and a first preemptive output,

41C) a second acceptable resource constraint determiner, operably coupled to receive the first non-preemptive output, for implementing acceptable resource constraints with non-preemptiveness and minimized delay to provide a non-preemptive delay-minimized output,

41D) a third acceptable resource constraint determiner, operably coupled to receive the first preemptive output, for, where step 41(B) is unsuccessful, implementing acceptable resource constraints with preemptiveness and minimized cost to provide a second preemptive cost-minimized output, and

41E) a fourth acceptable resource constraint determiner with preemptiveness, operably coupled to receive the second preemptive cost-minimized output, for implementing acceptable resource constraints with preemptiveness and minimizing delay to provide a preemptive delay-minimized output.

42. A method for routing a call in a communication network system, wherein "_-- -_-- " represents two letters separated by a dash, the letters being selected from X and I to represent exclusion (X) and inclusion (I) from/with requested resource constraints (first letter) and acceptable resource constraints (second letter), respectively, the method comprising the steps of:

42A) the network system'"'"'s determining how many resource attribute values are specified as required by the user;

42B) where one required resource attribute value is specified by a user for a given resource attribute, the network system'"'"'s assigning I--I to the required resource attribute value, and X--X to all other resource attribute values belonging to the same resource attribute;

42C) where greater than one required resource attribute value is specified for a given resource attribute, the network system'"'"'s classifying the selection as an invalid configuration;

42D) where the number of required resource attribute values for a given resource attribute is zero, the network system'"'"'s determining how many resource attribute values are preferred;

42E) where one or more resource attribute values for a given resource attribute are preferred, the preferred resource attribute values being assigned I--I, any don'"'"'t_-- care resource attribute values (X--I) being assigned X--I, and any don'"'"'t_-- use resource attribute values being assigned X--X;

42F) where the number of required resource attribute values for a given resource attribute is zero and where the number of preferred resource attribute values for the same resource attribute is zero, the network system'"'"'s determining how many don'"'"'t_-- care resource attribute values are specified;

42G) where one or more resource attribute values are specified as don'"'"'t_-- care, the don'"'"'t_{-- --} care resource attribute values being assigned I--I, and any don'"'"'t_-- use resource attribute values being assigned X--X; and

42H) where the number of required resource attribute values for a given resource attribute is zero, where the number of preferred resource attribute values for the same resource attribute is zero, and where the number of don'"'"'t_-- care resource attribute values for the same resource attribute is zero, the network system'"'"'s classifying the selection as an invalid configuration.