HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 11:06:45 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Tue, 17 Mar 1998 16:30:00 GMT ETag: "361fa7-5593-350ea508" Accept-Ranges: bytes Content-Length: 21907 Connection: close Content-Type: text/plain 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 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