01711-Fehlertoleranz ml04 PDF

Preview

Summary

01711-Fehlertoleranz ml04...

Description

Fakult¨ at f¨ ur Mathematik und Informatik Lehrgebiet Kommunikationsnetze

Kurs 01711: Fehlertoleranz in Computersystemen und Netzwerken ¨ Musterl¨ Kurseinheit 4 osungen der Ubungsaufgaben ¨ Ubungsaufgabe 4-1: Man entwickle einen endlichen Automaten, der demonstriert, dass das 2 Armeen Problem keine L¨osung besitzt, mit der es m¨oglich ist, die Bataillone so zu koordinieren, dass ein synchroner Angriff sichergestellt werden kann. L¨ osung:

Nachricht A1 zu A2

0,1

Nachricht A2 zu A1

0,0

Be

s

A k) c A t. (

Be

1,0

s

u 1z

A2

A k) c A t. (

u 2z

A1

1,1 Angriff ist koordiniert und kann stattfinden

Abbildung 1: Der Zustand 1,1 wird niemals erreicht, da niemals mit absoluter Sicherheit feststeht, dass das andere Bataillon angreift ¨ Ubungsaufgabe 4-2: Man betrachte ein 1 Mbps Daten¨ubertragungssystem, bei dem Sender und Empf¨anger eine Taktabweichung von 0,5% aufweisen. Nach wie vielen Bits kann in diesem System ein Bitinterpretationsfehler auftreten, wenn Sende- und Empfangstakt nicht synchronisiert werden? L¨ osung: ¨ F¨ur ein Ubertragungssystem mit einfacher Bitkodierung nimmt ein Bit die Zeit von 1/(1 × 106 )sec oder 1µsec in Anspruch. Eine 0,5% Abweichung f¨uhrt dazu, dass ein Bit vom Empf¨anger nicht im Zentrum interpretiert wird, sondern 1µsec ± 5ns fr¨ uher oder sp¨ ater. Somit kann ein Interpretationsfehler nach 200 Bits auftreten, muss aber nicht (1000ns/5ns). Stand: September 2020

Kurs 01711 Fehlertoleranz in Computersystemen und Netzwerken

¨ Ubungsaufgabe 4-3: Das beschriebene Stop-and-Wait Protokoll verwendet Sequenznummern SN und RN, um die Kommunikation der Frames zu ordnen. Man zeige anhand eines endlichen Automaten, dass es f¨ ur das einfache Protokoll gen¨ ugt, SN und RN durch jeweils ein Bit darzustellen und somit SN und RN auf 0 und 1 zu beschr¨ anken. L¨ osung: frame mit gerader Seq. Nr. wird von B empfangen

0,1

1,0

Ack. wird von A empfangen

Ack. wird von A empfangen

0,0

frame mit ungerader Seq. Nr.

1,1

wird von B empfangen

Abbildung 2: Die Sequenznummern der Frames wechseln zwischen gerade und ungerade. Somit gen¨ ugt ein Bit, um die jeweilige Sequenznummer darzustellen. ¨ Ubungsaufgabe 4-4: Geben Sie zwei Beispiele f¨ur Protokollelemente der zweiten Schicht, die die Kommunikation trotz auftretender Fehler erm¨oglichen. L¨ osung: Zwei Beispiele (andere sind durchaus m¨ oglich.) 1. Ethernet - CSMA/CD: Frames werden wiederholt ¨ubertragen, wenn sie mit anderen ¨ Frames auf dem Ubertragungsbus kollidieren. Wiederholte Kollisionen werden durch Randomisierung vermieden. 2. Zerst¨orung und Eliminierung des Token in einem Tokenring wird durch die Definition eines Leaderknotens, der den zirkulierenden Token ¨uberwacht und auf Bedarf erneuert, korrigiert. Bei Zerst¨orung des Leaderknotens (Station) wird ein LeaderElection Algorithmus einen neuen Leader definieren.

¨ bungsaufgaben KE4 Musterl¨ osungen der U

2 von 4

Kurs 01711 Fehlertoleranz in Computersystemen und Netzwerken

¨ Ubungsaufgabe 4-5: Man zeige die Schritte f¨ur die Ausf¨ uhrung von Dijkstras Algorithmus in Knoten A im Netzwerk der Abbildung 3: 5 3

B

C 5

2 3

2

A

F

1

1

2 D

E

1

Abbildung 3: Eine einfache Netzwerktopologie L¨ osung: Schritt Nr. Knoten-Menge N 0 {A} 1 {A,D} 2 {A,D,E} 3 {A,D,E,B} 4 {A,D,E,B,C} 5 {A,D,E,B,C,F}

dist(B) 2 (von A) 2 (von A) 2 (von A)

dist(C) dist(D) dist(E) dist(F) 5 (von A) 1 (von A) ∞ ∞ 4 (von D) 2 (von D) ∞ 3 (von E) 4 (von E) 3 (von E) 4 (von E) 4 (von E)

Tabelle 1: Einzelne Iterationen in Dijkstras Algorithmus ¨ Ubungsaufgabe 4-6: F¨ur das Netzwerk in Abbildung 4 ist die Distanztabelle aus der Sicht von Knoten E zu ermitteln. B

1

C

7 8

A

2

1 E

2

D

Abbildung 4: Eine einfache Netzwerktopologie L¨ osung: DE A A 1 B 7 C 6 D 4

B D 14 5 8 5 9 4 11 2

¨ bungsaufgaben KE4 Musterl¨ osungen der U

3 von 4

Kurs 01711 Fehlertoleranz in Computersystemen und Netzwerken

¨ Ubungsaufgabe 4-7: Warum m¨ussen die ¨ubertragenen Datenpakete von Protokollen der 4. Schicht gegen Bitfehler gesichert werden, wenn jeder Frame durch CRC oder Parit¨atsmethoden schon durch die zweite Schicht gesichert wurde? Untersuchen sie die Schritte der Daten¨ubertragung im Internet und identifizieren sie m¨ogliche Fehlerquellen, die nicht durch die Protokolle der zweiten Schicht abgedeckt sind. L¨ osung: Beim Generieren der Pakete der h¨oheren Schichten k¨onnen Daten modifiziert oder zerst¨ ort werden. Dar¨uber hinaus werden die Datenpakete eines Kommunikationskontextes oft u ¨ ber unterschiedliche Pfade weitergeleitet, wobei verschiedene Fehler auftreten k¨onnen. Die verschiedenen Pfade und deren Netzwekverbindungen basieren oft auf unter¨ bertragungseinheiten (Maximum schiedlichen Netzwerkarchitekturen mit verschiedenen U Transmission Units (MTUs)). Dabei ist es m¨ oglich, dass Pakete zerst¨uckelt werden m¨ussen, wobei Bitfehler auftreten k¨ onnen, die nicht von der 2. Schicht abgedeckt werden. ¨ Ubungsaufgabe 4-8: Sind folgende Implikationen im Falle eines loyalen Kommandeurs korrekt? Begr¨unden Sie Ihre Antwort. L¨ osung: • IC 1 ⇒ IC 2 ist falsch. Alle loyalen Leutnants gehorchen zwar dem selben Befehl, aber es ist noch nicht gew¨ ahrleistet, dass sie auch den Befehl des Kommandeurs befolgen. • IC 2 ⇒ IC 1 ist wahr. Da der Kommandeur loyal ist und alle loyalen Leutnants dessen Befehl befolgen, gehorchen alle loyalen Leutnants demselben Befehl. ¨ Ubungsaufgabe 4-9: Wie l¨ asst sich das Problem der byzantinischen Gener¨ale zu einem fehlertoleranten Rechnersystem in Verbindung setzen? Was entspricht loyalen und nicht loyalen Gener¨alen? L¨ osung: Die interaktiven Konsistenzbedingungen k¨onnen wie folgt auf ein Computersystem bezogen werden. IC1 Alle nicht-fehlerhaften Prozessoren m¨ussen den selben Eingangswert verwenden, damit sie den selben Wert ausgeben. IC2 Falls die Eingabeeinheit nicht-fehlerhaft ist, dann benutzen alle nicht-fehlerhaften Prozessoren den Eingangswert, den diese Eingabeeinheit bereitstellt, und somit wird die korrekte Ausgabe produziert. In diesem Zusammenhang entspricht ein Kommandeur der Eingabeeinheit, die Leutnants den Prozessoren und loyal bedeutet, dass eine Einheit nicht-fehlerhaft ist.

¨ bungsaufgaben KE4 Musterl¨ osungen der U

4 von 4...