INTERNET-DRAFT EXPIRES DECEMBER 1997 INTERNET-DRAFT
Network Working Group John Hickey
Internet-Draft 3Com Corporation
Category: Informational June 1997
PACE(TM) Technology's Ethernet Interactive Access Algorithm
<draft-rfced-info-hickey-00.txt>
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."
To learn the current status of any Internet-Draft, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
1. Introduction
PACE technology is designed to provide backwards-compatible
modifications to Ethernet to support multimedia applications. PACE
Technology's Ethernet Interactive Access [1] uses a modified 802.3 MAC
access algorithm to minimise access latency when communicating to
standard 802.3 MAC devices. This access algorithm is documented here
via pseudo code in a manner similar to the 802.3 MAC standard.
While Ethernet [2] is the most commonly deployed LAN technology, it
has some shortcomings for real-time multimedia application support. In
particular, due to the "capture effect", it performs poorly in support
of audio/video traffic in the presence of bursty data traffic [3].
The primary issues for multimedia network support are overall network
jitter and latency. These can be combined into a joint parameter known
as access latency. Access latency is defined as the maximum time that a
port will take to either successfully transmit a packet or discard it
measured from the time the packet is presented to the MAC for
transmission. To allow multimedia applications to run over Ethernet the
overall access latency for a packet needs to be bounded. Typical
figures mooted for multimedia applications have this access latency
specified in the 5ms to 10ms region.
June 23, 1997
- 2 -
This document describes in detail PACE technology's Interactive
Access which addresses this problem. The Interactive Access algorithm
is designed to optimise a point-to-point link between a PACE Technology
port and a standard 802.3 port. The second part of PACE technology is
the implicit Class of Service (CoS)[4]. PACE CoS allows delay sensitive
traffic to be given higher priority as compare to other traffic. The
CoS is not discussed in this document.
2. Interactive Access Mode
PACE technology's optimised access algorithm provides guaranteed
bounded low access latency for a port. This is known as PACE
Technology's Interactive Access mode. The Interactive Access algorithm
Hickey [Page 1]
I/D PACE Technology Interactive Access Algorithm June 1997
is designed to optimise a point-to-point link between a PACE Technology
port and a standard 802.3 port.
For "regular" Ethernet this access latency can be in the
order of seconds (i.e., maximum backoff time for 16 collisions plus
time deferring to others using network). Packets with access latency
in the order of 300ms can often be seen on regular Ethernet.
The main source of access latency for a port is the unpredictable
transmission of packets by other ports. This shows up as random
collisions and deference to packets being received. To provide a bound
on these access latency the PACE Technology's Interactive Access
protocol was developed. This protocol assumes it is operating on a
point-to-point link with a normal 802.3 end-station. The performance
with an end-station using the PACE Technology's interactive protocol
would be much higher but is not discussed here.
This section first gives a high level description of the algorithm
with its performance bounds, the second part details the changes
needed to make a 802.3 MAC into a MAC with PACE Technology. The pseudo
code for an 802.3 MAC can be found in [2]. The pseudo code for
procedures that need to be modified for PACE Technology are presented
with descriptions of the changes.
2.1 Interactive Access Mode
Interactive Access is a mode of operation where traffic is ordered by
a node with PACE Technology. The PACE Technology MAC keeps track of
whether it was the last port to transmit successfully or not. When it
has received a packet last, the MAC moves into "Trying to Transmit"
state where it will attempt to transmit a packet at the end of the
normal Ethernet IPG (does not care about state of carrier sense) if it
has a packet to send. If a collision occurs during this transmission,
it retries transmission again at the end of another IPG (i.e. backoff
June 23, 1997
- 3 -
time is forced to zero in this state ).
The way the MAC operates in "Trying to Transmit" state is that it
re-tries transmission with 0 backoff time (i. e. starts re-transmission
after IPG expired) every time up to (attemptLimit - 1) collisions have
been encountered. The MAC attempts transmission one last time after
waiting half a slot-time if carrier sense is not detected. If carrier
sense is detected at this time no attempt will be made to transmit the
packet but excessiveCollisionError will be asserted (basically the
packet will be discarded). The reason for performing the last attempt
in this manner is to guarantee that no collision will occur(thus ensure
access latency is not increased) while increasing the probability of
successfully transmitting the packet. After either transmitting a
packet or discarding after reaching attemptLimit, the MAC moves into
"Waiting to Receive" state.
In "Waiting to Receive" state the MAC allows the other port to have a
chance to transmit a packet if it has one to send. The time waited is
Hickey [Page 2]
PACE Technology Interactive Access Algorithm June 1997
directly related to the number of collisions we encountered in the
previous transmission. Every collision forced the other port to select
a backoff value from a wider range based on the 802.3 truncated
exponential backoff algorithm [2]. The time we wait is specified by :
Max. Defer Time = netDelayLimit, for rxAllocateEnld=1,attempts=1;
2n * 51. 2us, for rxAllocateEnld=1,attempts>1;
0, for rxAllocateEnld=0;
where n = no. of attempts
rxAllocateEnld is set when a collision is detected and is cleared
when the dead-timer expires in "Waiting to Receive" state and no
packet has been received. Thus we minimise the dead-time on the
media when no contention for it is detected.
netDelayLimit is a value between 256BTs-512BTs which is used to
minimise the wait after the transmission of a packet that had no
collisions but node has rxAllocateEnld set. Used to minimise the
wait for the other node to send a packet (which should be sent
after 96bts if other node has packet pending)when it has nothing to
send.
Thus if the previous "Trying to Transmit" state experienced no
collisions (attempts=1) then we have no extended defer time(known also
as the rxAllocate time ) and will attempt to transmit a packet after the
IPG has expired if the port has another to send. If there was
collisions in the previous "Trying to Transmit" state an extended
deference is used to guarantee that the other port will send us the
packet it was trying to transmit during our transmit state.
June 23, 1997
- 4 -
If the dead-timer expires in the "Waiting to Receive" state or if a
packet is received, the MAC moves back into "Trying to Transmit" state.
If the MAC exits the "Waiting to Receive" state without receiving a
packet the MAC stays in "Trying to Transmit" state until a collision is
seen and transmits packets with a min. IPG of 96BTs (or can be said to
stay 0 time in "Waiting to Receive" state).
The Table 1 below defines the maximum access latency and the
statistical packet loss rate as a function of the attemptLimit. The
latency is computed by adding in the worst case collision overhead while
in "Trying to Transmit" state and the worst case backoff of the 802.3
node while in "Wait to Receive" state and the max. packet length. The
packet loss rate (PLR) is computed by calculating the probability of
reaching attemptLimit in "Trying to Transmit" state (i.e., probability
of 802.3 node picking 0 as backoff attemptLimit times in a row ).
A typical maximum attempt of 7 for multimedia applications would give
an access latency of around 4.8ms and a max. packet loss rate of 0.24e-6
(i.e., 1 packet in over 4 million dropped). The bit error rate (BER) is
specified at no worse than 1 in 108 for 10BaseT. For minimum size
packets this is would give about 1 packet in 173,600 being discarded due
to CRC errors. For maximum size packets this would give about 1 packet
Hickey [Page 3]
PACE Technology Interactive Access Algorithm June 1997
in 8,500 being discarded due to CRC errors. Thus packet loss for a max.
of seven attempts in this mode is more than an order of magnitude less
than BER worst-case (i.e., sending all minimum size packets).
Table 1: PACE Technology's Interactive Access Mode Latency and PLR
bounds
Max. Attempt Max. Access Latency Packet Loss Rate
6 3.23 ms 0.002 E-3
7 4.83 ms 0.24 E-6
8 8.17 ms 1.86 E-9
9 14.80 ms 7.28 E-12
10 28.00 ms 1.42 E-14
11 54.24 ms 1.39 E-17
12 54.30 ms 6.78 E-21
13 54.37 ms 1.65 E-24
To use two node in PACE Technology's interactive mode on the same
point-to-point link each must have their attemptLimit set to different
values to ensure that one wins on the first collision window. The loser
will discard this first packet. After this a contention for the media
(i. e. collision ) will be resolved without further contention as each
device is monitoring the user of the media. In this mode only one
collision is needed to swap a burst of packets.
June 23, 1997
- 5 -
2.2 MAC with PACE Technology
[Refer to section 4 of [2] for pseudo code on which following
description is based on ].
New variables called paceEnld, txLast, lastAttempt, received and
rxAllocate are defined. The paceEnld variable is used to define
whether the MAC is operating in multimedia Ethernet mode or in standard
802.3 mode. The txLast variable indicates whether the last completed
operation was a transmission of a packet or not. A transmission
includes the successful sending of a packet on the network or the
discarding of the packet due to excessive collisions. The lastAttempt
variable is used to wait half a slot time before checking if activity on
the network on final attempt to transmit. If no activity packet is
transmitted, if activity packet is discard. The received variable is
used to indicate that a packet has been received from the other node.
It is set in the Deference process and cleared in the TransmitLinkMgmt
process during IPG time. The rxAllocate variable is used to minimise
the dead-time after a transmission when no contention for the network is
detected. When rxAllocate is set a defined delay expires before another
transmission can start (independent of IPG), when cleared this delay is
reduced to zero thus back-to-back frames can be transmitted with minimum
IPG. They are defined as follows :
var
paceEnld : Boolean;
txLast : Boolean;
Hickey [Page 4]
PACE Technology Interactive Access Algorithm June 1997
lastAttempt : Boolean;
rxAllocate : Boolean;
received : Boolean;
maxAttempt : Boolean;
Three of the new variables are initialised inside the 802.3 standard
procedure Initialize as follows:
paceEnld = {user-defined. }
txLast = false;
rxAllocate = false;
received = false;
maxAttempt = false;
Two constants are also defined. They are attemptLimit and
netDelayTime. attemptLimit is defined the same way as in 802.3 but can
be set from 1 to 16. It defines the number of times the
TransmitLinkMgmt process will attempt to transmit a packet before
discarding it as an excessive collision error. This variable can be set
from 1 to 16. Typical values would be 7 or 8 for low latency access.
June 23, 1997
- 6 -
netDelayTime is used to "extend" the IPG after a transmission if no
collision has occurred during the last transmission but rxAllocate is
enabled. It is used to give the other station a chance to transmit if
it has a packet to send. It can be set from 0 to 1 slot-time. This
value should be tuned to match the round-trip delay between the two
end-stations. A value of 256 to 512 Bit-Times would be typical.
const
attemptLimit = { user-defined - 1-16 }
netDelayTime = { user-defined - expressed in Bit-Times;
0-512bts }
2.2.1 TransmitLinkMgmt Process
The pseudo code for a new TransmitLinkMgmt process for standard 802. 3
and Ethernet with PACE-IA is shown below :
function TransmitLinkMgmt: TransmitStatus;
begin
attempts := 0; transmitSucceeding := false;
lastAttempt := false;
lateCollisionCount := 0;
deferred := false; {initialize}
excessDefer := false;
while (attempts < attemptLimit) and (not transmitSucceeding) do
begin {loop}
if attempts > 0 then
{ rxAllocate := paceEnld; { Had collision so enable
rxAllocate timer }
BackOff;
}
Hickey [Page 5]
PACE Technology Interactive Access Algorithm June 1997
/* Skip transmission attempt on lastAttempt in Pace-IA mode */
/* if activity detected on network. */
if not ( paceEnld and lastAttempt and carrierSense )
{
if received then
{ txLast := false; { accounts for any packets
received between transmit packets }
maxAttempt := false;
}
frameWaiting := true;
lateCollisionError := false;
while deferring do {defer to passing frame, if any }
begin
deferred := true;
if received then
June 23, 1997
- 7 -
{ txLast = false;
maxAttempt := false;
}
end;
frameWaiting := false;
StartTransmit;
while transmitting do WatchForCollision;
if lateCollisionError then
lateCollisionCount := lateCollisionCount + 1;
}
attempts := attempts + 1;
if (attempts == (attemptLimit - 1) ) then
lastAttempt := true
else
lastAttempt := false;
end; {loop}
if transmitSucceeding then
{ TransmitLinkMgmt := transmitOk;
txLast := true; {completed a transmission)
}
else TransmitLinkMgmt := excessiveCollisionError;
LayerMgmtTransmitCounters;
received := false; { clear here in the IPG as just
"transmitted" }
if (rxAllocate) then
begin
BackOff; { allow other node to transmit }
if ( not carrierSense ) then
rxAllocate := false; { timer expired and no packet
received }
end
end; {TransmitLinkMgmt}
2.2.2 BackOff Procedure
The pseudo code for a new BackOff procedure for standard 802. 3 and
PACE-IA Ethernet access is shown below :
Hickey [Page 6]
PACE Technology Interactive Access Algorithm June 1997
var maxBackOff: 2 .. 1024; {working variable of BackOff}
var backOffDelay;
procedure BackOff;
begin
if (paceEnld) { PACE mode backoff }
{ if (txLast and rxAllocate ) then {Receive wait timer
setting}
{ if ( ( attempts == 1 ) & transmitSucceeding ) then
backOffDelay := netDelayTime;
June 23, 1997
- 8 -
else if ( attempts <= backOffLimit ) then
backOffDelay := 2 ^ (attempts) * slotTime;
else
backOffDelay := 1024 * slotTime
else if ( lastAttempt ) then
{ backOffDelay := slotTime/2; {first time
lastAttempt reached }
if ( maxAttempt ) then {back-back packets
reached lastAttempt }
{introduce some randomness to help break
lockup of two PACE Technology nodes}
{random backoff range can also be based on
multiples of IPG}
backOffDelay :=
backOffDelay * Random(1, attempts);
else
maxAttempt := true;
}
else
backOffDelay := 0;
while ( Wait(backOffDelay) and ( not carrierSense ) )
do nothing
}
else {standard 802.3 mode }
{ if attempts = 1 then
maxBackOff := 2
else if attempts <= backOffLimit then
maxBackOff := maxBackOff x 2;
Wait( slotTime * Random( 0, maxBackOff ) )
}
end BackOff;
2.2.3 Deference Process
The pseudo code for the Deference process for standard 802.3 and
Multimedia Ethernet is shown below.
Hickey [Page 7]
PACE Technology Interactive Access Algorithm June 1997
process Deference;
begin
cycle {main loop}
while not carrierSense do nothing; {watch for carrier to appear}
deferring := true; {delay start of new transmission}
June 23, 1997
- 9 -
wasTransmitting := transmitting;
while ( carrierSense or transmitting )
wasTransmitting := wasTransmitting or transmitting;
received := not wasTransmitting; {received a packet}
if wasTransmitting then
Wait(interFrameSpacing1)
else
{ while carrierSense do nothing;
Wait(interFrameSpacing1)
}
Wait(interFrameSpacing2);
deferring := false; {allow new transmissions to proceed}
while frameWaiting do nothing; {allow waiting transmission
if any}
end {main loop}
end; {Deference}
2.2.4 Parameterized Values :
The following parameter values shall be used for PACE Technology's
Interactive Access implementations :
Parameter Name Minimum Maximum
attemptLimit 6 13
netDelayTime 256 BTs 512 BTs
3. References
[1] P. Sherer, L. C. Lo and J. Hickey, "Method and Apparatus for
Controlling Latency and Jitter in a Local Area Network Which Uses a
CSMA/CD Protocol," United States Patent 5,568,469.
[2] ISO/IEC 8802-3: 1993 [ANSI/IEEE Std. 802. 3, 1993],Information
technology - Local and metropolitan area networks - Part 3 :Carrier
sense multiple access with collision detection (CSMA/CD)access method
and physical layer specifications.
Hickey [Page 8]
PACE Technology Interactive Access Algorithm June 1997
June 23, 1997
- 10 -
[3] Chlamtac and M. Eisinger, "Performance of Integrated Services
(Voice/Data) on CSMA/CD Networks", Proceedings of ACM Sigmetrics'85,
pp. 87-93, August 1985.
[4] P. Wang, "Class-of-Service Implementation for PACE Technology",
January, 1997
4. Security Consideration
This document raises no security issues.
5. Author's Address
John Hickey,
3Com Corp.,
Ballycoolin Business Park,
Blanchardstown,
Dublin 15,
Ireland.
Phone : 353-1-8035711
EMail : John_Hickey@3Mail.3Com.com
INTERNET-DRAFT EXPIRES DECEMBER 1997 INTERNET-DRAFT
June 23, 1997