Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Computer or peripheral device
Reexamination Certificate
1999-12-22
2004-07-13
Jones, Hugh (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Computer or peripheral device
C703S002000, C703S013000, C709S224000, C709S223000
Reexamination Certificate
active
06763326
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 demand routing therein is optimized. A demand input structure having a plurality of demands organized by their time points is provided as an input to a model generator and an optimization processor associated therewith. Starting with the earliest demand set to be serviced by the network, a directed graph network model is obtained by applying appropriate transformation techniques to the network's topology. A cost function associated with the 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 current time point. When the next demand set is taken up for optimization, the network model and associated cost function are recursively updated by using the solution set obtained for the demand set previously. 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. Preferably, the demands are sorted by their time points. Starting with a demand set having the earliest time point, a recursive model building and optimization process is engaged for each of the time points. First, the network is transformed into a network model, preferably using certain transformation techniques available in the art. An optimization problem is constructed for the 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 network model and associated cost function are updated for optimizing the next demand set in the demand input structure. These steps are repeated for all Priority
1
demands which are optimized first. Thereafter, Priority
2
demands, if any, are optimized by using a capacitated shortest path algorithm. Accordingly, a schedule for successive deployment of the network equipment in the network may be planned based on the network equipment placement information obtained for each of the time points.
REFERENCES:
patent: 5204955 (1993-04-01), Kagei et al.
patent: 5295244 (1994-03-01), Dev et al.
patent: 5515367 (1996-05-01), Cox et al.
patent: 5530575 (1996-06-01), Acampora et al.
patent: 5583792 (1996-12-01), Li et al.
patent: 5657142 (1997-08-01), Fahim
patent: 5729692 (1998-03
Venugopal Nandagopal
Watkins Kristen L.
Jones Hugh
WorldCom, Inc.
LandOfFree
System and method for staggering time points for deployment... 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 staggering time points for deployment..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for staggering time points for deployment... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3242569