Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-08-30
2002-09-24
Ngo, Ricky (Department: 2731)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S455000, C370S468000
Reexamination Certificate
active
06456593
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to a system and method for communicating packetized data over a time division multiplexed communications system. In the early 1970's, telephone began using a time division multiplexed (TDM) communications system, known as D4, that used a channel bank to multiplex and communicate time division multiplexed (TDM) voice signals over a communications link, such as a T
1
link. The channel bank typically carried 24 digital voice signals between central telephone offices using only one pair of wires in each direction instead of the normal 24 pairs of wires required to communicate the 24 voice signals in analog form. This capability was achieved by digitizing and time division multiplexing the 24 analog voice signals into 24 channels or timeslots. In the TDM system, each of the channels is allocated a predetermined, equal amount of time (corresponding to a predetermined bandwidth) within each frame of the T
1
link to communicate any data. Each channel is always allocated its predetermined amount of time, even if that channel has no voice data to transmit. In addition to communicating voice signals, these systems may also communicate digital data because the D
4
system was designed to handle digital data. The systems are still widely used today to carry voice traffic between central telephone offices. Therefore, the communications hardware and the network necessary for this D
4
system are readily available.
A typical time division multiplexed (TDM) system, such as the D
4
system, has a data rate of 1.544 million bit per second (Mbps) wherein timeslots of 64 Kbps are fixedly allocated to each channel unit. The 1.544 Mbps data rate is typically known as a T
1
carrier.
Because conventional channel banks, such as the D
4
system, have allocated fixed time slots for each channel, these systems suffer from an inefficient use of bandwidth and cannot dynamically allocate that bandwidth. For example, if one or more channels do not have any voice or data signals to transmit at a particular time, the timeslot assigned to that channel unit in the T
1
frame is unused. In addition, if a particular channel has a need for more bandwidth than the allocated time slot, the TDM system does not allow that channel to request or receive any extra bandwidth. Due to these shortcomings, a number of alternative packet-based communications systems, such as asynchronous transfer mode (ATM), X.25 protocol, and frame relay, have been developed that do not assign fixed timeslots to each channel, but dynamically allocate bandwidth according to need. These packet-based communications systems are best used for digital data because digital data tends to be communicated in bursts. For example, a user sending a computer file that is 100 Kbytes long will need to send the entire 100 Kbytes as quickly as possible, but then will not require any more bandwidth until another transmission.
These packetized communications systems permit the total bandwidth of the communications link to be allocated in any manner depending on the need of the channels. For example, a single channel may use the entire bandwidth for several seconds because that channel has high priority digital data, such as an e-mail message or a computer file, that must be transmitted immediately. Most of the packetized communications systems provide some system for preventing any particular channel from over-using the communications link. These packetized systems, however, cannot use the hardware of an existing time division multiplexed channel bank, such as D
4
. Therefore, these packet-based systems require specialized hardware.
Since bandwidth allocation in TDM system is dedicated, there is no requirement for a bandwidth allocation mechanism to ensure fair delivery of bandwidth such as is required in packet-based systems. No established mechanism exists to ensure fair delivery of bandwidth for packet-based systems using TDM based hardware. Accordingly, a need exists to provide fair, low latency, delivery of packet-based bandwidth in a TDM system.
SUMMARY OF THE INVENTION
The invention provides a mechanism for fair, low latency packet-based bandwidth delivery in a TDM system using a priority scheme based on a “leaky bucket” mechanism. Bandwidth delivery to the TDM system is controlled by the priority assigned to user traffic. The priority scheme uses the “water level” in the leaky bucket priority scheme to fairly assign priority within a high or low priority band. Users are guaranteed a minimum traffic rate or Committed Information Rate (CIR) and are allowed to temporarily send a burst of traffic or a committed burst (B
c
) for short intervals at a higher rate in packet-based delivery systems. The priority assigned to user traffic is based on an amount of bandwidth allocation unused by the User over a given amount of time. This means that all users can receive the highest priority level for their traffic bandwidth allocation regardless of their preallocated bandwidth setting. It also means that all users will be throttled to the same percentage of their CIR when congestion occurs.
The priority scheme maintains two buckets to track the current bandwidth delivery rate and unused committed bandwidth. The size of the first bucket is dimensioned as twice the configured committed burst capacity (B
c
) for a given User connection. The water level in the first bucket represents the current bandwidth delivery rate for the User. If the water level is above the midpoint and is rising, the User is sending traffic below their CIR and is accumulating credit for the unused allocated bandwidth. If the water level is above the midpoint but is falling, the User is sending traffic above their CIR but has not exceeded the committed burst capacity configured. If the water level is below the bucket midpoint, the User has used up their committed burst capacity.
The second bucket represents bandwidth accumulated for the User in excess of the CIR and the committed burst bandwidth (B
c
). Thus if a User does not use their CIR nor their committed burst bandwidth over a period of time, the User is allowed to accumulate excess bandwidth credit (B
e
) up to a configured point. The water level in the second bucket represents the amount of excess bandwidth credit accumulated for the User connection overflowing from the first bucket.
Use of bandwidth by the channel unit is subtracted from the second bucket when the current priority assigned to User bandwidth delivery requests is less than or equal to the midpoint of the total priority range. Use of bandwidth by a port is subtracted from the first bucket at all other times.
If one considers the midpoint of the first bucket to be the origin, water levels above the midpoint of the first bucket are considered positive and those below are considered negative with the midpoint being equal to zero.
When the water level in the first bucket is above the zero, the priority is derived from the water level in the first bucket relative to the range from zero to the top of the bucket establishing a high priority band. The actual priority value is determined by a discrete mapping of the water level onto a range of high priority values in the high priority band.
When the water level in the first bucket is below the zero, the priority for future User bandwidth requests is derived from the water level in the second bucket relative to the range from the bottom to the top of the bucket establishing a low priority band. The actual priority value is determined by a discrete mapping of the water level onto a range of low priority values in the low priority band.
In another aspect of the invention, when the water level in the first bucket is above the origin, the priority value is alternatively derived for the high priority band by tracking the average percentage utilization of allocated bandwidth (CIR) by the User for a predetermined period of time prior to the derivation. The average percentage of utilization is then mapped onto a range of discrete priority values in the high priority band.
RE
Iverson Kent G.
Sharper Craig Alan
Sharper Sayuri Kuo
Cisco Technology Inc.
Marger Johnson & McCollom PC
Ngo Ricky
LandOfFree
Communicating packetized data over a channel using a dual... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Communicating packetized data over a channel using a dual..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communicating packetized data over a channel using a dual... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2819093