Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Fast Fairness Scheduling for a Reservation-Based Media Access Control Protocol

IP.com Disclosure Number: IPCOM000105537D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 8 page(s) / 252K

Publishing Venue

IBM

Related People

van As, HR: AUTHOR [+3]

Abstract

Consider a ring or bus network with a slotted transmission structure where nodes gain access to reserved slots as result of a prior reservation procedure and to nonreserved slots by making a simple busy/free decision. The four states of a slot are distinguished by a reservation flag and a busy/free flag. References [1, 2] describe a Media Access Control (MAC) protocol for such a network whereby fairness scheduling is a central element in achieving the unique combination of high network throughput, node-individual throughput fairness, and tightly-bounded access delays.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 32% of the total text.

Fast Fairness Scheduling for a Reservation-Based Media Access Control Protocol

      Consider a ring or bus network with a slotted transmission
structure where nodes gain access to reserved slots as result of a
prior reservation procedure and to nonreserved slots by making a
simple busy/free decision.  The four states of a slot are
distinguished by a reservation flag and a busy/free flag.  References
[1, 2] describe a Media Access Control (MAC) protocol for such a
network whereby fairness scheduling is a central element in achieving
the unique combination of high network throughput, node-individual
throughput fairness, and tightly-bounded access delays.

      To obtain throughput fairness, each node keeps track of its
number of slot transmissions by a transmit counter.  A RESERVE
command, which is cyclically issued by the scheduler, collects the
transmit counts of all active nodes together with their request count
(specifying future demand).  Upon return, the scheduler uses these
two parameters from each node to determine a fairness threshold.  All
nodes being below the threshold obtain confirmations for reserved
slots whereas all nodes exceeding the threshold are forced to defer
access to nonreserved slots accordingly before continuing further
transmissions.  To achieve that nodes experience a minimal degree of
control, the threshold is determined such that the sum of all slots
to be reserved and all slots to be deferred becomes minimal.  This
criterion achieves maximum network throughput in the next scheduling
cycle while guaranteeing throughput fairness to individual nodes.  By
returning the threshold in a CONFIRM command, each node is able to
derive the number of confirmations for reserved slots or the number
of nonreserved slots to be deferred.  In addition, a node updates its
transmit counter by subtracting the threshold value.  Marking of
slots as reserved is done by the scheduler whereby a reservation is
for only one transmission access.  When a slot is freed by the
destination, subsequent access to that slot is nonreserved, until the
next marking takes place.

      Fig. 1 shows a scheduling example for four nodes (A to D)
requesting slots (REQ-count) and reporting on slots transmitted
(TX-count).  For each possible fairness threshold, the number of
resulting confirmations and deferments is indicated at the right-side
of the left diagram.  The sum of these two numbers as a function of
the threshold value is shown in the diagram at the right.  The best
threshold resulting in a minimal control impact on the network
operation is at level three with one confirmation and four
deferments.  In general, suboptima may exist so that minimum
searching must cover all optima.

      An efficient algorithm to determine the optimum threshold is
given in Fig. 2.  Each of the node entries is represented by two
columns TX and SUM (being the transmit count and the sum of transmit
and request counts, respectively).  TX...