Method for selecting least weight end node to end node route in a data communications network

• US 4,873,517 A
• Filed: 06/23/1988
• Issued: 10/10/1989
• Est. Priority Date: 06/23/1988
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pozefsky, Diane P., Rafalow, Lee M., Gray, James P., Siddall, William E., Pollard, Melinda R., Baratz, Alan E., Clarke, Kathryn E.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Pudpud, E. O.
• Application Number:
  US07/210,273
• Time in Patent Office: 474 Days
• Field of Search: 340/825.03, 340/826, 340/827, 370/94, 370/54, 370/58, 379/220, 379/221, 364/514
• US Class Current: 370/236
• 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/44 Distributed routing
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor

Abstract

When computing a least weight path from an origin node to a destination node in a data communication network, a route-computing network node uses information provided by the origin and destination nodes to compute least weight routes from those nodes to adjacent network nodes. The route-computing network node uses information in the topology database to compute least weight routes from network nodes adjacent the origin node to network nodes adjacent the destination node. The results of the computations are concatenated to determine an optimum route from the origin node to the destination node. The topology database need not include information about the transmission groups connecting the origin/destination nodes to network nodes.

Claims

1. A method of enabling a network node to determine an optimal route through a data communications network including end nodes and network nodes, said end nodes and network nodes being interconnected by transmission groups, said method including the steps of:

receiving from the end nodes information about the characteristics of transmission groups connecting the end nodes to network nodes;

calculating optimal routes from the end nodes to network nodes using received information;

calculating optimal routes between network nodes using information stored in a network topology database; and

combining the results of the above-defined calculating steps to determine the optimal end node-to-end node route.

2. For use in a communications network including end nodes and network nodes, wherein weights are assigned to the various nodes and to transmission groups connecting the nodes as a function of known characteristics of said transmission groups and nodes, a method of determining an optimal route between a first user at an origin end node and a second user at a destination end node, said method comprising the steps of:

calculating the weights of routes from the origin end node to potential origin network nodes;

calculating the weights of routes from the destination end node to potential destination network nodes;

calculating the weights of optimal routes between potential origin network nodes and potential destination network nodes; and

concatenating the weights resulting from the above-defined calculating steps to determine an optimal route from the origin end node to the destination end node.

3. A method as defined in claim 2 wherein the step of calculating the weights of routes connecting potential origin and destination network nodes further comprises the steps of:

compiling a first list of potential origin network nodes comprising all network nodes connected to the origin end node;

compiling a second list of potential destination network nodes comprising all network nodes connected to the destination end node; and

calculating the weights of optimal routes from all nodes on said first list to all nodes on said second list.

4. A method as defined in claim 3 further including the step of caching the results of the final calculating step for possible use in further route computations.

5. A method as defined in claims 2, 3 or 4 further including the steps of:

determining whether there is a direct connection between the origin end node and the destination end node;

comparing the weight of any said direct connection to the weight of an optimal route through the network; and

selecting the direct connection as the optimal connection only where the optimal route through the network has a greater calculating weight.

6. For use in a communications network including end nodes and network nodes, wherein weights are assigned to the various nodes and to transmission groups connecting the nodes as a function of known characteristics of said transmission groups and nodes, a method of enabling a network node serving a first user at an origin end node to determine an optimal route between the first user and a second user at a destination end node when a topology database accessible by said serving network node contains only information about the network nodes and transmission groups interconnecting said network nodes, said method comprising the steps of:

receiving a message at said serving network node from the origin end node, said message including the characteristics of transmission groups connecting said origin end node to network nodes;

storing the characteristics received from said origin end node for use in computing optimal routes from the origin end node to potential origin network nodes before forwarding the message to the destination end node;

receiving a reply message from the destination end node, said message including the characteristics of transmission groups connecting said destination end node to network nodes; and

storing the characteristics received from the destination end node for use in computing optimal routes from potential destination network nodes to the destination end node.