Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-11-24
2004-09-21
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S252000, C370S255000, C709S226000, C709S238000
Reexamination Certificate
active
06795399
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to methods and apparatus for designing packet-based networks and, more particularly, for designing IP (Internet Protocol) networks with performance guarantees.
BACKGROUND OF THE INVENTION
Traditional IP networks are built with very limited capacity planning and design optimization. These networks can only provide a best-effort service without performance guarantees. However, customer expectations can only be met if IP networks are designed to provide predictable performance. In particular, network service providers have to support bandwidth guarantees for their virtual private network (VPN) customers.
In addition, included in any network design considerations, is the fact that there are several types of network routers that may be used in a given network. For instance, a packet switch such as Lucent's PacketStar™ (from Lucent Technologies, Inc. of Murray Hill, N.J.) IP Switch supports novel traffic scheduling and buffer management capabilities, including per-flow queuing with weighted fair queuing (WFQ) and longest-queue drop (LQD), which enable minimum bandwidth guarantees for VPNs while achieving a very high level of resource utilization. It is also known that existing legacy routers, on the other hand, do not support adequate flow isolation and their first-in-first-out (FIFO) scheduling, even when combined with the random early detection (RED) buffer management policy, results in little control over the bandwidth sharing among VPNs and throughput is mostly dictated by the dynamic properties of TCP (Transmission Control Protocol), which is the dominant transport protocol used in IP networks.
Accordingly, there is a need for a network design tool that permits users, i.e., network designers, to design IP networks having the same (homogeneous) or different (heterogeneous) types of routers which provide substantial performance guarantees for a variety of applications such as, for example, VPN. Specifically, there is a need for a design tool which: automatically computes worst-case and optimistic link capacity requirements based on a designer's specifications; optimizes the network topology; and determines optimal router placement in the network.
SUMMARY OF THE INVENTION
The present invention provides methods and apparatus for designing IP networks with substantially improved performance as compared to existing IP networks such as, for example, those networks designed under best-effort criteria. Particularly, the invention includes methods and apparatus for: computing worst-case and optimistic link capacity requirements; optimizing network topology; and determining router placement within a network.
In a first aspect of the invention, methods and apparatus are provided for computing link capacity requirements of the links of the network. Particularly, upper and lower link capacity bounds are computable to provide the user of the design methodology with worst-case and optimistic results as a function of various design parameters. That is, given a network topology, specific IP demands and network delays, the design methodology of the invention permits a user to compute link capacity requirements for various network congestion scenarios, e.g., network-wide multiple bottleneck events, for each link of the given network. In this design methodology, the user may design the IP network, given a specific topology, without the need to know where specific bottlenecks are located within the specific network. Also, the link capacity computation methods and apparatus of the invention handle the case where there are one or more connections within a given demand.
In a second aspect of the invention, methods and apparatus are provided for optimizing the network topology associated with a network design. Particularly, an optimal network topology is formulated according to the invention which attempts to reduce overall network costs. In one embodiment, an iterative augmentation methodology is provided which attempts to reduce network costs by packing small -demands on the spare capacity of some existing links rather than introducing additional poorly utilized links into the network topology. In another embodiment, an iterative deloading methodology is provided which attempts to reduce network costs by removing identified links which are lightly loaded to form an optimal network topology.
In a third aspect of the invention, methods and apparatus are provided for determining the placement of WFQ/LQD routers in order to replace FIFO/RED routers in an existing network such that network cost savings are maximized. The methodology of the invention accomplishes such determination by employing a mixed integer programming model.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.
REFERENCES:
G. Anastasi, M. La Porta, and L. Lenzini. Delay analysis of a worst-case model of the MetaRing MAC protocol with local fairness. Computer Communications 20 (1997) 671-680.*
R.G. Garroppo, S. Giordano, and M. Pagano. A CAC Algorithm for Per-VC Queueing Systems Loaded by Fractal Traffic. Global Telecommunications Conference—Globecom '99: High Speed Networks. IEEE. 1999. pp. 1610-1615.*
V.P. Kumar et al., “Beyond Best Effort: Router Architectures for the Differentiated Services of Tomorrow's Internet,” IEEE Comm. Magazine, vol. 36, No. 5, pp. 152-164, May 1998.
B. Suter et al., “Design Considerations for Supporting TCP with Per-Flow Queuing,” Proc. IEEE Infocom, pp. 299-306, San Francisco, Mar. 1998.
S. Floyd et al., “On Traffic Phase Effects in Packet-Switched Gateways,” Internetworking: Research and Experience, vol. 3, No. 3, pp. 115-156, Sep. 1992.
S. Floyd, “Connections with Multiple Congested Getaways in Packet-Switched Networks, Part I: One-Way Traffic,” ACM Computer Comm. Review, vol. 21, No. 5, pp. 30-47, Oct. 1991.
Benmohamed Lotfi
Dravida Subrahmanyam
Harshavardhana Paramasiviah
Lau Wing Cheong
Mittal Ajay Kumar
Kizou Hassan
Logsdon Joe
Lucent Technologies - Inc.
LandOfFree
Link capacity computation methods and apparatus for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Link capacity computation methods and apparatus for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Link capacity computation methods and apparatus for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3266794