Routing method for setting up a service between an origination node and a destination node in a connection-communications network

• US 5,805,593 A
• Filed: 09/26/1995
• Issued: 09/08/1998
• Est. Priority Date: 09/26/1995
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Busche, Matthew T.
• Primary Examiner(s): Jung, Min
• Application Number:
  US08/534,151
• Time in Patent Office: 1,078 Days
• Field of Search: 370/238, 370/254, 370/255, 370/397, 370/400, 370/406, 370/408, 370/409, 370/235, 370/396, 370/410, 395/200.68, 395/200.71, 395/200.72, 395/200.73, 455/445
• US Class Current: 370/396
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

A setup procedure employing distributed hop-by-hop routing reduces the number of signaling messages needed to establish a service (i.e., connection), thus enhancing network performance. A service is setup between an origination node and a destination node which are a part of a network of communication nodes interconnected by links. Each node maintains a topological database representing the network topology. Initially, a setup message for initiating the service is transmitted from the origination node to a neighboring node that serves as a local node. The topological database is then updated after the local node receives the setup message by eliminating links connected to a particular set of nodes. This set of nodes includes those nodes other than the local node that have previously transmitted a setup or failure message for the service. A shortest path is next determined from the local node to the destination node over the updated topology and another setup message is transmitted from the local node to a first neighboring node in the shortest path. The previously-mentioned steps are repeated, beginning with the step of updating the topological database, where the neighboring node now serves as a subsequent local node. The steps are repeated until either a setup message reaches the destination node so that the service enters a connected state or no shortest path is found at the origination node, which indicates that the service has failed to enter a connected state.

Claims

1. A method for setting-up a service between an origination node and a destination node, said origination and destination nodes being a part of a network of communication nodes interconnected by links, said nodes maintaining a topological database representing a network topology, said method comprising the steps of:

a. transmitting a setup message for initiating the service from the origination node to a local node;

b. updating the topological database of said local node after the local node receives said setup message by eliminating links connected to a set of nodes, said set of nodes including those nodes in said network of communication nodes other than the local node that have previously transmitted a setup or failure message for said service;

c. determining a shortest path from the local node to the destination node over the updated topology;

d. transmitting another setup message from the local node to a neighboring node in the shortest path;

e. repeating steps b-d with said neighboring node serving as a subsequent local node until either a setup message reaches the destination node so that said service enters a connected state or no shortest path is found at said origination node indicating that said service has failed to enter a connected state.

2. The method of claim 1 further comprising the steps of:

f. returning a failure message from a local node to a previous node if no shortest path is found in step (c);

g. returning to step (b) and repeating steps (b)-(e), wherein a link connected to said local node returning the failure message in step (f) is eliminated from the topological database in accordance with step (b).

3. The method of claim 1 wherein step (e) includes the step of transmitting an acknowledgment message from the destination node to the origination node prior to said service entering the connected state.

4. The method of claim 1 further comprising the step of associating with each node in the network a database containing identification information concerning other nodes in said network, links in said network and the respective lengths thereof.

5. The method of claim 4 wherein the lengths of the links are expressed in terms of relative cost.

6. The method of claim 4 wherein each setup message and each failure message received by each node further includes information concerning nodes that have previously transmitted a setup or failure message for said service.

7. The method of claim 1 wherein step (a) includes the step of performing a shortest path calculation from the origination node to the destination node to determine the local node that receives the setup message from the origination node.