Rate guarantees through buffer management

Details Rate guarantees through buffer management Rate guarantees through buffer management

1998-05-12

2002-04-23

Jung, Min (Department: 2663)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S462000

Reexamination Certificate

active

06377546

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to packet data transmission systems and, more particularly, to packet data transmission systems which provide a quality of service to individual or a group of flows in a router.
2. Description of the Related Art
Many applications inherently require the network to provide them with a steady stream of packets in order to work correctly. Some typical examples are those involving audio or video playback like video conferencing or video-on-demand applications. Most of these applications perform very poorly if the network does not provide them with a certain minimum amount of bandwidth on an end-to-end basis. Furthermore, several video and audio coders can vary their rate of coding based on the bandwidth that is made available to them. Thus, an a-priori knowledge of the bandwidth that the network can provide is useful for these applications to select the appropriate parameters for the coding process. If the network can provide minimum rate guarantee to a flow, then this rate can be used by the sender to appropriately deliver packets to the network so that the receiver gets a continuous stream of packets. The net result is a smooth and timely playback operation at the receiver.
There are many other applications where the provision of an end-to-end rate guarantee might be most useful. In a Virtual Private Network these rate guarantees may be used to dimension the size and number of virtual links that need to be setup. Other situations might use the rate guarantee as a means to obtaining a certain level of service from the network. For example in a World Wide Web environment a higher rate guarantee directly translates into a shorter time for downloading web pages.
Provision of service guarantees, especially rate guarantees, is becoming increasingly important in packet networks, and in particular the Internet. This is caused by both the heterogeneity of requirements from new applications, and the growing commercialization of the Internet. Support for such service guarantees requires that the network control the amount of resources that each flow or set of flows is allowed to consume. The network resources whose consumption is to be controlled, consist primarily of buffers and link bandwidth, with buffer management and scheduling being the associated mechanisms.
FIG.1
is a prior art illustration of a scenario where a flow
50
(or set of flows) between sender
20
and receiver
21
is to be guaranteed a given level of service as it crosses network
1
. As they cross network
1
, packets originating from sender
20
traverse links
30
to
34
and network elements, e.g., switches or routers,
11
to
14
. Resources that need to be controlled in this example are the bandwidth on links
30
to
34
and the buffer space in network elements
11
to
14
. This control is effected by controllers
40
to
43
, where each controller is responsible for ensuring that packets from flow
50
have access to sufficient buffers and bandwidth at the corresponding network element and link, respectively. For example, controller
41
is responsible for guaranteeing to flow
50
buffers in network element
13
and bandwidth on link
33
, despite the presence of interfering traffic from flows
64
and
65
which are contending for the same resources.
There is a cost associated with implementing such resource controllers. They are required to perform a number of processing steps for each packet received, in order to determine the appropriate actions to take on the packet and enforce the desired service guarantees. The cost is a function of the number and complexity of these per packet processing steps, which usually grow with the accuracy and efficiency of the service guarantees to be provided. As a result, it is desirable to identify mechanisms, that can be used to implement resource controllers at the minimum possible cost for a given level of performance in providing service guarantees. In particular, this means devising solutions that can scale with increasing link speeds.
In that context, it is important to understand the generic cost components of resource control. As mentioned earlier, there are two types of resource control mechanisms, buffer management and scheduling, which are responsible for controlling access to buffer and link bandwidth, respectively. Of the two, it turns out that packet scheduling costs are typically greater than those associated with buffer management.
This is because buffer management only involves the decision at the time of a packet arrival of whether to admit or drop it and this decision can be made based on a fixed amount of “state” information. Specifically, the information used in making buffer management decision typically consists of global state information, such as the total buffer content, and flow specific state information, such as the current number of packets for the flow. There are many examples of existing buffer management mechanisms that correspond to this model. Some of the more popular ones include threshold based mechanisms [I. Cidon, R. Guérin, and A. Khamisy. Protective buffer management policies. IEEE/ACM Trans. Networking, 2(3):240-246, June 199], schemes such as Early Packet Discard (EPD) [A. Romanow and S. Floyd. Dynamics of TCP traffic over ATM networks. IEEE J. Sel. Areas Commun., (13(4):633-641. May 1995, J. Turner. Maintaining high throughput during overload in ATM switches. In Proceedings of INFOCOM, pages 287-295, San Francisco, Calif., April 1996], Random Early Discard (RED) [S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Trans. Networking, 1(4):397-413, August 1993], and Fair RED (FRED) [D. Lin and R. Morris. Dynamics of random early detection. In Proceedings of SIGCOMM, pages 127-137, Sophia Antipolis, France, September 1997].
Scheduling decisions, on the other hand, require both flow specific state information, such as when the last packet of a flow was transmitted and the rate or delay guarantee for the flow, and operations involving all the flows currently contending for access to the link. The latter is typically in the form of insertion and deletion operations in a sorted list of packets waiting for transmission. For example in the case of algorithms such as Weighted Fair Queuing (WFQ) [A. K. J. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. PhD thesis, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Mass. 02139, February 1992. No. LIDS-TH-2089] or rate controlled Earliest Deadline First (EDF) [L. Georgiadis, R. Guérin, 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], the sorted list consists of maximum departure times for packets from each active flow, where the maximum departure time for a flow is computed so as to ensure specific rate and/or delay guarantees.
FIG. 2
is a prior art illustration of the operation of buffer management and scheduling mechanisms as performed by the prior art at a typical network node to control the amount of resources that can be consumed by different flows. Packets from different flows arrive on input link
35
where they are first processed by the buffer manager unit
70
. This unit makes decision of whether to accept and store an incoming packet into buffer
72
, based on the total number of free buffers (white space in the figure) and the current buffer occupancy of the flow to which the packet corresponds. Specifically, the figure shows packets
51
,
54
, and
56
from flow f
1
, packets
52
from flow f
4
, and packets
55
from flow f
3
, arriving to the buffer on the input link. The buffer manager unit
70
about to process incoming packet
56
from flow f
1
to determine if it should be accepted in the buffer. Based on the buffer state for flow f
1
shown in
FIG. 2
, adding packet
56
would take

Affiliated with

Also associated with

Rating

Rate guarantees through buffer 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 Rate guarantees through buffer management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rate guarantees through buffer management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2828885