WEBVTT 00:02.000 --> 00:03.010 So, good morning. 00:03.370 --> 00:06.750 Welcome to another session of Algorithms for Internet Applications. 00:07.450 --> 00:13.590 I was here in time today, but the data projector didn't work, so it 00:13.590 --> 00:15.570 took some time to actually get everything started. 00:15.750 --> 00:16.590 Now it should be okay. 00:18.450 --> 00:22.310 I hope that you can see sufficient things on the screen. 00:23.010 --> 00:28.350 Okay, I have to change something here... 00:28.350 --> 00:31.810 in order to be able to... yeah, this has to be changed. 00:34.390 --> 00:37.670 And then we are done. 00:39.690 --> 00:45.410 So, we have looked at internet technology for a few lectures now 00:45.410 --> 00:45.930 already. 00:46.310 --> 00:48.350 So, we've looked at quite a few things. 00:48.570 --> 00:54.010 I've told you something about routing protocols last time, about... 00:54.010 --> 00:56.450 after we had looked at Dijkstra, we had looked at flooding. 00:56.450 --> 01:01.470 I've shown you something on distance vector routing, which is one of 01:01.470 --> 01:08.430 the earliest routing algorithms in the internet. 01:09.290 --> 01:18.630 And as you have seen there, what we do is that we have this table, or 01:18.630 --> 01:22.010 these tables that are received from the direct neighbors, and then 01:22.010 --> 01:26.750 from the information from the tables, the best information is used. 01:27.150 --> 01:32.670 So, the tables are updated according to the distances to the direct 01:32.670 --> 01:36.510 neighbors, and then you always go for the shortest or for the best 01:36.510 --> 01:38.390 information that you see from your neighbors. 01:38.550 --> 01:44.950 And we had seen that this can lead to problems because bad news, like 01:44.950 --> 01:48.310 bad information, does not spread, is not adopted. 01:48.310 --> 01:50.390 Only the good information is adopted. 01:50.590 --> 01:55.870 And as long as the neighbors are assuming that there are better paths 01:55.870 --> 02:01.790 available, then you always go for those assumptions of your neighbors 02:01.790 --> 02:06.070 and don't consider the bad information that might be there also. 02:06.370 --> 02:09.130 And we had seen that at this simple example. 02:09.770 --> 02:13.210 You will have possibilities to look at that in the tutorials also. 02:13.210 --> 02:16.990 Then we looked at link state routing, where we have the different 02:16.990 --> 02:25.230 approach where we compute the link state packets, like the information 02:25.230 --> 02:27.510 that every node has about its direct neighbors. 02:28.070 --> 02:31.330 And this information is not exchanged only with the direct neighbors, 02:31.530 --> 02:35.090 but it's flooded to all the nodes in the system. 02:35.090 --> 02:42.470 And in that way you get information about all the connections in the 02:42.470 --> 02:44.450 graph that you are living in. 02:44.850 --> 02:47.850 And in that way you get a complete view of the system. 02:48.610 --> 02:57.670 And you can actually then get your local view, you have your adjacency 02:57.670 --> 03:01.410 matrix, the connectivity of the network, and you can compute shortest 03:01.410 --> 03:04.510 paths based on that local information that you have. 03:04.590 --> 03:11.190 Your local view is based on the measured costs of communicating 03:11.190 --> 03:13.250 between a node and the direct neighbors. 03:13.510 --> 03:17.110 And so this is much more accurate than what we had in the distance 03:17.110 --> 03:17.850 vector routing. 03:18.010 --> 03:21.490 And here the counter-infinity problem is no longer there. 03:21.650 --> 03:25.870 But the disadvantage is that you have quite a large overhead because 03:25.870 --> 03:28.890 of all these link state packets that have to be sent around. 03:29.110 --> 03:32.910 You always want to get the newest information, and so regularly you 03:32.910 --> 03:35.070 get updated information from all the nodes. 03:35.950 --> 03:38.370 Then we briefly looked at hierarchical routing. 03:38.570 --> 03:43.950 You want to reduce the size of your routing tables, and so you look at 03:43.950 --> 03:48.570 connectivity to networks and not to all the nodes inside those 03:48.570 --> 03:49.010 networks. 03:49.650 --> 03:52.430 And so that was what we looked at. 03:52.990 --> 03:58.070 And after that we looked at the problems that we have with IP, that 03:58.070 --> 04:03.350 there is a shortage of addresses, and there are a few more points that 04:03.350 --> 04:11.190 were not really satisfying or not satisfactory with the old protocols. 04:11.650 --> 04:16.850 So IP version 6 was introduced quite some time ago, like around 15 04:16.850 --> 04:18.670 years or so. 04:18.850 --> 04:23.970 But it took really some time before that actually got spreaded over 04:23.970 --> 04:25.450 the network. 04:25.450 --> 04:31.590 And I showed you the addressing format with 128-bit addresses, which 04:31.590 --> 04:35.410 is an abundance of addresses, and they are used in a reasonable way. 04:35.910 --> 04:38.590 There are all kinds of rules how to use those addresses. 04:38.990 --> 04:41.450 They are separated into different regions and so on. 04:42.690 --> 04:47.890 You should look that up in the protocols if you really have to use IP 04:47.890 --> 04:48.690 version 6. 04:49.090 --> 04:54.470 The important information is that there are certain rules how to use 04:54.470 --> 04:54.770 that. 04:54.770 --> 04:58.210 I have given you some examples so you know how to read those 04:58.210 --> 04:58.650 addresses. 04:59.090 --> 05:02.490 And if you need a specific information on an address, you always have 05:02.490 --> 05:04.350 to go into the protocols and look it up. 05:04.530 --> 05:07.990 But you know how they are actually built and what it means if you 05:07.990 --> 05:12.850 have, for example, some address and a slash and a number, it means 05:12.850 --> 05:16.050 that the relevant information is the prefix of that size. 05:17.670 --> 05:20.630 That was what we looked at for the addressing format. 05:20.630 --> 05:26.790 Then we looked at the header format, which is a fixed header of these 05:26.790 --> 05:30.050 20 bytes here. 05:30.410 --> 05:35.670 No, sorry, it's a 40-byte header. 05:36.330 --> 05:40.610 And it consists of a bit fewer information than we had before. 05:40.990 --> 05:46.270 In particular, the option field is missing here, but this is replaced 05:46.270 --> 05:51.210 with extension headers, which are following or potentially following 05:51.210 --> 05:53.670 this initial IP header. 05:54.470 --> 05:58.650 And the major part of that header certainly is the two addresses, 05:58.970 --> 06:00.650 source address and destination address. 06:01.210 --> 06:06.150 Then I told you something about the extension headers for different 06:06.150 --> 06:08.730 purposes, for routing, fragmentation, and so on. 06:09.110 --> 06:12.770 A particular point is that you can have something like loose routing 06:12.770 --> 06:17.990 implemented using, for example, the routing extension header, where 06:17.990 --> 06:22.550 you have a stack of addresses that you have to go to in sequence. 06:23.170 --> 06:28.590 And in the initial header, you always have the next router that you 06:28.590 --> 06:31.630 have to go to or the next destination that you have to go to. 06:31.890 --> 06:38.330 And then you can look for the next hop or the next further away 06:38.330 --> 06:43.930 destination in that routing header, which has to be indicated using 06:43.930 --> 06:47.410 this next header information, because there you have the information 06:47.410 --> 06:51.110 about which type of next header actually has to be looked at. 06:51.990 --> 06:58.990 And then while we talk a little bit about that, that has been delayed. 06:59.410 --> 07:00.910 And then I showed you something about TCP. 07:01.250 --> 07:03.010 We looked briefly at properties. 07:03.310 --> 07:06.810 I started to tell you something about the header format. 07:06.810 --> 07:09.550 And that was the last slide of the last lecture. 07:10.430 --> 07:14.790 So we have to... I should go into that again. 07:14.970 --> 07:18.550 That is the header format, the TCP header that we have. 07:18.910 --> 07:24.890 And there, essential information is about the ports that are 07:24.890 --> 07:25.290 connected. 07:25.490 --> 07:30.330 So you build up with TCP a logical connection between ports, or you 07:30.330 --> 07:37.450 should say between applications on the layer above TCP, which is 07:37.450 --> 07:43.470 actually or which are sending or the application above the TCP on the 07:43.470 --> 07:46.490 source side is sending data. 07:47.050 --> 07:49.610 And so it wants to communicate with another application on the 07:49.610 --> 07:50.530 destination side. 07:50.690 --> 07:55.990 And so you need the ports to be able to actually communicate using the 07:55.990 --> 07:57.010 appropriate services. 07:57.010 --> 08:02.910 And I told you that there are some special services like the well 08:02.910 --> 08:06.930 -known ports having numbers less than 1023. 08:08.050 --> 08:12.490 And so there's a list of all those services that we have. 08:12.610 --> 08:16.650 Then we have registered ports, which are for specific application 08:16.650 --> 08:18.450 programs registered. 08:18.450 --> 08:23.930 And after that, you have the freely available ports that you can use 08:23.930 --> 08:30.770 for socket programming, if you want to use additional ports for some 08:30.770 --> 08:31.750 additional applications. 08:32.030 --> 08:39.550 So there is this list of all the assignments of ports to services in 08:39.550 --> 08:40.450 that URL. 08:40.870 --> 08:43.990 Last time we briefly looked at that website. 08:45.650 --> 08:49.790 So that was why we need those ports. 08:50.550 --> 08:54.450 And then we have something again like a sequence number. 08:55.330 --> 09:01.990 And that's just telling again, well, we know that all bytes of a 09:01.990 --> 09:03.530 message are numbered. 09:03.530 --> 09:15.130 And here, what we have is the sequence or the number of the first data 09:15.130 --> 09:17.510 byte within this datagram. 09:17.890 --> 09:20.830 Now, why do we need this sequence number? 09:20.990 --> 09:25.870 I said that we only put in the information that is essential for the 09:25.870 --> 09:29.910 receiving side to actually adequately deal with the data payload. 09:30.370 --> 09:32.070 Why do they need the sequence number? 09:32.070 --> 09:36.970 You have this very long file that you want to send, and you have 09:36.970 --> 09:38.710 chopped that into segments. 09:39.270 --> 09:44.870 And now you certainly have to know when you receive a TCP packet, you 09:44.870 --> 09:49.570 have to know what is the location where I have to put that segment in 09:49.570 --> 09:53.410 order to reconstruct the old data. 09:54.270 --> 09:58.790 So you need the sequence numbers, the bytes are all numbered. 09:59.310 --> 10:06.410 And you always tell what is the first byte of this message, like the 10:06.410 --> 10:08.910 payload comes after that TCP header. 10:09.770 --> 10:14.910 And so you have to know what that byte actually is. 10:15.010 --> 10:17.350 Then you find the appropriate position. 10:18.890 --> 10:20.750 The next is an acknowledgment number. 10:20.750 --> 10:24.590 I said that TCP is responsible actually for reliability. 10:25.010 --> 10:30.070 That means TCP has to make sure that all the packets are adequately 10:30.070 --> 10:30.890 received. 10:31.330 --> 10:41.450 So the source node has to get information about successful receipt of 10:41.450 --> 10:43.370 datagrams that have been sent out. 10:43.370 --> 10:46.250 And for that we need the acknowledgment number. 10:46.370 --> 10:51.090 The acknowledgment number is put in by the destination side on receipt 10:51.090 --> 10:52.170 of a datagram. 10:52.850 --> 10:58.450 And so they have to put in, they have to acknowledge that they got 10:58.450 --> 10:59.470 certain bytes. 10:59.910 --> 11:03.270 And what they acknowledge is a number X plus one. 11:04.270 --> 11:08.450 And it acknowledges the correct receipt of all bytes up to number X. 11:08.450 --> 11:09.770 Or you could phrase it differently. 11:10.310 --> 11:14.170 What they put in there in the acknowledgment field is the first or the 11:14.170 --> 11:18.530 number of the first byte that they have not received so far. 11:20.310 --> 11:27.550 And now one problem is that the data packets might not be received in 11:27.550 --> 11:30.510 the same order as they are sent out. 11:31.190 --> 11:39.190 And so they will always only, like this X plus one I said, it 11:39.190 --> 11:43.070 acknowledges the correct receipt of all bytes up to number X. 11:43.670 --> 11:50.210 So if this part here has been received, then it will be the number of 11:50.210 --> 11:53.590 the next byte that is expected to be there. 11:53.590 --> 12:00.730 And even if further bytes have already been received, if there is some 12:00.730 --> 12:06.750 hole in there, some part that has not been received so far, the 12:06.750 --> 12:12.210 acknowledgment will only be for that part that has been completely 12:12.210 --> 12:12.830 received. 12:12.830 --> 12:19.190 So X plus one is always the address of the first, I could say, free 12:19.190 --> 12:25.370 spot or the first byte that did not arrive at the destination so far, 12:25.470 --> 12:29.630 regardless of what has been received, like what packets have been 12:29.630 --> 12:30.710 received after that. 12:30.710 --> 12:36.190 So only if this is also received, then the next byte that would be 12:36.190 --> 12:45.010 acknowledged or that would be sent is again the number of the next 12:45.010 --> 12:47.230 byte that has not been received so far. 12:47.550 --> 12:50.930 And then the other packet that had been received before is also 12:50.930 --> 12:51.350 acknowledged. 12:52.310 --> 12:58.370 So the acknowledgment number is the essential information that the 12:58.370 --> 13:01.750 source site needs in order to provide reliability. 13:03.230 --> 13:09.970 And if the source site notices, oh, this packet that I have sent out 13:09.970 --> 13:14.810 has not been received, after some time, they have to resend that. 13:14.810 --> 13:21.130 And they have to resend everything starting from that field where they 13:21.130 --> 13:22.990 did not get all the bytes. 13:23.510 --> 13:28.270 So they might even resend certain segments that had been sent before, 13:28.630 --> 13:31.710 which might have arrived already, but there's still one segment 13:31.710 --> 13:35.510 missing, and so everything from that position on has to be resend. 13:36.190 --> 13:40.070 That's the way TCP works. 13:41.070 --> 13:43.390 And now we have more fields there. 13:43.750 --> 13:47.710 So sequence number, acknowledgment number are essential to be able to 13:47.710 --> 13:50.370 actually provide reliability of communication. 13:50.530 --> 13:52.550 Without that, it wouldn't be possible. 13:52.950 --> 13:57.330 IP did only take care of sending messages on to the next hop. 13:57.550 --> 14:03.010 They didn't care about receipt of packets at the destination. 14:03.870 --> 14:08.950 And then we certainly have to know something about the length of the 14:08.950 --> 14:11.730 header, since the length is dynamic. 14:12.670 --> 14:16.850 Here you see already there's an option field there, so there may be 14:16.850 --> 14:18.750 some variable sizes. 14:19.410 --> 14:23.190 So the header length has to be specified, otherwise the receiving side 14:23.190 --> 14:27.210 would not know where actually the data payload begins. 14:27.210 --> 14:34.710 So header length is there, you see it's number of words in the header, 14:35.090 --> 14:36.170 at least five. 14:37.290 --> 14:44.830 And so this is just showing where the data payload actually begins. 14:45.950 --> 14:47.730 And then we have certain flags here. 14:48.410 --> 14:49.850 Here, there are certain flags. 14:50.010 --> 14:54.230 So here's some region which is reserved for whatever purpose, not of 14:54.230 --> 14:54.890 interest here. 14:54.890 --> 14:58.990 But then there is a number of flags, one-bit flags, which can be set. 14:59.530 --> 15:01.510 Now I have to tell you something about those flags. 15:02.210 --> 15:11.230 The urgent bit is telling that the urgent pointer here is pointing to 15:11.230 --> 15:14.310 data which has to be read immediately. 15:15.530 --> 15:20.330 So the receiving side at the destination, the TCP header is analyzed. 15:20.330 --> 15:24.870 And I said, well, first of all, the data stream has to be rebuilt 15:24.870 --> 15:28.570 before the data is forwarded to the application layer. 15:30.210 --> 15:32.490 And so some things have to be done. 15:33.130 --> 15:37.890 Now if the urgent pointer is set, this is a pointer, the urgent 15:37.890 --> 15:42.130 pointer, which is pointing to some data in the data payload which has 15:42.130 --> 15:42.930 to be looked at. 15:42.930 --> 15:47.510 So this is an instruction for the TCP protocol at the receiving side 15:47.510 --> 15:49.950 to do something with specific data. 15:50.470 --> 15:55.070 And which data has to be looked at is shown here with the urgent 15:55.070 --> 15:55.510 pointer. 15:56.050 --> 16:01.870 And the urgent flag is indicating this urgent pointer field is valid. 16:02.030 --> 16:05.410 You have to follow that pointer. 16:06.730 --> 16:12.530 The ACK bit is actually telling whether the acknowledgment field is a 16:12.530 --> 16:13.630 valid field or not. 16:14.310 --> 16:19.110 So only if the acknowledgment field contains a valid value that has 16:19.110 --> 16:24.010 been specifically set by the destination side, this is actually 16:24.010 --> 16:24.730 utilized. 16:26.590 --> 16:32.710 So otherwise, if that is zero, then the acknowledgment number is not 16:32.710 --> 16:33.410 relevant. 16:35.650 --> 16:38.250 And we need that on both sides, by the way. 16:38.330 --> 16:41.650 So this is bidirectional communication between source and destination. 16:41.850 --> 16:45.230 The destination sends packets back to the source with the 16:45.230 --> 16:46.970 acknowledgment fields valid. 16:47.470 --> 16:50.950 And it means that also we have a data stream from the destination to 16:50.950 --> 16:51.490 the source. 16:51.490 --> 16:57.030 And this has also to be acknowledged by the source when it responds to 16:57.030 --> 16:58.150 the packets. 16:58.550 --> 17:03.630 Like when it sends a new packet to the destination of its original 17:03.630 --> 17:09.470 data stream, it also has to specify what is actually the information I 17:09.470 --> 17:11.710 got back from the destination. 17:11.930 --> 17:14.710 So it's a bidirectional communication sending of data. 17:15.050 --> 17:18.370 And on both sides, it needs these acknowledgment numbers. 17:18.370 --> 17:22.870 And the ACK field just tells whether the acknowledgment number is a 17:22.870 --> 17:24.730 valid number or not. 17:26.370 --> 17:30.930 Then you have something which is called a push flag. 17:31.550 --> 17:36.130 And the push flag is also very important because sometimes you 17:36.130 --> 17:41.290 actually must make sure that a datagram is delivered directly to the 17:41.290 --> 17:41.750 application. 17:42.510 --> 17:47.790 I said that normally this information, like we have to build up our 17:47.790 --> 17:54.850 old data stream from the datagrams that TCP received. 17:55.510 --> 17:58.310 And only if it's complete, it is forwarded to the application. 17:58.890 --> 18:02.230 Now there may be some situations, for example, you have an interactive 18:02.230 --> 18:02.930 application. 18:02.930 --> 18:10.070 You're pushing your keys on the keyboard, and then you certainly want 18:10.070 --> 18:11.450 immediate response. 18:12.050 --> 18:16.830 And so in interactive applications, you want that immediately. 18:17.270 --> 18:19.650 There should be a response on the application side. 18:20.110 --> 18:23.550 And so for that, the push bid has to be set. 18:24.890 --> 18:28.310 And then sometimes faults occur. 18:29.250 --> 18:33.510 And so sometimes the reset button or the reset flag has to be set, 18:33.850 --> 18:38.210 meaning that the connection has to be reset, has to be restarted anew 18:38.210 --> 18:40.390 because certain faults have occurred. 18:41.490 --> 18:45.350 Then there is the synchronize flag, which is set in the beginning. 18:46.230 --> 18:48.850 Initially, you have to set up the logical connection. 18:48.850 --> 18:51.930 And for that, you need to specify. 18:52.150 --> 18:54.970 Now we are establishing a new connection. 18:55.370 --> 19:00.110 So we have to follow a certain protocol, the three-way handshake 19:00.110 --> 19:04.650 protocol that is used for TCP, which we will get to know in a moment. 19:05.730 --> 19:09.270 And so that's another flag that has to be set. 19:09.270 --> 19:13.770 And finally, we have the final flag, the FIN flag, which is indicating 19:13.770 --> 19:20.130 that this is actually the last packet that is sent on this connection. 19:20.370 --> 19:22.790 So after that, this logical connection can be closed. 19:24.830 --> 19:27.830 So this is all these flags that we have here. 19:28.630 --> 19:32.370 And now we have another field, which is the window size. 19:33.910 --> 19:36.090 What do we need the window for? 19:36.850 --> 19:40.670 Well, TCP is responsible for reliability. 19:41.850 --> 19:45.990 And that means it must make sure that the communication does not 19:45.990 --> 19:49.570 suffer from communication faults. 19:50.190 --> 19:52.530 So loss of messages and so on. 19:53.070 --> 19:57.630 And the problem is that the more packets you send, the more likely it 19:57.630 --> 20:01.330 is that some packets will be lost because certain nodes are just 20:01.330 --> 20:04.650 overloaded, cannot do their work, and packets are discarded. 20:04.650 --> 20:08.770 And so you have to be able to control the traffic. 20:09.190 --> 20:14.910 Now, there's no central traffic controller, but every sender or every 20:14.910 --> 20:19.830 initiator of a TCP connection is responsible actually for influencing 20:19.830 --> 20:20.490 the traffic. 20:21.190 --> 20:26.670 So you are able to in some way to notice, well, certain faults occur 20:26.670 --> 20:29.390 because packets have not been acknowledged. 20:29.390 --> 20:35.090 If packets don't get acknowledged for some time, probably you have 20:35.090 --> 20:38.690 sent too many packets per time unit. 20:38.870 --> 20:41.250 So you reduce the number of packets. 20:42.390 --> 20:46.790 And so this window size is used for flow control. 20:47.570 --> 20:54.470 It actually means how many packets may I send before I actually wait 20:54.470 --> 20:59.250 or assume that I get an acknowledgment for the first packet that I 20:59.250 --> 20:59.670 have sent. 21:00.030 --> 21:02.010 I will show you that in a moment how that works. 21:02.570 --> 21:05.890 So you have a number of packets that you send out which are traveling 21:05.890 --> 21:06.730 in the network. 21:06.730 --> 21:10.810 And certainly it takes some time, this round-trip time from source to 21:10.810 --> 21:13.150 destination and back from destination to source. 21:14.030 --> 21:18.450 And it would be wasting of the potential of the network if you would 21:18.450 --> 21:22.270 just send one packet out and wait for the acknowledgment and then send 21:22.270 --> 21:22.990 the next packet. 21:23.430 --> 21:27.210 But you send a number of packets before you wait for the 21:27.210 --> 21:29.430 acknowledgment of the first packet that you sent out. 21:30.250 --> 21:34.810 And so if you don't get that, you have to reduce the window size. 21:34.810 --> 21:40.490 If everything is fine, you can increase the window size. 21:40.630 --> 21:42.510 And so you will see in a moment how that works. 21:43.190 --> 21:44.170 That's the window size. 21:44.410 --> 21:49.670 The central parameter for actually the completely self-organized 21:49.670 --> 21:52.970 control of the traffic flow in the Internet. 21:52.970 --> 21:58.590 This is the very essential part why actually the communication in the 21:58.590 --> 22:05.270 Internet is working fine without having a central controller which is 22:05.270 --> 22:06.210 regulating everything. 22:06.210 --> 22:13.250 Every node is taking care of that by looking at the current 22:13.250 --> 22:18.910 reliability of the network which is visible looking at the success of 22:18.910 --> 22:22.390 your transmission of packets. 22:22.990 --> 22:30.650 You see the current situation and you respond to that by adapting the 22:30.650 --> 22:33.090 number of packets you send per time unit. 22:33.090 --> 22:37.690 And then again we have to look for reliability with respect to the 22:37.690 --> 22:38.090 content. 22:39.030 --> 22:42.690 The first thing is to look at are the packets actually received. 22:43.090 --> 22:45.730 The next thing is, is the content still correct? 22:46.330 --> 22:51.010 And for that, you remember in the IP headers, we had a checksum. 22:51.190 --> 22:53.770 In IP version 6, we didn't have a checksum anymore. 22:54.670 --> 22:59.710 And so now we have a checksum here. 22:59.850 --> 23:03.750 Again, the once complement of the 16-bit sum of all 16-bit fields of 23:03.750 --> 23:05.510 the datagram header. 23:06.170 --> 23:08.470 The checksum zero plus data. 23:11.010 --> 23:16.850 And a so-called pseudo header, which I just let pop up here. 23:17.610 --> 23:25.290 The pseudo header is not part of the TCP header, but it's contained in 23:25.290 --> 23:26.230 the IP header. 23:27.170 --> 23:29.550 What is in the IP header which was essential? 23:29.550 --> 23:34.870 That's the source address, the destination address, the protocol 23:34.870 --> 23:39.150 version, and the TCP segment length. 23:39.970 --> 23:43.810 So this is the information that actually is a pseudo header. 23:44.110 --> 23:49.510 This information is forwarded from IP to the TCP layer. 23:50.170 --> 23:52.790 And so this checksum can be computed. 23:52.790 --> 23:58.930 And then, as always, initially, when you compute this, the checksum is 23:58.930 --> 23:59.230 zero. 23:59.550 --> 24:03.470 You take the once complement of that value, put that into that 24:03.470 --> 24:04.750 checksum field here. 24:05.370 --> 24:11.550 And if you now, at the receiving side, make that checksum, if it's not 24:11.550 --> 24:13.850 zero, you know that a fault has occurred. 24:14.170 --> 24:15.330 Some bits have been flipped. 24:16.410 --> 24:19.450 So this is just the typical way you perform checksums. 24:21.090 --> 24:25.030 And so in this way, the receiver can check for correct transmission of 24:25.030 --> 24:25.410 the datagram. 24:25.890 --> 24:29.570 If you have a wrong checksum, then you have to discard the packet. 24:29.930 --> 24:32.770 You will not send an acknowledgement of that datagram. 24:34.390 --> 24:35.430 And then there are options. 24:35.650 --> 24:41.390 And these options are options for, for example, the maximally accepted 24:41.390 --> 24:42.410 segment size. 24:42.410 --> 24:47.990 So every host must accept at least 536 bytes of data. 24:50.070 --> 24:58.170 536 bytes of data means that, well, you have 40 bytes for the TCP 24:58.170 --> 25:01.230 header, at least. 25:02.190 --> 25:15.590 And so it's 576 bytes, which is the minimal size of a datagram, which 25:15.590 --> 25:19.790 is then extended by the IP header and so on. 25:20.790 --> 25:30.350 And so it's maximally 65k bytes, which you can have there in the size. 25:30.470 --> 25:36.010 And this size actually is negotiated between sender and receiver. 25:37.150 --> 25:38.930 So between source and destination. 25:39.690 --> 25:44.130 And it definitely would not make sense to have a very small value 25:44.130 --> 25:49.930 there, because if the data payload is too small, you have too much 25:49.930 --> 25:54.590 overhead for all these administrative information in all the headers 25:54.590 --> 25:55.190 that are there. 25:56.010 --> 26:03.710 And there is also a limit on the size, because if it's very large, 26:03.710 --> 26:09.290 then the probability of faults that might occur, and which lead to 26:09.290 --> 26:17.710 packet dismissal or packet deletion, then is just getting higher. 26:18.030 --> 26:22.610 So you don't want to send too long datagrams, and they should not be 26:22.610 --> 26:23.250 too short. 26:24.250 --> 26:29.270 And then there are certain restrictions because of the buffer sizes of 26:29.270 --> 26:32.670 the nodes in between and so on. 26:32.670 --> 26:39.630 So it depends on what kind of routers were visited when you 26:39.630 --> 26:49.390 established the connection between source and destination, which is 26:49.390 --> 26:51.610 just a logical connection, as you know. 26:51.610 --> 27:03.810 So in this, these initial communication, this length is like this 27:03.810 --> 27:07.310 segment size is negotiated. 27:07.790 --> 27:11.750 And later on, as I told you, maybe that some packets have to go over 27:11.750 --> 27:17.950 paths that do not support that size, and then you get fragmentation. 27:18.710 --> 27:23.050 Fragmentation of the segments into smaller packets, because there are 27:23.050 --> 27:29.250 certain restrictions on some parts of this physical path that actually 27:29.250 --> 27:33.610 is chosen, and TCP only knows about a logical path. 27:35.730 --> 27:40.190 And then you can also set a scaling factor for the window size. 27:41.150 --> 27:44.170 So here you have 16 bits for the window size. 27:44.230 --> 27:49.850 If you scale that, you have larger possibilities to actually have your 27:49.850 --> 27:50.490 window size. 27:50.610 --> 27:53.910 You see that the window may be quite large. 27:54.030 --> 28:00.930 The number of datagrams may get very large, but this is a dynamic 28:00.930 --> 28:01.250 thing. 28:01.890 --> 28:05.450 And then you might also request specific things. 28:05.450 --> 28:11.270 For example, it may be that the receiver sends information that a 28:11.270 --> 28:13.510 specific datagram is missing. 28:14.170 --> 28:16.070 So this is a negative acknowledgement. 28:16.690 --> 28:22.410 It just sends or asks for resending of a specific datagram, and that 28:22.410 --> 28:28.430 would avoid resending everything from a point on where information was 28:28.430 --> 28:33.230 not received by the destination, regardless of what has been received 28:33.230 --> 28:33.890 after that. 28:33.890 --> 28:38.850 So negative acknowledgement is something which can also reduce the 28:38.850 --> 28:43.210 necessary traffic if you can acknowledge or if you can send 28:43.210 --> 28:49.070 information that only a specific datagram out of a stream of datagrams 28:49.070 --> 28:52.770 has to be resend because that had not been received so far. 28:53.130 --> 28:56.810 Or maybe there has been a fault, has been received, and there has been 28:56.810 --> 29:00.030 a fault, so you ask for resending of that specific datagram. 29:00.990 --> 29:01.490 Okay. 29:02.250 --> 29:05.910 So this was just why we need this information. 29:06.310 --> 29:11.230 And I hope you agree that this kind of information is important to 29:11.230 --> 29:19.430 actually be able to deal adequately with the tasks of TCP, providing 29:19.430 --> 29:26.510 reliability, and so forth, and being able to actually forward the data 29:26.510 --> 29:31.510 payload to the appropriate destination application. 29:33.330 --> 29:37.970 So then we have to look at how we actually establish TCP connections. 29:38.610 --> 29:39.650 So how do we do that? 29:40.390 --> 29:43.990 The server always waits for incoming connection requests. 29:44.330 --> 29:45.390 So you send information. 29:45.390 --> 29:52.070 The sender has to execute something which is a connect primitive, and 29:52.070 --> 29:59.170 then you have to put in the IP address of the server, the desired port 29:59.170 --> 30:04.690 for the connection, like your port that you are using on the source 30:04.690 --> 30:08.170 side, or that the application on the source side is using, and the 30:08.170 --> 30:11.330 port for the destination side. 30:11.330 --> 30:18.190 You have to put in the maximally handled segment size on your side of 30:18.190 --> 30:25.270 the source, and maybe some more user data that you might need, which 30:25.270 --> 30:26.290 we just neglect. 30:27.390 --> 30:30.890 Those details can be looked up in the specific protocol 30:30.890 --> 30:31.570 specifications. 30:32.170 --> 30:36.470 The central point is that we have a so-called three-way handshake 30:36.470 --> 30:37.050 protocol. 30:37.750 --> 30:39.430 So it's a handshake protocol. 30:39.810 --> 30:44.770 You always have to agree that you do something, and you shake hands 30:44.770 --> 30:45.270 for that. 30:45.670 --> 30:48.210 So the host 1 and host 2 have to communicate. 30:49.250 --> 30:55.570 And they just send now packets having the sync field set in their 30:55.570 --> 30:59.310 flags, and then you have the time there. 31:00.490 --> 31:06.550 So host 1 will send a datagram with some sequence number. 31:07.290 --> 31:11.390 Now, x is just one value. 31:11.550 --> 31:13.390 It's a 32-bit value. 31:14.530 --> 31:20.910 So you just take one value adequately determined, depending on what 31:20.910 --> 31:22.950 has been sent before, and things like that. 31:23.050 --> 31:26.030 So the sender just selects an arbitrary value there. 31:26.770 --> 31:28.810 And so that is the sequence number x. 31:30.110 --> 31:33.070 And the send field has to be set to 1. 31:33.950 --> 31:40.350 And then host 2 receives that data, that request, hopefully, and will 31:40.350 --> 31:41.690 respond to that. 31:42.330 --> 31:49.670 Now, it will respond with its own sequence number, a sequence number 31:49.670 --> 31:56.710 y, because it also sends data, or the acknowledgement data, maybe some 31:56.710 --> 32:00.330 more information which sometimes has to be sent, some administrative 32:00.330 --> 32:02.010 data which might be important. 32:03.230 --> 32:10.690 And so it sends sequence number y, and it sends x plus 1, because it 32:10.690 --> 32:19.570 has received, or it requests that there should be information. 32:20.210 --> 32:24.710 The next information I get, the next byte, should be numbered with x 32:24.710 --> 32:25.230 plus 1. 32:28.500 --> 32:38.340 And now the host 1, on receiving that, acknowledges the 32:38.340 --> 32:38.960 acknowledgement. 32:38.960 --> 32:50.740 So it tells, okay, it sends a datagram where the acknowledgement field 32:50.740 --> 32:54.600 is set, where the sequence number is x plus 1, and the acknowledgement 32:54.600 --> 32:55.960 number is y plus 1. 32:58.300 --> 33:01.720 And now data actually can be sent. 33:01.920 --> 33:04.840 Host 1 can start sending data. 33:05.840 --> 33:10.920 So it's again sequence number x plus 1, and then you have the data, 33:11.300 --> 33:15.300 and after that it can work in the way I have indicated in a very 33:15.300 --> 33:18.280 superficial way on the previous slides. 33:19.460 --> 33:24.960 So this is the three-way handshake protocol, these three messages that 33:24.960 --> 33:25.720 have to be sent. 33:26.560 --> 33:32.260 And if that works correctly, you have a logical connection, which 33:32.260 --> 33:39.460 actually is characterized by x and y. 33:40.120 --> 33:44.520 Those are the two sequence numbers which actually indicate this is 33:44.520 --> 33:46.160 where the communication starts. 33:48.000 --> 33:51.300 Then you know something about all the data that will be sent, about 33:51.300 --> 33:54.740 the numbering of the bytes, and you can deal with that, you can put in 33:54.740 --> 33:56.860 the information at the appropriate places, and so on. 33:57.960 --> 34:01.720 Okay, now certainly faults can occur. 34:03.100 --> 34:06.840 So when you send a datagram, the timer has started. 34:07.900 --> 34:12.500 There are several timers that are always maintained in order to look 34:12.500 --> 34:14.420 for all kinds of faults that can occur. 34:15.180 --> 34:20.540 And if you have a timeout, if your timer has been decremented to zero, 34:20.540 --> 34:25.980 then you have to do some appropriate action, you have to retransmit 34:25.980 --> 34:26.480 something. 34:28.620 --> 34:32.900 Then there are certain things that can occur. 34:33.720 --> 34:39.560 So maybe the two hosts require or request a connection simultaneously. 34:40.140 --> 34:41.140 It may happen. 34:45.300 --> 34:50.780 Then here, for example, this is sent. 34:51.400 --> 34:57.800 You get an acknowledgment, and host 2 responds to that request, but 34:57.800 --> 35:03.580 before that had sent out its own sync request, and then it 35:03.580 --> 35:09.980 acknowledges sequence y and x plus 1, and now before that is received, 35:10.600 --> 35:17.660 host 1 had received the sync request, and has sent x and acknowledges 35:17.660 --> 35:18.740 y plus 1. 35:20.560 --> 35:27.860 And here, both essentially have established the same connection, so 35:27.860 --> 35:34.660 only one connection represented by x and y actually is established, 35:34.660 --> 35:39.320 and there is no problem with that situation. 35:40.740 --> 35:45.400 It is a call collision in some way, but only one connection gets 35:45.400 --> 35:49.460 established, and they have these same numbers, x and y in this case. 35:50.460 --> 36:03.400 And then maybe that something happens that you have sent out a 36:03.400 --> 36:10.040 synchronization request, and you have established a connection, and 36:10.040 --> 36:15.500 later on you get another synchronization request, which might have 36:15.500 --> 36:21.100 been sent out long before, but for some reason it was delayed 36:21.100 --> 36:29.920 somewhere, and so it's delivered only after that other synchronization 36:29.920 --> 36:33.600 request had been established actually here. 36:34.180 --> 36:38.220 So if you get another packet, another request with the same sequence 36:38.220 --> 36:43.380 number from this host 1, this second one, the late duplicate, which 36:43.380 --> 36:48.260 for some reason was delayed, which led to a resending of the 36:48.260 --> 36:54.280 synchronization request on the host 1 side, is ignored by the host 2. 36:56.220 --> 37:01.080 Okay, this is just an example of what kind of situations can occur. 37:01.280 --> 37:03.080 There are more situations that can occur. 37:03.420 --> 37:06.940 Just wanted to give you an indication that fault handling is very 37:06.940 --> 37:11.360 important, because you must make sure that you have a correct logical 37:11.360 --> 37:11.940 connection. 37:12.700 --> 37:17.780 And if you have established that, then again you might have problems 37:17.780 --> 37:20.760 with controlling the traffic flow. 37:21.120 --> 37:22.380 We will look at that in a moment. 37:23.300 --> 37:24.580 Now, connection closure. 37:26.020 --> 37:30.940 If a host does not intend to send more data, if all the data have been 37:30.940 --> 37:37.920 sent, it puts the final flag on the last datagram, and then the 37:37.920 --> 37:40.580 receiving side notes, now this connection can be closed. 37:41.880 --> 37:44.920 And then the other certainly will send data. 37:45.300 --> 37:49.660 It may still have to respond with certain acknowledgment packets. 37:50.020 --> 37:52.600 It will send out all the necessary acknowledgment packets. 37:52.600 --> 38:06.380 And then it will also send a fine, thin datagram, and then the 38:06.380 --> 38:07.360 connection is ended. 38:07.580 --> 38:11.920 So this is just, you have to be able to connect or to close the 38:11.920 --> 38:12.580 connections. 38:13.300 --> 38:21.960 And just to mention one point, you might have heard about denial of 38:21.960 --> 38:23.340 service attacks. 38:24.140 --> 38:31.300 One of those attacks is to just send very large numbers of 38:31.300 --> 38:37.080 synchronization requests to a host, and then the host is just busy 38:37.080 --> 38:40.400 with responding to those synchronization requests. 38:40.400 --> 38:45.000 And you just don't send anything more, you just send new requests. 38:45.500 --> 38:49.300 And by sending all these new requests, the receiving host has to 38:49.300 --> 38:54.020 respond to that, tries to establish a connection, has to reserve the 38:54.020 --> 39:02.580 connection points X and Y, and so it is overloaded with all these 39:02.580 --> 39:08.920 requests and can no longer support, really, connections which are real 39:08.920 --> 39:10.680 connections. 39:11.900 --> 39:22.960 So this protocol is actually carried out by the server. 39:23.000 --> 39:26.580 As I said, the server is always waiting for incoming synchronization 39:26.580 --> 39:31.780 requests, and then another routine takes over when you have the 39:31.780 --> 39:35.440 communication established between the appropriate ports. 39:36.440 --> 39:42.580 And so this is one point where denial of service attacks actually try 39:42.580 --> 39:48.980 to attack a certain service which is essential for providing 39:48.980 --> 39:49.740 communication. 39:50.880 --> 39:53.460 Now the question is how we can actually send data. 39:53.460 --> 40:00.980 As I said, we have the task to make sure that we have reliable 40:00.980 --> 40:04.960 communication, and so we have this sliding window protocol. 40:05.820 --> 40:07.440 What is the sliding window protocol? 40:07.840 --> 40:13.180 I just visualized that as a sliding window, and it means that this 40:13.180 --> 40:18.880 sliding window indicates that we have a certain number of packets 40:18.880 --> 40:27.320 which are sent, that's the window size, and as I said, we send out X 40:27.320 --> 40:34.760 or K packets, and we always wait for the acknowledgement of the first 40:34.760 --> 40:41.180 packet that has been sent out, like when we send this packet out, but 40:41.180 --> 40:50.300 the acknowledgement for the first packet that had been sent should be 40:50.300 --> 40:50.800 in there. 40:51.040 --> 40:58.320 So as long as the acknowledgements come in at exactly a sufficient 40:58.320 --> 41:04.700 speed, then we'll have that many packets that are sent out all the 41:04.700 --> 41:05.100 time. 41:05.580 --> 41:06.720 So that's the window size. 41:07.000 --> 41:11.880 Now this is not a constant value, this is changing all the time. 41:13.480 --> 41:17.760 So the window size determines how many datagrams we can send, and you 41:17.760 --> 41:21.780 might have noticed that if you look at your transmissions, you can 41:21.780 --> 41:26.860 look at TCP connections, and you can look at the performance of your 41:26.860 --> 41:32.320 computer, and if you perform a file transfer, you see that it looks 41:32.320 --> 41:37.120 like something like this, and then like that, and goes down for some 41:37.120 --> 41:37.440 time. 41:37.740 --> 41:39.460 So this is a curve like that. 41:41.240 --> 41:45.460 And the reason for that is explained in what I tell you now. 41:46.220 --> 41:54.440 So what we... or it will be explained on the next slide, actually. 41:55.140 --> 41:59.220 So the window size, as I said, is dynamically changing. 42:00.280 --> 42:06.360 And this, like here you have the number of bytes that are sent. 42:07.020 --> 42:12.660 So the number of bytes that are sent if you perform a file transfer 42:12.660 --> 42:19.040 depends on the current reliability of the system, or the changing 42:19.040 --> 42:20.760 window size. 42:21.580 --> 42:24.220 So sometimes you have a very small window size, and then you have a 42:24.220 --> 42:27.440 larger window size again, again a smaller window size, a larger window 42:27.440 --> 42:28.300 size, and so on. 42:28.300 --> 42:35.340 And that's why we have this dynamic pattern of the transfer rate if 42:35.340 --> 42:38.540 you send data using TCP IP. 42:40.700 --> 42:45.560 So W is... like the window size is dynamically determined between 42:45.560 --> 42:51.060 sender and receiver, but this is the maximum window size that can be 42:51.060 --> 42:51.420 used. 42:52.400 --> 42:58.440 And as I said, the acknowledgement field always contains the maximum 42:58.440 --> 43:03.220 received sequence number plus one, up to which all bytes have been 43:03.220 --> 43:05.940 received correctly, and the acknowledgement is done in the next 43:05.940 --> 43:07.600 available or reasonable datagram. 43:08.060 --> 43:12.100 So some datagram is sent back from destination to source, and the 43:12.100 --> 43:19.360 acknowledgement field there is always having that value, the last byte 43:19.360 --> 43:22.280 that has been received correctly, plus one. 43:24.420 --> 43:28.980 And if a segment has not been acknowledged in time, everything 43:28.980 --> 43:32.040 starting from that location has to be resent. 43:32.660 --> 43:37.280 So if that byte here is not acknowledged, everything starting from 43:37.280 --> 43:42.680 that has to be resent, although they have been sent out already. 43:45.960 --> 43:50.160 So that's what I mentioned now several times, and there is this 43:50.160 --> 43:54.620 negative acknowledge option which can be used, and then you have 43:54.620 --> 44:00.420 negative acknowledgement and only one datagram is sent again. 44:01.160 --> 44:04.200 And now we come to the dynamic flow control which I just indicated. 44:04.760 --> 44:08.140 So what we don't like is faults. 44:08.920 --> 44:15.540 And so if the window size is too large, you might have losses, and so 44:15.540 --> 44:18.020 the window size could be or should be reduced. 44:18.760 --> 44:25.160 Usually the current window size is just halved to achieve better 44:25.160 --> 44:26.080 transmission rates. 44:28.360 --> 44:32.380 And this is done in the following way. 44:32.380 --> 44:38.660 You don't start with a maximum window size, but you start with a very 44:38.660 --> 44:39.900 small window size. 44:40.300 --> 44:42.260 The first window size is one. 44:42.920 --> 44:51.280 And it means that you have here your, let me say, the window size or 44:51.280 --> 44:52.260 the... 44:53.800 --> 44:58.360 I take the window size. 44:59.020 --> 45:04.140 This is the window size, and you have here, initially you have a 45:04.140 --> 45:05.480 maximum window size. 45:06.580 --> 45:09.100 Maximum window size. 45:09.340 --> 45:16.620 And then you start with one, and then you wait for acknowledgement. 45:17.240 --> 45:21.380 If you get an acknowledgement, you increase the window size to two. 45:22.200 --> 45:30.680 If you get an acknowledgement for, like you send out two datagrams, 45:31.120 --> 45:34.700 and now after you send out the second datagram, you get an 45:34.700 --> 45:37.520 acknowledgement for the first one, you send out four. 45:37.520 --> 45:43.400 So this is increasing exponentially until you get to the maximum 45:43.400 --> 45:44.380 window size. 45:45.260 --> 45:53.260 Or you should not send larger datagrams or use larger window sizes 45:53.260 --> 45:53.980 than that. 45:56.640 --> 46:01.580 But maybe that you even don't get there, because there's a fault. 46:01.580 --> 46:08.860 A fault means you did not receive an acknowledgement for the first 46:08.860 --> 46:14.400 datagram that you had sent out of that window, and so you know this 46:14.400 --> 46:15.180 was too much. 46:16.220 --> 46:21.740 And so you decrease the current value that you have. 46:21.840 --> 46:28.360 So the initial threshold value, T here, is the max window size. 46:29.320 --> 46:39.080 And so if you have a problem there, then you reduce that value. 46:39.800 --> 46:44.140 So you set T to W over two. 46:45.380 --> 46:52.280 The threshold now is, like this is the current value of W, this is 46:52.280 --> 46:57.760 halved, so this will be the new threshold, T. 46:57.760 --> 47:00.660 Then you start again, the slow start. 47:02.480 --> 47:10.580 Exponential increase up to that point in time where you reach that 47:10.580 --> 47:14.580 threshold value, fast increase of the window size. 47:16.040 --> 47:20.660 And then you continue with a slow increase of the window size. 47:20.660 --> 47:22.920 So it's a linear addition. 47:23.040 --> 47:27.960 So you only add one datagram, or maybe two or something is the policy 47:27.960 --> 47:30.660 of the router. 47:31.200 --> 47:35.980 You only linearly increase the window size after you have reached that 47:35.980 --> 47:37.920 threshold value, T. 47:39.060 --> 47:44.220 And then you increase again, and then maybe you have a fault. 47:44.220 --> 47:50.440 And then this, or certainly you never get above that line. 47:51.400 --> 47:55.280 Maybe you have sent something for some time there, and then you have a 47:55.280 --> 47:55.620 fault. 47:56.760 --> 48:03.320 Again, you have to set the threshold value to half the current window 48:03.320 --> 48:07.300 size, and it continues like that. 48:07.580 --> 48:09.660 Maybe you have another failure. 48:09.660 --> 48:14.540 Again, you get down there, and you start again, and so on. 48:15.680 --> 48:17.900 And this is the way the traffic is controlled. 48:18.520 --> 48:22.360 As soon as you have a failure, that means a packet has not been 48:22.360 --> 48:25.280 acknowledged, you reduce the window size. 48:25.340 --> 48:30.120 You start anew with just a window size of one, and you increase the 48:30.120 --> 48:35.240 window size quite quickly up to the point where you reach that 48:35.240 --> 48:36.240 threshold value. 48:36.240 --> 48:42.880 And then you increase slowly, and you never go above the max window 48:42.880 --> 48:49.000 size, but you increase, increase, increase, and then if you have a 48:49.000 --> 48:51.060 fault again, it gets down again. 48:51.720 --> 48:56.480 You get a new threshold value, a new small window size, and you start 48:56.480 --> 48:56.880 again. 48:57.580 --> 49:00.740 So this is the way the communication is controlled. 49:00.740 --> 49:08.080 And that's why we have, if we transmit data, we have something like 49:08.080 --> 49:10.900 this. 49:11.300 --> 49:19.700 If you look at the data speed, or the speed of transmission, or the 49:19.700 --> 49:22.540 number of bytes that are transmitted, the bandwidth that you actually 49:22.540 --> 49:28.120 can use when you transmit a file between two computers. 49:29.080 --> 49:33.720 So here we have a dynamic data flow, and this is something which is 49:33.720 --> 49:40.880 controlled by every router, by every TCP controlling node in the 49:40.880 --> 49:41.320 network. 49:41.700 --> 49:46.140 It is controlling the flow, and so the traffic is adjusted dynamically 49:46.140 --> 49:48.360 in a completely self-organized way. 49:49.540 --> 49:53.860 There's no central controller telling everybody, you all have to 49:53.860 --> 49:56.460 reduce your window sizes. 49:56.460 --> 49:57.780 There's nothing like that. 49:58.880 --> 50:04.100 It's negotiated between the individual components there, and so this 50:04.100 --> 50:12.040 is the ingenious idea of those who invented the ARPANET initially, and 50:12.040 --> 50:13.560 designed TCP IP. 50:14.720 --> 50:20.040 It's amazing that it's still working, that it is so scalable, that it 50:20.040 --> 50:26.300 still works with very large traffic, or network sizes that we have 50:26.300 --> 50:26.740 now. 50:27.120 --> 50:33.400 At the time where it was designed, you had a few hundred nodes in the 50:33.400 --> 50:33.760 network. 50:35.580 --> 50:40.000 Okay, so this is called also congestion control. 50:40.660 --> 50:43.480 So you have slow start plus congestion avoidance. 50:44.180 --> 50:48.380 Congestion avoidance means that as soon as you have some problem, 50:49.180 --> 50:53.760 packets don't get acknowledged, you reduce the traffic, and so you 50:53.760 --> 50:56.460 avoid congestions in the network. 50:56.940 --> 50:59.380 You have reliability of communication. 51:01.040 --> 51:10.000 Now, this is a really perfect property, but it's also a problem of 51:10.000 --> 51:10.320 TCP. 51:11.020 --> 51:17.900 One problem is that this sliding window protocol means that if a 51:17.900 --> 51:23.400 segment is lost, then many segments have to be sent again. 51:24.280 --> 51:28.620 So it may mean that you have retransmission of many segments, and if 51:28.620 --> 51:35.360 you have some dynamic flow of data bytes or of datagrams, as I 51:35.360 --> 51:39.400 indicated in the previous slide, this is very bad for certain 51:39.400 --> 51:40.000 applications. 51:41.740 --> 51:46.380 So slow start may lead to frequent changes in throughput, and if you 51:46.380 --> 51:49.940 have, for example, multimedia applications, this is not what you want. 51:50.280 --> 51:55.240 You want to have a stable bandwidth, a stable transmission capacity, 51:56.060 --> 52:00.680 and it really is not that important if a packet is lost. 52:01.340 --> 52:06.600 You don't really notice that if one packet in an audio transmission is 52:06.600 --> 52:06.960 lost. 52:07.140 --> 52:13.840 There may be a short disturbance there, but you don't really notice 52:13.840 --> 52:14.260 that. 52:15.200 --> 52:21.940 And so it's more important to have a stable data rate than to have 52:21.940 --> 52:25.240 complete reliability of transmission. 52:26.120 --> 52:31.180 And so for transmission of audio signals and for multimedia 52:31.180 --> 52:37.000 applications, usually you move the reliability control into the next 52:37.000 --> 52:37.360 layer. 52:37.460 --> 52:39.120 You don't use TCP for that. 52:39.560 --> 52:44.340 There actually are, or people have designed special protocols to 52:44.340 --> 52:49.200 support audio transmission, but you can also do that on the next 52:49.200 --> 52:49.540 layer. 52:50.320 --> 52:55.000 To move this reliability control on the next layer is the application 52:55.000 --> 52:55.340 layer. 52:55.420 --> 53:00.860 You have to move it into the application, and this forwarding the 53:00.860 --> 53:04.560 reliability to the application layer means that you have to use a 53:04.560 --> 53:10.400 protocol different from TCP and that is UDP, which we will look at in 53:10.400 --> 53:10.740 a moment. 53:11.740 --> 53:17.640 And then this flow control scheme is based on assumptions that are 53:17.640 --> 53:20.100 valid for wire-based communication. 53:20.660 --> 53:30.520 If you have wireless communication, then it may be not actually 53:30.520 --> 53:37.880 reasonable to reduce the number of datagrams you send because it may 53:37.880 --> 53:42.100 be that faults have nothing to do with the number of bytes you send, 53:42.200 --> 53:47.740 but there are certain disturbances in the connection, something in 53:47.740 --> 53:50.040 between, in the air between two locations. 53:50.460 --> 53:54.440 And so that's not really the problem of bandwidth, but there are 53:54.440 --> 53:55.700 certain other disturbances. 53:56.380 --> 54:02.800 And so there, dynamic flow control may lead even to worse transmission 54:02.800 --> 54:03.340 rates. 54:04.840 --> 54:09.920 And if you have wireless communication, maybe that you should actually 54:09.920 --> 54:14.120 retransmit your packets at a higher rate in order to make sure that 54:14.120 --> 54:19.180 some actually get over that wireless communication or wireless 54:19.180 --> 54:19.780 connection. 54:20.640 --> 54:27.480 And so for that, it's not the best possible way to actually use TCP. 54:29.580 --> 54:36.960 So TCP has no idea about what kind of physical connection will be used 54:36.960 --> 54:41.880 later on because TCP is operating on the transport layer and the 54:41.880 --> 54:47.160 physical connection is on the lower levels of the physical data layer. 54:48.560 --> 54:51.760 And so it cannot decide for the most reasonable method of flow 54:51.760 --> 54:52.280 control. 54:52.280 --> 54:56.380 But if you know that something will be sent by wireless communication, 54:56.820 --> 55:00.820 if that information is available, you should go for a different policy 55:00.820 --> 55:02.800 in flow control. 55:05.080 --> 55:07.780 Okay, so there are some problems. 55:08.560 --> 55:14.380 Actually, there are quite a few efforts, quite a few projects in 55:14.380 --> 55:22.660 research to design new protocols for the next layer Internet, the next 55:22.660 --> 55:27.080 level of the Internet, certain ideas how you can actually modify those 55:27.080 --> 55:31.920 protocols to get more efficient communication for all kinds of 55:31.920 --> 55:35.140 properties that are reasonable there. 55:36.040 --> 55:39.540 And I just cannot address those topics in this course. 55:39.540 --> 55:44.080 For that, you have to go into courses on specifically looking at 55:44.080 --> 55:50.100 Internet technology where you can have a complete course just on those 55:50.100 --> 55:50.540 topics. 55:51.120 --> 55:55.640 As you know, I only tell you something about the basic protocols that 55:55.640 --> 55:56.960 we have, the basic algorithms. 55:57.680 --> 56:01.720 This course is not devoted completely to Internet protocols. 56:02.560 --> 56:05.720 But I have to tell you now about the UDP protocol. 56:05.720 --> 56:12.540 UDP is what I just mentioned on explaining the previous slide. 56:12.980 --> 56:18.180 We would like to be able to just ignore the reliability and forward 56:18.180 --> 56:20.060 that task to the application layer. 56:20.920 --> 56:23.400 And for that, we have the user datagram protocol. 56:23.980 --> 56:28.820 It essentially means that the user, the application, should actually 56:28.820 --> 56:36.020 take care of the datagrams and it will not get a complete sequence or 56:36.020 --> 56:42.600 a reconstructed sequence of data as TCP does, but it will just send 56:42.600 --> 56:43.660 datagrams on. 56:44.000 --> 56:48.620 So the IP service just gets extended to the application layer. 56:48.700 --> 56:52.460 It provides a connectionless, unreliable transport service. 56:53.160 --> 56:57.660 And this is exactly the properties that IP also looked at. 56:57.660 --> 57:02.920 So IP did not care about connections, about reliability. 57:03.800 --> 57:07.520 UDP also does not establish a logical connection. 57:08.020 --> 57:12.060 It just sends out packets and hopes that they will be received 57:12.060 --> 57:12.600 sometime. 57:13.080 --> 57:14.320 It doesn't care about that. 57:14.440 --> 57:17.220 The application layer has to care about that. 57:17.220 --> 57:21.660 Nevertheless, the UDP's header certainly has to provide the 57:21.660 --> 57:26.340 information that is necessary to actually make sure that, again, 57:27.480 --> 57:33.180 sender and destination, that they can communicate in the right way. 57:33.600 --> 57:38.780 That means that they don't establish a logical connection, but you 57:38.780 --> 57:42.560 have to know which ports actually are essential. 57:42.560 --> 57:47.940 So if a datagram is sent out here, it has to be put to the right port 57:47.940 --> 57:50.620 and then forwarded to the right application. 57:51.360 --> 57:55.420 So you need source port and destination port as we needed that in the 57:55.420 --> 57:56.100 TCP header. 57:56.480 --> 57:59.560 That's for addressing the adequate application. 58:00.920 --> 58:04.860 And you also have to tell about the length. 58:05.680 --> 58:10.520 So the length is the total length of the datagram header plus data. 58:10.520 --> 58:17.180 Here, the header always has the same size. 58:17.940 --> 58:20.660 So it's 8 bytes in this case. 58:21.300 --> 58:22.120 Very short header. 58:24.300 --> 58:29.080 And then the length is the total length of the datagram header plus 58:29.080 --> 58:29.480 data. 58:30.160 --> 58:32.740 The checksum is the same as before. 58:32.740 --> 58:36.880 For TCP also, the pseudo-header is included, the source address, 58:37.020 --> 58:41.040 destination address, and this administrative information that I showed 58:41.040 --> 58:43.040 you when I showed you the TCP header. 58:44.180 --> 58:50.200 So UDP is mainly used to grant application programs direct access to 58:50.200 --> 58:54.760 the IP layer, and then they have to deal with unreliability, with 58:54.760 --> 58:57.280 traffic control, and so on. 58:58.220 --> 59:07.240 So UDP is just sending out information at a certain rate, and it 59:07.240 --> 59:09.220 doesn't care about flow control. 59:11.440 --> 59:14.020 And so this is just very briefly a UDP. 59:14.520 --> 59:20.340 There are more details that are of interest, like how many datagrams 59:20.340 --> 59:23.120 per second are actually sent from UDP and things like that. 59:23.600 --> 59:25.440 I don't go into the details there. 59:25.440 --> 59:31.220 And I wanted to briefly mention also this other protocol I had in the 59:31.220 --> 59:32.660 list there a few times. 59:33.400 --> 59:38.060 A stream control transmission protocol, and that's an alternative to 59:38.060 --> 59:46.180 TCP, which is just like I just copied the properties from the 59:46.180 --> 59:54.040 description of SETP and the appropriate RSC here, 4960. 59:55.740 --> 01:00:04.560 And so again, it is providing reliability, error-free, non-duplicated 01:00:04.560 --> 01:00:09.100 transfer of user data, so that you have checksums in there and things 01:00:09.100 --> 01:00:09.720 like that. 01:00:10.260 --> 01:00:14.420 And it is acknowledged, so your reliability is taken care of, data 01:00:14.420 --> 01:00:21.820 fragmentation is dealt with appropriately, like the maximum transport 01:00:21.820 --> 01:00:30.480 unit size is the maximum segment size that you have there, or as I 01:00:30.480 --> 01:00:39.880 said, sometimes you have these smaller packet sizes, and then the 01:00:39.880 --> 01:00:48.100 fragments have to be reassembled into the original segment sizes and 01:00:48.100 --> 01:00:49.560 into the original data stream. 01:00:50.280 --> 01:00:53.260 And then you have something which TCP does not take care of. 01:00:53.260 --> 01:00:57.100 Here you have a sequence delivery of user messages within multiple 01:00:57.100 --> 01:01:02.600 streams, and you have an option for order of arrival delivery of 01:01:02.600 --> 01:01:03.880 individual user messages. 01:01:04.100 --> 01:01:08.740 This is something which TCP is not necessarily the case. 01:01:08.740 --> 01:01:22.220 It does not take care about order of, like normally you have this... 01:01:22.220 --> 01:01:30.400 TCP, as I said, has a sequence, like TCP had this sequence of 01:01:30.400 --> 01:01:35.700 segments, and will always provide the data in the same order as it had 01:01:35.700 --> 01:01:36.700 been sent out. 01:01:36.700 --> 01:01:40.300 And if something is missing, it's not sent out. 01:01:41.140 --> 01:01:45.800 And here you have an order of arrival option, that means if they come 01:01:45.800 --> 01:01:54.960 in in a different order, the datagrams will be forwarded to the next 01:01:54.960 --> 01:01:58.840 layer in the order of arrival, and not necessarily in the order they 01:01:58.840 --> 01:01:59.540 have been sent. 01:02:00.400 --> 01:02:06.180 And you can bundle multiple user messages into one SETP packet, so 01:02:06.180 --> 01:02:10.180 there are certain options that go beyond what TCP actually is doing. 01:02:11.180 --> 01:02:16.960 And I don't go into the details, I just wanted to mention that there 01:02:16.960 --> 01:02:23.780 is another protocol, which is also available there, and as I mentioned 01:02:23.780 --> 01:02:29.440 also, there are these protocols, like ICMP and so on, on the network 01:02:29.440 --> 01:02:33.360 layer, which I also didn't specify here in details. 01:02:33.360 --> 01:02:39.040 I cannot give here a course on internet technologies in depth, I just 01:02:39.040 --> 01:02:44.060 wanted to mention the major protocols in depth, which was TCP and IP. 01:02:45.540 --> 01:02:49.800 And then I briefly want to mention one alternative approach to 01:02:49.800 --> 01:02:57.160 controlling communication, and that, like ATM, was developed quite 01:02:57.160 --> 01:03:02.840 some time ago, but it was later than TCP-IP, and it addressed a 01:03:02.840 --> 01:03:06.420 different way of actually controlling the traffic. 01:03:08.040 --> 01:03:13.080 ATM, asynchronous transfer mode, actually would do if you have a 01:03:13.080 --> 01:03:18.700 network, and you have here your source and destination, then you would 01:03:18.700 --> 01:03:28.480 have a fixed path through that network to get from source to this 01:03:28.480 --> 01:03:29.280 destination. 01:03:30.000 --> 01:03:36.320 And all the packets would follow exactly that path, so you have a so 01:03:36.320 --> 01:03:38.120 -called virtual channel. 01:03:40.400 --> 01:03:46.520 And if all the packets are following the same path, then you don't 01:03:46.520 --> 01:03:51.840 need what we had with TCP-IP, where at every node we had to look for 01:03:51.840 --> 01:03:58.460 the best possible next hop to actually get on the shortest path to the 01:03:58.460 --> 01:04:02.060 destination, according to the current situation in the network. 01:04:03.140 --> 01:04:08.720 ATM says, okay, I just sent a stream of packets, and they will all go 01:04:08.720 --> 01:04:10.280 or follow the same path. 01:04:11.500 --> 01:04:17.280 And at a node, still they have to decide if they get information from 01:04:17.280 --> 01:04:22.980 there, they have to be able to select the appropriate outgoing link, 01:04:24.480 --> 01:04:36.000 and here for ATM, the datagrams are very small, just 53 bytes, very 01:04:36.000 --> 01:04:41.340 small packets, and you have a 5 bytes header plus 48 bytes data. 01:04:42.100 --> 01:04:46.580 And in these 5 bytes header, all the information is included that 01:04:46.580 --> 01:04:54.220 controls the selecting of outgoing channels for incoming packets. 01:04:56.300 --> 01:05:01.940 So, again, I don't tell you how that header in this case is specified, 01:05:01.940 --> 01:05:08.680 but this is just a small header because you don't need to provide as 01:05:08.680 --> 01:05:14.100 much information as we needed to provide with TCP-IP, because you have 01:05:14.100 --> 01:05:14.980 a virtual channel. 01:05:15.780 --> 01:05:21.960 All this dynamic freedom that you had in TCP-IP is not available for 01:05:21.960 --> 01:05:22.280 ATM. 01:05:22.880 --> 01:05:24.960 You have a virtual channel which has to be supported. 01:05:25.960 --> 01:05:33.200 And then, you have something which is also a very important 01:05:33.200 --> 01:05:33.860 difference. 01:05:34.460 --> 01:05:35.660 You have service classes. 01:05:36.600 --> 01:05:41.280 You establish a virtual channel when you build up a connection between 01:05:41.280 --> 01:05:47.340 server and destination, you have to negotiate that connection, and you 01:05:47.340 --> 01:05:53.120 establish a certain quality, and the initiator of a connection 01:05:53.120 --> 01:05:56.080 requests for a certain service class. 01:05:57.840 --> 01:06:02.700 And the best service class certainly would be to have a constant 01:06:02.700 --> 01:06:03.160 bitrate. 01:06:03.600 --> 01:06:08.520 You want to have a connection where you have a constant bitrate. 01:06:08.520 --> 01:06:11.940 That's your constant bitrate that you want to have, a very stable 01:06:11.940 --> 01:06:17.680 connection, perfect for audio-visual communication, because then you 01:06:17.680 --> 01:06:19.500 have a stable bitrate, stable quality. 01:06:21.380 --> 01:06:29.300 But it means that there's no influence of certain changes in the 01:06:29.300 --> 01:06:32.880 workload of nodes and things like that, which might influence the 01:06:32.880 --> 01:06:37.620 bitrate that can be supported. 01:06:37.620 --> 01:06:40.680 You must guarantee that constant bitrate. 01:06:42.040 --> 01:06:46.920 And then, there's something which is called real-time virtual variable 01:06:46.920 --> 01:06:47.380 bitrate. 01:06:47.520 --> 01:06:55.100 So you might say, okay, I allow for certain variations, but only 01:06:55.100 --> 01:07:02.460 within a certain bandwidth or a certain range. 01:07:03.280 --> 01:07:08.920 And you have here certain real-time requirements that you state that 01:07:08.920 --> 01:07:15.280 these deviations, this variability, must not be too large. 01:07:15.740 --> 01:07:21.160 You have to satisfy certain real-time requirements for the 01:07:21.160 --> 01:07:22.480 transmission of packets. 01:07:23.280 --> 01:07:25.300 Important for videoconferencing. 01:07:25.960 --> 01:07:31.800 So in the early times of videoconferencing or when we made experiments 01:07:31.800 --> 01:07:38.900 with telelecturing, we had talks in our seminar, in our colloquium 01:07:38.900 --> 01:07:44.320 here at Karlsruhe, and it was looked at at Heidelberg and Freiburg, 01:07:44.460 --> 01:07:48.840 and also a colloquium at Heidelberg, and we looked at it here at 01:07:48.840 --> 01:07:50.540 Karlsruhe and at Freiburg. 01:07:50.540 --> 01:07:59.040 And there were always desynchronized video and audio transmittance, so 01:07:59.040 --> 01:08:04.680 the bitrates for that were not really working correctly, and it was 01:08:04.680 --> 01:08:10.700 just awful, because it just was not synchronized adequately, because 01:08:10.700 --> 01:08:13.000 there was no constant bitrate. 01:08:14.000 --> 01:08:23.140 And then the next lower requirement would be non-real-time, still 01:08:23.140 --> 01:08:24.080 variable bitrate. 01:08:24.800 --> 01:08:26.640 And then you have available bitrate. 01:08:27.000 --> 01:08:32.240 It means whenever there are bits available, if the connection, like 01:08:32.240 --> 01:08:36.420 there are many communications going on simultaneously on a certain 01:08:36.420 --> 01:08:43.140 channel, and when you say available bitrate, you only get what the 01:08:43.140 --> 01:08:44.800 others left to you. 01:08:47.160 --> 01:08:52.760 And unspecified bitrate means that, well, you get communication 01:08:52.760 --> 01:08:57.740 whenever the server or the router say, now I can serve that request. 01:08:58.380 --> 01:09:02.340 So this certainly has the lowest cost, that's the highest cost. 01:09:03.120 --> 01:09:08.760 And this is important if you rely on a certain communication quality. 01:09:09.640 --> 01:09:14.460 And this is something which is not included in TCPIP, but in ATM. 01:09:14.940 --> 01:09:20.940 And ATM actually provided, at the time when it was designed, quite a 01:09:20.940 --> 01:09:22.340 high transmission rate. 01:09:22.840 --> 01:09:29.660 So it was something up to 600 megabit per second, which is, nowadays, 01:09:30.700 --> 01:09:32.620 not of interest anymore. 01:09:33.240 --> 01:09:38.200 But at the time when it was designed, it was very fast. 01:09:39.240 --> 01:09:44.820 And it was seen as a possibility for high-definition television, video 01:09:44.820 --> 01:09:46.740 on demand, audio on demand, and so on. 01:09:47.600 --> 01:09:55.480 Meanwhile, we are having gigabit technology, and for that, ATM does 01:09:55.480 --> 01:09:56.320 not work anymore. 01:09:56.840 --> 01:10:02.200 Because you have these very small bits, these very small packets, it's 01:10:02.200 --> 01:10:05.840 not really working adequately anymore. 01:10:06.060 --> 01:10:08.360 And so ATM, in some way, disappeared. 01:10:08.980 --> 01:10:16.040 But I still think it is adequate to mention this type of protocol, in 01:10:16.040 --> 01:10:20.400 particular because we have this notion, which is not available in the 01:10:20.400 --> 01:10:24.260 other protocols, but certainly you can now try to establish that on 01:10:24.260 --> 01:10:28.320 top of TCPIP, establish certain service classes. 01:10:29.320 --> 01:10:32.900 And this is, for example, important if you run, for example, services 01:10:32.900 --> 01:10:34.520 over a cloud. 01:10:35.820 --> 01:10:40.540 And you have to provide certain service level, make a service level 01:10:40.540 --> 01:10:44.640 agreement on a certain quality of the communication with the cloud 01:10:44.640 --> 01:10:46.540 storage or cloud applications. 01:10:47.240 --> 01:10:50.680 And for that, you need something like that service level that you have 01:10:50.680 --> 01:10:51.140 to guarantee. 01:10:51.840 --> 01:10:55.460 And this is something which was put into ATM when it was designed 01:10:55.460 --> 01:10:56.160 originally. 01:10:57.040 --> 01:11:01.380 Okay, and this is the end of this chapter. 01:11:02.120 --> 01:11:06.860 It was quite a bit, or it took us quite a bit of time, but it is 01:11:06.860 --> 01:11:09.420 essential to look at how the Internet actually operates. 01:11:11.200 --> 01:11:16.420 And after this, we will look into the next... 01:11:19.220 --> 01:11:26.860 Oops, I have to look at the next chapter, which actually yesterday I 01:11:26.860 --> 01:11:27.260 noticed... 01:11:27.260 --> 01:11:31.480 Oops, I have not provided that, but last night I put it into the 01:11:31.480 --> 01:11:31.880 store. 01:11:32.620 --> 01:11:36.280 And so it is available... Oops, did not want to go there. 01:11:36.280 --> 01:11:37.680 It is available now. 01:11:38.580 --> 01:11:43.400 And we will look at now applications on the Internet, which are 01:11:43.400 --> 01:11:44.680 essential for us meanwhile. 01:11:44.840 --> 01:11:48.960 If we look at how actually, what kind of algorithms we need to 01:11:48.960 --> 01:11:50.580 actually provide those applications. 01:11:50.820 --> 01:11:54.200 So searching for information, meanwhile, is one of the major 01:11:54.200 --> 01:11:55.960 applications of the Internet. 01:11:56.980 --> 01:11:58.800 And so we have to look at that. 01:12:01.180 --> 01:12:05.060 There are much more than 300 million web searches per day. 01:12:05.060 --> 01:12:07.320 They have to be supported adequately. 01:12:08.560 --> 01:12:14.440 It means you look for information in files, in data, which is stored 01:12:14.440 --> 01:12:20.400 somewhere on the world, on one of those servers, and you want to get 01:12:20.400 --> 01:12:21.420 that information. 01:12:21.600 --> 01:12:27.560 You send out a query, and it takes just almost no time to get the 01:12:27.560 --> 01:12:28.060 response. 01:12:29.140 --> 01:12:34.840 So you get the impression as if they would look into the current 01:12:34.840 --> 01:12:39.580 contents of all those data files and provide you with information on 01:12:39.580 --> 01:12:43.340 what is in all those servers stored currently. 01:12:43.840 --> 01:12:47.600 It is one of the most popular applications of the Internet, based on 01:12:47.600 --> 01:12:48.800 the World Wide Web technology. 01:12:49.800 --> 01:12:53.360 And what we need for that is certainly search engines. 01:12:53.360 --> 01:12:58.220 And there have been many search engines which had been designed 01:12:58.220 --> 01:12:58.780 initially. 01:12:59.940 --> 01:13:04.820 You know that most of us, meanwhile, use Google or maybe Bing. 01:13:05.240 --> 01:13:08.940 But there are alternatives, quite a few interesting alternatives. 01:13:11.740 --> 01:13:13.820 But Google performs quite well. 01:13:14.900 --> 01:13:18.220 And there are others who also perform quite well. 01:13:18.220 --> 01:13:22.000 And I will tell you things about how those search engines actually 01:13:22.000 --> 01:13:27.140 operate, and what actually the properties are that we should be 01:13:27.140 --> 01:13:32.580 interested in, and what kind of search engines actually are available, 01:13:33.060 --> 01:13:37.220 and what you could use, and why you should use certain things. 01:13:37.820 --> 01:13:43.780 So what we have to look at is something which is an old discipline 01:13:43.780 --> 01:13:46.340 called information retrieval. 01:13:46.340 --> 01:13:47.280 This is not new. 01:13:47.440 --> 01:13:51.760 This has been there a long time before you actually had the Internet 01:13:51.760 --> 01:13:52.780 and the World Wide Web. 01:13:54.120 --> 01:13:57.640 It means to do pattern matching in textual documents. 01:13:59.420 --> 01:14:01.440 You want to construct an index. 01:14:01.840 --> 01:14:02.720 What is an index? 01:14:03.000 --> 01:14:04.220 You know what an index is. 01:14:04.280 --> 01:14:04.900 You have a book. 01:14:06.840 --> 01:14:15.380 And then a book, let me say here, you have many, or a large content of 01:14:15.380 --> 01:14:16.920 that book, a very long file. 01:14:17.940 --> 01:14:22.660 And then you want to look at certain relevant information, and you 01:14:22.660 --> 01:14:23.360 have an index. 01:14:24.040 --> 01:14:27.680 And this index is, like if you have a book, at the end you have an 01:14:27.680 --> 01:14:31.780 index, and it shows you a list of the essential components, the 01:14:31.780 --> 01:14:37.420 essential words, and points you to the locations in that book where 01:14:37.420 --> 01:14:39.420 all these words actually occur. 01:14:39.500 --> 01:14:42.980 Maybe at several locations, that's an index. 01:14:43.900 --> 01:14:49.380 It tells you where you find certain information in some document. 01:14:51.620 --> 01:14:57.040 Now what do we do when we ask, or when we send a query to a search 01:14:57.040 --> 01:14:57.440 engine? 01:14:58.190 --> 01:15:03.500 We ask for the occurrence of a certain word in a document. 01:15:04.980 --> 01:15:06.260 For that we need an index. 01:15:07.380 --> 01:15:10.140 So search engines have to build up an index, and that's what 01:15:10.140 --> 01:15:11.700 information retrieval is about. 01:15:12.240 --> 01:15:16.360 You are looking for certain information, and you get a data structure 01:15:16.360 --> 01:15:20.380 which tells you where you actually find that information. 01:15:21.260 --> 01:15:25.700 So the search engines will not look into all the documents when they 01:15:25.700 --> 01:15:30.200 answer your queries, but they look into their index and provide you 01:15:30.200 --> 01:15:36.360 with links to those documents where actually it's not just for one 01:15:36.360 --> 01:15:37.880 document, but for many documents. 01:15:38.520 --> 01:15:44.140 So it gives you links to all the documents that actually contain the 01:15:44.140 --> 01:15:45.800 words that you are looking for. 01:15:45.920 --> 01:15:50.340 So you have an index providing you with links to all those documents 01:15:50.340 --> 01:15:54.320 where relevant content with respect to your query actually is 01:15:54.320 --> 01:15:54.700 available. 01:15:56.000 --> 01:16:02.320 So what you also have to do is usually you formulate a query to a 01:16:02.320 --> 01:16:05.380 search engine or for information retrieval. 01:16:06.560 --> 01:16:08.160 You have to analyze that query. 01:16:08.860 --> 01:16:11.640 What actually does the user look for? 01:16:12.140 --> 01:16:13.300 What is specified there? 01:16:13.920 --> 01:16:15.920 There is a certain syntax that is necessary. 01:16:16.340 --> 01:16:17.220 We will look at that. 01:16:17.870 --> 01:16:23.440 And you have to measure the relevance of retrieved documents. 01:16:24.840 --> 01:16:33.980 The quality, the relevance, so maybe you look for a certain page, 01:16:34.780 --> 01:16:41.240 let's say for Java, and you get information on programming languages 01:16:41.240 --> 01:16:47.020 and also on coffee from Java, from the island of Java. 01:16:48.300 --> 01:16:51.000 So some are relevant, some are not relevant. 01:16:51.000 --> 01:16:52.960 How do you determine what is actually relevant? 01:16:54.280 --> 01:16:58.900 And maybe somebody just, like if you look for, there are many examples 01:16:58.900 --> 01:17:05.420 that people put into their documents certain frequent search words and 01:17:05.420 --> 01:17:12.360 that way they direct the responses to their webpage even if there is 01:17:12.360 --> 01:17:16.220 nothing relevant with respect to the query in that document. 01:17:16.520 --> 01:17:24.200 But you get attention of some people on your website and so this is a 01:17:24.200 --> 01:17:25.820 side effect that you would like to get. 01:17:27.840 --> 01:17:30.180 And we have many search engines available. 01:17:30.180 --> 01:17:36.080 There is one service or one really interesting website which is called 01:17:36.080 --> 01:17:40.940 Search Engine Watch and I want to just briefly go into that or show 01:17:40.940 --> 01:17:41.840 you that website. 01:17:43.080 --> 01:17:48.840 This is Search Engine Watch it is called. 01:17:49.600 --> 01:17:53.740 And this is providing you with information, up-to-date information 01:17:53.740 --> 01:18:00.260 about the current search engine technology, what kind of algorithms 01:18:00.260 --> 01:18:11.140 are used in search engines and what kind of strategies you could 01:18:11.140 --> 01:18:13.980 follow in search engine optimization. 01:18:14.800 --> 01:18:16.440 What is search engine optimization? 01:18:16.800 --> 01:18:21.840 Search engine optimization does not mean that you want to optimize a 01:18:21.840 --> 01:18:22.460 search engine. 01:18:22.460 --> 01:18:27.180 But search engine optimization is addressing the topic that you are 01:18:27.180 --> 01:18:32.620 designing a website and you want to optimize your website such that 01:18:32.620 --> 01:18:40.660 you have the best possible response or the best possible number of 01:18:40.660 --> 01:18:42.300 requests for your website. 01:18:42.300 --> 01:18:48.540 So search engine optimization means how can I actually make sure that 01:18:48.540 --> 01:18:51.840 my website gets the most possible attention. 01:18:53.600 --> 01:18:55.220 That is search engine optimization. 01:18:56.100 --> 01:18:58.460 And there are many ways how you can do that. 01:18:58.900 --> 01:19:02.460 Some are inadequate, unjustified, that is spamming. 01:19:03.220 --> 01:19:08.040 Some are very adequate and you always have to do something where it is 01:19:08.040 --> 01:19:10.340 adequate and to get the top rates. 01:19:10.340 --> 01:19:14.940 Because if you are responsible for designing the website of your 01:19:14.940 --> 01:19:20.360 company, you must make sure that your company gets the most attention. 01:19:20.840 --> 01:19:22.140 But it has to be justified. 01:19:22.860 --> 01:19:27.280 And if you do a bad job, you might have nice products, but nobody sees 01:19:27.280 --> 01:19:27.500 them. 01:19:29.380 --> 01:19:35.520 And so if you look at certain or if you perform a query, look at the 01:19:35.520 --> 01:19:41.560 responses, you notice that some companies or institutes or so always 01:19:41.560 --> 01:19:44.400 get top ranks in those listings. 01:19:44.720 --> 01:19:50.200 You want to be among the top 10 on the first page of responses to a 01:19:50.200 --> 01:19:53.060 query for the relevant queries. 01:19:53.600 --> 01:19:55.460 If you achieve that, that's perfect. 01:19:56.080 --> 01:20:02.680 If you are at position 100 or something, nobody will see that. 01:20:03.600 --> 01:20:05.060 So that's what you have to make sure. 01:20:05.060 --> 01:20:09.800 And here on this website, you get all kinds of information how to do 01:20:09.800 --> 01:20:10.160 that. 01:20:10.920 --> 01:20:13.340 You also get information on how they actually work. 01:20:13.700 --> 01:20:15.740 You get information like search engine math. 01:20:15.900 --> 01:20:16.960 What is search engine math? 01:20:17.100 --> 01:20:27.200 Search engine math is some information on how to actually use or how 01:20:27.200 --> 01:20:28.480 to specify queries. 01:20:28.480 --> 01:20:31.160 You can use the plus symbol. 01:20:31.520 --> 01:20:33.900 You can use the product symbol. 01:20:34.380 --> 01:20:38.680 You can use other symbols so it looks like mathematical expressions. 01:20:39.340 --> 01:20:44.520 And this is just a website or a page there where they tell you what is 01:20:44.520 --> 01:20:47.580 the best way to actually formulate a query. 01:20:48.160 --> 01:20:49.900 This is another point of optimization. 01:20:50.560 --> 01:20:54.560 How can I phrase my queries such that I get the best response? 01:20:55.820 --> 01:20:56.800 How do I do that? 01:20:57.780 --> 01:21:00.840 And so this is also an essential point. 01:21:01.080 --> 01:21:02.540 And you get information on that. 01:21:02.820 --> 01:21:05.600 And then you get here all kinds of analytics. 01:21:09.080 --> 01:21:15.540 So a lot of information and always current news on those topics. 01:21:16.020 --> 01:21:19.120 So it is interesting to look at that website. 01:21:19.320 --> 01:21:21.720 Just wanted to give you that link. 01:21:22.500 --> 01:21:28.680 And let me go back to the slides. 01:21:28.820 --> 01:21:30.240 Just a little bit more about that. 01:21:30.340 --> 01:21:32.100 So that's what I told you about. 01:21:32.540 --> 01:21:36.280 So there's all kinds of search engine facts and so on. 01:21:36.840 --> 01:21:42.000 Like what are the most frequent words looked for and things like that. 01:21:42.060 --> 01:21:45.560 All kinds of statistics about the use of search engines. 01:21:47.700 --> 01:21:51.200 Okay, we have to look into search engine technology. 01:21:51.420 --> 01:21:54.800 And for that we have to look at what a search engine actually is 01:21:54.800 --> 01:21:55.240 about. 01:21:55.880 --> 01:22:01.820 So a search engine is visiting the websites on the internet. 01:22:02.840 --> 01:22:07.940 And wants to get information on what is actually stored there on those 01:22:07.940 --> 01:22:08.520 websites. 01:22:08.800 --> 01:22:10.240 Those web server sites. 01:22:10.760 --> 01:22:13.840 Then it produces a catalog of the web pages. 01:22:13.840 --> 01:22:16.640 And these catalogs are created automatically. 01:22:17.860 --> 01:22:19.200 Updated constantly. 01:22:19.660 --> 01:22:20.860 This is an automated process. 01:22:21.500 --> 01:22:25.160 There's no necessary human interference. 01:22:26.020 --> 01:22:27.360 And then we have directories. 01:22:28.380 --> 01:22:33.900 In the directory you have a created catalog or manually created 01:22:33.900 --> 01:22:34.980 catalog of web pages. 01:22:35.200 --> 01:22:40.000 So there you have a certain catalog where you have a structured 01:22:40.000 --> 01:22:49.280 information on maybe certain topics like information on cars, on 01:22:49.280 --> 01:22:54.420 bookstores, on travel agents. 01:22:54.560 --> 01:22:56.300 So it is categorized information. 01:22:57.320 --> 01:23:01.940 And you have an ordered approach or an ordered entry into the world of 01:23:01.940 --> 01:23:03.200 the World Wide Web. 01:23:03.900 --> 01:23:05.580 So that's a directory. 01:23:06.000 --> 01:23:08.180 And there the sites must be submitted. 01:23:09.120 --> 01:23:11.740 And they are looked at. 01:23:12.220 --> 01:23:13.320 They are quality assured. 01:23:13.920 --> 01:23:19.340 And then you get actually they are entered in that directory. 01:23:19.800 --> 01:23:21.780 And then you are visible. 01:23:23.780 --> 01:23:27.920 And so directories can provide better results than search engines. 01:23:28.260 --> 01:23:33.140 Yahoo was one of the first ones who provided actually quality assured 01:23:33.140 --> 01:23:33.620 content. 01:23:34.350 --> 01:23:39.920 And it does not mean that they are successful on the long run. 01:23:40.660 --> 01:23:46.820 Sometimes those who provide unqualified information get better 01:23:46.820 --> 01:23:49.340 results, like are better on the market. 01:23:49.860 --> 01:23:54.200 But directories are quality assured content. 01:23:54.740 --> 01:23:57.520 And then you have hybrid search engines where you have a search engine 01:23:57.520 --> 01:23:58.400 plus a directory. 01:23:58.400 --> 01:24:06.220 So you can provide quality controlled information plus search engine 01:24:06.220 --> 01:24:07.140 based information. 01:24:07.740 --> 01:24:11.520 And then you get this kind of hybrid search engine. 01:24:12.160 --> 01:24:16.240 And next time I will tell you more about how search engines actually 01:24:16.240 --> 01:24:16.580 work. 01:24:16.880 --> 01:24:17.900 Okay, that's it for today. 01:24:18.000 --> 01:24:19.040 Thank you very much for your attention.