Prof. Frederik Armknecht Sascha Müller Daniel Mäurer Grundlagen der Informatik 3 Wintersemester 09/10 Lösungsvorschlag zur 12. Übung 1 Präsenzübungen 1.1 Schnelltest a) Welche der Behauptungen zum OSI-Modell der Netzwerkschichten sind wahr? 4 In der Regel fügt jede Schicht den Übertragungseinheiten einen neuen Header hinzu. 4 Die Sicherungsschicht (Schicht 2) regelt bei Broadcast-Medien die Nutzung des Mediums zwischen den Teilnehmern. 2 Zuverlässige Ende-zu-Ende-Verbindungen zwischen Teilnehmern sind in der Netzwerkschicht (Schicht 3) angesiedelt. 2 Die Transportschicht (Schicht 4) kümmert sich um das Routing der Pakete. b) Wie sieht der Aufbau eines Pakets mit Headern Hi für jeder Schicht i auf der OSISchicht 3 aus? 2 H3 H2 H1 Daten 4 H1 H2 H3 Daten 2 Daten H3 H2 H1 2 Daten H1 H2 H3 1 Lösungsvorschlag zur 12. Übung Grundlagen der Informatik 3, WS 09/10 c) Welche Aussagen zu den Zuteilungsverfahren für Übertragungsmedien treffen zu? 2 Beim reinen ALOHA-Zuteilungsverfahren steht das Übertragungsmedium jedem Teilnehmer in festen Intervallen exklusiv zur Verfügung. 2 Ethernet-LANs verwenden i. d. R. ein Slotted-ALOHA-Protokoll. 4 Bei einem Zuteilungsverfahren mit Zufallsstrategie kann der Sender eine Kollision nur dann erkennen, wenn er gleichzeitig das Medium abhören kann. 2 Bei CSMA-Protokollen sendet jeder Teilnehmer seine Daten über den Kanal, unabhängig von der Aktivität der anderen Teilnehmer. d) Bei welchen Routing-Algorithmen handelt es sich um adaptive Verfahren? 2 kürzeste Wege (Dijkstra-Alg.) 2 Flooding 4 Link State Routing 4 Distance Vector Routing e) Was sind HOPs? 4 Punkt-zu-Punkt-Verbindungen 2 Host-zu-Host-Protokoll 2 Formatklassen 2 Die letzten Bits der Subnetz-Maske. f) Wie viele Rechner können in einem Klasse B Subnetz adressiert werden? 2 212 4 216 2 220 2 224 1.2 TCP a) Auf welcher ISO/OSI-Schicht ist TCP angesiedelt? Warum ist TCP dort einzuordnen? b) TCP ist ein zuverlässiges, verbindungsorientiertes Transportprotokoll. Skizzieren Sie den Mechanismus zum Verbingsaufbau! c) Welche Vor- und Nachteile hat TCP als verbindungsorientiertes Protokoll im Gegensatz z.B. zu UDP? In welchen Anwendungen würden Sie eher UDP als TCP einsetzen? d) TCP bietet Mechanismen zur Sicherung der Datenintegrität. Welche sind dies? Ist dadurch ausgeschlossen, dass ein Angreifer unbemerkt Datenpakete manipulieren kann? Begründen Sie ihre Antwort! 2 Lösungsvorschlag zur 12. Übung Grundlagen der Informatik 3, WS 09/10 a) Schicht 4. TCP ist eine Vereinbarung (Protokoll) darüber, auf welche Art und Weise Daten zwischen Computern ausgetauscht werden sollen. b) TCP-Handshake: c) Vorteile: u.a. • TCP bietet einen bidirektionalen, byte-orientierten, zuverlässigen Datenstrom zwischen zwei Endpunkten. • Umgeht einige Probleme der darunter liegenden Protokolle (wie z.B. IP). • Paketverluste werden erkannt. Der Sender wiederholt das Senden von Paketen, falls keine Bestätigung innerhalb einer bestimmten Zeitspanne (Timeout) eintrifft. • Stellt die Reihenfolge der Pakete durch Sequenznummern sicher. • Doppelte Pakete werden erkannt und werden verworfen. • ... Nachteile: u.a. • hoher Protokolloverhead • Nicht so “schnell“ wie z.B. UDP, deshalb für Anwendungen wie z.B. Videostreaming eher ungeeignet. Bei diesen Anwendungen ist es oft auch unerheblich, ob einzelne Pakete verloren gehen. Hierbei steht die Performanz eher im Vordergrund. Deshalb wird für Audio-, Videostreaming etc. meist UDP eingesetzt. • ... d) 16-bit TCP Checksumme; kein CRC; Ein Angreifer kann immer noch Datenpakete manipulieren, da die Datenpakete vollständig manipulieren kann; d.h. er kann zu den modifizierten Daten eine korrekte Checksumme berechnen und den TCPHeader entsprechend manipulieren. Checksum: 16 bits The checksum field is the 16 bit one’s complement of the one’s complement sum of all 16 bit words in the header and text. If a segment contains an odd number of header and text octets to be checksummed, the last octet is padded on the right with zeros to form a 16 bit word for checksum purposes. The pad is not transmitted as part of the segment. While computing the checksum, the checksum field itself is replaced with zeros. – [RFC793] 1.3 Flussregelung: Sliding-Window-Verfahren a) Nennen Sie zwei Gründe für die Notwendigkeit einer Flussregelung. b) Im Folgenden sollen 9 Frames (Sequenznummern 1 - 9) von einem Sender zu einem 3 Lösungsvorschlag zur 12. Übung Grundlagen der Informatik 3, WS 09/10 Empfänger unter Einsatz des Sliding-Windows-Verfahrens zur Flussregelung übertragen werden. Die Fenstergröße beim Sender („Send Window Size“) und Empfänger („Receive Window Size“) seien jeweils 3. Um explizit zu verdeutlichen, welches Frame bestätigt wird, wird ein ACK mit der Sequenznummer des bestätigten Frames ergänzt. Frames dürfen nur einzeln bestätigt werden, d.h. nicht kumulativ. Alle Frames werden korrekt übertragen. Die Übertragungsdauer eines Frames sowie eines ACKs betrage eine Zeiteinheit. Das Versenden eines bereitgestellten Frames der oberen Schicht hat beim Sender höhere Priorität als das Empfangen einer Quittierung, analog das Empfangen eines Frames gegenüber dem Versenden eines ACKs beim Empfänger. Gleichzeitiges Senden und Empfangen einer Station seien nicht möglich. Ergänzen Sie Tabelle A auf der letzten Seite des Übungsblatts. c) Im Folgenden sei keine korrekte Übertragung für die 4 Frames garantiert. Nehmen Sie an, dass das Frame mit der Sequenznummer 2 verloren geht, d.h. es wird nicht quittiert. Als Fehlerbehandlung wird „Selective-Repeat“ verwendet: Es werden dabei alle Pakete erneut versendet, welche nach der Beendigung eines Timeouts nicht bestätigt wurden. Als Timeout werden t = 6 Zeiteinheiten nach Versenden des verlorenen Frames angenommen: Wird ein Frame z.B. bei t = 3 versendet, wird bei Nicht-Quittierung des Frames, ein Timeout bei t = 9 geworfen. Ergänzen Sie Tabelle B auf der letzten Seite des Übungsblatts. 4 Lösungsvorschlag zur 12. Übung a) Grundlagen der Informatik 3, WS 09/10 • Angleichen der Sende- und Empfangsgeschwindigkeiten (Sender darf Empfangspuffer nicht zum Überlauf bringen). • Garantie von zuverlässigen Übertragungen b) Zeit 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 24 Sender Fenster 0-0 0-1 0-1 0-2 1-2 1-3 1-4 2-4 2-4 3-4 4-4 4-4 4-5 4-6 4-7 4-7 4-7 5-7 5-8 6-8 6-9 7-9 8-9 9-9 Frame(s) sendebereit F1 F2 F3, F4 F5, F6, F7, F8 F9 - Zeit 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Sender Grenze 0-0 0-1 0-2 0-3 1-3 1-3 1-3 1-3 1-3 1-3 1-4 1-4 1-4 3-4 4-4 Frame(s) sendebereit Sender Senden F1, F2, F3 F4 - F1 F2 F3 Timeout F2 F4 - 5 - - Sender Senden F1 F2 F3 F4 F5 F6 F7 F8 F9 - Sender Empfangen ACK1 ACK2 ACK3 ACK4 Empfänger Empfangen F1 F2 F3 F4 ACK5 ACK6 ACK7 ACK8 ACK9 F5 F6 F7 F8 F9 - Sender Empfangen ACK1 ACK3 ACK2 ACK4 Empfänger Empfangen F1 F3 F2 F4 - Empfänger Senden ACK1 ACK2 ACK3 ACK4 ACK5 ACK6 ACK7 ACK8 ACK9 - Empfänger Fenster 0-3 0-3 1-4 1-4 2-5 2-5 3-6 4-7 4-7 4-7 4-7 4-7 4-7 4-7 5-8 6-9 7 - 10 7 - 10 7 - 10 8 - 11 8 - 11 9 - 12 9 - 12 9 - 12 Empfänger Senden ACK1 ACK3 ACK2 ACK4 - Empfänger Grenze 0-3 0-3 1-4 1-4 1-4 1-4 1-4 1-4 1-4 1-4 3-6 4-7 4-7 4-7 4-7 c) Lösungsvorschlag zur 12. Übung Grundlagen der Informatik 3, WS 09/10 2 Hausübungen 2.1 Distance Vector Routing (4 Punkte) Gegeben sei folgendes Netzwerk mit den 7 Routern A, B, C, D und E. Knoten A bekommt von seinen Nachbarknoten die Distanzvektoren wie in Tab.1 notiert. D E C A D 1 B E 1 8 9 C B D Delay 1 8 A 1 4 B 0 3 C 1 2 D 3 0 E 2 1 Tab.1 E 9 3 2 1 1 0 To A B C D E Dir - Dist 0 Tab.2 1 A To A B C D E 1 B Dir Dist 0 B 1 B 2 B 4 B 3 Tab.2 a) Vervollständigen Sie die Routingtabelle von A (Tab.2). b) Beschriften Sie alle Kanten des Graphen (Ganzzahlig), so daß die Distanzvektoren gültig bleiben. c) Sie wollen gerade eine Nachricht von A nach E versenden, da fällt Router C wegen eines taktischen Nuklearschlags am Standort von C aus. Beschreiben Sie detailliert, was während der nächsten Meldungszyklen passiert. Wie ändert sich die Routingtabelle von A? Betrachten Sie dabei auch die Routingtabelle von Nachbarknoten B. Die Werte inkrementieren im Zusammenspiel mit B wie beim count-to-infinity. d) Wie lange braucht das Netz um sich zu erholen, d.h. wieder zuverlässig Daten von A nach E senden kann? Bis die Verbindung A-E die kürzeste ist. Dafür benötigt es in diesem Fall mindestens 5 Zyklen. 6 Lösungsvorschlag zur 12. Übung Grundlagen der Informatik 3, WS 09/10 2.2 Link State Routing (6 Punkte) Gegeben sei folgendes Netzwerk mit den 7 Routern A, B, C, D, E, F und G. 1 E 6 6 9 10 F A D 24 B 2 2 G 8 3 C 5 a) Wozu dienen die Felder Seq und Age der Link State Packets? Ein Link State Packet kann einen Router über mehrere Wege erreichen. Jeder Router inkrementiert die Sequenz-Nummer bei jedem neuen Link State Packet. Wenn ein neues Packet bei einem Router ankommt, vergleicht er zunächst die SequenzNummer mit einem eventuell bereits vorhandenen Packet und verwirft das ankommende, wenn dessen Sequenz-Nummer kleiner oder gleich der des bereits vorhandenen Packets ist. Das age-Feld dient dazu, Ausfälle eines Routers zu erkennen. Das Feld wird in regelmäßigen Zeitintervallen (z.B. jede Sekunde) dekrementiert. Wenn das Feld den Wert 0 erreicht, wird die Information des Packets verworfen. Da die Router neue Link State Packets in regelmäßigen Intervallen verschicken (z.B. alle 10 Sekunden), können so Router-Ausfälle registriert und neue Wege ermittelt werden. Das age-Feld dient ebenfalls dazu, dass Packets nicht ewig zirkulieren. b) Führen Sie ein Link State Routing auf dem Graphen für die beiden Knoten B und F schrittweise aus. Zunächst ermittelt jeder Router die Kosten zu seinen Nachbarn. Die Link State Packets kommen danach in folgender Reihenfolge bei B an: D,G,A,C,E,F. F erhält die Packets in der Reihenfolge E,A,G,D,B,C. Vernachlässigen Sie bei den Link State Packets die Felder Seq und Age. B A B E F G 24 1 9 2 A C D E G 24 5 2 6 3 C B G Knoten B: Ablauf: Nr. M1 0 1 B 2 B-D 3 B-D-G 4 B-D-G-A 5 B-D-G-A-C 6 B-D-G-A-C-E 7 B-D-G-A-C-E-F D 5 8 B F A ∞ 24,B 24,B [5,G] 2 10 C ∞ [5,B] E A B F F 1 6 6 A D E D ∞ [2,B] G 9 10 6 E ∞ 6,B 6,B 6,B [6,A] Routing-Tabelle: 7 A B C F ∞ ∞ 12,D 12,D 12,D 12,D [12,E] 2 3 8 G ∞ [3,B] Lösungsvorschlag zur 12. Übung Knoten A C D E F G über G B B A E B Grundlagen der Informatik 3, WS 09/10 Kosten 5 5 2 6 12 3 Knoten F: Ablauf: Nr. M1 0 1 F 2 F-E 3 F-E-A 4 F-E-A-G 5 F-E-A-G-D 6 F-E-A-G-D-B 7 F-E-A-G-D-B-C A ∞ 9,F [7,E] B ∞ ∞ 12,E 12,E 12,G [12,D] C ∞ ∞ ∞ ∞ 17,G 17,G [17,B] D ∞ [10,F] E ∞ [6,F] G ∞ ∞ ∞ [9,A] Routing-Tabelle: Knoten über Kosten A E 7 B D 12 C B 17 D F 10 E F 6 G A 9 Hinweis: in den Ablauf-Tabellen haben wir Werte, die sich im weiteren Verlauf nicht mehr ändern, in eckige Klammern gesetzt und der Übersichtlichkeit wegen nicht fortgeführt. Zudem haben wir immer den letzten kürzesten Weg übernommen, wenn es mehr als eine Möglichkeit gibt – diese Festlegung ist willkürlich gewählt. c) Geben sie für die übrigen Knoten A,C,D,E,G die aus dem Link State Routing entstehenden Routing-Tabellen an. Geben Sie dabei zu jeder Verbindung den gewählten Weg an. Knoten A: Knoten B C D E F G über G G G A E A Kosten 5 10 7 1 7 2 Knoten C: 8 Lösungsvorschlag zur 12. Übung Knoten A B D E F G über G C B G B B Kosten 10 5 7 11 17 8 Knoten D: Knoten über A B B D C B E B F D G B Kosten 7 2 7 8 10 5 Knoten E: Knoten über A E B C C B D B F E G A Kosten 1 6 11 8 6 3 Knoten G: Knoten über A G B G C B D B E A F A Kosten 2 3 8 5 3 9 Grundlagen der Informatik 3, WS 09/10 d) Beim Distance Vector Routing kann es zum count-to-infinity kommen. Treten beim Link State Routing ähnliche Probleme auf? Was geschieht, wenn eine Verbindung ausfällt? Begründen Sie. Nein, das count-to-infinity Problem kann beim Link State Routing nicht auftreten, da die Kosten-Informationen des Knotens nicht an die jeweiligen Nachbarn gesendet werden. Beim Link State Routing hat jeder Knoten eine Tabelle mit seinen direkten Nachbarn und sendet an diese periodisch eine Abfrage. Falls eine Verbindung ausfällt, bemerken es die Nachbarn des Knotens innerhalb des Intervalls. Anschließend verbreiten sie die Nachricht über den Ausfall. e) Welchen Nachteil besitzt Link State Routing gegenüber Distance Vector? Welche Möglichkeiten zur Abmilderung des Problems gibt es? 9 Lösungsvorschlag zur 12. Übung Grundlagen der Informatik 3, WS 09/10 Link State Routing verursacht extrem viel Netzwerkverkehr, da jeder Knoten im Netzwerk Link State Packets weiterleitet. Dieses Flooding-Prinzip ist in großen Netzwerken nicht praktikabel, da die Datenmenge exponentiell ansteigt. Ansatzweise abmildern kann man das Problem durch ein hierarchisches Routing. Zeit 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 Sender Fenster 0-0 0-1 0 - ... Frame(s) sendebereit F1 F2 Sender Senden F1 - Sender Empfangen ACK. . . F3, F4 F5, F6, F7, F8 F9 Tabelle 1: Tab. A 10 Empfänger Empfangen F1 Empfänger Senden ACK1 Empfänger Fenster 0-3 0-3 1-4 Lösungsvorschlag zur 12. Übung Zeit 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Sender Grenze 0-0 0-1 Frame(s) sendebereit F1, F2, F3 Grundlagen der Informatik 3, WS 09/10 Sender Senden F1 Sender Empfangen - F4 Tabelle 2: Tab. B 11 Empfänger Empfangen - Empfänger Senden - Empfänger Grenze 0-3 0-3
© Copyright 2024 ExpyDoc
