Dark Mode
Image
  • Wednesday, 16 October 2024
Computer Network-3: Transport Layer

Computer Network-3: Transport Layer


Computer Network-1: Overview - Outline

Transport Layer

Transport layer goal

Understand principles behind transport layer services:

  • Multiplexing-demultiplexing
  • Reliable data transfer
  • Flow control
  • Congestion control

Transport services and protocols

Network layer: logical communication between hosts

Transport layer: logical communication between processes

  • Provide logical communication between application processes running on different hosts.
  • Sender: breaks application messages into segments, passes to network layer
  • Receiver: reassembles segments into messages, passes to application layer
  • Two transport protocols available to Internet applications- TCP, UDP

Two principal Internet transport protocols

  • TCP: Transmission Control Protocol: Connection Oriented, Reliable, Guarantee Delivered, Not Real time, Acknowledgement, In order delivery.
  • UDP: User Datagram Protocol: Connection less, Non-Reliable, Non-Guarantee, Suitable for Real Time, Not Acknowledgement, Unorder delivery

Multiplexing and demultiplexing

Multiplexing

Multiplexing in the transport layer refers to the process of combining multiple data streams or connections into a single communication channel, thereby allowing multiple applications to share the same network resources efficiently.

 

There are different types of multiplexing techniques, including time-division multiplexing (TDM), frequency-division multiplexing (FDM), and wavelength-division multiplexing (WDM) and so on.

 

multiplexing at sender: handle data from multiple sockets, add transport header (later used for demultiplexing)

Demultiplexing

Demultiplexing in the transport layer is the process of extracting data from a single communication channel and delivering it to the appropriate receiving application. demultiplexing at receiver: use header info to deliver received segments to correct socket.

A screenshot of a computer  Description automatically generated

How demultiplexing works

host receives IP datagrams.

  • Each datagram has source IP address, destination IP address.
  • Each datagram carries one transport-layer segment.
  • Each segment has source, destination port number.

host uses IP addresses & port numbers to direct segment to appropriate socket.

A screenshot of a computer  Description automatically generated

Connectionless demultiplexing

Connectionless demultiplexing is a process performed by the transport layer in networking, specifically in protocols like UDP (User Datagram Protocol). In connectionless demultiplexing, the transport layer examines the incoming datagrams (packets) based on certain criteria to determine how to route them to the appropriate receiving application or process.

Connection-oriented demultiplexing

Connection-oriented demultiplexing is a process performed by the transport layer in networking, primarily in protocols like TCP (Transmission Control Protocol). In connection-oriented demultiplexing, the transport layer examines incoming segments based on various criteria to determine how to route them to the appropriate receiving application or process.

Connectionless transport: UDP

Why is there a UDP?

  • no connection establishment
  • simple: no connection state at sender, receiver
  • small header size
  • no congestion control.

UDP: User Datagram Protocol

UDP use: DNS, SNMP, HTTP/3

if reliable transfer needed over UDP (e.g., HTTP/3):

  • add needed reliability at application layer.
  • add congestion control at application layer.

UDP segment header

UDP payload size minimum 45 byte and maximum 1500 byte.

Internet checksum

Goal: detect errors (i.e., flipped bits) in transmitted segment.

Sender:

  • treat contents of UDP segment (including UDP header fields and IP addresses) as sequence of 16-bit integers.
  • checksum: addition (one's complement sum) of segment content
  • checksum value put into UDP checksum field.

Receiver:

  • Compute checksum of received segment.
  • Check if computed checksum equals checksum field value:
    • not equal - error detected.
    • equal - no error detected.

A white rectangular object with a black border  Description automatically generated

Question: Limitation of error checksum in UDP?

  1. UDP's error checksum is limited to error detection, not correction.
  2. It lacks mechanisms for retransmission of lost or corrupted packets.
  3. UDP relies on higher-layer protocols or applications for error recovery.
  4. It does not guarantee end-to-end reliability like TCP.
  5. UDP is suitable for real-time applications prioritizing low overhead and speed over reliability.
  6. Even though numbers have changed (bit flips), no change in checksum!

Principles of reliable data transfer

Reliable data transfer refers to a set of techniques and protocols used to ensure that data sent from one entity to another is delivered accurately and in the correct order, despite potential errors, losses, or delays in transmission. The principles of reliable data transfer include:

  1. Acknowledgment (ACK): The receiver sends acknowledgment messages to the sender to confirm successful receipt of data packets.
  2. Sequence Numbers: Each packet is assigned a sequence number to enable the receiver to reorder out-of-order packets and detect missing packets.
  3. Timeouts: A timer mechanism is used to trigger retransmissions if the sender does not receive acknowledgments within a specified time period.
  4. Checksums: Error detection codes, such as checksums, are included in packets to detect corruption during transmission.
  5. Pipelining: The sender may be restricted to sending only packets with sequence numbers that fall within a given range.
  6. Selective Repeat: The receiver individually acknowledges correctly received packets, allowing the sender to retransmit only the missing or damaged packets.
  7. Flow Control: Techniques are employed to ensure that the sender does not overwhelm the receiver with data, preventing congestion and potential packet loss.

By adhering to these principles, reliable data transfer protocols ensure the integrity and order of transmitted data, even in the presence of network errors or congestion.

A screenshot of a computer  Description automatically generated

rdt1.0

Reliable Data Transfer (RDT) 1.0 works on a perfectly reliable channel, that is, it assumes that the underlying channel has:

  • No bit errors.
  • No loss of packets

This transfer of data is shown by using FSM (finite state machine) for sender, receiver:

  • sender sends data into underlying channel.
  • receiver reads data from underlying channel.

Sender Side: When the sender sends data from the application layer, RDT simply accepts data from the upper layer via the rdt_send(data) event. Then it puts the data into a packet (via the make_pkt(packet,data) event) and sends the packet into the channel using the udp_send(packet) event.

Receiving Side: On receiving data from the channel, RDT simply accepts data via the rdt_rcv(data) event. Then it extracts the data from the packet (via the extract (packet, data)) and sends the data to the application layer using the deliver_data(data) event.

rdt2.0

Reliable Data Transfer (RDT) 2.0 protocol bit errors that are present in a channel while transferring it may be the bits in the packet are corrupted. Such bit errors occur in the physical components of a network when a packet is transmitted, propagated, or buffered.

Users send ACK (acknowledgement, i.e., the packet that received is correct and it is not corrupted) or NAK (negative acknowledgement i.e. the packet received is corrupted). In this protocol we detect the error by using Checksum Field.

Checksum: Checksum is a value that represents the number of bits in a transmission message.

To check the checksum value calculated by the end user is even slightly different from the original checksum value, this means that the packet is corrupted.

Error Detection: The mechanism that is needed to allow the receiver to detect bit errors in a packet using checksum is called Error Detection.

Receiver Feedback: When sender sends packet to receiver, it's positive (ACK) and negative acknowledgement (NAK) replies in the message dictation scenario are an example of such feedback. A zero value indicates a NAK and a value of 1 indicates an ACK.

Sender Side: The send side of RDT 2.0 has two states.

  • In one state, the send-side protocol is waiting for data to be passed down from the upper layer to lower
  • In the other state, the sender protocol is waiting for an ACK or a NAK packet from the receiver( a feedback).

A diagram of a call center  Description automatically generated

Figure: Sender Side & Receiver Side

Receiver Side:

  • ACK: If an ACK packet is received i.e rdt_rcv(rcvpkt) && is ACK(rcvpkt), the sender knows that the most recently transmitted packet has been received correctly and thus the protocol returns to the state of waiting for data from the upper layer.
  • NAK: If a NAK is received, the protocol re-transmits the last packet and waits for an ACK or NAK to be returned by the receiver in response to the re-transmitted data packet.
  • N.B: When the receiver is in the wait-for-ACK-or-NAK state, it cannot get more data from the upper layer, that will only happen after the sender receives an ACK and leaves this state. Thus, the sender will not send a new piece of data until it is sure that the receiver has correctly received the current packet, it's known as Stop and Wait Protocol.

Question: What is Stop-wait protocol?

Sender sends one packet, then waits for receiver response.

Question: how to recover from errors?

  • Acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK.
  • Negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors.
  • sender retransmits pkt on receipt of NAK.

What happens if ACK/NAK is corrupted?

The sender doesn't know what happened to the receiver! can't just retransmit: possible duplicate.

How to handle duplicate?

  • sender retransmits current pkt if ACK/NAK corrupted.
  • Sender adds sequence number to each pkt.
  • Receiver discards (doesn't deliver up) duplicate pkt.

rdt2.1

sender:

  • seq # added to pkt.
  • two seq. #s (0,1) will suffice.
  • must check if received ACK/NAK corrupted.
  • twice as many states: state must "remember" whether "expected" pkt should have seq # of 0 or 1

receiver:

  • must check if received packet is duplicate: state indicates whether 0 or 1 is expected pkt seq #
  • note: receiver cannot know if its last ACK/NAK received OK at sender.

rdt2.2

How RDT 2.2 is NAK free?

in the RDT 2.2 is the exclusion of Negative acknowledgment. In RDT 2.2 a new field is added to the packet at receiver side acknowledgment with the sequence of the packet sent, this enables the sender to compare the sequence number. If the sequence number doesn't match the sender acknowledgment the received acknowledgment packet is corrupted, and it resends the packet. This packet gets rid of the use of negative acknowledgment. The communication between sender and receiver is enhanced as each keeps a record of the packets sent and received.

  • Instead of NAK, receiver sends ACK for last pkt received OK. Receiver must explicitly include seq # of pkt being ACKed
  • Duplicate ACK at sender results in same action as NAK: retransmit current pkt.
  • As we will see, TCP uses this approach to be NAK-free.

rdt3.0

Before RDT 3.0, RDT 2.2 was introduced to account for the channel with bit errors in which bit errors can also occur in acknowledgments. As the design of RDT 2.2 is a stop and wait for protocol. If there is a network issue and the acknowledgment/packet is lost. The sender waits infinitely for it.

Question: How RDT 3.0 solves the problem like sender waits infinity due to acknowledgment/packet is lost?

Underlying channel can also lose packets (data, ACKs) can be solve by checksum, sequence #s, ACKs, retransmissions but it's not enough.

RDT 3.0 introduces a timer at the sender side if the acknowledgment is not received within a particular time the sender resends the packet. This method solves the issue of packet loss.

Question: What is the approach for channel with error and loss?

Approach: sender waits "reasonable" amount of time for ACK

  • retransmits if no ACK received in this time.
  • if pkt (or ACK) just delayed (not lost): retransmission will be duplicate, but seq #s already handles this!

Receiver must specify seq # of packet being ACKed timeout.

use countdown timer to interrupt after "reasonable" amount of time.

Sender Action:

State-1(Top-Left): This is the Start state in the sender's which is called wait for call 0 from above. It waits till it receives a message to start from the application layer.

State-2(Top-Right): This state confirms whether the receiver has received the packet or not. state check that if the received acknowledgment is not corrupt, has the sequence number "1", and is reached within the time. If these two criteria are satisfied the execution moves to the next state else the state resends the packet.

State-3(Bottom-Right): This state in the sender's is called wait for a call 1 from above. It waits till it receives a message to start from the application layer.

State-4(Bottom-Left): This state confirms whether the receiver has received the packet or not. state check that if the received acknowledgment is not corrupt, has the sequence number "0", and is reached within the time. If these two criteria are satisfied the execution moves to the next state else the state resends the packet.

Receiver Action:

RDT 3.0 Action:

A screenshot of a computer  Description automatically generated A screenshot of a computer screen  Description automatically generated

Performance of rdt 3.0

Stop-and-wait operation:

For example: 1 Gbps link, 15 ms prop. delay, 8000-bit packet

Time to transmit packet into channel:

A black text with a line  Description automatically generated

Utilization fraction of time sender busy sending

A mathematical equation with numbers and lines  Description automatically generated

Pipelining: increased utilization

pipelining: sender allows multiple, "in-flight", yet-to-be-acknowledged packets.

  • range of sequence numbers must be increased.
  • buffering at sender and/or receiver

Utilization fraction of time sender busy sending

A mathematical equation with numbers and symbols  Description automatically generated

3-packet pipelining increases utilization by a factor of 3.

Go-Back-N

Go-Back-N is an Automatic Repeat Request (ARQ) protocol, in which the sending process continues to send a number of frames specified by a window size even without receiving an acknowledgement (ACK) packet from the receiver. It is a transmit window size of N and receive window size of 1. It can transmit N frames to the peer before requiring an ACK.

Working of Go-Back-N ARQ:

Let's assume that there are 11 frames to be sent. These frames are represented as 0,1,2,3,4,5,6,7,8,9,10, and these are the sequence numbers of the frames. The window size as 4,

Go-Back-N ARQ Go-Back-N ARQ Go-Back-N ARQ Go-Back-N ARQ Go-Back-N ARQ Go-Back-N ARQ

Reference: https://www.javatpoint.com/go-back-n-arq

Features of the Go-Back-N (GBN) protocol:

  • Sliding window mechanism
  • Sequence numbers
  • Cumulative acknowledgements
  • Timeout mechanism
  • NACK mechanism
  • Simple implementation.

Example 1: In GB4, if every 6th packet being transmitted is lost and if we have to spend 10 packets then how many transmissions are required?

Solution: Here, GB4 means that N is equal to 4. The size of the sender's window is 4.

Go-Back-N ARQ

Go-Back-N: Sender

    • sender: window of up to N, consecutive transmitted but unACKed pkts, k-bit seq # in pkt header

A screenshot of a computer  Description automatically generated

  • cumulative ACK: ACK(n): ACKs all packets up to, including seq # n
  • on receiving ACK(n): move window forward to begin at n+1
  • timer for oldest in-flight packet
  • timeout(n): retransmit packet n and all higher seq # packets in window

Go-Back-N: receiver

ACK-only: always send ACK for correctly-received packet so far, with highest in-order seq #

  • may generate duplicate ACKs
  • need only remember rcv_base

On receipt of out-of-order packet:

  • can discard (don't buffer) or buffer: an implementation decision
  • re-ACK pkt with highest in-order seq #

Example:

A screenshot of a computer  Description automatically generated

RDT 3.0 Vs Go-back-N

Answer: In Go-Back-N

  • All packet sent
  • In order delivery
  • Pipelining Concept
Aspect RDT 3.0 Go-Back-N
Protocol Type Reliable data transfer (RDT) protocol Sliding window protocol
Feedback Mechanism Positive acknowledgments (ACKs) and NAKs Positive acknowledgments (ACKs) only
Error Handling Uses NAKs to request retransmission Uses cumulative ACKs
Retransmission Only retransmits packets for which NAK is received Retransmits all packets from the damaged one onwards
Buffering Receiver buffers out-of-order packets until all preceding packets are received Receiver buffers all received packets until the expected one
Selective Repeat Supports selective repeat Does not support selective repeat
Complexity More complex due to NAK handling Less complex due to cumulative ACKs

Selective repeat

It is also known as Sliding Window Protocol and used for error detection and control in the data link layer.

In the selective repeat, the sender sends several frames specified by a window size even without the need to wait for individual acknowledgement from the receiver as in Go-Back-N ARQ. In selective repeat protocol, the retransmitted frame is received out of sequence.

Steps:

receiver individually acknowledges all correctly received packets

  • buffers packets, as needed, for eventual in-order delivery to upper layer

sender times-out/retransmits individually for unACKed packets

  • sender maintains timer for each unACKed pkt

sender window

  • N consecutive seq #s
  • limits seq #s of sent, unACKed packets

Sender:

data from above:

  • if next available seq # in

window, send packet timeout(n):

  • resend packet n, restart timer.

ACK(n) in [sendbase,sendbase+N]:

  • mark packet n as received.
  • if n smallest unACKed packet, advance window base to next unACKed seq #

Receiver:

packet n in [rcvbase, rcvbase+N-1]

  • send ACK(n)
  • out-of-order: buffer
  • in-order: deliver (also deliver buffered, in-order packets), advance window to next not-yet received packet.

packet n in [rcvbase-N,rcvbase-1]

  • ACK(n)

otherwise:

  • ignore

Features of Selective Repeat:

  • Receiver-based protocol
  • Each packet is individually acknowledged by the receiver
  • Only lost packets are retransmitted, reducing network congestion
  • Maintains a buffer to store out-of-order packets
  • Requires more memory and processing power than Go-Back-N
  • Provides efficient transmission of packets.

A screenshot of a computer  Description automatically generated

Question: Advantages of selective repeat over Go-Back-N?

Answer: Bandwidth and channel utilization is better

# Go-Back-N Selective Repeat
Definition If the sent frame is found suspected then all the frames are re-transmitted from the lost packet to the last packet transmitted. It only those frames are re-transmitted which are found suspected.
2. Sender Window Size Sender window size of is N. Sender window size is also N.
3. Receiver Window Size Receiver window size is 1. Receiver window size is N.
4. Complexity It is less complex. It is more complex.
5. Sorting In, neither sender nor at receiver need sorting. In, receiver side needs sorting to sort the frames.
Acknowledgement Acknowledgement is cumulative. Acknowledgement is individual.

For Example:

Let's see how we can transmit data using the SRP. We divide our sample data into 6 data packets or frames: 0,1,2,3,4,5

Assuming the window size is 2.Hence, we transmit two frames and wait for the receiver to acknowledge the frames transmitted before sending the next frames. In case of a missing or unacknowledged frame, we need to resend it before proceeding with the next set of frames.

No Error in Transmission:Let's start sending the packets using the SRP. We send the first two frames to the receiver and wait for the acknowledgment:

two frames

As we can see, the receiver successfully received and acknowledged the first two data frames. One crucial point is that when the sender sends a frame, it waits for a specific time to get a response. In this case, we receive responses from the receiver within the waiting time of each frame. Hence, we move on to the next 2 data frames.

Frame Is Lost:Let's discuss a scenario when a frame is lost during the transmission:

lost frame

Here,frame 2 is lost during the transmission.Hence, the sender waits for a specific amount of time to get a response from the receiver. In this case, we received a negative acknowledgment for frame 2. Therefore, we need to resend frame 2 before we proceed further:

frame resend

Acknowledgment Is Lost:Let's take a look at another situation when the acknowledgment of a frame is lost during transmission:

acknowledgment lost

In this case, the receiver successfully receives frames 4 and 5, butthe acknowledgment of frame 5 is lost.Hence, the sender waits for a specific amount of time in order to receive an acknowledgment for frame 5. After the waiting time is over, the sender sends frame 4 again:

frame 4

Reference: https://www.baeldung.com/cs/selective-repeat-protocol

Connection-oriented transport: TCP

  • point-to-point: one sender, one receiver
  • Reliable, in-order byte steam: no message boundaries"
  • full duplex data: bi-directional data flow in same connection
  • MSS: maximum segment size
  • Cumulative ACKs
  • Pipelining: TCP congestion and flow control set window size
  • Connection-oriented: handshaking (exchange of control messages) initializes sender, receiver state before data exchange.
  • Flow controlled: sender will not overwhelm receiver.

TCP segment structure

Sequence numbers: byte stream "number" of first byte in segment's data.

Acknowledgements: seq # of next byte expected from other side.

Question: Is it possible for an application to enjoy reliable data transfer even when the application runs over UDP? If so, how?

Answer: Yes, it is possible for an application to achieve reliable data transfer even when running over UDP. This can be accomplished by implementing reliability mechanisms at the application layer itself, such as retransmission of lost packets, acknowledgment of received packets, sequencing of packets, and error detection and correction. These mechanisms can provide reliability similar to TCP's reliable data transfer, albeit at the cost of additional complexity and overhead in the application code.

Comment / Reply From