Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-10-09
2002-04-30
Vincent, David R. (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235100, C370S395210
Reexamination Certificate
active
06381214
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
This invention is in the field of data communications, and is more specifically directed to traffic management of packet-based data communications.
In the field of digital communications, whether applied to voice, video, or data communication, various techniques have been developed for routing messages among nodes, or processors, that are connected in a network. One such approach is referred to as packet-based data communications, in which certain network nodes operate as concentrators to receive portions of messages, referred to as packets, from the sending units. These packets may be stored at the concentrator, and are then routed to a destination concentrator to which the receiving unit indicated by the packet address is coupled. The size of the packet refers to the maximum upper limit of information that can be communicated between concentrators (i.e., between the store and forward nodes), and is typically a portion of a message or file. Each packet includes header information relating to the source network address and destination network address, which permits proper routing of the message packet. Packet switching with short length packets ensures that routing paths are not unduly dominated by long individual messages, and thus reduces transmission delay in the store-and-forward nodes. Packet-based data communications technology has enabled communications to be carried out at high data rates, up to and exceeding hundreds of megabits per second.
A well-known example of a fast packet switching protocol, which combines the efficiency of packet switching with the predictability of circuit switching, is Asynchronous Transfer Mode (generally referred to as “ATM”), in which packet lengths and organization are fixed, regardless of message length or data type (i.e., voice, data, or video). The fixed packets according to the ATM protocol are referred to as “cells”, and each ATM cell is composed of fifty-three bytes, five of which are dedicated to the header and the remaining forty-eight of which serve as the payload. According to this protocol, larger packets are made up of a number of fixed-length ATM cells. The fixed-size cell format enables ATM cell switching to be implemented in hardware, as opposed to software, resulting in transmission speeds in the gigabits-per-second range. In addition, the switching of cells rather than packets permits scalable user access to the network, from a few Mbps to several Gbps, as appropriate to the application. The asynchronous nature of the transmission permits ATM cells to be used in transmitting delay-tolerant data traffic intermixed with time-sensitive traffic like voice and video over the same backbone facility. To more efficiently utilize the bandwidth for these various applications, traffic management techniques are now employed which give priority to time-sensitive traffic relative to delay-tolerant traffic.
Closed loop traffic management involves the use of feedback signals between two network nodes to govern the data rates of channels, with a goal of improving the efficiency of bandwidth utilization. This efficiency improvement is particularly necessary when communication of compressed voice and video information is involved, because of the variability in bit rate caused by compression. In this case, the feedback signals enable the network to communicate either the availability of bandwidth or the presence of congestion.
Current traffic management schemes utilize various transmission categories to assign bandwidth in ATM communications. One high priority category is Constant Bit Rate (CBR), in which the transmission is carried out at a constant rate. Two categories of Variable Bit Rate (VBR) transmission are also provided, one for real-time information and another for non-real-time information. A low priority category is Unspecified Bit Rate (UBR), in which data are transmitted by the source with no guarantee of transmission speed. In the recently-developed Available Bit Rate (ABR) service class, feedback from the network nodes, via Resource Management (RM) cells or by way of explicit congestion indications in data cells, is used by the source network node to dynamically control channel transmission rate in response to current network conditions, and within certain transmission parameters that are specified upon opening of the transmission channel (i.e., in the traffic “contract”).
For the ABR class of service, the source and destination nodes agree, in the traffic contract, upon the Peak Cell Rate (PCR) and Minimum Cell Rate (MCR), thus setting the upper and lower bounds of transmission for an ABR communication. Once these bounds are established, a flow control algorithm is executed, typically at the source network node and in ATM switches, to define the desired transmission rate for each channel. As is known in the art, thousands of connections may be simultaneously open between a given pair of network nodes. As such, traffic management can be a relatively complex operation, especially in controlling ABR category communications.
At the source network node, and also at switches within the ATM network (e.g., at the edges of network domains), Segmentation and Reassembly (SAR) devices or shaper devices are used to arrange and transmit ATM cells according to the traffic contract established at the time of subscription. An often-used traffic shaping device is referred to in the art as a “leaky bucket”, as this device includes buffers that can rapidly fill up with cell data during bursts, but steadily “leak” or transmit data over the network. These leaky bucket functions effectively verify conformance of each cell with respect to its traffic “contract”, ensuring that one or more channels do not dominate the bandwidth, to the exclusion of others.
The algorithm according to which such conformance is defined is referred to, for example in
Traffic Management Specification, Version
4.0 (The ATM Forum, April 1996), Section 4.4.2, as the Generic Cell Rate Algorithm, or GCRA. The GCRA is required, by this specification, to be performed at each public User-to-Network Interface (UNI) as part of Usage Parameter Control (UPC) operations for Peak Cell Rate (PCR) of the Cell Loss Priority (CLP=
0
+
1
) flow; similar processing is optional in Network Parameter Control (NPC) at Network-to-Node Interfaces (NNIs), for example in the case where a downstream network domain requires traffic shaping to be performed by domains transmitting traffic thereto. UPC (and, analogously, NPC) “polices” the traffic on each ATM connection to enforce the compliance of every ATM connection to its traffic contract.
Fundamentally, the leaky bucket device is a container of “tokens” that are periodically added to the bucket as a measure of elapsed time, where one token is removed from the bucket for every cell that is found to be compliant. An arriving cell is found to be compliant if the token bucket is not empty upon its arrival. When used as a “traffic shaper”, the GCRA operates to transmit traffic at a relatively steady rate, even if the cells are arriving in a “bursty” fashion. It is with respect to this shaper function that the GCRA is referred to as a “leaky bucket” function, as the arriving cells are effectively stored and sent along the network at a fixed rate; if too many cells arrive over a period of time, the cell “bucket” overflows (i.e., the token bucket is empty), in which case some cells are deemed non-conforming (as arriving at an excessively high frequency) and may be discarded.
One bit in the header of each ATM cell is the CLP (Cell Loss Priority) bit. The CLP bit permits two priorities of traffic, where lower priority, CLP(
1
), cells may be discarded as necessary to ensure adequate network performance for higher priority CLP(
0
), cells. CLP(
0
+
1
) traffic refers to the aggregate traffic, including both the lower and higher priority flows. With regard to the policing function, such as using the GCRA, if a CLP(
0
) cell is found to
Brady III W. James
Moore J. Dennis
Phunkulh Bob A.
Vincent David R.
LandOfFree
Memory-efficient leaky bucket policer for traffic management... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory-efficient leaky bucket policer for traffic management..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory-efficient leaky bucket policer for traffic management... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2851014