Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-08-27
2003-05-06
Nguyen, Steven (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S395400
Reexamination Certificate
active
06560195
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to a scheduling apparatus and method for scheduling when an entity is to receive service from a server unless the entity will not be in conformance with a predetermined criteria. More specifically, the present invention is related to a scheduling apparatus and method for scheduling when an entity is to receive service from a server unless a session of the entity will not be in conformance with a predetermined criteria based on leaky bucket accounting, in which case the session is stored in a revival queue.
BACKGROUND OF THE INVENTION
Emerging broadband networks introduce new challenges in designing high-speed shaper architectures that can scale to a large number of connections with diverse traffic parameters. Many new networking applications, such as large scale web and video servers, require traffic shaping for hundreds or even thousands of connections with different burst and bandwidth descriptors. ATM switches can also amortize implementation costs across multiple end systems by providing traffic shaping at the network edge. In addition to shaping at the network end points, available bit-rate connections require traffic enforcement in the interior of the network at each virtual source node, where a connection's bandwidth allocation may change over time in response to feedback from the network. Variable-bit rate and constant-bit-rate connections may also be reshaped in the interior of the network to limit delay variation and buffer requirements at the downstream switches. Reinforcing the traffic parameters is particularly important when connection traverse switches with different performance characteristics or service providers.
Most existing traffic shapers employ some version of leaky bucket control to buffer non-conforming cells and schedule for later transmission. Conceptually, a leaky bucket control generates tokens at rate &rgr;, where the token holds at most &sgr; credits; an arriving cell must claim a token before receiving service. Given the status of the token bucket for each connection, the shaper can determine whether an arriving cell is conforming or not.
Traditionally, leaky bucket based traffic policing algorithms have been used at the ingress of a network or network component to ensure that incoming traffic is within negotiated contract. Similarly, leaky bucket based shaping algorithms have been used at the source or edge of networks to ensure injected traffic is conforming. It has been demonstrated [L. Georgiadis, R. Geurin, V. Peris, and K. N. Sivarajan. Efficient network qos provisioning based on per node traffic shaping.
IEEE/ACM Trans. Networking,
4(4) :482-501 August 1996, incorporated by reference herein] that conforming traffic entering at the ingress of a network element such as a router or switch, can become non-conforming due to burstiness introduced by buffering and multiplexing with other sessions. Such traffic may be treated as non-conforming at the next router or switch and dropped/tagged, leading to unexpected end-to-end behavior.
Rate based schedulers [J. C. R. Bennett and H. Zhang. Wf
2
q: Worst-case fair weighted weighted fair queueing. In
INFOCOM'
96, pages 120-128, March 1996; S. Golestani. A self-clocked fair queueing scheme for broadband applications. In
INFOCOM'
94, pages 636-646, June 1994, incorporated by reference herein] ensure sessions obtain their minimum guaranteed rate. Bandwidth left-over from meeting such guarantees is divided based on some predefined fairness policy among sessions. Thus, although scheduling ensures a minimum to meet guarantee of a session, it does not limit the maximum bandwidth a session may receive while sharing the left-over bandwidth. Thus, its possible for a session to be served out in bursts, violating maximum burst size contract at next network element.
FIG. 1
depicts a block-level diagram of an outgoing link, incoming links feeding to the outgoing link, buffer to store the incoming cells, and a scheduler to serve out cells from the buffer to the outgoing link.
Further, it has been demonstrated that buffering and scheduling decisions within a networking equipment can lead to traffic becoming more bursty at egress than it was at ingress. The egress traffic on any connection is required to be in compliance with its traffic contract. Non-conforming egress traffic entering another switch or network may be policed leading to it being tagged or dropped. The present invention includes a leaky-bucket based shaping to ensure conforming traffic at egress. Such out-bound shaping is important to keep within traffic contract specifications like PR, SCR, and ACR.
SUMMARY OF THE INVENTION
The present invention pertains to a scheduling apparatus. The apparatus comprises a server for providing service to entities. The apparatus comprises a mechanism for determining whether an entity that is to receive service at a future time from the server will be in conformance with a predetermined criteria at the future time when the entity is to receive service from the server. The apparatus comprises a scheduler mechanism for scheduling when entities are to receive service from the server unless the determining mechanism determines the entity is not in conformance.
The present invention pertains to a method for scheduling entities in an ATM network. The method comprises the steps of receiving a session of an entity in a memory of an ATM switch connected to the ATM network. Then there is the step of scheduling the session for service by a server of the ATM switch. Next there is the step of determining with a determining mechanism whether the session will be conforming in terms of compliance to traffic contract of the ATM network in the future. Next there is the step of deleting the session if the session will not be conforming in the future.
REFERENCES:
patent: 5533020 (1996-07-01), Byrn et al.
patent: 5831971 (1998-11-01), Bonomi et al.
patent: 5982749 (1999-11-01), Daniel et al.
patent: 6011775 (2000-01-01), Bonomi et al.
patent: 6247061 (2001-06-01), Douceur et al.
patent: 6266327 (2001-07-01), Hernandez-Valencia
S. Jamaloddin Golestani, “A Self-Clocked Fair Queueing Scheme for Broadbend Applications,” Infocom 94, p. 636-646, Jun. 1994.
Leonidas Georgiadis, Roch Guerin, Vinod Peris, Kumar N. Sivarajan, “Efficient Network QoS Provisioning Based on per Node Traffic Shaping,” IEEE/ACM Transactions on Networking, vol. 4 (No. 4), p. 482-501, Aug. 1996.
Jennifer Rexford, Flavio Bonomi, Albert Greenberg, Albert Wong, “A Scalable Architecture for Fair Leaky-Bucket Shaping,” Infocom 97, p. 1054-1062, Apr. 1997.
Abhay Kumar J. Parekh, “A Generalized Processor Sharing Approach to Flow Control In Integrated Services Networks,” PhD Thesis, Massachusetts Institute of Technology, 1992.
Adams Jay P.
Basak Debashis
Marconi Communications Inc.
Nguyen Steven
Schwartz Ansel M.
LandOfFree
Method and apparatus for leaky bucket based out-bound... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for leaky bucket based out-bound..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for leaky bucket based out-bound... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3037603