Combined progressive and source routing control for connection-oriented communications networks

• US 5,649,108 A
• Filed: 11/30/1994
• Issued: 07/15/1997
• Est. Priority Date: 11/30/1993
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Spiegel, Ethan, Murase, Tutomu
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): HARRITY, JOHN E
• Application Number:
  US08/351,073
• Time in Patent Office: 958 Days
• Field of Search: 395/200.08, 395/200.12, 395/200.01, 370/54, 370/94.1, 364/284, 364/DIG. 1
• US Class Current: 709/241
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04Q 2213/1307 Call setup
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13144 Searching path through number of switching stages or nodes, e.g. revertive blocking
• CPC Class Codes: H04Q 2213/13148 Maximum profit routing
• CPC Class Codes: H04Q 2213/13217 Cranckback in routing, trombone connection, loopback circuit
• CPC Class Codes: H04Q 2213/1329 Asynchronous transfer mode, ATM
• CPC Class Codes: H04Q 2213/13342 Arrangement of switches in the network
• CPC Class Codes: H04Q 2213/13353 Routing table, map memory
• CPC Class Codes: H04Q 2213/1338 Inter-exchange connection
• CPC Class Codes: H04Q 2213/13399 Virtual channel/circuits
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

In a connection-oriented communications network, a source node selects one of first and second routing mode flags and a first route to a destination node in response to a connection request, and establishes a connection to a first intermediate node located along the first route. The first intermediate node is responsive to the first flag for extending the connection along the first route if there is an acceptable link in the first route. If there is no acceptable link, it finds a first route section therefrom to the destination node and extends the connection along the first route section if a total cost of links from the source node to the destination node using the first route section is less than a cost threshold, or cranks the connection back to an upstream node if there is none of such route sections. The upstream node then finds a second route section if a total cost of links from the source node to the destination node using the second route section is less than the cost threshold and extends the connection from the upstream node to a second intermediate node along the second route section, or clears the connection if there is none of the such route sections. On clearing the connection, the source node may or may not select the other flag. In either case, it selects a second, alternate route to the destination node and establishes a connection to a third intermediate node along the second route. If the flag is set to the first mode, the third intermediate node operates in the same manner as the first intermediate node does, and if the flag is set to the second mode, it extends the connection along the second route if there is an acceptable link. Otherwise, it clears the connection if there is no acceptable link and communicates this fact to the source node.

Claims

1. In a connection-oriented communications network including a plurality of network nodes interconnected by links, each of said network nodes functioning as a source node, an intermediate node or a destination node, a method comprising the steps of:

a) selecting, at a source node, a route therefrom to a destination node and establishing a connection from the source node to an intermediate node on the route;

b) extending the connection from the intermediate node along the route if there is an acceptable link in the selected route;

c) selecting, at said intermediate node, a first route section including one or more intermediate nodes therefrom to said destination node if there is no acceptable link in the route selected by the step (a);

d) determining, at said intermediate node, whether a total cost of links from said source node to said destination node via said first route section is more or less than a cost threshold and extending said connection from the intermediate node along said first route section if said total cost is less than the cost threshold and there is an acceptable link in the first route section;

e) cranking the connection from the intermediate node back to an adjacent upstream node if said total cost is more than the cost threshold and there is no acceptable link in the first route section;

f) selecting, at said upstream node, a second route section including one or more intermediate nodes therefrom to said destination node and determining whether a total cost of links from said source node to said destination node via the second route section is more or less than said cost threshold;

g) extending the connection from the upstream node along the second route section if the total cost of the step (f) is less than the cost threshold and there is an acceptable link in the second route section; and

h) clearing the connection if the total cost of the step (f) is more than the cost threshold or there is no acceptable link in the second route section and repeating the steps (a) to (g).

2. In a connection-oriented communications network including a plurality of network nodes interconnected by links, each of said network nodes functioning as a source node, an intermediate node or a destination node, a method comprising the steps of:

a) selecting, at a source node, one of first and second flags respectively representing different routing modes and a first route from the source node to a destination node in response to a connection request and establishing a connection from the source node to a first intermediate node located along the first route;

b) responsive to the first flag, extending the connection from the first intermediate node along the first route if there is an acceptable link in said first route far the first intermediate node to use, selecting a first route section from the first intermediate node to the destination node if there is no acceptable link in said first route and extending the connection from the first intermediate node along the first route section if a total cost of links from said source node to said destination node using said first route section is less than a cost threshold, and cranking the connection back to an upstream node if there is none of said first route sections;

c) selecting, at the upstream node, a second route section if a total cost of links from the source node to the destination node using the second route section is less than the cost threshold and extending the connection from said upstream node to a second intermediate node along the second route section, and clearing the connection if there is none of said second route sections;

c) selecting, at the source node, the other flag and a second route from the source node to the destination node, and establishing a connection from the source node to a third intermediate node along the second route; and

d) responsive to the second flag, extending the connection from the third intermediate node along the second route if there is an acceptable link from the third intermediate node toward the destination node, and clearing the connection if there is no acceptable link therefrom toward the destination node.

3. A connection-oriented communications network having a plurality of network nodes interconnected by links, each of the nodes functioning as a source node or an intermediate node,

the source node comprising:

a routing table for mapping a plurality of routes from the source node to other network nodes; and

means for searching the routing table of the source node and selecting a first candidate route to a destination node in response to receipt of a request for a connection and selecting a second candidate route in response to a negative acknowledgment (NACK) packet from an adjacent node, setting a list of node identities of one of the first and second candidate routes, a cost threshold and a cost of the link from the source node to an intermediate node of one of said routes into a packet, and transmitting the packet from the source node to the intermediate node as a connection setup packet;

said intermediate node comprising;

a routing table for mapping a plurality of routes from the intermediate node to other network nodes;

means for receiving a said connection setup packet from an adjacent node located upstream of the intermediate node;

means for adding a cost of the link from the intermediate node to an adjacent intermediate node which is identified by the list of the received packet to the cost set in the received packet if the link between the intermediate node to said adjacent intermediate node has enough resources to support a required value, and transmitting the packet to said adjacent intermediate node as a new connection setup packet;

means for searching the routing table of the intermediate node and selecting a route section from the intermediate node to the destination node not included in the list of node identities of the received packet if the route indicated by the list of the received packet has not. enough resources for the link between the intermediate node and the adjacent intermediate node, the selected route section having enough resources to support the required value for the link between the intermediate node and an adjacent intermediate node of the route section, a total of the cost set in the received packet and the cost of the route section being less than the cost threshold set in the received packet;

means for replacing one or more node identities of the list of the received packet with one or more node identities of the route section, adding a cost of the link between the intermediate node and the adjacent intermediate node of the route section to the cost set in the received packet, and transmitting the packet to said adjacent intermediate node of the route section as a new connection setup packet;

means for returning a NACK packet to said adjacent upstream node if there is no acceptable route in the routing table of the intermediate node to reach said destination node; and

means for relaying a NACK packet when same is received from an adjacent downstream node to said adjacent upstream node.

4. A connection-oriented communications network as claimed in claim 3, wherein the NACK packet includes a second list of node identities identifying the nodes through which the connection setup packet has traveled so that the source node identifies previously blocked links for selecting said second candidate route.

5. A connection-oriented communications network having a plurality of network nodes interconnected by links, each of the nodes functioning as a source node or an intermediate node,

the source node comprising:

a routing table for mapping a plurality of routes from the source node to other network nodes; and

means for searching the routing table of the source node and selecting a first candidate route to a destination node in response to receipt of a request for a connection and selecting a second candidate route in response to a negative acknowledgment (NACK) packet from an adjacent node, setting a list of node identities of one of the first and second candidate routes, a cost threshold, a crankback limit and a cost of the link from the source node to an intermediate node of one of said routes into a packet, and transmitting the packet from the source node to the intermediate node as a connection setup packet;

said intermediate node comprising;

a routing table for mapping a plurality of routes from the intermediate node to other network nodes;

means for receiving a said connection setup packet from an adjacent node located upstream of the intermediate node;

means for adding a cost of the link from the intermediate node to an adjacent intermediate node which is identified by the list of the received packet to the cost set in the received packet if the link between the intermediate node to said adjacent intermediate node has enough resources to support a required value, and transmitting the packet to said adjacent intermediate node as a new connection setup packet;

means for searching the routing table of the intermediate node and selecting a route section from the intermediate node to the destination node not included in the list of node identities of the received packet if the route indicated by the list of the received packet has not enough resources for the link between the intermediate node and the adjacent intermediate node, the selected route section having enough resources to support the required value for the link between the intermediate node and an adjacent intermediate node of the route section, a total of the cost set in the received packet and the cost of the route section being less than the cost threshold set in the received packet;

means for replacing one or more node identities of the list of the received packet with one or more node identities of the route section, adding a cost of the link between the intermediate node and the adjacent intermediate node of the route section to the cost set in the received packet, and transmitting the packet to said adjacent intermediate node of the route section as a new connection setup packet;

means for decrementing the crankback limit set in the received packet by one and returning the received packet to said adjacent, upstream node if there is no acceptable route in the routing table of the intermediate node to reach said destination node and the crankback limit is greater than zero, or transmitting a NACK packet upstream from said intermediate node to said adjacent upstream node if there is no acceptable route in the routing table of the intermediate node to reach said destination node and the crankback limit is not greater than zero; and

means for relaying a said NACK packet when same is received from an adjacent downstream node to said adjacent upstream node.

6. A connection-oriented communications network as claimed in claim 5, wherein the NACK packet includes a second list of node identities identifying the nodes through which the connection setup packet has traveled so that the source node identifies previously blocked links for selecting said second candidate route.

7. A connection-oriented communications network having a plurality of network nodes interconnected by links, each of the nodes functioning as a source node or an intermediate node,

the source node comprising:

a routing table for mapping a plurality of routes from the source node to other network nodes; and

means for searching the routing table of the source node and selecting a first candidate route to a destination node and one of first and second routing modes in response to receipt of a request for a connection, selecting a second candidate route and the other routing mode in response to receipt of a negative acknowledgment (NACK) packet from an adjacent node, setting a list of node identities of one of the first and second candidate routes and a flag indicating the selected routing mode into a packet, additionally setting a cost threshold and a cost of the link from the source node to an intermediate node of one of said candidate routes into said packet if said first routing mode is selected, and transmitting the packet from the source node to the intermediate node as a connection setup packet;

said intermediate node comprising;

a routing table for mapping a plurality of routes from the intermediate node to other network nodes;

means for receiving a said connection setup packet from an adjacent node located upstream of the intermediate node;

means, responsive to the flag of the received packet indicative of the first routing mode, for adding a cost of the link from the intermediate node to an adjacent intermediate node which is identified by the list of the received packet to the cost set in the received packet if the link between the intermediate node and sold adjacent intermediate node has enough resources to support a required value, and transmitting the packet to said adjacent intermediate node as a new connection setup packet;

means, responsive to the flag of the received packet indicative of the first routing mode, for searching the routing table of the intermediate node and selecting a route section from the intermediate node to the destination node not included in the list of node identities of the received packet if the link between the intermediate node and the adjacent intermediate node has not enough resources to support said required value, the selected route section having enough resources to support the required value for the Link between the intermediate node and an adjacent intermediate node of the route section, a total of the cost set in the received packet and the cost of the route section being less than the cost threshold set in the received packet;

means, responsive to the flag of the received packet indicative of the second routing mode, for transmitting a copy of the received packet to said adjacent intermediate node if the link between the intermediate node and said adjacent intermediate node has enough resources to support said required value or returning a NACK packet to sold adjacent upstream node if the link between the intermediate node and said adjacent intermediate node has not enough resources to support said required value;

means, responsive to the flag of the received packet indicative of the first routing mode, for returning a NACK packet to said adjacent upstream node if there is no acceptable route in the routing table of the intermediate node to reach said destination node;

means, responsive to the flag of the received packet indicative of the first routing mode, for replacing one or more node identities of the list of the received packet with one or more node identities of the route section, adding a cost of the link between the intermediate node and the adjacent intermediate node of the route section to the cost set in the received packet, and transmitting the packet to said adjacent intermediate node of the route section as a new connection setup packet; and

means for relaying a NACK packet when same is received from an adjacent downstream node to said adjacent upstream node.

8. A connection-oriented communications network as claimed in claim 7, wherein the NACK packet includes a second list of node identities identifying the nodes through which the connection setup packet has traveled so that the source node identifies previously blocked links for selecting said second candidate route.

9. A connection-oriented communications network having a plurality of network nodes interconnected by links, each of the nodes functioning as a source node or an intermediate node,

the source node comprising:

a routing table for mapping a plurality of routes from the source node to other network nodes;

means for searching the routing table of the source node and selecting a first candidate route to a destination node and one of first and second routing modes in response to receipt of a request for a connection, selecting a second candidate route and the other routing mode in response to receipt of a negative acknowledgment (NACK) packet from an adjacent node, setting a list of node identities of one of the first and second candidate routes and a flag indicating the selected routing mode into a packet, additionally setting a cost threshold, a crankback limit and a cost of the link from the source node to an intermediate node of one of said candidate routes into said packet if said first routing mode is selected, and transmitting the packet from the source node to the intermediate node as a connection setup packet;

said intermediate node comprising;

a routing table for mapping a plurality of routes from the intermediate node to other network nodes;

means for receiving a said connection setup packet from an adjacent node located upstream of the intermediate node;

means, responsive to the flag of the received packet indicative of the first routing mode, for adding a cost of the link from the intermediate node to an adjacent intermediate node which is identified by the list of the received packet to the cost set in the received packet if the link between the intermediate node and said adjacent intermediate node has enough resources to support a required value, and transmitting the packet to said adjacent intermediate node as a new connection setup packet;

means, responsive to the flag of the received packet indicative of the first routing mode, for searching the routing table of the intermediate node and selecting a route section from the intermediate node to the destination node not included in the list of node identities of the received packet if the link between the intermediate node and the adjacent intermediate node has not enough resources to support said required value, the selected route section having enough resources to support the required value for the link between the intermediate node and an adjacent intermediate node of the route section, a total of the cost set in the received packet and the cost of the route section being less than the cost threshold set in the received packet;

means, responsive to the flag of the received packet indicative of the first routing mode, for replacing one or more node identities of the list of the received packet with one or more node identities of the route section, adding a cost of the link between the intermediate node and the adjacent intermediate node of the route section to the cost set in the received packet, and transmitting the packet to said adjacent intermediate node of the route section as a new connection setup packet;

means, responsive to the flag of the received packet indicative of the first routing mode and the crankback limit thereof being greater than zero, for decrementing the crankback limit by one and returning the received packet to said adjacent upstream node if there is no acceptable route in the routing table of the intermediate node to reach said destination node, or responsive to the flag of the received packet indicative of the first routing mode and the crankback limit thereof being not greater than zero, for transmitting a NACK packet to said adjacent upstream node if there is no acceptable route in the routing table of the intermediate node to reach said destination node;

means, responsive to the flag of the received packet indicative of the second routing mode, for transmitting a copy of the received packet to said adjacent intermediate node if the link between the intermediate node and said adjacent intermediate node has enough resources to support said required value, or returning a NACK packet to said adjacent upstream node if the link between the intermediate made and said adjacent intermediate node has not enough resources to support said required value;

means for relaying a said NACK packet when same is received from an adjacent downstream node to said adjacent upstream node.

10. A connection-oriented communications network as claimed in claim 9, wherein the NACK packet includes a second list of node identities identifying the nodes through which the connection setup packet has traveled so that the source node identifies previously blocked links for selecting said second candidate route.