Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-05-20
2004-07-06
Ton, Dang (Department: 2666)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S252000
Reexamination Certificate
active
06760310
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to optimization methods and more particularly, to a system and method for optimizing allocation of multi-service traffic concentrators in a telecommunications network by employing linear programming.
BACKGROUND OF THE INVENTION
A typical telecommunications network includes, transmission components, switching components and facilities for maintaining equipment. Transmission components or links are the media used to transmit signals. Switching components or nodes include transmitters and receivers for voice and data and routers for routing using circuit-switching techniques. The transmission components in the local loop are largely made of copper twisted-pair wiring with the long distance service providers, i.e., the interexchange carriers providing services between local carriers, generally employ fiber-optic cables and radio systems for their backbone trunks and long distance lines. In such a communication network, it is highly desirable to allocate the transmission and switching components optimally such that every component in the network is utilized to its maximum capacity. Furthermore, in order to automate such an optimization procedure, it is also highly desirable to implement a solution that employs a mathematical technique such as linear programming.
Linear programming is generally concerned with the maximization or minimization of a linear object function having many variable terms subject to linear equality and inequality constraints. In its application, linear programming provides the ability to state general objectives or goals and to find optimal policy solutions, i.e., to determine detailed decisions to be taken in order to “best” achieve these goals when faced with practical situations or decision problems of great complexity. An example of an objective may be to minimize total costs or maximize profits measured in monetary units. In other applications, the objective may be to minimize direct labor costs or to maximize the number of assembled parts.
In its implementation, linear programming encompasses models that formulate real word problems in detailed mathematical terms, the algorithm that solve the models and the software that executes the algorithm on computers based on the mathematical theory. Commercial software is presently available for solving linear problems implemented with known mathematical theory, such as the universally known Simplex Method. However, before the software may be used to compute a solution using various mathematical algorithm, a mathematical model representing the real world problem must be built and programmed as an input to the existing software.
Building the mathematical model which represents a specific objective desired in a specific situation or practical application in the real world is frequently referred to as the model formulation or the problem formulation. Although general algorithm for solving linear problems are well known, the formulation of the linear problem is unique to each situation involving various decision making processes and requires an exact artistry to procure the most efficient solution possible. Models of the real world are not always easy to formulate because of the diversity and ambiguity that exists in the real world or because of the ambiguous understanding of it. For instance, linear problem models can be very large in practice, some having many thousands of constraints and variables. Yet, it is possible to abstract a real world problem and formulate it as a collection of mathematical relationships which characterize the set of feasible solutions to that problem. Consequently, it is well known in the field of mathematics that the process of the initial problem formulation is considered an essential and important aspect equally as solving it and merits a field of technological art in itself. Thus, in linear problem programming, it is highly desirable to define and formulate a linear problem well and suited to each unique situation, such that the most optimal solution may be obtained.
Formulating linear problems involves defining decision variables which represent the quantity to be controlled for optimal efficiency, defining item sets or data sets, and setting up constraints and objective functions. Item sets represent the classes or objects that are required as inputs or outputs in a system. Constraints refer to set of rules to which the solution must conform, and the objective function defines the goal desired in a practical application expressed in terms of a mathematical equation. Although there is more than one way to formulate a known problem, only a correct formulation will result in a correct solution. Moreover, the number of decision variables and constraints defined dictates whether or not a correct solution by linear programming can be attained quickly and efficiently. For example, depending on how well the problem is formulated and defined, a linear problem program can take from hours to days to execute before determining a solution. Thus, in linear programming it is also highly desirable to formulate a given problem in a most efficient manner such that a solution may be obtained quickly and efficiently.
In a typical network layout or design, it is always highly desirable to be able to minimize the cost of networking by allocating network circuit equipment including the communication servers, nodes, devices, lines and trunks in a most optimal manner, thereby balancing the available resources such that any unused surplus is utilized and a shortage of resources is avoided. Advantageously, and as described above with reference to linear programming, such network optimization problem provides an ideal application for solution by linear programming. Therefore, it is highly desirable to find an optimal allocation of communication components in a telecommunications network topology employing a linear programming method.
SUMMARY OF THE INVENTION
The present invention provides a system and method for optimally allocating multi-service traffic concentrators in telecommunications network by formulating a unique problem model in terms of mathematical expressions which represents the telecommunications network topology such that the model may be input to a linear programming algorithm for obtaining the most optimal allocation or layout of the network components. To conform to the rules of the linear programming, data set indices, decision variables, constraints and objective functions are selected and defined as parameters that represent the telecommunications network topology.
Data set indices are defined as those components and/or factors in the telecommunications network which affect various operations of the network, and include origination, concentration and destination sites as well as different multiplexer levels at each of the sites. Decision variables representing measures of efficiency in the network and whose optimal values are to be computed by the linear program are defined to include concentrator node selection, concentrator to destination site connection status, and the number of optical carrier trunks for each concentrator. The values for each of the three variables represent the equipment quantity for optimally allocating multi-service traffic concentrators.
The objective function to be minimized is defined as the sum of: the total transmission cost between selected origination sites and selected concentration sites; the total transmission cost between selected concentration sites and selected destination sites; the total unit cost of concentrators; the total port cost on the low side of the concentrators; and the total optical carrier level port cost on the high side of the concentrators and the destination switches. Thus, in setting up the objective function, the transmission costs, the unit costs of equipment, and the backbone switch ports are considered.
Further, the minimization of the objective function is computed subject to the unique constraints defined in the present invention. These constraints include conditions that one
Ton Dang
Tran Phuc
WorldCom, Inc.
LandOfFree
Optimal allocation of multi-service concentrators does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimal allocation of multi-service concentrators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal allocation of multi-service concentrators will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3248638