Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-12-22
2004-09-28
Nguyen, Steven H. D (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C709S241000
Reexamination Certificate
active
06798747
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 discovering Time Slot Assignment (TSA)-compatible routes that optimize demand transport in a network with optimal placement of network equipment. 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. After recursively optimizing the network for each MUX level—time point combination, demand routes are analyzed to verify if they are TSA-compatible. Where demands with TSA-blocked routes are found, blocking spans are identified and a cost associated therewith is increased during an iterative re-routing process with respect to each of such blocked demands. Accordingly, alternate spans are discovered that may allow TSA transport for the initially blocked demands. The iterative re-routing process is effectuated by using a capacitated shortest path algorithm, and may be bounded by a limit on the number of iterations or a timeout period.
In a further aspect, the present invention is directed to a method for optimally routing information using a TSA transport mechanism in a network comprising one or more spans. The method provides a demand input structure having a plurality of demands to be serviced by the network, wherein each demand is preferably associated with a corresponding time point and a MUX level. Routes for transporting the demands in the network are determined by optimizing with respect to the MUX levels at each time point. The demand routes are then analyzed to determine if the routes conform to the TSA transport mechanism. Demands whose routes are blocked with respect to the TSA transport mechanism are identified. Thereafter, spans in the routes that block the TSA transport mechanism with respect to the blocked demands are identified. The blocked demands then are iteratively re-routed using a capacitated shortest path algorithm on alternate spans, wherein a cost associated with blocked spans increases foreach re-routing iteration. The iterative re-routing process is continued until a TSA-compliant route is identified or a limit is reached for each of the blocked demands.
REFERENCES:
patent: 4991204 (1991-02-01), Yamamoto et al.
patent: 5136581 (1992-08-01), Muehrcke
patent: 5442623 (1995-08-01), Wu
patent: 5452294 (1995-09-01), Natarajan
patent: 5546542 (1996-08-01), Cosares et al.
patent: 5649108 (1997-07-01), Spiegel et al.
patent: 5657142 (1997-08-01), Fahim
patent: 5729692 (1998-03-01), Qiu et al.
patent: 5787271 (1998-07-01), Box et al.
patent: 5835482 (1998-11-01), Allen
patent: 6304548 (2001-10-01), Shaffer et al.
Venugopal Nandagopal
Watkins Kristen L.
Nguyen Phuongchau Ba
Nguyen Steven H. D
WorldCom, Inc.
LandOfFree
System and method for time slot assignment in a fiber optic... 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 time slot assignment in a fiber optic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for time slot assignment in a fiber optic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3269980