Method for routing data in a near-optimal manner in a distributed data communications network

• US 5,253,161 A
• Filed: 02/06/1990
• Issued: 10/12/1993
• Est. Priority Date: 02/06/1990
• Status: Expired due to Fees

• Current Assignee: Michael Ball, Michael Post, Paul Nemirovsky
• Original Assignee: Michael Ball, Michael Post, Paul Nemirovsky
• Inventors: Post, Michael, Ball, Michael, Nemirovsky, Paul
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): Tran, Khai
• Application Number:
  US07/475,872
• Time in Patent Office: 1,344 Days
• Field of Search: 364/401, 364/402, 364/408, 370/16, 370/94.1, 370/17, 370/60
• US Class Current: 709/241
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A method to produce near-optimal routes for the flow of data between clusters in a distributed data communications network. A backbone traffic matrix and a backbone topology at the cluster level are used to produce minimum hop routes, minimum delay routes, or routes which maximize throughput. The inputs of the system are the number of requirements, the number of backbone links, and the number of backbone nodes.

Claims

1. A method for constructing a data communication network having:

a) a backbone including

i) backbone nodes for routing data traffic within sad backbone, and

ii) a plurality of first links for connecting said backbone nodes,

b) terminals;

c) concentrators;

d) a plurality of second links for connecting said terminals with said concentrators; and

e) a plurality of third links for connecting said concentrators with said backbone nodes, wherein each of said first, second, and third links has an associated traffic delay time and data flow,

comprising the steps of;

1) assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow;

2) determining the shortest routes between each pair of said backbone nodes;

3) placing requirements corresponding to a current data flow pattern onto said shortest routes;

4) storing said shortest routes;

5) determining an approximation of a second derivative of traffic delay time with respect to data flow;

6) determining an amount of slack on each of said shortest routes;

7) rerouting said data flow from all other routes onto said shortest routes based on said first derivative, said second derivative, and said slack;

8) determining an updated data flow of the network; and

9) determining an updated traffic delay time for the updated data flow of the network.

2. The method for constructing a data communication network according to claim 1 further comprising repeating the steps (1) through (9) and selecting for operation the network having a network data flow which incurs a minimum traffic delay time.

3. The method according to claim 1 for constructing a data communication network wherein the concentrators are statistical multiplexers with protocol conversion capabilities.

4. The method according to claim 1 for constructing a data communication network wherein said backbone nodes include data switches.

5. The method for constructing a data communication network according to claim 1 wherein said second links are data lines of telephone service providers.

6. The method for constructing a data communication network according to claim 1 wherein said first links are high volume data lines.

7. The method for constructing a data communication network according to claim 6 wherein said high volume data lines are fiber optic lines.

8. A computer system for constructing a data communication network having:

a) a backbone including,

i) backbone nodes for routing data traffic within said backbone, and

i) a plurality of first links for connecting said backbone nodes,

b) terminals;

c) concentrators;

d) a plurality of second links for connecting said terminals with said concentrators; and

e) a plurality of third links for connecting said concentrators with said backbone nodes, wherein each of said first, second and third links has an associated traffic delay time and data flow,

said computer system comprising;

1) means for assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow;

2) means for determining the shortest routes between each pair of said backbone nodes;

3) means for placing requirements corresponding to a current data flow pattern onto said shortest routes;

4) means for storing said shortest routes;

5) means for determining an approximation of a second derivative of traffic delay time with respect to data flow;

6) means for determining an amount of slack on each of said shortest routes;

7) means for rerouting said data flow from all other routes onto said shortest routes based on said first derivative, said second derivative, and said slack;

8) means for determining an updated data flow of the network; and

9) means for determining an updated traffic delay time for the updated data flow of the network.

9. The computer system according to claim 8 for constructing a data communication network wherein the concentrators are statistical multiplexers with protocol conversion capabilities.

10. The computer system according to claim 8 for constructing a data communication network wherein said backbone nodes include data switches.

11. The computer system for constructing a data communication network according to claim 8 wherein said second links are data lines of telephone service providers.

12. The computer system for constructing data communication network according to claim 8 wherein said first links are high volume data lines.

13. The computer system for constructing a data communication network according to claim 12 wherein said high volume data lines are fiber optic lines.

14. A method for constructing a data communication network having,

a) a backbone including,

i) a plurality of first links for connecting said backbone nodes,

b) terminals;

c) concentrators;

d) a plurality of second links for connecting said terminals with said concentrators; and

e) a plurality of third links for connecting said concentrators with said backbone nodes, and having an associated traffic delay and data flow,

comprising steps of;

(1) assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow;

(2) determining the shortest routes between each pair of said backbone nodes;

(3) assigning at least one requirement to each route;

(4) diverting flow from other routes to the shortest route which meets each of the assigned requirements;

(5) determining a slack value based on a minimum spare capacity of any link in the route;

(6) determining a correction factor based on an estimate of the second derivative of traffic delay with respect to flow, for each link;

(7) determining the amount of diverted flow based on the requirements assigned to each route, a step size, said correction factor, the length of the route and the length of the shortest path, for each route;

(8) setting the amount of diverted flow equal to the slack value divided by the number of nodes when the amount of diverted flow is greater than the slack value divided by the number of nodes;

(9) determining a link delay for each link;

(10) determining a length of each link based on said link delay; and

(11) repeat steps (1) through (10) until change in length is less than said step size.