13 Communication at Data Link and Transport Layer

Prof. Bhushan Trivedi

Introduction

Communication at data link layer is very important as it is between two adjacent machines or rather two data link layer cards. The way communication between two peer entities takes place is also known as a protocol so we will be in a way talking about how protocols govern the process of communication at the data link layer. Though our concentration remains on data link layer, many issues that we discuss also affects transport layer. The reason is, what data link layer does for two adjacent machines, transport layer does almost the same for client and server (actual sender and recipient). That is why most of the issues that we discuss here will also be applicable to the transport layer protocols like TCP and UDP. We will mention about some typical cases which have more significance at the transport layer as and when there is a need. The word ‘segment’ is used to indicate transport layer data unit while word ‘frame’ is used to indicate a data link layer unit.

Communication between two data link layer entities can happen in multiple ways and the process chosen to communicate depends on many things including the connection being operated upon is wired or wireless.

The process of communication is also affected by the choice of data transfer, connection-oriented or connectionless. Connection-oriented transfer includes how sender sends a connection request and how it is honored or rejected by the receiver and how complexities of that process are managed. Let us begin our discussion with some fundamental concepts like sender, receiver, acknowledgment, timer, timeout etc.

Sender and receiver

Every communication process has one sender and one receiver. Most of our discussion will be based on considering one server and one receiver. However, there are cases where multiple senders or multiple receivers are present. Most of the things we discuss here will also be applicable to the multiple sender-receiver cases. Multiple sender-receiver cases have some additional issues like arbitration between multiple potential senders etc. which we will look at when we discuss the MAC layer in the next and few more subsequent modules. Sender and Receivers have many things to manage, for example, buffers for frames which are sent but not received by the sender, buffers for frames received out of order at the receiver, timers for sent frames and retransmit if need be at the sender, and responding back using an acknowledgment and so on. We will learn about those things in this module.

Acknowledgement

In the noisy channel, when the data is likely to be lost or corrupted, there has to be a mechanism for the sender to learn about such events. A simple method to do so is called acknowledgment or ack for short. It is an indicator that serves the purpose of confirming the delivery of the frame at the receiver’s end. Both frames and their acks are numbered and thus help in unambiguously identifying the frame received. The CRC like mechanism is deployed by the communicating parties to determine if the frame is corrupted.

Assigning sequence number is trickier than it seems at the first glance. The simplest method to number frames from 1 and increment it by one every time sender sends a new frame. There are two problems with this approach. First, a sequence number is a field (or variable) which is always of a fixed size. The number cannot go beyond and wraps around. For example, a 3-bit number cannot go beyond 7 (if starts from 0). The size of the number determines when it wraps around. Sequential numbering scheme has another problem when the segments are to be fragmented in transit.

Let us try to understand. Suppose if we sent segments numbered as 1,2,3 when we have encountered a case where segment number 2 is to be fragmented in the middle of transmission, how do the intermediary number both these fragments is a problem. It cannot change to 2 and 3 as 3 is already numbered. It cannot be anything else like 2.1 and 2.2 as the receiver has no idea whether there is 2.3 or not and also what if 2.2 is to be fragmented later. Keeping a floating point number as a field also is not directly possible. However, TCP solves the problem with a very clever scheme.

TCP numbers the segment as the first data byte in the segment. For example, if TCP sends a segment with sequence number 124 with the content of 120 bytes, the next segment will have sequence number 244 (124 + 120). Now if the first segment is to be fragmented into two segments of size 100 and 201, they will be numbered as 124 and 224(124 + 100), indicating the byte they begin with. TCP considers the sender’s data as a stream. It counts bytes one after another and number each byte. When a sender sends, it looks at the number of the first byte and numbers the frame accordingly. The only point to note is that the first byte is not given a number as either 0 or 1 but a different value. All subsequent bytes will be given numbers accordingly. For example, the first byte is given a number 2500, the next byte is given 2501 and the 100th byte is given number 2599 and so on. The reasons will soon be clear.

Let us take one example to understand. Assume TCP decides to give the number 2500 to the first byte of the data it starts transmitting. This number 2500 is known as the initial sequence number. Also assume that TCP sends 1000 bytes in the first segment, 1500 in the second segment and 1000 again in the third. You may ask how these numbers are decided. The size of the segment is decided based on many things including the physical layer’s capacity. TCP tries to send as much data as it can in every segment but only for a specific period of time. Once that period is elapsed, it has to send data. So when that time arrives, TCP sends whatever size of data accumulated from the application so far.

In above case, TCP sends bytes from 2500 to 3499 in the first segment (total 1000 bytes), sends 3500 to 4999 in the second segment (total 1500 bytes) and 5000 to 6000 bytes in the third segment (total 1000 bytes). The first segment is numbered as 2500, second is named as 3500 and third is named as 5000. The TCP ack is always defined as ‘next byte expected’. That means, when the first segment is received at the receiver’s end, it sends back the next byte it expects.

1 This happens when the intermediary router cannot send more than 100-byte segment. 100 bytes is little too small value for a real case but this is done to simplify the explanation.

It has received bytes till 3499 and expects 3500 as the next byte, so that is going to be the ack value.

Table 1 Sequence and ACK numbers in TCP

Segment no.	ACK in scheme 1	byte Starting	Last byte	Sequence no.	Length	ACK in scheme 2
1	1 (frame no)	0	999	2500	1000	3500 (next byte expected)
2	2	1000	2499	3500	1500	5000
3	3	2500	3499	5000	1000	6000

Unlike TCP, a data link layer is not required to number like this in most real cases as they don’t need to fragment their frames. The wired layer like Ethernet does not provide ack and does not expect retransmission, though it checks if there is an error in the received frame. In the case of wireless transmission, the most popular Wi-Fi only sends one frame at a time and provide a sequence number based on frame number than a byte number.

What should a data link layer (or a transport layer) do when a corrupted frame arrives? In most cases, the receiver does not send the ack back and the sender retransmits after timing out. However, some protocols have provision for sending a negative ack. A negative ack confirms a corrupted frame receipt and thus the sender retransmits without waiting for that frame to timeout. Negative ack, however, is not used by most commercial protocols. When the sender retransmits after timeout and receiver only acks the uncorrupted frames, the scheme is known as positive acknowledgment with retransmission (PAR).

Piggybacking

When the traffic flows in both directions, a better form of acknowledgment is possible. The receiver attaches the ack to the traffic it originates and sends to the sender.

This process is known as piggybacking and the ack is known as piggybacked ack. Look at figure 15.1. The sender sends Frame 1,2,3, and 4 and the receiver sends the frame 11,12,13 and 14. You can see that the ack is piggybacked both by the sender and the receiver2.

Piggybacking is good as it saves bandwidth. The special acknowledgment frames are not needed now and the network bandwidth is saved. However, there is a new problem emerges now. The receiver generates a frame depends on the time user generates reverse traffic. For example, the sender is a browser which sent the URL to the web server, now if the web server takes time in getting the requested page from the database or need user’s consent, it might take a while. By the time the sender’s TCP times out and resend. That defeats the purpose of saving the special ack frame. It is better if a special ack frame is sent in such cases. An additional timer is used here and if the receiver’s next traffic is delayed beyond a specific period of time (500 nsec for TCP) a special ack frame is sent and piggybacking is not used. The receiver needs to run an additional code for these additional timers and also need to take care of such timeouts.

Timers

We have mentioned timers a few times during our discussion. Let us throw some more light on the issue. Timers are software driven entities which increment or decrement time. One can set specific time values for timers. When the timer completes that period, a timeout event is said to have occurred. In real world operating systems, timers send interrupt signal at the timeout event.

Sending and receiving windows

When the sender sends over a long and fat (high bandwidth) lines, many of the segments of frames can be on the flight before the ack arrives back. Normally sender estimates the ack time and determines how many frames (or segments if we consider transport layer), can be outstanding when an ack is expected. Consider a case where the distance and the bandwidth between the sender and the receiver are big enough for the sender to send three frames and while it is ready with fourth, the ack of the first is likely to arrive. In that case, the sender should be ready to send three frames and only then wait for the ack. That will keep the line busy. If the ack arrives on time, the sender can keep on sending continuously without taking any break. The only issue is, the sender may not know how many of the three frames it sent are already received by the receiver and thus must keep a copy of them in case any one of them needs retransmission. The sender keeps all such frames in a buffer popularly known as sender’s window. Similarly, the receiver also keeps all out of order frames together with unprocessed frames. Figure 15.3 describes one typical case. When F1 is sent, it took more time but the other frames took less time. The sender sends F1, F2, and F3 before the acknowledgment of F1 arrives. The sender’s window helps sender continue sending even in the case where the frames are being delayed. Similarly, the receiver also has kept F2 and F3 in the buffer until the F1 arrives eventually. The place where receiver stores its uncorrupted but out of order frames is known as receiver’s window. The receiver only sends frames up in order.

22You may be surprised to find that both of them are sending so why we call one party as the sender and another as the receiver. The better word is the initiator. You can see that the party on the left side is initiating and so it is better to be called initiator. However, we will follow the sender and receiver words even when both parties are sending to simplify the case where only one party is sending. Whenever only one party is sending, we call it sender and the other party as the receiver. When both of them are sending, we call the initiator of the communication as the sender.

One more interesting point to note. The ack of F2 and F3 have not arrived. Only when the F1 is received properly, the receiver acknowledges all three frame cumulatively by sending ack of F3. When a receiver is waiting for some frame’s ack, and some other later frame’s ack arrives, the sender assumes all frames prior to that acked frame are received by the receiver. This is called the idea of cumulative acknowledgment. The idea is really important because it saves receiver to respond back to all received frames. While a reverse traffic is expected, a receiver might forgo sending the ack for a valid frame. In the case of TCP, the standard allows acknowledging alternate frames.

Now you can see that why the receiver does not ack the frames F2 and F3 in 15.3. It is because if he would have sent, the sender would have misunderstood that all frames prior to that also are received at the receiver which includes F1. Figure 15.4 describes a case to illustrate the advantage of cumulative ACK. When F2’s ack is lost, in the normal case, the timer of F2 will time out and thus F2 needs to be resent. Fortunately, F3 is received properly and its ACK also arrives in time. This indicates all frames prior to F3 are received at the receiver, eliminating the need to retransmit F2.

Cumulative ACK can sometimes confuse the sender. Take two examples depicted in 15.5. F2 is lost in this case. The F3 is corrupted in the first case and not in the second case. The receiver has no option but to send ACK of F1 only. The sender has no clue whether F3 is properly received or not. Sometimes this type of ACK is also known as an ambiguous ack. Ambiguous ACK confuses the sender.

An interesting measure provided by TCP is called SACK or selective acknowledgment to thwart this problem. Instead of only sending the ack, the SACK option, if enabled, provides information about all correctly received frames and thus the ack is no longer be ambiguous. Such elaborate measures are not required at data link layer so there is no protocol which demands such selective acks at data link layer.

Sliding windows

An interesting characteristic of the sender and receiver windows is that they are sliding in the forward direction. Let us try to understand the meaning of word sliding in this context by an example.

Carefully observe the transmission depicted in figure 15.6. It shows how frames are sent one by one, received by the receiver and acked. The sender sends frame 1 to 8 while receiver acknowledges them in the same order. This is a simple case where no frame or ack is lost or delayed or corrupted. The sender’s window size is 4. That means it can send 4 frames without ack. Accordingly, a maximum number of outstanding frames at any given point of time cannot be more and thus sequence number is chosen to be a field of 3 bits. Thus the frames are numbered as 0, 1,2,3 and wrap around to 0 for the fifth frame. The difference is indicated in the figure by providing the sequence number and frame which the sender is sending as separate entities. For example, the combination F6, 1 indicates that sender is sending frame 6 with sequence number 1. The windows of sender and receiver are shown on respective sides. The receiver’s window is also shown to be of size 4 but it can be anything else. Sender and receiver’s windows do not need to be of the same size.

You can also see that the windows are moving in the forward direction. The sender’s window advances when a new frame is sent on the right-hand side. When the ack is received, it is shrieked from the left-hand size. The numbers keep on moving in the forward direction until wraps around. Once wrapped around, again the window starts moving in forwarding direction. Same thing happens with the receiver also. Whenever a frame is received, the window advances on the right-hand side. When the application reads the frames, the window advances from the left-hand side. You can now understand why these windows are known as sliding windows. One question may arise out of our discussion. What if the window is full? In the case of the sender, if the window size has reached four, it cannot send any frame further, it has to wait. In the case of the receiver, if the window size has reached 4, it has to drop any other out of order incoming frames.

The size of sequence number field

We have already seen that the size of the sequence number field decides when the number wraps around. TCP uses a 32-bit sequence number and is working fine so far. However, such a field cannot work at data link layer due to tremendously high-speed networks we have today. Let us try to understand by referring to an example.

The frame size is 1500 bytes and a bandwidth of 1.5 Mb. Every frame is given a unique sequence number incremented by 1 from the previous frame. Assuming a 32-bit sequence number, the sequence number wraps around after 232 (4294967296) frames.

In case of 1.5 Mb bandwidth, in one second 1500000 / 1500 = 1000 frames are sent. Thus every second total 1000 sequence numbers are used. In that case, it will consume 1000 * 60 * 24 sequence numbers in a day. That means it will take 4294967296 / 1000 * 60 * 24 days to consume sequence numbers. That turns out to be nearly 3000 days. Thus our sequence numbers take almost 8 years to wrap around. Thus a 32-bit sequence number is good enough.

On the contrary, if a conventional TCP sequencing is used with 32-bit sequence number on a 10 Gb line, an altogether different situation arises. A 10-Gb line sends data at 1010 bits per second, that means little more than 109 bytes per second. 232 is approximately 2 * 106. That means the number wraps around after approximately after 2 * 106 bytes sent. That means in a single second, it wraps around 5000 times! That clearly indicates that a 32-bit sequence number is just unacceptable. The TCP provides window scale factor option for this case when it is used over a fast link.

The ack number should also bear the same size. One can easily understand that a proper size of sequence and ack number is critical in designing the frame structure.

Duplicate frames

Another important point to consider is, how a receiver or sender handles the case of duplicate frames. Look at the case depicted in the figure 15.7.

The sender sends F1, gets the acknowledgment of it, sends F2, ack of which is lost, and F2 is resent after a timeout. The receiver receives a duplicate copy of F2. What should the receiver do? He has a few options. Here is the list.

1. Accept the frame and resend the acknowledgment

2. Accept the frame and do not send an acknowledgment

3. Drop the frame and do not send an acknowledgment

4. Drop the frame and resend the acknowledgment

The first two options are not acceptable as they make the network and eventually the application layer accept a duplicate frame. That means they get the same piece of the message twice. This might not be troublesome in some cases as we may find a para in a mail being duplicated. That might surprise or irritate us but nothing more. However, if that piece of information is an online transaction where our ₹1,000,00 are deducted and deposited to somebody else’s account, it is altogether a different thing. In the era for IoT, if that piece of information indicates the dosage of the insulin pumped into the patient’s body, the double dose might kill the patient.

So we need to choose from last two options. If we do not send the ack, the sender again times out and resend the same frame and we are into the kind of a deadlock so that option is also not preferred. The only option that is acceptable is to send the ack back so the sender understands that the receiver has indeed received the frame and send the next frame. We will not give that frame content to the network layer and actually drop the frame. This is the way to handle duplicate frames.

Retransmission

Any communication process is incomplete without a strategy for retransmission. A frame is to be retransmitted when it is expected to be lost. However trivial it looks like, it is often one of the most complex issues. More often at transport than a data link layer. For example, how to set the retransmission time? If we set a pessimistic value, we may lose important time when the frame is lost much earlier. If we set a lesser value, the sender will unnecessarily timeout and retransmit when not needed. It results into both, wastage of network bandwidth and, unnecessary additional processing at the receiver. We will later see how TCP decides this timeout value and how it handles this.

Another issue in retransmission is related to receiver’s window size. In a simple solution, a receiver’s window is restricted to just one. That means the receiver can only accept the current frame and no other frame. Any out of order frame received is sent to a dustbin. That means, if a sender times out for any frame, all subsequent frames must be retransmitted. This strategy is called go back n and is described in figure 15.8. Frames are sent one after another, F1 and F2 are received properly and F3 is lost. The receiver expects F3 and won’t accept any other frame. That means when the sender sends F4 to F8 and all of them are properly received at the other end, they are all not considered by the receiver. The sender once timed out, decides the resend F3, also continue to send other frames thereafter, and the sender will now accept those frames and acknowledge. This seems to be a wasteful strategy, but sometimes we need it. We will hold off this discussion after discussing the other, more prevalent strategy, called selective repeat next.

The selective repeat strategy is depicted in the figure 15.9. In this strategy, the receiver accepts out of order frames but do not give them to the application. When the frame in order arrives, these frames are passed up.

The case is quite similar to the earlier case, here also we assume frame F3 is lost and all other frames from F4 to F8 are received properly at the other end. The different is, the sender only needs to retransmit F3 now. Once the receiver correctly receives the F3 frame, it accepts all other frames from F4 to F8 and passes all the contents of the frames from F3 to F8 to the network layer. The sender does not need to transmit all frames but selectively those which are lost (in our case only F3), hence the name selective repeat is provided.

Here are the consequences of the go back n strategy.

1. The receiver won’t be in a position to accept any out of order frames.

2. Receiver logic is simplified, it only accepts the frame it has to and nothing else.

3. The receiver requires less memory, which can only hold the current frame

4. In the case of a receiver having either of the processing or memory constraints, go back n is quite useful.

Point no. 4 needs some elaboration. Consider a mobile phone receiving a movie from a web server. The web server might send huge frames to the mobile phone. The memory and processing power of the mobile phone does not allow multiple out of order frames to be stored on the phone. Consider another case of a city’s smart electricity meter to accept and process incoming data from the electricity company’s web server. The smartphones of today might have gigabits of memory but the smart meters do not have that much amount of memory or even processing power. Go back n strategy might not be all that useless for such cases.

The selective repeat strategy is obviously better when the receivers are desktops or laptops or even servers residing at various locations of the world. However, this advantage of this better strategy does not come without a cost. The receiver now must be able to store all out of order correctly received frames from all connections, must have logic to deal with such out of order frames, compiling them together and send them up when the ordered frame arrives and so on. TCP has all those component built in which makes it quite a heavy protocol. Whenever there is a long and high bandwidth data is communicated selective repeat provides a distinct advantage. Consider a case of 500 Mb Satellite link of the distance about 3 lakh kilometers. Another case is of 40 Gb transcontinental line with the delay of 30 sec. A go back n would lose a huge amount of data for every frame lost.

Summary

In this module, we looked at how data transmission happens at the data link and transport layer. We have seen various terms like retransmission, sender, receiver, timeout, timer, go back n and selective repeat associated with data communication. We also have seen how sender and receiver windows are managed and also how windows slide in the forward direction. We have seen that selective repeat being a better technique, sometimes inferior to go back n as the receiver does not have the amount of memory of processing power to manage out of order frames.

References

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