1 00:00:24,093 --> 00:00:29,593 There were lots of campus Ethernets because they were really easy to deploy and you 2 00:00:29,593 --> 00:00:34,662 could put them in a department, and then you could run a wire between two 3 00:00:34,662 --> 00:00:40,054 departments and it made a bigger network. And so, we've grown up networks sort of by 4 00:00:40,054 --> 00:00:47,242 agglomeration in lots of different university campuses and, NSF came up 5 00:00:47,242 --> 00:00:53,158 with some money and said, oh we've got a little bit in our budget where we could 6 00:00:53,158 --> 00:00:59,737 get some 56 kilobit lines, and tie those campuses together. And, they did that. 7 00:00:59,737 --> 00:01:07,689 Made the NSFNET phase one. But now you're tying together ten megabit campus 8 00:01:07,689 --> 00:01:16,197 infrastructure with 56 kilobit wires and it was wildly popular because people that 9 00:01:16,197 --> 00:01:22,392 couldn't talk could suddenly talk. And they're sending emails and moving huge 10 00:01:22,392 --> 00:01:31,897 files and, just, everybody's really excited about this technology. But, any 11 00:01:31,897 --> 00:01:36,762 one of those campuses could oversubscribe a net by, you know, a factor of a 12 00:01:36,762 --> 00:01:42,757 thousand. So we had a lot of packets piling up and getting dropped. At the 13 00:01:42,757 --> 00:01:49,213 time, I was, a researcher at Lawrence Berkeley Lab, which is in the hills up 14 00:01:49,213 --> 00:01:56,915 above the Berkeley Campus. And I was also teaching on the Berkeley Campus. 15 00:01:56,915 --> 00:02:07,448 Even back in those days, which was mid 80's we had a, for every class there was a 16 00:02:07,448 --> 00:02:11,569 messages group, you know like a little news group that was set up, all the assignments would 17 00:02:11,569 --> 00:02:19,144 be put online. And I was trying to get course materials from my office in LBL 18 00:02:19,144 --> 00:02:26,343 down to a machine in Evans Hall at Berkeley. And if there was, like, zero 19 00:02:26,343 --> 00:02:34,500 throughput in the net. It was, one packet every ten minutes or so. And, it seemed 20 00:02:34,500 --> 00:02:42,531 unbelievably bad. And I went down and talked to Mike Karels, who was heading the BSD 21 00:02:42,531 --> 00:02:49,908 group, the people that developed Berkeley Unix. And he's getting reports of these 22 00:02:49,908 --> 00:02:57,192 problems from all over the country. From, in those days, the easiest way to start 23 00:02:57,192 --> 00:03:02,887 running TCP/IP was to bring up Berkeley Unix because there was a ARPA funded, very 24 00:03:02,887 --> 00:03:11,572 nice implementation in it. And everybody was seeing poor performance. So, we talked 25 00:03:11,572 --> 00:03:18,168 for a long time that day and on succeeding days, about well, what's going wrong? Is 26 00:03:18,168 --> 00:03:23,447 there some mistake in the protocol implementation? Is there some mistake in 27 00:03:23,447 --> 00:03:32,177 the protocol? This thing was working on smaller scale tests and then it suddenly 28 00:03:32,177 --> 00:03:39,936 fell apart. I think we struggled for three or four months, just, going through the 29 00:03:39,936 --> 00:03:46,150 code writing tools to capture packet traces and looking at the packet traces 30 00:03:46,150 --> 00:03:52,897 and trying to, to sort out what was breaking, and I, I remember, the two of us 31 00:03:52,897 --> 00:03:59,670 were sleeping in Mike's office after we'd been pounding our head against the wall 32 00:03:59,670 --> 00:04:04,930 for, for literally months. And one of us, I can't remember which one said, you know 33 00:04:04,930 --> 00:04:08,333 that the reason I can't figure out why it's breaking is, I don't understand how 34 00:04:08,333 --> 00:04:15,239 it ever worked. You know we're, we're sending these bits out at ten megabits. 35 00:04:15,239 --> 00:04:21,638 They're zipping across campus.They're running into this 56 kilobit wire. 36 00:04:21,638 --> 00:04:26,335 We expect them to go through this wire, pop out on the other side. Go through 37 00:04:26,335 --> 00:04:34,547 How could that function? That turned out to be the, the crucial starting point. 38 00:04:34,547 --> 00:04:42,365 At that point, we started saying well what is there about this protocol that makes it 39 00:04:42,365 --> 00:04:47,261 work, how does it deal with all of those bandwidth changes, how does it deal with 40 00:04:47,261 --> 00:04:55,014 the multiple hops? So, this picture, that direction is time, this direction is 41 00:04:55,014 --> 00:05:01,629 bandwidth. So that's a fat pipe and that's a skinny pipe, and, the scale at the time, 42 00:05:01,629 --> 00:05:09,628 this is a ten megabit pipe and this is a 56 kilobit pipe. So, here the difference 43 00:05:09,628 --> 00:05:17,648 is about three to one. It was really closer to hundred to one. And, so time, 44 00:05:17,648 --> 00:05:24,957 seconds times bits per second equals bits. So each of these little boxes in there is 45 00:05:24,957 --> 00:05:32,062 a packet, it's the number of bits in the packet and if you scrunch it down in 46 00:05:32,062 --> 00:05:40,599 bandwidth its got to spread out in time because the number of bits doesn't change. And so see 47 00:05:40,599 --> 00:05:44,835 the burst of packets, a window's worth of packets, gets launched. It's going to fly 48 00:05:44,835 --> 00:05:50,418 through the net until it hits this fast to slow transition. And then, because the 49 00:05:50,418 --> 00:05:55,599 packets have to stretch out in time, they'll have to sit there and wait as 50 00:05:55,599 --> 00:06:05,093 they're fed into the slower wire and you - they pop out the other side. 51 00:06:05,093 --> 00:06:10,100 They get spread out by this bottleneck, by the slower wire. Once they're spread out, they 52 00:06:10,100 --> 00:06:15,557 stay spread out. That there's nothing to push them back together again. They hit a 53 00:06:15,557 --> 00:06:21,924 receiver, it turns every data packet into an ACK. So you've got a bunch of ACKs that 54 00:06:21,924 --> 00:06:26,735 are going back towards the sender. And they remember what's the right spacing for 55 00:06:26,735 --> 00:06:33,814 that bottleneck. So the ACKs get back to the sender and every ACK gets turned 56 00:06:33,814 --> 00:06:40,965 into a data packet. So we can see the data packets flowing back and this is after 57 00:06:40,965 --> 00:06:46,739 one round trip time. Now the packets are coming out perfectly spaced so they go by 58 00:06:46,981 --> 00:06:53,467 a new one goes into the net in exactly the time it takes a packet to exit from the 59 00:06:53,467 --> 00:06:58,811 bottleneck. So these ACKs are sort of acting as a clock that tells you, tells 60 00:06:58,811 --> 00:07:05,548 the sender when it's safe to inject every new packet. And they're always going to be 61 00:07:05,548 --> 00:07:08,809 spaced by whatever is the slowest point in the net. ≫> And then the key thing 62 00:07:08,809 --> 00:07:13,040 is how, how quick, how can you get to steady state, sort them most quickly without wasting 63 00:07:13,040 --> 00:07:19,091 ≫> I, yeah, and the issue of the failure we saw was: this works 64 00:07:19,091 --> 00:07:25,541 perfectly after you've exchanged a round trip time worth of packets. But, when 65 00:07:25,541 --> 00:07:32,389 you're starting up, when you're here, there's no clock. And so the hard part on 66 00:07:32,389 --> 00:07:37,135 TCP is not getting it running, it's getting it started. Because once you've 67 00:07:37,135 --> 00:07:41,145 got it running, you've got a clock that tells you exactly what to do. If you turn 68 00:07:41,145 --> 00:07:46,244 them on suddenly you get in this repetitive failure mode where you saturate 69 00:07:46,244 --> 00:07:51,496 the, the buffering that was available at some gateway. Then when you retransmit you 70 00:07:51,496 --> 00:07:56,894 do the same thing again. So your always losing packets. But if you turned it on 71 00:07:56,894 --> 00:08:00,889 more gradually, then you wouldn't overload the buffering. And then you'd get enough 72 00:08:00,889 --> 00:08:08,522 of a clock going, so that you'd control the amount of backlog to fit the available 73 00:08:08,522 --> 00:08:11,188 buffer. But you'd still be growing the number of packets in-flight, so that 74 00:08:11,188 --> 00:08:15,447 you'd eventually get a, a, you'd start with a kind of sporadic clock where you you'd 75 00:08:15,447 --> 00:08:19,661 eventually fill in the details and get a per-packet clock. ≫> How did you 76 00:08:19,661 --> 00:08:24,282 get it to the point where it was in all the TCP/IP implementations on the planet. 77 00:08:24,282 --> 00:08:27,835 Cuz they kind of have to cooperate in a way. ≫> So, remember it was a much 78 00:08:27,835 --> 00:08:33,657 simpler time when you're talking about all the TCP/IP implementations on the planet. 79 00:08:33,657 --> 00:08:38,794 At that time, there were, like four. So, there was the Berkeley Unix one. There was 80 00:08:38,794 --> 00:08:46,373 the MIT PC/TCP. There was a BBN one that was used in Butterflies and Nymphs. And 81 00:08:46,373 --> 00:08:54,930 there was a Multics one. I took the couple of TCP kernel modules that we'd been 82 00:08:54,930 --> 00:09:00,981 working on. Packaged them up a tar. I had this horrible driver hack that would 83 00:09:00,981 --> 00:09:05,693 let us snarf packets from the kernel. And I mean, it was really a horrible driver 84 00:09:05,693 --> 00:09:10,689 hack. It was the way you said what you wanted to snarf was by adb-ing the kernel, 85 00:09:10,689 --> 00:09:16,119 you, you wrote, in binary, some new values. These are the ports that I wanna 86 00:09:16,119 --> 00:09:19,452 look at. And the driver would capture those into a circular buffer. And you'd 87 00:09:19,452 --> 00:09:28,857 read kernel memory to pull that buffer out. Craig Leres and Chris Torek who were 88 00:09:28,857 --> 00:09:38,469 working in my group at LBL and were both long time kernel hackers were just 89 00:09:38,469 --> 00:09:45,363 embarrassed at this and they put together a really nice, clean driver I think called 90 00:09:45,363 --> 00:09:49,815 BPF, the Berkeley Packet Filter, that would let you pull packets out of the 91 00:09:49,815 --> 00:09:58,681 kernel by a, a very efficient I/O control interface and so we bundled all of that up 92 00:09:58,681 --> 00:10:08,710 and on the TCP/IP mailing list, which, in those days was, you know, TCP/IP was very 93 00:10:08,710 --> 00:10:13,049 experimental. It was very leading edge. And pretty much everybody who was playing 94 00:10:13,049 --> 00:10:17,988 with it was on that mailing list. So, now, since this stuff was available, a bunch of 95 00:10:17,988 --> 00:10:26,185 people FTPd it, tried it, it blew up, sent kernel core dumps, and bug reports, and 96 00:10:26,185 --> 00:10:31,763 I fixed the bug reports and put new versions out. Somebody would immediately come back 97 00:10:31,763 --> 00:10:38,775 and say, paniced here, do you want the kcore? And I'd go, oh, no. [laugh] embarrassed 98 00:10:38,867 --> 00:10:41,734 Put out a new version, go out. Somebody else would come back and 99 00:10:41,734 --> 00:10:47,690 say, paniced here, and fix that. And just cycled like that. And after about a day we 100 00:10:47,690 --> 00:10:53,955 got a version that didn't immediately panic, and then started working on the, 101 00:10:53,955 --> 00:10:59,525 actual algorithms and a little bit of tuning to make sure that it actually did 102 00:10:59,525 --> 00:11:07,991 good all the time and didn't do any harm. Just completely a, a community effort and 103 00:11:07,991 --> 00:11:17,546 ya know sort of when the, the community was saying this, mostly does good, and never seems to 104 00:11:17,546 --> 00:11:23,632 do harm. That's pretty much what Mike needed to put it into the kernel. 105 00:11:23,632 --> 00:11:29,624 So he took that, the community developed modules, and rolled them into the BSD release.