+===========================================+ | Reducing the Effects of Propagation Delay | | on CSMA/CD Networks | +===========================================+ Mart L. Molle Computer Science Department University of California Riverside, CA 92521 (Ascii version of talk presented to Gigabit study group, in La Jolla CA, March 1996) Purpose of Talk: ================ - To describe two techniques for modifying CSMA/CD networks to reduce the *cost* of collisions - First technique is to add =Collision Deletion= to the receiver below the MAC (i.e., PCS layer), and therefore it can be applied to Repeaters (and, optionally, to hosts) in 10BaseT, 100BaseT, and Gigabit Ethernet - It reduces the duration of most collisions - Second technique is just to switch from asynchronous (unslotted) to synchronous (slotted) operation -- like the difference between unslotted and slotted ALOHA - Together, they change the collision slot time to be the round-trip delay to the repeater only! Collision Deletion in Repeaters =============================== - Observation is that =leading edge= of a collision fragment contains the information content of the fragment as far as the MAC is concerned. - As soon as a transmitter receives the start of an incoming fragment, its response is fully determined (finish preamble, send jam, stop) - However, its next action must wait for silence, which in general can be delayed a long time while we wait for collision fragments to fall off the ends of the network - Here we speed things along their natural course by giving the input port on a repeater a "proxy": permission to truncate an incoming signal the way the sender would have done if it had been closer to the event. - "Obviously", this reduces the time wasted on forwarding collision fragments, which is good - "Not so Obviously", this doesn't break anything with existing CSMA/CD DTEs, because the interFrameGap is still valid if you compute it based on the end of a truncated fragment - Method still works with irregularly spaced repeaters, and/or multiple repeaters as long as all of them follow these same rules - Method can also be applied to the receive side of a host interface. - Result is to shorten the typical collision fragments by 20%-50% by the time they reach the hosts, depending on the event timing - Does not affect the worst-case collision timing, and hence the "slot time" for CSMA/CD Example of Operation ==================== Host A Repeater Host B Host A Repeater Host B * | | * | | |* | | |* | | | * | | | * | | | * | | | * | | | * | + | * | + | * | +| | * | +| | * | + | | * | + | | * | + | | * | + | | * | + | | * | + | | * | + | | * | + | | * | + | | * | + | | *| + | | *| + | | * + | | * + | | |* + | | |* + | | | * | | | * | | |+ * | | |+ * | | (1)+ * | | (1)+ * | | +| * | | +|J * | | + | * | | + | J * | | + | * | | + | J * | | + | * | | + | J * | | + | * | | + J(2) J * | | + | * | | + J| J * | | + | (3)*| | + J.|. J(3)*| | + | J | | + J. | . J J | | + | J | | + J. | . J | | + | J | | + J. | . J J | |+(4) | J | |+(4) J. | . J(5)J| | J | J | | J J. | J | | J | J | | JJ. | J . | | J | J | | JJ | J . +| | J | J | | J. J | J .+ | | J | J | |J(6) J | J +. | | J |J | |. J |J + .| | J J | | J J(7) + | | J J|(7) | | J | + | | J | | | J | + | | J J| | | (8)J| + | | J(8)J | | | + | | J |J | | | + | | J | J | | |+ | | J | J | | + | | J | J | | +| | | J | J | | + | | | J | J | | + | | |J(9) | J | | + | | | | J | | + | | | | J | | + | | | | J | | + | | | | (10)J| | + | | | | | | + | | | | | | + | | | | | |+(11) | | With a conventional repeater, the With a collision truncating repeater, signals from hosts A and B pass the collision is first detected AT THE straight through the repeater, and REPEATER at time (1). We assume that nothing changes until the signals Host A has transmitted enough to get reach the hosts on the other side past its preamble, so the repeater and the collision is detected at switches from Host A's signal to a JAM respective times (3) and (4), when being sent towards Host B. However, the two hosts switch to their JAM Host B's signal is just starting signals, and then stop and wait repeater first finishes transmiting for the incoming signal to stop Host B's preamble at time (2), then at respective times (9) and (10). switches to the JAM signal being sent towards Host A. Thereafter, Hosts A and B detect the collision as usual, at respective times (3) and (4) and shortly thereafter, the truncated (by the repeater) incoming collision fragments end at times (5) and (6), and these hosts can go on to calculating the interframe gap for their next packet transmissions relative to times (5) and (6). For example, Host B could send the new packet indicated by the bottom line that arrives at Host A at time (11), which we can guarantee will not arrive at Host A before the channel has been idle for a valid interframe gap --- even though the gap at the left side of the repeater (measured below time (8)) may be too small or even completely absent. Synchronous (Slotted) Operation =============================== - Using previous collision deletion technique, the best-case performance occurs if all transmitters in a collision are timed to arrive at the repeater at exactly the same time - The repeater could force this to happen by issuing a "next step" symbol on each output port at the right time. (With reference to the above diagram, the timing symbol would be sent out all ports at time (2), and as shown in the figure by the dotted lines going away from the repeater in both directions.) - MAC acts normally, but PHY delays start of transmission until the arrival of the "next step" symbol (similar to slotted ALOHA delaying transmissions to next slot boundary) - No need for PHY to "extend carrier" like Howard Frazier's proposal - However, for short frames, the PHY waits to end of slot to return success/collision status - Repeater sends a "next step" symbol after each successful frame transmission - Thereafter, if the channel remains continuously idle, it sends another symbol every "slot time" - Can compensate for varying propagation delays by a simple feedback control loop - Ideally, timing of the "next step" symbols is arranged so that all responses return to the repeater at the same time (i.e., delay timing symbol for a nearby host) - Collision window at the repeater is essentially zero, i.e., just a tolerance for timing errors - Result is that repeater knows if the responses to a "next step" symbol will be a success or a collision as soon as the responses from the hosts start arriving - Successful transmissions can be followed immediately by the "next step" symbol on all ports. (MAC receiver doesn't need to strip extended carrier.) - Method is independent of which version of the MAC we use (BEB or BLAM) - BLAM burst mode can be efficiently supported: * Sender doesn't wait for "next step" symbol within a burst (but MAC must do Go-Back-N) * Repeater witholds the "next step" symbol after a non-collision until XmitBurstSpace has passed - Result: we pay the cost of the long propagation delay (wait for "next step" symbol, or extend carrier, etc) only once per burst, even with minimum length frames - Collisions happen simultaneously at the repeater (by design!) - Collision deletion truncates each incoming frame to just preamble/SFD and jam, which gets sent to everyone - Thereafter, even though the hosts keep sending until they hear the collision, the repeater ignores the rest of the incoming signal. - When the outbound signal arrives from the repeater, the MAC does its normal JAM and stop, at which point the incoming fragment ends too, and a "next step" symbol arrives. - Result: minimum slot time is determined by the sum of the round-trip delay between a host and the repeater, and a minimum length collision. Effect on Howard Frazier's Timing Budget ======================================== - At January Interim Meeting, he showed some bit budget estimates for single repeater 1000BaseF networks - Assuming 200 meter *diameter*, i.e., DTE <-- 100m --> Repeater <-- 100m --> DTE he estimated a round-trip delay of 2476 bits, including 2020 bits of cable delay. - Using these two techniques, the cable delay can be computed based on a 100 meter *radius*, i.e., DTE <-- 100m --> Repeater which reduces his estimate to 1466 bits, or 183.25 bytes - Assuming 20 meter diameter, the techniques reduce his estimate from 82.25 bytes to 69.625 bytes Conclusions =========== 1. Incoming Collision Deletion combined with slotted operation make CSMA/CD much more practical at 1 Gigabit/sec because the slot-time calculation can be based on the network =radius= instead of its diameter 2. Result is that only a modest increase in the slot time is required: -- 72 bytes, or 12.5%, for 20 meters -- 192 bytes, or 300%, for 200 meters 3. Incoming Collision Deletion by itself is compatible with standard CSMA/CD DTEs and should be added as an optional feature to the repeater spec (or possibly the PCS sublayer)