[00:11.530 --> 00:16.110]  The traditional first words of any conference are, is this on?
[00:17.470 --> 00:17.910]  Yes!
[00:19.090 --> 00:19.770]  Can everyone hear me?
[00:22.930 --> 00:23.370]  Welcome.
[00:23.370 --> 00:24.290]  Welcome, everybody.
[00:28.410 --> 00:31.510]  This is the H2K2 conference.
[00:31.750 --> 00:34.170]  I see a lot of name tags, so you're all in the right place.
[00:34.790 --> 00:41.790]  We're going to go ahead and get started more or less on time, even though, as you've noticed, not quite everything is set up at the conference site.
[00:41.790 --> 00:51.270]  But we do have speakers here, and we do have an extremely exciting set of panelists and talks and all kinds of other things going on.
[00:51.770 --> 00:59.770]  Let me just mention one thing to you, which is, if you might have noticed, the elevators out there are tasked to run between this floor and the second floor.
[00:59.990 --> 01:01.870]  So that's really sort of your way in and out.
[01:02.030 --> 01:05.670]  And we thought that was a good idea, and we'll see later on if it actually is.
[01:06.990 --> 01:09.910]  But don't expect to be able to get elsewhere from the elevators.
[01:10.090 --> 01:13.330]  Once you get in there on 18, we'll have to go back down in the second floor.
[01:14.490 --> 01:21.790]  So our first talk is the shape of the Internet, as you see, with Adam.
[01:22.730 --> 01:23.890]  And go ahead and take it away.
[01:26.470 --> 01:26.950]  Hello?
[01:27.770 --> 01:28.650]  Can anyone hear me?
[01:28.950 --> 01:29.310]  No?
[01:30.890 --> 01:31.810]  Hi, how's it going?
[01:32.490 --> 01:39.750]  You can call me either Javaman or Adam, whichever you prefer.
[01:40.250 --> 01:41.790]  It doesn't make much difference to me.
[01:42.970 --> 01:48.310]  And I guess today I'll be addressing you about a topic that's been of great interest to me and some...
[01:48.310 --> 02:02.090]  actually a lot of interest in the academic research community of computer networks on what is the actual shape and structure and how does the actual Internet take form.
[02:02.290 --> 02:08.130]  And I want to also discuss some of the actual implications of it, which not too many people have discussed yet in the academic world.
[02:08.130 --> 02:19.070]  I mean, it really is an effort to translate what I view to be the critical research that's being done in academia over to the active community.
[02:19.390 --> 02:24.850]  Because, let's be honest, I mean, they may find a lot of the basic parameters.
[02:25.190 --> 02:34.650]  They might discover a lot of the behaviors that go on, but they don't know sometimes how to fully exploit them for their own purpose.
[02:34.650 --> 02:37.210]  Is there anyone here who is at Infocom 2002?
[02:38.270 --> 02:38.890]  Right, James?
[02:39.550 --> 02:42.510]  This is a big network of conferences in New York two weeks ago.
[02:44.170 --> 02:44.670]  Showed up.
[02:45.630 --> 02:47.730]  What do I mean by the shape of the Internet?
[02:48.590 --> 02:52.410]  There are several ways that we could define the structure.
[02:53.170 --> 02:57.590]  We could look at it on a web level where we just look at URL links.
[02:57.930 --> 03:02.950]  We could look at it on a BGP level, a router level, you know, physical Ethernet level.
[03:02.950 --> 03:06.370]  But mostly we could be concentrating on the BGP level.
[03:06.690 --> 03:14.950]  And just as a good example, some of the related research is, how many people remember a couple years ago that everyone said that the Internet was shaped like a bowtie?
[03:15.530 --> 03:16.530]  Do you remember this?
[03:18.090 --> 03:18.510]  Hands?
[03:19.090 --> 03:19.870]  You got to show hands.
[03:21.810 --> 03:22.230]  Excellent.
[03:22.790 --> 03:25.030]  That was a URL level example.
[03:26.010 --> 03:29.610]  And if you think about it, the Internet really can't be shaped like a bowtie because that was a directed graph.
[03:29.610 --> 03:32.570]  And if that was true, it would be mostly segmented.
[03:32.750 --> 03:35.890]  So you would be able to traverse large sections of the network.
[03:38.190 --> 03:42.630]  But conventionally, most people thought that the Internet was shaped something like what's called a random graph.
[03:42.910 --> 03:45.730]  Let's go into what a graph is.
[03:46.410 --> 03:47.670]  Is anyone here familiar with graph theory?
[03:49.630 --> 03:50.170]  A couple?
[03:50.370 --> 03:50.790]  A couple people?
[03:50.970 --> 03:51.110]  All right.
[03:51.110 --> 03:53.770]  Graph theory is basically a mathematical construction.
[03:55.670 --> 03:57.270]  We define the set...
[03:57.270 --> 04:01.670]  We define a graph G as a set of vertices and edges.
[04:03.670 --> 04:04.850]  Oh, crap.
[04:05.110 --> 04:05.390]  Sorry.
[04:10.830 --> 04:11.450]  All right.
[04:11.610 --> 04:12.150]  How does that look?
[04:12.490 --> 04:12.910]  Good?
[04:13.830 --> 04:14.290]  Okay.
[04:15.070 --> 04:17.330]  We define a graph as a set of vertices and edges.
[04:17.330 --> 04:24.390]  V and A in each edge is defined as a ordered pair of vertices.
[04:25.250 --> 04:27.450]  So, for example, if we just...
[04:27.450 --> 04:28.930]  I mean, a very simple graph would be a triangle.
[04:30.050 --> 04:31.670]  Node, node, node.
[04:33.490 --> 04:34.770]  Three nodes and three edges.
[04:36.470 --> 04:36.910]  Excuse me?
[04:37.870 --> 04:39.510]  Oh, Jesus Christ.
[04:40.310 --> 04:40.590]  All right.
[04:42.510 --> 04:45.050]  So, as I was saying, a simple graph would just be...
[04:45.050 --> 04:47.110]  An example would be three nodes and three edges.
[04:47.510 --> 04:51.170]  And this is actually how we model most data and most relations.
[04:51.350 --> 04:56.790]  If you think about good examples, it would be six degrees of Kevin Bacon, for example.
[04:57.590 --> 04:58.470]  That is actually...
[04:58.470 --> 05:03.430]  I think it's a very appropriate one, where each node would be an actor, and the edges between them would be films that they shared.
[05:03.910 --> 05:05.130]  That's how you actually draw a relation.
[05:05.130 --> 05:08.690]  And if you were to traverse the graph from one...
[05:08.690 --> 05:09.330]  And the actual...
[05:09.330 --> 05:13.950]  The total path length would be the traversal between Kevin Bacon and any specific actor.
[05:15.490 --> 05:19.450]  And so, I mean, you know, this person is six hops, seven hops away, for example.
[05:20.030 --> 05:24.290]  In the mathematical community, they have something along those lines called the Erdo number.
[05:24.710 --> 05:33.730]  This is basically how far away a person is from Paul Erdo, based on how many papers you co-author with people that co-author people with Paul Erdo.
[05:33.730 --> 05:36.990]  So that's how you traverse that graph, for example.
[05:37.950 --> 05:38.390]  So...
[05:39.050 --> 05:43.530]  People thought the Internet was what was called a Waxman graph.
[05:44.970 --> 05:45.530]  Basically...
[05:46.790 --> 05:48.750]  I want to go through these things so quickly.
[05:53.140 --> 05:55.460]  Basically, what a Waxman graph is, is...
[05:55.460 --> 06:00.020]  It's very similar to a wireless-style topology.
[06:01.280 --> 06:07.440]  Basically, you say, you have a random field of nodes.
[06:08.180 --> 06:11.440]  And the connection between them is based off a...
[06:14.420 --> 06:18.040]  Really a planar relationship, but it's based off the function of the distance between two nodes.
[06:24.780 --> 06:25.300]  And...
[06:25.300 --> 06:28.120]  What are the routing protocols against?
[06:28.460 --> 06:30.480]  They're testing against this, they're testing against meshes.
[06:31.680 --> 06:33.060]  Mesh being just simple.
[06:33.500 --> 06:35.000]  If you can imagine, just a grid.
[06:36.660 --> 06:38.100]  An individual nodes connecting.
[06:41.090 --> 06:44.010]  And when I mean testing routing protocols, I mean testing stuff like...
[06:44.010 --> 06:46.410]  So you develop protocol like RIP.
[06:47.070 --> 06:49.790]  How do you check it out before you actually implement it?
[06:49.790 --> 06:55.050]  And there really isn't too many formal verification tools that exist for routing analysis.
[06:56.130 --> 07:00.750]  There are some mathematical tools that do exist, but you wanna try it out against a large graph.
[07:00.830 --> 07:03.310]  You wanna simulate against performance.
[07:04.350 --> 07:06.190]  Or simulate to try to determine performance.
[07:06.710 --> 07:10.110]  How you do so against the Internet, you can't.
[07:10.330 --> 07:12.090]  I mean, you don't know exactly what the full...
[07:12.090 --> 07:15.430]  Well, at first they didn't know what the full structure of the Internet was.
[07:15.610 --> 07:18.150]  They even tried to determine how to go about that.
[07:18.150 --> 07:24.130]  So using these rough models, for example, one being a regular mesh and one being just a simple random graph.
[07:26.510 --> 07:28.630]  So, we'll flash back to 1999.
[07:29.070 --> 07:40.790]  And this guy by the name of, actually probably about 98, this guy by the name of Michaelis Folatos, he's now a professor at UC Riverside, was working on his PhD in multicast.
[07:41.730 --> 07:49.910]  And his doctoral committee comes to him and says, you know, you have to define, you know, give, you know, certain optimality points of your multicast trees.
[07:50.150 --> 07:51.850]  Is anyone familiar with IP multicast?
[07:52.650 --> 07:54.550]  It never really, it never really hit big.
[07:55.350 --> 07:57.310]  And it's really a router level thing.
[07:57.410 --> 08:05.570]  But what happens with IP multicast is you send, you have an initiation protocol, something like RSVP or something along those lines.
[08:06.750 --> 08:12.370]  And you define, and what happens is that you're supposed to create a Steiner tree across a network topology.
[08:13.110 --> 08:17.430]  And what happens is that initial packer come out and each router along the lines of reproducing packets.
[08:17.570 --> 08:20.670]  And they thought it would be a great solution for doing Internet broadcasting.
[08:21.270 --> 08:25.130]  And at the surface, yeah, it would work great if people would adopt it.
[08:25.370 --> 08:31.550]  But it's much easier to do application layer things than it is to do network layer things.
[08:32.010 --> 08:40.050]  Application layer and layer, or layer five and layer two technologies can roll out in six months.
[08:40.430 --> 08:42.630]  Layer three takes sometimes upwards of ten years.
[08:43.490 --> 08:45.590]  And, you know, we're still seeing that on 5Pv6.
[08:46.530 --> 08:52.690]  So anyway, he was working on this, his doctoral thesis in IP multicast.
[08:53.450 --> 09:02.170]  And so, on his committee, they asked him, you know, well, how would you actually say, how effective is this, is this tree for, in the lines of optimality?
[09:02.310 --> 09:03.210]  Or how effective is this?
[09:03.310 --> 09:04.030]  And he's like, well, I don't know.
[09:04.130 --> 09:05.110]  No one knows the shape of the Internet.
[09:05.330 --> 09:05.750]  You know, ooh.
[09:06.270 --> 09:10.670]  And it's like, well, it's like, well, the guy on his thesis committee said, well, you really should do some measurements and find out.
[09:11.250 --> 09:11.890]  And the guy's like, fine.
[09:11.990 --> 09:12.610]  We'll do some measurements.
[09:14.450 --> 09:17.250]  And, meanwhile, his two brothers were also college professors.
[09:19.150 --> 09:20.970]  And, I can't remember if they ever thought it was his name.
[09:21.210 --> 09:24.430]  But anyway, so he says to his brother, this is what they want me to do to get my PhD.
[09:24.890 --> 09:25.850]  He's like, how am I supposed to do that?
[09:26.510 --> 09:38.130]  And his one brother had just read a book called Fractals, Chaos, and Power Laws, Visions from an Infinite Dimension.
[09:38.170 --> 09:39.610]  I think it's the full title of it.
[09:41.030 --> 09:42.570]  And he had fractals on the brains.
[09:42.690 --> 09:44.430]  He says, oh, oh, the Internet has got to be a fractal.
[09:44.450 --> 09:45.050]  It's got to be a fractal.
[09:45.170 --> 09:45.730]  It's got to be a fractal.
[09:45.810 --> 09:46.630]  It's like, well, why do you think that?
[09:46.670 --> 09:49.610]  He's like, well, every natural process ends up being a fractal.
[09:49.650 --> 09:50.830]  So the Internet has to be one, too.
[09:52.510 --> 09:54.570]  And he said, well, how would we go about proving this?
[09:54.570 --> 09:59.250]  And some of the conventional methods of showing something in a fractal is like box counting methods.
[09:59.550 --> 10:02.570]  Like if you were to, let's say we have a coastline.
[10:05.130 --> 10:10.450]  You would lay down boxes of a certain size, you know, n by n.
[10:11.430 --> 10:14.610]  And you would count how many boxes it would take to cover that area.
[10:17.910 --> 10:23.890]  And the next thing you would do is you would reduce the size of n by, like, n over 2, for example.
[10:23.890 --> 10:26.890]  And it should take two times as many boxes.
[10:27.590 --> 10:29.310]  I think it's two times as many or a power of 10.
[10:29.430 --> 10:30.070]  I can't remember exactly.
[10:30.270 --> 10:30.830]  I just fell in my head.
[10:31.390 --> 10:32.890]  To fully cover the coastline.
[10:34.170 --> 10:35.430]  So we could do this to the Internet.
[10:35.670 --> 10:42.630]  And so they tried coming up with some kind of algorithm to translate, you know, the global topological map of the Internet to this.
[10:42.730 --> 10:45.950]  And first of all, they didn't even know how to derive the global topological map to begin with.
[10:46.730 --> 10:48.770]  So they stopped that approach.
[10:54.250 --> 11:02.180]  So what they did is pull out the BGP data from places like, which now exists for everyone.
[11:02.650 --> 11:03.650]  Everyone can do this now.
[11:03.990 --> 11:05.650]  But they went and examined BGP data.
[11:10.530 --> 11:11.970]  It's hard to look at that.
[11:12.390 --> 11:13.930]  It's going blind from the light.
[11:15.670 --> 11:24.150]  So anyway, you can get this now from places like NLANL, CADA.org.
[11:28.210 --> 11:31.610]  They've now been putting on their slides recently, Al, CADA.
[11:34.070 --> 11:40.430]  But this is for the Center for Analysis of, or Creative Analysis.
[11:40.830 --> 11:42.710]  Anyway, all they do is Internet data analysis.
[11:43.130 --> 11:50.830]  Like trying to do, pulling out, you know, topological structures and trying to determine, you know, some of the actual global emergent properties of the network.
[11:54.790 --> 11:56.710]  Anyway, so you're able to pull out the BGP data.
[11:56.830 --> 11:59.750]  And they basically took it and they dropped it and they created a graph out of the data.
[12:00.570 --> 12:07.690]  And so you would have a centralized point, you know, like this would be some AS, some autonomous system.
[12:07.770 --> 12:08.650]  Is everyone familiar with BGP?
[12:09.910 --> 12:10.310]  Okay.
[12:11.210 --> 12:12.010]  What's BGP?
[12:12.350 --> 12:16.490]  You have, everyone's got small networks, or most people have small networks in their house.
[12:16.690 --> 12:18.970]  You do static writing in a small network, okay?
[12:18.970 --> 12:23.310]  Let's say we go to a small core, just like small SP level.
[12:23.530 --> 12:24.830]  You have multiple routers.
[12:26.810 --> 12:29.950]  In a situation like this, for example.
[12:36.540 --> 12:38.960]  Sounds like the, the telco graph.
[12:39.480 --> 12:43.400]  Anyway, you have a, you have a pair of routers, R1 and R2.
[12:45.120 --> 12:52.120]  And you have, you know, your three, your mail server and your web server and your, I don't know, NetNews, you know, Usenet.
[12:52.260 --> 12:53.740]  I don't know if anyone even uses that anymore.
[12:54.340 --> 12:54.840]  Everybody in this room.
[12:55.740 --> 12:56.480]  Usenet was the bomb.
[12:57.120 --> 12:57.480]  Anyway.
[13:00.380 --> 13:02.340]  And even in this situation, you do static routing.
[13:02.500 --> 13:08.420]  But when you start getting more and more complex network topologies, you have to implement, you know, or OSPF.
[13:08.980 --> 13:11.720]  RIP is what's called a, a distance vector protocol.
[13:12.040 --> 13:13.700]  And OSPF is a link state protocol.
[13:14.120 --> 13:18.640]  Basically, a distant vector only communicates with its neighbors immediate link information.
[13:19.380 --> 13:26.400]  And, and, link state protocols broadcast over the entire global network, the information.
[13:26.740 --> 13:28.720]  That's all well and good for the inside of the subnet.
[13:28.720 --> 13:30.640]  What happens when you get above the subnet?
[13:30.860 --> 13:33.260]  Or inside, above the, the ISP.
[13:33.440 --> 13:34.560]  You go to tier two ISPs.
[13:35.340 --> 13:36.920]  Tier two ISPs do the same thing.
[13:37.060 --> 13:40.060]  They'll, you know, they'll just do internal routing policies.
[13:40.180 --> 13:46.540]  When you get to tier one, for example, though, there's no real good agreement on how to route in between tier one ISPs.
[13:47.260 --> 13:55.220]  You can't, you know, no one wants to implement a RIP protocol, something like that, because all it does is change, is pick an optimality point of the actual network.
[13:55.680 --> 13:58.460]  But it doesn't actually give you any control about where your packets really go.
[13:59.080 --> 14:03.940]  So what BGP does is, let's say we have a situation where you have a node here.
[14:04.120 --> 14:05.720]  We'll call this, I don't know, Apple.
[14:08.620 --> 14:10.540]  And this is Microsoft.
[14:14.840 --> 14:17.600]  And this is ISP.
[14:18.380 --> 14:19.900]  This is a customer.
[14:22.120 --> 14:22.600]  Okay?
[14:23.060 --> 14:24.240]  Network looks something like this.
[14:25.380 --> 14:29.880]  And let's say this is a, so apple.com has two routes to a customer.
[14:30.700 --> 14:33.260]  Two physical possible ways of actually getting a customer.
[14:33.980 --> 14:35.780]  One's through Microsoft and one's through an ISP.
[14:36.280 --> 14:39.500]  And Apple wants to sell this customer a product.
[14:39.780 --> 14:42.180]  But Apple doesn't want Microsoft to know what the hell is selling.
[14:42.660 --> 14:49.680]  So, how would you actually be able to go about, you know, routing these packets only to the customer without having to go across, you know, Microsoft?
[14:49.680 --> 14:53.240]  Well, conventional routing protocols would say whatever is the best path it's going to take at the end.
[14:54.200 --> 14:56.580]  BGP is what's called a distance vector protocol.
[14:56.860 --> 15:00.560]  All they do is share physical interconnections.
[15:00.800 --> 15:08.600]  They say that Microsoft.com, for example, would broadcast to Apple.
[15:09.040 --> 15:14.920]  You can get to customer through me, then through the ISP.
[15:15.440 --> 15:18.740]  That's not exactly the, you know, that's not exactly the packet for that.
[15:19.160 --> 15:21.060]  But that's roughly the idea of it.
[15:21.920 --> 15:24.900]  And ISP broadcasts to Apple.
[15:25.280 --> 15:26.840]  You can get to customer through me.
[15:27.680 --> 15:31.280]  And so, what happens is that Apple gets a list of these routes.
[15:31.760 --> 15:41.400]  And he's able to say, by defining a local policy, which is completely alien to, they're completely unknown to his neighbors, which of these routes to pick.
[15:42.260 --> 15:43.300]  And this is BGP.
[15:43.560 --> 15:50.440]  If you think about it, basically what you're doing, you're stating who you're able to connect from, and you're able to, you know, define whether or not you like these people.
[15:51.160 --> 15:53.500]  On the surface, this seems very fragile.
[15:53.760 --> 15:55.380]  In reality, it's very fragile.
[15:57.520 --> 16:01.160]  And there is a lot, let me give you, okay.
[16:01.280 --> 16:08.260]  Do you remember a couple of years ago how Mudge and a couple of the other guys came from Congress and said they could break the Internet in five minutes?
[16:08.560 --> 16:09.200]  This is how.
[16:09.540 --> 16:13.140]  The reason why is because BGP routes are exchanged over TCP inside the network core.
[16:13.960 --> 16:18.820]  If two peers do not trust each other, then they will shut each other out from accepting routes.
[16:19.000 --> 16:24.120]  You will get two peers not to trust each other by dropping packets inside the TCP window and disrupting the TCP session.
[16:24.980 --> 16:30.060]  That's actually not too easy traditionally because you have to know the initial sequence number of the communication.
[16:31.520 --> 16:46.380]  But, a guy by name, Tim Newsham, showed that it is possible to predict within a certain statistical error the initial sequence numbers used by different operating systems based off of pre-known statistics about the systems.
[16:46.380 --> 16:51.580]  So, in general, it's possible, yes, to fracture the Internet.
[16:52.620 --> 16:53.880]  That's, I digress.
[16:55.620 --> 16:58.280]  So, what they did was they extracted BGP data.
[16:58.420 --> 17:05.240]  And they created a very long list of all, of all this BGP data.
[17:05.240 --> 17:07.620]  And they drew, they had a computer, create a graph.
[17:07.800 --> 17:11.040]  And you're able to do this with, you know, standard structures.
[17:12.820 --> 17:13.760]  And, you can see.
[17:13.920 --> 17:17.340]  You think about it as just, you know, you define with, you know, a linked list or something like that.
[17:17.520 --> 17:24.660]  Or, you know, it just depends on how sparse the graph is, what would be the most optimal data structure for it.
[17:25.300 --> 17:29.120]  But, anyway, so they defined this structure.
[17:29.540 --> 17:32.260]  And they went and started doing statistical measurements on this structure.
[17:32.980 --> 17:44.370]  Now, as we go back to the Waxman graph, let's say we were to do an analysis where we wanted to look at the out degree versus the rank.
[17:46.250 --> 17:47.490]  Now, what is out degree?
[17:49.190 --> 17:50.790]  Again, this is a graph theoretic concept.
[17:51.550 --> 17:56.390]  Basically, it's the number of edges that radiate from a specific node.
[18:00.130 --> 18:03.650]  In graph theory, you're allowed to have digraphs, which means directed graphs.
[18:03.770 --> 18:08.470]  Basically saying that this is, you know, node A goes to node B only through this path.
[18:08.470 --> 18:09.370]  It's not a reverse path.
[18:09.730 --> 18:11.870]  But we're going to exclude that possibility.
[18:11.970 --> 18:13.750]  We're just going to look at undirected graphs.
[18:15.030 --> 18:18.190]  So, for example, if we look at this node, how many edges are radiating from this one?
[18:18.410 --> 18:18.730]  Five.
[18:19.210 --> 18:20.210]  From this guy, three.
[18:20.630 --> 18:20.990]  Three.
[18:21.810 --> 18:22.170]  Four.
[18:22.810 --> 18:23.170]  Four.
[18:23.550 --> 18:23.830]  Two.
[18:24.070 --> 18:24.770]  And so on.
[18:28.150 --> 18:35.490]  So they made, they went through and they did this for every, they created a graph and they did this for every node that they pull out.
[18:35.570 --> 18:37.270]  And they also did it for other random graphs.
[18:38.670 --> 18:40.430]  Erdo-Renni style random graphs.
[18:40.630 --> 18:52.330]  And all Erdo-Renni style random graphs mean is that you have a set of vertices v, which has a numerous, we'll say it has a complete size of little v.
[18:52.330 --> 18:54.130]  There's a total number of possible vertices.
[18:54.470 --> 18:55.750]  And we started off with zero edges.
[18:56.190 --> 18:59.770]  And then we continue to add edges until eventually we hit a complete graph.
[19:00.210 --> 19:08.410]  So our number of edges goes from zero to v by v plus one or two.
[19:08.790 --> 19:09.770]  What's a complete graph?
[19:09.770 --> 19:13.170]  Basically, every possible edge that can exist does exist.
[19:13.490 --> 19:14.040]  So for a...
[19:16.670 --> 19:17.910]  Am I missing one?
[19:18.430 --> 19:19.750]  That's K4.
[19:20.810 --> 19:21.210]  Okay.
[19:22.010 --> 19:22.450]  What was that?
[19:24.870 --> 19:25.890]  Oh, Jesus.
[19:26.230 --> 19:26.670]  I'm sorry.
[19:26.970 --> 19:27.790]  That's K4.
[19:27.790 --> 19:30.290]  Basically, what it says is that you have a set of nodes.
[19:30.570 --> 19:33.210]  Every possible edge that can exist between the nodes does exist.
[19:33.430 --> 19:34.390]  That's a complete graph.
[19:34.770 --> 19:38.710]  And as we can see for four edges, it's one, two, three, four, five, six.
[19:40.090 --> 19:40.890]  So it's...
[19:45.180 --> 19:47.520]  4 by 5 is 20, 10.
[19:48.220 --> 19:51.260]  So right there on me, this is b minus one.
[19:56.180 --> 19:56.980]  And that's...
[19:56.980 --> 19:57.600]  4 by 3 is...
[19:57.600 --> 19:58.040]  Oh, yeah.
[19:58.200 --> 19:59.160]  That's the actual equation.
[19:59.300 --> 19:59.560]  I'm sorry.
[20:02.360 --> 20:15.960]  And so in Paul and Ardell-Renni graphs, if you look at, for example, the out-degree, which we just discussed, versus the rank, which basically, if you're making an order list of all the octa-degrees, and so for this guy, we have 4, 4, 4, I'm sorry, 3,
[20:16.180 --> 20:16.320]  3.
[20:17.860 --> 20:19.000]  That's actually a bad example.
[20:20.860 --> 20:21.880]  And we're to order them.
[20:22.080 --> 20:23.580]  1, 2, 3, 4.
[20:24.480 --> 20:27.700]  And we're to plot, on one axis,
[20:35.830 --> 20:42.610]  the rank versus the degree.
[20:44.170 --> 20:46.670]  On a complete graph, we would get a straight line, right?
[20:49.090 --> 20:52.150]  On a complete random graph, we would get what's called Poisson distribution.
[20:53.970 --> 20:55.270]  It looks something like this.
[20:57.230 --> 21:01.830]  If we're looking at a log-log scale, and we're to plot for the Internet, you get something completely different.
[21:02.790 --> 21:03.610]  You get a straight line.
[21:05.650 --> 21:08.870]  And the only time you really see these straight lines is what's in power-law relationships.
[21:09.770 --> 21:27.770]  What this means is we define a function g of g of a times x is equal to f of a g of x.
[21:27.930 --> 21:31.870]  What that means is if you scale the input, it's just the original function scaled again.
[21:32.530 --> 21:33.730]  It's called a scaling law.
[21:34.310 --> 21:43.710]  An example is if you look at... you've probably heard this example a thousand times, but if you look at a coastline a thousand miles away, and you look at a coastline from a meter... or a thousand kilometers away, and you look at a coastline from a meter away,
[21:43.810 --> 21:45.510]  it looks kind of exactly the same shape.
[21:45.810 --> 21:49.370]  And you look at the same coastline ten centimeters away, it looks kind of the same shape.
[21:49.690 --> 21:50.650]  This is what that's saying.
[21:51.150 --> 21:54.810]  It's the same general structure repeated over and over and over again.
[21:54.810 --> 22:01.850]  And it doesn't matter what scale you look at it on, you just have the original network scaled by that parameter.
[22:03.430 --> 22:08.330]  And so they found on the BGP level that the Internet actually takes this power law structure.
[22:09.210 --> 22:10.970]  And it's actually kind of an interesting fact.
[22:12.370 --> 22:19.010]  Here we have a completely man-made structure that is only very, very young.
[22:20.110 --> 22:26.910]  But it takes this very innate property of being a fractal.
[22:27.190 --> 22:29.250]  Something we see over and over and over again in nature.
[22:29.890 --> 22:31.150]  In a way, it's kind of beautiful.
[22:31.490 --> 22:34.450]  And that's one of the reasons why I really chose to have a study of this.
[22:35.250 --> 22:36.470]  Now, why does this happen?
[22:38.030 --> 22:43.950]  There's a couple of reasons that have been cited.
[22:46.130 --> 22:48.130]  And this is really up to debate right now.
[22:49.250 --> 22:55.390]  The first guy is a physicist by the name of Barry Bassi.
[22:55.630 --> 22:58.790]  He published this in Nature not too long ago.
[22:58.870 --> 23:04.730]  And what he says is that you're able to grow a graph by adding nodes.
[23:05.410 --> 23:09.030]  And node will only connect to nodes that are already in the member of the network.
[23:09.330 --> 23:10.150]  That's fine.
[23:10.930 --> 23:17.550]  And the rate of connection, or who it would connect to, is a function of the out degree of its target.
[23:18.390 --> 23:21.050]  Basically what it's saying is that it wants to meet popular people.
[23:21.550 --> 23:26.090]  It wants to interact with the more popular networks before it connects to just anybody.
[23:27.290 --> 23:29.030]  And this was the initial model.
[23:31.110 --> 23:32.850]  And there were some problems with it.
[23:33.030 --> 23:36.430]  And they weren't able to fully simulate it and get the same results.
[23:37.350 --> 23:39.770]  And so, again, it's often some debate.
[23:40.450 --> 23:44.570]  My opinion of it was that the Internet would go through different phases of growth over time.
[23:44.570 --> 23:48.390]  And the reason is because of economic reasons.
[23:49.190 --> 23:53.050]  That is, the initial growth of the Internet was having government-sponsored.
[23:53.670 --> 23:56.710]  People would just do connections to whoever.
[23:56.990 --> 24:01.390]  But as time went on, they would try to do the cheapest service provider.
[24:01.710 --> 24:06.570]  The cheapest service provider would be one who is able to provide the most connections already.
[24:07.270 --> 24:09.610]  Because, you know, economies of scale.
[24:12.490 --> 24:15.130]  And it's actually pretty fascinating.
[24:16.270 --> 24:18.030]  They're just starting to answer the questions.
[24:18.790 --> 24:20.290]  What does this really imply?
[24:21.710 --> 24:30.510]  We have a network that the vast majority of connections lay in very few people's hands.
[24:33.030 --> 24:42.430]  For example, I think the most connective node, or the most highly connected autonomous system on the Internet is UUNet.
[24:43.830 --> 24:45.950]  I believe it has an out degree of around 1,000.
[24:46.770 --> 24:53.370]  What this means is that if UUNet were to drop all its BGP routes, there would be a big problem.
[24:54.470 --> 24:57.170]  To be, you know, frank about it.
[24:59.610 --> 25:12.290]  Also, additionally, at the core of the Internet, there is at one point, maybe two years ago, about 20 of these top, top, top tier, you know, highly connected autonomous systems.
[25:13.530 --> 25:16.390]  As of now, seven of them have gone out of business.
[25:18.430 --> 25:24.230]  And we're still seeing, you know, for economic reasons, we're still seeing, you know, mergers and acquisitions in this area.
[25:25.810 --> 25:27.310]  So, what does this mean?
[25:29.870 --> 25:35.770]  And this is the, like, it'll be some of the more scary, interesting parts.
[25:38.270 --> 25:46.070]  We have controllable bandwidth that's able to be analyzed, or measured, you know.
[25:57.990 --> 25:59.190]  It's becoming high centralized.
[26:00.410 --> 26:04.610]  Have you guys ever heard of 80-20 rules with web traffic?
[26:04.910 --> 26:08.690]  20% of your users are responsible for 80% of your traffic.
[26:08.930 --> 26:09.810]  Same kind of thing.
[26:11.170 --> 26:16.990]  We're in a situation where 1% of the ISPs are responsible for 99% of the traffic, routing of the traffic.
[26:19.590 --> 26:24.730]  And since this is H2K2, I'm sure there's a lot of, you know, libertarian-minded people.
[26:25.710 --> 26:26.530]  What does this mean?
[26:27.010 --> 26:27.730]  We have...
[26:48.150 --> 26:51.210]  We have very highly centralized points of failure in monitoring.
[26:52.510 --> 26:55.250]  Again, I mentioned that UUNet goes down the entire Internet.
[26:56.110 --> 27:03.630]  Well, probably the American half of it probably will cease to function because of BGP rerouting and route flaps.
[27:05.110 --> 27:11.470]  Additionally, if you want to monitor 80% or 90% of the traffic on the Internet, all you can do is drop a couple of boxes and a few ISPs.
[27:12.970 --> 27:13.930]  Which is...
[27:13.930 --> 27:16.990]  I mean, there have got to be really powerful machines to be able to parse all the traffic.
[27:17.150 --> 27:17.730]  Yeah, that's fine.
[27:18.250 --> 27:23.290]  But this is not a difficult task for some of the large economic means.
[27:24.430 --> 27:27.210]  We know certain organizations that have such means.
[27:32.590 --> 27:34.250]  So, let's see, what else?
[27:35.630 --> 27:37.630]  Are there any questions as of this point?
[27:39.030 --> 27:41.530]  I want people to raise their hands and interject at any point.
[27:41.530 --> 27:47.630]  What do you think is the problem structure on the more abstract level?
[27:47.910 --> 27:48.970]  More abstract level.
[27:49.350 --> 27:49.530]  All right.
[27:50.830 --> 27:51.950]  Let's see a good example.
[27:52.430 --> 27:55.350]  Abstract or a good example of nature?
[27:56.570 --> 27:57.210]  Nature.
[27:57.330 --> 27:57.730]  Nature.
[27:57.730 --> 27:57.770]  Nature.
[28:06.620 --> 28:07.580]  You have a fern.
[28:12.640 --> 28:14.300]  You know what fern tree is, right?
[28:15.060 --> 28:15.340]  All right.
[28:15.820 --> 28:18.560]  You have a main branch, which stems out.
[28:18.760 --> 28:22.000]  And on the opposite sides, you have diminishingly smaller sub-branches.
[28:22.360 --> 28:25.720]  If you take one of those leaves, you get the exact same structure.
[28:26.560 --> 28:28.600]  It's diminishing these smaller leaves.
[28:30.480 --> 28:33.760]  And if you over each individual leaf, you kind of see the same structure in the veins.
[28:34.680 --> 28:37.100]  This is a perfect example of power-loss scaling.
[28:37.300 --> 28:40.600]  And actually, it's kind of interesting because the fern is one of the more primitive plants that we...
[28:41.220 --> 28:43.060]  Like one of the...
[28:43.060 --> 28:45.540]  And my biology is really bad anymore.
[28:46.000 --> 28:47.800]  But it's like, you know, one of the first...
[28:47.800 --> 28:50.420]  One that's supposed to be one of the most ancient species.
[28:51.360 --> 28:53.660]  And it obeys a power-loss structure.
[28:54.020 --> 28:56.740]  Which means that power-loss is probably very easy to genetic code.
[28:56.740 --> 28:59.000]  And very natural to the world.
[29:11.970 --> 29:13.510]  It's another term.
[29:14.250 --> 29:15.410]  Self-similar, fractal.
[29:16.110 --> 29:17.210]  Scalic variance.
[29:17.230 --> 29:18.110]  Scalic variance.
[29:18.610 --> 29:19.650]  These are all...
[29:19.650 --> 29:24.850]  And the reason why each of these terms come up is because people discover these things in different ways.
[29:25.170 --> 29:27.350]  And then they begin to realize they're all related.
[29:28.250 --> 29:29.690]  One of the first...
[29:29.690 --> 29:31.590]  For example, you see...
[29:33.050 --> 29:35.010]  You see the term long-term dependence.
[29:35.170 --> 29:37.830]  Or long-range dependence in one-dimensional fractals.
[29:38.770 --> 29:41.770]  One-dimensional fractals would be rain patterns.
[29:42.350 --> 29:46.890]  You get one heavy rain every 12 weeks.
[29:47.270 --> 29:50.130]  You get a week of heavy rain every 12 months.
[29:50.130 --> 29:55.590]  You get 12 days of heavy rain every 12 months.
[29:55.870 --> 29:58.130]  You get one year of heavy rain every 12 years.
[29:58.370 --> 30:00.930]  You get 12 years of heavy rain every 144 years.
[30:01.410 --> 30:06.370]  And this actually has been shown through statistical analysis by a guy by the name of Hurst.
[30:06.390 --> 30:08.410]  When he was trying to design a reservoir in Egypt.
[30:08.730 --> 30:10.730]  He wanted to see how big the reservoir should be.
[30:10.830 --> 30:13.090]  He wanted to look at past rainfall patterns.
[30:13.090 --> 30:14.290]  And he found the structure.
[30:15.510 --> 30:16.690]  And I'll get to it later.
[30:16.770 --> 30:18.630]  But you actually see the same exact structure in Ethernet traffic.
[30:20.570 --> 30:21.330]  You actually see...
[30:21.330 --> 30:23.590]  And it has a lot of applications for router design.
[30:24.130 --> 30:24.230]  Yes?
[30:24.410 --> 30:26.450]  You said control of BW.
[30:26.690 --> 30:27.810]  What does that stand for?
[30:28.530 --> 30:29.010]  Bandwidth.
[30:33.270 --> 30:35.350]  A quick question as far as...
[30:35.350 --> 30:36.890]  You were talking about say...
[30:36.890 --> 30:37.930]  Do you network disappear?
[30:38.230 --> 30:40.870]  How would disrupt traffic on the Internet?
[30:41.670 --> 30:43.330]  BGP is decision-making protocol.
[30:44.370 --> 30:46.110]  So wouldn't that be a temporary gap?
[30:46.930 --> 30:51.310]  How long the rest of the network's reallocated the routing?
[30:51.450 --> 30:52.690]  I don't know how much bandwidth there is.
[30:52.750 --> 30:54.430]  There's enough to complete reprovision.
[30:54.650 --> 30:56.450]  Supposedly there's a glut of bandwidth in the court.
[30:56.450 --> 30:59.950]  And from the research I've seen recently, yeah, there's heavy blood.
[31:00.410 --> 31:01.470]  So you should be able to reroute.
[31:01.730 --> 31:02.710]  Right, that's what you're going to do.
[31:02.870 --> 31:05.070]  Because you're going to get some overhead from the rerouting.
[31:05.290 --> 31:07.070]  And of course, there will be dashed out in that process.
[31:07.290 --> 31:08.850]  But that's a temporary disruption.
[31:09.090 --> 31:11.990]  The problem is, how strict are the policies that people have in place?
[31:12.450 --> 31:13.070]  That's right.
[31:13.570 --> 31:14.490]  And every...
[31:14.490 --> 31:15.550]  Like UNIT...
[31:15.550 --> 31:16.890]  Okay, let's say the situation happens.
[31:16.990 --> 31:17.750]  UNIT drops routes.
[31:18.590 --> 31:18.770]  Okay?
[31:18.950 --> 31:19.610]  People panic.
[31:19.950 --> 31:21.230]  They're trying to pull up new sites.
[31:21.530 --> 31:22.430]  And try to generate a lot of traffic.
[31:22.550 --> 31:23.010]  Try to reroute.
[31:23.770 --> 31:25.790]  Each of these organizations...
[31:26.430 --> 31:28.110]  Have to go and try to communicate with each other.
[31:28.250 --> 31:30.410]  To try to figure out how to redo policy.
[31:31.690 --> 31:32.010]  To...
[31:32.010 --> 31:33.270]  So that it would be more flexible.
[31:33.850 --> 31:36.070]  And normally they don't communicate with each other for having created the policy.
[31:36.230 --> 31:38.430]  So one person may say, oh, I'm just going to reroute through this person.
[31:38.810 --> 31:41.310]  The neighbor says, I actually refuse to carry traffic.
[31:44.230 --> 31:45.730]  And it's actually kind of interesting.
[31:45.890 --> 31:50.330]  Right now, there's a lot of push saying that, you know, we've got to fix BGP.
[31:50.570 --> 31:54.330]  And the reason why is because the current state of BGP is that it's a hand massage protocol.
[31:54.950 --> 31:59.430]  The only reason why the Internet works is because a handful of people around the world who know BGP really well...
[32:01.990 --> 32:02.690]  If you know it.
[32:04.030 --> 32:04.530]  Hey, Jason.
[32:04.650 --> 32:05.030]  What's going on?
[32:05.130 --> 32:05.770]  You going to show up my talk?
[32:11.080 --> 32:12.400]  I'm upstairs talking right now.
[32:14.400 --> 32:15.000]  Hi, Jason.
[32:17.040 --> 32:18.240]  Yeah, it would be a bad time to call me.
[32:20.840 --> 32:21.220]  All right.
[32:21.280 --> 32:21.620]  Take care.
[32:31.840 --> 32:34.020]  How long will it take for the Internet to come back up?
[32:34.180 --> 32:34.660]  Good question.
[32:35.340 --> 32:51.920]  If someone wanted to go and take advantage of the opportunity to do something else, like, I think it's really bad.
[32:53.660 --> 32:56.920]  And I just want to comment on something, how fragile BGP is.
[32:57.460 --> 33:02.240]  Only a handful of people around the world continue to keep up and massage the tables and make sure the Internet doesn't break right now.
[33:02.360 --> 33:04.700]  Just through experience, not through scientific research.
[33:05.100 --> 33:05.740]  It's through gut feel.
[33:06.520 --> 33:08.560]  And occasionally when people make mistakes, networks break.
[33:09.120 --> 33:10.980]  And it happens actually on a regular basis.
[33:11.760 --> 33:18.080]  A couple years ago, someone announced a BGP route that directed traffic, or announced a subnet that contained all of AT&T's name servers.
[33:18.080 --> 33:23.860]  So not only did it route a chunk of traffic over the Internet, right into the name servers, AT&T was down, so they couldn't figure out what was happening.
[33:25.580 --> 33:27.640]  This is all sorts of bad.
[33:28.060 --> 33:28.180]  Yes?
[33:30.480 --> 33:35.060]  Basically, you're mentioning that it's very simple to break down the Internet.
[33:35.480 --> 33:37.300]  Why spoke in BGP traffic?
[33:37.720 --> 33:39.520]  I didn't say it's simple.
[33:39.920 --> 33:40.360]  Well...
[33:40.360 --> 33:41.960]  It's definitely non-trivial.
[33:42.140 --> 33:43.040]  It's so trivial.
[33:43.040 --> 33:45.060]  However, two things I have to point out.
[33:45.220 --> 33:48.460]  First of all, BGP for the...
[33:49.540 --> 33:52.340]  As the SSL...
[33:52.960 --> 33:56.000]  In other words, a number of peers...
[33:58.300 --> 34:00.580]  It's not a matter of installing false routes.
[34:01.040 --> 34:04.060]  It's a matter of dropping packets in the TCP layer.
[34:04.060 --> 34:04.660]  Yeah?
[34:04.760 --> 34:05.280]  Well...
[34:05.280 --> 34:06.740]  In BGP...
[34:06.740 --> 34:09.000]  It's designed to handle that as well.
[34:09.220 --> 34:10.860]  It's probably the theory of BGP here.
[34:11.020 --> 34:14.580]  But you could introduce some penalties as each one of the blocks.
[34:14.800 --> 34:14.980]  Yes.
[34:15.200 --> 34:15.780]  After about three.
[34:16.380 --> 34:16.680]  You're...
[34:16.680 --> 34:17.300]  I don't know...
[34:17.300 --> 34:24.460]  If you do a BP or E-flat two times in a particular period of time, I just drop you around and ignore you...
[34:24.460 --> 34:24.960]  Exactly.
[34:25.360 --> 34:26.420]  That's the problem.
[34:27.060 --> 34:31.060]  But as far as I can see, that's perfectly correct for a number of...
[34:31.060 --> 34:31.380]  All right.
[34:31.740 --> 34:32.060]  So...
[34:32.060 --> 34:33.300]  So we have ten nodes.
[34:33.500 --> 34:35.100]  Each of them doing BGP between each other.
[34:35.580 --> 34:37.480]  Actually, a core of the Internet is about 20 nodes.
[34:37.700 --> 34:38.200]  And they form...
[34:38.200 --> 34:40.340]  They're about three of us to 20 edges short of a clique.
[34:40.600 --> 34:41.960]  Meaning they completely pure up each other.
[34:42.140 --> 34:42.400]  Yeah.
[34:42.920 --> 34:43.800]  All right.
[34:44.260 --> 34:44.700]  So...
[34:44.700 --> 34:48.320]  We take these 20 nodes and start dropping packets in each of their sessions.
[34:48.520 --> 34:49.300]  In each of their windows.
[34:49.780 --> 34:50.360]  What happens?
[34:50.720 --> 34:51.700]  They start...
[34:53.360 --> 34:54.660]  I didn't say it's impossible.
[34:54.820 --> 34:55.300]  I said it's difficult.
[34:55.740 --> 34:56.460]  Nothing's impossible.
[34:57.000 --> 34:57.440]  Well...
[34:57.440 --> 34:57.660]  Okay.
[34:57.660 --> 35:00.000]  But what happens is that...
[35:00.000 --> 35:01.980]  As the gentleman pointed out...
[35:01.980 --> 35:02.560]  I'm sorry.
[35:02.620 --> 35:03.000]  What was her name?
[35:03.840 --> 35:04.220]  Standing.
[35:04.360 --> 35:05.040]  What was it?
[35:06.440 --> 35:06.880]  Standing?
[35:07.320 --> 35:07.860]  All right.
[35:08.180 --> 35:16.400]  As standing pointed out, as two routers are talking to each other and they begin to flap, they'll start dropping routes between each other.
[35:16.800 --> 35:17.760]  That's the problem.
[35:17.960 --> 35:19.880]  You try to instantiate those flaps.
[35:21.420 --> 35:22.480]  That's the entire idea.
[35:22.760 --> 35:25.120]  If you just give them the flap, you're not trying to get them to insert routes.
[35:25.120 --> 35:26.480]  You just get them to flap between each other.
[35:26.720 --> 35:28.520]  And they stop trusting each other.
[35:29.060 --> 35:33.740]  If you do that across enough of the nodes that are forming a clique, then you break all the traffic rules.
[35:33.980 --> 35:35.900]  And they start dropping rounds between each other.
[35:36.140 --> 35:36.840]  It's difficult.
[35:37.160 --> 35:39.740]  I didn't say it was easy.
[35:40.400 --> 35:41.400]  I didn't say it was non-trivial.
[35:41.640 --> 35:42.800]  But I did say it was possible.
[35:44.940 --> 35:45.760]  Any other questions?
[35:48.020 --> 35:49.600]  Alright, so scale-free parameters.
[35:50.860 --> 35:53.040]  Let's see what's next, what other people want to talk about.
[35:53.540 --> 35:54.280]  What's time available?
[35:55.440 --> 35:55.740]  Alright.
[35:58.300 --> 35:58.780]  Ethernet traffic.
[35:59.780 --> 36:00.340]  Ethernet traffic.
[36:00.540 --> 36:02.840]  I want to get to that, but I want to also get to the solutions for this.
[36:03.260 --> 36:04.620]  I pose a challenge to you.
[36:04.720 --> 36:09.420]  Since I do not have time to do something like this, I definitely do not have the, I probably don't have the skill to write it.
[36:09.560 --> 36:10.600]  I'm not a great coder.
[36:12.060 --> 36:14.920]  I write, for lack of a better term, hacker code.
[36:15.440 --> 36:17.340]  You know, a couple hundred lines, it barely works.
[36:17.880 --> 36:19.140]  And it pretty much works for me.
[36:20.900 --> 36:24.120]  And I find that if I come into it a few months later, it doesn't work either.
[36:26.980 --> 36:27.940]  This is the challenge.
[36:28.960 --> 36:29.660]  Step one.
[36:30.860 --> 36:32.440]  How many people got 802.11 equipment?
[36:32.740 --> 36:33.200]  Pretty common?
[36:33.520 --> 36:34.140]  A lot of people?
[36:34.380 --> 36:34.500]  Alright.
[36:35.960 --> 36:45.160]  Current 802.11 architecture works is that you have an infrastructure mode, and you come into a network, you open up your laptop, and your, you know, your card negotiates the access point.
[36:45.620 --> 36:46.060]  You're good.
[36:46.440 --> 36:48.120]  There's another mode called peer-to-peer mode.
[36:48.560 --> 36:50.680]  In peer-to-peer mode, everyone has to be in the same range of each other.
[36:50.900 --> 36:53.040]  They do a broadcast and they all listen.
[36:53.460 --> 36:53.580]  Okay.
[36:54.400 --> 37:02.260]  Researchers have come up with things called wireless ad hoc routing protocols, which are now starting, kind of being touched on by industry, not yet.
[37:02.260 --> 37:04.520]  This is a good way for the hackers to get a jump on them.
[37:05.000 --> 37:05.080]  Okay.
[37:05.720 --> 37:07.280]  There are a couple of other protocols out there.
[37:07.420 --> 37:10.840]  They've been approved by IETF, and they've been, you know, pretty well described.
[37:11.300 --> 37:16.600]  There isn't a very good, well-written support for these in multiple operating systems.
[37:17.180 --> 37:19.380]  One, for example, is called a fisheye routing protocol.
[37:19.680 --> 37:21.400]  Another one is called ad hoc on demand.
[37:21.960 --> 37:27.160]  Another one is called a DSR, dynamic source routing.
[37:29.300 --> 37:35.000]  Anyway, step one, implement these routing protocols in every operating system.
[37:36.260 --> 37:36.780]  Okay.
[37:37.580 --> 37:41.700]  Step two, people are familiar with peer-to-peer.
[37:42.000 --> 37:44.640]  It's been, it's a, it's a term bandied about.
[37:45.000 --> 37:45.740]  It's been beaten to death.
[37:46.300 --> 37:48.700]  But I think Freenet is a beautiful thing.
[37:49.480 --> 37:51.320]  And let's take Freenet for example.
[37:51.980 --> 38:00.520]  The way Freenet connects to its initial hosts, as it goes onto the main core Internet, pulls down a list of IP addresses for its first local peers.
[38:01.520 --> 38:06.520]  Grabs that list and use that locally, and then connects to those guys and find out who else to connect to.
[38:06.980 --> 38:13.560]  So you have a core vulnerability as that is going to the network, into the mainstream network over IP, and grab that list.
[38:14.340 --> 38:22.600]  Step two, on a wireless ad hoc network, grab the list of the first people to connect to in a peer-to-peer system from the local routing table.
[38:25.830 --> 38:33.490]  Step three, implement some useful applications on top of Freenet, or build an actual API layer for peer-to-peer systems.
[38:35.070 --> 38:41.910]  There were, there was an effort I know one time to do like, email and news services and stuff like that on top of Freenet.
[38:42.550 --> 38:45.530]  Find out what these people are doing, help along their way.
[38:46.250 --> 38:54.570]  End result, you can have several thousand people open up a laptop, and jack in and be on this one network instantly.
[38:54.910 --> 39:01.610]  Completely cut off from the main network, and become fully functional, fully autonomous, and work on its own.
[39:02.350 --> 39:06.770]  Without having to go onto the core Internet, and pull down a list of IPs for the peer-to-peer system.
[39:07.390 --> 39:09.610]  Without having to use corporate bandwidth.
[39:10.150 --> 39:21.910]  And, the reason why I bring this up, is because the structure of a wireless graph, a wireless topology, is going to be pretty much by its nature, a Waxman graph.
[39:22.270 --> 39:25.230]  Which means that there are no nodes of very high connectivity.
[39:26.010 --> 39:30.750]  Sure, there's an argument that can be made, that someone will go and put up an antenna with very high power, and be able to listen to a lot of crap.
[39:31.410 --> 39:35.310]  But, everyone can just, building the protocol, you throttle back on your power a little bit.
[39:35.910 --> 39:39.130]  Where you don't receive certain signal strings, or something along those lines.
[39:40.190 --> 39:46.170]  The end result is a network that's fully autonomous, fully usable, and fully capable of communication.
[39:46.170 --> 39:50.450]  That has no one single point of being sniffed, or being analyzed.
[39:50.830 --> 39:52.090]  Unlike the main public Internet.
[39:53.010 --> 39:56.190]  So, again, since I don't have the time to do something like this, back yourself out.
[39:56.890 --> 39:59.750]  That doesn't necessarily have guarantees of connection either.
[40:00.530 --> 40:01.890]  Nothing has guarantees of a connection.
[40:02.230 --> 40:02.430]  Right.
[40:03.050 --> 40:06.770]  What connection guarantee do you get from your ISP, that your packet will wrap?
[40:07.750 --> 40:14.290]  Well, except that they have an interest, which is that they get paid only if you have connectivity for a while.
[40:15.830 --> 40:16.530]  That's true.
[40:16.750 --> 40:18.690]  So, how can you solve that in a peer-to-peer system?
[40:20.750 --> 40:22.450]  You don't, you don't route the packets.
[40:22.690 --> 40:26.490]  You could not, you could have a distributed network where you won't route the packets of people who don't route you.
[40:27.210 --> 40:48.430]  And it's actually, this has been worked out in a game theoretic constant, called a Vickery pricing, where you, across a network flow, you promise ISPs, the theoretical concept is you promise ISPs a certain cost to the routing, plus a certain percentage.
[40:48.890 --> 40:56.530]  And by that very nature, from a non-cooperative game standpoint, they'll obey the rules of the routing.
[40:56.870 --> 41:04.790]  I'm not saying you're actually using monetary units, but it could be something along the lines of you trade credits for storage space, or for bandwidth, or something along the lines.
[41:04.970 --> 41:07.610]  Kind of like file points, if anyone uses PBS.
[41:09.990 --> 41:14.290]  As with any other peer-to-peer networks, that doesn't scale very well, how do you deal with that?
[41:14.790 --> 41:18.150]  How does it, well, what do you mean it doesn't, what's the problem that it doesn't scale?
[41:18.750 --> 41:25.930]  Well, in a large enough environment, your routing for any one vector in there is just going to get extremely huge.
[41:26.150 --> 41:26.370]  Okay.
[41:26.370 --> 41:29.190]  So each node is going to have to be able to deal with that.
[41:29.210 --> 41:33.230]  In fisheye routing protocols, you don't, for example, there's one of them.
[41:33.810 --> 41:37.870]  The idea is that your local nodes have to know exactly where you are.
[41:38.650 --> 41:41.530]  The next level further out needs to have a rough idea of where you are.
[41:41.690 --> 41:44.770]  At the very opposite end of the network, all you have to know is that you're out there.
[41:45.530 --> 41:48.170]  And so you don't maintain perfect routing tables.
[41:48.550 --> 41:49.870]  You maintain pretty rough.
[41:50.050 --> 41:51.270]  You know exactly where your neighbors are.
[41:51.270 --> 41:58.130]  And the reason why I call it fisheye routing is because it's clearly a fisheye, a fish's eye has very perfect vision, very clear end.
[41:58.270 --> 42:02.570]  It's kind of cloudy, a little bit more out of focus when you get further out, and it's very bad further out.
[42:05.010 --> 42:09.450]  Now there are algorithms, one's called CAN, the other one's called CORD.
[42:09.450 --> 42:13.030]  the CAN stand for Content Addressable Network.
[42:13.230 --> 42:16.530]  It was presented at SIGCOM of 2001.
[42:17.850 --> 42:19.170]  This is an ACM conference.
[42:19.350 --> 42:22.850]  You should be able to pull it down from the web.
[42:23.630 --> 42:33.570]  Basically, it's peer-to-peer protocols that emulate hypercube mesh routing in a supercomputer across a peer-to-peer system.
[42:33.950 --> 42:38.350]  Basically, what it does is it takes to compute the hash, it resorts all the data across the network.
[42:38.590 --> 42:50.190]  So as you try to search for that piece of data, it looks at the hamming distance between the hash of the data you're looking for and the hash of the data on the local computer, and the routes further along.
[42:50.710 --> 42:54.170]  And it will trace a link right down to where your data is.
[42:54.390 --> 42:57.430]  That's a good way of doing searching across the peer-to-peer system.
[42:57.930 --> 43:01.030]  These are all somewhat open problems, but none of them are unsolvable.
[43:03.510 --> 43:04.550]  Any questions?
[43:06.810 --> 43:07.870]  Ethernet traffic.
[43:08.190 --> 43:15.450]  Since that's pretty much going to be our last topic, and then we'll discuss that.
[43:16.470 --> 43:24.630]  Anyway, Ethernet traffic, a traditional way of doing modeling of traffic across networks is what's called Poisson modeling.
[43:25.110 --> 43:32.970]  Basically, it says no matter what happened in the past, the probability of a packet coming in the next n seconds is m, for example.
[43:33.450 --> 43:39.790]  So let's say you're standing in line at the bank, and there's 30 people ahead of you, and you expect one person in a minute to show up.
[43:41.810 --> 43:43.850]  So how many people in the next minute are going to show up?
[43:44.850 --> 43:45.770]  One, right?
[43:47.250 --> 43:48.590]  For example, one person in a minute.
[43:48.770 --> 43:53.170]  Let's say you're in the bank, and all of a sudden a thousand people show up in like one gigantic burst.
[43:53.770 --> 43:56.770]  What's the probability that another person is going to show up after that in the next minute?
[43:57.630 --> 43:58.250]  One minute.
[43:58.490 --> 43:59.690]  I mean, it's a constant probability.
[44:00.430 --> 44:19.350]  The problem is, though, people use these models and design, you know, router buffers based upon it, and design, you know, link capacity measurements, and everything based off this one assessment that network traffic is going to be, you know, exactly non-burst-y,
[44:19.810 --> 44:23.690]  non-very predictable, very smooth across all scales.
[44:24.190 --> 44:29.390]  And so if you were to say, you know, you do a traffic sample, you would see something like this.
[44:30.670 --> 44:37.950]  And if you look at over, you know, this is over, I don't know, 500 milliseconds or something like that.
[44:37.950 --> 44:43.630]  And if you look at five, you know, you look at five seconds.
[44:45.590 --> 44:46.610]  What the hell is that?
[44:47.590 --> 44:50.230]  If you look at five seconds, you should see it a little bit smoother.
[44:56.240 --> 45:01.040]  And if you look at a larger timescale again, you should see it smoother and smoother.
[45:01.340 --> 45:02.620]  This is definitely not the case.
[45:02.900 --> 45:03.700]  The reason why?
[45:03.800 --> 45:05.000]  Traffic is bursting in nature.
[45:05.700 --> 45:12.960]  The initial assessment is because multimedia traffic by its very nature is fractal, very self-similar after compression.
[45:13.780 --> 45:15.120]  There are some assessments now.
[45:15.280 --> 45:16.080]  The paper came out.
[45:16.880 --> 45:18.980]  People blasted it, but I thought it was very much true.
[45:19.460 --> 45:24.980]  They said TCP by its very nature causes traffic to be self-similar because of the way it does congestion control.
[45:25.200 --> 45:27.440]  If you have a block, you throttle.
[45:27.700 --> 45:32.740]  Then once a bunch of acts come in, you do a fast acknowledgement and start blasting traffic again.
[45:32.980 --> 45:34.700]  So your local buffers are starting to fill up.
[45:34.700 --> 45:36.640]  And so that causes a burst of missing nature.
[45:37.200 --> 45:41.240]  And so this paper was published in 94 by Sally Floyd.
[45:41.740 --> 45:44.180]  And I want to say Sally Floyd and Vern Paxson.
[45:46.660 --> 45:51.300]  I think it's something along the lines of Long Range Dependence in Ethernet Traffic.
[45:52.160 --> 45:53.300]  I think that's the name of it.
[45:54.200 --> 46:01.200]  Anyway, so this is another example of, you know, someone sitting down reassessing, you know, the structure of traffic.
[46:01.400 --> 46:04.040]  And just the same way they reassess the structure of the Internet.
[46:04.040 --> 46:08.080]  And it completely changed, you know, how people do modeling.
[46:08.680 --> 46:09.580]  One last thought.
[46:09.800 --> 46:10.440]  Very interesting point.
[46:12.260 --> 46:14.340]  Do we have a lot of router network administrators here?
[46:15.740 --> 46:19.000]  Okay, when you get an iOS update comes out, do you apply it immediately?
[46:21.140 --> 46:22.120]  No, I'm just curious.
[46:22.120 --> 46:22.700]  No.
[46:22.900 --> 46:23.200]  No?
[46:23.740 --> 46:24.160]  Okay.
[46:24.580 --> 46:30.140]  There is a direct correlation between major BGP route flaps and iOS updates.
[46:31.540 --> 46:34.380]  And the reason why is an iOS update comes out.
[46:34.460 --> 46:41.100]  The next two weeks people are pulling down core routers and not doing it in a very soft manner, and the route starts flapping.
[46:42.600 --> 47:00.740]  What this means is that if someone were so inclined, or someone really was interested in doing it, after an iOS update would come out, it would be an optimal time to launch a large-scale attack on a network.
[47:00.880 --> 47:01.540]  And this is not good.
[47:03.380 --> 47:13.080]  So for those network administrators out there who are doing this kind of work, the love of God, put up backup routers and don't let your route flap those easily.
[47:13.360 --> 47:19.040]  If you have to pull down a core router, please do some backup implementation.
[47:19.360 --> 47:20.840]  It's like switches.
[47:21.120 --> 47:25.080]  For us electrical engineers, it's make before break, not break before make.
[47:25.860 --> 47:29.380]  You actually make sure you have that provision before you actually toggle it over.
[47:30.700 --> 47:33.640]  So, is there any questions or comments?
[47:34.120 --> 47:34.980]  Dumb looks?
[47:46.820 --> 47:48.200]  A time assistant, yes.
[47:53.610 --> 47:54.190]  Yes.
[47:55.070 --> 47:55.190]  Yes.
[47:57.740 --> 48:02.520]  Do you have any thoughts about in case you talked about the UUNet work system?
[48:04.860 --> 48:06.560]  Well, let's put it this way.
[48:08.280 --> 48:09.810]  What exactly is UUNet?
[48:10.460 --> 48:15.460]  It's a collection of routers and buildings with electric bills and payrolls to make.
[48:16.320 --> 48:21.080]  If worse comes to worse, I think it would be deemed a national security issue if the UUNet would go down.
[48:21.400 --> 48:23.620]  I don't think... I really don't think that...
[48:23.620 --> 48:29.980]  I mean, it's a real possibility, but I don't think the government would really let that happen.
[48:30.520 --> 48:31.320]  I'll be honest with you.
[48:31.320 --> 48:33.740]  I mean, it seems like it would be...
[48:34.140 --> 48:36.580]  you know, and everyone's like, oh, well, the government's going to do this.
[48:36.660 --> 48:37.880]  But it's like, they're not...
[48:37.880 --> 48:39.220]  they're not bone stupid.
[48:40.000 --> 48:41.120]  I mean, they're not going to...
[48:41.120 --> 48:41.960]  I mean, it would...
[48:41.960 --> 48:42.860]  You would...
[48:42.860 --> 48:45.120]  Put it this way, the powers that they would see a major drop...
[48:45.120 --> 48:48.100]  you'd see a major drop in the stock market if the UUNet showed up their network.
[48:48.840 --> 48:51.300]  You would see trading stopped because all these people were doing day trading.
[48:53.080 --> 48:54.260]  So I don't think that would...
[48:56.040 --> 48:57.780]  you know, actually physically happen.
[48:58.300 --> 49:00.860]  They said the same thing in Europe about eBone.
[49:01.360 --> 49:01.400]  Yeah.
[49:01.400 --> 49:03.920]  If eBone would stop and the European Internet would die.
[49:04.200 --> 49:04.400]  No.
[49:04.480 --> 49:05.080]  Didn't happen.
[49:05.080 --> 49:05.840]  Yeah.
[49:06.040 --> 49:08.540]  I mean, and the EU is even...
[49:08.540 --> 49:11.640]  Could be, sorry, a different sound system.
[49:15.960 --> 49:20.760]  So, anyway, the EU is even weaker, politically, than the United States is.
[49:21.780 --> 49:24.060]  I mean, it tried to, like, keep up those things.
[49:24.160 --> 49:27.020]  And the EU is able to keep up that mission, that network for going down.
[49:28.000 --> 49:28.400]  Then...
[49:28.400 --> 49:29.700]  No, but they didn't.
[49:29.820 --> 49:30.480]  They didn't break.
[49:30.720 --> 49:30.980]  It did.
[49:31.180 --> 49:31.720]  I mean, exactly.
[49:32.120 --> 49:32.560]  And that...
[49:32.560 --> 49:33.620]  it didn't go.
[49:33.800 --> 49:34.600]  So it's...
[49:34.600 --> 49:35.580]  I mean, it's a perfect example.
[49:35.980 --> 49:43.460]  And I think that, again, it's, you know, with some of the silly things that our government does at times, I don't think they're gonna...
[49:43.460 --> 49:47.120]  they actually will permit that to happen, because it would be a major hit to our gross domestic product.
[49:50.730 --> 49:52.070]  I mean, it'd be bad for our economy.
[49:54.850 --> 49:56.570]  Yeah, that's scary.
[49:58.570 --> 50:09.730]  No, and actually, it's kind of funny, because Sprint says that they actually have the real possibility of their network being segmented, several times a week, just by fiber cuts and things like that.
[50:10.110 --> 50:11.330]  And so they quad over-provision.
[50:11.690 --> 50:14.830]  So they run about 25% utilization on any of the fiber lines.
[50:15.890 --> 50:18.410]  And that's how you actually do any kind of over-provisioning in a network.
[50:18.690 --> 50:25.370]  The problem is with the Internet, or with the road system, there actually is no over-provisioning, completely under-provisioned.
[50:25.370 --> 50:31.830]  So, when they said, when Al-Qaeda said that they're, you know, attack infrastructure, I was like, well, they'll shut things down.
[50:33.010 --> 50:35.070]  So, that's, I'm sorry, that's kind of dark.
[50:36.830 --> 50:37.730]  Any other questions?
[50:40.050 --> 50:46.390]  I think we're getting, there's about ten minutes left, and they told me to shut up about five minutes before, before the end.
[50:46.390 --> 50:49.230]  So, comments?
[50:51.250 --> 50:51.710]  All right.
[50:52.470 --> 50:52.970]  Oh yeah, go ahead.
[50:53.150 --> 50:53.630]  Hold on.
[50:53.690 --> 50:54.670]  Wait, wait, wait, wait, wait, wait, wait.
[50:56.090 --> 51:03.790]  I don't know, it's conventionally, complex routing routes, say, like a hundred hops, how does one person know?
[51:04.210 --> 51:05.910]  Like you said, it's gray out there.
[51:06.690 --> 51:07.650]  Oh, that's the point.
[51:07.770 --> 51:13.010]  With fisheye routing protocols, for wireless routing, you don't worry about a hundred route hops.
[51:13.210 --> 51:14.370]  All you worry about is the first hop.
[51:14.570 --> 51:16.710]  All you gotta worry is the general direction where your packet's gotta go.
[51:17.650 --> 51:20.990]  And when you get closer there, then the routing tables are gonna be more specific.
[51:21.550 --> 51:22.070]  So.
[51:24.870 --> 51:25.390]  Okay.
[51:25.610 --> 51:26.210]  Thank you very much.
[51:36.630 --> 51:37.150]  Yeah.
[51:37.650 --> 51:40.350]  And, and, I dedicated this talk...