TCP b : Additive Increase Multiplicative Decrease & 'Slow Start' - Computerphile

[00:00:00]We're still doing TCP. So, now where are we? We're at the transport layer.

[00:00:07]We are trying to get data between an application on one computer and an application on another computer.

[00:00:14]We want to make that connection reliable or we want to make it fast. So, in previous video, we have introduced mechanisms like the sequence number and acknowledgement number.

[00:00:29]And we have this idea there might be a timeout.

[00:00:37]Let's get a reminder. So, we've got a sender, we've got a receiver.

[00:00:45]That's very wonky and isn't it? Let's fix that up. So, we had the sequence number the SEQ and the acknowledgement number.

[00:00:53]I'm going to pretend these are just integers. They aren't in reality, but let's pretend they are. In a crude model, we would send this is our data and this is the data with sequence number one.

[00:01:04]And I'm going to leave a bit of space here and you'll see why.

[00:01:08]And I'm going to send back an ack, an acknowledgement to say that we've got that data.

[00:01:17]But, that is going to be really slow if we just send one packet of data.

[00:01:26]So, a packet of data around about 1,500 bytes. It's not a lot of data. And if you send one of those, wait for acknowledgement, send another one, wait for an acknowledgement, it's going to be horribly slow.

[00:01:38]What we want to do is send a lot of them together.

[00:01:46]Uh say 1 2 3 4. So, that that would be So, here's our dream.

[00:01:56]We send these five and then we acknowledge five and that acknowledgement is a cumulative acknowledgement. We're saying all right, we've got everything up to five. Now, this we can call it a flight of packets.

[00:02:12]So, the flight or packets in flight are the ones that we haven't yet gotten acknowledgement for. So, you as the sender, what you can be sure of is you've sent this many packets. Well, as far as you're aware, they're out there in the world. You don't know how big the network you're connected to is cuz remember you've got to connect to everybody, right? They may be in Melbourne, they may be in Beijing, they may be just next door.

[00:02:37]There may be a huge, wonderful fiber connection or there may be some horrible bit of wet string that can take like two bytes a year and you've got to operate with whatever that is. Maybe it's going, you know, via a satellite and it's going to take a long, long time.

[00:02:54]How do we deal with the fact that we don't know how big that network is? We don't know how long it should take for this to come back. How can we do that efficiently?

[00:03:07]For congestion mechanisms, also there's the problem of this round trip time.

[00:03:18]What we want to do is detect when there's congestion on the network.

[00:03:24]Mhm.

[00:03:25]But there's no The network isn't It's not like they've got a a congestionometer like the motorway saying, "Slow down. Queues ahead." Yeah?

[00:03:35]What we need to do is have some mechanism that's going to kind of automatically do that.

[00:03:40]So, what sort of things might we use to signal there's a problem? Well, I'm guessing you're going to have to time how long it takes for the acknowledgement to come back.

[00:03:48]>> Yeah, yeah, yeah. So, that that's really important. So, we call this the RTT, the round trip time, and that round trip time is really crucial to us, right?

[00:03:57]So, that that's one thing we can certainly do. All right. So, beyond the round trip times, a few other things we might do. All right. Mhm.

[00:04:06]>> Yeah, well, you could look at what else is going on, you know, previous kind of experience.

[00:04:10]>> Yeah, yeah, yeah, absolutely. So, we can look at the previous experience of our round trip time.

[00:04:15]So, we start to get into this world where we are measuring the round trip time and saying, is it fluctuating? The RFC we're dealing with RFC, remember is our rules, our request for comments is the the kind of Bible for us internet people that lays down our rules. And here we're dealing with RFC 5681 about congestion control.

[00:04:33]Now, the TCP standards lay down certain things you must do. They've got this this kind of lovely language where it's you should do this, you must do this, and you may do this. There's kind of a hierarchy.

[00:04:48]Um some things in transmission control protocol are must. Some things are may.

[00:04:55]There's a bit of flexibility. We call them flavors. So, as life develops, as as the internet moves on, we change the flavor of TCP we're using.

[00:05:08]Uh nowadays, almost everything is using a flavor called Cubic. That's the the most popular now. And the flavor is really about how we're going to respond to these signals. When do we say that a packet is lost?

[00:05:23]And how do we respond to that? The main mechanism we have for response is this idea of a congestion window.

[00:05:31]Now, last time we were doing this, uh we played this window and I said, not that window.

[00:05:36]>> [laughter] >> And I this by window we mean the amount of packets that we have out there in the network. It's number of bytes we believe the network can handle.

[00:05:46]There's two windows. Now, I'll deal this one real briefly cuz it's not actually that important. So, this this window is our receiver window.

[00:05:55]So, in in the early days of the internet, the receiver would probably be in the same lab as you just for the sake of the experiment, and maybe it's running a bit slow, so it's saying, "Oh, hey, I've got room for uh 100 kilobytes of data. Do not send me more than 100 kilobytes. I won't be able to deal with it."

[00:06:12]And that is sent in the packet header.

[00:06:15]So, it's telling us you don't want more than this many bytes of data out there in the world, or your receiver might have to throw them away anyway cuz it can't cope.

[00:06:24]That's not actually really that important in in or it's not as important in the world as the congestion window. And the congestion window is kept track of by the sender and the receiver, and they're constantly tracking and thinking, "How much data do I believe this network can send?"

[00:06:43]There's two signals we could look at.

[00:06:45]Most of them just look at a lost signal.

[00:06:47]So, most TCP variants, they're just looking has a packet actually got lost? Yeah?

[00:06:57]So, this these acknowledgements have numbers, and if we don't get an acknowledgement, if nothing comes back, or we also said, "If the wrong number of acknowledgement comes back." So, let's imagine this packet two dies. What I do then is to communicate it. So, here, this is two, this is three, four, and five. Packet two has got lost somewhere.

[00:07:25]So, in fact, what I'm going to send back here is ACK one ACK one ACK one again. So, I keep saying ACK one, I have received packet one. I've received another packet, it wasn't what I wanted. Yeah?

[00:07:44]Remember we can't communicate too much information in these things. It's just important to keep in mind this.

[00:07:49]We can't say anything complicated like I've received packets 1 3 5 7 and 8, but I'm missing two and that could you please >> Too much data.

[00:07:58]>> It's It's It's Yeah, it's not how this mechanism is designed to work. This is all living in a header. We don't want to be sending a telegram worth of information. We want to send the minimum possible information to get our job done.

[00:08:14]That's why we're using kind of obscure signals. There are other mechanisms that could do that. Not time to get into them.

[00:08:21]So, we're sending this ACK one and we're sending it repeatedly to say um this packet two is missing.

[00:08:30]By the time we get uh So, we've got an ACK one here acknowledging sequence packet one and three more of them. This is a triple duplicate.

[00:08:43]And now we suspect uh >> [snorts] >> probably something bad has happened to packet two.

[00:08:50]Some things I need to do for that.

[00:08:53]Things I need to do for that, obviously, packet two needs to go out there again.

[00:08:58]But now I need to think uh am I overwhelming the network? Am I sending out too much data?

[00:09:06]Now, even worse than receiving a triple duplicate, maybe I send them all out there.

[00:09:11]>> And nothing >> Nothing. Nothing comes back.

[00:09:14]So, now if I send out all the data, nothing comes back. I think you've Now, maybe my network is catastrophically overwhelmed, right?

[00:09:25]If one packet is lost, like perhaps one buffer has overflowed, perhaps or perhaps it was just, you know, randomly got corrupted or one little thing went wrong.

[00:09:36]But if I receive nothing, if I if I just get a timeout, now I think, "God, there's a lot of congestion here."

[00:09:47]So, this is where the flavors of TCP come in. So, what we need is is another bit of paper.

[00:09:54]What we need to think of is how I evolve my window size. So, roughly speaking, so I'm going to call this time, even though I actually it's kind of a clock between acknowledgements. And this is the size of the congestion, the C W N D. Now, I'm going to start over here weirdly, but you see why in a minute. If I send out all of my packets, we count them all out, we count them all back, and it's success.

[00:10:24]I'm going to make my window go up a little bit.

[00:10:27]So, I've counted one round of packets, they've all come back. Great news.

[00:10:31]So, the network's maybe it's a little bit bigger than I thought. So, you can sort of push it. Yeah, yeah, yeah, I'll try [clears throat] that.

[00:10:37]Yeah, 65 miles an hour is good. Let's try 70. 70 was good, let's try 75. So, we're going to creep our window size up.

[00:10:48]Okay, it's getting bigger and bigger.

[00:10:50]But we get a loss, we're going to slam it back down. We're actually probably going to cut it in half. So, we'll make our window half as big, maybe, and and and creep it back up. If I get that triple duplicate, I'm going to cut it in half. Bam, bam, bam.

[00:11:05]And start creeping it back up again.

[00:11:07]Theoretically, we get this kind of sawtooth. If we get a catastrophic loss, we might want to start again, but I've I've left this bit cuz I haven't really talked about how we set off. Cuz what we want to do is these windows can be quite big, they can contain quite a lot of data. And if we started with this creeping it up slowly.

[00:11:29]Oh, I didn't give this a name. We should give that name. We call this AIMD, additive increase multiplicative decrease. I'm going to make the window one packet bigger if we get them all back successfully, but if I detect congestion, I'm really shut things down quick.

[00:11:46]All right? I don't want to creep things down and still keep overwhelming the overwhelmed network.

[00:11:52]So, additive increase, I'm popping up by one. Multiplicative multiplicative decrease, cutting it in half.

[00:11:59]But, at the start, we want to be a little more aggressive.

[00:12:04]Cuz if we start and we send one packet, and we send two packets, three packets, four packets, five packets, >> Life is too short.

[00:12:10]>> Yeah, exactly. Life is far too short.

[00:12:12]It's going to be a long while before we're sending a thousand packets.

[00:12:17]So, we have maybe one of the worst names in computer, and we have what we call here, we have slow start.

[00:12:25]And we call it slow start because it's tremendously quick.

[00:12:29]I know. I didn't name it.

[00:12:31]Um no, it's to get out of the slow start.

[00:12:35]So, our window, I'm going to give the window packet numbers, which I shouldn't do. It should really be in bytes, but to make it easier. So, I'm going to send one packet. See if it comes back.

[00:12:46]Now, I'm going to send two.

[00:12:48]Now, I'm going [clears throat] to send four.

[00:12:50]Now, I'm going to send eight. Now, I'm going to send 16.

[00:12:53]Up up up up up, it's go Right.

[00:12:56]So, the initial phase is exponential growth.

[00:13:00]Just until Just to get us out of that rut where things would be real real slow.

[00:13:07]And then, once we've had our first loss, once the connection's going properly, we're going to move into the additive increase multiplicative decrease.

[00:13:14]>> So, you might shoot all the way up to 1024, and then you have loss, so you >> You have loss, so we're going to drop back down, and get back into this AIMD.

[00:13:22]And this is where we get into the flavors, cuz firstly, like we said, "Okay, if we get those duplicates back, we can infer a loss."

[00:13:32]But also, there might be that timeout loss where we're going to shut it down at a little bit further.

[00:13:37]How long do we wait?

[00:13:38]Mhm.

[00:13:40]So, we think back to that round trip time.

[00:13:44]Uh there's there's various algorithms involved here, but we're going to wait a kind of multiple of that round trip time. So, we're going to measure, "Ooh, it took 0.1 seconds for all these packets."

[00:13:55]I'm going to wait a multiple of that, and then I'm going to say, "If we haven't seen any acknowledgements, uh something really bad's happened."

[00:14:02]That's it. That's That's where that timeout adjusts with the round trip time. And that means we can have the same algorithm working for across a data center or across to Australia, where the round trip times are very, very different. The same algorithm or even up to a satellite, the same algorithm more or less can work. Um get something sensible cuz they're adjusting to the round trip time.

[00:14:26]Now, people look at this, and they immediately want to start tweaking it and they go, "Oh, well, you know, look at that."

[00:14:32]Yeah, that seems like a waste, doesn't it?

[00:14:35]And over the years, the exact nature of where you finish your slow start, the exact nature of what when do we halve it, when do we increase it. And this is why we end up with all of these flavors, like And I said, the moment the Oh, literally the flavor of the month actually is is cubic, which most uh which I think People are going to kill me if I get this wrong. I think Windows, Mac, uh Linux are all using those. There's other things they can use.

[00:15:06]Some of Some of these algorithms they look at the round trip time, they say, "Oh, that round trip time's creeping up.

[00:15:11]I'm going to I'm going to I'm going to shut it down in case that means congestion." So, that That's another way of doing it. But most of them are working on the losses signal.

[00:15:19]So, people look at this, and they think, "Seems a bit I could do better than that. I can probably improve on that. Maybe Oh, what if we don't create an half or if we cut in three quarter what we So, maybe what we need to do is is look at the situation in the wild and we'll see that it doesn't quite look like this kind of beautiful clean picture in here.

[00:15:39]And we'll see also why um If we think about the early days, this network those early networks were real slow, right? You know, you would you would lucky to get a few kilobits per second coming through kilobytes per second coming through.

[00:15:54]Whereas nowadays, you go, you know, I've got my one gig connection, but it's not really enough.

[00:15:59]Um and the same Yeah.

[00:16:00]>> More we all want >> Yeah, we all want more bandwidth, right?

[00:16:04]And it's Oh, could I have 10 fibers connecting to my home? We're going to have a look in the wild, look at some actual genuine packets coming through and see that the situation for TCP is not as clean maybe as I presented it here.

[00:16:15]>> So, what do the different colors mean there then?

[00:16:17]>> Uh so, these are these are telling us about the uh nature of the protocols and which particular protocol is being used for that. One we'll see later there's some black ones indicating something's gone horribly wrong. This one's indicating that I have highlighted it.

[00:16:34]And here we're going to follow this particular stream, which I hope is the correct one. Yes, it is. So, what I'm doing here, I'm grabbing a large, I think it's just over a gigabyte data file from my virtual server at Manchester, but a relatively short in network terms connection.

[00:16:53]And I'm asking Wireshark reconstruct this T this TCP stream. So, it's finding all of the packets associated so that we can take a look at that as a conversation um starting with the SYN SYN-ACK ACK.

[00:17:09]But, we'll see things are a little more complex than we teach them in the classroom. Here we're finding things right at the start of the stream working like I said they would. So, we've got a sin a syn-ack and an ack.

[00:17:29]Immediately things start to look different cuz we've got transport layer security on top. So, this is the bit that makes it secure, but it's not part of layer four. So, we don't care about it today.

[00:17:39]But, that's making it secure. So, we've all we've got a lot of cipher stuff.

[00:17:45]>> [snorts] >> And now So, again some transport layer security stuff.

[00:17:50]Here, so looking at this this is the source IP 5.28.62.245.

[00:17:56]That's my server in Manchester.

[00:17:58]192.168.68.

[00:17:59]That's a local. So, that people might recognize. That's a local address on a home network. So, that's my machine at home.

[00:18:07]And this is saying the server has sent 2,766 bytes of data and a 66-byte acknowledgement in response to it.

[00:18:18]Now, if you're a network person, you'd kind of immediately be worried by that 2766 because that's bigger than it should be.

[00:18:25]Um and it turns out I've got a lot of like mesh stuff in my home network. So, it's it's gluing packets together in a way I didn't expect it would. So, already we're seeing something that's not quite the clean pure network signal we might send. That's not what was sent over the big internet. My home network is somehow sticking them together.

[00:18:46]We've also got the thing being clocked by these TLS packets every so often. So, they're sitting there providing an extra bit of security as well. So, this is we see here four reassembled TCP segments, 8,000 bytes.

[00:19:03]So, that TLS is is adding the extra security information related to the data which sitting in those TCP packets. But we can see here is uh packet. We can see the sequence number associated with it and the acknowledgement coming back from it. And I said this acknowledgement uh when I was talking about the sequence number and acknowledgement, I was saying I'm giving you a simplified version cuz these sequence numbers and acknowledgements are not 1 2 3 4.

[00:19:34]They're actually telling which bytes we're looking at. And in the case of the acknowledgement which byte we expect.

[00:19:41]Let's actually see how this TCP window shapes up. So, I've written a little bit of code and it's going to it's going to cycle through the capture file from my home network. It's going to cycle through the capture file and it's going to ask the question every I think it's 100 milliseconds. How many bytes have we sent? It's going through it. So, since the start of file we've had 23 seconds, 24 seconds. Here's how many bytes we saw. So, it's just a little bit Python I've thrown together.

[00:20:13]I'll give Shawn the um the GitHub for it if you fancy playing with this on your own network. And then it's just going to spit up a a simple matplotlib style graph.

[00:20:24]Let's get that bigger. And here. And we'll see this isn't that beautiful kind of sawtooth. When this trace starts off actually, it's taking a long while. So, this this uh that's that's not my best scale ever. Uh megabytes per 100 milliseconds. But that's showing how many were in that 100 millisecond sample. And then the orange line we're averaging over 10 samples to get a nicer trace out of it. When it drops down, slams down real low like that, well, that's indicating there was no data whatsoever in that particular 100 milliseconds sample.

[00:21:01]Or well, actually not none, but indicating a very low amount of data in that sample.

[00:21:06]But we're not seeing that additive increase, multiplicative decrease. We're seeing much, much more uh jaggity, complex behavior because there's so many things going on. You know, we're competing for space with lots of people.

[00:21:22]So, when a lot of people see that initial diagram, they're trying to go, "Oh, we could make it more efficient if we're tweak this and tweak that."

[00:21:30]I'm going to show you another one. So, this this was uh downloading a data file using Wget. Um Wget's just a command that pulls a named file off a network. So, here I'm actually downloading uh the latest Ubuntu distribution from their website, and it's going to go and pass them all again and throw myself up the same kind of graph. And we're going to see that kind of jaggity behavior where we don't in real life see that sort of hitting a limit and coming down.

[00:22:03]But, actually, what you can see here, which I absolutely love, is >> That's the slow start, isn't >> Yeah. We can see the be- I honestly, I was so happy when I saw that. It's absolutely beautiful. I had I swear I swear it's real data. I haven't faked this. It's um Yeah, so it's a beautiful, beautiful slow start here getting us up to So, given it's a 100 uh given my stupid scale, that's about 10 megabytes per second I'm getting through to the Ubuntu server before the slow start is starting to break down here.

[00:22:33]So, we've got the beautiful slow start mechanism actually visible, which it wasn't in the previous graph. So, I think we're quite we're quite lucky to capture that in the wild.

[00:22:41]>> And then get I'm guessing life just happens, right? Like you say, there's all sorts of things going on the internet, so it's going up and it halves. It's going up halves. It might go a bit further next time and less.

[00:22:50]>> Yeah, yeah, yeah, yeah. So, I guess my my final my final message for this is when we think about TCP, people come up with these kind of it's anti-complicated.

[00:23:02]Oh, well, right, if you if you send a signal saying there's 53% congestion on route number five and if we we have no idea every single packet very carefully or you you're you're you've got two problems. You've got a problem that a lot of the mechanism is fixed, right?

[00:23:25]The I showed the packet header in the previous video and there's a little bit of space there and there are a few bits you could use if you wanted to, but that's probably going to cause trouble cuz there'll be middle boxes and firewalls looking out for funny things going on with those. So, if you start messing with those, maybe some middle boxes are rejecting your traffic as like, "Oh, what's happening here?

[00:23:45]Something dodgy, right? We'll get rid of that one."

[00:23:48]So, you don't have a lot of freedom to tweak, but also you're in quite a noisy world. The real internet is really really much more complicated than the sketches we draw out in the classroom.

[00:24:01]Um And and so much like that the TCP protocol dates back to the to the '80s.

[00:24:09]So, it it was the first thing that worked and then we're kind of it was adapted as if we made the Model T car and then people say, "Well, why doesn't it have a cup holder? Why doesn't it have a a Bluetooth? Why doesn't that TCP header is is it evolves real real slowly. Things can change in it, but it hasn't really been able to change much since the '80s. It's it's gained a couple of flags and become established.

[00:24:42]And you can't signal too much. You can't say, "I'm going to add on a mechanism which is going to to to do all of these newfangled things that I've thought of that will fix this problem."

[00:24:54]So, um in the real world, TCP does its job and it's been doing its job very, very well for for about the best part of 50 years now.

[00:25:07]Um There's so many things I've left out of this video. There's so many things that could be added on. But I think we've now we've seen we've seen the mechanisms that make it work. We've seen how in real life is pretty complicated. It's a It It It's a messy world that it's dealing with. And it's got to deal with not only this just going to some data center somewhere. It's got to deal with going across the home network, going across up to a satellite, or anything like that.

[00:25:38]So despite its age, it's it's doing a very, very, very good and complicated job.

[00:25:51]do with a VPN is we create like a passageway, so the first router hop um the first router that our traffic pops out at is in a different country.

[00:26:07]So our