So, last week, the recorded lecture was starting at, well, a location
where, where was it, we were talking about routing algorithms.
And I had shown you, that was the last slide of two weeks ago, the
basic router algorithm, and then in the recorded lecture you got
information on routing tables, on standard routing algorithms, like
the Dijkstra algorithm for computing shortest paths.
I hope you know that we have here at Karlsruhe people who are working
intensively on shortest paths algorithms and have won many prizes for
that because they have improved it on very large networks in a
significant way.
But still, Dijkstra is a standard algorithm for getting the shortest
paths in a reasonable time.
So it's, it takes some time, but for the, for the internet routing
algorithm, it's okay to do it like that.
Then we looked at flooding, like broadcasting information over all the
nodes in a network.
And the next thing was showing the distance vector routing, where
distance vectors are broadcasted from or between all the nodes in some
kind of heartbeat algorithm.
So telling for every node in the network what the estimated distance
is from the, from each node.
And by comparing tables from the neighboring nodes, you can update the
information on your node, knowing something about the delay between
the individual nodes.
So here the situation that is shown here is that node j gets
information from the neighbors a, i, h, and k.
And so you get there a new table, which was not shown in this way of
presenting it.
But if I go to presentation mode, you see the, the resulting table
that is computed from the other tables.
And then you have shown the problems that we have, the count to
infinity problem, which is due to the fact that information on the
loss of the connection is not really communicated immediately to all
the neighbors, because you always look for the best possible
information from your neighbors.
And since the neighbors are just estimating the distance to all the
other nodes, they don't realize that a link has broken.
And so it takes a very long time before this bad information actually
spreads in the network.
And so there's an alternative, which is link state routing, which is
the standard algorithm.
Meanwhile, part of the open shortest path first framework, where you
have link state packets, which are broadcast all over the network, not
just to the nearest neighbors, to get information on the status of the
network.
And so every node gets all these link state packets, has information
on the complete network, and can then run shortest path algorithms and
build up the routing information from that.
So this is what's happening here in the open shortest path first,
combined with also hierarchical routing, where you don't record the
distances to all the nodes, but only to the gateways to distant parts
of the network.
And so the routing tables are reduced in their size, and that's what
hierarchical routing.
Then, yeah, a few more things were in that lecture that was recorded.
The brief remark on the internet control message protocol, that
congestion control is one part, so reporting errors and faults back to
the source of the packet in order to do something with the traffic
flow, which is actually done then by the next layer, by the transport
control protocol.
And the routing for mobile hosts is another topic, which I don't
address here in the moment.
And this was the last slide in that recorded lecture, the new internet
protocol IP version 6.
And so this is something which has several different goals to support
all the large numbers of hosts that we have in current networks.
So you know that the 32-bit addresses don't suffice, so we have to
extend that.
So this is one of the objectives.
Then the size of routing tables should be reduced.
I have to select the 10.
So size of routing tables is another topic.
Then to speed up the traffic, to reduce the overhead that you have by
looking at all the different information, all different headers in the
headers of datagrams.
Security is another issue, so all these have to be addressed.
Also type of service, quality of service is another topic in
particular for real-time applications.
We'll come back to that a bit later.
And also better support of multicasting and mobile IP is another
topic.
And so what is this about?
The new address format, we have the 16-byte addresses, that means 128
bits, which is quite a large number.
The addresses don't look as nice as before, so you are completely lost
if you would like to memorize these numbers.
It's hard enough for the 32-bit numbers.
And certainly we still have the domain name system and have the nicer
names that we can memorize.
The important point is that we actually here with 128 bits per
address, we have quite a few addresses.
10 to the 24 addresses means, it's about 10 to the 24 addresses per
square meter of the earth's surface.
So that's quite a bit.
And so it should suffice.
But you know that we have all kinds of devices which need addresses.
It's not just a laptop or computer, like here's one laptop, a few
laptops are here in this room, but you have your smartphones, you
have, there might be, like all the lights here in the room might have
their own IP addresses in order to allow for remote control.
There are microphones in the ceiling.
There are all kinds of devices in this room.
And if you go into your car or go into your office, there are many
different devices that have their own IP addresses.
So we really need lots of addresses.
And this address space is distributed in a systematic way.
So certainly the old IP version 4 addresses have to be included there.
So if you have here leading zeros as indicated here, this would be
just the old IP version 4 address.
Then there are some other address systems which are also included here
from some other addressing schemes.
Then there are special addresses for certain service providers for
certain specific geographic regions.
There are some link-specific local addresses.
There are site-specific local addresses.
There is an address for multicast and one prefix for multicast.
And then there is also something which is called anycasting.
What is anycasting?
For example, you would like to send a message to just any mail server.
And then it's sufficient that one mail server gets your message.
It's not necessary that all the hosts or all the address systems
actually respond on that message.
It's sufficient if an arbitrary member actually is responding to that.
So this is an interesting type of alternative to multicasting where
you don't know the specific address that is necessary, but you have a
range of addresses and it's sufficient if one of them actually is
using or is responding to that address or is processing that address.
And then what I skipped over is that there are some prefixes which are
actually there for potential further extensions.
So this addressing scheme actually should be sufficient to also have
more addresses on some other planets, like on Mars or Moon or
whatever, or wherever we might want to go for solar systems, galaxies,
whatever you like.
So this is quite a large number of addresses.
So this is not restricted to what we are looking at at the moment on
Earth, but can be extended.
Just to indicate, we have here a system which is designed such that it
should last for quite some time.
Then you're right.
That's what I just also thought.
But so it should be 96 leading zeros, which would then you have 32
bits left.
So I have to check that.
Yeah, you're right.
So this would be 48 bits which are left, which is more than we need
for the IP version 4 system.
So you could say the other bits are arbitrary, but then the least
significant 32 bits are used for the old IP version 4 system.
I have to check that.
Question is valid.
So I have to check what actually is behind that.
Okay.
Sorry, I should have known that, but that's what I got from the
specification, and I should have looked at that.
So maybe that it's, you have certain more, but this is just, this here
is only related to the multicast system.
I will check that.
We'll come back to you on that.
Sorry for that.
So if we look at the new header format, so we have the new addresses,
which are the 128-bit addresses.
So if we look at the headers of the IP protocol, this certainly has to
change.
We need room for these new long addresses.
So there is certainly space for source address and destination
address.
And if you compare the IP version 6 header with the IP version 4
header, you notice that this looks like a fixed-size header, and this
is actually the case.
Here we have a bit more information.
We have the version information, which indicates whether this is a
version 4 or version 6 header.
We have the traffic class.
You can indicate priority here.
I said that in IP version 6, there should be some quality of service
specifications.
You remember that this was also something which was part of the IP
version 4 header, but there it was not really used.
Here in IP version 6, this is also present there, and you can specify
their priorities, but this is something which will be specified in the
course of time.
Then there is something which is called flow label.
The flow label is there for indicating that sometimes you have a long
sequence of packets, and they all have the same information on how
they should be treated.
Like this initial header here can be followed by other headers, and so
the idea is that you would only like to indicate certain information
on an initial packet, and not on all the others which are following.
And so you have some kind of pseudo-connection packet sequences, which
would all be treated in the same way.
And then this is just indicated with a flow label.
All those packets having the same flow label are then treated in the
same way, and the processing gets improved, because you don't have to
process all the following headers, which are containing all the
options for routing.
There is a payload length indicated there, like the payload has to be
indicated the bytes after this 40 byte long header.
You have to know how much information is there in the datagram.
So this is specified by the payload length of the datagram after this
header, which are just 40 bytes for those two initial 32-bit words
here, and then the remaining source address and destination address
field.
And you have the next header information, so the next header shows
what kind of header is following.
So you remember in the IP header, we had like IP version 4 header, we
had an indication of the next protocol, which was indicating whether
that was TCP or UDP, for example.
And here you can have a sequence of other headers, which might give
more information on the way how you should actually treat that
datagram.
In IP version 4, we had the option fields.
The option fields are not in here.
So what we have in IP version 6 is that you can have more extension
headers after that, which are providing all the information on
potential options.
So this next header then just specifies what type of next header is
there, and this is treated then in the appropriate way.
The next, the final field, the hop limit is the same as before.
The time to live is showing the number of hops that the packet should
be allowed to travel before it gets discarded.
So this is the same as before.
Then we have extension headers, which are just telling something on,
yeah, certain information on, for routers which are looking at this
datagram.
So you can have, you can indicate very large datagrams or some, have
some other options there.
I don't want to go into all the details.
There are options like routing options.
Remember that we had strict routing or some specification of routes
that should be followed.
So in the routing extension header, you might have a sequence of
addresses that should be the next destinations on that, like for the
routing of that packet.
And fragmentation is giving information on how fragmentation of
datagrams should be handled.
There is some options, you know, field extension header for
authentication where you can provide the information for
authenticating the sender's identity.
So you need public key information and things like that.
You have encryption security data, some information on key or type of
algorithm that is used there.
So just some information that you need in order to actually deal with
the content, certainly will not provide the key in open format, but in
a way such that the appropriate recipient can deal with that.
We will come back to encryption later on.
Then some more options for the destination of that packet.
So there are many different optional headers and these headers are
checked at the destination address only.
So for example, the routing extension header is only checked at the
destination address.
That means you have in the initial IPv6 header, you have the
destination and this is just an intermediate destination and if the
packet actually gets to that location, then the routing header is
looked at for the next destination that this packet has to be sent to.
So you have here a sequence of addresses and these are just used in
turn in order to send the packet to the appropriate address.
And this way you reduce the amount of work that has to be done in the
intermediate hops because you only have to look there at this
initial IPv6 header and there are some optional extension headers that
have to be looked at every hop, but all those that are indicated here
are options that are only relevant for the destination, which might be
not the final destination if routes are specified in between.
If it is the final destination, then you have more information on
security and things like that.
What you don't have here is header checksums.
So this is no longer in there.
So the control of correctness of the datagrams is restricted to the
next layer in the TCP header.
We will have that again.
And so if you don't have header checksums, you don't have to compute
the checksums, so this reduces the time.
But certainly you might run into problems later on if there is a
fault, you would detect it just a little bit later.
You have more flexibility by extension headers and can include more
information there than in these very restricted option fields of the
IPv4 header.
And certainly here you have the possibility to do more about security
of communication, about confidentiality, look at authentication and
things like that.
So there's just more flexibility in there.
And I don't want to go into more details of IPv6 because I would like
to get to the algorithms that we are more interested in.
The IPv6 is meanwhile more and more getting implemented.
It took a very long time.
It has been designed about 10 years ago and even more than that.
And it took very long before it actually was implemented.
Reasons are that the problems with the small number of addresses in
IPv4 were circumvented by having some more dynamic ways of dealing
with addresses or the extensions of the IPv4 addressing systems that
were included there.
The dynamic address selection and things like that.
Like here the DHCP service providing a dynamic assignment of addresses
was circumventing that problem or relieving a bit the problems.
And we also have these network address translation which is hiding
private address spaces.
So the need for having that was not that urgent, but meanwhile it gets
implemented more and more.
So it's happening.
And if you look at your computer you will also have TCP IP settings.
You will find also there IPv6 settings.
Okay, I would like to get to the transport control protocol because
here we have a few interesting things to look at with respect to some
algorithmic issues on flow control.
So what is TCP about?
TCP is on the next layer, on the transport layer, as you remember.
It's the transmission control protocol.
And here is again the specification of the different layers that a
datagram is running through.
Coming from the application we go to TCP and then we have all the
other information from IP from the physical layer until we get back
here to the receiving sites to the destination.
Now the task of TCP is to provide, like IP was or had the task to
provide a connectionless unreliable service, TCP has to take care of
reliability.
So IP didn't know anything about connections.
So if we have many nodes in the network, then IP would just receive
some packet and would not know anything about a specific connection
for some node, but would just decide sometimes on one link or on
another link to send messages to it, even if it's for the same host.
So this IP doesn't care about connections, just cares about the next
hop for some packet.
TCP has to look at the connection, but only looks at the logical
connection.
So it has to provide some information that there will be a sequence of
datagrams sent from some source to some destination.
And TCP has to make sure that that all the packets actually are sent
reliably.
That means that every packet is received.
And for that, if you have to know that every packet that is sent out
from there from A is actually received at B, you have to provide some
information back to A that this datagram actually is acknowledged.
This adds additional traffic to the system and adds additional
complexity, but we have to do something about the reliability.
And so this is taken care of in a reasonable way by TCP.
Another point is that TCP is just sending out data into the network.
It's getting information from the application layer and sending out
data.
The question is how much data is reasonable to send out.
This is something which is completely distributed.
Every node can decide on how much data actually is sent.
And now you need something like traffic control.
You could think about having just one central observer which would
just look at the system and try to optimize the traffic and decide for
every node how much data they might be able to send out.
This is not feasible, but this is a completely self-organized system
where every node decides on how much information is sent out.
That means we need some information on how TCP can actually find out
what the appropriate number of packets is that have to be sent, or
that is reasonable to send.
And what you know is that every segment gets a header, in this case a
header which will be used by the receiving side in an appropriate way
in order to know what to do with that packet.
And segment and header together form a datagraph which is then handled
by IP.
And we have looked at that briefly, how IP is actually dealing with
those datagraphs that it receives from TCP.
Now, first of all, what is the TCP information that is necessary?
Again, we have 32-bit words in that header.
And the first two things are source port and destination port.
Not source address and destination address, but source port and
destination port.
Why do we need a source port and a destination port?
So we have here our source, we have our destination, source and
destination, and we have here a certain application which is trying to
send information in some way.
Now this has to be established, there are many different applications,
and so we have many different ports, many different slots where an
application can talk to the system.
So these are the possible ports numbered by 16-bit addresses.
And a specific connection then has to know what is the appropriate
port that has to be used by that connection.
And it should be usually the same on both sides, because you have the
same type of application which is talking to each other.
Could also be different ports depending on the kind of communication
that is necessary.
So you have to select a specific port which is used for connecting the
system, or for connecting an application at the source and destination
side.
Now there are certain services which are standard services, which
always have the same ports.
And so, as I said, you have 2 to the 16 different ports, and these
ports are separated into some standard values, some reserved values,
and some open values which can be used arbitrarily.
And what I did not mention here, I just noticed, is that as soon as
you select for an application a specific port, you call that the
socket, the socket for this connection line, this logical connection
line between the 2 ports on the source, or the 2 applications.
So that's why we talk about sockets for this virtual cable that you
plug into certain sockets there.
And then these are just the ports.
Now, what kind of ports do we have?
We have so-called well-known ports.
If you would like to look at all the different ports, I will try to
open this address here.
Yesterday I tried it and it did not work.
Couldn't be... interesting, I thought I was connected.
Somehow this does not work.
Okay, then I advise you to try that out yourself, and I don't want to
go and to use the time for that.
So this is a valid address, so this is a problem of switching from
Windows 7 to Windows 8, and all of a sudden all these features, or not
all the features really work anymore, and I had problems with using
links in PowerPoint presentations.
I checked that last night.
It worked on one document, it worked with a newly inserted link, it
did not work in some way with an old link that was embedded in the
system.
I don't know what's happening there.
So this is problems with different operating system versions.
Now, let's come back to the ports.
I can give you the information that I would have shown you on the
website.
On the website you get a long list, a text document, having all the
different addresses, or the names for the ports, and how they are
assigned to different services.
So we have the so-called well-known ports, which are the first two to
the ten ports, for standard services like an echo service, that means
you have two nodes and they would like to check whether they are
actually there, and you send an echo message just to find out what are
your neighbors, and they respond with their address.
You have the FTP service, you have Telnet, you have the simple mail
transfer protocol, you have the time service, you have the finger
service to find out certain information, you have HTTP, whatever you
like, all these different standard services are in there.
Look it up on that address and you see all the different standard
services which have fixed ports which everybody knows and can use for
communication.
I guess you have done socket programming in Java, you can address
there specifically ports and then can deal with those ports and
programs.
Then there are registered ports which are quite a few, like here 1024
to 49000, so the next layer or next range of ports which are
specifically registered with this institution here, with the Internet
Assigned Number Authority for specific application programs and the
remaining are just for more flexible use, so you have some dynamic or
private use which can be used by application programs.
So you have a range of different ports which can be used for
communication between different application programs.
So this is the essential information in order to know how an
application can actually talk to an application on a different site.
You have to know what is actually the appropriate port, usually on the
destination site when you set up a communication, there is one port
which is just where the server is listening for incoming requests, for
synchronization requests, and then the information on the appropriate
port is interpreted and for establishing connection, the ports are
assigned to that connection and then the applications can talk to each
other.
Okay, what else do we have?
We have the sequence number, we have our, yeah, we have data items, we
have our long stream of data chopped into segments, and then we have
to know what are the specific bytes in that TCP connection, so it's
always the number of the first data byte within this datagram, so you
have the data payload that is following the TCP header and there's a
specific byte number in that datagram and this is, you have to know
when you receive a datagram what the position of the datagram in the
sequence of all the datagrams actually is.
And this is also important for telling the source of the datagram that
a specific datagram has been received or has not been received.
And it essentially means that if you don't get acknowledgments for all
the datagrams, like for all the sequence numbers that you have sent,
then you have to assume that a datagram has not been received, has
been discarded somewhere on its way, you have to send it again.
So the acknowledgment number is also a sequence number of a datagram,
specifying the first byte of a datagram that has been received.
So that is the sequence number, the acknowledgment number.
So the host sends the next address, not actually, does not send the
address that has been received, but always sends the address of the
next byte that it expects to receive.
And it means that all the bytes up to position x have been received.
And so as you know how large your datagram is, then you know what kind
of number you have to send.
Okay, so in this way you can send sequence numbers indicating this is
the appropriate position of a specific datagram.
And so even if you have received all the datagrams starting from some
specific position here, but this is still missing, then you will, in
your acknowledgments, you can only send this position here, which has
not been received so far.
You cannot indicate that you have received all the others that are
coming later.
Only after you have received this missing datagram, you will specify
that somewhere after that you need to acknowledge that that location
there actually has to be received.
So you can always know the location or the position up to which you
have actually received data.
And it means if this has not received this datagram in here, then all
the information starting from that point has to be re-sent, because
the ascending side only knows that starting from some position
information has not been received so far, and then this has to be re
-sent.
We'll come back to that also in a moment.
Then you have information on the header length.
We only need that because there's an optional part.
Some options can be specified there in the header.
And we also have, so we have to tell how many how many words are
actually needed in that.
So definitely we also need some padding bits here, because if this
option field is variable, then we always have to use appropriate
additional bits to come up to a multiple of 32 bits in the options.
And then we have here the flag fields, like here are all kinds of flag
fields, the so-called urgent flag.
If that bit is set, then this is indicating there is information which
has to be looked at immediately.
So TCP would put datagrams in a buffer and not provide everything to
the application, because datagrams are not coming in a sending
sequence, but they are coming in some ordering, and you have to put
them in appropriate positions.
So usually you don't provide the information immediately, but if the
urgent pointer is set, then certain information has to be read
immediately, and this datagram has to be provided to the application.
That's the urgent flag.
The acknowledgment flag indicates that the acknowledgment number here
actually is a valid number, should be looked at, it is an actual
acknowledgment.
Not every datagram will have an actual acknowledgment only if that F
field is set.
Then there is a push flag, which is similar to the urgent.
This here just means that you have to deliver data again, like deliver
data immediately.
So if you would have, for example, interactive applications, you are
sending just a few, or if you have a sequence of communication which
is sent, and for interactive applications you need that the
application side actually is looking at the data, so for that the push
field can be set in order to make sure that datagrams are delivered
immediately and not put into a buffer waiting for more datagrams to
come.
A reset field can be set in order to indicate that there has been some
problem with the connection, it has to be reset.
So this also can be indicated, there is a sync field, or a syn field,
which is used in the initial packets, indicating that you would like
to synchronize with the sum host, so to set up actually a connection
establishing the logic link.
So this is the sync field.
And then there's another field, the final bit, which is set if it is
the last datagram in a sequence of datagrams indicates to the
destination site that now this connection can be closed.
Because if you are establishing a connection, then you also have to
indicate at what time you can actually close that connection.
What else do we have?
We have the window size.
Right, what is the window size?
That's used for low control.
The window size is actually the number of packets that can be sent
before you have to receive an acknowledgement for the first datagram
that you have sent in that window.
We will come back to that.
So this window size is changing over time.
Then we have the checksum.
So I said that in IPv6 we don't have a checksum anymore, in IPv4 we
had a checksum.
We also have a checksum on the TCP header.
And this checksum is again the once complement of the 16-bit sum of
which fields of all the 16-bit fields of the datagrams, they are all
edit of the datagram.
Not just the header, but the complete datagram.
And there is a little bit more information which is used.
So it's, as I said, the header, which is the header with the checksum
field zero, and the data that is following.
And then there is a pseudo-header.
Now, the pseudo-header is information which is definitely known to the
TCP protocol, but which is not included in the TCP header.
And this information is information which is included in the IP
header, because it's necessary for the information for the IP protocol
on the receiving side.
But it's, and since at every hop the routers only look at the IP
header, they don't look at the TCP header, this source address and
destination address has to be, or is part of the IP header.
It's not needed anymore in the TCP header, because if the TCP header
is looked at, the datagram is already, or has already arrived at the
destination.
So then this information on source and destination address is no
longer necessary.
But nevertheless, the pseudo-header is included in that checksum.
So it's the source address, the destination address, and also
information on the protocol and the TCP segment length.
And so this is all together added up, all the 16-bit fields, and then
you get some value, take the ones complement, put it into the checksum
field, and at the receiving side, you just have to add up all the
information in the datagram, all the 16-bit information, plus the
information in the pseudo-header, and you can find out whether there
has been some bit error in between or not.
So you can check for correct transmission, and if it's not correct,
then you would not send an acknowledgement, but would discard that
datagram.
Then there can be some more options.
So you can specify things like specification of the maximally accepted
segment size.
This is something which is part of the acknowledgement packets.
So you can send back information on what is the segment size that you
actually accept.
So this is information for TCP, because TCP is separating the data
stream into individual packets, and in this initial synchronization
phase, you have to negotiate the appropriate size of the packets,
which depends on what information from the...at least the information
from the destination host.
And there is some lower limit for that, so every host has to accept...
whoops, what is this?
Oh, it's still working.
It has to accept at least 536 bytes of data plus the headers, so you
have 476 bytes including TCP IP header, and the maximum is 65k bytes,
so 2 to the 16 different bytes can be specified.
And so you have
the...like just some variance of the size of the packets.
Usually you have something like a few thousand bytes that are in those
packets.
If it's too long, you will have fragmentation in between, which
certainly is something which is, again, additional overhead which you
don't want to get.
If you would have a very small value, for example, less than these 536
bytes, which certainly is just some value which has been agreed upon,
but if you would have very, very small values, just a very few bytes,
you would have almost no effective data communication, but you would
have only overhead information in those headers that have to be
specified in those datagrams.
So you would like to have a reasonable tradeoff between number of
bytes for administration, for like the administrative overhead, and
TCP IP header, and so on.
And if it's too large, then you might have a too high fault rate due
to fragmentation, which you also would like to avoid.
And so if you have a very long packet, the probability of faults in
that very long packet definitely is higher than in a smaller packet,
and so you have to find out the appropriate value for that.
So this is agreed upon between the different partners in the
communication.
So this is the one part of the options.
You could set also a scaling factor for the window size, if you would
like to have that, or to make that a bit larger.
You can, like this can be done, and you can also indicate that you
would like to avoid a resending of packets that have been sent
already, by indicating that you are providing a negative
acknowledgement.
What is a negative acknowledgement?
You indicate that a specific datagram has not been received, and so
only this datagram has to be sent again.
Whereas if you don't get, usually if you don't get positive
acknowledgements, you would send everything again, even if only one
datagram is missing.
So in this way you could also indicate that a specific datagram has
not been received.
So many different pieces of information which are necessary at the
receiving side in order to process the data appropriately and manage
the communication between source and destination.
And it's also important information for dealing with the reliability
of the system, of the communication.
That's why we need all the acknowledgement information.
Okay, that's the header.
And then we have to look at how we actually connect between source and
destination.
So the server always waits for incoming connection requests.
That is that specific port that's always listening.
And the client then executes some, the sender executes some connect
primitive, which will send a few initial packets.
I will show you in a moment how that works.
And what do you have to send?
You have to know the IP address of the server.
You have to find, or you have to indicate the port for the connection.
You have to send the maximally handled segment size.
You have to indicate how long the segment might be that you are
sending out.
You can optionally send more user, more data that might be necessary.
And the logical connection then is established in a simplified way
here, or what I indicate here is a simplified protocol, which is just
showing this three-way handshake protocol.
If you have the two hosts, the first host sends a datagram, a sync
datagram.
So a datagram with a TCP header where the sync field is set to one.
And the host sends a certain sequence number, X.
Now why do you need the sequence number X?
The destination, the receiver, has to know what are the sequence
numbers of the datagrams that are received, how they have to fit into
the sequence of data that are sent by host one.
And so you have to know what is the starting address for
communication.
So the host one tells, I will start at position X.
That's the first address I use for the data that is sent.
And then the host number two is sending back some connection accept
message, which is acknowledging that it now expects information
starting at X plus one.
And it itself tells that it will use the sequence number Y for the
data that it itself will send.
So it's a bidirectional connection, both sides have to send data, and
they indicate these two values, X and Y.
And as soon as they have both agreed on X and Y, the connection
actually is established.
They know how to deal with those datagrams.
They know how they fit into a sequence of data that actually is sent.
And then after that, host one is sending an acknowledgment of that
connection accept, and sends a message just stating that it is
sequence number X plus one.
Acknowledgement Y plus one, it acknowledges the receipt of that
synchronization message, acknowledges that it will start with those
two positions, X and Y, or it has received those data, and now accepts
information starting at positions X plus one and Y plus one.
And after that, it can actually send data to the host number two,
because now both know that the connection actually has been
established.
So this is the three-way
handshake protocol agreeing on these two values, X and Y.
And certainly a bit more things that have to be exchanged between the
two hosts, but these are beyond the detail that I would like to tell
you here.
This would be something which you would look at in courses on computer
networks.
Now, certain things have to be looked at here also.
What happens if, for example, you have several synchronization
requests, maybe both sides are sending out synchronization requests,
then like host one sends out synchronization requests for sequence
number X, host two sends one for sequence number Y, and after that
gets the synchronization request, sends out again a message here, and
now it could happen that there would be two attempts to establish a
connection, but only one of them actually is acknowledged.
So this is like, one could call that a call collision, because both
sides are trying to establish connections at the same time.
And this response here is sent before the response for that request
actually is received, so this connection here actually is established,
and then the next one is discarded.
Only one connection gets established here.
Another thing could be that you have, for example, some late duplicate
of a synchronization message.
You are sending out synchronization packets.
If after some time you don't get a response, you could resend the
synchronization request, and if at some later time the synchronization
request actually gets to the host number two, so a late
synchronization packet is received at host two later on.
This also does not lead to a new connection, but this later duplicate
is discarded.
So this is just several ways of dealing with faults in those
protocols, and this was very brief indication of what could happen
there, but I just wanted to mention that there is definitely
necessary, or the necessity, to deal with these kinds of problems, and
all these things are taken care of reasonably in the TCP protocol.
Then you have to indicate the connection closure at some point in
time, so if it wants to close the connection, it can send a final
datagram, and the other connection will exist until the other host
sends a FIN diagram.
So they usually have to send FIN final datagrams from both sides.
If they don't do that, if you have a timeout, then there is an
automatic closure of that connection.
And you know that sometimes you can interrupt the TCP connection for
some time, and if you reconnect, you have the same connection which is
still there, but if it takes too long, then the connection is lost.
So this is establishing a connection, dealing with faults, and closing
the connection again.
And then we have the interesting part, which is how we actually deal
with the traffic control, how much data actually is sent.
We have to make sure that we have fault-free transmission of data.
Now TCP cannot do that.
TCP cannot make sure that data is sent without any faults.
Faults may occur, in particular if, for example, you have a node, and
you get here on one connection, you get many datagrams, and now maybe
the processing capacity of that node in between the path is not
sufficient, and some packets just get discarded because there's just
no space in the connection buffers that node has available, and so
some datagrams might get lost.
So this is out of control of the sender or the receiver, but things
like that can occur.
And that's why we need the acknowledgement that at some time actually
the datagrams have been received.
And in order to make sure that fewer faults occur, you could say if we
have less traffic on the system, then the probability of faults is
smaller than having a very, or a highly populated data network.
And so what we actually use is some kind of a sliding window.
Now what is this animation here indicating?
This is the sequence of datagrams, so every slot here is a datagram,
symbolizing a datagram, and this is indicating that actually this
datagram here has been sent, and now all the other ones also are sent,
but we only continue moving this window if we have received
acknowledgement for the first datagram in that window that has been
sent.
So we wait for an acknowledgement of this datagram that has been sent,
but we just send more packets, and so certainly this almost continuous
movement here indicates that we assume that we get a continuous inflow
of acknowledgements, but as soon as a packet does not get
acknowledged, the window stops.
Now the question is, how do we determine the size of that window?
I mentioned that in the TCP header we have this field for window size.
Now this window size is initially set by the destination host, which
is telling how many packets actually can be maximally operated on, so
this is some information on that initial window size, but then we have
to make sure that the number of packets that are sent are adjusted to
the traffic in the system, and so you have to observe the system, how
it's actually operating, now how can you observe the system?
You observe the system by looking at how many acknowledgements you
get.
So you send your data somehow to some hosts, and then you get the
acknowledgements, and so this is also called like the time you need
for sending a datagram out, and later on receiving on some path the
acknowledgement, is the so-called round-trip time that it takes to
send the data or send an acknowledgement for a datagram that has been
sent.
Now if you would wait for every packet to get that acknowledgement,
you would have very little traffic on the system, so you send more of
them.
The window size determines how many datagrams may be sent, as I said,
before the sender has to wait for an acknowledgement, and this is
negotiated between sender and receiver, so the receiver has a maximum
window size that is set, and then there's the traffic performance, or
the transport performance of the network, which is observed, and this
acknowledgement field, as I said, always contains the maximum received
sequence number, as I said, that is the next sequence, or the next
sequence number, next data item that actually is expected to be
received.
All the bytes up to that position have been received correctly, and
this acknowledgement is always set in the next available datagram that
is sent back to the source of that datagram.
And as I said, if a segment with a certain sequence number x does not
get acknowledged in time, then all the segments starting with that
byte have to be retransmitted.
So if this is not received in time, then all those packets also have
to be reset.
Okay, this is the sliding window protocol.
If you have a fixed window size, you just have that way of sliding
window over the sequence of datagrams.
And then there was this option of a negative acknowledgement.
If that is sent, then you would only send that datagram again, and
then proceed with the other ones that have not been sent before.
Okay, now this is the sliding window protocol.
You have a certain number of packets that you can send before you
actually wait for the acknowledgement and don't send any more packets.
Now there is this dynamic flow control which is deciding on the window
size in order to control the traffic in the network.
It means if there is a lot of traffic, many faults occur, you
shouldn't send a datagram, or very few.
If you have a lot of room, if there are no faults, you can increase
the number of datagrams.
And so what we use there is a method called slow start.
Now what is slow start actually doing?
Slow start is operating the way, let me draw that here.
So this is the time, and here is the size of the window.
So the window size, and here what we do is we start with a small
window, just with one datagram.
And we have a threshold value which is initially the maximum window
size which has been indicating in the connection phase from the
destination port, or the destination router has told what the maximum
window size is that can be accepted.
This is some value, this is an upper limit.
Initial value of T, threshold.
Now what do we need this threshold for?
Now we would like to increase the window size in a reasonable way.
So as soon as we get an acknowledgement for the first datagram that we
send, so initially we wait for an acknowledgement for the first
datagram, then if that is received, we double the window size.
If the window size is less than the threshold value, so after we had
window size 1, we get window size 2.
If everything gets acknowledged in time, we get window size 4, window
size 8, and so on.
So we have initially an exponential increase here in the window size,
and then we would get here to the maximum window size, and that's it.
Now this is not the complete story, but this threshold value, maximum
window size, was just the initial value for that.
If some fault occurs, so if there are faults, then the threshold value
is set to half the value of the current window size.
So assume that initially we could actually get up to the maximum
window size, now we have a fault, and we get half that value.
So then we have a new value of t, which is there.
So here, we start again with window size 1, and again, this is
increased exponentially, and then we have this threshold t, and now,
starting from that value t, we only add one additional packet to the
window size.
So starting from that, we just have a linear increase of the window
size.
So a smaller increase.
This is increased and increased and so on, until, again, we have some
fault, and it may be reduced again to half the size, and then again
have here initially exponential increase, and then linear increase,
maybe up to that maximum value again.
So in this way, you have a continuous adaptation of the window size to
the current situation in the traffic, or in the network.
If you have faults in the network, you don't get an acknowledgement.
If you don't get acknowledgements, then you reduce the window size,
reduce the traffic, and you start again with very few segments that
are sent, and increase that again, and you get more restrictive with
respect to the increase of the window.
Initially, you're optimistic, and double it every time, but later on,
we have this threshold value, and then you only increase it with care,
only linearly, in order to make sure that the traffic is not
increasing too much.
So this is the slow start protocol of TCP, and this is exactly what
you can observe if you look at the transmission rate of the data rate
of a TCP connection.
Usually, the transmission rate of a TCP connection doesn't look
exactly like this, because it's on a very fine scale level here, but
it's always going up and down.
And you don't have a steady flow of packets in a TCP connection,
because again and again, you get down to a window size one, and then
you have an increase again, but the window size, the data rate, the
number of packets that are sent per second, is changing all the time.
Depending on the current situation, the current reporting of errors,
the current rate of acknowledgment from the destination.
So here you have an adaptive data flow, which adapts to the network
capacity that is available for that connection.
So in this way, you have this adaptivity, and it also means that if
you need a connection, which guarantees a specific minimum data rate,
TCP cannot provide that, because it's always varying the data rate in
its transmission system.
So since the window is changing all the time, you don't have a
guarantee for a minimum window size and minimum data rate, minimum
number of packets.
Which is a certain problem for certain, or which might be a problem
for certain applications.
In particular, assume you have an application where, for example, you
require a certain number of bytes per second that have to be received
in order to provide a certain quality.
For example, for audio transmission.
There, it's not really that important if one packet is missing.
If one packet is missing, you have this small missing noise for a
short period, but it's much worse if the transmission rate is reduced
significantly, because then the number of bytes per second is going
down.
In some applications, you can actually tolerate a certain loss of
packets, but you cannot tolerate significant variation in the
transmission rate.
And so for that, TCP is not appropriate.
So we have different protocols for that.
We'll come to that in a moment.
Okay, I think that is most of what I wanted to tell you.
So this is congestion control.
We have the slow start with a small window, and then we have
congestion avoidance, which means that as soon as there are
congestions which are visible to the sender, by getting a reduced
number of acknowledgements.
So if you have indications of faults, then you reduce the window size
and reduce the traffic and have a larger probability that you actually
will get through with your data graphs.
So this is the main point of TCP, a very self-organized, distributed
way of controlling the traffic in a system.
You don't calculate the appropriate traffic centrally and then find
out how all the nodes should behave, what the threshold should be, the
window size should be at all the individual hosts, but this is
calculated individually.
And this was designed for a system with a few hundred or a few
thousand nodes, and it's operating with billions of nodes, which is
amazing that it's actually working in quite a stable way.
Certainly with certain fluctuations, sometimes it's not available, but
usually it is a very stable system.
The largest self-organized system that we actually have designed.
So the problems are that if you have some loss of segments, you can
have retransmission of many segments, which is a problem for certain
applications.
As I said already, if you have like slow start, may lead to frequent
changes in throughput.
As I said, this is unacceptable for multimedia applications.
So for multimedia applications, you need other types of controls of
communication.
And another point is that this protocol is assuming that the more
datagrams you send, the more likely you will get transmission faults.
Now this is something which is valid for transmission on wires, but
what about transmission on wireless carriers?
So if you are transmitting something on air, and you send fewer
datagrams, if you're sending them on some just some wireless
communication, so we have here some sender and there's a receiver, and
you send the packets to the air.
Now if you send fewer packets, then it's not more likely that they are
received here.
There it might be even counterproductive to actually send fewer
packets, but there it might be more reasonable to send more packets,
or send the packet several times, in order to make sure that it is
actually received.
And so for wireless communication, the characteristic properties are
different from communication over wires.
And the problem is that if you send something, or if you decide on
which protocol to use, TCP doesn't know anything about the network
that is below there, because TCP is the transport layer, and the
question whether you have transmission over wires, or whether it is
wireless, is something on the physical layer of the network.
So somehow you should know about the communication in order to be able
to deal with the flow control on the system.
Things like that are established meanwhile in these systems.
So if we just rely on dynamic flow control, then like of TCP, then it
might not be the adequate way of dealing with traffic problems.
Okay, so TCP cannot decide on the most reasonable method of flow
control, because the physical system is not really dealt with on the
TCP layer, unless you move information up to the TCP level, and then
it could be incorporated there.
So the question is how one could deal with that.
If you would like to make sure for certain applications that you get a
specific data rate, then you could use a different protocol, and one
alternative would be to use the user datagram protocol.
Now what is the difference between the transmission control protocol
and the user datagram protocol?
In the user datagram protocol, what we are doing is we are just not
taking care of reliability.
So the user datagram protocol, which is also the transport layer,
provides a connectionless, unreliable transport service.
Now this is exactly what IP does.
So essentially, the UDP protocol is just transferring data from the IP
layer to the application layer, but it's not building up a logical
connection, it's not taking care of acknowledgements, it's just
sending data.
So if you have your two applications, you certainly have the different
ports here, the different source and destination ports, and you select
the appropriate port, but you don't establish a connection, you just
send out packets to the destination, and they are received here
somewhere at that destination, at the appropriate port, and then the
application has to deal with their datagram.
The application has to take care of appropriate ordering, of finding
out whether a datagram is missing, or things like that.
So all the things that we have just looked at at TCP, taking care of
reliability, taking care of acknowledgements, taking care of the
ordering of datagrams, and things like that, are not taken care of by
UDP.
It just has almost the same functionality as UDP, or it just forwards
the datagram that is received at the destination to the next layer, to
the UDP layer, and then to the application layer, without doing
anything else.
So the UDP header can be very small, it only has to know something
about the source port, destination ports, what are the applications
talking to each other, what about the length of the datagram, how much
data is in the payload of that datagram, which has to be provided to
the application, and there's again the checksum as we had in the TCP
header, again the one's complement of the 16-bit fields in the UDP
header, data path, and the pseudo header.
So that is essentially the same as for the TCP header, this checksum,
but we don't have all the fields dealing with flow control.
So UDP is in some way providing direct access to the application
program, to the IP layer, you don't have the TCP functionality in
between, and now all this has to be taken care of by the application
program, like reliability, flow control, and things like that.
We can do that.
And so this is the way that protocols for multimedia applications
actually are working, they usually don't use TCP, but build their
quality of service on the UDP protocol and take care of quality of
service themselves.
And so certainly they don't have a guaranteed service quality, but
they only have, well, whatever they get from the network.
Yeah, but they have to deal with that on their own and don't use that
slow start and congestion control protocol on an algorithm, what I
showed to you just a moment ago.
Okay, that's UDP, and then I just, now you could say almost for
historic reasons, I present to you also the ATM, the asynchronous
transfer mode, in particular because there, in this alternative
protocol, this topic of quality control, service quality, has been
taken care of explicitly, which has not been done in TCP, IP, and UDP.
So what is the ATM protocol about?
Here, we don't have a connection-less service.
Here, we have, like, if we have different alternatives, root, and
different possibilities here in our system, in our, in ATM, you get a
virtual channel.
So you get some virtual channel which is used by all the different
packets in the sequence of packets that you send.
They are all sent over the same channel.
And so, if you establish such a connection, you, like, all the nodes
there after that know that they have to provide a certain service
quality for all the packets that are following on this connection
here.
So you send here a sequence of packets, and these packets are very
small, just 53 bytes.
You have a 5-byte header and 48-byte data.
The 5-byte header just gives the address information, the routing
information of that virtual channel, and you have 48-bytes data.
Very small bytes, or very, very, very small, not very small bytes,
very small numbers of bytes, so very small packets.
And you have a fixed header, and this header can be interpreted very
fast, and then this data is sent.
So the objective of the protocol was to provide high-speed
communication, with a very simplified communication protocol,
providing service classes, service quality, and so you could actually
now distinguish different service classes.
And so a connection is only established if all the hosts in between
can actually provide the necessary service.
And now the least quality would be UBR, the unspecified bitrate.
It means you don't care how much data is transferred.
Then the next one would be, okay, the hosts just make sure, or they
say, okay, the available bitrate at this moment will be provided to
that connection.
But they don't guarantee a specific data rate.
That's the available bitrate.
The unspecified actually means, well, I might provide less than the
remaining available bitrate on the connections.
Then there's a certain variable bitrate, so you specify a certain
range for the bitrate.
It can be in between a certain number of packets, maximum and minimum,
and it's non-real-time.
So it does not satisfy certain time restrictions, specific time
restrictions.
Now, if you have even higher quality requirements, you have real-time
variable bitrate.
So you allow for a specific variance in the bitrate, you have some
tolerance, but you have certain real-time requirements on the sending
or the time it needs for sending information.
This is certainly important for video conferencing.
So the time you have for sending information, if you have a long delay
in between the sending of data and you have a video conference, such a
delay can be very annoying.
And so for that you would like to have a guarantee that certain real
-time requirements are actually met.
And the highest quality would be a constant bitrate that you have a
guarantee that all the information that is sent over that virtual
connection actually is provided with a constant bitrate.
You have a guaranteed bitrate for that, no variance, just the same
bitrate while that connection is live.
So this is the service quality.
Certainly, you would have to pay for service quality.
And so this means that if you have the ATM protocol, you can make
specifications, you can give guarantees on service quality, which is
difficult if you don't have ATM but TCP IP.
The typical transmission rates at that time when it was designed were
in between 155 megabit per second and 622 megabit per second.
And meanwhile, TCP has much higher data rates, supports much higher
data rates.
And so for ATM, in order to support those high data rates, you needed
hardware implementations of the processing of the ATM packets, so
processing the five bytes header.
And this was expensive.
And so it was a high-speed system at that time when it was invented,
when it was designed.
It provided those service class properties, which was very
interesting.
But the gigabit technology, which is possible with the TCP based or
TCP IP, is just making that ATM technology obsolete.
So it's not used anymore.
But it was interesting to see those service classes.
And there are certain applications where you would like to have that.
And so you have not, like in TCP, you don't have this fixed service
guarantees as you could get here from ATM.
Okay, now this is all I wanted to tell you about routing protocols.
Time is almost over for today.
Thank you for your attention.
Next time I will also show you again the feedback tool, I use the
feedback tools.
Although in such a small group here, we can easily have feedback
directly.
Nevertheless, I think it's interesting to have the feedback tools and
I can ask you questions.
Thank you very much for your attention.
See you not next week.
Next week, as I said, is again a recorded lecture.
So two weeks from now, we will meet again in this room.
Thank you.