home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_n_r / draft-rfced-info-hickey-00.txt < prev    next >
Text File  |  1997-06-24  |  22KB  |  660 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6. INTERNET-DRAFT               EXPIRES DECEMBER 1997      INTERNET-DRAFT
  7.  
  8. Network Working Group                                        John Hickey
  9. Internet-Draft                                          3Com Corporation
  10. Category: Informational                                        June 1997
  11.  
  12.  
  13.       PACE(TM) Technology's Ethernet Interactive Access Algorithm
  14.        <draft-rfced-info-hickey-00.txt>
  15.  
  16.  
  17. Status of this Memo
  18.  
  19. This document is an Internet-Draft. Internet-Drafts are working
  20. documents of the Internet Engineering Task Force (IETF), its areas,
  21. and its working groups. Note that other groups may also distribute
  22. working documents as Internet-Drafts.
  23.  
  24. Internet-Drafts are draft documents valid for a maximum of six months
  25. and may be updated, replaced, or obsoleted by other documents at any
  26. time. It is inappropriate to use Internet-Drafts as reference material
  27. or to cite them other than as "work in progress."
  28.  
  29. To learn the current status of any Internet-Draft, please check the
  30. "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
  31. Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
  32. munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
  33. ftp.isi.edu (US West Coast).
  34.  
  35.  
  36.  
  37. 1.   Introduction
  38.  
  39.    PACE technology is designed to provide backwards-compatible
  40. modifications to Ethernet to support multimedia applications.  PACE
  41. Technology's Ethernet Interactive Access [1] uses a modified 802.3 MAC
  42. access algorithm to minimise access latency when communicating to
  43. standard 802.3 MAC devices.  This access algorithm is documented here
  44. via pseudo code in a manner similar to the 802.3 MAC standard.
  45.  
  46.    While Ethernet [2] is the most commonly deployed LAN technology, it
  47. has some shortcomings for real-time multimedia application support.  In
  48. particular, due to the "capture effect", it performs poorly in support
  49. of audio/video traffic in the presence of bursty data traffic [3].
  50.  
  51.    The primary issues for multimedia network support are overall network
  52. jitter and latency.  These can be combined into a joint parameter known
  53. as access latency.  Access latency is defined as the maximum time that a
  54. port will take to either successfully transmit a packet or discard it
  55. measured from the time the packet is presented to the MAC for
  56. transmission.  To allow multimedia applications to run over Ethernet the
  57. overall access latency for a packet needs to be bounded.  Typical
  58. figures mooted for multimedia applications have this access latency
  59. specified in the 5ms to 10ms region.
  60.  
  61.  
  62.  
  63.                        June 23, 1997
  64.  
  65.  
  66.  
  67.  
  68.  
  69.                            - 2 -
  70.  
  71.  
  72.    This document describes in detail PACE technology's Interactive
  73. Access which addresses this problem.  The Interactive Access algorithm
  74. is designed to optimise a point-to-point link between a PACE Technology
  75. port and a standard 802.3 port.  The second part of PACE technology is
  76. the implicit Class of Service (CoS)[4].  PACE CoS allows delay sensitive
  77. traffic to be given higher priority as compare to other traffic.  The
  78. CoS is not discussed in this document.
  79.  
  80. 2.   Interactive Access Mode
  81.  
  82.    PACE technology's optimised access algorithm provides guaranteed
  83. bounded low access latency for a port.  This is known as PACE
  84. Technology's Interactive Access mode.  The Interactive Access algorithm
  85.  
  86.  
  87. Hickey                                                          [Page 1]
  88.  
  89.  I/D       PACE Technology Interactive Access Algorithm  June     1997
  90.  
  91.  
  92. is designed to optimise a point-to-point link between a PACE Technology
  93. port and a standard 802.3 port.
  94.  
  95.    For "regular" Ethernet this access latency can be in the
  96. order of seconds (i.e., maximum backoff time for 16 collisions plus
  97. time deferring to others using network).  Packets with access latency
  98. in the order of 300ms can often be seen on regular Ethernet.
  99.  
  100.    The main source of access latency for a port is the unpredictable
  101. transmission of packets by other ports.  This shows up as random
  102. collisions and deference to packets being received.  To provide a bound
  103. on these access latency the PACE Technology's Interactive Access
  104. protocol was developed.  This protocol assumes it is operating on a
  105. point-to-point link with a normal 802.3 end-station.  The performance
  106. with an end-station using the PACE Technology's interactive protocol
  107. would be much higher but is not discussed here.
  108.  
  109.    This section first gives a high level description of the algorithm
  110. with its performance bounds, the second part details the changes
  111. needed to make a 802.3 MAC into a MAC with PACE Technology.  The pseudo
  112. code for an 802.3 MAC can be found in [2].  The pseudo code for
  113. procedures that need to be modified for PACE Technology are presented
  114. with descriptions of the changes.
  115.  
  116. 2.1   Interactive Access Mode
  117.  
  118.    Interactive Access is a mode of operation where traffic is ordered by
  119. a node with PACE Technology.  The PACE Technology MAC keeps track of
  120. whether it was the last port to transmit successfully or not.  When it
  121. has received a packet last, the MAC moves into "Trying to Transmit"
  122. state where it will attempt to transmit a packet at the end of the
  123. normal Ethernet IPG (does not care about  state of carrier sense) if it
  124. has a packet to send.  If a collision occurs during this transmission,
  125. it retries transmission again at the end of another IPG (i.e.  backoff
  126.  
  127.  
  128.  
  129.                        June 23, 1997
  130.  
  131.  
  132.  
  133.  
  134.  
  135.                            - 3 -
  136.  
  137.  
  138. time is forced to zero in this state ).
  139.  
  140.    The way the MAC operates in "Trying to Transmit" state is that it
  141. re-tries transmission with 0 backoff time (i. e.  starts re-transmission
  142. after IPG expired) every time up to (attemptLimit - 1) collisions have
  143. been encountered.  The MAC attempts transmission one last time after
  144. waiting half a slot-time if carrier sense is not detected.  If carrier
  145. sense is detected at this time no attempt will be made to transmit the
  146. packet but excessiveCollisionError will be asserted (basically the
  147. packet will be discarded).  The reason for performing the last attempt
  148. in this manner is to guarantee that no collision will occur(thus ensure
  149. access latency is not increased) while increasing the probability of
  150. successfully transmitting the packet.  After either transmitting a
  151. packet or discarding after reaching attemptLimit, the MAC moves into
  152. "Waiting to Receive" state.
  153.  
  154.    In "Waiting to Receive" state the MAC allows the other port to have a
  155. chance to transmit a packet if it has one to send.  The time waited is
  156.  
  157.  
  158. Hickey                                                          [Page 2]
  159.  
  160.            PACE Technology Interactive Access Algorithm  June     1997
  161.  
  162.  
  163. directly related to the number of collisions we encountered in the
  164. previous transmission.  Every collision forced the other port to select
  165. a backoff value from a wider range based on the 802.3 truncated
  166. exponential backoff algorithm [2].   The time we wait is specified by :
  167.  
  168.      Max. Defer Time = netDelayLimit,  for rxAllocateEnld=1,attempts=1;
  169.                        2n * 51. 2us,   for rxAllocateEnld=1,attempts>1;
  170.                        0,              for rxAllocateEnld=0;
  171.      where n = no.  of  attempts
  172.  
  173.      rxAllocateEnld is set when a collision is detected and is cleared
  174.      when the dead-timer expires in "Waiting to Receive" state and no
  175.      packet has been received.  Thus we minimise the dead-time on the
  176.      media when no contention for it is detected.
  177.  
  178.      netDelayLimit is a value between 256BTs-512BTs which is used to
  179.      minimise the wait after the transmission of a packet that had no
  180.      collisions but node has rxAllocateEnld set.  Used to minimise the
  181.      wait for the other node to send a packet (which should be sent
  182.      after 96bts if other node has packet pending)when it has nothing to
  183.      send.
  184.  
  185.    Thus if the previous "Trying to Transmit" state experienced no
  186. collisions (attempts=1) then we have no extended defer time(known also
  187. as the rxAllocate time ) and will attempt to transmit a packet after the
  188. IPG has expired if the port has another to send.  If there was
  189. collisions in the previous "Trying to Transmit" state an extended
  190. deference is used to guarantee that the other port will send us the
  191. packet it was trying to transmit during our transmit state.
  192.  
  193.  
  194.  
  195.                        June 23, 1997
  196.  
  197.  
  198.  
  199.  
  200.  
  201.                            - 4 -
  202.  
  203.  
  204.    If the dead-timer expires in the "Waiting to Receive" state or if a
  205. packet is received, the MAC moves back into "Trying to Transmit" state.
  206. If the MAC exits the "Waiting to Receive" state without receiving a
  207. packet the MAC stays in "Trying to Transmit" state until a collision is
  208. seen and transmits packets with a min. IPG of 96BTs (or can be said to
  209. stay 0 time in "Waiting to Receive" state).
  210.  
  211.    The Table 1  below defines the maximum access latency and the
  212. statistical packet loss rate as a function of the attemptLimit.  The
  213. latency is computed by adding in the worst case collision overhead while
  214. in "Trying to Transmit" state and the worst case backoff of the 802.3
  215. node while in "Wait to Receive" state and the max. packet length.  The
  216. packet loss rate (PLR) is computed by calculating the probability of
  217. reaching attemptLimit in "Trying to Transmit" state (i.e., probability
  218. of 802.3 node picking 0 as backoff attemptLimit times in a row ).
  219.  
  220.    A typical maximum attempt of 7 for multimedia applications would give
  221. an access latency of around 4.8ms and a max. packet loss rate of 0.24e-6
  222. (i.e., 1 packet in over 4 million dropped). The bit error rate (BER) is
  223. specified at no worse than 1 in 108 for 10BaseT.  For minimum size
  224. packets this is would give about 1 packet in 173,600 being discarded due
  225. to CRC errors.  For maximum size packets this would give about 1 packet
  226.  
  227.  
  228. Hickey                                                          [Page 3]
  229.  
  230.          PACE Technology Interactive Access Algorithm  June     1997
  231.  
  232.  
  233. in 8,500 being discarded due to CRC errors.  Thus packet loss for a max.
  234. of seven attempts in this mode is more than an order of magnitude less
  235. than BER worst-case (i.e., sending all minimum size packets).
  236.  
  237. Table 1: PACE Technology's Interactive Access Mode Latency and PLR
  238. bounds
  239.  
  240.    Max. Attempt          Max. Access Latency       Packet Loss Rate
  241.       6                     3.23 ms                0.002 E-3
  242.       7                     4.83 ms                0.24 E-6
  243.       8                     8.17 ms                1.86 E-9
  244.       9                    14.80 ms                7.28 E-12
  245.      10                    28.00 ms                1.42 E-14
  246.      11                    54.24 ms                1.39 E-17
  247.      12                    54.30 ms                6.78 E-21
  248.      13                    54.37 ms                1.65 E-24
  249.  
  250.    To use two node in PACE Technology's interactive mode on the same
  251. point-to-point link each must have their attemptLimit set to different
  252. values to ensure that one wins on the first collision window.  The loser
  253. will discard this first packet.  After this a contention for the media
  254. (i. e.  collision ) will be resolved without further contention as each
  255. device is monitoring the user of the media.  In this mode only one
  256. collision is needed to swap a burst of packets.
  257.  
  258.  
  259.  
  260.  
  261.                        June 23, 1997
  262.  
  263.  
  264.  
  265.  
  266.  
  267.                            - 5 -
  268.  
  269.  
  270. 2.2   MAC with PACE Technology
  271.  
  272. [Refer to section 4 of [2] for pseudo code on which following
  273. description is based on ].
  274.  
  275. New variables called paceEnld, txLast, lastAttempt, received and
  276. rxAllocate  are defined.  The paceEnld variable is used to define
  277. whether the MAC is operating in multimedia Ethernet mode or in standard
  278. 802.3 mode.  The txLast variable indicates whether the last completed
  279. operation was a transmission of a packet or not.  A transmission
  280. includes the successful sending of a packet on the network or the
  281. discarding of the packet due to excessive collisions.  The lastAttempt
  282. variable is used to wait half a slot time before checking if activity on
  283. the network on final attempt to transmit.  If no activity packet is
  284. transmitted, if activity packet is discard.  The received variable is
  285. used to indicate that a packet has been received from the other node.
  286. It is set in the Deference process and cleared in the TransmitLinkMgmt
  287. process during IPG time.  The rxAllocate variable is used to minimise
  288. the dead-time after a transmission when no contention for the network is
  289. detected.  When rxAllocate is set a defined delay expires before another
  290. transmission can start (independent of IPG), when cleared this delay is
  291. reduced to zero thus back-to-back frames can be transmitted with minimum
  292. IPG.  They are defined as follows :
  293.  
  294.    var
  295.      paceEnld     : Boolean;
  296.      txLast       : Boolean;
  297.  
  298.  
  299. Hickey                                                          [Page 4]
  300.  
  301.              PACE Technology Interactive Access Algorithm  June     1997
  302.  
  303.  
  304.      lastAttempt  : Boolean;
  305.      rxAllocate   : Boolean;
  306.      received     : Boolean;
  307.      maxAttempt   : Boolean;
  308.  
  309.    Three of the new variables are initialised inside the 802.3 standard
  310. procedure Initialize as follows:
  311.  
  312.      paceEnld    = {user-defined. }
  313.      txLast      = false;
  314.      rxAllocate  = false;
  315.      received    = false;
  316.      maxAttempt  = false;
  317.  
  318.    Two constants are also defined.  They are attemptLimit and
  319. netDelayTime.  attemptLimit is defined the same way as in 802.3 but can
  320. be set from 1 to 16.  It defines the number of times the
  321. TransmitLinkMgmt process will attempt to transmit a packet before
  322. discarding it as an excessive collision error.  This variable can be set
  323. from 1 to 16.  Typical values would be 7 or 8 for low latency access.
  324.  
  325.  
  326.  
  327.                        June 23, 1997
  328.  
  329.  
  330.  
  331.  
  332.  
  333.                            - 6 -
  334.  
  335.  
  336. netDelayTime is used to "extend" the IPG after a transmission if no
  337. collision has occurred during the last transmission but rxAllocate is
  338. enabled.  It is used to give the other station a chance to transmit if
  339. it has a packet to send.  It can be set from 0 to 1 slot-time.  This
  340. value should be tuned to match the round-trip delay between the two
  341. end-stations.  A value of 256 to 512 Bit-Times would be typical.
  342.  
  343.    const
  344.      attemptLimit   = { user-defined - 1-16 }
  345.      netDelayTime   = { user-defined - expressed in Bit-Times;
  346.                         0-512bts }
  347.  
  348. 2.2.1   TransmitLinkMgmt Process
  349.  
  350. The pseudo code for a new TransmitLinkMgmt process for standard 802. 3
  351. and Ethernet with PACE-IA is shown below  :
  352.  
  353. function TransmitLinkMgmt: TransmitStatus;
  354. begin
  355.     attempts := 0; transmitSucceeding := false;
  356.     lastAttempt := false;
  357.     lateCollisionCount := 0;
  358.     deferred := false;    {initialize}
  359.     excessDefer := false;
  360.     while (attempts < attemptLimit) and (not transmitSucceeding) do
  361.     begin {loop}
  362.         if attempts > 0 then
  363.         {    rxAllocate := paceEnld;    { Had collision so enable
  364.                                       rxAllocate timer }
  365.             BackOff;
  366.         }
  367.  
  368.  
  369.  
  370. Hickey                                                          [Page 5]
  371.  
  372.              PACE Technology Interactive Access Algorithm  June     1997
  373.  
  374.  
  375.         /* Skip transmission attempt on lastAttempt in Pace-IA mode */
  376.         /* if activity  detected  on network.                    */
  377.         if  not ( paceEnld and lastAttempt and carrierSense )
  378.         {
  379.             if received then
  380.             {    txLast := false;    { accounts for any packets
  381.                                      received between transmit packets }
  382.                 maxAttempt := false;
  383.             }
  384.             frameWaiting := true;
  385.             lateCollisionError := false;
  386.             while deferring do     {defer to passing frame, if any }
  387.             begin
  388.                 deferred := true;
  389.                 if received then
  390.  
  391.  
  392.  
  393.                        June 23, 1997
  394.  
  395.  
  396.  
  397.  
  398.  
  399.                            - 7 -
  400.  
  401.  
  402.                 {    txLast = false;
  403.                     maxAttempt := false;
  404.                 }
  405.             end;
  406.             frameWaiting := false;
  407.             StartTransmit;
  408.             while transmitting do WatchForCollision;
  409.             if lateCollisionError then
  410.                 lateCollisionCount := lateCollisionCount + 1;
  411.         }
  412.         attempts := attempts + 1;
  413.         if (attempts == (attemptLimit - 1)  ) then
  414.             lastAttempt := true
  415.         else
  416.             lastAttempt := false;
  417.     end; {loop}
  418.  
  419.     if transmitSucceeding then
  420.     {    TransmitLinkMgmt := transmitOk;
  421.         txLast := true;                {completed a transmission)
  422.     }
  423.     else TransmitLinkMgmt := excessiveCollisionError;
  424.     LayerMgmtTransmitCounters;
  425.     received := false;                { clear here in the IPG as just
  426.                                      "transmitted" }
  427.     if (rxAllocate) then
  428.     begin
  429.         BackOff;                { allow other node to transmit }
  430.         if ( not carrierSense ) then
  431.             rxAllocate := false;    { timer expired and no packet
  432.                                       received }
  433.     end
  434. end;   {TransmitLinkMgmt}
  435.  
  436. 2.2.2   BackOff Procedure
  437.  
  438.    The pseudo code for a new BackOff procedure for standard 802. 3 and
  439. PACE-IA Ethernet access is shown below :
  440.  
  441. Hickey                                                          [Page 6]
  442.  
  443.              PACE Technology Interactive Access Algorithm  June     1997
  444.  
  445.  
  446. var maxBackOff: 2 .. 1024;    {working variable of BackOff}
  447. var backOffDelay;
  448.  
  449. procedure BackOff;
  450. begin
  451.         if (paceEnld)             { PACE mode backoff  }
  452.         {    if (txLast and rxAllocate ) then      {Receive wait  timer
  453.                                                     setting}
  454.             {  if ( ( attempts == 1 ) & transmitSucceeding ) then
  455.                     backOffDelay := netDelayTime;
  456.  
  457.  
  458.  
  459.                        June 23, 1997
  460.  
  461.  
  462.  
  463.  
  464.  
  465.                            - 8 -
  466.  
  467.  
  468.                 else if ( attempts <= backOffLimit ) then
  469.                     backOffDelay := 2 ^ (attempts) * slotTime;
  470.                 else
  471.                 backOffDelay := 1024 * slotTime
  472.  
  473.             else if ( lastAttempt ) then
  474.                 { backOffDelay := slotTime/2;   {first time
  475.                                                   lastAttempt reached }
  476.                     if ( maxAttempt ) then    {back-back packets
  477.                                   reached lastAttempt }
  478.                     {introduce some randomness to help break
  479.                       lockup of two PACE Technology nodes}
  480.                     {random backoff range can also be based on
  481.                       multiples of IPG}
  482.                     backOffDelay :=
  483.                         backOffDelay * Random(1, attempts);
  484.                 else
  485.                     maxAttempt := true;
  486.                 }
  487.             else
  488.                 backOffDelay := 0;
  489.  
  490.             while (  Wait(backOffDelay) and ( not carrierSense )  )
  491.                 do nothing
  492.         }
  493.         else                {standard 802.3 mode }
  494.         {    if attempts = 1 then
  495.                 maxBackOff := 2
  496.             else if attempts <= backOffLimit then
  497.                 maxBackOff := maxBackOff x 2;
  498.             Wait( slotTime *  Random( 0, maxBackOff )  )
  499.         }
  500. end BackOff;
  501.  
  502. 2.2.3   Deference Process
  503.  
  504.    The pseudo code for the Deference process for standard 802.3 and
  505. Multimedia Ethernet is shown below.
  506.  
  507.  
  508.  
  509.  
  510.  
  511.  
  512. Hickey                                                          [Page 7]
  513.  
  514.              PACE Technology Interactive Access Algorithm  June     1997
  515.  
  516.  
  517. process Deference;
  518. begin
  519.     cycle     {main loop}
  520.         while not carrierSense do nothing; {watch for carrier to appear}
  521.         deferring := true;            {delay start of new transmission}
  522.  
  523.  
  524.  
  525.                        June 23, 1997
  526.  
  527.  
  528.  
  529.  
  530.  
  531.                            - 9 -
  532.  
  533.  
  534.         wasTransmitting := transmitting;
  535.  
  536.         while ( carrierSense or transmitting )
  537.             wasTransmitting := wasTransmitting or transmitting;
  538.  
  539.         received := not wasTransmitting;    {received a packet}
  540.  
  541.         if wasTransmitting then
  542.             Wait(interFrameSpacing1)
  543.         else
  544.         {    while carrierSense do nothing;
  545.             Wait(interFrameSpacing1)
  546.         }
  547.  
  548.         Wait(interFrameSpacing2);
  549.         deferring := false;        {allow new transmissions to proceed}
  550.  
  551.         while frameWaiting do nothing;     {allow waiting transmission
  552.                                             if any}
  553.  
  554.     end        {main loop}
  555.  
  556. end; {Deference}
  557.  
  558.  2.2.4   Parameterized Values :
  559.  
  560.    The following parameter values  shall be used for  PACE Technology's
  561. Interactive Access implementations :
  562.  
  563. Parameter Name              Minimum                   Maximum
  564. attemptLimit                   6                         13
  565. netDelayTime                 256 BTs                    512 BTs
  566.  
  567.  
  568. 3.   References
  569.  
  570.    [1]  P. Sherer, L. C. Lo and J. Hickey, "Method and Apparatus for
  571.    Controlling Latency and Jitter in a Local Area Network Which Uses a
  572.    CSMA/CD Protocol," United States Patent 5,568,469.
  573.  
  574.    [2]  ISO/IEC 8802-3: 1993 [ANSI/IEEE Std.  802. 3, 1993],Information
  575.    technology - Local and metropolitan area networks - Part 3 :Carrier
  576.    sense multiple access with collision detection (CSMA/CD)access method
  577.    and physical layer specifications.
  578.  
  579.  
  580.  
  581.  
  582.  
  583. Hickey                                                          [Page 8]
  584.  
  585.               PACE Technology Interactive Access Algorithm  June     1997
  586.  
  587.  
  588.  
  589.  
  590.  
  591.                        June 23, 1997
  592.  
  593.  
  594.  
  595.  
  596.  
  597.                            - 10 -
  598.  
  599.  
  600.    [3]  Chlamtac and M.  Eisinger, "Performance of Integrated Services
  601.    (Voice/Data) on CSMA/CD Networks", Proceedings of ACM Sigmetrics'85,
  602.    pp. 87-93, August 1985.
  603.  
  604.    [4]  P. Wang, "Class-of-Service Implementation for PACE Technology",
  605.    January, 1997
  606.  
  607.  
  608. 4.   Security Consideration
  609.  
  610.    This document raises no security issues.
  611.  
  612.  
  613. 5.   Author's Address
  614.  
  615.     John Hickey,
  616.     3Com Corp.,
  617.     Ballycoolin Business Park,
  618.     Blanchardstown,
  619.     Dublin 15,
  620.     Ireland.
  621.  
  622.     Phone :    353-1-8035711
  623.     EMail :    John_Hickey@3Mail.3Com.com
  624.  
  625.  
  626.  
  627. INTERNET-DRAFT         EXPIRES DECEMBER 1997     INTERNET-DRAFT
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.  
  635.  
  636.  
  637.  
  638.  
  639.  
  640.  
  641.  
  642.  
  643.  
  644.  
  645.  
  646.  
  647.  
  648.  
  649.  
  650.  
  651.  
  652.  
  653.  
  654.  
  655.  
  656.  
  657.                        June 23, 1997
  658.  
  659.  
  660.