Principles of Reliable Data Transport in Networking

Reliable data transport in networking involves handling packet loss, corruption, and reordering on unreliable channels. Key concepts include stop-and-wait protocol, Go-Back-N protocol, Selective Repeat protocol, and basic principles of communication reliability.

• Networking
• Data Transport
• Reliable Communication
• Protocol Design
• Packet Loss

ckel Follow

Uploaded on Sep 12, 2024 | 2 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. 9. Principles of Reliable Data Transport Part 1 Basic concepts Stop-and-wait protocol Go-Back-N protocol Selective Repeat protocol Roch Guerin (with adaptations from Jon Turner and John DeHart, and material from Kurose and Ross)

2. Preliminaries Physical channels are never completely reliable wireless links subject to interference transmission noise can introduce bit errors routers & switches may drop packets due to buffer overflow Reliable communication relies on (1) detection (of lost or corrupted packets) and (2) retransmissions as necessary sender retains copy until it knows packet has been received receiver notifies sender and delivers (to application) each piece of data once, and only once, preferably in order Protocol design specifies coordination between sender and receiver, anddepends on nature of channel may corrupt packets, but never lose them may corrupt and/or lose packets but never re-order them may corrupt, lose or re-order packets 2

3. Model for Reliable Communication application application send receive send receive reliable data transfer reliable data transfer unreliable channel Reliable data transfer layer provides send/receive methods used by applications to transfer packets Reliable data transfer layer uses fields in packet header to coordinate with peer this is transparent to application 3

4. Basic Concepts focus separately on sender and receiver behavior receiver acknowledges packets from sender positive acks and/or negative acks (nack) sender transmits and retransmits based on information provided by the receiver time-out to trigger action if ack/nack is not received within a certain time-frame both packets and acks can get lost sequence numbers in each packet sequence number in ack identifies received packet(s) size of seq. num. field determines # packets that can be sent before acknowledgments must be received simplest protocol uses 1 bit sequence number sends one packet and waits for ack before sending another 4

5. Basic Protocols RDT 1.0 3.0 RDT 1.0: RDT over reliable channel RDT 2.0: RDT over channel with bit errors Stop and wait Acks and Nacks RDT 2.1: RDT 2.0 plus 1-bit sequence number RDT 2.2: RDT 2.1 with duplicate Acks instead of Nacks Stop and wait Acks but no need for Nacks RDT 3.0: RDT over channel with bit errors and pkt loss Stop and wait. Also called alternating-bit protocol RDT 2.2 plus timeouts Sender can ignore duplicate Acks and wait for timeout And beyond Pipelined RDT protocols (next time) 5

6. Basic Protocol RDT 2.x (2.0 & 2.1) Assume channel may corrupt but never lose packets receiver can always detect if packet has been corrupted Simple protocol for such a channel uses acks and nacks sender transmits one packet at a time and waits for ack/nack or erroneous packet receiver sends ack when it receives packet correctly, sends nack when it receives a packet with an error Is this enough? packets, acks and nacks can all get corrupted 6

7. Basic Protocol RDT 2.x many things can go wrong? Corruption of acks, nacks, or packets means that sender may not be able to tell which packet was received correctly or not if sender retransmits the packet, the receiver could deliver the same packet to the application twice. If it transmits a new one, the receiver can fail to deliver a packet to the application. 0 0 0 1 0 ? ? x x x 0 0 1 2 solution is to add a 1 bit sequence number in this case, it is sufficient to use positive acks only 7

8. Protocol Diagrams Packet ID Ack ID A packet being sent from sender to receiver normal case packet 0 deliver An acknowledgement being sent from receiver A packet being delivered to upper layer in receiver ack to sender packet 1 ack RECEIVER SENDER packet 0 x nack packet 0 ack . . . Passage of time 8

9. RDT 2.2 Behavior Eliminating Nack corrupted ack corrupted packet normal case packet 0 packet 0 packet 0 deliver ack 0 ack 0 ack 0 packet 1 packet 1 packet 1 ack 1 ack 0 ack 1 packet 1 packet 1 packet 0 ack 1 ack 1 ack 0 packet 0 packet 0 packet 1 ack 0 ack 0 ack 1 . . . . . . . . . 9

10. RDT 2.2 Receiver Specification received packet 1 or received corrupted packet send ack 1 State W0: wait for packet 0 State transition received packet 0 with no errors deliver packet and send ack 0 received packet 1 with no errors deliver packet and send ack 1 Event Action received packet 0 or received corrupted packet send ack 0 W1: wait for packet 1 State transition State machine specifies behavior States, events, and state transition+action Used to guide implementation and to analyze behavior 10

11. RDT 2.2 Sender Specification ack 1 received or ack corrupted resend packet with seq # 0 packet available to send send packet with seq # 0 S0: wait to send 0 A0: wait for ack 0 ack 1 received correctly do nothing else ack 0 received correctly do nothing else ack 0 received or ack corrupted resend packet with seq #1 A1: wait for ack 1 S1: wait to send 1 packet available to send send packet with seq # 1 11

12. A More Realistic Protocol RDT 2.x assumed the channel can corrupt packets but never loses them entirely means receiver always gets something whenever a packet is sent and sender always receives an ack after sending a packet In practice, packets can also be lost without a trace receiver never acks lost packet, since does not know it was sent sender left waiting for ack, but no ack ever comes Recovering from lost packets option 1: keep sending packet repeatedly until ack received means that in normal case, sender/receiver both do extra work option 2: sender waits for ack for a limited time period, then re-sends the packet if ack fails to arrive in time works well if maximum ack delay is known and does not change Still operating with 1-bit sequence number 12

13. RDT 3.0 Behavior premature timeout lost ack lost packet packet 0 packet 0 packet 0 ack 0 ack 0 ack 0 packet 1 packet 1 packet 1 ack 1 timeout timeout timeout ack 1 packet 1 packet 1 packet 1 ack 1 ack 1 ack 1 packet 0 packet 0 packet 0 ack 0 ack 0 ack 0 13

14. How Long Should timeout Be? 0 ack0 ack0 ack xmit time Propagation + queueing Propagation + queueing Pkt. Proc. timeout should be at least equal to roundtrip time (RTT), i.e., transmission+propagation+queueing of packet & ack + processing time at receiver timeout RTT The challenge lies in (accurately) estimating RTT, when its components are unknown and variable (more on this later, when we discuss TCP) 14

15. RDT 3.0 Receiver Specification received packet 1 send ack 1 Note that it is simpler than RDT 2.2 No need to send ack s when corrupted packets are received The timeout at the sender now serves as the trigger for packet retransmissions W0: wait for packet 0 received packet 0 deliver packet and send ack 0 received packet 1 deliver packet and send ack 1 received packet 0 send ack 0 W1: wait for packet 1 15

16. RDT 3.0 Sender Specification timeout resend packet with seq # 0 and restart timer packet available to send send packet with seq # 0 and start timer S0: wait to send 0 A0: wait for ack 0 ack 1 received do nothing ack 0 received cancel timer ack 1 received cancel timer timeout resend packet with seq # 1 and restart timer A1: wait for ack 1 S1: wait to send 1 packet available to send send packet with seq # 1 and start timer ack 0 received do nothing 16

17. RDT 3.0 Performance RDT 3.0 sends only one packet at a time works well if delay between sender and receiver is small inefficient if RTT >> transmission time of a packet (tpkt=L/C) Consider a 1 Gb/s link with 10 ms delay in each direction RDT 3.0 sends only one packet every 20 ms, but link is capable of sending 20 million bits in 20 ms, so for typical packet sizes, only tiny fraction of link s capacity is used 17

18. RDT 3.0 Performance RDT 3.0 sends only one packet at a time works well if delay between sender and receiver is small inefficient if RTT >> transmission time of a packet (tpkt=L/C) <tpkt> 0 0 0 0 1 0 <RTT> <RTT> <RTT> <RTT> p p p p p p 1-p 1-p or or or q = p+(1-p)p q 1-q q RDT 3.0 performance as a function of RTT (= tout) link speed C average packet size L packet/ack loss/corruption probability q 18

19. RDT 3.0 Performance <tpkt> 0 0 0 0 1 0 <RTT> <RTT> <RTT> <RTT> p p p p p p 1-p 1-p or or or q = p+(1-p)p q 1-q q RDT 3.0 performance as a function of RTT = tout, link speed C, average packet size L, and packet/ack loss/corruption probability q Expected time between successful transmissions = = 0 + RTT t 1 pkt + + = + = k RTT RTT ( 1 )( ) 1 ( ) 1 ( )( ) T k t q q q t succ pkt pkt 2 1 q 1 ( ) q k Throughput = L/Tsucc = C(1-q)/(1+RTT/tpkt) Improves as qgets smaller (no surprise) Improves as RTT gets smaller compared to tpkt 19

20. Exercise 1. Consider this scenario for RDT 2.2 (no losses). Two packets are sent. the first packet and its ack are not corrupted the second packet is corrupted, but when it is sent a second time, the packet is not corrupted, but the ack is Draw a time-space diagram (like those on the previous slide) describing this scenario, showing how RDT 2.2 recovers and delivers packets to the receiving application. corrupted packet + corrupted ack 20

21. Exercise 1. Consider this scenario for RDT 2.2 (no losses). Two packets are sent. the first packet and its ack are not corrupted the second packet is corrupted, but when it is sent a second time, the packet is not corrupted, but the ack is Draw a time-space diagram (like those on the previous slide) describing this scenario, showing how RDT 2.2 recovers and delivers packets to the receiving application. corrupted packet + corrupted ack packet 0 0 ack 0 packet 1 ~ ack 0 packet 1 1 ack 1 ~ packet 1 ack 1 packet 0 0 ack 0 21

22. Exercise 2. For each of the time-space diagrams on slide 9, show the sender state and the receiver state at each point in time (just add state labels to the diagram next to the vertical lines). normal case corrupted packet corrupted ack packet 0 packet 0 packet 0 deliver ack 0 ack 0 ack 0 packet 1 packet 1 packet 1 ack 1 ack 0 ack 1 packet 1 packet 1 packet 0 ack 1 ack 1 ack 0 packet 0 packet 0 packet 1 ack 0 ack 0 ack 1 . . . . . . . . . 22

23. Exercise 2. For each of the time-space diagrams on slide 9, show the sender state and the receiver state at each point in time (just add state labels to the diagram next to the vertical lines). corrupted ack corrupted packet normal case S0 S0 S0 W0 W0 packet 0 packet 0 packet 0 W0 A0 A0 S1 A0 S1 ack 0 ack 0 ack 0 W1 W1 W1 S1 packet 1 packet 1 packet 1 A1 A1 A1 ack 1 ack 0 ack 1 W1 S0 A1 A1 W0 W0 packet 1 packet 1 packet 0 A1 A1 A0 S1 ack 1 ack 1 ack 0 W0 W1 S0 S0 W0 packet 0 packet 0 packet 1 A1 A0 A0 ack 0 ack 0 ack 1 W1 W1 W0 S0 S1 S1 . . . . . . . . . 23

24. Exercise 3. For each of the time-space diagrams on slide 13, show the sender state and the receiver state at each point in time (just add state labels to the diagram next to the vertical lines). premature timeout lost ack lost packet packet 0 packet 0 packet 0 ack 0 ack 0 ack 0 packet 1 packet 1 packet 1 ack 1 timeout timeout timeout ack 1 packet 1 packet 1 packet 1 ack 1 ack 1 ack 1 packet 0 packet 0 packet 0 ack 0 ack 0 ack 0 24

25. Exercise 3. For each of the time-space diagrams on slide 13, show the sender state and the receiver state at each point in time (just add state labels to the diagram next to the vertical lines). lost packet packet 0 W0 A0 S1 premature timeout lost ack S0 S0 S0 packet 0 packet 0 W0 W0 A0 A0 ack 0 ack 0 ack 0 S1 W1 W1 S1 packet 1 packet 1 W1 packet 1 ack 1 timeout timeout timeout ack 1 W0 A1 A1 W1 A1 W0 packet 1 packet 1 packet 1 ack 1 ack 1 ack 1 S0 S0 S0 packet 0 W0 packet 0 packet 0 A0 W0 A0 A0 ack 0 ack 0 ack 0 S1 W1 W1 W1 S1 S1 25

26. Exercise 4. 1 Gb/s link with 20 ms RTT, L=10,000 bits, q=10-6 What is the link throughput under RDT 3.0 What is the best possible throughput if the maximum packet size is 12,000 bits? 26

27. Exercise 4. 1 Gb/s link with 20 ms RTT, L=10,000 bits, q=10-6 What is the link throughput under RDT 3.0 Throughput = C(1-q)/(1+RTT/tpkt)=109(1-10-6)/(1+2x10-2/10-5) ~ 109/2001~500 kbps What is the best possible throughput if the maximum packet size is 12,000 bits? If q is unchanged, the only difference is that tpkt increases to 1.2x10-5, so that the throughput is now about 600 kbps. Still about 2000 times slower than the link capacity! If we assume q=0, the throughput hardly improves since 1-10-6~1-0 27