MEDIUM ACCESS CONTROL
What follows is a discussion of the medium access control protocol for a 10 Mbps half-duplex Ethernet network operating with several nodes.
When a station wants to transmit, it first waits for an absence of a carrier, which would indicate that some other station is transmitting. As soon as silence is detected, the station waiting to transmit continues to defer until the Interframe Gap (IFG) time has expired which is a minimum of 96-bit times (9.6 µs). If a carrier still appears to be absent, the station begins to transmit while observing its collision sense circuitry. If no collision is detected, the transmitting station assumes the transmission was sent successfully. If a collision is detected, the transmitter will continue to send 32 bits of data to reinforce the collision. If the transmitter detects an early collision, one which occurred during the preamble, the station continues to send the preamble plus 32 bits of data called a jam signal. This ensures that other stations will note the collision as well. After the collision, the transmitting station will back off from retransmitting based upon a backoff algorithm. If no collisions are detected after 512-bit times (not counting the preamble), the station is assumed to have acquired the channel and no late collisions should occur on a properly working network. The collision counter is cleared. This 512-bit time (51.2 µs) is called the slot time and is critical in the way Ethernet arbitrates access to the cable.
Collision Domain
This slot time defines the upper bound limit of the total propagation delay of a transmitted symbol from one end of the network to the farthest end and back. This includes the time it takes the symbol to travel through cables, repeaters and MAUs and varies with devices used. However, regardless of the path, the resulting propagation delay must be less than the slot time. Within this time, faithful detection of a collision can occur. This is called the collision domain. Therefore, the slot time defines Ethernet’s maximum network diameter which cannot exceed the collision domain. A collision domain that is less than the maximum network physical diameter violates Ethernet’s medium access control mechanism and results in unreliable operation.
Collisions can generate runt packets that are less than 512 bits in length. These can be detected by the receiving nodes and discarded accordingly. That is why it is important that a minimum valid Ethernet frame always be sent to distinguish valid packets from packet fragments. A minimum of 46 bytes in the data field ensures that a valid Ethernet frame is 512-bits long. Control messages are typically short so it should be remembered that the shortest Ethernet frame is 64 bytes in length.
If the network diameter is small, collision detection is faster and the resulting collision fragments are smaller. As the network diameter increases more time is lost detecting collisions and the collision fragments get larger. Increased network diameter aggravates the collision problem. Silence on the line does not necessarily mean a distant transmitter has not already sent a packet down the cable, which will eventually result in a collision.
 |
Figure 3 — For proper operation, the maximum network diameter must be less than the collision domain.
|
Collision Detection
A collision is defined as two stations attempting to transmit at the same time. On coaxial cable transceivers, there is circuitry to detect the DC level of the signal on the cable. This is the indicator of a collision. On fiber optic and twisted-pair interfaces with separate receive and transmit circuitry, a collision is detected by the simultaneous receiving and transmitting of data. Remember that we are discussing half-duplex Ethernet that allows either transmitting or receiving but not at the same time. Only transmitters look for collisions and it is their responsibility to reinforce a collision with a jam signal. Receivers only look for valid packets and automatically discard runt packets that are caused by collisions. Once a collision is detected by simultaneous transmitters, these transmitters will follow a backoff algorithm
Backoff Algorithm
When a collision occurs on the network, the colliding transmitters will back off from retransmitting for a time determined by a backoff algorithm. This algorithm requires each transmitter to wait an integral number of slot times (51.2 µs) before attempting a new transmission sequence. The integer is determined by the equation:
0 
r 
2 <size= “-2″=””>k where k = min (n, 10)
The variable k is actually the number of collisions capped at a maximum of 10. Therefore, r can range from 0 to 1023 when k = 10. The actual value for r is determined by a random process within each Ethernet node. As the number of consecutive collisions increases, the range of possible backoff times increases exponentially. The number of possible retries is also capped, but at 16.
For example, assume two stations A and B on the network wanting to transmit. They both wait for an absence of carrier and then wait for the IFG time to expire before initiating a transmission. It does not matter if they are 10 meters or 2500 meters apart. They could both be sensing silence and simultaneously begin to transmit causing a collision at some point. They each sense the collision and back off for either 0 or 1 slot time. The odds are 50-50 they will pick the same value and collide again. If they do, they will now back off for either 0, 1, 2 or 3 slot times. The probability of collision is now 25%. Eventually, one will win in which case its collision timer is cleared to zero while the other collision timer continues to increment until a successful transmission.
A high number of retries indicates a busy network with more stations wanting to transmit than originally assumed. That is why the backoff time range is increased exponentially to provide more possible slot times for the additional stations. At ten retries, it is assumed that 1024 simultaneous transmitters exist. This becomes the upper bound limit of stations that can coexist on one Ethernet network. Actually this is the logical limit. Physically it may be impossible to have that many stations on one collision domain without violating cabling rules.
|
BACKOFF RANGE AS A FUNCTION OF COLLISIONS
|
|||
|
Collision on Attempt Number
|
Estimate of Number of Other Stations
|
Range of Random Numbers
|
Range of Backoff Times (µs)
|
| 1 | 1 | 0 … 1 | 0 … 51.2 |
| 2 | 3 | 0 … 3 | 0 … 153.6 |
| 3 | 7 | 0 … 7 | 0 … 358.4 |
| 4 | 15 | 0 … 15 | 0 … 768.0 |
| 5 | 31 | 0 … 31 | 0 … 1587.2 |
| 6 | 63 | 0 … 63 | 0 … 3225.6 |
| 7 | 127 | 0 … 127 | 0 … 6502.4 |
| 8 | 255 | 0 … 255 | 0 … 13056.0 |
| 9 | 511 | 0 … 511 | 0 … 26163.2 |
| 10 | 1023 | 0 … 1023 | 0 … 52377.6 |
| 11 | 1023 | 0 … 1023 | 0 … 52377.6 |
| 12 | 1023 | 0 … 1023 | 0 … 52377.6 |
| 13 | 1023 | 0 … 1023 | 0 … 52377.6 |
| 14 | 1023 | 0 … 1023 | 0 … 52377.6 |
| 15 | 1023 | 0 … 1023 | 0 … 52377.6 |
| 16 | Too High | N/A | Discard Frame |
Table 1 — Backoff range increases exponentially with the number of collisions