Browse Prior Art Database

Overflow Prevention for Full-duplex Buffer Insertion Ring With Fairness

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

Publishing Venue

IBM

Related People

Cidon, I: AUTHOR [+2]

Abstract

This article describes two algorithms to prevent overflow of the insertion buffer of a full-duplex buffer insertion ring. One mechanism uses safety margins between packets, and the other uses the global fairness mechanism to prevent the overflow.

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

Overflow Prevention for Full-duplex Buffer Insertion Ring With Fairness

       This article describes two algorithms to prevent overflow
of the insertion buffer of a full-duplex buffer insertion ring. One
mechanism uses safety margins between packets, and the other uses the
global fairness mechanism to prevent the overflow.

      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 access on each direction of the ring is regulated by a
control message, SAT, which circulates in the opposite direction to
the data traffic it is regulating.  The access is completely fair
(all nodes have equal opportunity), while maintaining most of the
potential spatial reuse in the full-duplex buffer insertion ring.

      The figure shows the basic SAT mechanism for one direction of
the ring.  In this case the data is transferred down-stream, and the
SAT message is transferred up-stream.

      In principle, the node will forward the SAT message up-stream
with no delay, unless it is "starved." By "starved," we mean that the
node could not send the permitted number of messages since the last
time it has forwarded the SAT message.

      Timing Constraints and Overflow Prevention In this section we
show what are the safety margins needed in order to avoid overflow
(while receiving a packet) of the insertion buffer.

      The source for these problems is that the high speed serial
transmission clocks are not identical.  Let the rates of the n local
clocks be represented by {c1, c2, ..., cn}. We assume

                            (Image Omitted)

 that the manufacturer's specification
guarantees that any ci is bounded below by cnominalmin     (the
l...