Least cost route selection in distributed digital communication networks

• US 5,317,566 A
• Filed: 08/18/1993
• Issued: 05/31/1994
• Est. Priority Date: 08/18/1993
• Status: Expired due to Fees

• Current Assignee: Ascom Timeplex, Inc.
• Original Assignee: Ascom Timeplex Trading AG
• Inventors: Joshi, Ramchandra
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): Patel, Ajit
• Application Number:
  US08/107,869
• Time in Patent Office: 286 Days
• Field of Search: 370/13, 370/16, 370/54, 370/60, 370/94.1, 370/94.3, 340/826, 340/827, 379/221, 364/200, 395/200
• US Class Current: 370/238
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A distributed digital communications network has an originating node and a multiplicity of destination nodes. The various nodes are interconnected by links and at least some of the nodes are accessible to other nodes only by multiple links. To save time in establishing the least cost path from an originating node to a destination node, the attributes of the various links are stored in memory at the originating node, a least cost path from the originating node to a destination node is calculated in response to a connection request and stored in memory. Then, when a subsequent connection request to any destination node requires the same link attributes as the least cost path already stored in memory, that same least cost path is used if it is still operational. Significant time saving is achieved in that no new least cost calculation need be made.

Claims

1. A method for selecting a least cost route from an originating node in a distributed digital communications network to one of a plurality of destination nodes in said network, the nodes in said network being interconnected by links with at least some of said destination nodes being accessible to said originating node only by multiple links, and at least said originating node having a memory and a processor associated therewith, the method comprising the steps of:

receiving in said processor a connection request including a first set of transmission requirements for a route from said originating node to a designated one of said destination nodes;

storing said first set of transmission requirements in said memory;

calculating in said processor and storing in said memory the least cost route from said originating node to said designated destination node in which each link satisfies said first set of transmission requirements;

establishing the route stored in said memory from said originating node to said designated destination node;

receiving in said processor a second service request including a second set of transmission requirements for a route from said originating node to said designated destination node;

comparing, in said processor, said second set of transmission requirements to said first set of transmission requirements stored in said memory;

if said second set of transmission requirements matches said first set of transmission requirements, then validating the route stored in said memory to determine that it is still functional; and

establishing the route stored in said memory from said originating node to said designated destination node.

2. The method of claim 1 in which both said first and said second sets of transmission requirements include transmission bandwidth.

3. The method of claim 1 in which both said first and said second sets of transmission requirements include transmission delay.

4. The method of claim 1 in which both said first and said second sets of transmission requirements include bit error rate.

5. The method of claim 1 in which both said first and said second sets of transmission requirements include encryption.

6. The method of claim 1 comprising the additional steps, whenever the configuration of said network changes, of:

recalculating in said processor a least cost route from said originating node to each of said destination nodes in which each link satisfies said first set of transmission requirements;

replacing routes stored in said memory with said recalculated routes; and

establishing the recalculated stored least cost route from said originating node to said designated destination node if said second set of transmission requirements matches said first set of transmission requirements.

7. The method of claim 6 in which said recalculation takes place in said processor as a background operation, permitting other operations to be performed as foreground operations.

8. A method for selecting a least cost route from an originating node in a distributed digital communications network to one of a plurality of destination nodes in said network, the nodes in said network being interconnected by links with at least some of said destination nodes being accessible to said originating node only by multiple links, and at least said originating node having a memory and a processor associated therewith, the method comprising the steps of:

receiving in said processor a service request including a first set of transmission requirements for a route from said originating node to a designated one of said destination nodes;

storing said first digital transmission requirements in said memory;

calculating in said processor and storing in said memory a least cost route as a primary route from said originating node to said designated destination node in which each link in said primary route satisfies said first set of transmission requirements;

calculating in said processor and storing in said memory an alternate route from said originating node to said designated destination node in which each link satisfies said first set of transmission requirements, where the cost of said alternate route is no less than the cost of said primary route;

selecting said stored primary route from said memory and establishing it from said originating node to said designated destination node;

receiving in said processor a second service request including a second set of transmission requirements for a route from said originating node to one of said destination nodes;

comparing, in said processor, said second transmission requirements to said first set of transmission requirements stored in said memory;

if said second set of transmission requirements matches said first set of transmission requirements, then validating the stored primary route to determine that it is still functional;

if the stored primary route is not functional, then validating the stored alternate route to determine that it is functional; and

establishing the alternate route stored in said memory from said originating node to said designated destination node.

9. The method of claim 8 in which both said first and said second sets of transmission requirements include transmission bandwidth.

10. The method of claim 8 in which both said first and said second sets of transmission requirements include transmission delay.

11. The method of claim 8 in which both said first and said second sets of transmission requirements include bit error rate.

12. The method of claim 8 in which both said first and said second sets of transmission requirements include encryption.

13. The method of claim 8 comprising the additional steps, whenever the configuration of said network changes, of:

recalculating in said processor a route from said originating node to each of said destination nodes in which each link satisfies said first set of transmission requirements;

replacing routes stored in said memory with said recalculated routes; and

establishing the recalculated stored route from said originating node to said designated destination node if said second set of transmission requirements matches said first set of transmission requirements.

14. The method of claim 13 in which said recalculation takes place in said processor as a background operation, permitting other operations to be performed as foreground operations.