Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-01-02
2001-02-20
Marcelo, Melvin (Department: 2739)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S412000
Reexamination Certificate
active
06192032
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to video image processing and more particularly to the transmission of video images over networks.
BACKGROUND OF THE INVENTION
The bandwidth requirements of uncompressed digital video streams may exceed the available bandwidth of communication networks such as local area networks (LANs). For example, uncompressed video streams may require between 100 and 240 million bits per second (MBPS) for delivery without distortions or delays at the receiving end. As a result, various methods of compressing digital video streams have been developed to reduce bandwidth requirements to levels acceptable to most networks.
Digital video compression methods typically utilize a collection of algorithms and techniques for replacing the original pixel-related information with more compact mathematical descriptions. Decompression is the reverse process of decoding mathematical descriptions back to pixels for display. Video compression and decompression may be performed using a CODEC (Coder/Decoder or Compressor/Decompressor).
Digital video streams may be transmitted over networks at either a variable bit rate (VBR traffic) or a constant bit rate (CBR traffic). Digital video systems may use buffers to smooth out rate variations in compressed data streams. For example, U.S. Pat. No. 5,485,211 to Kuzma relates to introducing feedback between a video CODEC and a communications channel such that characteristics of the channel are used to drive multiple output buffers. The communications channel can select from the buffer that best matches the communications channel's current conditions.
Buffer control for CBR traffic is reasonably well understood. However, VBR has only recently become widely available and buffer control methods for VBR traffic are still developing. U.S. Pat. No. 5,159,447 to Haskell et al. relates to controlling the number of bits employed to encode each video frame and the transmission bit-rate of the VBR channel as experienced by the encoder.
The difficulty in transporting VBR traffic over communications networks is that VBR traffic is bursty (high peak-to-mean ratios), highly correlated and has strict delay bounds. VBR traffic sources can strain a network's resources and potentially degrade performance, causing excessive packet delays and loss. To manage this problem, traffic shaping mechanisms for shaping traffic before it enters the network have been proposed. Examples of such mechanisms include Traffic “Smoothers” and “Token Buckets.”
A token bucket is a device placed at the entry point of a network. Tokens are generated at a fixed rate, &sgr;, and flow into a bucket of a fixed size, &bgr;. Tokens arriving when the bucket is full are discarded. Each token represents a unit of data. Packets entering a network must acquire tokens equal to its data unit size (e.g. one token for each byte of data in the packet). If there are insufficient tokens, the packet is downgraded in priority, and sent into the network. The number of tokens in the bucket cannot be less than zero and no packets are dropped at the source.
Transport protocols which police incoming traffic deliver low priority packets on a best-effort basis. High priority packets are sent with guarantees on both delivery and delay. Low priority packets, however, can be dropped by the network if the network becomes congested. For video traffic, this can cause severe degradations in quality due to late or missing packets at the receiver.
Traffic smoothers have been proposed to reduce the burstiness of VBR video. A smoother chooses a transmission rate to minimize bit-rate variation, while conforming to a predetermined delay bound. A smoother guarantees that all frames from a video source will meet its transmission delay bound. A smoother may choose a rate which might cause packets to be downgraded in priority. As a result, a higher percentage of low priority packets may enter the network.
SUMMARY OF THE INVENTION
In view of the above discussion, it is an object of the present invention to allow a traffic smoother and token bucket to work together to reduce the number of low priority packets entering a network.
It is another object of the present invention to transmit VBR video data over congested computer networks without performance degradation and without causing excessive frame packet delays and loss.
These and other objects of the present invention are provided by methods, systems and computer program products for facilitating the transmission of video data over computer networks. A video frame transmitter for transmitting packets of each video frame into a network includes a traffic smoother for adjusting video frame packet transmission rates; a traffic policing device (e.g., a token bucket) for controlling video frame packet entry into the network; and a transmission rate attenuator for adjusting video frame packet transmission rates. The traffic smoother adjusts transmission rates from a video frame source to meet a transmission delay bound of the frame source. Video frame packet transmission rates are attenuated to conform with the state of the token bucket in order to maintain a high percentage of high priority video frame packets entering the network. The rate attenuator allows the traffic smoother and token bucket to work together, thereby reducing the number of low priority packets entering a network.
According to an aspect of the present invention, video frame packets containing tokens enter a network via the video frame transmitter and a rate attenuator predicts the future state of the token bucket. Utilizing the predicted state of the token bucket, the rate attenuator determines whether the token bucket has a sufficient number of tokens for each video packet within a video frame. In response to determining that a video frame packet does not have a sufficient number of tokens, the video frame packet transmission rate is reduced. Predictions of the future state of the token bucket may be based on: the current number of tokens in the token bucket; the size of the video frame packets currently in the traffic smoother buffer; the size of the current video frame; and the transmission rate of each frame.
A video frame which has just arrived may be referred to as the “current frame” and is the frame the transmission rate is calculated for. The state of the token bucket is predicted once to generate the number of tokens which will be in the token bucket when the current frame begins transmission. An iteration process starts with this number of tokens and then uses the current frame and transmission rate to calculate a token bucket state to see if any of these packets will be downgraded.
When a video frame packet transmission rate is reduced, the reduced rate is compared with a lower bound to determine whether the reduced video frame packet transmission rate is below this lower bound. The smoother determines the slowest transmission rate to transmit the current frame which will satisfy delay bound (D). This is the lower bound on the transmission rate. In response to determining that the reduced video frame packet transmission rate is below the lower bound, the video frame packet transmission rate is set to the lower bound. Video frame packet transmission rates are stored in a rate queue accessible by a scheduler.
According to another aspect of the present invention, the need for additional predictions of a future token bucket state can be reduced using an identified “pivot-point.” A pivot-point is a point in time where token overflow within a token bucket occurs. Transmission rate reductions will not change the number of tokens in the token bucket at the pivot-point. By recalculating the number of tokens needed starting at the pivot-point, there is no need to recalculate starting from the first packet in the frame. When the transmission rate of the current frame is reduced, more tokens will be generated. As a result it is possible for the token bucket to overflow at this rate. If this happens, there will not be enough tokens (i.e., the process is “short” to
International Business Machines - Corporation
Marcelo Melvin
McConnell Daniel E.
Nguyen Phuongehau Ba
LandOfFree
Rate attenuation systems, methods and computer program... 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 attenuation systems, methods and computer program..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rate attenuation systems, methods and computer program... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2597526