Method and computer system for selecting and evaluating data routes and arranging a distributed data communication network

• US 5,426,674 A
• Filed: 10/25/1993
• Issued: 06/20/1995
• Est. Priority Date: 02/06/1990
• Status: Expired due to Term

• Current Assignee: Michael Ball, Paul Nemirovsky
• Original Assignee: Michael Ball, Paul Nemirovsky
• Inventors: Ball, Michael, Nemirovsky, Paul
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US08/141,502
• Time in Patent Office: 603 Days
• Field of Search: 395/650, 395/200
• US Class Current: 709/241
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]

Abstract

A method for constructing and utilizing a distributed data communication network that will meet its performance specifications in the most economical and efficient manner. The steps of the method include clustering terminals based on their proximity and traffic; selecting backbone node sites based on cost; designing the access network composed of terminals, concentrators, backbone nodes and the links between them; generating a backbone link topology; and determining routes in the backbone given the backbone topology and a traffic matrix.

Claims

1. A computer based method for selecting and evaluating data routes and arranging a data communication network having a number of terminals, said arranged network including backbone nodes, a plurality of first links connecting the backbone nodes, concentrators connected between said terminals and said backbone nodes, a plurality of second links disposed between and connecting said terminals and said concentrators, and a plurality of third links disposed between and connecting said concentrators and said backbone nodes, said method comprising steps of:

(a) clustering said terminals into terminal clusters and assigning said terminal clusters to virtual terminals, concentrator locations, or backbone node locations;

(b) selecting said backbone nodes from a set of backbone nodes to minimize the cost of the network and adding said selected backbone nodes to the network;

(c) selecting said concentrators from a set of concentrators, assigning said clustered terminals to said selected concentrators, and adding said selected concentrators to the network;

(d) selecting said first links from a set of first links to minimize the cost of said first links and said backbone nodes and adding said selected first links to the network to connect the selected backbone nodes; and

(e) evaluating routes for data traffic between said selected backbone nodes through said selected first links and allocating data traffic among said routes.

2. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, further comprising a step of repeating any one or more of the steps (a) through (e) to further refine the network configuration in response to a previously performed one or more of said steps (a) through (e).

3. The method for selecting and evaluating data routes and arranging a data communication network according to claim 2, wherein said step (b) of selecting said backbone nodes from a set of backbone nodes and adding said selected backbone nodes to the network is repeated to further refine the network configuration in response to said step (c) of selecting said concentrators from a set of concentrators.

4. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, wherein the concentrators are statistical multiplexers with protocol conversion capabilities.

5. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, wherein said backbone nodes include data switches.

6. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, wherein said second links are data lines of telephone service providers.

7. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, wherein said first links are high volume data lines.

8. The method for selecting and evaluating data routes and arranging a data communication network according to claim 7, wherein said high volume data lines are fiber optic lines.

15. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, wherein said step (a) of clustering said terminals into terminal clusters and assigning said terminal clusters is performed in response to inputs including locations of terminals to be clustered and a weight for each of said locations of terminals to be clustered that represents data traffic carried by that location.

16. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, wherein said step (b) of selecting said backbone nodes from said set of backbone nodes and adding said selected backbone nodes to the network is performed in response to inputs including locations of each of said set of backbone nodes, locations of said terminals, and a traffic table which specifies data traffic between said terminals.

17. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, wherein said step (c) of selecting said concentrators from said set of concentrators, assigning said clustered terminals to said selected concentrators, and adding said selected concentrators to the network is performed in response to inputs including said set of concentrators, said terminal clusters, and terminal level requirements for a number of data communication lines and a volume of traffic.

19. The method for selecting and evaluating data routes and arranging a data communication network according to claim 1, wherein said selected backbone nodes and said selected first links together comprise a backbone topology and wherein said step (e) of evaluating routes for data traffic between said backbone nodes through said first links and allocating traffic among said routes is performed in response to inputs including said backbone topology and a backbone traffic matrix which contains data traffic accumulated at a backbone level.

9. A computer system for selecting and evaluating data routes and arranging a data communication network having a number of terminals, said arranged network including backbone nodes, a plurality of first links connecting the backbone nodes, concentrators connected between said terminals and said backbone nodes, a plurality of second links disposed between and connecting said terminals and said concentrators, and a plurality of third links disposed between and connecting said concentrators and said backbone nodes, said computer system comprising:

(a) means for clustering said terminals into terminal clusters and assigning said terminal clusters to virtual terminals, concentrator locations, or backbone node locations;

(b) means for selecting said backbone nodes from a set of backbone nodes to minimize the cost of the network and adding said selected backbone nodes to the network;

(c) means for selecting said concentrators from a set of concentrators, assigning said clustered terminals to said selected concentrators, and adding said selected concentrators to the network;

(d) means for selecting said first links from a set of first links to minimize the cost of said first links and said backbone nodes, and for adding said selected first links to the network to connect the selected backbone nodes; and

(e) means for evaluating routes for data traffic between said selected backbone nodes through said selected first links and allocating data traffic among said routes.

10. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein the concentrators are statistical multiplexers with protocol conversion capabilities.

11. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein said backbone nodes include data switches.

12. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein said second links are data lines of telephone service providers.

13. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein said first links are high volume data lines.

14. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 13, wherein said high volume data lines are fiber optic lines.

20. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein at least one of said means for clustering, means for selecting said backbone nodes, means for selecting said concentrators, means for selecting said first links, and means for evaluating routes is responsive to at least one other one of said means for clustering, means for selecting said backbone nodes, means for selecting said concentrators, means for selecting said first links, and means for evaluating routes.

21. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 20, wherein said means for selecting said backbone nodes from a set of backbone nodes and adding said selected backbone nodes to the network further refines the network configuration in response to said means for selecting said concentrators from a set of concentrators.

22. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein said means for clustering said terminals into terminal clusters and assigning said terminal clusters is responsive to inputs including locations of terminals to be clustered and a weight for each of said locations of terminals to be clustered that represents data traffic carried by that location.

23. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein said means for selecting said backbone nodes from said set of backbone nodes and adding said selected backbone nodes to the network is responsive to inputs including locations of each of said set of backbone nodes, locations of said terminals, and a traffic table which specifies data traffic between said terminals.

24. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein said means for selecting said concentrators from said set of concentrators, assigning said clustered terminals to said selected concentrators, and adding said selected concentrators to the network is responsive to inputs including said set of concentrators, said terminal clusters, and terminal level requirements for a number of data communication lines and a volume of traffic.

25. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein said means for selecting said first links to minimize the cost of said first links and said backbone nodes is responsive to inputs including locations of the set of backbone nodes, a backbone traffic matrix which contains data traffic accumulated at a backbone level, and a list of links available for inclusion in the network as said first links connecting said backbone nodes.

26. The computer system for selecting and evaluating data routes and arranging a data communication network according to claim 9, wherein said selected backbone nodes and said selected first links together comprise a backbone topology and wherein said means for evaluating routes for data traffic between said backbone nodes through said first links and allocating traffic among said routes is responsive to inputs including said backbone topology and a backbone traffic matrix which contains data traffic accumulated at a backbone level.

18. A computer based method for selecting and evaluating data routes and arranging a data communication network having a number of terminals, said arranged network including backbone nodes, a plurality of first links connecting the backbone nodes, concentrators connected between said terminals and said backbone nodes, a plurality of second links disposed between and connecting said terminals and said concentrators, and a plurality of third links disposed between and connecting said concentrators and said backbone nodes, said method comprising steps of:

(a) clustering said terminals into terminal clusters and assigning said terminal clusters to virtual terminals, concentrator locations, or backbone node locations;

(b) selecting said backbone nodes from a set of backbone nodes to minimize the cost of the network and adding said selected backbone nodes to the network;

(c) selecting said concentrators from a set of concentrators, assigning said clustered terminals to said selected concentrators, and adding said selected concentrators to the network;

(d) selecting said first links from a set of first links to minimize the cost of said first links and said backbone nodes and adding said selected first links to the network to connect the selected backbone nodes; and

(e) evaluating routes for data traffic between said selected backbone nodes through said selected first links and allocating data traffic among said routes;

wherein said step (d) of selecting said first links to minimize the cost of said first links and said backbone nodes is performed in response to inputs including locations of the set of backbone nodes, a backbone traffic matrix which contains data traffic accumulated at a backbone level, and a list of links available for inclusion in the network as said first links connecting said backbone nodes.