When Packets Collide
Noah Davids If I had known a month ago what I know now, I could have saved a lot of time and reduced significantly my blood pressure. For the attention deficit disordered readers, I'll sum up early - you can usually ignore the collision counter reported by netstat or any of the SNMP or RMON monitors you may be using. This article will explain what a collision is and why it usually doesn't matter. Ethernet is based on carrier sense multiple access with collision detection (CSMA/CD). Basically, a station that wants to send something on the network, listens to the network. If the station does not detect a signal on the channel indicating another station is sending, then it begins transmitting. While the station is sending, it also monitors the network to make sure that another station does not also start sending (i.e., collision detection). Collision Detection Ethernet uses two major physical media, and each has its own detection mechanism. The first media type is coax, consisting of thick coax (10Base5) and thin coax (10Base2). Each bit of data travels as a current in both directions from the station's connection to the cable. The voltage on the cable is monitored by the sending station. If more than one station sends at the same time, the voltage will not be what is expected, and a collision will be indicated. The other major media type is unshielded twisted pair (10BaseT). With this media type, a signal is transmitted on one pair of wires while another pair is used to receive a signal. The cable holding these pairs goes from the station to a hub, which is really just a multiport repeater. The repeater will transmit any signal it receives from one port to all its other ports. If a station receives a signal at the same time that it is transmitting, a collision will be indicated. Ethernet Frames For the rest of this discussion, an understanding what an Ethernet frame looks like will be helpful. A diagram is shown in Figure 1. The Interframe Gap (IFG) is not really transmitted; instead, it is the time needed to transmit 12 bytes. During the IFG, no station should be transmitting. It is literally a gap between frames. For my purposes in calculating the effects of collisions, I will include the IFG delay. The minimum Ethernet frame size is 64 bytes, and the maximum is 1518 bytes. That includes the 4 bytes of CRC (cyclic redundancy check) at the end of the frame but not the 8-byte preamble. Again for my purposes, I will include the time it takes to transmit the preamble. For those wondering, the preamble is a bit pattern used to indicate that the data portion of a frame is about the start. If each station listens before sending, how can a collision even occur? There are two ways that a collision can happen. First, let's assume there are two stations (A and Z) at opposite ends of a network. The network is currently idle and has been for some time greater than the IFG time. At time T, station A starts to send. It takes a certain amount of time for the signal to go from station A to station Z. On a maximum length network, this will be 23.2 microseconds (s) or half of the round trip time. Station Z can start transmitting any time before T+23.2 s since it will not hear station A until then. At T+23.2 s station Z "hears" the signal from station A and recognizes the collision. The second way is caused by the way that the Ethernet chip reacts when it starts to send a frame but there is already a station sending. In this case, the chip waits (defers) for the sender to finish, waits for the IFG time, and then sends its frame. If two stations were waiting, they will both send, thereby creating a collision. What happens once a station recognizes that a collision has occurred? Many people may say to themselves that it will send a jam packet. Actually, the station will send the next 4 bytes of the frame. If the station has not yet finished sending the preamble sequence, it will complete that before sending the first 4 bytes of the frame. The purpose of sending the additional 4 bytes is to make sure that the transmitted signal is "heard" by the other station, so it also knows about the collision. A maximum of 72 bytes may be sent (preamble + minimum data + 4 byte "jam"); these bytes are called a collision fragment. The Collision When a collision occurs, the Ethernet chip experiencing the collision will wait a random amount of time and then retransmit the frame. The amount of time that the chip waits is bounded by (2**n)-1 slot times where n = min (K, 10) and K is the number of times that the chip has tried to transmit the frame. This is known as truncated binary exponential backoff. The slot time is a time longer than the maximum round trip time plus the maximum "jam" time. The maximum round trip time is the time it takes to transmit 58 bytes. The "jam" is 4 bytes, so the slot time must be at least the time it takes to transmit 62 bytes. It's actually defined as the time it takes to transmit 64 bytes or 512 bits. On a 10-megabit Ethernet, this is 51.2 s. For 100-megabit Ethernet, it's 5.12 s. Everything hereworks for Fast Ethernet as well, just divide the times by 10. Performance Impact Collisions do not impact performance significantly. Let's assume a 100% collision rate as seen from the network layer. That is, each packet of data submitted by the network layer to the data link layer results in one collision. This means that the Ethernet chip's first attempt to transmit the data results in a collision, and the second attempt is successful. As seen from the network layer, the data is delayed by the 67.2 s (IFG + preamble + minimum data (worst case) + CRC) that it took during the initial attempt to send the frame plus the 51.2 s backoff time (again, worst case). Transferring a 5-MB file via ftp requires 3,592 frames (5,242,880 bytes / 1,460 bytes of file data/frame) with a total delay due to collisions of 425.3 ms (3592 * 118.4 s). A collision rate of 300% (each packet of data submitted by the network layer to the data link layer results in three collisions with the data successfully transmitted on the fourth attempt) will delay each packet a maximum of 560 s, adding a little more than 2 seconds to the time it takes to transfer our 5-MB file. Table 1 summarizes the maximum backoff times, maximum time to transmit the collision fragments, and the maximum total delays. Note that in Table 1 the "time (s) to wait for packet to pass (deferral time)" column is 0. Table 1 assumes that after a collision, (when the chip is ready to send), the network is idle, and it can send. This may not be true. Table 2 assumes that after every collision (when the chip is ready to send), it must wait long enough for a maximum-length frame that just started transmission to complete. This adds another 1230.4 s (preamble + maximum data + CRC + IFG) delay to each attempt. The delay at 100% now becomes 4.8 seconds, and at 300% is 15.3 seconds. Of course, the deferral time may occur even if there are no collisions. The worst case deferral time has much more impact on the delay in sending data than the worst case collision time, at least until the eighth collision. In fact, it's not until the fifth collision that the maximum delay caused by collision backup and collision fragments exceeds the delay caused by one maximum deferral and no collisions. Note that your network is not idle during these delays; other stations are transmitting. If they weren't, there would be no deferrals and no collisions. 16 Collisions What happens after 16 collisions? After 16 attempts to send a frame, the Ethernet chip will discard the frame (instead of waiting and trying a 17th time). At this point, a higher layer protocol becomes responsible for queuing the packet to be retransmitted. The chip counts the number of times that this happens in the dot3StatsExcessiveCollisions counter (defined in RFC-1643). It is possible that the overall collision rate can be low, but a burst of activity from many stations may create a period when frames are dropped due to excessive collisions. Collisions, Not When is a collision not a collision? What happens if a network is so long or a frame so short that at least one of the stations can complete its transmission before the signal from the other station arrives? In that case, the first station notices nothing wrong, but the stations in the middle of the network see both signals overlapped and hence garbage. This collision detection mechanism dictates to Ethernet the maximum length of the network and the minimum length of a frame. The network must be short enough that the first bit of a frame from a station at one end of the network (station A) can reach station Z at the other end of the network, and the first bit of station Z's frame can travel back to station A, before station A is done transmitting. To accomplish this, the Ethernet specification requires all frames to be at least 64 bytes in length (not counting the 8-byte preamble). If a collision occurs before the 65th byte is transmitted, the Ethernet chip will declare a collision, back off, and retransmit the frame. If the collision occurs after the 64th byte has been transmitted, it is declared a late collision. In this case, the Ethernet chip will just drop the frame and not try to retransmit it. It's left to the higher layer protocols to retransmit the data. This latter case can have a serious impact on performance because the time out for higher layer protocols is typically in the hundreds of milliseconds, or even seconds, instead of microseconds. In most cases, late collisions are caused by bad network design (the network is too large) or a failed transmitter that is not detecting when another station is sending. The transmitter may also be set to full duplex. In this mode, the transmitter has been told that it can send and receive simultaneously. This is possible only when using 10BaseT, since it uses separate wires for sending and receiving. Many PC cards can also be set in full-duplex mode. If the hub to which the PC cards are cabled also supports full-duplex mode, you can theoretically double the bandwidth of the network. However, if the hub, or any device connected to the hub, does not support full duplex, the effect can be just as spectacular in the other direction. A late collision can also occur because of electrical noise created when a connector is inserted or removed from a cable or hub. RFC-1643 defines the counter dot3StatsLateCollisions to count late collisions. This counter should always be 0, or at the very worst, a small number. Also, if a station is sending mostly minimum-sized frames, (e.g., a telnet client), it's possible that late collisions will not be identified, because there is no 65th byte. Network Utilization How much does a collision impact network utilization? A maximum length collision will use 84 bytes of capacity (IFG + preamble + minimum data + CRC). A maximum length non-collision frame is 1538 bytes. At a 100% collision rate, there will be an extra 84 bytes wasted or about 5.5% ((1538+84)/1538). At 300%, the waste grows to 16%. When should you start worrying about the collision rate? Probably never. There are many rules of thumb about what constitues an acceptable collision rate. Most such rules indicate a value between 30 and 60%. But, as the above analysis shows, anything below 100% doesn't add a significant amount of overhead. Even at 300%, the time delay caused by collisions is not significant, although the added deferral delay may be. Remember however, that the above analysis is the absolute worst case. Collision backoff times are random. Thus, they will not always be the maximum that I used. Deferral times will depend on the size of frames on the network, and it's a very unusual network that has nothing but maximum-sized packets. Finally, the time that it takes to recognize a collision depends on the size of the network. If instead of assuming a maximum-sized network (so collisions always take 84 bytes), we assume that all stations are plugged into a single 10BaseT hub, every collision will occur in the preamble, and the collision fragments will only be 24 bytes and take only 19.2 s to transmit. If we assume average backoff times (max /2), collision fragments of 24 bytes, and a frame size of 759 bytes, the values in the "max time to transmit first bit for try #" column in Table 2 drop by slightly more than half. Slam Dance, Dunk Another point to remember is that collisions are normal events on an Ethernet, not abnormal incidents. Collisions are used to decide which station gets to transmit its frame. Thus, Ethernet can be thought of as one of those clubs where it is normal for the dancers to bump into each other. As the number of stations on an Ethernet increases (or, the dancers on the floor), so will the number of collisions. As long as application performance is acceptable, the rate of collisions is not important. So, if your boss comes to you and declares that her new network monitor tool is reporting a 90% collision rate, ask her how the network is actually performing. If you're not getting complaints about performance, tell her that you'll get right on it - after you've sorted your sock drawer. If you are getting complaints, start looking for the real problem and don't worry about perfectly normal collisions. Although the real problem may be elusive, the no-fix fix for the slam dance non-problem is a slam dunk. References RFC-1643. Definitions of Managed Objects for Ethernet-like Interface Types MIB
Richard Seifert. The Effect of Ethernet Behavior on Networks Using High-Performance Workstations and Servers. ftp://ftp.netcom.com/pub/se/ \ David R. Boggs, Jeffery C. Mogul, and Christopher A. Kent. Measured Capacity of an Ethernet: Myths and Reality. Digital Western Research Laboratory Research Report 88/4. About the Author
Noah Davids works in the Customer Assistance Center of Stratus Computer Inc. He specializes in the diagnosis and correction of LAN problems. "It's the wire" followed by "it's the router" covers most problems. The trick is finding which wire or router. He can be reached at Noah_Davids@stratus.com.
|