Browse Prior Art Database

Starvation-Free Access Protocol for a Full-Duplex Buffer Insertion Ring Local Area Network

IP.com Disclosure Number: IPCOM000100523D
Original Publication Date: 1990-May-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 4 page(s) / 157K

Publishing Venue

IBM

Related People

Ofek, Y: AUTHOR [+2]

Abstract

This invention presents a media-access protocol for a full-duplex buffer insertion ring that prevents starvation. The protocol is stable and provides a minimum guaranteed throughput. The protocol has several attractive properties: it is decentralized, uses only local information and makes efficient use of the architecture. Furthermore, the protocol operates during certain types of failures, continuing to provide fair access to the medium.

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

Starvation-Free Access Protocol for a Full-Duplex Buffer Insertion Ring Local Area Network

       This invention presents a media-access protocol for a
full-duplex buffer insertion ring that prevents starvation. The
protocol is stable and provides a minimum guaranteed throughput.  The
protocol has several attractive properties: it is decentralized, uses
only local information and makes efficient use of the architecture.
Furthermore, the protocol operates during certain types of failures,
continuing to provide fair access to the medium.

      The nodes are connected by full-duplex links and thus,
logically, we say that there are two independent rings and every node
has a transmitter-receiver pair in each of the two rings.  The two
rings, which we call the I-ring (or Inner ring) and the O-ring (or
Outer ring) for simplicity, carry messages in opposite directions.

      In order to present the criterion by which starvation is
determined as well as the access protocol, we introduce some
definitions and notation.  Since the operation of the two rings, the
I-ring and the O-ring, are identical, for simplicity the description
that follows pertains to only one ring (the I-ring, for example).  We
distinguish between the following two terms:
 o   Transmit.  We say that a node transmits a message if the node
either transmits a message originating at the node or transmits onto
the ring a message from upstream that is present in its buffer.
 o   Insert.  We say that a node inserts into the ring when a message
locally originating at the node is at the head of the queue, finds
the insertion buffer empty and is able to transmit onto the ring
successfully.

      Next, let
 n     =  the number of nodes in the system.
 w(k)i    =    the number of upstream messages that the kth message
(arriving to the head of the queue) at node i must wait for, without
being able to transmit.
 t(k)i    =    the time of arrival of the kth message to the head of
the queue at node i.
 T(k)i  (m)  = the time at which m upstream messages (and no local
messages) are transmitted from node i after t(k)i , i.e., after the
arrival of the kth message to the head of the queue at node i.
 t(k)i  (m) = the time at which m messages (both upstream or local)
are transmitted from i after T(k)i  (n). Next we define a cycle:
 o  Cycle. A cycle is the period between the pairs t(k)i (ln) and
t(k)i  (l+1)n) for each n and l = 1,2,3,...etc.
Finally, let
 I(k)i  (l) = the number of inserts that node i makes in the cycle
delimited by t(k)i   (ln) and ((l + 1)n)..

      We define two nodal states: normal and starved with transitions
taking place between these two states as follows:
 o  normalTstarved:  when w(k)i   = n for any k, i.e., when a message
is made to wait for at least n upstream messages to go by.  Thus, a
node is declared starved when there is a message at the head of its
transmit queue and the insertion buffer succes...