Small, Fast Available Contention Slot Selector

Small, Fast Available Contention Slot Selector

      For high-speed home Internet access using existing cable
Television (TV) networks, the local cable company will provide a
connection between the Internet and their cable TV network using a
device called a "Headend" unit.  Customers will connect their home
Personal Computers (PCs) to the cable TV system using a relatively
inexpensive "Subscriber" unit (or cable modem).  Since there will be
many more Subscribers than Headends, the Subscriber design is
extremely cost-sensitive.

      The protocol for data transfer over this system consisting of
Headend, cable TV network, and the Subscriber is defined in the IEEE
802.14 standard and is called MLAP (MAC Level Access Protocol).  The
Headend maintains synchronization with approximately 500 Subscribers
by sending a specific data pattern known as DS.SYNC every so many
milliseconds.  The time between DS.SYNC signals is known as a Block.
The Subscribers set their clocks by the DS.SYNC signal and use it to
synchronize their data transmissions back to the Headend.  Data
flowing from the Headend to a Subscriber is said to be going
"downstream", and  data sent from a Subscriber to the Headend is said
to be going "upstream".  An upstream Block is divided into a fixed
number of Slots,  each of which may contain a message from a
Subscriber to the Headend.  The Headend controls which Subscribers
are allowed to transmit  a message in a given Slot.  These messages
are mostly data packets to be forwarded to the Internet, but they may
also contain requests by the  Subscribers for the Headend to reserve
Slots in the next upstream Block  for their use.  After the Headend
receives the Subscribers' requests, it  decides which ones will be
allowed to transmit on the next upstream Block  and notifies them via
downstream messages.  The number of Slots in an upstream Block is
typically much smaller than the number of Subscribers,  so the
Headend designates some of the Slots as "Contention Slots" in which
several Subscribers can attempt to transmit.  If more than one
Subscriber transmits a message in the same Slot, a "collision"
occurs; meaning none of the messages got through and the Headend
tells those Subscribers to resend their messages.

      To reduce the probability of collisions, each Subscriber
randomly selects one Contention Slot in which to transmit its message
to the Headend, hoping that other Subscribers will not pick that Slot
as well.  This selection process requires two steps.  First,
throughout a given downstream Block, the Headend sends messages to
all Subscribers  indicating which Slots in the next upstream Block
will be Contention Slots.  As a subscriber receives these messages,
it builds one or more  Lists which it uses to keep track of available
Contention Slots. These  Lists are built by a Contention Resolution
Algorithm which can be implemented in software since the Block time
is relatively long. Once  the d...