Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system
Reexamination Certificate
1999-02-23
2002-03-26
Teska, Kevin J. (Department: 2763)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
C703S002000
Reexamination Certificate
active
06363334
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to telecommunication networks of the kind that comprise nodes and trunks (or links) for carrying communication traffic among the nodes. More particularly, this invention relates to methods for designing such networks; i.e., for determining the layout of the physical interconnections within the network, and for choosing the trunk types for implementing such interconnections. Still more particularly, this invention relates to optimization methods for achieving such interconnections at least cost.
BACKGROUND OF THE INVENTION
Trunks for carrying telecommunications traffic may be classified according to capacity and according to cost per mile (for purchasing or leasing the trunks). Typically, the cost per mile is not proportional to the capacity, but instead increases much less than linearly as the capacity is increased. For example, Table 1 gives a typical set of leasing prices for trunks of four types. As a consequence of such cost structures, an economy of scale is often achieved by concentrating traffic to or from relatively many nodes into relatively few trunks, at least in specific portions of a network.
TABLE 1
Type
Capacity (kbps)
Cost (in dollars)/mile
DSO
64
4
DS1
1544
23
DS3
44736
200
OC3
155520
300
Some communication networks lend themselves to an access network model, in which such economies of scale may be substantial. With reference to
FIG. 1
, such a network consists of core nodes
10
occupying a central core
15
, and a distribution of end nodes
20
. Links
25
interconnect the nodes. Each link comprises one or more trunks. Each of the core nodes typically has switching capability, and the core nodes are highly interconnected.
The end nodes are connected to the core via access network
35
. To achieve economies of scale, traffic from neighboring end nodes is advantageously multiplexed on to relatively high-capacity trunks
30
on its way to the core. Conversely, traffic destined for the end nodes is demultiplexed after leaving the core.
In effect, the core, as a whole, serves as a main switch for traffic between the end nodes. For example, traffic to be routed from end node A to end node B may go first from A to core node C, then across the core to core node D, and finally to end node B.
Every node that lies outside the core is referred to here as an end node, even if it is an intermediate point for traffic to or from multiple other end nodes.
As a general rule, the nodes
20
of an economically efficient access network are organized by the links into a tree-like structure, as shown in FIG.
2
. (In the figure, the links are denoted by reference numeral
40
.) Links in such a structure have various branching depths, such as 1, 2, 3, and 4 in the case of links
40
.
1
,
40
.
2
,
40
.
3
, and
40
.
4
of the figure, respectively. It will be apparent from the figure that there is no unique way to define such a structure. Instead, the branching depth of the link that reaches any given end node, and the branch (or sub-branch, etc.) with which any given end node is associated, are matters of design choice. Additionally, it is a matter of design choice whether to add capacity to a link by multiplying trunks of the same type, or by substituting trunks of higher capacity.
The design choices will generally be directed toward minimizing the total cost of the access network, while accommodating the expected demand from each of the end nodes. To “accommodate demand” means to provide sufficient capacity to carry demand to or from the respective end nodes. For convenience, we will refer to this desideratum as accommodating demand from the end nodes. It should be understood, however, that the actual flow of data may be to the end nodes, from the end nodes, or bidirectional.
The cost of the access network will be determined by the lengths of the various trunks that are installed, by the number of trunks of a given type that are installed between a given pair of nodes, and by the cost structure. Thus, each design choice will have an impact on the total cost of the access network. When there are only a few nodes in the access network, it is tractable to examine the most reasonable design choices and to identify those that result in minimum cost. However, practical access networks often have many tens, hundreds, or even thousands of nodes. In such cases, it is generally necessary to use an automated procedure to find a network design having relatively low cost.
Trunks must be acquired (i.e., purchased or leased—the term purchase will be used herein to denote any type of acquisition) in whole units. Therefore, the problem of finding the least-cost network design lends itself naturally to the methodologies of integer programming (IP). The integer program is defined by the cost function to be minimized, and by the constraints to which the minimization is subject. The designer typically specifies the locations of the end nodes (thus determining the lengths of the pertinent trunks), the available trunk types, the cost structure, and the demand from each node. Conventionally, the cost structure specifies a capacity and a cost per mile for trunks of each respective type.
Unfortunately, the IP problem is NP-hard. As those versed in the relevant airts will appreciate, this implies that there can be no assurance that the optimal design has been achieved, or even approached, within any specified computation time that is practical in a commercial sense. As a consequence, IP formulations are of limited value in designing access networks of significant size.
An alternative to IP is to formulate the problem according to the methodologies of linear programming (LP). In an LP formulation, it would be permissible to purchase fractional trunks. Thus, certain strictures imposed by the IP approach are relaxed. As a consequence, the computational problem (in an LP formulation) becomes tractable.
However, such an approach can lead to inutile solutions. That is, a rounding rule could be applied to the LP solutions, which are largely expressed in terms of fractional purchased trunks, to derive realizable solutions using integral trunks. Naive applications of LP fail to constrain the problem in such a way that the optimal unrounded solution remains economically efficient after rounding.
One earlier approach to the design of least-cost networks is described in F. S. Salman et al., “Approximating the Single-Sink Edge Installation Problem in Network Design,”
Proceedings of the ACM
-
SIAM Symposium on Discrete Algorithms
(
SODA
1997), pp. 619-628. In that approach, which is limited to Euclidean metric spaces, a procedure of constructing successively smaller grids is used to distinguish between nodes that are relatively distant and those that are relatively close together.
Those authors were able to provide a performance bound of O(log D) for their approach, where D represents the total demand. That is, the total cost of a network designed by the method of Salman et al. is guaranteed to lie within O(log D) of the optimal cost. (The meaning of “O( . . . )” is explained below.) A performance bound is useful for choosing between design methods on a worst-case basis. However, a performance bound that is too great gives little or no assurance that, in practice, the pertinent method will give commercially desirable results.
Another such approach is described in B. Awerbuch and Y. Azar, “Buy-at-Bulk Network Design,” in
Proceedings of the
38
th
Annual Symposium on Foundations of Computer Science
, Miami Beach, Fla., October 1997, pp. 542-547. In that approach, the authors applied a method, referred to as a tree metric embedding method, for approximating distances within the network by distances on a tree structure. Those authors provided a performance bound of O(log N)
2
, where N represents the number of nodes in the network.
Large total demands are often encountered in actual networks, and practical networks often include large numbers of nodes. Therefore, the performance bounds provided by the method of Salman et al. and by the method of Awerbuch et al. may, in p
Andrews Daniel Matthew
Zhang Yihao Lisa
Finston M. I.
Jones Hugh
Lucent Technologies - Inc.
Teska Kevin J.
LandOfFree
Linear programming method of networking design for carrying... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Linear programming method of networking design for carrying..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear programming method of networking design for carrying... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2855906