US 5,404,451 AGrant
System for Identifying Candidate Link, Determining Underutilized Link, Evaluating Addition of Candidate Link and Removing of Underutilized Link to Reduce Network Cost
Issue Date:1995-04-04
•10 Claims
•9 Drawing Sheets
Abstract
A method for selecting the most cost-efficient configuration for backbone links in a distributed data network is disclosed. The method identifies candidate links between pairs of backbone nodes, evaluates the effect on the network of adding each candidate link to the network, and adds to the network those candidate links which produce a cost savings in the network. The method also routes data through the backbone to minimize transmission delays, and eliminates redundant lines from underutilized links, and removes from the network those links whose removal reduces the cost of the backbone.
Metadata
Inventors
- Paul Nemirovsky
- Michael Ball
- Michael Post
Application Information
Application Number:US 0387568
Filing Date:1993-03-29
Priority Date:1990-02-06
Art Unit:237
Classifications
IPC:
G06F 1300
Field of Search:
395364370371200200;242.9416;17;94.1;94.311.1;11.2;20.1;60
Patent Drawings (9 sheets)
Description
Field of the Invention
This invention relates generally to distributed data communication networks and, more specifically, to a method for selecting the most cost-efficient configuration for backbone links in a distributed data communication network.
Background of the Invention
The design of distributed data network topologies has been practiced for many years. The need for a comprehensive method for constructing a distributed data communication network results from the complexity of such a system. A distributed data communication network is a hierarchical system of hardware components arranged to connect each hardware device, directly or indirectly, to every other device. At the lowest level in the hierarchy are user terminals or host devices, which form part of the local access network. These terminals are linked to one or more concentrators, which are statistical multiplexers with several low data rate input data lines and fewer high data rate output data lines. The concentrators form the second level of the network hierarchy and, together with the terminals, form the local access network.
The concentrators, which may be connected to other concentrators in a hierarchical fashion, are ultimately connected to the backbone, which forms the highest level in the network hierarchy. The backbone consists of high data capacity lines, or backbone links, that terminate at backbone nodes. A backbone node consists of one or more devices including switching devices for routing traffic within the backbone. Data traffic from the concentrators enters the backbone at the backbone nodes via the switches. A collection of terminals and associated concentrators are aggregated into a cluster and the devices in the cluster all connect to one or more switches at a single backbone node. More than one cluster may be associated with a single backbone node.
The backbone links can be conventional 56 kilo-bit per second data lines or fiber optic T1 lines effectively comprising 24 56 k lines. T1 lines offer lower cost per unit capacity, while multiple 56 k lines offer higher reliability through redundancy than a single T1 line. A well designed backbone will frequently require use of both T1 lines and 56 k lines to achieve required levels of reliability and performance at the lowest possible cost. Some of the existing backbone link configuration methods design backbones based on T1 lines, while others use 56 k lines. None of the existing methods are capable of designing a backbone based on a combination of T1 and 56 k lines. The invention described herein overcomes the deficiencies of the existing methods with a system that permits the configuration of a hybrid backbone incorporating both T1 and 56 k lines as backbone links. The invention also allows the use of three alternative initial network topologies.
Summary of the Invention
The present invention is directed to a method used to select backbone links in a distributed data network that overcomes the limitations of the prior art. More specifically, the invention is composed of a personal computer-based software tool used to aid in the selection of backbone links between specified backbone nodes in distributed data communication networks that make use of equipment provided by Telenet Communications Corporation as well as similar equipment from other vendors. These networks include the Telenet Public Data Network, private networks that employ Telenet equipment and hybrid networks that contain both privately-owned components and public data network equipment.
The invention selects a set of backbone links to meet performance requirements in the least costly manner. It uses as inputs backbone cluster locations and data traffic between those clusters. The method can generate a set of candidate links using one of two methods or can accept a set of candidate links specified by the user. The method is also capable of integration into a global network optimization method. The user can also exercise significant control over the configuration process by specifying the values of important parameters.
The above is a brief discussion of some of the prior art and features of the invention. Other advantages of the invention can be gleaned from the detailed discussion of the preferred embodiment that follows.
Brief Description of the Drawings
FIG. 1 is a diagram depicting a distributed data communications network comprising terminals, concentrators, and backbone nodes and the data line links connecting those devices;
FIG. 2 is a flow chart diagram of the steps of the invention;
FIG. 3 is a diagram depicting a set of backbone clusters used as the basis for an example of the method's operation;
FIG. 4 presents tabular information about the some of the terminals of the network shown in FIG. 3;
FIG. 5 presents tabular information about the concentrators and backbone clusters of the network shown in FIG. 3;
FIG. 6 presents additional tabular information about the concentrators of the network shown in FIG. 3;
FIG. 7 presents tabular information about data traffic between backbone nodes in the network shown in FIG. 3;
FIG. 8 is a diagram depicting the network of FIG. 3 in its final topology as configured by the method; and
FIG. 9 is a tabular description of the backbone link topology produced by the method, corresponding to the topology shown graphically in FIG. 8.
Detailed Description of the Preferred Embodiment
In describing an illustrative embodiment, it is helpful in conveying the principles of the present invention to consider the specific network depicted in FIG. 1. Although this network is less complex than those encountered in practice, the small size of the network allows for brevity of description without loss of generality. The network consists of a set of interconnected data terminals S.sub.1 -S.sub.19 ; these can be a variety of data terminals. The terminals are connected to concentrators C.sub.1 -C.sub.8 which are statistical multiplexers such as one of the Telenet Communications Corporation model number TP 3000 series multiplexers. The concentrators are in turn connected to backbone nodes N.sub.1 to N.sub.4 ; the backbone nodes contain data switches such as a Telenet Communications Corporation TP4/III series switch.
The links TL.sub.1 -TL.sub.19 between the terminals and the concentrators are data lines leased from local telephone service providers, as are the links CL.sub.1 -CL.sub.8 between the concentrators and backbone nodes. The backbone nodes are connected by backbone data link lines BL.sub.1 -BL.sub.5, which are high-volume leased data lines such as T1 fiber optic lines leased from a long-distance telephone service provider such as U.S. Sprint and conventional 56 k lines from a provider such as AT&T. The backbone nodes N and the backbone links BL collectively form the backbone of the data communications network. The terminals S, concentrators C, and data links TL and CL collectively form the local access network. Data is transmitted between the terminals S through the backbone and the local access network. The amount of data which flows per unit time through the network from one terminal to another terminal is the traffic volume TS between the terminals.
The invention is a method for determining the least-cost set of backbone links BL based on a set of backbone node locations N and traffic volumes TR from the clusters located at those backbone nodes.
The hardware components shown schematically in FIG. 3 can represent a variety of hardware devices. Each terminal S.sub.i can also represent a virtual terminal composed of an aggregate of more than one physical terminal. In general, a single physical location may have more than one hardware device. Similarly, a backbone node N.sub.i can consist of more than one hardware device, which can have one or more switches. A collection of terminals and associated concentrators are aggregated into a cluster R and the devices in the cluster all connect to one or more switches at a single backbone node. More than one cluster R may be associated with a single backbone node. For example, in FIG. 1 concentrator C.sub.3 and its associated terminals could comprise one cluster associated with a switch at node N.sub.2 and concentrator C.sub.4 and its terminals could comprise another cluster associated with another switch at node N.sub.4. The location of a cluster's switch defines the "location" of a cluster. The links CL, TL, and BL can be analog or digital communications lines.
In order to configure the network, the locations of the backbone clusters R and the traffic volume TR between the clusters must be known. The locations of the clusters R in the network can be fixed in a two-axis coordinate system by specifying their locations in standard AT&T V,H coordinates or as area code/exchange locations. The traffic volumes TR between the clusters R can be specified in the form of bytes/second, packets/second, or calls/second. The traffic from cluster R.sub.i to cluster R.sub.j is TR.sub.ij.
The logical flow of the method is illustrated schematically in FIG. 2. In the first step 100 the required input information is supplied. The next step, as shown in step 200 of FIG. 2, is to establish an initial, minimal backbone link topology. The user can supply the initial topology or the method can generate it using one of two techniques. The first technique for generating an initial topology employs Kruskal's Algorithm for finding a minimum spanning tree. This technique is well known. The second technique is a pq-median based topology. By either technique, the result is an initial, minimal set of backbone links which, although they connect all of the backbone cluster locations, do not necessarily do so in the most efficient manner.
The next step of the method is an add phase in which other links are considered for addition to the minimal backbone link topology established in the first step. The method first identifies a set of candidate links for addition to the network, as shown in step 300 of FIG. 2. To identify candidate links, the method first determines the shortest path between each pair of backbone clusters along the links of the initial topology using the standard technique of Floyd's Algorithm. The method then determines the length of a direct link between each pair of clusters and compares the direct length to the shortest path in the initial topology. The set of candidate additional links are all those direct links for which the ratio of direct length to shortest existing path is less than a specified value less than 1.
As shown in step 400 of FIG. 2, the method next evaluates each of the candidate links for inclusion in the backbone, with the object of constructing the lowest-cost backbone. For each candidate link, the method determines how much its inclusion in the backbone would reduce the shortest paths between all of the pairs of nodes. This is an iterative evaluation process. In each iteration, the method determines a figure of merit for each candidate link and adds that candidate link with the highest figure of merit to the backbone. The figure of merit FM is determined as follows:
where TR.sub.i,j is the traffic between clusters R.sub.i and R.sub.j, D.sub.k+(i,j) is the shortest path distance between R.sub.i and R.sub.j with candidate link k in the network and D.sub.k-(i,j) is the shortest path distance between the clusters without k in the network. The shortest path with and without the candidate link is determined using the incremental shortest path algorithm of Murchland, Dionne, and Florian. The best candidate link added to the backbone in one iteration becomes part of the backbone for purposes of evaluating candidate links in the next iteration.
In each iteration, the method calculates the cost of the backbone. The cost of the backbone is the sum of the cost of its constituent links. Each link is composed of one or more lines leased from a long-distance telephone service provider. The cost of leasing each line is determined from the provider's tariff for the type of line and the distance between the endpoints of the line. The number of lines required in each link, which is the link's multiplicity, is determined by the volume of traffic which must be carried on that link and the capacity of individual lines.
The method continues to evaluate candidate links and add the link with the highest figure of merit until the figure of merit for the best candidate link falls below a user-specified threshold. The method then determines which of the prior iterations produced the lowest-cost backbone. The lowest-cost backbone is not necessarily the one produced by the addition of the best candidate link in the last iteration.
In the next phase of the method, as shown in step 500 of FIG. 2, the multiplicity of links with low utilization is reduced. The traffic is routed through the network to produce the minimum delay between transmitting data from a source node and receiving the data at a target node. The method then identifies those links which have a lower utilization rate (ratio of traffic routed through the link to link data capacity) than a user-specified minimum utilization threshold and eliminates one or more lines from that link so that the link's utilization exceeds the minimum utilization threshold. The method establishes minimum.-delay routing and eliminates unnecessary lines iteratively until no more lines can be eliminated.
The next phase in the method of the invention, as shown in step 600 of FIG. 2, is a drop phase. In this phase, the method reevaluates lines to eliminate unnecessary lines. In the process described above, the method selects T1 lines and/or standard 56 k lines to produce an optimum backbone.
The operation of the method can be illustrated with an example. The example presented here is based on the network configuration shown in FIG. 3. Information about several of the terminals in the network is presented in tabular form in FIG. 4. Information about the concentrators and the backbone nodes is presented in FIG. 5 and FIG. 6. Information about the data traffic between backbone nodes is presented in FIG. 7.
The final network configuration produced by the method in this example is shown in FIG. 8. This configuration is also shown in tabular format in FIG. 9
The preferred embodiment of the invention described above represents one desirable, workable embodiment of the invention. It is to be understood that the methodology described herein is not limited to specific forms disclosed by way of example and illustration, but may assume other embodiments and methods limited only by the scope of the appended claims and their equivalents.
Claims
What is claimed is:
1. A computer implemented method for constructing a data communication network having a number of terminals comprising: i) backbone nodes for routing data traffic within a backbone; and ii) a plurality of first links connecting the backbone nodes; said method comprising steps of: (a) finding a shortest path between pairs of said backbone nodes; (b) identifying a candidate link between each pair of backbone nodes for which a length of said candidate link is shorter than the shortest path between the pair of backbone nodes; (c) evaluating an effect on the network of adding each candidate link to the network and adding those candidate links which reduce a cost of the network; (d) determining routing paths along said first links which produce a minimum delay for traffic between said backbone nodes and reducing a capacity of first links that are underutilized; and (e) evaluating an effect of removal of a first link on the network and removing the first link if the effect of removal of the first link is to reduce the cost of the network.
2. The method for constructing a data communication network according to claim 1 further comprising repeating steps (a) through (e) and selecting a lowest cost system to transmit data between said terminals.
3. The method according to claim 1 for constructing a data communication network wherein said backbone nodes include data switches.
4. The method for constructing a data communication network according to claim 1 wherein said first links are high volume data lines.
5. The method for constructing a data communication network according to claim 4 wherein said high volume data lines are fiber optic lines.
6. The method for constructing a data communication network according to claim 1 wherein said step of evaluating and adding candidate links to the network comprises identifying a best candidate link to add to the network, adding the best candidate link to the network, calculating the cost of the network with the added best candidate link, and repeating the step until a savings produced by the addition of the best candidate link is below a specified threshold.
7. A computer system for constructing a data communication network having a number of terminals comprising: i) backbone nodes for routing dam traffic within the backbone; and ii) a plurality of first links connecting the backbone nodes; said computer system including: (a) means for finding a shortest path between pairs of said backbone nodes; (b) means for identifying a candidate link between each pair of backbone nodes for which a length of said candidate link is shorter than the shortest path between the pair of backbone nodes; (c) means for evaluating the effect on the network of adding each candidate link to the network and adding those candidate links which reduce a cost of the network; (d) means for determining routing paths along said first links which produce a minimum delay for traffic between said backbone nodes and reducing a capacity of first links that are underutilized; and (e) means for evaluating an effect of removal of a first link on the network and removing the first link if the effect of removal of the first link is to reduce the cost of the network.
8. The computer system for constructing a data communication network to claim 7 wherein said backbone nodes include data switches.
9. The computer system for constructing a data communication network according to claim 7 wherein said first links are high volume data lines.
10. The computer system for constructing a data communication network according to claim 9 wherein said high volume data lines are fiber optic lines.