Transport Layer Part 2 Flashcards
Principles of Reliable Data Transfer
Reliable Service Implementation
Unreliable channel with reliable transport protocol creates reliable service
Principles of Reliable Data Transfer
Reliable Service Abstraction
Reliable channel creates reliable service
Principles of Reliable Data Transfer
RDT
Reliable data transfer
RDT Interfaces
RDT Interfaces
- rdt_send()
- udt_send()
- deliver_data()
- rdt_rcv()
RDT Interfaces
rdt_send()
- Called from upper layer (e.g. app)
- Passes data that has to be delivered to receiver
RDT Interfaces
deliver_data()
- Called by rdt
- Delivers data from lower to upper layer
RDT Interfaces
udt_send()
- Called by rdt
- Transfers packet over unreliable channel to receiver
RDT Interfaces
rdt_rcv()
Called when packet arrives on receiver side of channel
rdt 1.0
rdt 1.0
- Reliable transfer over reliable channel
- Separate processes for sender, receiver
rdt 1.0
rdt 1.0 Sender FSM
- enter to
wait for call - loop with
rdt_send(data) > packet = make_pkt(data) > udt_send(packet)
rdt 1.0
rdt 1.0 Receiver FSM
- enter to
wait for call from below - loop with
rdt_rcv(packet) > extract(packet, data) > deliver_data(data)
rdt 2.0
rdt 2.0
- unreliable channel (bit errors)
- recovers from errors using acknowledgements
rdt 2.0
ACKs
Acknowledgements, receiver explicitly tells sender that packet was received okay
rdt 2.0
NAKs
Negative acknowledgements, receiver explicitly tells sender that packet had errors. Sender retransmits packet on receipt of NAK
rdt 2.0
Stop and Wait
Sender sends one packet, then waits for receiver response
rdt 2.0
rdt 2.0 Fatal Flaws
- corrupted ACK/NAKs
- handling duplicates
rdt 2.0
Review rdt 2.0 FSM Specifications
rdt 2.1
What if ACK/NAK corrupted?
- sender doesn’t know what happened at receiver
- can’t retransmit in case of duplicates
rdt 2.1
Handling Duplicates
- if ACK/NAK corrupted, sender retransmits packet
- sender adds sequence number to each packet
- receiver discards duplicates using sequence numbers
rdt 2.1
Sequence Number
Added to each packet to identify duplicates
rdt 2.1
Sender Process
- seq # added to packet (1 or 0)
- must check to know if ACK/NAK is corrupted
- adds twice as many states to FSM
rdt 2.1
Receiver Process
- must check if received packet is duplicate
- doesn’t know if its last ACK/NAK was received at sender
rdt 2.2
rdt 2.2
- NAK-free protocol, only uses ACKs
- receiver must explicitly include seq # of packet being ACKed
rdt 2.2
Review rdt 2.2 FSM Specifications
rdt 2.1
Review rdt 2.1 FSM Specifications
rdt 2.2
rdt 2.2 Fatal Flaw
Packets can be lost, not just corrupted
rdt 3.0
rdt 3.0
- Channel with errors and loss
- Sender retransmits if no ACK received in reasonable amount of time
- If packet just delayed, then will be duplicate but will be handled by seq #s
- Receiver must specify seq # of packet being ACKed
rdt 3.0
Sender Utilization
Fraction of time the sender is busy sending
U_sender = (L/R) / (RTT + L/R)
rdt 3.0
Pipelining
- Sender allows multiple, “in-flight”, yet-to-be-ACKed packets.
- # of packets depends on window size.
- Increases sender utilization
rdt 3.0
Window Size
Maximum number of “in-flight” packets allowed.
Go-Back-N: Sender
Go-Back-N: Sender
- Has window of up to N consecutive transmitted but unACKed packets
- timer for oldest in-flight packet
- upon receiving an ACK, move forward to begin at N+1
Go-Back-N: Sender
Cumulative ACK
ACKs all packets up to, including seq # N
Go-Back-N: Sender
timeout(n)
Retransmits packet N and all higher seq # packets in window
Go-Back-N: Receiver
Go-Back-N: Receiver
- Only sends ACKs
- Has buffer holding sequence numbers
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 (next sequence number)
Go-Back-N: Receiver
On receipt of out-of-order packet…
- Can discard or buffer (implementation decision)
- Re-ACK packet with highest in-order seq #
Selective Repeat
Selective Repeat: Sender
- if next seq # avaliable, send packet
- if packet times-out (front of window), then sender retransmits that packet
- if first seq # in window is ACKed, move window up
- sender window: N consecutive seq #s
Selective Repeat
Selective Repeat: Receiver
- if receive packet n, send ACK(n)
- out-of-order: buffer
- in-order: deliver buffered in-order packets, advance window to next not yet received packet
Selective Repeat
Selective Repeat
- Unique ACK sent for every received packet
- if need to retransmit, use previously sent ACKs to determine how many packets to resend (doesn’t resend packets that were received ok)
Go-Back-N
Go-Back-N
- Send ACK for each received packet
- If packet lost, discard all following packets and all following ACKs will have lost packet’s sequence number
- Resends lost packet and all packets that were sent after lost packet
Selective Repeat
Selective Repeat Dilemma
If range of seq #s too short, then receiver might not be able to distinguish between a resent packet and new packet (can cause receiver to accept duplicates)
TCP
TCP Acknowledgements
- Sends cumulative ACKs
- Value of ACK should be -> seq # + size of sent data
TCP
TCP Sequence Numbers
Byte stream number from first byte of segment data
OR
Previous ACK value
TCP
TCP Retransmission
In case of premature timeout:
* sender retransmits packet
* receiver resends cumulative ACK (informs of all previously received packets)
TCP
TCP Fast Retransmit
- If sender receives 3 duplciate ACKs, resend smallest unACKed segment with smallest seq #
- Don’t wait for timeout
