Note: Descriptions are shown in the official language in which they were submitted.
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
1
SYSTEM, DEVICE, AND METHOD FOR SCHEDULING
VARIABLE BIT RATE TRAF=FIC IN A COMMUNICATION
NETWORK
Related Applications
This application claims priority from United States provisional
patent application number 60/055,658 entitled System, Device, And
Method For Scheduling In A Communication Network filed on August 14,
1997, incorporated herein by reference in its entirety.
Background
1. Field of the Invention
- The invention relates generally to communication systems, and
more particularly to scheduling transmission opportunities in a
communication network.
2. Discussion of Related Art
In today's information age) there is an increasing need for high-
speed communications that provide guaranteed quality of service (QoS)
for an ever-increasing number of communications consumers. To that
end, communications networks and technologies are evolving to meet
current and future demands. Specifically, new networks are being
deployed which reach a larger number of end users, and protocols are
being developed to utilize the added bandwidth of these networks
efficiently.
One technology that has been widely employed and will remain
important in the foreseeable future is the shared-medium network. A
shared medium network is one in which a single communications
channel (the shared channel) is shared by a number of end users such
that uncoordinated transmissions from different end users may intertere
with one another: Since communications networks typically have a
limited number of communications channels) the shared medium network
CA 02268794 1999-04-14
WO 99/09690 PCTNS98/14894
2
allows many end users to gain access to the network over a single
communications channel, thereby allowing the remaining
communications channels to be used for other purposes. However, the
shared medium network is only feasible when each end user only
transmits data intermittently) allowing other end users to transmit during
periods of silence.
One problem in a shared medium network involves scheduling
end user transmissions to provide each end user with guaranteed
bandwidth and QoS. In a cell-based network such as an Asynchronous
Transfer Mode (ATM) network, one technique for scheduling end user
transmissions is to provide each end user with data transmission
opportunities at its peak cell rate) which is the maximum rate at which the
end user can generate cells. Such a scheduling technique works well for
continuous bit rate traffic which always generates cells at the peak cell
rate. However, such a scheduling technique may be inefficient for
variable bit rate traffic, which does not always generate cells at the peak
cell rate. Furthermore, such a scheduling technique does not allow for
statistical multiplexing (i.e.) bandwidth sharing) of end user traffic.
Therefore, an efficient technique for scheduling variable bit rate traffic
that
allows for statistical multiplexing is needed.
Brief Description of the Drawing
In the Drawing,
FIG. 1 is a block diagram showing an exemplary shared medium
network in accordance with a preferred embodiment of the present
invention;
FIG. 2 is a block diagram showing a headend unit and an access
intertace unit in accordance with a preferred embodiment of the present
invention;
FIG. 3 is a state diagram showing three possible states of a MAC
User and the transitions among them in accordance with various
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
3
embodiments including prior art embodiments and a preferred
embodiment of the present invention;
FIG. 4 is a logic diagram showing exemplary head end scheduler
logic in accordance with a first embodiment of the present invention;
FIG. 5 is a logic diagram showing exemplary head end scheduler
logic in accordance with a second embodiment of the present invention;
FIG. 6 is a logic diagram showing exemplary MAC User logic in
accordance with a third embodiment of the present invention;
FIG. 7 is a logic diagram showing exemplary head end scheduler
logic in accordance with a third embodiment of the present invention;
FIG. 8 is a logic diagram showing exemplary head end scheduler
logic in accordance with a fourth embodiment of the present invention;
F1G. 9 is a logic diagram showing exemplary head end scheduler
logic in accordance with a fifth embodiment of the present invention;
Detailed Description
An efficient technique for scheduling variable bit rate traffic that
allows for statistical multiplexing is needed. The present invention
provides such an efficient technique for scheduling variable bit rate traffic
by providing data transmission opportunities at the peak cell rate when
the end user is actively transmitting data, and providing data transmission
opportunities at a lower rate when the end user has no data to transmit.
When the end user has no data to transmit, any excess data transmission
opportunities (i.e., data transmission opportunities from the lower rate up
to the peak cell rate) are available for statistically multiplexing traffic
from
other end users. Various embodiments of the present invention utilize a
lower rate anywhere between a zero rate and a sustainable cell rate,
inclusive. Alternative embodiments of the present invention allocate a
burst of data transmission opportunities equivalent to a maximum burst
3 0 size at the peak cell rate when the end user has data to transmit) after
which the end user is once again provided data transmission
opportunities at the lower rate.
CA 02268794 1999-04-14
WO 99/09690 PCTNS98/14894
4
FIG. 1 is a block diagram showing an exemplary shared medium
network 100 in accordance with a preferred embodiment of the present
invention. The shared medium network 100 allows a number of end
users 110, through 110N to access a remote external network 108 such
S as the Internet. The shared medium network 100 acts as a conduit for
transporting information between the end users 110 and the external
network 108.
The shared medium network 100 includes a Headend Unit (HU)
102 that is coupled to the external network 108. The HU 102 is in
communication with a plurality of Access Intertace Units 104, through
104N (collectively referred to as "AIUs 104" and individually as an "AIU
104") by means of a shared physical medium 106. Each end user 110
intertaces to the shared medium network 100 by means of an AIU 104. A
single AIU 104 may support one or a number of the end users 110.
The shared physical medium 106 includes a pluraVity of channels
over which information can be transferred between the HU 102 and the
AIUs 104. In the preferred embodiment, each channel is unidirectional;
that is, a particular channel either carries information from the HU i 02 to
the AIUs 104 or from the AIUs 104 to the HU 102. Those channels that
carry information from the HU 102 to the AIUs 104 are typically referred to
as "downstream channels." Those channels that carry information from
the AIUs 104 to the HU 102 are typically referred to as "upstream
channels." In alternative embodiments, these various upstream and
downstream channels may, of course, be the same physical channel, for
example) through time-division multiplexing/duplexing) or separate
physical channels, for example, through frequency-division
multiplexing/duplexing.
In the preferred embodiment) the shared medium network 100 is a
data-over-cable (DOC) communication system wherein the shared
3 0 physical medium 106 is a two-way hybrid fiber-optic and coaxial cable
(HFC) network. The HU 102 is a headend device typically referred to as
a "cable router." The AIUs 104 are cable modems. In other
CA 02268794 1999-04-14
WO 99I09690 PCT/US98/14894
embodiments, the shared physical medium 106 may be coaxial cable,
fiber-optic cable, twisted pair wires, and so on, and may also include air,
atmosphere, or space for wireless and satellite communication.
In the shared medium network 100 of the preferred embodiment,
5 the downstream channels are typically situated in a frequency band
above approximately 50 MHz, although the particular frequency band
may vary from system to system, and is often country-dependent. The
downstream channels are classified as broadcast channels, since any
information transmitted by the HU 102 over a particular downstream
channel reaches all of the AIUs 104. Any of the AIUs 104 that are tuned
to receive on the particular downstream channel can receive the
information.
_ In the shared medium network 100 of the preferred embodiment,
the upstream channels are typically situated in a frequency band
1 S between approximately 5 through 42 MHz, although the particular
frequency band may vary from system to system, and is often country-
dependent. Each upstream channel is divided into successive time slots,
and is therefore often referred to as a "slotted channel." A slot may be
used to carry a protocol data unit including user or control information) or
may be further divided into mini-slots used to carry smaller units of
information. The upstream channels are classified as shared channels,
since only one A1U 104 can successfully transmit in a slot or mini-slot at
any given time) and therefore the upstream channels must be shared
among the plurality of AIUs 104. If more than one of the AIUs 104
simultaneously transmit in a slot or mini-slot) there is a collision that
corrupts the information from all of the simultaneously transmitting AIUs
104.
In order to allow multiple AIUs 104 to share a single upstream
channel, the HU 102 and the AIUs 104 participate in a medium access
control (MAC) protocol. The MAC protocol provides a set of rules and
procedures for coordinating access by the AIUs 104 to the shared
channel. Each AIU 104 participates in the MAC protocol on behalf of its
CA 02268794 1999-04-14
WO 99/09690 PCTNS98/14894
6
end users. For convenience) each participant in the MAC protocol is
referred to as a "MAC User."
A MAC User typically represents a connection supporting a
particular end user application. Although it is not elaborated upon, a
MAC User could also represent an aggregate of connections that share
similar traffic characteristics. In many modern communication networks,
each MAC User has specific traffic parameters and QoS requirements,
which are agreed upon when the MAC User establishes a connection in
the network and which are guaranteed by the network. For example) a
MAC User may require a guaranteed minimum amount of bandwidth, a
guaranteed maximum transfer delay for the data it transmits, or a
minimum time variation between transmission opportunities provided by
the HU 102. In a cell-based network such as an Asynchronous Transfer
Mode (ATM) network) a number of parameters are used to characterize
the bandwidth requirements of each MAC User. Specifically, a set of
ATM Traffic Descriptors is used for characterizing the type of traffic
generated by the MAC User) and a set of QoS Parameters is used for
specifying the network services required by the MAC User.
The ATM Traffic Descriptors include Peak Cell Rate (PCR))
Sustainable Cell Rate (SCR), Minimum Cell Rate (MCR), and Maximum
Burst Size (MBS). The PCR is an indication of the maximum data rate
(cells per second) that will be generated by the MAC User. The SCR
represents the long-term average data rate generated by the MAC User.
The MCR is the minimum data rate (cells per second) required by the
MAC User. The MBS is the maximum size (number of cells) of any burst
generated by the MAC User.
The ~oS parameters include Maximum Cell Transfer Delay
(MaxCTD)) Cell Delay Variation (CDV), and Cell Loss Ratio (CLR). The
MaxCTD specifies the maximum delay (including the access delay and
propagation delay of the underlying communications network) that will be
tolerated by the MAC User. The CDV specifies the maximum time
variation between data transmission opportunities that will be tolerated
CA 02268794 1999-04-14
WO 99l09690 PCTJUS98/14894
7
by the MAC User. The CLR specifies the MAC User's allowance of cells
that may be dropped by the network, in terms of a ratio of lost cells to all
the cells transmitted by the MAG User.
MAC Users having similar traffic characteristics are categorized
into service categories. ATM defines five service categories, namely
continuous bit rate (CBR), real-time variable bit rate (RT-VBR), non-real-
time variable bit rate (NRT-VBR), available bit rate (ABR)) and-unspecified
bit rate (UBR). Each MAC User is categorized into one of the service
categories.
CBR connections are characterized by traffic having a fixed bit rate
and requiring real-time delivery of cells. The ATM Traffic Descriptor for
the CBR service category is PCR. The QoS Parameters far the CBR
service category are MaxCTD, CDV, and CLR.
RT-VBR connections are characterized by traffic having a variable
bit rate and requiring real-time delivery of cells. In a typical RT-VBR
connection, the traffic over the connection will have periods where cells
are generated in bursts at the PCR and periods of silence where no cells
are generated (voice and real-time video are good examples of RT-VBR
traffic). The ATM Traffic Descriptors for the RT-VBR service category are
PCR, SCR) and MBS. The G~oS Parameters for the RT-VBR service
category are MaxCTD, CDV, and CLR.
NRT-VBR connections are characterized by traffic having a
variable bit rate (similar to RT-VBR connections), but not requiring real
time delivery of cells. NRT-VBR connections typically require a low CLR.
ABR connections are characterized by traffic requiring a minimum
cell rate, but willing to accept additional bandwidth if and when such
additional bandwidth becomes available. The ATM Traffic Descriptors for
the ABR service category are the MCR and PCR. The MCR is the
minimum guaranteed cell rate required by the connection. The PCR is
the maximum cell rate at which the connection can transmit if allowed by
the network. Consequently, the transmission rate of the ABR connection
lies somewhere between the MCR and the PCR. No QoS Parameters
CA 02268794 1999-04-14
WO 99/09690 PCTNS98/14894
g
are defined for the ABR service category. ABR connections are typically
subject to a flow control mechanism with feedback that requires the
source of the connection to adapt its rate in response to changing ATM
layer transfer characteristics.
UBR connections are not guaranteed any bandwidth and have no
QoS requirements. The ATM Traffic Descriptor for the UBR service
category is the PCR. The PCR is the maximum cell rate at which the
connection can transmit if allowed by the network.
FIG. 2 is a block diagram 200 showing the HU 102 and the AIU
104 in accordance with a preferred embodiment of the present invention.
The block diagram 200 shows the HU 102 in communication with one of
the AIUs 104 by means of a downstream channel 230 and an upstream
channel 240. In the preferred embodiment, the downstream channel 230
and the upstream channel 240 are separate channels carried over the
shared physical medium 106. The AIU 104 supports at least one End
User 110. The HU 102 transmits data and control messages to the AIU
104 by means of downstream channel 230, and receives reservation
requests and data from the AIU 104 by means of upstream channel 240.
The HU 102 includes a Connection Manager (CM) 215. The CM
215 is responsible for connection admission control for the network.
More specifically, the CM 215 is responsible for establishing and
terminating connections in the network.
Before an End User such as the End User 1 i 0 can communicate
over the network, a connection must be established. Therefore, when the
End User 110 requests admission to the network, a connection request
message is forwarded to the CM 215. The connection request message
specifies the bandwidth and QoS requirements for the connection in the
form of an ATM Service Category and associated ATM Traffic Descriptors
and QoS Parameters. The CM 215 decides whether or not to establish
the connection, and thereby admit the End User 110 to the network)
based on the ability (or inability) of the network to meet the bandwidth
and QoS requirements of the End User 110.
CA 02268794 1999-04-14
WO 99/09690 PCTNS98/14894
9
The HU 102 also includes a Headend Scheduler (HES) 214 that is
coupled to the CM 215 and to an Adaptive Reservation Manager (ARM)
211. The HES 214 is responsible for scheduling data transmission
opportunities for those End Users that have been admitted to the network
by the CM 215. When the CM 215 establishes a connection, the CM 215
sends a connection setup message to the HES 214 including a
connection identifier and the ATM Service Category and associated ATM
Traffic Descriptors and QoS Parameters for the established connection.
Similarly, when the CM 215 terminates a connection, the CM 215 sends
a connection release message to the HES 214 including a connection
identifier for the terminated connection. The HES 214 uses the
connection information received from the CM 215 together with feedback
information received from the ARM 211 to control the timing of control
messages transmitted by the ARM 211.
The ARM 211 is responsible for implementing the MAC protocol in
the HU 102. The ARM 211 includes a Reservation Manager (RM) 212
and a Feedback Controller (FC) 213. The RM 212 monitors the
contention mini-slots on the upstream channel 240 to determine the
result of contention for each contention mini-slot. The RM 212 sends the
contention results to the FC 213 and to the HES 214. The FC 213
maintains the state information for each priority class (if multiple priority
classes are implemented to support differentiated quality of service),
determines the assignment of contention mini-slots for each contention
cycle, and formats the control messages to be transmitted on the
downstream channel 230. The FC 213 bases the timing of control
message transmissions on, among other things, timing information
received from the HES 214.
The AIU 104 includes a User Intertace (UI) 225 for interfacing with
the End User 110. Data transmitted by the End User 110 is received by
the UI 225 and stored in a Memory 224. The UI 225 also stares in the
Memory 224 a time stamp indicating the arrival time of the data.
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
The AIU 104 also includes a Control Message Processor (CMP)
222 that is coupled to the Memory 224. The CMP 222 is responsible for
processing data and control messages received from the HU 102 by
means of Receiver 221. The CMP 222 participates as a MAC User in the
5 MAC protocol on behalf of the End User 110.
A number of different MAC protocols have been developed for use
in the shared medium network 100. These protocols can generally be
categorized as contention-free protocols and contention-based protocols.
Contention-free protocols, such as time-division multiple-access (TDMA)
10 and round-robin polling, avoid collisions on the shared channel by
authorizing only one MAC User to transmit at a time. Contention-based
protocols, such as certain reservation-based protocols, do not avoid
collisions but instead resolve any collisions that do occur on the shared
channel.
In a preferred embodiment, the MAC protocol uses a combination
of polling and contention-based reservation for scheduling upstream
transmissions. Contention-based reservation requires a MAC User to
make a reservation before the HU 102 will allocate bandwidth to the MAG
User. The HU 102 provides reservation opportunities to the MAC Users
by transmitting special control messages (described in detail below) to
the MAC Users by means of the downstream channel 230. A MAC User
makes a reservation by transmitting a reservation request message in
response to a reservation opportunity provided by the HU 102. Each
reservation opportunity typically authorizes multiple MAC Users to
respond, and therefore the MAC Users must contend for a reservation.
Not all MAC Users are required to make a reservation. Certain MAC
Users are allocated bandwidth regularly without having to make
reservations.
Each MAC User that is required to make a reservation maintains a
MAC User state machine as known in the prior art and described with
reference to FIG. 3. The MAC User starts in the INACTIVE state 302) and
remains there so long as it has no data to transmit. When the MAC User
CA 02268794 1999-04-14
WO 99109690 PCTNS98/14894
11
receives data to be transmitted) the MAC User transitions into the
CONTENTION state 304. In the CONTENTION state 304, the MAC User
contends for access to the shared channel until it is able to make a
successful reservation for itself. Upon making a successful reservation in
state 304, the MAC User transitions into the ACTIVE state 306. Here) the
MAC User receives opportunities from the HU 102 to transmit data, and
remains in the ACTIVE state 306 so long as it has data to transmit. Upon
transmitting all of its data) the MAC User is considered to be "fulfilled,"
and the MAC User transitions back into the INACTIVE state 302. Each
MAC User that is not required to make a reservation remains in the
ACTIVE state 306 so long as its connection is active.
In a preferred embodiment, the MAC protocol divides each
upstream channel into discrete time slots. A MAC User transmits
reservation request messages and data in slots designated by the HU
102. In the preferred embodiment) the upstream channel supports two
types of slots, namely contention slots and data slots. Contention slots
are typicaNy of shorter duration than data slots, and are therefore often
referred to as "mini-slots" or "contention mini-slots." Contention mini-slots
are used for transmitting reservation request messages, white data slots
are used for transmitting data messages. Each data slot is typically
capable of carrying the equivalent of a single protocol data unit, which, in
a cell-based network such as Asynchronous Transfer Mode (ATM)) is a
cell.
Although not required, a typical embodiment divides the upstream
channel 240 into consecutive contention cycles) where each contention
cycle is typically composed of a predetermined number of contention
mini-slots and a predetermined number of data slots set at fixed locations
within the contention cycle. It is typical for the contention mini-slots (and
therefore the data slots also) to be contiguous within the contention cycle.
For the sake of simplicity, the contention mini-slots are typically
scheduled in clusters, each of which consists of the maximum number of
contention mini-slots that can fit within a data slot.
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
12
For each contention cycle, the HU 102 transmits an entry poll
message to the MAC Users by means of the downstream channel 230.
The entry poll message includes an assignment of contention mini-slots
for the contention cycle, indicating which MAC Users) are permitted to
contend in each contention mini-slot, and an assignment of data slots for
the contention cycle, indicating which MAC User is permitted to transmit
data in each data slot. Each entry poll message also includes feedback
information (described in detail below) for each contention mini-slot in the
preceding contention cycle. The feedback information allows each MAC
User that contended in the preceding contention cycle to determine the
outcome of its contention (i.e., success or failure).
Typically, only MAC Users that are in the CONTENTION state 304
that have data to transmit may contend for a reservation by transmitting a
reservation request message in a designated contention mini-slot. The
HU 102 monitors each contention mini-slot to determine the result of
contention for each contention mini-slot. Specifically) the HU 102
receives either (1 ) no transmission, indicating that no MAC User
transmitted in the contention mini-slot; (2) a reservation request message,
indicating that a single MAC User transmitted in the contention mini-slot
and identifying that MAC User; or (3) a collision) indicating that more than
one MAC User transmitted in the contention mini-slot. For convenience,
the three states are referred to as IDLE, SUCCESS, and COLLISION,
respectively.
As discussed above, the HU 102 includes feedback information in
each entry poll message. Specifically, in each entry poll message, the
HU 102 indicates a feedback state (i.e.) IDLE) SUCCESS, or
COLLISION) for each contention mini-slot in the preceding contention
cycle. The feedback information allows each MAC User that transmitted
a reservation request message in the preceding contention cycle to
determine the result of its contention attempt. Specifically, each MAC
User examines the feedback state corresponding to the contention mini-
slot in which the MAC User transmitted its reservation request message
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
13
to determine if the result is SUCCESS or COLLISION. If the feedback
state indicates SUCCESS, then the MAC User transitions from the
CONTENTION state 304 to the ACTIVE state 306 and awaits data
transmission opportunities from the HU 102; otherwise) the MAC User
remains in the CONTENTION state 304 and awaits further contention
opportunities from the HU 102.
The HU 102 provides data transmission opportunities to the active
MAC Users (i.e., those MAC Users that have made a successful
reservation or require no reservation). Specifically, the HES 214
schedules data transmission opportunities to the active MAC Users by
allocating data slots on the upstream channel 240 such that each MAC
User receives a sufficient amount of bandwidth within its QoS constraints.
CBR connections require bandwidth at a constant rate within
specified delay and fitter constraints. Therefore, CBR MAC Users are
allocated data transmission opportunities at regular intervals at the PCR.
CBR MAC Users are not required to make reservations, and therefore
remain in the ACTIVE state 306 as long as the CBR connection is active.
RT-VBR connections are allocated a sufficient amount of
bandwidth to meet the bandwidth and real-time delivery requirements of
the connection. One approach is to treat the RT-VBR connection like a
CBR connection by allocating bandwidth at regular intervals at the PCR.
This guarantees that the bandwidth and real-time delivery requirements
of the connection will be met. However, it may also be an inefficient use
of bandwidth, since the RT-VBR connection does not generate data
constantly at the PCR.
Treating a RT-VBR connection like a CBR connection may be
acceptable for certain RT-VBR connections, specifically those having an
SCR close to the PCR, but is less desirable if there is a significant
difference between the SCR and the PCR. Therefore) it is convenient to
categorize each RT-VBR connection according to the ratio of SCR to
PCR. If the ratio of SCR to PCR exceeds a predetermined value, for
example 0.5, then the connection is considered to be a CBR-like
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
14
connection that can be treated like a CBR connection with little loss of
bandwidth efficiency. However, if the ratio of SCR to PCR is less than or
equal to the predetermined value, then the connection is considered to
be a "bursty" connection, and is preferably not treated like a CBR
S connection.
For a "bursty" RT-VBR connection, bandwidth allocation at the PCR
is excessive and is therefore inefficient and undesirable. Likewise, it is
also undesirable to allocate bandwidth at the SCR, since the network
would then be unable to guarantee real-time delivery of cells for the
connection. Therefore) various embodiments of the present invention
allocate data transmission opportunities for "bursty" RT-VBR traffic at the
PCR when the MAC User has data to transmit and at a lower rate when
the MAC User has no data to transmit. For convenience) the MAC User is
said to be "active" when it is determined that the MAC User requires data
transmission opportunities at the PCR and "inactive" when it is
determined that the MAC User does not require data transmission
opportunities at the PCR.
In a first embodiment, the HES 214 allocates data transmission
opportunities at the PCR while the MAC User is "active" and at a zero rate
while the MAC User is "inactive". In this first embodiment) the MAC User
begins in the INACTIVE state 302, and transitions into the CONTENTION
state 304 when the MAC User receives data to be transmitted. In the
CONTENTION state 304, the MAC User contends as described above.
Once a successful reservation is made, the MAC User transitions into the
ACTIVE state 306, and the HES 214 allocates data slots to the MAC User
at the PCR. The HES 214 monitors the data slots allocated to the MAC
User to determine whether the MAC User continues to transmit data, in
which case the MAC User is active, or the MAC User is no longer
transmitting data, in which case the MAC User is inactive. After a
3 0 predetermined number of data slots in which no data is transmitted by the
MAC User, the MAC User transitions back to the INACTIVE state 302) and
the HES 214 stops allocating data slots to the MAC User.
CA 02268794 1999-04-14
WO 99/09690 PCTlUS98l14894
Exemplary HES 214 logic for scheduling data transmission
opportunities in accordance with the first embodiment of the present
invention is shown in FIG. 4. The HES 214 allocates data transmission
opportunities for the MAC User at the zero rate when the MAC User is
5 "inactive" (402). When the MAC User makes a reservation (404), the
HES 214 allocates data transmission opportunities for the MAC User at
the PCR (406). The HES 214 continues allocating data transmission
opportunities at the PCR as long as the MAC User continues transmitting
data. When the MAC User has not transmitted data for a predetermined
10 number of consecutive data transmission opportunities (408)) the HES
214 returns to allocating data transmission opportunities for the MAC
User at the zero rate (402).
-This first embodiment for handling "bursty" RT-VBR traffic is
bandwidth efficient) at least to the degree that the MAC User is not
15 allocated bandwidth in excess of its required bandwidth (other than the
overhead of waiting until the MAC User has not transmitted data for a
predetermined number of consecutive data transmission opportunities
before the MAC User is considered to be "inactive"). However, because
the MAC User is required to contend for access following a period of
inactivity) the MAC User is required to buffer data during the period of
contention and therefore is delayed in transmitting the data. The
contention access delay may vary each time the MAC User contends,
since there is no a priori knowledge as to how many contention cycles it
will take before a successful reservation is made. Therefore, the
contention access delay and its variability makes it difficult for the HES
214 to meet the guaranteed CDV for the MAC User.
The contention access delay also affects the CLR. If the contention
access delay is too large, some cells become "obsolete" and are
consequently dropped by the MAC User. Although typical RT-VBR
connections can tolerate a certain amount of cell loss, it is desirable to
minimize such degradation if possible. Moreover, the smaller the CLR)
the more closely the SCR requirement is matched. Thus, it is preferable
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
16
that a contention-based reservation access scheme that supports
multiple priority classes be used so that the RT-VBR users can be given
high priority for reservation access. One contention-based reservation
access scheme that supports multiple priority classes is described in U.S.
S Patent Application No. 08/865,924 entitled System, Device) and Method
for Sharing Contention Mini-Slots Among Multiple Priority Classes, filed
on May 30) 1997 in the name of Chester A. Ruszczyk, Whay Chiou Lee,
and Imrich Chlamtac (Attorney Docket No. CX097020) with a preferred
collision resolution technique described in U.S. Patent Application No.
08l866,865 entitled System, Device, and Method for Contention-Based
Reservation in a Shared Medium Network, filed on May 30, 1997 in the
name of Chester A. Ruszczyk, Whay Chiou Lee) and Imrich Chlamtac
(Attorney Docket Na. CX096053). Even with the use of an efficient
contention-based reservation access scheme that supports multiple
priority classes, it is important that the CM 215 only admit an additional
RT-VBR user if the system can support the user without excessive
contention access decay.
In a second embodiment) the HES 214 allocates data transmission
opportunities at the PCR rate white the MAC User is "active" and at a
lower non-zero rate, preferably at the SCR, while the MAC User is
"inactive". In this second embodiment, HES 214 allocates data
transmission opportunities for the MAC User regularly (although the
allocation rate varies)) so the MAC User remains permanently in the
ACTIVE state 306 and is not required to make a reservation. The HES
214 typically begins by allocating bandwidth at the lower non-zero rate
and monitoring for data transmissions by the MAC User. As soon as the
MAC User begins transmitting data in the designated data slots) the HES
214 increases the bandwidth allocation to the PCR and monitors for the
MAC User to stop transmitting data. The HES 214 continues allocating
bandwidth at the PCR so long as the MAC User is actively transmitting
data. When the MAC User stops transmitting data) the HES 214 throttles
the bandwidth allocation back to the lower non-zero rate. This throttling
*rB
CA 02268794 1999-04-14
WO 99l09690 PCT/US98/14894
1~
can occur immediately upon a determination that the MAC User is
"inactive" (e.g., following a predetermined number of data transmission
opportunities in which no data was transmitted) or gradually by
decreasing the bandwidth allocation in steps. By providing a minimum
bandwidth equal to the tower non-zero rate and providing PCR on
demand, the HES 214 is more easily able to meet the delay and fitter
requirements of the MAC User because the slots allocated at the lower
non-zero rate are sent at known intervals) and the HES 214 is able to
react quickly when the MAC User requires bandwidth at the PCR._
Exemplary HES 214 logic for scheduling data transmission
opportunities in accordance with the second embodiment of the present
invention is shown in FIG. 5. The HES 214 allocates data transmission
opportunities for the MAC User at the lower non-zero rate when the MAC
User is "inactive" (502). When the MAC User transmits data in response
to an allocated data transmission opportunity (504), the HES 214
allocates data transmission opportunities for the MAC User at the PCR
(506). The HES 214 continues allocating data transmission opportunities
at the PCR as long as the MAC User continues transmitting data. When
the MAC User has not transmitted data for a predetermined number of
consecutive data transmission opportunities (508), the HES 214 returns
to allocating data transmission opportunities for the MAC User at the
lower non-zero rate (502).
One advantage of this second embodiment is that the MAC User
"knows" that it is being provided regular data transmission opportunities.
Therefore, any data received between scheduled data transmission
opportunities can be buffered until the next scheduled data transmission
opportunity, and the MAC User is not required to contend in order to get
transmission opportunities. However, if the MAC User is frequently
"inactive" for a comparatively long time with respect to the time it is
"active," much bandwidth is wasted. Moreover, the ability for the system
to statistically multiplex RT-VBR connections is diminished. In this
second embodiment, it is also possible that under certain circumstances,
CA 02268794 1999-04-14
WO 99/09690 PCTNS98/14894
18
the reduced allocation rate will be insufficient to guarantee that data
received by the MAC User between polls can be transmitted within the
QoS constraints simply by waiting for the next data transmission
opportunity. fn this situation, it is preferable for the MAC User to contend
for a reservation) prompting the HES 214 to provide a data transmission
opportunity to the MAG User sooner than the next scheduled data
transmission opportunity.
In a third embodiment, the MAC User decides whether or not to
contend when it receives data between scheduled data transmission
opportunities. When the MAC User receives data to be transmitted, the
MAC User first determines the amount of time before the next scheduled
data transmission opportunity) and then determines whether the QoS
constraints will be violated if the MAC User waits until the next scheduled
data transmission opportunity. If waiting until the next scheduled data
transmission opportunity will violate the QoS constraints, then the MAC
User contends for a reservation; otherwise, the MAC User waits for the
next scheduled data transmission opportunity.
Exemplary MAC User logic in accordance with the third
embodiment of the present invention is shown in FIG. 6. The logic begins
in step 602) and upon receiving data to be transmitted in step 604)
proceeds to determine the amount of time before the next scheduled data
transmission opportunity, in step 606. The logic then determines whether
the GloS constraints for the MAC User will be violated if the MAC User
waits until the next scheduled data transmission opportunity) in step 608.
If the QoS constraints will not be violated if the MAC User waits until the
next scheduled data transmission opportunity (NO in step 610), then the
logic buffers the data until the next scheduled data transmission
opportunity, in step 612. However) if the QoS constraints will be violated
if the MAC User waits until the next scheduled data transmission
opportunity (YES in step 610)) then the logic contends for a reservation,
in step 614. The logic terminates in step 699.
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
19
Exemplary HES 214 Logic for scheduling data transmission
opportunities in accordance with the third embodiment of the present
invention is shown in FIG. 7. The HES 214 allocates data transmission
opportunities for the MAC User at the lower non-zero rate when the MAC
User is "inactive" (702). When the MAC User either transmits data in
response to a data transmission opportunity or makes a reservation
(704), the HES 214 allocates data transmission opportunities for the MAC
User at the PCR (706). The HES 214 continues allocating data
transmission opportunities at the PCR as long as the MAC User
continues transmitting data. When the MAC User has not transmitted
data for a predetermined number of consecutive data transmission
opportunities (708), the HES 214 returns to allocating data transmission
opportunities for the MAC User at the lower non-zero rate (702).
In the embodiments described above, the HES 214 utilizes only
1 S the PCR and SCR traffic descriptors for scheduling data transmission
opportunities. However, RT-VBR traffic is also characterized by the MBS,
which specifies the maximum amount of data that the MAC User can
transmit at the PCR during any one burst. Alternative embodiments
utilize the MBS to simplify scheduling by automatically allocating a burst
of data transmission opportunities (referred to as a "burst allocation")
equivalent to the MBS at the PCR when the MAC User becomes "active."
During the burst allocation, the HES 214 does not have to monitor and
react to the status of the MAC User (i.e., "active" or "inactive"), and
therefore the HES 214 logic is simplified. Upon completion of the burst
allocation, the HES 214 automatically treats the MAC User as being
"inactive" and allocates data transmission opportunities at the lower rate.
By automatically providing a burst allocation when the MAC User
becomes "active," the HES 214 provides for efficient bandwidth utilization
if the MAC User transmits a maximum size burst each time it becomes
"active." However, utilizing the burst allocation is inefficient if the actual
burst size is variable or is consistently less than the MBS. When the MBS
CA 02268794 1999-04-14
WO 99/09690 PCTJUS98114894
is considerably larger than a typical burst size, the system's ability to
statistically multiplex RT-VBR connections is diminished.
Exemplary HES 214 logic for scheduling data transmission
opportunities in accordance with a fourth embodiment of the present
5 invention is shown in FIG. 8. The HES 214 allocates data transmission
opportunities for the MAC User at the zero rate when the MAC User is
"inactive" (802). When the MAC User makes a reservation (804), the
HES 214 makes a burst allocation for the MAC User at the PGR (806).
When the burst allocation is complete (808), the HES 214 returns to
10 allocating data transmission opportunities for the MAC User at the zero
rate (802).
Exemplary HES 214 logic for scheduling data transmission
opportunities in accordance with a fifth embodiment of the present
invention is shown in FIG. 9. The HES 214 allocates data transmission
15 opportunities for the MAC User at the lower non-zero rate when the MAC
User is "inactive" (902). When the MAC User either transmits data in
response to a data transmission opportunity or makes a reservation
(904), the HES 214 makes a burst allocation for the MAC User at the PCR
(906). When the burst allocation is complete (908), the HES 214 returns
20 to allocating data transmission opportunities for the MAC User at the
lower non-zero rate (902).
Although the above embodiments are described with reference to
a particular reservation-based MAC protocol that utilizes a slotted
upstream channel, the present invention is not limited to either the
reservation-based MAC protocol or the slotted upstream channel. The
described scheduling techniques are applicable to other MAC protocols
and other upstream channel configurations. In particular, the described
scheduling techniques are applicable to a MAC protocol commonly
referred to as Multimedia Cable Network System (MCNS). It will be
apparent to a skilled artisan how the described scheduling techniques
can be applied to the MCNS protocol and to other MAC protocols and
upstream channel configurations.
CA 02268794 1999-04-14
WO 99/09690 PCT/US98/14894
21
All logic described herein can be embodied using discrete
components, integrated circuitry, programmable logic used in conjunction
with a programmable logic device such as a Field Programmable Gate
Array (FPGA) or microprocessor, or any other means including any
S combination thereof) Programmable logic can be fixed temporarily or
permanently in a tangible medium such as a read-only memory chip, a
computer memory, a disk, or other storage medium. Programmable logic
can also be fixed in a computer data signal embodied in a carrier wave,
allowing the programmable logic to be transmitted over an intertace such
as a computer bus or communication network. All such embodiments are
intended to fall within the scope of the present invention.
The present invention may be embodied in other specific forms
without departing from the essence or essential characteristics. The
described embodiments are to be considered in all respects only as
illustrative and not restrictive.
