Source routing for connection-oriented network with repeated call attempts for satisfying user-specified QOS parameters

• US 5,933,425 A
• Filed: 12/03/1996
• Issued: 08/03/1999
• Est. Priority Date: 12/04/1995
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwata, Atsushi
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Sam, Phirin
• Application Number:
  US08/759,159
• Time in Patent Office: 973 Days
• Field of Search: 370/229, 370/230, 370/232, 370/234, 370/238, 370/237, 370/252, 370/251, 370/395, 370/389, 370/225, 370/227, 370/216, 370/400, 370/353, 370/379, 370/382, 370/401, 370/397 , 370/399, 370/409, 340/827, 340/825.5
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS

Abstract

In a connection-oriented network where ATM nodes are interconnected by links, periodically updated link status information of the network is stored in a database to indicate resource constraints of the network links. Responsive to a connection request specifying multiple QOS parameters, a first path to a destination is selected and a first signaling message is transmitted containing routing data of the first path toward the destination if resource constraints of the first path satisfy all the specified QOS parameters. If the transmission of the first signaling message is unsuccessful or the resource constraints of the first path do not satisfy all the specified QOS parameters, then a second path to the destination is selected according to contents of the database that correspond to one of the specified QOS parameters, and a second signaling message containing routing data of the second path is transmitted toward the destination.

Claims

1. A routing apparatus for a connection-oriented network comprising a plurality of nodes interconnected by communication links, the routing apparatus comprising:

a database for storing periodically updated link status information of the network indicating resource constraints of the links; and

control means, responsive to a connection request specifying a plurality of QOS (quality of service) parameters, for performing the functions of;

selecting a first path to a destination;

transmitting a first signaling message containing routing data of the first path toward the destination if resource constraints of the first path satisfy all the specified QOS parameters;

selecting one of the specified OOS parameters;

determining a plurality of candidate paths to the destination using resource constraints of the database corresponding to the selected QOS parameter;

selecting an optimum one of the candidate paths as a second path if the transmission of the first signaling message is unsuccessful or the resource constraints of the first path do not satisfy all the specified QOS parameters; and

transmitting a second signaling message containing routing data of the second path toward the destination if resource constraints of the second path satisfy all other specified OOS parameters.

2. A method for routing a call through a connection-oriented network comprising a plurality of nodes interconnected by communication links, the method comprising the steps of:

a) storing link status information of the network and periodically updating the stored information according to link status of the network, the link status information indicating resource constraints of the links;

b) responsive to a connection request specifying a plurality of QOS (quality of service) parameters, selecting a first path to a destination;

c) transmitting a first signaling message toward the destination containing routing data of the first path if resource constraints of the first path satisfy all the specified QOS parameters;

d) selecting one of the specified OOS parameters;

determining a plurality of candidate paths to the destination using resource constraints of the database corresponding to the selected QOS parameter;

selecting an optimum one of said candidate paths as a second path if the resource constraints of the first path do not satisfy all the specified QOS parameters or the transmission of the first signaling message is unsuccessful; and

e) transmitting a second signaling message containing routing data of the second path toward the destination if resource constraints of the second path satisfy all other specified OOS parameters.

3. A method as claimed in claim 2, wherein said first path of the step (b) is a predetermined path.

4. A method as claimed in claim 2 or 3, wherein the step (d) further comprises the steps of:

calculating a sum of weights respectively assigned to the links of each of the candidate paths; and

selecting, as the second path, one of the candidate paths having a minimum sum.

5. A method as claimed in claim 2 or 3, wherein the step (d) further comprises the steps of:

selecting, as a link cost, one of the QOS parameters;

calculating a sum of the link costs for each of the candidate paths to said destination; and

selecting, as the second path, one of the candidate paths having a minimum link cost sum.

6. A method as claimed in claim 5, wherein the step (d) further comprises the steps of:

selecting, as the link cost, one of the QOS parameters with each of which the transmission of a signaling message was previously unsuccessful.

7. A method as claimed in claim 2, wherein the step (b) further comprises the steps of:

finding a plurality of candidate paths to said destination;

calculating a sum of weights respectively assigned to the links of each of the candidate paths; and

selecting, as the first path, one of the candidate paths having a minimum sum.

8. A method as claimed in claim 2, wherein the step (b) further comprises the steps of:

selecting one of the QOS parameters as a link cost;

calculating a sum of the link costs for each one of a plurality of candidate paths to said destination; and

selecting, as the first path, one of the candidate paths having a minimum link cost sum.

9. A method for routing a call through a connection-oriented network comprising a plurality of nodes interconnected by communication links, comprising the steps of:

a) storing link status information of the network and periodically updating the stored information according to link status of the network, said link status information indicating resource constraints of the links;

b) responsive to a connection request specifying a plurality of QOS (quality of service) parameters, resetting a count value;

c) selecting a path to a destination according to said count value, one of the specified QOS parameters and contents of the stored information corresponding to said one of the QOS parameters;

d) transmitting a signaling message containing routing data of the path toward the destination if resource constraints of the path satisfy all the specified QOS parameters;

e) incrementing the count value if the resource constraints of the path do not satisfy all the QOS parameters or if the transmission of the signaling message is unsuccessful; and

f) repeating steps (c) to (e) a predetermined number of times.

10. A method as claimed in claim 9, wherein the step (c) further comprises the steps of:

finding a plurality of candidate paths to said destination;

calculating a sum of weights respectively assigned to the links of each of the candidate paths; and

selecting one of the candidate paths having a minimum sum.

11. A method as claimed in claim 9 or 10, wherein the step (c) further comprises the steps of:

selecting one of the QOS parameters as a link cost;

calculating a sum of the link costs for each one of a plurality of candidate paths to said destination; and

selecting one of the candidate paths having a minimum link cost sum.

12. A method as claimed in claim 9 or 10, wherein the step (c) further comprises the steps of:

selecting, as a link cost, one of the QOS parameters with each of which the transmission of a transmitter signaling message was previously unsuccessful;

calculating a sum of the link costs for each one of a plurality of candidate paths to said destination; and

selecting one of the candidate paths having a minimum link cost sum.

13. A method as claimed in claim 9, wherein the step (c) further comprises the steps of:

when the count value is 0, selecting a predetermined path;

when the count value is incremented to 1, finding a plurality of candidate paths to said destination;

calculating a sum of weights respectively assigned to the links of each of the candidate paths; and

selecting one of the candidate paths having a minimum sum.

14. A method as claimed in claim 9, wherein the step (c) further comprises the steps of:

when the count value is 0, selecting a predetermined path;

when the count value is incremented to 1, selecting one of the QOS parameters as a link cost;

calculating a sum of the link costs for each one of a plurality of candidate paths to said destination; and

selecting one of the candidate paths having a minimum link cost sum.

15. A method as claimed in claim 9, wherein the step (c) further comprises the steps of:

when the count value is 0, selecting a predetermined path;

when the count value is incremented to 1, finding a plurality of candidate paths to said destination;

calculating a sum of weights respectively assigned to the links of each of the candidate paths;

selecting one of the candidate paths having a minimum sum;

when the count value is incremented to 2, selecting one of the QOS parameters as a link cost;

calculating a sum of the link costs for each one of a plurality of candidate paths to said destination; and

selecting one of the candidate paths having a minimum link cost sum.

16. A method as claimed in claim 15, wherein the step (c) further comprises the steps of:

when the count value is incremented to 3, selecting, as the link cost, one of the QOS parameters with each of which the transmission of a signaling message was previously unsuccessful.