Multiplex communications – Network configuration determination – In a bus system
Reexamination Certificate
1999-12-22
2003-11-25
Kizou, Hassan (Department: 2662)
Multiplex communications
Network configuration determination
In a bus system
C370S255000, C379S112050
Reexamination Certificate
active
06654354
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates generally to communications networks. More particularly, the present invention relates to a system and method for optimizing the deployment of network elements over a period of time in a network, e.g., a Fiber Optic Network, that routes bandwidth demands having multiple channel rate requirements and variable time points. In addition, the present patent application provides a scheme for routing demands in a Fiber Optic Network using Time Slot Assignment (TSA) technology.
2. Description of Related Art
Installing, maintaining, and upgrading a communications network is very costly. Huge expenditures are involved in deploying suitable network equipment at predetermined locations and establishing transmission paths or conduits therebetween via an appropriate physical medium (or, media). Because of these cost considerations, network operators have to be circumspect about when and where to put in a new network or expand an existing one.
Furthermore, information transport—the primary function of a communications network—needs to be efficiently performed in a network in order to optimize its size so that costs associated with unnecessary expansion of the network, sub-optimal deployment/upgrading of the equipment, etc., for example, are avoided. As is well known, efficient network usage generally implies using available channel capacity or capacities efficiently, in addition to employing techniques that achieve cost-effective routing of information via available network equipment.
It should be readily apparent that there is a need for planning tools that enable network operators and owners to schedule equipment deployment intelligently, especially in light of the aforementioned considerations. In addition, such tools have lately become even more essential because of the ever-increasing need for the deployment of high-capacity networks (thus involving more sophisticated and expensive equipment) capable of transporting a wide variety of information—voice, data, video, multimedia, and the like—at phenomenal transport rates.
Conventional solutions in this regard typically employ mathematical modeling or simulation techniques coupled with optimization procedures to arrive at estimates for placement of network equipment that routes information as efficiently as possible. Although such methodologies represent a significant advancement in the field of communications network modeling, there exist several shortcomings and deficiencies in the state of the art.
First, the existing methods treat demand, a quantified volume of bandwidth requested to transfer information over a network path, as a time-independent parameter, thereby compressing all demands—current and projected—to be serviced by the network to a single point in time. In other words, all network equipment required to satisfy both current and projected demands is treated as operational at a single instance. Those skilled in the art should readily recognize that while such a technique may yield a “good” first approximation, it is nevertheless unsatisfactory for accurate planning purposes where new network portions (e.g., rings) are built in a phased manner across the life of a deployment plan, typically stretching over several quarters or years.
Further, as a by-product of treating demands as time-invariant entities, resultant mathematical formulations become formidable because, typically, several hundreds of thousands of demand quantities—including demand forecasts—need to be optimized (that is, demands to be optimally routed in a network) over a deployment plan. Computation loads therefore become enormous, leading to critical time delays in obtaining results which often tend to be unstable because of the unwieldy modeling efforts.
In addition, the existing solutions typically consider only a single type of channel bandwidth for the demand quantities that need to be optimized. Moreover, the channel rate thus considered is oftentimes a lower rate, thereby necessitating decomposition of demands of higher channel bandwidth rates into equivalent demand units of the lower rate used. However, no controls are implemented to ensure that these equivalent lower rate demands are routed together on the same network paths or to the same intended destinations. Clearly, such routing is unacceptable and is only a poor approximation of the actual routing loads in the network.
Yet another drawback in the current network planning methodologies is where the underlying modeling apparatus does not accurately reflect today's network transport technology. For example, where Fiber Optic Network rings are implemented, current solutions yield results which are not compatible with the transport technology that is widely deployed.
SUMMARY
Accordingly, the present invention advantageously provides a system for deploying network equipment with staggered time points in a network such that routing of demands with multiple channel rates or MUX levels therein is optimized. A demand input structure having a plurality of demands organized by their time points and MUX levels is provided as an input to a model generator and an optimization processor associated therewith. Starting with the earliest demand with highest MUX level to be serviced by the network, a directed graph network model is obtained via the model generator by applying appropriate transformation techniques to the network's topology. MUX modularity means is included to apply a modularity constraint with respect to the network model in order to obtain a filtered network model that can support a MUX level of a selected demand. A cost function associated with the filtered or reduced network model is constructed using a flow cost term and an equipment cost term. Appropriate constraints are imposed on the cost function for optimization. A solution set comprising network placement information and demand routing information is obtained for a MUX level within a current time point. When the next demand with a different MUX level is taken up for optimization, the filtered network model and associated cost function are recursively updated by using the solution set obtained for the previous MUX level demand. The recursive optimization process takes place for each of the demands provided in the demand input structure in accordance with their time points. Preferably, Priority
1
demands are optimized first. Thereafter, Priority
2
demands are optimized by employing a capacitated shortest path algorithm with respect to each Priority
2
demand presented in its order.
In another aspect, the present invention is directed to a network planning method for optimally deploying network equipment in a network over a period of time. The method provides a demand input structure having a plurality of demands to be serviced by the network, wherein each demand is associated with a corresponding time point and MUX level. Preferably, the demands are partitioned by their time points and MUX levels. Starting with the highest MUX level demand having the earliest time point, a double-loop recursive model building and optimization process is engaged for each of the demands. First, the network is transformed into a network model, preferably using certain transformation techniques available in the art. A MUX modularity constraint is applied with respect to the network model to obtain a filtered or reduced network model that can support a MUX level of a selected demand. An optimization problem is constructed for the filtered network model to minimize a cost function associated therewith. Thereafter, the optimization problem is solved using known integer programming techniques. Network equipment placement information and demand routing information are obtained as a solution set from the optimization process. After examining and analyzing the solution set information, the reduced network model and associated cost function are updated for optimizing the next MUX level at that time point as provided in the demand input structure. The double recursi
Venugopal Nandagopal
Watkins Kristen L.
Odland David
WorldCom, Inc.
LandOfFree
System and method for planning multiple MUX levels in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for planning multiple MUX levels in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for planning multiple MUX levels in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3171532