14 The Medium Access Sublayer: Ethernet

Prof. Bhushan Trivedi

Introduction

The MAC or Medium Access Sublayer is part of the data link layer and needed where the media is shared between machines. We will look at two popular solutions, Ethernet and 802.11 or Wi-Fi in this module. Whenever there are multiple machines wants to communicate with each other, they need to coordinate their process otherwise there is a possibility of a chaos. If more than one sender starts sending, their signals merge into each other and resultant signal may not be recognizable at all. Such a signal is known (obviously) as garbage. This clearly means that there must be some form of arbitration needed to decide who shall send next and who shall wait. The arbitration can be done in two different ways, first, having a central arbitrator machine which decides so. Another is to use some distributed algorithm which takes consensus on all potential senders to decide who will send next.

The MAC layer is designed to handle this problem and both forms of arbitration, with and without a central coordinator, are used in practice. For example, Wi-Fi, when used with access points (AP), (the infrastructure mode) the AP acts as a central arbitrator and decides who should be sending next. When the same Wi-Fi is used without an access point, (the ad hoc mode), the arbitration process is collectively decided based on specific method chosen for communication. Ethernet, in its first version, used a strategy known as “let anybody send at any point in time, resolve if there is a collision”. This is also an example of distributed processing.

The FDM and TDM etc. are also channel-acquisition policies which evenly distribute the available time or frequency to all communicators. We have already seen that they are not appropriate for data transmission as they are not suited for bursty traffic like data.

Arbitration in ad hoc and infrastructure modes

Closely look at figures 16.1 and 16.2. The access point connects all machines which want to communicate with each other. Access point authenticates them and allows them to communicate through itself. That means no two machines directly talk to each other. When a machine A wants to talk to machine B, it (A) will send it to AP and AP relays it to B. AP also decides the time and frequency to use for each machine, eliminating any possibility of collision. A collision is an event when two machines send together and their signals result into the garbage.

In Ad-hoc (or Distributed Coordinated Function, DCF) mode, two machines directly talk to each other. It is possible to have both types of communication going on together. That means, it is possible that access point is arbitrating between some machines and some other machines are communicating directly. The 802.11 have carefully designed its arbitration mechanism to handle this problem.

It is interesting to note that Ethernet uses a start topology which looks similar to the PCF mode. When hubs were used in the first version of Ethernet, they broadcast everything coming in and work exactly like the AP. Later on, when switches have come into use, they changed the strategy and provided point to point communication.

Ethernet

Ethernet is the de-facto standard for wired LAN. Bob Metcalfe and David Boggs were the mastermind behind the design of Ethernet. They derived the inspiration from an older wireless network called ALOHA.

The first popular version of Ethernet was called DIX based on initial letters of the names of the three companies which were involved in the standardization, DEC1, Intel and Xerox. It was running at the speed of 10 Mb. Later on, IEEE has also standardized the Ethernet and gave its own frame format. This version of Ethernet is now known as classic Ethernet. This classic Ethernet was designed as a broadcast network and had all the problems of broadcast networks. Later versions did not use the broadcast version so we will not stress here that further. For details please refer to reference-1. Whenever there is a collision, the Ethernet uses an algorithm called binary exponential back off. That algorithm is used in many other cases including the wireless cases, so we will study that later in this module.

Later versions of Ethernet increased the speed to 100 Mb, 1 Gb, 10 Gb, 40 Gb and 100Gb. The first version used coaxial cables but later versions switched over to UTP cables and most recent versions use FO cables. For details of different types of cables used in various versions of Ethernet please refer Reference-1. For coding schemes used for those systems, refer to reference-2.

Ethernet uses start topology as depicted in figure 16.3. Though the figure names the central device as hub or switch, hubs are out of vogue and hardly used. The implementation also uses a

1 DEC (Digital Equipment Corporation, later merged with Compaq which in turn merged with HP cascaded star topology which allows connecting networks together. Figure 16.4 depicts the case. Three different networks are connected using three different switches.

As Ethernet was first standardized by DIX and later by IEEE, there were two different frame formats. DIX came earlier, actually more appropriate and thus normally preferred by users and vendors. That forced IEEE to accept old DIX standard as new IEEE standard.

Once IEEE has accepted the old DIX standard, the Ethernet have two different frame formats, now named as Ethernet-I (the IEEE format which came later) and Ethernet II (original DIX standard which was standardized by IEEE later). We will look at both of them in the following. All later versions of the Ethernet use the same frame format and all versions of Ethernet are interoperable; that means older machines can communicate with newer switches and vice versa. How that is done is also discussed at the end of this chapter. Let us, first of all, begin with the frame structures of Ethernet. The classic Ethernet’s IEEE name was 802.3 and we will use that as the synonym for Ethernet in our course.

Frame structure

An Ethernet frame consists of 7 (Ethernet II) to 8 (Ethernet I) fields. A minimum size of the frame is 64 bytes and the maximum is 1518 bytes (including frame headers). When virtual LAN was introduced later, the maximum frame size was increased to 1522 bytes. Figure 16.5 depicts both formats. The Ethernet standard from IEEE is also known as 802.3 and this frame format is also known as 802.3 frame format.

In figure 16.5 the top part depicts the Ethernet II or DIX frame format and lower one depicts the Ethernet-I frame format. Both of them are valid formats but only the first one is used in practice. Both the frame formats differ at two places. The last bit of preamble is named as SOF (Start of Frame) and instead of 0, it has value 1. Second and more significant change is that Ethernet II have a field called Type which is replaced by a field called Length in the Ethernet I version. Let us look at both frame formats, field by field.

The frame always has the preamble in the beginning. Technically it is not part of the frame. Our discussion about synchronization earlier had a mention of preamble of type 10101…. The receiver gets alternate zeros and ones and synchronizes properly. The first seven bytes of the preamble in both formats are the same. The final byte in Ethernet II format is 10101010 while in Ethernet-I it is 10101011. The last bit is known as SOF or Strat of Frame.

The next is the Destination address. It indicates the MAC address of the receiver. In the case of Ethernet, it is 6 bytes or 48 bits long. A unicast address starts with a zero and identifies a single node. A multicast address begins with 1 and identifies a group of nodes. An address with all 48 bits as 1 is called broadcast address which identifies every node of the network. The destination address is any one of these three addresses.

A group address is used to map a network group. The IP also has many groups (for example, group of all routers) and give each group a typical group address. Whenever somebody sends to a group, all members will receive that packet. How is such functionality implemented by the lower layers? Ethernet solves it by providing these groups. An IP group is mapped to an Ethernet group and actual communication to all the group members is done by such multicast address. When a network layer passes a packet with a multicast address, the Ethernet frame generated to carry that packet also contain a multicast address containing those members. If an IP packet contains a group address as its destination address, it is transmitted over a specific group using the Ethernet multicast address 01-00-5E-xx-xx-xx, where the ‘x’ values depend on the group identifier. The xx-xx-xx-xx values are picked up from the last 23 bits of the IP multicast address and placed here with preceding zeros if need be.

The Type field is used for multiplexing multiple types of data the Ethernet frame carries within. It is possible that the IP layer running over Ethernet is IPv4 as well as IPv6. Thus there are two processes running, one with IPv4 and another with IPv6. The Ethernet card might receive one packet from IPv4 and another from IPv6. It has to multiplex both. We have already seen how TYPE field helps in multiplexing process. The Ethernet I does not have TYPE field but a length field instead. The length indicates the length of the frame. In a case of any truncation during transmission, it will help the receiver to detect. When both Ethernet I and Ethernet II are used in a network, whether the incoming frame contains a Length or Type field is hard to determine as there is no indicator in the header which tells us whether it is an Ethernet I or II. Fortunately, all Type values are more than 1500 and the maximum length of an Ethernet frame is 1500 bytes. That means, if a value is less than 1500, it indicates length and it is an Ethernet I frame. On the contrary, if it contains a value more than 1500, the frame is of type Ethernet II and this field is the Type field.

The next field is data or payload. Anything that is passed from the network layer is to be inserted here as is. We call that content a packet. Thus, in other words, network layer packet is inserted here. Sometimes the word datagram is also used instead of a packet but as long as this course is concerned, we will confine to word packet. The length of the data field has limitation from both the ends, lower as well as higher. Highest value is 1500 bytes and lowest value is 64 bytes2.

The minimum value does not confine a user to generate a data of very few bytes. For example, a user running a Telnet client might generate a two-byte data (say by typing ‘ls’). This is much lesser than 64. We need minimum 64, what is the solution? The sender uses the next field Padding. The Padding field can contain maximum 48-bit dummy data to bloat the frame to minimum size if need be. In above case (The ‘ls’ is being sent) a padding of 46 bytes will make the data + padding field length as 48 bytes when added with 18-byte header, comes to 64 bytes. Even when there is no data, the padding will be of maximum 48 bytes and when we add the 18-byte header, we will achieve the minimum required size.

The next field is called Checksum but is basically a CRC method that we have looked at. Sender calculates the CRC based on all other fields and receiver discards the frame if recalculating CRC does not match at its own end. Such a mechanism saves network layer to receive garbled content. However, Ethernet does not have any acknowledgment field and thus it does not send any ack back. When there is no ack coming back, there is no point in retransmitting. So, Ethernet does not retransmit either.

CSMA/CD

The first version of Ethernet allowed anybody to transmit in a broadcast domain at any point in time. That means there is a possibility of collision if two machines start sending at the same point in time. Machines, in the true sense, were (and still are) quite courteous and won’t transmit when they find somebody else already doing so but collide when two of them start almost simultaneously. The CS means Carrier Sense, that means machine sense carrier (the wire) before sending. If they sense anything being transmitted, they differ to transmit. MA means multiple access. This wired channel was accessible to all members of the network and hence this phrase. CD means collision detection. Every Ethernet card in the first version was capable of detecting if it is getting something other than what it is putting on the wire. In that case, they assume collision. The Ethernet cards of all collided nodes were designed to immediately stop once the collision was detected and deploy an algorithm called binary exponential backoff algorithm. Later versions of Ethernet did away with broadcast domain and

2 For learning about reasons for these values kindly refer to reference-1

allowed a point to point communication, in a way eliminating the possibility of collision and thus CSMA/CD is no longer in use.

The binary exponential backoff algorithm

This algorithm is about doubling the waiting period every time a collision occurs. Every node which collides run this algorithm. Let us call a time to travel to the farthest end of network and comeback, as t. This t value is the time slot used by this algorithm. A node normally transmits once somebody else has just completed transmission. Suppose the earlier sender completes the job at some time CurrentTime. The next transmission normally happens immediately at the Current time. If there is a collision, it will have to retransmit. It will recalculate the current time and calculate two slots (CurrentTime, CurrentTime + t) and (CurrentTime + t,, CurrentTime + 2t). Now it will choose any one slot at random and send in that slot. If the collision reappears, it doubles numbers of slots and tries again. The formal method is described in the following.

1. The sender senses the channel and sends if find idle. If the channel is busy, it will wait till it becomes free and sends only after waiting for a small time called interframe time.

2. While transmitting, the sender continues to listen to the channel. As long as it receives the same amount of voltage it is putting in, no problem. Otherwise, it understands that collision has taken place.

3. The sender now waits for a random period of time (either one or two time slots) and send in that time slot if nobody is transmitting. If this sender has chosen the second time slot and another sender has chosen first, this is possible.

4. Assuming that there are two senders who collided when both of them chooses from two available slots, the repeat collision has a probability of just 50% when both of them either chose first or the second slot together. Either of them if has chosen first while second has chosen second then they won’t collide next time.

5. If the collision reappears, both of them chooses one out of four slots at random and the collision probability now reduces to 25%. For all subsequent collisions, the interval is just doubled. When the interval reaches to 1024 slot in the case of 10 consecutive collisions, it remains fixed for 10 more repeat transmissions. If there is still a collision, the algorithm terminates with an error.

One typical argument against such method is; Instead of starting with just 2 slots, one can start using highest number of slots to reduce the possibility of collisions. On the other hand, one can argue that we can keep only two slots for each iteration.

Let us try to answer these queries. In most cases two senders are colliding and choosing two slots is the most optimum solution. If we use maximum value one may choose a 1023rd slot and another may choose a 1024th slot, it is possible that precious time is just wasted. On the other hand, a number of senders colliding cannot be predetermined. For example, if all students go to the lab together after a class and start their machines and start uploading latest assignment at the same point of time, it is possible that many student machines collide. In that case, if there are 50 machines colliding, one can only transmit if 49 of them chooses one slot and the rest chooses another. This is highly improbable. Increasing number of slots will soon reach to a value where the probability of only one sender chooses a typical slot is much higher and communication can proceed further.

Choosing a Point to Point domain

Another choice current Ethernet designers have made is to choose the point to point domain by preferring to use switches instead of hubs. Hubs broadcast data coming on any one port to all other ports while switch only sends data to a port where the receiver is connected to. That means switches allow multiple communicating parties to communicate with each other simultaneously.

Switches are better than a hub in two respects, first is they allow a port to port communication instead of broadcast and second, they also allow a frame to be stored if the destination port is busy. For example, B is receiving F1 in fig 16.7. Now another frame from some other user (assume E which is second last) also arrives at the fifth port where a node E is connected to, the port won’t send the frame over to port 3 where B is connected. It will store the frame and send only when port 3 is free. Thus B will receive both frames, un-collided and one after another.

The second advantage of the switch is that the backplane which connects all ports has much higher bandwidth than all ports collectively has. That means all ports can send and receive at the same point in time to allow a maximum amount of parallelism.

However, there is still a possibility that a collision may sneak in. When the sender is sending a frame and at the same point of time, it has to receive a frame from some other sender, the incoming and outgoing frames can collide with each other. The solution is to use a full duplex line where sending and receiving lines are separate and this possibility is also avoided.

Choosing a point to point domain has a definite advantage as collisions are reduced, throughput has increased. CSMA/CD was a poor technique as it performs poorer with increasing bandwidth and bigger networks. When a point to point links and switches are chosen, those issues vanished and Ethernet has become a de-facto standard.

Ethernet versions

We have already seen that the first version of Ethernet is known as classic Ethernet and provided 10 Mbps which was considered very good during that period. The second version was 100 Mb and known as Fast Ethernet. This was initially designed to interconnect multiple networks of 10 Mb each. There were some competitors like Fibre3 Channel and Fiber Distributed Data Interface (FDDI) and frame relay but Ethernet not only survived but eliminated all of them from networking technology arena.

3 The person who named it was British

The very IEEE committee which standardized the 10 Mb version also standardized 100 Mb version. They only did one thing, reduced the bit length by to 1/10th of the original. The first version allowed multiple topologies but from fast Ethernet onwards the Ethernet only allowed star topology.

There are a few choices of cables and coding schemes available to be used for Fast Ethernet. Kindly refer to reference 1 for the details. One of the most important things Fast Ethernet brought was the paradigm shift. The first version was shared channel broadcast type and Fast Ethernet was the point to point. The IEEE name of Fast Ethernet is 802.3u.

Paradigm shift by fast Ethernet

The first version allowed coaxial cables and also allowed more than one machine to connect using same wire. With Fast Ethernet, the only option allowed was to use a UTP cable which was much better, faster and less error prone. That helped fast Ethernet to operate at much higher speeds. From Fast Ethernet onwards, all connections were point-to-point. Thus every node is connected to a dedicated port of a switch which is not shared.

The minimum frame size was an option was actually due to the possibility of collision. Another restriction imposed in the first version was on maximum distance between any two nodes. In the first version, the maximum distance between any two nodes cannot exceed 2500 meters. When a point-to-point domain is chosen, both those restrictions imposed were lifted and the distance between two nodes now can be arbitrarily long. A machine can connect to a switch from an arbitrarily long distance and thus switches can also be used to connect two different networks. For longer distances, the only requirement for the sender to raise the signal power (amplitude) enough to outsmart the noise in the channel.

Ethernet started with CSMA/CD and forged ahead with continuous improvement with a change in time. It remained unfazed even 45 years after its inception. Very few, if any, technology has survived this long. Such a long and successful journey is due to many reasons but one of the most important is this paradigm shift.

Gigabit and further Ethernet

The gigabit Ethernet is yet another faster version of Ethernet. It was given a number 802.3z. The naming of Fast and Gigabit Ethernet indicates that they are an extension of the original design of 802.3 and not a separate technology. Many clever schemes were designed to make sure different types of USB cables, as well as FO cables, provide this gigabit speed. The version after Gigabit Ethernet is 10G Ethernet and the final one is 40/100 Gb which is quite huge speed. For more information, please consult either reference-1 or reference-2.

Though we will not discuss these versions of Ethernet in more details, there are a few things stand out. First, is choosing a smart coding to avoid positive DC voltage, another is flow control and the third is an auto-negotiation. Let us see all of them one after another.

Avoiding DC component

A DC component is a positive voltage in the signal. When a square signal is passing through a transformer, the DC component of a signal won’t pass through. To understand what a DC component is, consult the figure 16.8. The upper signal is centered around 0 and is considered a signal without a DC component. The lower signal which is not centered around 0 but some positive value is a signal without DC component.

Now the signal with DC component is decomposed into two parts in figure 16.9. You can see that the signal equals the summation of two parts, the first part is the same as the signal without DC component and another part is continuous positive voltage, which is actually a DC component.

The Fast and Gigabit Ethernet uses a clever coding scheme which makes sure such DC component is minimized during transmission. Both Reference-1 and 2 throws more light on this process.

Flow Control

Speed mismatch can occur if a classic Ethernet network is connected to Fast Ethernet or Fast Ethernet is connected to Gigabit Ethernet etc. For example, if a 10G Ethernet sender sends at full speed to a fast Ethernet node, which is currently very common, a fast Ethernet node can easily be swamped in a few seconds.

This problem is avoided by a simple trick. A special frame is sent by the receiver to the sender, known as a pause frame as and when it fears that it runs out of buffer while receiving frames.

The sender receives a pause frame; it waits for the period specified in that frame before transmitting next frame. During this period, the receiver processes the pending frames and be ready for next burst of frames.

Any machine can send the pause frame. A typical pause frame structure is presented in figure 16.10. you can see that a typical destination or multicast address is provided depending on who the recipient is. The Type value is provided as 88-08 (in hex), which is known as opcode for pause frame. Next two bytes contain a value from 0000 to FFFF. That value indicates time for which the sender should remain quiet. The recipient multiplies that value by 512-bit period and waits for that period. A bit period is an amount of time to send a single bit, lesser for high transmission lines. Increasing speed reduces a bit period.

Dual speed cards and auto negotiation

One critical reason one can attribute for Ethernet’s success is the auto-negotiation between dual speed cards. The dual or triple speed cards allowed smoother upgrades from lower versions of Ethernet to higher versions. Ethernet cards which can work at two or more speeds and choose an appropriate speed based on the capacity of the card at the other end were always there in the industry. When Fast Ethernet arrived, there were cards known as 10/100 cards which can work with both 10Mb as well as 100 Mb. When a user has an entire network running on 10 Mb with the hub or switch at all ports running at 10 Mb, buys a new machine with fast Ethernet card with 10/100 card, the machine can work with existing network without any problem. As soon as it realizes the other end port is working at 10 Mb, it starts functioning at 10 Mb. The user may go ahead and buy few more machines of the same type and all of them continue to function in the same fashion. When a user decides to upgrade its switch and buys a new switch, it will also have 10/100 ports. These new machines suddenly realized the better capacity of the other end and start working at increased speed. Those poor machines which still use old 10Mb cards can still function as the ports of the switch realize that those ports are of lower capacity so they slow down and work at 10 Mb only. Thus one can gradually increase machines with faster cards. Later on, when Gigabit Ethernet arrived, we had 10/100/1000 cards which can work at any one of those speeds. Thus it allowed heterogeneous nodes in the network and all of them can continue working. If ever a faster node is sending to a slower node, the flow control saves the day.

Summary

In this module, we have looked at how the MAC layer and Ethernet MAC layer works in particular. We have looked at various requirements of the Ethernet MAC layer and seen how it provides them. We have looked at the frame structure of Ethernet frame, two different types of frames used in Ethernet and the difference between them. We have also seen how Ethernet has grown from broadcast domain to point to point and increased the speed. We have seen the factors which help this tremendous growth and survival of almost 45 years.

References

1. Computer Networks by Bhushan Trivedi, Oxford University Press
2. Data Communication and Networking, Bhushan Trivedi, Oxford University Press