Die Technologie, die die Welt veränderte - 50 Jahre Internet

1. 00:00Now we want to look at routing in wide area networks take another closer look.
2. 00:04When we introduced the wide area networks, we had already the basic principle.
3. 00:10But you have to look a little closer, i.e. networks in wide area networks are interconnected via routers.
4. 00:21These routers are responsible for the packet switches, can translate formats from one technology to another and can determine routes.
5. 00:31So for the incoming data packets can determine by analyzing the destination address, where should the packet be forwarded to.
6. 00:43The determination of this optimal path for such a data packet, from transmitter to receiver, that was the routing.
7. 00:52And, had already said at the introduction of the wide area networks, this routing is source independent.
8. 01:03So in a certain point for the forwarding of a data packet, for optimal forwarding, it is irrelevant to know on which way did this packet reach the router
9. 01:16This is the so-called optimality principle. Optimality principle says that the optimal route of a parcel depends solely on the destination, from the destination alone and not from its point of departure or the distance travelled so far.
10. 01:34This is a mathematical theorem, that's easy to prove.
11. 01:37Let's assume that this is the optimum route from A to B, and this optimal path from A to B runs via node C.
12. 01:54Now we're in C and we're wondering, what is the optimal way to B?
13. 02:02Let us assume that there is a shorter way from C to B than our section A, let's say B is shorter than part A.
14. 02:18Well, if there was such a way, then this way from A via C and via small a to B would not be the optimal one.
15. 02:29Because then this road that runs from A to C and then runs along B, shorter than the path that runs from A to B via small a.
16. 02:41So in this way is actually proven, The optimal route of a parcel depends solely on the destination and not on the point of departure.
17. 02:50The principle of source independence, that now makes this use of these next-hop algorithms possible and thus helps to find optimal paths in the network very quickly.
18. 03:06And that's what the routers have to do, because it's a big exchange of data packets, They remember everything they send over the Internet in a short time, what they receive over the Internet,
19. 03:16that is, it has to happen very quickly at these connection points of two networks, that it is clear how the data packet is forwarded so that it reaches its destination as quickly as possible.
20. 03:28To take a closer look at these routing algorithms, it is good, if one imagines this network group of this wide area network as a graph.
21. 03:41Namely, the nodes, i.e. the routers, are the connection points between two networks, and an edge represents a connection between two routers, which typically runs through such a connected network.
22. 03:57That means we abstract from the networks, this graph doesn't look at all anymore, which end systems are all in these individual networks connected in the wide area network.
23. 04:11Why? The calculation of an optimal path, that's what it is, to find the way from this router to the next router.
24. 04:22How it then runs over a concrete network, it's not that important.
25. 04:26And in the case where it is important, namely that the router is the target of the target computer, well, then the suffix, which evaluates the second part of the address
26. 04:37and then no longer worked with the routing mechanisms at all, but directly then the computer is selected.
27. 04:43That is, if we look at the example, that's what we saw earlier as networks with packet switches 1 to 4 and the respective connected networks,
28. 04:53then the graph, based on which then the routing paths are discussed, just this one.
29. 05:00You see at P1, I have omitted all connected computers, at P3, there are no more connected computers.
30. 05:06Why? In determining the route from such an end system to such an end system
31. 05:12the big question is, how can I get across this router connection to organize this extradition process?
32. 05:21So optimal routes, that is the result of such routing algorithms, and the crucial data structure, which we have already mentioned, these are the routing tables.
33. 05:35They need the individual routers to be able to look, what is the next hop on an optimal path to the goal.
34. 05:43This routing table is natural very specific to each packet switch.
35. 05:50In another packet switch there are other entries, because from the point of view of the other packet switch the network looks quite different.
36. 06:01The routing table gives - and only then the whole thing works - the next router for each destination, i.e. for each destination address of a data packet, to which this must be sent.
37. 06:19If you think of our graph, i.e. the edge to the adjacent router, on which our package is to be forwarded, and vividly they're talking about the next jump, the next hop.
38. 06:33Now there are requirements for these routing tables, the routing table must allow the router to do so, to really figure out any potential target as he needs to forward this.
39. 06:47So for each potential destination you need an entry in the routing table, so that universal routing is possible, i.e. really to every computer in the network.
40. 07:00And the second requirement is, that these routing tables do not have to specify just any output, over which the packet is sent,
41. 07:08but this output should be at an optimum, should lead to an optimal route.
42. 07:14Now the question is, of course, what does optimal mean? And indeed, this can be interpreted in many different ways.
43. 07:22So you could say it's a matter of the shortest route, that is, the least number of hops through which the packet is forwarded.
44. 07:30One could say because costs are incurred by these different networks, that you want to have the cheapest possible way to get the package to its destination.
45. 07:41One could discuss that it is a path where the paths are as wide as possible, so where a high data transfer rate is available and thus a fast transmission is possible.
46. 07:54So what optimal means, that has to be determined.
47. 07:57But if you have this metric, that is a metric, if you have established that metric, then these procedures can always lead the way.
48. 08:07Let's take a look at it again, again, in a mathematical way, because that's graph theory, that's right there, not some kind of heuristic, but they are procedures that function very precisely.
49. 08:20The underlying theorem says, if you can find optimal routes from all possible nodes, that is, from all possible routers in a wide area network
50. 08:35to a destination router Z, then a tree emerges.
51. 08:40So A1 to An should be our individual routers in this network, and the task is to send a packet in the network of the destination router Z.
52. 08:56This so-called Sink Tree, that's the scaffolding, on which these optimal routes can then be determined.
53. 09:07We will discuss this in more detail in a digression, here only the understanding that this sink tree has ways is important, has optimal paths to the destination packet switch Z.
54. 09:24These paths in such trees, tree means tree, there's no bows.
55. 09:31Loops are always a problem, that there are suddenly paths, if I run the loop over and over again, can become as long as I want.
56. 09:38That's why we need this tree, we have to use the shortest connection, let's stick to the optimality metric,
57. 09:46this way with the least possible distances, this shortest way, so there can't be any loops.
58. 09:54This is exactly the characteristic of these Sink Trees, the packets reach their destination after a finite number of steps.
59. 10:02The goal now of the various routing algorithms is to to build such a sink tree, to build such a sink tree for each participating router
60. 10:15and then know how to populate the routing table and how the data packets are then optimally sent.
61. 10:24Let's look at an example: This is a network, these are the different network routers.
62. 10:29This is already the abstract form, we left out all the end systems from the networks attached to these routers.
63. 10:35And the question is always, what is the shortest way or more precise, what is the shortest route to our destination computer Z.
64. 10:45And this is one of those sink trees, so from A4 the shortest way to Z is via A2, A1 to Z.
65. 10:54You could also go to Z via A5 and A3 and A1, but it wouldn't be the shortest route.
66. 11:01From A2 the shortest way is of course on the shortest way to A4.
67. 11:07And you see, so no matter what network a data packet comes from is to be sent to a computer in the network belonging to Z, along this route, which is the shortest way.
68. 11:20And if this sink tree is meant to be, then each of these routers can calculate its routing table.
69. 11:32Now there are completely different routing procedures, each with certain advantages and disadvantages.
70. 11:38You could say, yes, you put a powerful instance into the network, which calculates the routing tables for all participating routers, thus a central instance with a lot of computing power.
71. 11:52This is an approach known as central routing, which causes relatively long waiting times.
72. 11:59Why? Well, this centrally calculated routing table must then to their place with the respective packet switch.
73. 12:09If this central instance, since any error is, then it will be here, the failure or resource bottleneck, which then leads to the entire network operation being compromised.
74. 12:25We are talking about a single point of failure, by the way, this is always a point when operating large, digital systems,
75. 12:34if there's a single spot and something goes wrong at that spot, if then everything is affected, then this is often not a sensible approach.
76. 12:43On the other hand, and this is then what is used in practice, we have these decentralized routing algorithms.
77. 12:51Here, every router with these decentralized routing algorithms is able to to calculate its own routing table.
78. 13:00Yeah, how can he? He doesn't even know about the network.
79. 13:05The basic idea here is that he's interviewing the neighbors, what does the network look like from your point of view, and then they transmit their knowledge.
80. 13:16And of course they only know about their immediate neighbours, so you'll need to take further steps to calculate that.
81. 13:27This means that there is a relatively long adjustment process here, ...until that information is disseminated even from the furthest corners, what the situation is there.
82. 13:37This is a problem, but the decentralised approach also makes it easier to deal with changing network situations,
83. 13:49where, of course, a routing algorithm has to be activated again and again, to discuss these routing tables.
84. 13:58Here are times, here are times three procedures: Isolated routing, distance vector method, called link state routing, the Link-State-Routing, with the distance vector method it started in the internet.
85. 14:11Today the link state routing is used, which succeeds in accelerating this process of adaptation.
86. 14:19These routing algorithms, that goes into a little bit of detail.
87. 14:23The important thing is to understand, that such a router is needed at these interconnection points of two networks
88. 14:33and that this router, via its routing tables must be enabled to make decisions with the help of the routing algorithms,
89. 14:40what is the next output, what is the next hop for the data packet, what I have received and what I must forward.

To enable the transcript, please select a language in the video player settings menu.