3.4-2 Principles of Reliable Data Transfer (Part 2)
Vložit
- čas přidán 14. 01. 2022
- Video presentation: "Transport layer: Principles of Reliable Data Transfer (Part 2)." Pipelining. Go-back-N. Selective Repeat.
Computer networks class.
Jim Kurose
Textbook reading: Section 3.1, Computer Networking: a Top-Down Approach (8th edition), J.F. Kurose, K.W. Ross, Pearson, 2020.
See gaia.cs.umass.edu/kurose_ross for more open student resources.
Extra note: For Selective Repeat: Relationship between Sequence Number Size & Window Size
The ppt slides include the issue where receiver accepts duplicate data packet when the sequence number & window sizes are not adjusted correctly. However, the video does not cover that.
So here is the issue:
Window Size, N = 4. Sequence Numbers = [0, 1, 2, 3]
Sender sends Packets{0,1,2}.
Receiver receives all Packets{0,1,2} and sends ACKs{0,1,2}. Then moves its window to [ 3 0 1 2 ], so that it is now ready to receive new Packets{3, 0, 1, 2}.
However, ACK(0) gets lost and sender never receives ACK(0). So the sender's window is still sitting on [ 0 1 2 3 ].
Now, after a certain amount of time, the timer for Packet(0) runs out. Timeout(0) is called and Packet(0) is Re-Sent !
This Packet(0) is the SAME packet as the previous Packet(0).
Receiver, however, receives the Packet(0) and treats it as a New Packet(0) since the receiver's window is sitting on [ 3 0 1 2 ].
Then the receiver will deliver this DUPLICATE data packet to upper layer, which is an issue.
So the question is: What relationship do we need between the Sequence Numbers & Window Sizes?
The answer is, simply increase the sequence numbers by doubling and leave the window size.
So, that the window size is at least half or less than the amount of sequence numbers.
If this is applied to the same situation as above, this is what happens:
Window Size, N = 4. Sequence Numbers = [0, 1, 2, 3, 4, 5, 6, 7]
Sender sends Packets{0, 1, 2}
Receiver receives all Packets{0, 1, 2}, sends ACKs{0, 1, 2}, and moves its window to [ 3 4 5 6 ]
However, ACK(0) gets lost and sender never receives ACK(0). So, the sender's window is still sitting on [ 0 1 2 3 ]
Timeout(0) is called, and sender re-sends Packet(0).
Receiver gets Packet(0), checks that it is out of its window [ 3 4 5 6 ]. So, it discards the data packet, and Re-Sends ACK(0).
Now, the receiver side does not deliver duplicate packet to upper layer !
Sir, this is a joy to watch. Your patient explanations are a huge help! - Thank you!
This video was fantastic. I've had issues understanding my class and this was absolutely magnificent
Extra note: For Go-Back-N: How can Cumulative ACK actually work without an issue?
On the slide it says, "cumulative ACK: ACK(n): ACKs all packets up to , including seq# n".
This means that if the Sender receives ACK(5) - although never have received ACK(2), ACK(3) and ACK(4) - the Sender will ACK all of them anyway.
You may think that this could cause some issues but that is not true. This is because the Receiver will only send ACK with the highest seq # out of the packets it received so far. If the Receiver did not get all or any of the Packets{2,3,4}, but got the Packet(5), it will never send ACK(5) because Packet(5) is not the in-order highest seq# of the packets it received so far.
So, by the stage where the Receiver actually sends ACK(5), it means that the Receiver actually received all Packets{1,2,3,4,5}. Then, if sender gets ACK(5), although it didn't get ACKs{2,3,4}, the Sender can reasonably think that the Receiver actually has received all the packets correctly up to seq# 5.
Thus, Sender does not have to worry about missing ACKs{2,3,4}, and it can just ACK them all when it gets ACK(5). At the Sender side, Packets{2,3,4,5} were accumulated to be waiting for ACKs, and all of them got ACKed once ACK(5) was received.
Hence the name suggests, Cumulative ACK.
The most detailed video i have ever watched on reliable data transfer
Great Work
thank you so much for these videos, it's really amazing that you are explaining such content on youtube, thank you so much for the content
there! Thanks a lot for the help, I'm going to subscribe to your channel and keep up with all the videos!
I suppose the answer to that last question is:
Sender starting transmission of pkt 6 to 9, with window transferred to new location of 6 to 9.
rdt protocol mechanisms:
• error detection (e.g., checksum)
• ACKs, NAKs
• retransmission
• sequence numbers (duplicate detection)
• timeout-and-retransmit (lost messages)
Summarizing: The video discusses the development of a reliable data transfer protocol that accounts for both message corruption and loss. The protocol uses timeout retransmission and sequence numbers, and can be pipelined to improve utilization. Two approaches are presented, Go-Back-N and Selective-Repeat.
clearly explained sir
0:50 rdt 3.0
15:15 selective repeat
Why are we restarting the sequence and resending pkt0 after pkt1 (in all of the examples)? Isn't it supposed to be pkt2?
This is a bit confusing, since you'd think packet number = sequence number that correspond to the chunks of data being sent ...
But this is not that. It's not resending the same data (though it looks that way) ... It's the state of the sending & receiving ticking back & forth.
This pkt0 & pkt1 is only used in the explanation of basic Reliable Data Transfer to build up to the points shown at the end of this video.
In the simplest model, we need sender & receiver to send, receive, acknowledge, and await confirmation.
To cover all those bases, we only need 2 sequence numbers: 0 and 1.
If you've sent 0, you await 0 and queue up 1. If you've sent 1 you await 1 and queue up the other one again (0).
The packet currently being sent/received is either the next one, or it's a repeat of the previous packet that wasn't received / Ack'd (or it was corrupted).
(In the book he calls this "the alternating bit protocol")
This simple 0/1 binary approach is like a ticking grandfather clock. The pendulum either ticked the correct direction, or it doesn't.
If a packet arrives swinging the wrong direction (not what's expected), that packet is acknowledged but thrown out, in the simple model.
If it arrives with the expected direction, the packet is acknowledged and sent on to the application.
As we see in this video though, that binary approach is extremely inefficient - it's far better to send/acknowledge > 1 packet at a time.
Once he introduces pipelining of multiple packets at once, 0/1 alone is not adequate to track the packets so he does add more packet numbers.
In SR, can't we move the out-of-order ACKed packets outside the window? Why are we keeping them?
At time 8:08, what if the duplicate ack1 arrives the sender side after the sending of the last pkt1? Sender will think this ack1 is for the last pkt1, but actually it is for the previous duplicate pkt1.
Interesting theory indeed.
I think ack 0 will keep delaying until all duplicate ack 1 received
add a time-to-live (TTL) in the ACK; if TTL is expired then that ACK is corrupt
Shouldn't the packets (of same sequence #) be identical, in which case it doesn't matter which packet it's acknowledging?
It will be ignored because it has already received an ACK 1 earlier and waiting for ACK 0 next.
So is TCP a SR or a GBN protocol? I guess I will find out next...
I love thee to the depth and breadth and height my soul can reach.
Sir Sakath video 😘
Hi bbg
🧠
Comment here for finance with bob
rdt2.2 is not there in lecture????????
rdt2.2 is same as 2.1 but without NAK
Hi guys I'm Bob finance advisor
Hii sir love from Pakistan
Sir how is market doing?
I am ur big fan sirrrr
@@Sudeep-dh7zo Even im big fan of him...his videos r soo nice
@@vigneshvinu1088 hello Pakistan , i am from Malaysia
All other videos are excellet except these two of RDT, its boring doesnt serve any usecase
no they serve an usecase in midterms
Apparently this is pretty similar to what wifi base stations do
LGBTQ+ i support, hence love video