NUS CS MODS: CS2105: Lecture 4 - UDP, Reliable Protocol

Transport Layer Services

Transport services and protocols

- Provide logical communication between app processes running different hosts.

They communicate though sockets

- Run in end system

Send sides: Breaks app messages into segment passes to network

RCV side: Reassembles segments into messages passes to app layer.

When the socket is called, the upper layer might be http that attach a large files, the transport layer will chop it up and assemble it (segment) at the recieving side

From the application pov, it makes it feels like they are directly connected to the other host.

Transport vs Network

Transport: Logical Communication between PROCESSES

- Replies on, enhance network layer services

Network Layer: Logical communication between HOSTS

- Unreliable "best effort"

This services is generically unreliable, there is no guarantee of the performance

Difference between host and processes

One host can have multiple processes.

Connectionless Transport: UDP

UDP: User Datagram Protocol

UDP adds very little service on top of IP

1. Connectionless multiplexing/ de-multiplexing

Connectionless means no handshaking before connecting

Process to process communcation

We use the port number to defereitaite the different types of processes

2. Checksum

IP is the network layer.

UDP transmission is UNreliable

- Often for streaming multimedia

To achieve reliable, need something on top of UDP

= Use TCP at transport layer

- Application implements error detection and recovery mechanisms

Connectionless De-Multiplexing

The operating system will gen the port number

But for server side, they must generate itself and let it known to the hosts

The server process will specify the ip address of itself such that when the server recieve the packet it will correctly be demultiplex.

The key point: For all the segments, as long as they are specifying the same destination, all packets well be delievered to the same socket.

This is not the same for TCP as for each TCP get a indiviudaul socket for individual client.

Encapsulation

The transport layer will

- chop packet if its too large

- Addes a packet header

- This is when it is called a segment

UDP: Segment Header

Length: Entire of UDP packet in bytes

Checksum: Check if there is bit errors

Remaining: application data

Reason why some app use UDP

- No need handshake

- Simple: No guarantee of anything

- Packet header is shorter than TCP

UDP: CheckSum

Goal: Detect errors in recieved segments (ie flipped bits)

Computation:

1. Treat UDP segment as a sequence of 16 bit integer

2. Apply Binary addition on every 16 bit integer

(Check sum is init as 0)

Try to add all 16 bits together

3. Carry over sfb if any

4. Comput 1's complement to get UDP checksum

<Insert slide 12 table>

How to use the checksum?
Use the binary summation of all the 16 bit integers,

You would expect to get the same final sum and when we add same check sum to see if we get the same sum.

If there is a bit flips, the sum will not be same.

Principles of reliable data transfer

How can we provide a reliable data transfer at transport layer?

If its realible , it means that all data be send in order and no data is lost.

We have a assumption that the layer below transport layer is relible and has already set up the connection (But in fact it isnt)

Reliable data transfer (RDT): Interface

udt_send() is called by rdt to transfer packet over unreliable channel to receiver

udt_rcv() is called when packet arrives on rcv side of channel

Getting started

- Consider only unidirectional data transfer

- Control info flow on both direction

- Use FSM (finite state machines) to specify sender and reciever

FSM diagrams shows the states which are defined as circle with arrows.

Any entity can be in any of the states at a point

During transition, we have a label (Denoted as an arrow) to show the state transition

This is specify by the corresponding actions

RDT1.0: Reliable transfer over reliable channel

- Underlying channel perfectly reliable

- Separate FSM for sender and receiver

Each side only have one transition to itself.

What the sender needs to do is to wait for call from above (the need to transfer data from upper application layer) When that happens,there is a transition where the sender use the data to make a packet. That includes checksum, packet header etc

Receiver: When it is waiting, a transition happen when the lower side deliever a packet to the reicever. The layer will extract the actual application layer data from the packet and deliever the data upwards

RDT2.0: Channel with Bit Errors

- Some of the bits get flipped

- Packets might be loss/dropped

How can we handle these bit error?

We can use checksum (receiver) to check if bit flipped happen?

How are we going to change to get the right packet.

We can give a feedback

- Acknowledge (ACKs) : Positive feedback, tells sender that received is OK

- Negative Acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors

Summary Mechanisms:

- Error detection

- Feedback

RDT2.0 in actions

Correct

1. sender send packet1

2. reciever send back a ACK

3 sender send next packet

Corrupted

1. Sender send packet1

2. Receiver send back NAK

3. Sender resends the packet1

Sender sends one packet at a time then waits for receiver to response

RDT2.0: FSM specification

Insert 23>

The differences are shown in red

Differences:

Sender

Have two states

It has to wait for the feedback from the reciever before sending the next packet

Checksum has to be place together to the packet when send to the reciever

In waiting states, it depends on what kind of response from reciever

- ACKs : Next packet

- NAK: Resent the previous packet

Reciever

When it receive, it checks if packet is corrupted.

If it isn't: Sends a ACK to sender, It extracts and send data to up to the upper layer

But RDT2 has a fatal flaw!

What if the ACK and NAK is corrupted??

If we try to use feedback, there is always a chance that it will send a corrupted packet. It is like an infinite loop

Corrupted ACK: We just have to make sure that the receiver do not detect the duplicate pkt

To handle duplicates:

Attache a sequence number to each packet

Receiver discard duplicates

RTD2.1 In aCTION

If a NAK/AK is corrupted, just resend

The number of states for 2.1 is double. But it is symmetric as now we need to attach a sequence number to the packet.

It needs to wait.

IT only need to differentiate to know if its is the previous or the next

2 states for sequence 0

2 states for sequence 1

This is to differentiate the packets

Waiting states:

Recieve no corrupted: ACK, doesnt do anything, move to next stage to get packet

Recieve corrupted: Resend packet

Receive feedback is NAK: Resend packet

The difference is so that the feedback also has an checksum.

Reciever

If the reciever is sequence 0, it is expecting a packet with sequence 0.

The reciever can use checksum to check if its corrupted and if it has the correct number of 0s

If it is correct, it will send an acknodlege witht eh chechksum and send the data to upper layer

Feedback:
11. Recieve packet is not corrupt: Different sequence number,

This can happen when the reciever reciveve a duplicate pakcet

It sends an ack back to sender thats all

Corrupted: Sends back Nak back with checksum

RDT2.2: A NAk free Protocol

Alternaive to 2.1

By specifying the sequence numbers we ack.

How to ignore Nak?

Sender:

We will try to specify the sequence number in the ack.

e.g ACK0

This implies that we are expecting the next packet to be 1

If its corrupted, it will just resend the previous ACK0

FSD

Insert slide 31

Receiver:

Not corrupted: Just send the next ACK

Corrupted: Send the previous ACK

Sender:

Just send the packet with the number of reciever's ACKN, n+1

RDT 3.0 Channels with errors and loss

New Assumption: Underlying channels can also lose packets (data,ACks)

- Checksum, seq

Approach Sender waits "reasonable" amount of time for ACK

- Countdown timer

- Time out

- Retransmit if no ACK received in this time

Use interrupts to implements a count down..

Use countdown timer to wait for the packet.

If the packet get delayed, we treat it as lost, the retransmission will be duplicate but the seq number already handle this issues.

<Insert 33>
The sender/receiver will start a timer after sending the packet/ack
If timer runs out and no response, it will resend again.

Premature Timeout
The ack got delayed, the sender sends because it thoughts its packet is lost or the receivers packet is lost.
But the receiver will see the duplicate and throw it away.

Duplicated ACKS?

- In the Textbooks

Performance of RDT3.0

Even thou it is correct, it's performance is still not good.

D(trans) = L / R

U(sender) = (L/R) / (RTT + L / R)

Fractuon of the time the sender waits to send

It needs to take a whole round trip before the sender is able to send the next packet.

The RTT is too long and very inefficient.

In order to stop, we will send multiple packets (Pipelining)

Pipelining Protocols

Allows senders to send multiples in flight yet to be acknowldge pkts

- Range of seq numbers must be increase

- Buffering at both sender and receiver side

Go back N in action

We allow N packets to be send without acknowledgements

These are "Sliding window protocols"

When the receiver receives, it will send back the ACK but identify its an out of order packet.

It will discard the packets after the missing and send back the ACKn where n is the packet ID before the missing one.

The sender will send the next corresponding packet base on the acks where the next packet is packet(n+N)

The sender's time out will happen for the missing pkt and it will resend it to the receiver.

GO-Back-N only use one timer.

This is under the assumption that the receiver will not accept the discarded packets

Sender

- Sends packets

- K-bit seq # in pkt header

- Window of up to N consecutive unack'ed packets allowed.

- One timer for oldest inflight packet (If pkt 0-3 is send and pkt 2 is lost, the timeout is for pkt0)

- If timeout: Resends all packets from latest ack received

- Waiting Ack delayed but recieved the next ACK: Mark all packets below received as sent

- Moves window everytime an ack is received correctly

Receiver

- Receives packets

- Sends Ack of the next expected packet

- Discards out of order packets/Duplicated and resend the Ack of expected packet

Selective Repeats

Key Differences

Receiver individually acknowledges all correct received pkts

- Buffer out of order pkts

Sender maintain timer for each unack

<Insert 45>

Sender
- Send packets
- Have a timer for each unACKed packet
- Timeout: Resent only that packet, restart timer
- Acked: Move window up, send the next packet.
- Moving window: If there are unACKed packets before the moving window, resent them

Receiver

pkt n in [rcvbase, rcvbase + N -1 ] (Sliding window)
- send ACK
- Out of order buffer: Buffer packets that are not in order, sends ACK for packets recieved
- Deliver all in order packets as soon as possible, move window
- Duplicated Packets: ReACK for that packet
- Corrupted Packet: Ignore
- Delayed ACK/Packet: Rely on timer on sender side

My sender probably did not recieve the ack so we send again so that sender will not get stuck

Recap

<Insert slide 5-2>
Stop and wait protocol: Summary

What happen if the received ack is thrown again?
We are using to few bits to represent the sequence number of the packets. We cannot differentiate.
Solution: Use a large number of packets (TCP)

Go back N
- Use cumulative ack to acknowledge the most recent pkt
- receiver does not buffer
- sender maintains only one timer and is for the most unknowlege
- But sender has to resent all transmitted packet since the last unacked pkt

Selective repeats
- Sliding window to buffer out of order for reciever
- Sender: only retransmit the missing ack packet (one only)\
- Sender has timer for each pkt

Transport layer services

Overview:

- Point to point: One sender and one receiver

- Connection oriented: Handshaking inits sender, received state before data exchange

- Full duplex: Sender can receive and send at the same connection

- Reliable, in order byte stream: No message boundaries

Assumes that input will be output in the same order

- Pipeline: dynamic window size set by congestion/flow control

It is different from go back n and selective n (fix sliding window), pipeline's can change

TCP: Buffers and Segments

- Tcp send and receive buffers

Two buffer created after handshaking at any side

Should be regarded as a stream of bytes

The TCP will accumulate the bytes from the application layer above.

The TCP create a segment to be send to the reciever

How large will each segment will be?

- 1460 bytes typically (From application)

- Limited by maximum transmission unit, largest link layer frame (1500 bytes for ethernet)

TCP segment structure

Typically 20 bytes for header

<Insert 10\13\21>

TCP needs to differentiate between clients. TCP will use a 4 tuple to match to different sockets. The server can be running over a single process with multiple threads each serving on different socket connections.

- Source port

- Dest port

- Sequence number

It tells the index of the first byte in the data segment

e.g send a file of 500000 bytes where MSS is 1000 bytes (Max num of bytes that can be carried in one seg)

Dividing the file into 1000 bytes, there are 500 segments

The first segment will be 1000 bytes (Index 0-999)

Second segment will be 1000- 1999

TCP's sender implement a similar data structure as go back N

The difference is that each little piece, represent a packet (go back) while in tcp it represent a byte

The sequence number will specify the first byte of the next tcp segment

- ACK number

Seq# of the next byte expected from the other side

This is express using cumulative ack

Assuming the receiver has receive the first byte, in the ack, the receiver will put the index of the 2nd byte as the ack number. Cumulative means that all the bytes before that has been receiver. Sending this, tells the sender that that is the missing byte it does not have.

How does the receiver handles out of order segments?
- TCP spec doesnt say, it is up to the implementer

- Can choose to buffer

- WE will still send back the next expected byte back to the sender

Sequence and ACK is counted by bytes of data (Not segments)

Selective repeat: Sender, receiver windows

When receive send back the ack, it always send back the number if the first byte of the unreceived and expected byte.

TCP seq. numbers, ACKS

Assume a echo server, the client sends a message with only one byte.

data = 'C', seq = 42 (Sequence number is randomly chosen) [Data message]

The server can choose to send something to the client as well since the connection is bi directional

When the server behaves like a client, it use a different sequence number

The server side will expect something of 43, so it will send back an ack = 43, seq = 79 [Data message and ack]

The client will put an ack = 80 and seq = 43

TCP flow Control

When the receiver receive an ip packet at the ip layer, it will go through protocol stack upwards.

It is going to go through the ip protocol to be stripped before delivered to the transport layer. The tcp will look at the header and take out the data to be put in the buffer before sending it back to the application layer.

If the application layer process is slower than the time use to fill buffer. (The host running alot of processes)

The receiver buffer might be overflowed by the sender side

This is why we need flow control. This is for the receiver side to informed the sending side to warn it of incoming overflow (Do not send too much)

- receiver advertises free buffer space in TCP header

- RcvBuffer size set bia socket option

- Many operating system autoadjust

- Sender limits amounts of unacked data to receivers rwnd value (Window frame)

- This ensure that the buffer does not overflow at the receiver side

Head Len

Holds the typical header length of the header of tcp segment

There might be optional fields thus some tcp headers are longer than 20 bytes

This is only in theory, in practice it is not use

PSH: Push data now

Due to the application data carrying important detail, it can set this bit to be 1 so that the reciever can know that this packet is important

(Not ise in practice)

URG: Urgent data

Tells that some part of the data is urgent and need to be push to application layer of the receiver immediately

Has a corresponding pointer that show where the urgent part is

RST, SYN, FIN

Rst - reset

When the sender and receiver try to start a connection. If the server is not available due to being down, the host side will send a feedback message with this bit set to be 1. This tells that the server/port is not running/open.

Connection Management

Sender and receiver will handshake first before exhanging data:
- Agree on establish connection

- Agree on connection parameters

Each side will reserve buffers and negotiate states for a connections.

e.g sequence number (init) for each direction

3 way handshake procedure

The use of 3 packets to establish a connection

1. Both sides are at listen

2. Client sent a syn packet and choose seq num

Sets synbit = 1, seg = x

This does not have any data

3. Client transition into syn sent

4. Server will try to create socket after receiving syn

5. Server will create a syn ack message which will set the synbit to be 1

Both the syn and ack bit will be 1, it will put the number x+1 (client seq) into the ack field

The server will also generate a seq number = y

This is for the other side

What the server is saying that it expecting x+1 byte next.

6. Client saw that the server agreed to have a connection, it will transition into the ESTAB stage

7. But the server side have not transition to ESTAB stage, so the sender have to send another ACK

ACKNUM = y +1

//This is telling the server that the receiver is expecting y+1 to be the next packet

8. The sender can either piggy bag or use x+1

TCP: Closing a connection

- Client, server each close their side connection

Fin bit = 1

- Respond to received FIN with ACK

Even if one side has close, it will keep its receiving up until the other side is ready to close (Clear its buffer)

Once the other side receive the ack, it will close as well

Reliable Data transfer

- TCP creates a rdt service on top of IP udt service

- pipeline segments

- Cumulative Acks

- Single retransmission timer

- Retransmission are triggered by

- timeout events

- duplicate ack

Go back N and TCP are similar due to both using one single transmission timer and cumulative ack

TCP sender events

Ignoring flow control and congestion

Data rcvd from application layer:

- Create segment with seq# (Byte stream number of first data byte in segment)

- Start timer if not already running

- pass segment to IP

Timeout:

- retransmit segment that cause timeout

- Restart timer

ack Rcvd (Receives ack):
- If ack acknowledges prev unacked segments

update what is known to be acked

- start timer if there are still unacked

Moving sliding window and restart the timer. ACK are cumulative thus we need to update.

If theres a lost ack

The sender will resent the same pkt

If there is a premature timeout

Sender will resend again even if the receiver has already receive it already.

Receiver will resend the next expected packet

Cumulative ack

If the ack got lost, upon receiving the later ack,

it will implicitly know that the missing ack has already been received

TCP Ack generation

Event at receiver: Arrival of in order segment with expected seq #. All data up to expected seg # already ACKED

TCP receiver action: delay ack, wait up to 500 ms. If during this time, there is no other packets, it will send the ack back

Event at receiver: In order but one seg has ack pending

Have not send the ack pending even thou i have receive it

TCP at receiver: Send a single cumulative ack, ack both in order segments

Instead of sending 2, we can just send one latest one

Event at receiver: Arrival of out of order segment.

Gap detected

TCP receiver: Immediately send duplicate ack indicating the next expecting byte via seq#

Event at receiver: Arrival of segment that partially or completely fills gap.

TCP receiver action: Immediately send ack provided that segments starts at lower end grip

TCP round trip time, timeout

How to set tcp timeout value?

- Longer than RTT (RTT varies)

- Too short: Premature timeout

- Too long: Slow reaction to segment loss

How to estimate RTT?
- ignore retransmission (Measure time from segment transmission until ack receipt)

EstimatedRTT = (1 -a) * estimatedRTT + a*sampleRTT

TimeoutInterval = EstimatedRTT + 4 *DevRTT

DevRTT is the safety margin

TCP fast retransmit

- Sometimes the timeout can be very long due to the congestion/distance

- Detection of packet loss would let us not to wait for timeout

- Timeout is use to infer packet loss if we got no other methods

- Duplicated ACKS checks for missing packet losses before time out

= Sender often sends back many segment backto back

= There will likely be many duplicate acks

Since ACks will show the expecting packet, so if it got loss, the sender can infer which packet got loss if it recieve multiple acks showing the same next expecting packet

Pages

Tuesday, February 11, 2020

CS2105: Lecture 4 - UDP, Reliable Protocol