Lehrstuhl für Netzarchitekturen und Netzdienste
School of Computation, Information and Technology
Technische Universität München
Grundlagen Rechnernetze und Verteilte Systeme (IN0010)
Übungsblatt 11
10. Juli – 14. Juli 2023
Aufgabe 1 Kompression: Huffman-Kodierung
Gegeben sei das Alphabet A = {a, b, c, d } und die Nachricht
m = aabcbdacababbbbcbddbbbaababdbdbb ∈ A32 .
a)* Bestimmen Sie die Auftrittswahrscheinlichkeiten pi der einzelnen Zeichen i ∈ A in der Nachricht m.
b) Bestimmen Sie den Informationsgehalt I(i) der einzelnen Zeichen aus A.
c) Die Nachricht m stamme aus einer Nachrichtenquelle X . Bestimmen Sie auf Basis der bisherigen
Ergebnisse die Quellenentropie H(X ).
– Seite 1 / 12 –
d) Bestimmen Sie nun einen binären Huffman-Code C für diese Nachrichtenquelle.
e) Bestimmen Sie die durchschnittliche Codewortlänge von C .
f) Vergleichen Sie die durchschnittliche Codewortlänge von C mit der Codewortlänge eines uniformen1
Binärcodes.
1 Ein Code heißt uniform, wenn alle Codewörter dieselbe Länge aufweisen.
– Seite 2 / 12 –
Aufgabe 2 Domain Name System (DNS)
Hinweis: Angelehnt an Endterm 2015
Zentrale Aufgabe des Domain Name Systems (DNS) ist es, menschenlesbare Namen auf IP-Adressen
abzubilden, die dann für die Wegwahl auf der Netzwerkschicht verwendet werden können. Bei dem Namen
[Link]. handelt es sich um einen sog. Fully Qualified Domain Name (FQDN).
a)* Was ist der Unterschied zwischen einem vollqualifizierten Domain Name (FQDN) und einem nicht
(voll)qualifizierten?
b)* Benennen Sie die einzelnen Bestandteile des FQDNs, sofern es dafür gängige Bezeichnungen gibt.
[Link].
In Abbildung 2.1 sind ein PC sowie eine Reihe von Servern dargestellt. Wir nehmen an, dass PC1 den
Router als Resolver nutzt. Der Router wiederrum nutzt einen Resolver von Google unter der IP-Adresse
[Link] zur Namensauflösung. Ferner nehmen wir an, dass der Google-Resolver gerade neu gestartet wurde
(also insbesondere keine Resource Records gecached hat) und rekursive Namensauflösung anbietet.
Die autoritativen Nameserver für die jeweiligen Zonen sind in Tabelle 2.1 gegeben.
[Link]
[Link] [Link].
Client 1 [Link].
Internet
Router
[Link].
Client 2
[Link]. [Link].
Abbildung 2.1: Vorlage zu Aufgabe 2f)
– Seite 3 / 12 –
Zone autoritativer Nameserver
. [Link].
com., net. [Link].
[Link]. [Link].
[Link]. [Link].
Tabelle 2.1: Zonen mit zugehörigen autoritativen Nameservern
c)* Erläutern Sie den Unterschied zwischen einem Resolver und einem Nameserver.
d)* Welche Funktion erfüllen [Link] und [Link]?
e)* Erklären Sie den Unterschied zwischen iterativer und rekursiver Namensauflösung.
f) Zeichnen Sie in Abbildung 2.1 alle DNS-Nachrichten (Requests / Responses) ein, die ausgetauscht werden,
sobald PC1 auf [Link]. zugreift. Nummerieren Sie die Nachrichten gemäß der Reihenfolge, in
der sie zwischen den einzelnen Knoten ausgetauscht werden.
g)* Wie wird im DNS sichergestellt, dass kein bösartiger Nameserver Anfragen für andere Domänen
beantwortet? (Wir gehen davon aus, dass keine Man-in-the-Middle-Angriffe möglich sind.)
– Seite 4 / 12 –
Aufgabe 3 TCP und Long Fat Networks (Hausaufgabe)
In dieser Aufgabe betrachten wir sog. Long Fat Networks. Darunter versteht man Verbindungen, welche zwar
eine hohe Übertragungsrate aber insbesondere auch eine hohe Verzögerung aufweisen. Beispiele dafür
sind u. a. Satellitenverbindungen in Folge der hohen Ausbreitungsverzögerungen. Wir wollen insbesondere
die Auswirkungen auf die TCP-Staukontrolle untersuchen.
a)* Bei TCP wird das Sendefenster in Abhängigkeit des Empfangsfensters sowie des Staukontrollfensters
gewählt. Wie lautet der genaue Zusammenhang?
Zwei Nutzer seien nun über einen geostationären Satelliten an das Internet mit hoher Übertragungsrate
angebunden. Die RTT zwischen beiden Nutzern betrage 800 ms, die Übertragungsrate sei r = 24 Mbit/s.
b)* Wie groß muss das Sendefenster (gemessen in Byte) gewählt werden, damit kontinuierlich gesendet
werden kann?
c)* Warum ist die Situation in Teilaufgabe b) ein Problem für die TCP-Flusskontrolle?
d)* Lesen Sie Sektion 2 von RFC 1323 ([Link] siehe Anhang). Beschrei-
ben Sie die Lösung für das Problem aus Teilaufgabe c).
– Seite 5 / 12 –
e) Bestimmen Sie den minimalen Wert für das [Link]-Feld der TCP-Window-Scaling-Option.
f) Geben Sie den Header des ersten TCP-SYN-Pakets an, welches die Verbindung aufbaut. Verwenden Sie
dazu die konkreten Zahlenwerte aus der Angabe. Ein TCP-Header ist zur Erinnerung nochmals in Abbildung
3.1 dargestellt. Dort finden sich auch zwei Vordrucke zur Lösung.
Hinweis: Es ist nicht notwendig, den Header binär auszufüllen. Machen Sie aber bitte deutlich, ob es sich
um hexadezimale, dezimale oder binäre Darstellung der Zahlen handelt.
Angenommen die Größe des Staukontrollfensters betrage derzeit die Hälfte des in Teilaufgabe b) berechneten
Werts. Die MSS betrage 1200 B und die TCP-Verbindung befinde sich derzeit in der Congestion-Avoidance-
Phase.
g) Wie lange dauert es, bis das Fenster die Leitung komplett ausnutzen kann?
Hinweis: Das Staukontrollfenster wird durch TCP-Window-Scaling nicht beeinflusst.
h) Ergibt sich aus dem Ergebnis von Teilaufgabe g) ein Problem?
– Seite 6 / 12 –
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Source Port Destination Port
Sequence Number
Acknowledgement Number
URG
PSH
SYN
ACK
RST
Data Offset Reserved (Receive) Window
FIN
Checksum Urgent Pointer
Options (0 or more multiples of 4 b)
Data
(a) TCP-Header
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Source Port Destination Port
Sequence Number
Acknowledgement Number
Reserved (Receive) Window
Checksum Urgent Pointer
(b) Vordruck
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Source Port Destination Port
Sequence Number
Acknowledgement Number
Reserved (Receive) Window
Checksum Urgent Pointer
(c) Noch ein Vordruck, falls man sich vermalt hat
Abbildung 3.1: TCP-Header und Vordrucke zur Lösung von Aufgabe 3
– Seite 7 / 12 –
2. TCP WINDOW SCALE OPTION
2.1 Introduction
The window scale extension expands the definition of the TCP window to 32
bits and then uses a scale factor to carry this 32- bit value in the 16-bit
Window field of the TCP header ([Link] in RFC-793). The scale factor is
carried in a new TCP option, Window Scale. This option is sent only in a SYN
segment (a segment with the SYN bit on), hence the window scale is fixed in
each direction when a connection is opened. (Another design choice would be to
specify the window scale in every TCP segment. It would be incorrect to send
a window scale option only when the scale factor changed, since a TCP option
in an acknowledgement segment will not be delivered reliably (unless the ACK
happens to be piggy-backed on data in the other direction). Fixing the scale
when the connection is opened has the advantage of lower overhead but the
disadvantage that the scale factor cannot be changed during the connection.)
The maximum receive window, and therefore the scale factor, is determined by
the maximum receive buffer space. In a typical modern implementation, this
maximum buffer space is set by default but can be overridden by a user program
before a TCP connection is opened. This determines the scale factor, and
therefore no new user interface is needed for window scaling.
2.2 Window Scale Option
The three-byte Window Scale option may be sent in a SYN segment by a TCP. It
has two purposes: (1) indicate that the TCP is prepared to do both send and
receive window scaling, and (2) communicate a scale factor to be applied to
its receive window. Thus, a TCP that is prepared to scale windows should send
the option, even if its own scale factor is 1. The scale factor is limited to
a power of two and encoded logarithmically, so it may be implemented by binary
shift operations.
TCP Window Scale Option (WSopt):
Kind: 3 Length: 3 bytes
+---------+---------+---------+
| Kind=3 |Length=3 |[Link]|
+---------+---------+---------+
This option is an offer, not a promise; both sides must send Window Scale
options in their SYN segments to enable window scaling in either direction. If
window scaling is enabled, then the TCP that sent this option will right-shift
its true receive-window values by '[Link]' bits for transmission in
[Link]. The value '[Link]' may be zero (offering to scale, while applying
a scale factor of 1 to the receive window).
This option may be sent in an initial <SYN> segment (i.e., a segment with the
SYN bit on and the ACK bit off). It may also be sent in a <SYN,ACK> segment,
but only if a Window Scale op- tion was received in the initial <SYN> segment.
A Window Scale option in a segment without a SYN bit should be ignored.
The Window field in a SYN (i.e., a <SYN> or <SYN,ACK>) segment itself is never
scaled.
– Seite 8 / 12 –
Aufgabe 4 DNS nochmal (Hausaufgabe)
Gegeben Sie die folgende Menge von Domain Names:
• [Link]. • [Link]. Nameserver:
• [Link]. • [Link]. • [Link].
• [Link]. • [Link]. • [Link].
• [Link]. • [Link]. • [Link].
• [Link]. • [Link]. • [Link].
• [Link]. • [Link].
• [Link]. • [Link].
• [Link]. • [Link].
Abbildung 4.1: Einige FQDNs.
a)* Stellen Sie basierend auf den gegebenen Domain Names (einschließlich die der Nameserver) den
Namespace als Baum beginnend bei der Wurzel . dar.
– Seite 9 / 12 –
b)* Stellen Sie mittels des Kommandozeilenprogramms dig (Linux / macOS) bzw. nslookup (Windows) fest,
welche der in Abbildung 4.1 aufgelisteten Nameserver jeweils für die Zonen [Link], [Link], [Link],
[Link] und [Link] autoritativ sind.
[Link]. [Link]. [Link]. [Link].
[Link].
[Link].
[Link].
[Link].
[Link].
– Seite 10 / 12 –
c) Zeichnen Sie in den Namespace (Lösung von Teilaufgabe a)) die Abfolge der DNS-Nachrichten ein, die
entsteht, wenn der Resolver [Link] versucht, den FQDN [Link].
aufzuösen. Gehen Sie davon aus, dass dem Resolver aus vorherigen Anfragen bereits [Link]. als
autoritativer Nameserver für [Link]. bekannt ist.
Die in der Vorlesung bzw. den Programmieraufgaben verwendeten virtuellen Maschinen haben Adressen
aus dem Subnetz [Link]/21.
d)* Erläutern Sie, wie der IPv4-Adressbereich in den DNS Namespace eingebettet wird.
e) Ergänzen Sie Ihre Lösung von Teilaufgabe a) um die FQDNs der zugehörigen Reverse Lookup Zones.
f)* Stellen Sie fest, welche Nameserver autoritativ für die Reverse Lookup Zones dieses Adressbereichs
sind.
g)* Aus welchem Grund ist es im DNS nicht möglich, die 4 Subnetze [Link]/24, [Link]/24,
[Link]/24 und [Link]/24 mit nur einer Reverse Lookup Zone abzubilden?
– Seite 11 / 12 –
– Seite 12 / 12 –