 |
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
locations for backbone nodes in a distributed data network.
BACKGROUND OF THE INVENTION
The design of distributed data network topologies has been practiccd for
many years. 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 that terminate at backbone nodes, the latter
including one or more devices including a switching device for routing
traffic within the backbone. Data traffic from the concentrators enters
the backbone at the backbone nodes.
Systems for constructing the most efficient arrangement of nodes on the
backbone have been so generic as not to accommodate all of the parameters
typically used in the communications industry. Other approaches have been
so narrowly focused so as to render the system relatively inflexible. The
invention described herein overcomes the deficiencies with a unique system
that permits greater facility for arriving at a particular node
construction. Although certain assumptions are made with respect to local
access cost and node capacity, the user is given great flexibility in
varying many other parameters which control the node construction.
SUMMARY OF THE INVENTION
The present invention is directed to a method used to determine backbone
node locations 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 location of
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 node locations to meet performance
requirements in the most efficient manner. It uses as inputs candidate
backbone node locations, data terminal locations, and data traffic between
those terminals. The cost of the backbone (backbone node switch hardware
and backbone link data line costs) is compared to the cost of the local
access network (terminal-to-backbone node line costs). Both the backbone
and local access network costs are approximated. The invention can also
accommodate a partial list of backbone locations which have been chosen by
the user and select the remaining sites. In another mode of operation, the
user can specify all node locations and have the performance of the
backbone evaluated. The various modes of operation can be compared by
incrementally adding or deleting nodes from the backbone.
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 data terminals and candidate
backbone node sites used as the basis for an example of the method's
operation;
FIG. 4 is a tabular presentation of information about candidate backbone
nodes in the network configuration shown in FIG. 3.
FIG. 5 is a tabular presentation of information about some of the data
terminals in the network configuration shown in FIG. 3;
FIG. 6 is a diagram depicting the data terminals and candidate backbone
node sites shown in FIG. 3 with the backbone node sites selected by the
method; and
FIG. 7 is a tabular presentation of the network topology shown graphically
in FIG. 6.
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 includes a set of
interconnected data terminals S.sub.1 -S.sub.19 ; a variety of terminals
can be used. 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. 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 T between the terminals.
In establishing a network the goal is the most efficient selection of
components to maximize service at the lowest cost. The cost of
establishing the network shown in FIG. 1 can be divided into the cost of
the backbone and the cost of the local access network. The cost of the
backbone includes the cost of the switches located at the backbone nodes
and the cost of the backbone links BL. The cost of the local access
network consists of the cost of concentrators C and data links TL and CL.
The invention is a method for determining that set of backbone node
locations N which will have the least cost combination of backbone costs
and local access network costs based on a set of candidate backbone node
locations NC, terminals S, and traffic volumes T from those terminals.
The hardware components shown schematically in FIG. 1 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, having in addition to a switch such other
devices as concentrators. The links CL, TL, and BL can be analog or
digital transmission lines.
To configure the network, the locations of the terminals, the traffic
volume between the terminals, and the possible locations of backbone nodes
must be known. Each terminal location can be a potential backbone node
location, specified either as an optional site NC or as a mandatory site
NM. The locations of the terminals 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
between the terminals can be specified in the user-chosen form of
bytes/second, packets/second, and calls/second.
The logical flow of the method is illustrated schematically in FIG. 2. The
method works in an incremental fashion. At each stage of the node location
process, each terminal S.sub.i is associated with one of the backbone
nodes already selected. Initially, all mandatory nodes are included and
each terminal S.sub.i is associated with the node physically closest to
the terminal. If no mandatory nodes are specified, the candidate node
NC.sub.i closest to the unweighted center of mass of all of the terminals
is selected and all of the terminals S.sub.i are associated with that
candidate node. This step in the method is shown in step 200 of FIG. 2.
The next step of the method is an add phase. Each candidate node NC.sub.i
not yet selected is evaluated for addition to the backbone. Node N.sub.i
will be added, and therefore terminals associated with the switch at that
location, if the addition of that location produces a positive savings
SAV.sub.i.
The savings SAV.sub.i associated with adding a candidate node NC.sub.i can
be expressed as:
SAV.sub.i =ST.sub.i -CB.sub.i -CS.sub.i
where ST.sub.i is the savings in local access network costs, CB.sub.i is
the change in the cost of the backbone attributed to adding node NC.sub.i,
and CS.sub.i is the cost of adding a switch at node NC.sub.i.
ST.sub.i is the total savings associated with reassigning all those
terminals which would be more cheaply assigned to a switch at candidate
node NC.sub.i than to the switch to which they are currently assigned. The
cost of assigning a terminal S.sub.i to a switch at node N.sub.i is based
on the exact or approximate cost of leasing a direct line from a telephone
service provider to connect the terminal location to the node location.
The cost of leasing the line from the service provider is determined from
the standardized tariff that the provider charges to supply a line of the
required data-carrying capacity over the required distance. The providers'
tariffs are generally monotonically increasing as a function of distance,
so the method assumes that positive savings will always result from
assigning a terminal to the node location which is physically closest to
the terminal.
CB.sub.i is an estimate in the change in the cost of the backbone
associated with adding candidate node NC.sub.i to the backbone. The cost
of a given backbone topology can be estimated as the sum over all pairs of
switches at the backbone nodes of the traffic between those switches times
the cost of sending a unit of traffic between two switches. A table of
traffic for backbone node switches can be constructed from the terminal
traffic table by aggregating traffic from the terminals associated with
each backbone node switch. This in turn can be modeled as a constant
(detour factor) times the direct cost of connecting the two devices.
Referring to FIG. 1, the cost of sending a unit of traffic between nodes
N.sub.1 and N.sub.3 is estimated as the cost, based on the appropriate
tariff of the applicable telephone service provider, of sending that
traffic over the physical distance between the locations of those two
nodes (based on an input data line speed) times a detour factor. This
detour factor reflects the fact that, as is the case with nodes N.sub.1
and N.sub.3, the traffic cannot go directly from one node to the other,
but must instead be routed through an intermediate node, such as N.sub.2.
The detour factor is set based upon assumptions as to the sparsity of the
network and the expected utilization of the backbone links BL. The detour
factor does not vary significantly since the network sparsity and link
utilization are relatively constant among well-designed networks. The cost
CB.sub.i of adding a candidate node NC.sub.i to the backbone is therefore
the cost of the backbone as calculated above with the candidate node in
the backbone less the cost of the backbone without the candidate node.
The invention employs a more efficient, estimated method for calculating
the backbone cost with and without the candidate node. This method
estimates the traffic T.sub.ij between backbone node switches i and j as:
T.sub.ij =T.sub.i T.sub.j /T
where T.sub.i is the total traffic associated with the terminals associated
with backbone node switch i and T is the total traffic in the network.
This method is much less time consuming than making the pairwise
calculations for each combination of backbone node switches. CB.sub.i can
therefore be expressed as:
##EQU1##
where T(i+)jk is the traffic from backbone node switch j to backbone node
switch k assuming a switch at candidate node NC.sub.i is included while
T(i-)jk assumes NC.sub.i is not included, F is the detour factor, T is the
total network traffic, and D(j,k) is the cost per unit traffic for
transmitting data between backbone node switches j and k.
CS.sub.i, the cost of adding a communication switch at candidate node
location NC.sub.i is a fixed cost plus a cost per unit traffic times the
total traffic (both traffic terminating at the switch and traffic
transiting through the switch) associated with the candidate node.
The method iteratively evaluates the remaining candidate nodes, adding in
each iteration the candidate node which provides the greatest savings.
After a candidate node is added to the backbone, the next iteration
evaluates the remaining candidate nodes with the newly added node as part
of the backbone. Because the dominant savings associated with adding a
node is the reduction in local network access cost, which decreases as the
number of backbone nodes increases (because the average distance from
sources to candidate nodes decreases), not all of the remaining candidate
nodes need to be evaluated in each iteration. The candidates can be ranked
by the amount of savings they produce in one iteration and the savings
produced by the top ranked candidate in the current iteration is chosen
unless its associated savings are lower than the savings of the next lower
candidate in the preceding iteration. This iterative process is repeated
until no candidate nodes remain whose addition would create positive cost
savings. In those cases where no mandatory nodes were specified, terminals
that have not been assigned to an added candidate node are assigned to the
calculated center of mass node location.
The next phase in the method of the invention, as shown in step 400 of FIG.
2, is a drop phase. In this phase, the same calculations are made as in
the add phase except that the method considers whether the removal of a
backbone node could produce positive overall savings. It is possible that
dropping a previously added candidate node could produce cost savings
because the added node may have had some of its associated terminals
reassigned to later-added node locations such that its remaining terminals
are more cheaply assigned to other nodes. As with the add phase, the
existing nodes are ranked in order of the magnitude of the savings from
their removal as calculated in one iteration to reduce the number of nodes
that must be considered in the following iteration.
The next step of the method, as shown in step 500 of FIG. 2, fixes the node
locations remaining after the add and drop phases and reassigns each
source to its best (cheapest) switch to minimize the total backbone cost.
The switches are then resized as necessary to correspond to the sources
assigned to the switch.
In the final step, as shown in step 600 of FIG. 2, the method prepares an
estimate of the network cost.
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. This
configuration includes a number of data terminals (shown as solid circles)
and candidate backbone node sites (shown as hollow squares). Information
about the candidate backbone nodes corresponding to the network shown in
FIG. 3 is shown in tabular format in FIG. 4. Id. Information about several
of the data terminals is shown in FIG. 5.
Based on these inputs, the method of the invention configures the network
shown in FIG. 6. Information about the selected backbone nodes is shown in
tabular format in FIG. 7.
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.
* * * * *
|
|
 |
|
 |
Description |
|
