So, good morning.
Welcome to another session of Algorithms for Internet Applications.
I was here in time today, but the data projector didn't work, so it
took some time to actually get everything started.
Now it should be okay.
I hope that you can see sufficient things on the screen.
Okay, I have to change something here...
in order to be able to... yeah, this has to be changed.
And then we are done.
So, we have looked at internet technology for a few lectures now
already.
So, we've looked at quite a few things.
I've told you something about routing protocols last time, about...
after we had looked at Dijkstra, we had looked at flooding.
I've shown you something on distance vector routing, which is one of
the earliest routing algorithms in the internet.
And as you have seen there, what we do is that we have this table, or
these tables that are received from the direct neighbors, and then
from the information from the tables, the best information is used.
So, the tables are updated according to the distances to the direct
neighbors, and then you always go for the shortest or for the best
information that you see from your neighbors.
And we had seen that this can lead to problems because bad news, like
bad information, does not spread, is not adopted.
Only the good information is adopted.
And as long as the neighbors are assuming that there are better paths
available, then you always go for those assumptions of your neighbors
and don't consider the bad information that might be there also.
And we had seen that at this simple example.
You will have possibilities to look at that in the tutorials also.
Then we looked at link state routing, where we have the different
approach where we compute the link state packets, like the information
that every node has about its direct neighbors.
And this information is not exchanged only with the direct neighbors,
but it's flooded to all the nodes in the system.
And in that way you get information about all the connections in the
graph that you are living in.
And in that way you get a complete view of the system.
And you can actually then get your local view, you have your adjacency
matrix, the connectivity of the network, and you can compute shortest
paths based on that local information that you have.
Your local view is based on the measured costs of communicating
between a node and the direct neighbors.
And so this is much more accurate than what we had in the distance
vector routing.
And here the counter-infinity problem is no longer there.
But the disadvantage is that you have quite a large overhead because
of all these link state packets that have to be sent around.
You always want to get the newest information, and so regularly you
get updated information from all the nodes.
Then we briefly looked at hierarchical routing.
You want to reduce the size of your routing tables, and so you look at
connectivity to networks and not to all the nodes inside those
networks.
And so that was what we looked at.
And after that we looked at the problems that we have with IP, that
there is a shortage of addresses, and there are a few more points that
were not really satisfying or not satisfactory with the old protocols.
So IP version 6 was introduced quite some time ago, like around 15
years or so.
But it took really some time before that actually got spreaded over
the network.
And I showed you the addressing format with 128-bit addresses, which
is an abundance of addresses, and they are used in a reasonable way.
There are all kinds of rules how to use those addresses.
They are separated into different regions and so on.
You should look that up in the protocols if you really have to use IP
version 6.
The important information is that there are certain rules how to use
that.
I have given you some examples so you know how to read those
addresses.
And if you need a specific information on an address, you always have
to go into the protocols and look it up.
But you know how they are actually built and what it means if you
have, for example, some address and a slash and a number, it means
that the relevant information is the prefix of that size.
That was what we looked at for the addressing format.
Then we looked at the header format, which is a fixed header of these
20 bytes here.
No, sorry, it's a 40-byte header.
And it consists of a bit fewer information than we had before.
In particular, the option field is missing here, but this is replaced
with extension headers, which are following or potentially following
this initial IP header.
And the major part of that header certainly is the two addresses,
source address and destination address.
Then I told you something about the extension headers for different
purposes, for routing, fragmentation, and so on.
A particular point is that you can have something like loose routing
implemented using, for example, the routing extension header, where
you have a stack of addresses that you have to go to in sequence.
And in the initial header, you always have the next router that you
have to go to or the next destination that you have to go to.
And then you can look for the next hop or the next further away
destination in that routing header, which has to be indicated using
this next header information, because there you have the information
about which type of next header actually has to be looked at.
And then while we talk a little bit about that, that has been delayed.
And then I showed you something about TCP.
We looked briefly at properties.
I started to tell you something about the header format.
And that was the last slide of the last lecture.
So we have to... I should go into that again.
That is the header format, the TCP header that we have.
And there, essential information is about the ports that are
connected.
So you build up with TCP a logical connection between ports, or you
should say between applications on the layer above TCP, which is
actually or which are sending or the application above the TCP on the
source side is sending data.
And so it wants to communicate with another application on the
destination side.
And so you need the ports to be able to actually communicate using the
appropriate services.
And I told you that there are some special services like the well
-known ports having numbers less than 1023.
And so there's a list of all those services that we have.
Then we have registered ports, which are for specific application
programs registered.
And after that, you have the freely available ports that you can use
for socket programming, if you want to use additional ports for some
additional applications.
So there is this list of all the assignments of ports to services in
that URL.
Last time we briefly looked at that website.
So that was why we need those ports.
And then we have something again like a sequence number.
And that's just telling again, well, we know that all bytes of a
message are numbered.
And here, what we have is the sequence or the number of the first data
byte within this datagram.
Now, why do we need this sequence number?
I said that we only put in the information that is essential for the
receiving side to actually adequately deal with the data payload.
Why do they need the sequence number?
You have this very long file that you want to send, and you have
chopped that into segments.
And now you certainly have to know when you receive a TCP packet, you
have to know what is the location where I have to put that segment in
order to reconstruct the old data.
So you need the sequence numbers, the bytes are all numbered.
And you always tell what is the first byte of this message, like the
payload comes after that TCP header.
And so you have to know what that byte actually is.
Then you find the appropriate position.
The next is an acknowledgment number.
I said that TCP is responsible actually for reliability.
That means TCP has to make sure that all the packets are adequately
received.
So the source node has to get information about successful receipt of
datagrams that have been sent out.
And for that we need the acknowledgment number.
The acknowledgment number is put in by the destination side on receipt
of a datagram.
And so they have to put in, they have to acknowledge that they got
certain bytes.
And what they acknowledge is a number X plus one.
And it acknowledges the correct receipt of all bytes up to number X.
Or you could phrase it differently.
What they put in there in the acknowledgment field is the first or the
number of the first byte that they have not received so far.
And now one problem is that the data packets might not be received in
the same order as they are sent out.
And so they will always only, like this X plus one I said, it
acknowledges the correct receipt of all bytes up to number X.
So if this part here has been received, then it will be the number of
the next byte that is expected to be there.
And even if further bytes have already been received, if there is some
hole in there, some part that has not been received so far, the
acknowledgment will only be for that part that has been completely
received.
So X plus one is always the address of the first, I could say, free
spot or the first byte that did not arrive at the destination so far,
regardless of what has been received, like what packets have been
received after that.
So only if this is also received, then the next byte that would be
acknowledged or that would be sent is again the number of the next
byte that has not been received so far.
And then the other packet that had been received before is also
acknowledged.
So the acknowledgment number is the essential information that the
source site needs in order to provide reliability.
And if the source site notices, oh, this packet that I have sent out
has not been received, after some time, they have to resend that.
And they have to resend everything starting from that field where they
did not get all the bytes.
So they might even resend certain segments that had been sent before,
which might have arrived already, but there's still one segment
missing, and so everything from that position on has to be resend.
That's the way TCP works.
And now we have more fields there.
So sequence number, acknowledgment number are essential to be able to
actually provide reliability of communication.
Without that, it wouldn't be possible.
IP did only take care of sending messages on to the next hop.
They didn't care about receipt of packets at the destination.
And then we certainly have to know something about the length of the
header, since the length is dynamic.
Here you see already there's an option field there, so there may be
some variable sizes.
So the header length has to be specified, otherwise the receiving side
would not know where actually the data payload begins.
So header length is there, you see it's number of words in the header,
at least five.
And so this is just showing where the data payload actually begins.
And then we have certain flags here.
Here, there are certain flags.
So here's some region which is reserved for whatever purpose, not of
interest here.
But then there is a number of flags, one-bit flags, which can be set.
Now I have to tell you something about those flags.
The urgent bit is telling that the urgent pointer here is pointing to
data which has to be read immediately.
So the receiving side at the destination, the TCP header is analyzed.
And I said, well, first of all, the data stream has to be rebuilt
before the data is forwarded to the application layer.
And so some things have to be done.
Now if the urgent pointer is set, this is a pointer, the urgent
pointer, which is pointing to some data in the data payload which has
to be looked at.
So this is an instruction for the TCP protocol at the receiving side
to do something with specific data.
And which data has to be looked at is shown here with the urgent
pointer.
And the urgent flag is indicating this urgent pointer field is valid.
You have to follow that pointer.
The ACK bit is actually telling whether the acknowledgment field is a
valid field or not.
So only if the acknowledgment field contains a valid value that has
been specifically set by the destination side, this is actually
utilized.
So otherwise, if that is zero, then the acknowledgment number is not
relevant.
And we need that on both sides, by the way.
So this is bidirectional communication between source and destination.
The destination sends packets back to the source with the
acknowledgment fields valid.
And it means that also we have a data stream from the destination to
the source.
And this has also to be acknowledged by the source when it responds to
the packets.
Like when it sends a new packet to the destination of its original
data stream, it also has to specify what is actually the information I
got back from the destination.
So it's a bidirectional communication sending of data.
And on both sides, it needs these acknowledgment numbers.
And the ACK field just tells whether the acknowledgment number is a
valid number or not.
Then you have something which is called a push flag.
And the push flag is also very important because sometimes you
actually must make sure that a datagram is delivered directly to the
application.
I said that normally this information, like we have to build up our
old data stream from the datagrams that TCP received.
And only if it's complete, it is forwarded to the application.
Now there may be some situations, for example, you have an interactive
application.
You're pushing your keys on the keyboard, and then you certainly want
immediate response.
And so in interactive applications, you want that immediately.
There should be a response on the application side.
And so for that, the push bid has to be set.
And then sometimes faults occur.
And so sometimes the reset button or the reset flag has to be set,
meaning that the connection has to be reset, has to be restarted anew
because certain faults have occurred.
Then there is the synchronize flag, which is set in the beginning.
Initially, you have to set up the logical connection.
And for that, you need to specify.
Now we are establishing a new connection.
So we have to follow a certain protocol, the three-way handshake
protocol that is used for TCP, which we will get to know in a moment.
And so that's another flag that has to be set.
And finally, we have the final flag, the FIN flag, which is indicating
that this is actually the last packet that is sent on this connection.
So after that, this logical connection can be closed.
So this is all these flags that we have here.
And now we have another field, which is the window size.
What do we need the window for?
Well, TCP is responsible for reliability.
And that means it must make sure that the communication does not
suffer from communication faults.
So loss of messages and so on.
And the problem is that the more packets you send, the more likely it
is that some packets will be lost because certain nodes are just
overloaded, cannot do their work, and packets are discarded.
And so you have to be able to control the traffic.
Now, there's no central traffic controller, but every sender or every
initiator of a TCP connection is responsible actually for influencing
the traffic.
So you are able to in some way to notice, well, certain faults occur
because packets have not been acknowledged.
If packets don't get acknowledged for some time, probably you have
sent too many packets per time unit.
So you reduce the number of packets.
And so this window size is used for flow control.
It actually means how many packets may I send before I actually wait
or assume that I get an acknowledgment for the first packet that I
have sent.
I will show you that in a moment how that works.
So you have a number of packets that you send out which are traveling
in the network.
And certainly it takes some time, this round-trip time from source to
destination and back from destination to source.
And it would be wasting of the potential of the network if you would
just send one packet out and wait for the acknowledgment and then send
the next packet.
But you send a number of packets before you wait for the
acknowledgment of the first packet that you sent out.
And so if you don't get that, you have to reduce the window size.
If everything is fine, you can increase the window size.
And so you will see in a moment how that works.
That's the window size.
The central parameter for actually the completely self-organized
control of the traffic flow in the Internet.
This is the very essential part why actually the communication in the
Internet is working fine without having a central controller which is
regulating everything.
Every node is taking care of that by looking at the current
reliability of the network which is visible looking at the success of
your transmission of packets.
You see the current situation and you respond to that by adapting the
number of packets you send per time unit.
And then again we have to look for reliability with respect to the
content.
The first thing is to look at are the packets actually received.
The next thing is, is the content still correct?
And for that, you remember in the IP headers, we had a checksum.
In IP version 6, we didn't have a checksum anymore.
And so now we have a checksum here.
Again, the once complement of the 16-bit sum of all 16-bit fields of
the datagram header.
The checksum zero plus data.
And a so-called pseudo header, which I just let pop up here.
The pseudo header is not part of the TCP header, but it's contained in
the IP header.
What is in the IP header which was essential?
That's the source address, the destination address, the protocol
version, and the TCP segment length.
So this is the information that actually is a pseudo header.
This information is forwarded from IP to the TCP layer.
And so this checksum can be computed.
And then, as always, initially, when you compute this, the checksum is
zero.
You take the once complement of that value, put that into that
checksum field here.
And if you now, at the receiving side, make that checksum, if it's not
zero, you know that a fault has occurred.
Some bits have been flipped.
So this is just the typical way you perform checksums.
And so in this way, the receiver can check for correct transmission of
the datagram.
If you have a wrong checksum, then you have to discard the packet.
You will not send an acknowledgement of that datagram.
And then there are options.
And these options are options for, for example, the maximally accepted
segment size.
So every host must accept at least 536 bytes of data.
536 bytes of data means that, well, you have 40 bytes for the TCP
header, at least.
And so it's 576 bytes, which is the minimal size of a datagram, which
is then extended by the IP header and so on.
And so it's maximally 65k bytes, which you can have there in the size.
And this size actually is negotiated between sender and receiver.
So between source and destination.
And it definitely would not make sense to have a very small value
there, because if the data payload is too small, you have too much
overhead for all these administrative information in all the headers
that are there.
And there is also a limit on the size, because if it's very large,
then the probability of faults that might occur, and which lead to
packet dismissal or packet deletion, then is just getting higher.
So you don't want to send too long datagrams, and they should not be
too short.
And then there are certain restrictions because of the buffer sizes of
the nodes in between and so on.
So it depends on what kind of routers were visited when you
established the connection between source and destination, which is
just a logical connection, as you know.
So in this, these initial communication, this length is like this
segment size is negotiated.
And later on, as I told you, maybe that some packets have to go over
paths that do not support that size, and then you get fragmentation.
Fragmentation of the segments into smaller packets, because there are
certain restrictions on some parts of this physical path that actually
is chosen, and TCP only knows about a logical path.
And then you can also set a scaling factor for the window size.
So here you have 16 bits for the window size.
If you scale that, you have larger possibilities to actually have your
window size.
You see that the window may be quite large.
The number of datagrams may get very large, but this is a dynamic
thing.
And then you might also request specific things.
For example, it may be that the receiver sends information that a
specific datagram is missing.
So this is a negative acknowledgement.
It just sends or asks for resending of a specific datagram, and that
would avoid resending everything from a point on where information was
not received by the destination, regardless of what has been received
after that.
So negative acknowledgement is something which can also reduce the
necessary traffic if you can acknowledge or if you can send
information that only a specific datagram out of a stream of datagrams
has to be resend because that had not been received so far.
Or maybe there has been a fault, has been received, and there has been
a fault, so you ask for resending of that specific datagram.
Okay.
So this was just why we need this information.
And I hope you agree that this kind of information is important to
actually be able to deal adequately with the tasks of TCP, providing
reliability, and so forth, and being able to actually forward the data
payload to the appropriate destination application.
So then we have to look at how we actually establish TCP connections.
So how do we do that?
The server always waits for incoming connection requests.
So you send information.
The sender has to execute something which is a connect primitive, and
then you have to put in the IP address of the server, the desired port
for the connection, like your port that you are using on the source
side, or that the application on the source side is using, and the
port for the destination side.
You have to put in the maximally handled segment size on your side of
the source, and maybe some more user data that you might need, which
we just neglect.
Those details can be looked up in the specific protocol
specifications.
The central point is that we have a so-called three-way handshake
protocol.
So it's a handshake protocol.
You always have to agree that you do something, and you shake hands
for that.
So the host 1 and host 2 have to communicate.
And they just send now packets having the sync field set in their
flags, and then you have the time there.
So host 1 will send a datagram with some sequence number.
Now, x is just one value.
It's a 32-bit value.
So you just take one value adequately determined, depending on what
has been sent before, and things like that.
So the sender just selects an arbitrary value there.
And so that is the sequence number x.
And the send field has to be set to 1.
And then host 2 receives that data, that request, hopefully, and will
respond to that.
Now, it will respond with its own sequence number, a sequence number
y, because it also sends data, or the acknowledgement data, maybe some
more information which sometimes has to be sent, some administrative
data which might be important.
And so it sends sequence number y, and it sends x plus 1, because it
has received, or it requests that there should be information.
The next information I get, the next byte, should be numbered with x
plus 1.
And now the host 1, on receiving that, acknowledges the
acknowledgement.
So it tells, okay, it sends a datagram where the acknowledgement field
is set, where the sequence number is x plus 1, and the acknowledgement
number is y plus 1.
And now data actually can be sent.
Host 1 can start sending data.
So it's again sequence number x plus 1, and then you have the data,
and after that it can work in the way I have indicated in a very
superficial way on the previous slides.
So this is the three-way handshake protocol, these three messages that
have to be sent.
And if that works correctly, you have a logical connection, which
actually is characterized by x and y.
Those are the two sequence numbers which actually indicate this is
where the communication starts.
Then you know something about all the data that will be sent, about
the numbering of the bytes, and you can deal with that, you can put in
the information at the appropriate places, and so on.
Okay, now certainly faults can occur.
So when you send a datagram, the timer has started.
There are several timers that are always maintained in order to look
for all kinds of faults that can occur.
And if you have a timeout, if your timer has been decremented to zero,
then you have to do some appropriate action, you have to retransmit
something.
Then there are certain things that can occur.
So maybe the two hosts require or request a connection simultaneously.
It may happen.
Then here, for example, this is sent.
You get an acknowledgment, and host 2 responds to that request, but
before that had sent out its own sync request, and then it
acknowledges sequence y and x plus 1, and now before that is received,
host 1 had received the sync request, and has sent x and acknowledges
y plus 1.
And here, both essentially have established the same connection, so
only one connection represented by x and y actually is established,
and there is no problem with that situation.
It is a call collision in some way, but only one connection gets
established, and they have these same numbers, x and y in this case.
And then maybe that something happens that you have sent out a
synchronization request, and you have established a connection, and
later on you get another synchronization request, which might have
been sent out long before, but for some reason it was delayed
somewhere, and so it's delivered only after that other synchronization
request had been established actually here.
So if you get another packet, another request with the same sequence
number from this host 1, this second one, the late duplicate, which
for some reason was delayed, which led to a resending of the
synchronization request on the host 1 side, is ignored by the host 2.
Okay, this is just an example of what kind of situations can occur.
There are more situations that can occur.
Just wanted to give you an indication that fault handling is very
important, because you must make sure that you have a correct logical
connection.
And if you have established that, then again you might have problems
with controlling the traffic flow.
We will look at that in a moment.
Now, connection closure.
If a host does not intend to send more data, if all the data have been
sent, it puts the final flag on the last datagram, and then the
receiving side notes, now this connection can be closed.
And then the other certainly will send data.
It may still have to respond with certain acknowledgment packets.
It will send out all the necessary acknowledgment packets.
And then it will also send a fine, thin datagram, and then the
connection is ended.
So this is just, you have to be able to connect or to close the
connections.
And just to mention one point, you might have heard about denial of
service attacks.
One of those attacks is to just send very large numbers of
synchronization requests to a host, and then the host is just busy
with responding to those synchronization requests.
And you just don't send anything more, you just send new requests.
And by sending all these new requests, the receiving host has to
respond to that, tries to establish a connection, has to reserve the
connection points X and Y, and so it is overloaded with all these
requests and can no longer support, really, connections which are real
connections.
So this protocol is actually carried out by the server.
As I said, the server is always waiting for incoming synchronization
requests, and then another routine takes over when you have the
communication established between the appropriate ports.
And so this is one point where denial of service attacks actually try
to attack a certain service which is essential for providing
communication.
Now the question is how we can actually send data.
As I said, we have the task to make sure that we have reliable
communication, and so we have this sliding window protocol.
What is the sliding window protocol?
I just visualized that as a sliding window, and it means that this
sliding window indicates that we have a certain number of packets
which are sent, that's the window size, and as I said, we send out X
or K packets, and we always wait for the acknowledgement of the first
packet that has been sent out, like when we send this packet out, but
the acknowledgement for the first packet that had been sent should be
in there.
So as long as the acknowledgements come in at exactly a sufficient
speed, then we'll have that many packets that are sent out all the
time.
So that's the window size.
Now this is not a constant value, this is changing all the time.
So the window size determines how many datagrams we can send, and you
might have noticed that if you look at your transmissions, you can
look at TCP connections, and you can look at the performance of your
computer, and if you perform a file transfer, you see that it looks
like something like this, and then like that, and goes down for some
time.
So this is a curve like that.
And the reason for that is explained in what I tell you now.
So what we... or it will be explained on the next slide, actually.
So the window size, as I said, is dynamically changing.
And this, like here you have the number of bytes that are sent.
So the number of bytes that are sent if you perform a file transfer
depends on the current reliability of the system, or the changing
window size.
So sometimes you have a very small window size, and then you have a
larger window size again, again a smaller window size, a larger window
size, and so on.
And that's why we have this dynamic pattern of the transfer rate if
you send data using TCP IP.
So W is... like the window size is dynamically determined between
sender and receiver, but this is the maximum window size that can be
used.
And as I said, the acknowledgement field always contains the maximum
received sequence number plus one, up to which all bytes have been
received correctly, and the acknowledgement is done in the next
available or reasonable datagram.
So some datagram is sent back from destination to source, and the
acknowledgement field there is always having that value, the last byte
that has been received correctly, plus one.
And if a segment has not been acknowledged in time, everything
starting from that location has to be resent.
So if that byte here is not acknowledged, everything starting from
that has to be resent, although they have been sent out already.
So that's what I mentioned now several times, and there is this
negative acknowledge option which can be used, and then you have
negative acknowledgement and only one datagram is sent again.
And now we come to the dynamic flow control which I just indicated.
So what we don't like is faults.
And so if the window size is too large, you might have losses, and so
the window size could be or should be reduced.
Usually the current window size is just halved to achieve better
transmission rates.
And this is done in the following way.
You don't start with a maximum window size, but you start with a very
small window size.
The first window size is one.
And it means that you have here your, let me say, the window size or
the...
I take the window size.
This is the window size, and you have here, initially you have a
maximum window size.
Maximum window size.
And then you start with one, and then you wait for acknowledgement.
If you get an acknowledgement, you increase the window size to two.
If you get an acknowledgement for, like you send out two datagrams,
and now after you send out the second datagram, you get an
acknowledgement for the first one, you send out four.
So this is increasing exponentially until you get to the maximum
window size.
Or you should not send larger datagrams or use larger window sizes
than that.
But maybe that you even don't get there, because there's a fault.
A fault means you did not receive an acknowledgement for the first
datagram that you had sent out of that window, and so you know this
was too much.
And so you decrease the current value that you have.
So the initial threshold value, T here, is the max window size.
And so if you have a problem there, then you reduce that value.
So you set T to W over two.
The threshold now is, like this is the current value of W, this is
halved, so this will be the new threshold, T.
Then you start again, the slow start.
Exponential increase up to that point in time where you reach that
threshold value, fast increase of the window size.
And then you continue with a slow increase of the window size.
So it's a linear addition.
So you only add one datagram, or maybe two or something is the policy
of the router.
You only linearly increase the window size after you have reached that
threshold value, T.
And then you increase again, and then maybe you have a fault.
And then this, or certainly you never get above that line.
Maybe you have sent something for some time there, and then you have a
fault.
Again, you have to set the threshold value to half the current window
size, and it continues like that.
Maybe you have another failure.
Again, you get down there, and you start again, and so on.
And this is the way the traffic is controlled.
As soon as you have a failure, that means a packet has not been
acknowledged, you reduce the window size.
You start anew with just a window size of one, and you increase the
window size quite quickly up to the point where you reach that
threshold value.
And then you increase slowly, and you never go above the max window
size, but you increase, increase, increase, and then if you have a
fault again, it gets down again.
You get a new threshold value, a new small window size, and you start
again.
So this is the way the communication is controlled.
And that's why we have, if we transmit data, we have something like
this.
If you look at the data speed, or the speed of transmission, or the
number of bytes that are transmitted, the bandwidth that you actually
can use when you transmit a file between two computers.
So here we have a dynamic data flow, and this is something which is
controlled by every router, by every TCP controlling node in the
network.
It is controlling the flow, and so the traffic is adjusted dynamically
in a completely self-organized way.
There's no central controller telling everybody, you all have to
reduce your window sizes.
There's nothing like that.
It's negotiated between the individual components there, and so this
is the ingenious idea of those who invented the ARPANET initially, and
designed TCP IP.
It's amazing that it's still working, that it is so scalable, that it
still works with very large traffic, or network sizes that we have
now.
At the time where it was designed, you had a few hundred nodes in the
network.
Okay, so this is called also congestion control.
So you have slow start plus congestion avoidance.
Congestion avoidance means that as soon as you have some problem,
packets don't get acknowledged, you reduce the traffic, and so you
avoid congestions in the network.
You have reliability of communication.
Now, this is a really perfect property, but it's also a problem of
TCP.
One problem is that this sliding window protocol means that if a
segment is lost, then many segments have to be sent again.
So it may mean that you have retransmission of many segments, and if
you have some dynamic flow of data bytes or of datagrams, as I
indicated in the previous slide, this is very bad for certain
applications.
So slow start may lead to frequent changes in throughput, and if you
have, for example, multimedia applications, this is not what you want.
You want to have a stable bandwidth, a stable transmission capacity,
and it really is not that important if a packet is lost.
You don't really notice that if one packet in an audio transmission is
lost.
There may be a short disturbance there, but you don't really notice
that.
And so it's more important to have a stable data rate than to have
complete reliability of transmission.
And so for transmission of audio signals and for multimedia
applications, usually you move the reliability control into the next
layer.
You don't use TCP for that.
There actually are, or people have designed special protocols to
support audio transmission, but you can also do that on the next
layer.
To move this reliability control on the next layer is the application
layer.
You have to move it into the application, and this forwarding the
reliability to the application layer means that you have to use a
protocol different from TCP and that is UDP, which we will look at in
a moment.
And then this flow control scheme is based on assumptions that are
valid for wire-based communication.
If you have wireless communication, then it may be not actually
reasonable to reduce the number of datagrams you send because it may
be that faults have nothing to do with the number of bytes you send,
but there are certain disturbances in the connection, something in
between, in the air between two locations.
And so that's not really the problem of bandwidth, but there are
certain other disturbances.
And so there, dynamic flow control may lead even to worse transmission
rates.
And if you have wireless communication, maybe that you should actually
retransmit your packets at a higher rate in order to make sure that
some actually get over that wireless communication or wireless
connection.
And so for that, it's not the best possible way to actually use TCP.
So TCP has no idea about what kind of physical connection will be used
later on because TCP is operating on the transport layer and the
physical connection is on the lower levels of the physical data layer.
And so it cannot decide for the most reasonable method of flow
control.
But if you know that something will be sent by wireless communication,
if that information is available, you should go for a different policy
in flow control.
Okay, so there are some problems.
Actually, there are quite a few efforts, quite a few projects in
research to design new protocols for the next layer Internet, the next
level of the Internet, certain ideas how you can actually modify those
protocols to get more efficient communication for all kinds of
properties that are reasonable there.
And I just cannot address those topics in this course.
For that, you have to go into courses on specifically looking at
Internet technology where you can have a complete course just on those
topics.
As you know, I only tell you something about the basic protocols that
we have, the basic algorithms.
This course is not devoted completely to Internet protocols.
But I have to tell you now about the UDP protocol.
UDP is what I just mentioned on explaining the previous slide.
We would like to be able to just ignore the reliability and forward
that task to the application layer.
And for that, we have the user datagram protocol.
It essentially means that the user, the application, should actually
take care of the datagrams and it will not get a complete sequence or
a reconstructed sequence of data as TCP does, but it will just send
datagrams on.
So the IP service just gets extended to the application layer.
It provides a connectionless, unreliable transport service.
And this is exactly the properties that IP also looked at.
So IP did not care about connections, about reliability.
UDP also does not establish a logical connection.
It just sends out packets and hopes that they will be received
sometime.
It doesn't care about that.
The application layer has to care about that.
Nevertheless, the UDP's header certainly has to provide the
information that is necessary to actually make sure that, again,
sender and destination, that they can communicate in the right way.
That means that they don't establish a logical connection, but you
have to know which ports actually are essential.
So if a datagram is sent out here, it has to be put to the right port
and then forwarded to the right application.
So you need source port and destination port as we needed that in the
TCP header.
That's for addressing the adequate application.
And you also have to tell about the length.
So the length is the total length of the datagram header plus data.
Here, the header always has the same size.
So it's 8 bytes in this case.
Very short header.
And then the length is the total length of the datagram header plus
data.
The checksum is the same as before.
For TCP also, the pseudo-header is included, the source address,
destination address, and this administrative information that I showed
you when I showed you the TCP header.
So UDP is mainly used to grant application programs direct access to
the IP layer, and then they have to deal with unreliability, with
traffic control, and so on.
So UDP is just sending out information at a certain rate, and it
doesn't care about flow control.
And so this is just very briefly a UDP.
There are more details that are of interest, like how many datagrams
per second are actually sent from UDP and things like that.
I don't go into the details there.
And I wanted to briefly mention also this other protocol I had in the
list there a few times.
A stream control transmission protocol, and that's an alternative to
TCP, which is just like I just copied the properties from the
description of SETP and the appropriate RSC here, 4960.
And so again, it is providing reliability, error-free, non-duplicated
transfer of user data, so that you have checksums in there and things
like that.
And it is acknowledged, so your reliability is taken care of, data
fragmentation is dealt with appropriately, like the maximum transport
unit size is the maximum segment size that you have there, or as I
said, sometimes you have these smaller packet sizes, and then the
fragments have to be reassembled into the original segment sizes and
into the original data stream.
And then you have something which TCP does not take care of.
Here you have a sequence delivery of user messages within multiple
streams, and you have an option for order of arrival delivery of
individual user messages.
This is something which TCP is not necessarily the case.
It does not take care about order of, like normally you have this...
TCP, as I said, has a sequence, like TCP had this sequence of
segments, and will always provide the data in the same order as it had
been sent out.
And if something is missing, it's not sent out.
And here you have an order of arrival option, that means if they come
in in a different order, the datagrams will be forwarded to the next
layer in the order of arrival, and not necessarily in the order they
have been sent.
And you can bundle multiple user messages into one SETP packet, so
there are certain options that go beyond what TCP actually is doing.
And I don't go into the details, I just wanted to mention that there
is another protocol, which is also available there, and as I mentioned
also, there are these protocols, like ICMP and so on, on the network
layer, which I also didn't specify here in details.
I cannot give here a course on internet technologies in depth, I just
wanted to mention the major protocols in depth, which was TCP and IP.
And then I briefly want to mention one alternative approach to
controlling communication, and that, like ATM, was developed quite
some time ago, but it was later than TCP-IP, and it addressed a
different way of actually controlling the traffic.
ATM, asynchronous transfer mode, actually would do if you have a
network, and you have here your source and destination, then you would
have a fixed path through that network to get from source to this
destination.
And all the packets would follow exactly that path, so you have a so
-called virtual channel.
And if all the packets are following the same path, then you don't
need what we had with TCP-IP, where at every node we had to look for
the best possible next hop to actually get on the shortest path to the
destination, according to the current situation in the network.
ATM says, okay, I just sent a stream of packets, and they will all go
or follow the same path.
And at a node, still they have to decide if they get information from
there, they have to be able to select the appropriate outgoing link,
and here for ATM, the datagrams are very small, just 53 bytes, very
small packets, and you have a 5 bytes header plus 48 bytes data.
And in these 5 bytes header, all the information is included that
controls the selecting of outgoing channels for incoming packets.
So, again, I don't tell you how that header in this case is specified,
but this is just a small header because you don't need to provide as
much information as we needed to provide with TCP-IP, because you have
a virtual channel.
All this dynamic freedom that you had in TCP-IP is not available for
ATM.
You have a virtual channel which has to be supported.
And then, you have something which is also a very important
difference.
You have service classes.
You establish a virtual channel when you build up a connection between
server and destination, you have to negotiate that connection, and you
establish a certain quality, and the initiator of a connection
requests for a certain service class.
And the best service class certainly would be to have a constant
bitrate.
You want to have a connection where you have a constant bitrate.
That's your constant bitrate that you want to have, a very stable
connection, perfect for audio-visual communication, because then you
have a stable bitrate, stable quality.
But it means that there's no influence of certain changes in the
workload of nodes and things like that, which might influence the
bitrate that can be supported.
You must guarantee that constant bitrate.
And then, there's something which is called real-time virtual variable
bitrate.
So you might say, okay, I allow for certain variations, but only
within a certain bandwidth or a certain range.
And you have here certain real-time requirements that you state that
these deviations, this variability, must not be too large.
You have to satisfy certain real-time requirements for the
transmission of packets.
Important for videoconferencing.
So in the early times of videoconferencing or when we made experiments
with telelecturing, we had talks in our seminar, in our colloquium
here at Karlsruhe, and it was looked at at Heidelberg and Freiburg,
and also a colloquium at Heidelberg, and we looked at it here at
Karlsruhe and at Freiburg.
And there were always desynchronized video and audio transmittance, so
the bitrates for that were not really working correctly, and it was
just awful, because it just was not synchronized adequately, because
there was no constant bitrate.
And then the next lower requirement would be non-real-time, still
variable bitrate.
And then you have available bitrate.
It means whenever there are bits available, if the connection, like
there are many communications going on simultaneously on a certain
channel, and when you say available bitrate, you only get what the
others left to you.
And unspecified bitrate means that, well, you get communication
whenever the server or the router say, now I can serve that request.
So this certainly has the lowest cost, that's the highest cost.
And this is important if you rely on a certain communication quality.
And this is something which is not included in TCPIP, but in ATM.
And ATM actually provided, at the time when it was designed, quite a
high transmission rate.
So it was something up to 600 megabit per second, which is, nowadays,
not of interest anymore.
But at the time when it was designed, it was very fast.
And it was seen as a possibility for high-definition television, video
on demand, audio on demand, and so on.
Meanwhile, we are having gigabit technology, and for that, ATM does
not work anymore.
Because you have these very small bits, these very small packets, it's
not really working adequately anymore.
And so ATM, in some way, disappeared.
But I still think it is adequate to mention this type of protocol, in
particular because we have this notion, which is not available in the
other protocols, but certainly you can now try to establish that on
top of TCPIP, establish certain service classes.
And this is, for example, important if you run, for example, services
over a cloud.
And you have to provide certain service level, make a service level
agreement on a certain quality of the communication with the cloud
storage or cloud applications.
And for that, you need something like that service level that you have
to guarantee.
And this is something which was put into ATM when it was designed
originally.
Okay, and this is the end of this chapter.
It was quite a bit, or it took us quite a bit of time, but it is
essential to look at how the Internet actually operates.
And after this, we will look into the next...
Oops, I have to look at the next chapter, which actually yesterday I
noticed...
Oops, I have not provided that, but last night I put it into the
store.
And so it is available... Oops, did not want to go there.
It is available now.
And we will look at now applications on the Internet, which are
essential for us meanwhile.
If we look at how actually, what kind of algorithms we need to
actually provide those applications.
So searching for information, meanwhile, is one of the major
applications of the Internet.
And so we have to look at that.
There are much more than 300 million web searches per day.
They have to be supported adequately.
It means you look for information in files, in data, which is stored
somewhere on the world, on one of those servers, and you want to get
that information.
You send out a query, and it takes just almost no time to get the
response.
So you get the impression as if they would look into the current
contents of all those data files and provide you with information on
what is in all those servers stored currently.
It is one of the most popular applications of the Internet, based on
the World Wide Web technology.
And what we need for that is certainly search engines.
And there have been many search engines which had been designed
initially.
You know that most of us, meanwhile, use Google or maybe Bing.
But there are alternatives, quite a few interesting alternatives.
But Google performs quite well.
And there are others who also perform quite well.
And I will tell you things about how those search engines actually
operate, and what actually the properties are that we should be
interested in, and what kind of search engines actually are available,
and what you could use, and why you should use certain things.
So what we have to look at is something which is an old discipline
called information retrieval.
This is not new.
This has been there a long time before you actually had the Internet
and the World Wide Web.
It means to do pattern matching in textual documents.
You want to construct an index.
What is an index?
You know what an index is.
You have a book.
And then a book, let me say here, you have many, or a large content of
that book, a very long file.
And then you want to look at certain relevant information, and you
have an index.
And this index is, like if you have a book, at the end you have an
index, and it shows you a list of the essential components, the
essential words, and points you to the locations in that book where
all these words actually occur.
Maybe at several locations, that's an index.
It tells you where you find certain information in some document.
Now what do we do when we ask, or when we send a query to a search
engine?
We ask for the occurrence of a certain word in a document.
For that we need an index.
So search engines have to build up an index, and that's what
information retrieval is about.
You are looking for certain information, and you get a data structure
which tells you where you actually find that information.
So the search engines will not look into all the documents when they
answer your queries, but they look into their index and provide you
with links to those documents where actually it's not just for one
document, but for many documents.
So it gives you links to all the documents that actually contain the
words that you are looking for.
So you have an index providing you with links to all those documents
where relevant content with respect to your query actually is
available.
So what you also have to do is usually you formulate a query to a
search engine or for information retrieval.
You have to analyze that query.
What actually does the user look for?
What is specified there?
There is a certain syntax that is necessary.
We will look at that.
And you have to measure the relevance of retrieved documents.
The quality, the relevance, so maybe you look for a certain page,
let's say for Java, and you get information on programming languages
and also on coffee from Java, from the island of Java.
So some are relevant, some are not relevant.
How do you determine what is actually relevant?
And maybe somebody just, like if you look for, there are many examples
that people put into their documents certain frequent search words and
that way they direct the responses to their webpage even if there is
nothing relevant with respect to the query in that document.
But you get attention of some people on your website and so this is a
side effect that you would like to get.
And we have many search engines available.
There is one service or one really interesting website which is called
Search Engine Watch and I want to just briefly go into that or show
you that website.
This is Search Engine Watch it is called.
And this is providing you with information, up-to-date information
about the current search engine technology, what kind of algorithms
are used in search engines and what kind of strategies you could
follow in search engine optimization.
What is search engine optimization?
Search engine optimization does not mean that you want to optimize a
search engine.
But search engine optimization is addressing the topic that you are
designing a website and you want to optimize your website such that
you have the best possible response or the best possible number of
requests for your website.
So search engine optimization means how can I actually make sure that
my website gets the most possible attention.
That is search engine optimization.
And there are many ways how you can do that.
Some are inadequate, unjustified, that is spamming.
Some are very adequate and you always have to do something where it is
adequate and to get the top rates.
Because if you are responsible for designing the website of your
company, you must make sure that your company gets the most attention.
But it has to be justified.
And if you do a bad job, you might have nice products, but nobody sees
them.
And so if you look at certain or if you perform a query, look at the
responses, you notice that some companies or institutes or so always
get top ranks in those listings.
You want to be among the top 10 on the first page of responses to a
query for the relevant queries.
If you achieve that, that's perfect.
If you are at position 100 or something, nobody will see that.
So that's what you have to make sure.
And here on this website, you get all kinds of information how to do
that.
You also get information on how they actually work.
You get information like search engine math.
What is search engine math?
Search engine math is some information on how to actually use or how
to specify queries.
You can use the plus symbol.
You can use the product symbol.
You can use other symbols so it looks like mathematical expressions.
And this is just a website or a page there where they tell you what is
the best way to actually formulate a query.
This is another point of optimization.
How can I phrase my queries such that I get the best response?
How do I do that?
And so this is also an essential point.
And you get information on that.
And then you get here all kinds of analytics.
So a lot of information and always current news on those topics.
So it is interesting to look at that website.
Just wanted to give you that link.
And let me go back to the slides.
Just a little bit more about that.
So that's what I told you about.
So there's all kinds of search engine facts and so on.
Like what are the most frequent words looked for and things like that.
All kinds of statistics about the use of search engines.
Okay, we have to look into search engine technology.
And for that we have to look at what a search engine actually is
about.
So a search engine is visiting the websites on the internet.
And wants to get information on what is actually stored there on those
websites.
Those web server sites.
Then it produces a catalog of the web pages.
And these catalogs are created automatically.
Updated constantly.
This is an automated process.
There's no necessary human interference.
And then we have directories.
In the directory you have a created catalog or manually created
catalog of web pages.
So there you have a certain catalog where you have a structured
information on maybe certain topics like information on cars, on
bookstores, on travel agents.
So it is categorized information.
And you have an ordered approach or an ordered entry into the world of
the World Wide Web.
So that's a directory.
And there the sites must be submitted.
And they are looked at.
They are quality assured.
And then you get actually they are entered in that directory.
And then you are visible.
And so directories can provide better results than search engines.
Yahoo was one of the first ones who provided actually quality assured
content.
And it does not mean that they are successful on the long run.
Sometimes those who provide unqualified information get better
results, like are better on the market.
But directories are quality assured content.
And then you have hybrid search engines where you have a search engine
plus a directory.
So you can provide quality controlled information plus search engine
based information.
And then you get this kind of hybrid search engine.
And next time I will tell you more about how search engines actually
work.
Okay, that's it for today.
Thank you very much for your attention.