Communications network and method which implement diversified routing

• US 5,608,721 A
• Filed: 04/03/1995
• Issued: 03/04/1997
• Est. Priority Date: 04/03/1995
• Status: Expired due to Term

• Current Assignee: CDC Propriete Intellectuelle
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Natarajan, Kadathur S., Murty, Katta G.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Blum, Russell
• Application Number:
  US08/415,800
• Time in Patent Office: 701 Days
• Field of Search: 370/16, 370/17, 370/54, 370/58.2, 370/60, 370/94.1, 370/95.1, 370/95.3, 370/110.1, 455/12.1, 455/13.1, 379/113, 379/133, 379/134, 379/139, 379/220, 379/221
• US Class Current: 370/238
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A communications network (20) includes any number of moving switching nodes (30) and a route-determining node (28). The route-determining node (28) performs an off-line procedure (58) to define a-priori routing for the entire network. This procedure (58) is performed repetitively to track switching node (30) movement and to define routing for numerous epochs included in a planning period. The procedure (58) includes a process (86) for determining all shortest path routes between all possible origination and destination switching nodes (30). Another process (84) matches predicted call traffic for a subject epoch with the shortest path routes. Another process (88) generates routing code tables (54) in response to the predicted call traffic matched to shortest path routes. This process (88) assigns logical routing IDs (52) to physically distinct, shortest path routes in proportion to the predicted call traffic allocated to the distinct routes.

Claims

1. A method of sending information through a network having a plurality of switching nodes, said switching nodes including a destination node, an origination node, and any number of intermediate nodes, and said method comprising the steps of:

identifying a plurality of physically distinct, shortest paths through said intermediate nodes between said origination and destination nodes;

appending routing data to said information, said routing data describing one of said paths;

routing said information through said network in response to said appended routing data;

assigning each of said paths a route identification code, said route identification code serving as said routing data

conveying said route identification code using N bits of data, where N is an integer number; and

when less than 2^N shortest paths exist through said intermediate nodes between said origination and destination nodes, assigning multiple ones of said route identification codes to individual ones of said paths.

2. A method as claimed in claim 1, wherein every node in said network communicates with at least one other node through communication links;

and

wherein said method further comprises the step of predicting call traffic in said network.

3. A method as claimed in claim 2, wherein said method further comprises the step of defining a maximum capacity for each of a plurality of links in said network.

4. A method as claimed in claim 3, wherein said identifying step comprises the steps of:

defining a first network configuration that associates each of said links with pairs of said switching nodes;

searching said first network configuration to determine said shortest paths;

allocating said predicted call traffic to said links included in said shortest paths from said first network configuration;

identifying fully-loaded links, said fully-loaded links being links in said first network configuration for which said predicted call traffic exceeds said maximum capacity, said call traffic in excess of said maximum capacity being predicted excess call traffic;

defining a second network configuration that omits said fully-loaded links;

searching said second network configuration to determine additional shortest paths; and

allocating said predicted excess call traffic to said links included in said shortest paths from said second network configuration.

5. A method as claimed in claim 1, wherein every node in said network communicates with at least one other node through communication links, said method further comprises the step of defining a maximum capacity for each of a plurality of links in said network.

6. A method as claimed in claim 1, wherein:

said identifying step includes the step of associating said paths with a future epoch; and

said appending and routing steps occur substantially at said future epoch.

7. A method as claimed in claim 6, further comprising the steps of:

repeating said identifying step for each of a plurality of future epochs so that an identified plurality of physically distinct shortest paths are associated with each future epoch; and

repeating said appending and routing steps substantially at each of said future epochs in correspondence with said shortest paths identified therefor.

8. A method as claimed in claim 7, wherein a route-determining node of said network is physically separated from said origination node, and said method further comprises the steps of:

performing said identifying step at said route-determining node;

forming said routing data at said route-determining node in response to said identified shortest paths; and

communicating said routing data to said origination node prior to said future epochs.

9. A method as claimed in claim 1, wherein said method further comprises the steps of:

predicting call traffic over said paths; and

assigning said multiple ones of said route identification codes to said individual ones of said paths roughly in proportion to predicted call traffic over said paths.

10. A method as claimed in claim 1, further comprising the step of:

dividing said information into a plurality of distinct calls; and

wherein said appending step comprises the step of configuring said routing data so that said calls are split among said paths.

11. A method of sending information through a network having a plurality of switching nodes, said switching nodes including a destination node, an origination node, and any number of intermediate nodes, every node in said network communicating with at least one other node through communication links, said method comprising the steps of:

predicting call traffic over each of a plurality of links in said network;

identifying a plurality of physically distinct, shortest paths through said intermediate nodes between said origination and destination nodes, said shortest paths being formed from sets of said links, and said identifying step being responsive to said predicted call traffic over said links;

assigning each of said shortest paths a route identification code;

appending one of said route identification codes to said information, said appending occurring at said origination node; and

routing said information through said network in response to said appended route identification code;

conveying said route identification code using N bits of data, where N is an integer number; and

when less than 2^N shortest paths exist through said intermediate nodes between said origination and destination nodes, assigning multiple ones of said route identification codes to individual ones of said shortest paths.

12. A method as claimed in claim 11, further comprising the step of defining a maximum capacity for each of said links in said network.

13. A method as claimed in claim 12, wherein said identifying step comprises the steps of:

defining a first network configuration that associates each of said links with pairs of said switching nodes;

searching said first network configuration to determine said shortest paths;

allocating said predicted call traffic to said links included in said shortest paths from said first network configuration;

identifying fully-loaded links, said fully-loaded links being links in said first network configuration for which said predicted call traffic exceeds said maximum capacity, said call traffic in excess of said maximum capacity being predicted excess call traffic;

defining a second network configuration that omits said fully-loaded links;

searching said second network configuration to determine additional shortest paths; and

allocating said predicted excess call traffic to said links included in said shortest paths from said second network configuration.

14. A method as claimed in claim 11, further comprising the steps of:

predicting call traffic over said shortest paths; and

assigning said multiple ones of said route identification codes to said individual ones of said shortest paths roughly in proportion to said predicted call traffic over said shortest paths.

15. A method as claimed in claim 11, further comprising the steps of:

repeating said identifying and assigning steps for each of a plurality of future epochs so that an identified plurality of physically distinct shortest paths are associated with each future epoch; and

repeating said appending and routing steps substantially at each of said future epochs in correspondence with said shortest paths identified therefor.

16. A communication network for sending information between nodes comprising:

a route-determining node configured to identify sets of physically distinct, shortest paths between various other nodes of said network;

an origination node, in data communication with said route-determining node, said origination node being configured to append route identification codes to said information, said route identification codes describing one of said shortest paths, and to send said information and route identification codes over a first communication link chosen in response to said route identification codes, said route identification codes being conveyed using N bits of data, and when less than 2^N shortest paths exist assigning multiple ones of said route identification codes to individual ones of said shortest paths;

an intermediate node configured to receive said information and appended route identification codes from said first communication link and to send said information and route identification codes over a second communication link chosen in response to said route identification codes; and

a destination node configured to receive said information from said second communication link.

17. A communication network as claimed in claim 16, further comprising the step of:

dividing information sent between said origination and destination nodes into a plurality of distinct calls; and

configuring said origination node so that said calls are split among said shortest paths.

18. A communication network as claimed in claim 16, further comprising the steps of:

configuring said route determining node to predict call traffic over communication links in said shortest paths and to assign a route identification code to each of said shortest paths, said route identification code serving as said routing data; and

configuring said route determining node to assign said route identification codes to said shortest paths roughly in proportion to said predicted call traffic over communication links included in said shortest paths.