Note: Descriptions are shown in the official language in which they were submitted.
CA 02292479 1999-12-02
WO 99/00941 PCT/US98/09715
System, Device, And Method For Providing Low Access Delay For
Time-Sensitive Applications In A Shared Medium Network
Background
1. Field of the Invention
The invention relates generally to communication systems and, more
particularly, to multiple access protocols for use over a shared
communications
medium
2. Discussion of Related Art
In today's information age, there is an increasing need for high speed
communications that provides 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 will be employed increasingly in the 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 interfere
with
each other. In modern broadband communications networks, the shared
communications channel is typically one of a number of frequency bands carried
over a shared physical medium, such as a hybrid fiber-optic/coaxial cable
(HFC)
network or by electromagnetic waves in free space. Since communications
networks typically have a limited number of communications channels, the
shared
medium network 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.
!n the shared medium network, each end user interfaces to the shared
channel by means of an Access Interface Unit (AIU) which allows the end user
to
transmit and receive information via the shared channel. A single AIU may
support
i
CA 02292479 1999-12-02
WO 99/00941 PCT/US98/09715
one or a number of end users. Each end user wishing to utilize the shared
channel participates in a Medium Access Control (MAC) protocol which provides
a
set of rules and procedures for accessing the shared channel. For convenience,
each participant in the MAC protocol is referred to as a MAC User.
S FIG. 1 is a logical representation of a shared medium network 100 as is
known in the art. As illustrated in FIG. 1, a headend unit 110 is coupled to a
plurality of AIUs 120a through 120 (collectively referred to as AIUs 120) via
a
shared channel 130. In the preferred embodiment, the shared channel 130 is one
of a number of communications channels carried by a shared physical medium
such as an HFC or wireless network. In other embodiments, the shared physical
medium 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. The headend unit 110 is also coupled to a communications
network 140, which may include networks such as the Internet, on-line
services,
telephone and cable networks, and other communication systems.
Continuing to refer to FIG. 1, in the preferred embodiment, the shared
physical medium, such as an HFC or wireless network, has or supports a
plurality
of communications channels. For ease of reference, the communications
channels in which a headend unit, such as the headend unit 110, transmits
information, signals, or other data to an AIU, such as AIU 120, are referred
to as
downstream channels. Also for ease of reference, the communications channels
in which an AIU, such as AIU 120, transmits information, signals, or other
data to a
headend unit, such as headend unit 110, are referred to as upstream channels.
These various upstream and downstream channels may, of course, be the same
physical channel or may be separate physical channels, for example, through
time-division multiplexing or frequency-division multiplexing. These various
channels may also be logically divided in other ways, in addition to upstream
and
downstream directions. In the preferred embodiment, the communications
medium is an HFC network, with downstream channels in the frequency spectrum
(band) typically 50 - 750 MHz (and up to 1 GHz), and with upstream channels in
the frequency spectrum typically 5 - 42 MHz.
In a simple model of ar: exemplary HFC network, the headend unit uses a
single downstream channel to send information, including poll messages, to the
MAC Users, and a single upstream channel is used by the MAC Users to send
information to the headend unit. Since the headend unit is the only device
which
2
CA 02292479 1999-12-02
WO 99/00941 PCT/US98/09715
transmits on the downstream channel, the downstream channel is not a "shared
channel" as that term is applied to the present invention. However, since
multiple
MAC Users transmit on the upstream channel, the upstream channel is a shared
channel, and the MAC protocol must provide for orderly access to the channel
so
as to maximize the data throughput over the channel.
A number of different access techniques have been developed for use over
a shared channel. These techniques can generally be categorized as contention-
free, which avoid collisions on the shared channel by means of various
scheduling
methods, and contention-based, which do not avoid collisions but instead
resolve
any collisions that do occur on the shared channel. Contention-free protocols,
such as time-division multiple access (TDMA) and round-robin polling
protocols,
are typically less efficient than contention-based protocols under light loads
because the contention-free protocols generally allocate some amount of
bandwidth to each MAC User whether or not the MAC User has information to
send. On the other hand, contention-based protocols only allocate bandwidth to
those MAC Users that have information to send, although some amount of
bandwidth is wasted whenever collision resolution is required. Hybrid
protocols,
utilizing both contention-free and contention-based access, have been
developed
in an attempt to gain the advantages of both techniques.
In many multiple access protocols, some form of round-robin polling is used.
In the round-robin polling technique, a list of MAC Users is maintained, and
the
MAC Users on the list are polled sequentially, one after the other, to provide
each
MAC User with an opportunity to transmit data on the shared channel. In
straight
round-robin polling, each MAC User is provided equal access to the shared
channel whether the MAC User is "active" (i.e., is actively generating data)
or
"inactive" (i.e., infrequency has data to transmit).
Some round-robin polling protocols attempt to improve the effectiveness
and efficiency of polling by segregating the MAC Users into multiple lists
according
to the frequency with which the MAC User has data to transmit. The "active"
MAC
Users are typically placed on a "fast poll" list, and are polled at a
relatively high
frequency, while the "inactive" MAC Users are typically placed on a "slow
poll" list,
and are poll at a relatively low frequency. An alternative approach maintains
a list
of "recently active" MAC Users (i.e., MAC Users that are currently "inactive"
but had
recently been "active") which are polled less frequently than the MAC Users on
the
3 S fast poll list but more frequently than the MAC Users on the slow poll
fist. By
3
CA 02292479 1999-12-02
WO 99/00941 PCT/US98/09715
polling a MAC User at a frequency commensurate with its likelihood of having
data
to transmit, bandwidth efficiency may be improved.
Hybrid protocols go one step further and replace the round-robin polling of
"inactive" MAC Users with contention-based access. The "inactive" MAC Users
are provided opportunities to contend for access to the shared channel along
with
other "inactive" MAC Users. In this way, individual poll messages are not
wasted
on "inactive" MAC Users that have no data to transmit.
One problem with round-robin polling is that the MAC Users on each poll list
are treated as having equal priority and are provided equal access to the
shared
channel, even if the MAC Users have different priorities. For example, an
"active"
MAC User having high-priority, time-sensitive data is polled in the same
manner,
and at the same frequency, as an "active" user having low-priority, time-
insensitive
data. In that case, the data from the high-priority MAC User may be delayed
while
data from low-priority MAC Users is being transmitted. Clearly, segregating
MAC
Users according to data availability alone does not adequately address the
issue
of prioritizing MAC User transmissions. A knowledge of the MAC User priority a
priori would allow the polling sequence to account for MAC User priority.
However, the MAC User priority is typically not known at the time the MAC User
enters the system, and may change over time as the MAC User accesses various
services over the network. Therefore, a need remains for a system, device, and
method for providing low access delay for time-sensitive applications in a
shared
medium network.
Brief Descripfion of the Drawing
In the Drawing,
FIG. 1 is a block diagram of a shared medium network as is known in the art;
FIG. 2 is a logic flow diagram for processing an upstream burst
transmission; and
FIG. 3 is a logic flow diagram for a polling cycle.
Detailed Description
As discussed above, the need remains for a system, device, and method for
providing low access delay for time-sensitive applications in a shared medium
network. The present invention provides such low access delay by having the
4
CA 02292479 1999-12-02
WO 99/00941 PCTlUS98/09715
headend unit segregate MAC Users into a high-priority group and a low-priority
group. The headend unit first polls all of the high-priority MAC Users, and
then
polls low-priority MAC Users until either all low-priority MAC Users have been
polled or the low-priority MAC Users have been serviced for a predetermined
maximum polling time. The headend unit repeats this polling sequence in
sequential polling cycles to provide the high-priority MAC Users with
expedited
access to the shared channel.
In order for the headend unit to segregate the MAC Users into the high-
priority group and the low-priority group, the headend unit must be able to
determine the relative priority of each MAC User. In some networks, the MAC
User
priorities may be known a priori, for example, through configuration by a
network
administrator or by service class designations in an ATM or other network. In
other
networks, the MAC User priorities may not be known a priori, and, in fact, may
change over time as the end users access different applications over the
network.
In networks where the MAC User priorities are not explicitly known, the
headend
unit must determine the MAC User priorities by other means.
In the preferred embodiment, the MAC User priority is not known a priori
and is instead inferred from the characteristics of the upstream transmissions
generated by the MAC User. The headend unit monitors the MAC User
transmissions and determines the delay requirements of the MAC User according
to a predetermined set of parameters such as the burst/packet sizes
transmitted by
the MAC User, the packet types included in the MAC User transmissions, the
applications accessed by the MAC User, and any of a number of other parameters
that will be apparent to the skilled artisan. The headend unit may use one or
more
parameters to determine the relative priority of the MAC User, and may use a
different set of parameters for each MAC User.
In the preferred embodiment, the MAC User priority is inferred solely from
the size of the data packets transmitted by the MAC User. It has been observed
that time-sensitive, low-latency applications typically generate small data
packets
while time-insensitive applications typically generate larger data packets.
For
example, in a typical shared medium network carrying TCP/IP traffic, much of
the
upstream traffic for a TCP/IP application will be TCP acknowledgement packets
which are transmitted over the upstream channel to allow TCP/IP traffic to
continue
flowing over the downstream channel. Web surfing and gaming applications will
likewise typically generate small data packets in the upstream direction.
These
5
CA 02292479 1999-12-02
WO 99/00941 PCTlUS98/09715
small data packets transmitted over the upstream channel are time-sensitive,
since
a delay in their delivery may result in noticeably unacceptable performance of
the
application. Upstream file transfers, on the other hand, will typically be
characterized by large data packets transmitted over the upstream channel.
These
large data packets transmitted over the upstream channel are considered time-
insensitive, since a delay in their delivery will typically go unnoticed.
While it is not
universally true that time-sensitive applications transmit small packets over
the
upstream channel and that time-insensitive applications transmit large packets
over the upstream channel, the size of the packets is used by the headend unit
to
make an assumption as to the delay requirements of the application and
therefore
to categorize the MAC Users as either high-priority or low-priority.
Since transmit packet sizes may vary between transmissions, the preferred
embodiment utilizes an exponential weighted average of the received burst size
for each MAC User. The headend unit calculates the exponential weighted
average for each MAC User as bursts are received over the upstream channel.
MAC Users having an average packet size below a predetermined threshold
packet size are placed in the high-priority group, while the remaining MAC
Users
are placed in the low-priority group. The exponential weighted average for a
MAC
User is calculated according to the following formula:
avg_packet size = a * avg~acket size + (1 - a) * received_burst size
where a is a predetermined weighting factor and received burst size is the
size of
the most recent burst received from the MAC User.
Each time an upstream burst transmission is received from a MAC User, the
headend unit updates the average packet size calculation for the MAC User and
re-categorizes the MAC User into either the high-priority group or the low-
priority
group. A logic flow diagram for processing an upstream burst transmission is
shown in FIG. 2. The logic begins in step 210, and upon receiving a burst
transmission from the MAC User in step 220, the logic updates the average
packet
size for the MAC User, in step 230. The logic then determines whether the
average packet size is below the predetermined threshold packet size, in step
240.
If the average packet size for the MAC User is below the predetermined
threshold
packet size (YES in step 240), then the logic categorizes the MAC User in the
high-priority group, in step 250; otherwise, the logic categorizes the MAC
User in
the low-priority group, in step 260. The logic terminates in step 299.
6
CA 02292479 1999-12-02
WO 99/00941 PCT/US98/09715
Because the categorization of a MAC User represents an assumption as to
the delay requirements of the MAC User, the values selected for the
predetermined weighting factor a and the predetermined threshold packet size
affect whether or not a valid categorization is made. The selection of the
predetermined weighting factor a is a policy-based determination as to the
weight
placed on the most recently received burst relative to the historical average
calculated over prior bursts. In the preferred embodiment, the predetermined
weighting factor a is selected to be 0.5, which places equal weight on the
most
recently received burst and the historical average. The selection of the
predetermined threshold packet size is based on observed traffic
characteristics.
In the preferred embodiment, the predetermined threshold packet size is
selected
to be 200 bytes.
A logic flow diagram for a polling cycle is shown in FIG. 3. The logic for
each polling cycle begins in step 310 and proceeds to poll the next high-
priority
MAC User in the high-priority round-robin polling list, in step 320. After
polling the
MAC User in step 320, the logic proceeds to step 330 where it determines if
all of
the high-priority MAC Users have been polled during the polling cycle. If all
of the
high-priority MAC Users have not been polled during the polling cycle (NO in
step
330), then the logic recycles to step 320 to poll the next high-priority MAC
User.
However, if ali of the high-priority MAC Users have been polled during the
polling
cycle (YES in step 330), then the logic proceeds to step 340 where it polls
the next
low-priority MAC User in the low-priority round-robin polling list. After
polling the
next low-priority MAC User in step 340, the logic determines if all of the low-
priority
MAC Users have been polled during the polling cycle, in step 350. If all of
the low-
priority MAC Users have been polled during the polling cycle (YES in step
350),
then the logic recycles to step 310 to begin a new polling cycle. However, if
all of
the low-priority MAC Users have not been polled during the polling cycle (NO
in
step 350), then the logic determines whether the low-priority MAC Users have
been serviced for a predetermined maximum polling time, in step 360. if the
low-
priority MAC Users have not been serviced for the predetermined maximum
polling time (NO in step 360), then the logic recycles to step 340 to poll the
next
low-priority MAC User. However, if the predetermined maximum polling time has
been reached (YES in step 360), then the logic recycles to step 310 to begin a
new polling cycle.
CA 02292479 1999-12-02
WO 99/00941 PCT/US98/09715
If the headend unit terminates a polling cycle before polling all of the low-
priority MAC Users (i.e., by reaching the predetermined maximum polling time
in
step 360), then polling of the low-priority MAC Users in step 340 during the
next
polling cycle begins with the next low-priority MAC User in the list following
the last
low-priority MAC User polled. As a result, the low-priority MAC Users may be
round-robin polled over a number of polling cycles.
The present invention may be embodied in other specific forms without
departing from the spirit or essential characteristics. The described
embodiments
are to be considered in all respects only as illustrative and not restrictive.
What is claimed is:
8
