Browse Prior Art Database

Local Fairness Algorithm for Full-Duplex Buffer Insertion Ring

IP.com Disclosure Number: IPCOM000100949D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 7 page(s) / 203K

Publishing Venue

IBM

Related People

Cidon, I: AUTHOR [+2]

Abstract

This invention describes a local fairness algorithm over a full-duplex buffer insertion ring. Buffer insertion is a distributed and asynchronous technique for accessing a ring network and is suitable for fixed- and variable-size packets. In this scheme, a node can transmit a packet only if its insertion buffer is empty.

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

Local Fairness Algorithm for Full-Duplex Buffer Insertion Ring

       This invention describes a local fairness algorithm over
a full-duplex buffer insertion ring.  Buffer insertion is a
distributed and asynchronous technique for accessing a ring network
and is suitable for fixed- and variable-size packets.  In this
scheme, a node can transmit a packet only if its insertion buffer is
empty.

      The hardware control messages are used for exchange of state
information between neighboring nodes.  These messages can be used
for source fairness, back pressure and overflow prevention, and have
the following characteristics:
o    Very short - few characters (possibly one).
o    Preemptive priority - can be sent in the middle of a data
packet.
o    Non-distructive - does not damage the data packets which they
preempt.
o    Delay - virtually only the link propagation delay (no queueing
delay).
o    Independent hardware - used for the ring control mechanism.
      The global fairness algorithm has two basic drawbacks:
1.   It is GLOBAL (among all n nodes).
2.   It is CONTINUOUS (operates even if there is no starvation).

      The first drawback, being global, is demonstrated in Fig. 1.
In this example there are 3 independent subsets of users that
communicate only among themselves.  A reasonable approach is to
provide fairness within each subset while maintaining the maximal
achievable throughput in each of the subsets.  A global fairness
algorithm will force all groups to maintain fairness (the same
maximal throughput) among themselves, even if they do not interfere
at all.

      The second drawback, being continuous, means that the fairness
algorithm is operational even if no node starves. This may result in
some unnecessary performance degradation if the fairness parameters
are not set properly.  This problem is considerably less important.

      These drawbacks motivate the development of an event-driven
fairness algorithm that will be initiated only when starvation
occurs.  In addition, the algorithm should only involve segments of
interfering nodes.  In the above example of Fig. 1, the local
algorithm will be executed independently among the three nodes'
subsets with no interference or message exchange.  Note that under
worst-case load scenarios the local fairness algorithm can
"degenerate" to global fairness.

      Informal Description The local fairness algorithm distinguishes
between two basic nodal modes classes:
o    Non-restricted buffer insertion mode.
o    Restricted buffer insertion modes (the deferent modes of this
class will be later described).
The algorithm uses two types of control messages: o    REQ(i) - sent
by node i when it is starved. o    SAT - sent when the node is
satisfied after being starved.

      Fig. 2 demonstrate the basic operation of the algorithm.  A
starved node i triggers the operation by sending the request REQ(i)
up-stream and is...