Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-05-26
2002-04-09
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S389000, C370S230000, C370S235000
Reexamination Certificate
active
06370116
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to fast packet switching for communications networks and more particularly to an improved rate enforcement strategy for packet rate control based on the “leaky bucket” algorithm.
BACKGROUND
Fast packet switching employing frame or cell relay (Frame Relay or Asynchronous Transfer Mode—ATM) technologies is used extensively in broadband communications networks. These switching techniques route packets of data through a mesh-type switching network in accordance with category and quality of service parameters agreed upon at call setup. Frame Relay (FR) is designed to handle bursty traffic patterns and Packet Transfer Exchange (PTX) systems such as the Newbridge 36120 provide dynamic bandwidth allocation on demand through its Rate Enforcement algorithms. FR products, generally, implement the ANSI and ITU-T standards for data traffic rate enforcement. By setting Committed Information Rate (CIR), committed burst (Bc) and excess burst (Be) values per Virtual Circuit (VC), the incoming traffic is regulated. CIR gives a guaranteed data rate whereas EIR (as calculated from CIR, Bc and Be) gives an excess burst information rate (over CIR) which will be allocated to a VC if there is enough bandwidth available (i.e. no congestion). The term Virtual Circuit (VC) as used herein is intended to include Permanent Virtual Circuits (PVC), Switched Virtual Circuits (SVC) and Soft Permanent Virtual Circuits (SPVC)
At VC establishment, the network operator agrees to provide Frame Relay service at CIR and EIR values. While CIR is a configurable parameter, other parameters (Bc and Be) have to be configured to meet a requested EIR value. Then, the rate enforcement algorithm is used to ensure that these limits are complied with by the user. This also ensures that Frame Relay service is provided fairly to all users.
The rate enforcement algorithm has come to be known as the “leaky bucket” algorithm. This name is applied to the algorithm in as much as its implementation can be compared to a bucket having a hole in the bottom. If a substance is poured into the top of the bucket it will drain from the hole in the bottom at a constant rate. The capacity of the bucket and the size of the drain hole dictates how much of the substance can be poured into the bucket before it overflows. In frame relay terms the substance may be equated to packets of information, the drain hole is the negotiated or committed information rate and the overflow relates to marked or discarded frames or packets.
At connection setup the committed information rate (CIR) in bits/sec, which is the rate the network commits to meet, is configured. The excess information rate (EIR) in bits/sec is the rate in excess of CIR that the network agrees to transfer information under normal conditions. All information classified as EIR is subject to discard and will be dropped or discarded in the event of network congestion. Thus, EIR frames are marked as being discard (or drop) eligible (DE).
In view of the two classes of information, i.e. CIR and EIR, the leaky bucket algorithm is frequently extended to a dual bucket analogy. In this analogy Bc and Be are considered as two buckets that are used to monitor that the traffic rate is within CIR and EIR respectively. According to one implementation of the dual leaky bucket algorithm if DE bits are not set in the incoming frames, Bc starts to fill up first and if there is no space left in Bc, the excess goes into Be and DE bits are set for frames flowing into Be. When Be fills too, the excess is discarded. The buckets are leaking at the rate of CIR and EIR respectively. That is, new space is opening in the buckets at allowed traffic rates so that new frames can make it into the buckets. The replenishing of the buckets are performed at the receipt of every frame. That is, before calculating to determine whether the new frame will fit in any of the buckets, the buckets are updated. The time difference between this frame and the previous update is calculated with a precision of a set time interval, 5 ms for example, and the allowed traffic amount within this interval is added to the buckets.
Thereafter the frame is tried to be placed in the buckets. This is actually the same as updating the bucket levels every 5 ms since bucket levels are not checked at any other time than the one at frame arrival. The standard recommends keeping this replenishing interval (5 ms in this case) as small as possible. This is to provide a precise calculation. In the present case, if two or more frames arrive in less than 5 ms, then it is necessary to make a decision without updating the bucket levels.
If DE bits are set in the incoming frames, they go directly into the Be bucket and if Be fills up, then excess frames are discarded.
Bucket size determines which sample of the traffic the algorithm will monitor. The bucket size can also be thought of as the length of a window on the incoming data sequence.
If the traffic pattern is varying rapidly, i.e. bursty traffic, then a larger window is needed to make a judgment on the data traffic values as an average value. Otherwise, i.e. with a small bucket size (or a small window), the switch will not be able to capture the correct data pattern. With a small window, the algorithm might observe the peak of a burst and discard too many frames since it would then assume that the high traffic rate is persistent but, if there is a large window it will observe that the traffic is varying and it will consider an average value in which case the peaks will be compensated for by the low traffic regions. The standard also indicates that measurement interval (T=Bc/CIR) should be proportional to the burstiness of the traffic which implies that the Bc bucket size should be proportional. CIR itself is not a parameter to change since it is the value being monitored. Thus a larger window will increase tolerance to variations in the traffic rate.
On the other hand, a large bucket size with bursty traffic might render the Rate Enforcement algorithm ineffective if the traffic rate falls too far below the CIR or EIR values or if there are completely idle periods after bursts of data at very high data rates such as the Access Rate (AR) and this repeats itself. The algorithm might end up letting through data at rates of multiples of CIR or EIR. This is due to the fact that by keeping the bucket size large an uncertainty is introduced to the process: rate enforcement takes effect only when the bucket is nearly full. That's when the frames are not let through or marked as DE. Until the bucket fills up, the algorithm has no way of knowing at what rate the traffic is flowing into the bucket. It is only known that it can come at most at the access rate (AR). In the extreme case, the traffic might come at the AR until the bucket fills and then stops until the bucket empties (leakage) and starts again. In this case frames are not discarded or marked DE, which doesn't necessarily mean that traffic rate is within CIR and/or EIR.
Technologies in this area have relied on the Committed Information Rate algorithms defined in ANSI specifications. These algorithms essentially state that the user devices in a network can be policed to CIR, but are allowed to burst up to an excess burst. Excess burst traffic is marked as excess in frame relay by setting the discard eligible (DE) bit, (DE=1).
Most standards based CIR algorithms discard frames too frequently because if any part of an incoming frame causes the bucket to empty, the frame is tagged or discarded. This can cause a frame to be discarded even if it is over its committed burst (Bc) or its excessive burst (Be) by just one data bit. The end result is that frame relay customers may not get subscribed CIR because of the size of frames they are sending.
Other alternatives, such as a shared bucket strategy (i.e. shared Bc and Be buckets) discard the correct number of frames, but tag too often. Every frame that is not discarded because of bucket sharing is tagged. This results in frames being tagged at rates
Giroux Natalie
Liu Bo
Paquette Andre
Rezaki Ali
(Marks & Clerk)
Alcatel Canada Inc.
Chin Wellington
Duong Frank
LandOfFree
Tolerant CIR monitoring and policing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tolerant CIR monitoring and policing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tolerant CIR monitoring and policing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2833770