Lösungsvorschlag Computer Networks FS06

Aus VISki
Wechseln zu: Navigation, Suche

Aufgabe 1 - Multiple Choice

a)
3
b)
3
c)
3
d)
1
e)
4
f)
2
g)
1
h)
2
Anm: Die nummern zwischen klammern sind anscheinend _nicht_ Faktoren sondern genauere Werte. (Danke Shial)
i)
3
j)
4

Aufgabe 2 - Kurzfragen

a)

Bei NAT kann man Verbindungen initiieren, aber Maschinen ausserhalb des lokalen Netzwerks des Clients können keine Verbindungen zu diesem initiieren, weil der Client keine eigene öffentliche IP Adresse hat, sondern diejenige vom NAT-Gateway benutzt. Deswegen können zwei Clients, die beide hinter NAT sind, keine direkte Verbindung haben: keine von den beiden kann sie initiieren. Falls aber beide eine Verbindung zu eine "Supernode" machen, der nicht hinter NAT ist, kann dieser Paketen von eine nach der andere weiterleiten.

[Bemerkung: Obige ist sicher was an der Prüfung erwartet ist, aber mann könnte auch von UDP hole punching reden. Wenn ich mich gut errinere war das allerdings nicht Vorlesungsstoff. ]

b)

  1. DNS-Server: Eintrag für www.greedbank.com ändern, so dass es auf die IP-Adresse der "falschen" Website zeigt.
  2. Ein Router zwichen Client und Bankserver ändern, so dass alle Paketen für den Bankserver an den "falschen" Webserver geroutet werden.
  3. Ein Virus auf dem Client. (Es ist nur der Browser, den mann nicht ändern darf.)
  4. ARP Spoofing

c)

Slow Start Algorithm ist ein Algorithmus für TCP Congestion Control. Es fängt mit eine Congestion Window von 1 an und erhöhert es, so lang dass keine Packets verloren gehen oder ein Grenzwert nocht nicht erreicht ist.

d)

Max-min fairness diagramme

-- Rvjr 16:22, 1. Jun 2008 (CEST) Zu Bild 3: Ich waere der Meinung, dass die Geschwindigkeiten im unteren Knoten jeweils maximal 1/2 betragen; Die Verbindung über den Knoten rechts oben hätte damit die Bandbreite 1/3 (limitiert durch den Knoten links oben), die Verbindung die nur den unteren Knoten passiert hat Bandbreite 1/2. Das wuerde sich dann mit dem Beispiel in Excercise 5 Slides auf Seite 3 decken.

-- Rvjr 22:02, 2. Jun 2008 (CEST) Korrektur: Die Exercise Slides die ich oben als Quelle angegeben habe scheinen falsch zu sein. Wenn man sich an die Vorlesungsslides hält, ist die ursprüngliche Lösung korrekt.

e)

Wir haben , was
101
entspricht. Unsere Daten sind:
D = 1001101

Beim CRC überträgt man Daten D und ErrorCorrectingCode EDC. (D + EDC) sei T(x), welches übertragen wird. Um EDC zu berechnen, setzen wir erst EDC := 00 setzen (2 Stellen, da G(x) 3 Stellen hat). Dann dividieren wir T(x) durch G(x). Dazu rechnen wir jeweils XOR (statt wie bei der bekannten Polynomdivison zu dividieren bzw. subtrahieren)

T(x) = (D + EDC) = 

100110100 -> 001110100 -> 001110100 -> 000100100
101           101           101           101

-> 000001100 -> 000000110 -> 000000011
        101           101 

Der Rest ist 2 Bits gross, da unser Generator 3 Bits enthält.

Wir setzen also
EDC := 11 
Wir müssen folgenden Bitstring übertragen:
T(x) := D + EDC = 100110111 

Der Empfänger der Nachricht kann Fehler bemerken, indem er das empfangene T'(x) durch G(x) teilt. Ist der Rest = 0 so sind die empfangenen Daten mit hoher Wahrscheinlichkeit fehlerfrei.

-- Gregr 21:50, 25. Jun 2007 (CEST)

f)

Gegeben:

.

Bei Bob kommt alles mit einer Verzögerung d an.

.

Bob empfängt somit während mit der Rate . Die Datenmenge, die Bob nach empfangen hat, ist somit

.

g)

Hauptvorteil: Routers müssen keine Checksums mehr berechnen und brauchen deswegend weniger Zeit, ein Paket zu routen.

h)

Node A, step 2
Destination via B via C
B 2 5
C 6 1
D 3
Node A, step 3
Destination via B via C
B 2 5
C 6 1
D 8 3
Node A, step 4
Destination via B via C
B 2 5
C 6 1
D 8 3

Aufgabe 3 - Launische Bankbeamten

a)

Die Kette ist unendlich lang, jeder Zustand entspricht einer bestimmten Anzahl Kunden im System. Die Ankunftsrate (Zustand i zu i+1) ist , die Bearbeitungsrate (Zustand i zu i-1) ist für i < 10 und für i >= 10.

Es ist klar, dass der Zustand i = 10 erreichbar ist. Sobald das System diesen Zustand erreicht, ist die Ankunftsrate höher als die Bearbeitungsrate (), d.h. die Warteschlange wird unbeschränkt wachsen.

b)

Es gibt 3 Zustände. Dies darum, da man einen weiteren Zwischenschritt benötigt um von annoyed nach happy zu kommen. Nach Aufgabenstellung müssen zwei freundliche Kunden kommen, damit man den zustand wechselt. Nun zu den Wahrscheinlichkeiten. Wir wissen, dass wenn der Bankbeamte happy ist, er zu 60% annoyed wird, wenn ein unfreundlichen Kunde kommt. Ein unfreundlicher Kunde kommt zu 20%. Damit wechselt er zu annoyed in WS 0.2*0.6 = 0.12 (12%) der Fälle. In den restlichen 88% bleibt er happy. Ist er nun genervt, so kann er nur gerettet werden, falls ein freundlichen Kunde kommt. Dieser kommt zu 25% der Fälle (laut Aufgabenstellung). Ist er also genervt, wechselt er mit 25% zu half_annoyed, dem Zwischenschritt. Ist er half_annoyed und es kommt wieder ein freundlichen Kunde so ist er wieder happy. In allen anderen Fällen (75%) fällt er wieder zurück zum Zustand annoyed.


3 Zustände: happy, half-annoyed (Zwischenschritt von annoyed zu happy bei Ankunft eines freundlichen Kunden) und annoyed. Übergangsmatrix:

c)

Für stationäre Verteilung ergeben sich die Zustandswahrscheinlichkeiten


und damit die "gewichtete" Verkehrsdichte

.

Das System ist also nicht stabil.

Question.png

Dem Autor des Lösungsvorschlags stellt sich eine Unklarheit betreffend der Prüfungsfrage oder deren Lösung:
Keine Ahnung ob die Überlegung stimmt, andere Vorschläge? ;) —Gnome Icons-balloon.png Icons-bomb.png 00:37, 18. Jun 2007 (CEST)
Hilf mit, die Qualität dieser Seite zu verbessern, indem du eine eindeutige Lösung einfügst oder auf der Diskussionsseite dieses Themas deine Meinung äusserst.

Aufgabe 4 - Programmierung eines einfaches FTP-Clients

a)

private void downloadFile(InetAddress dataAddr, String filename) throws IOException { 
    sendLine("RETR " + filename);

    dataSocket = new Socket(dataAddr, dataPort);
    dataIn = new BufferedReader(new InputStreamReader(dataSocket.getInputStream()));

    String temp = null;
    temp = dataIn.readLine();

    while (temp != null) {

        System.out.println(temp);
        temp = dataIn.readLine();
    }
   
    dataSocket.close();

}

b)

Zwei Verbindungen machen Sinn, da mann während das Übertragung von grossen Daten noch Kommandos senden kann bzw. deren Rückgaben lesen.

Aufgabe 5 - Distributed Systems - Architecture

a)
3
b)
3
c)
3
d)
4
e)
4
f)
4
g)
2
h)
2
i)
4
j)
2
k)
1
l)
4
m)
3
n)
1
o)
4

Aufgabe 6 - Failure Semantics in RPC

Message exchange diagram

Aufgabe 7 - Optimised Linear 2 Phase Commit

We can assume no limitations on how the nodes are able to communicate. This means every code can in theory communicate with every other node. We also assume that there is some sort of circular ordering among the nodes: each node knows who it's two neighbours are. (see diagram: Ring network)


Now, the coordinator can start by sending his vote to his two neighbours. These neighbours abort if it is a NO and forward the NO further round the ring. If it is a YES, they decide and then either abort and send a NO in _both_ directions or send a YES further round the ring. We need to think of what happens with the "other end of the ring": if the ring has a even number of nodes, the "last" node will get two votes in the same round. It is easy to see that then he should decide and either do nothing (if YES) or forward NO in both directions.

If there is an uneven number of nodes, two neighbouring nodes will get a vote in the same round. Their votes in the next round will "cross" and so we must have the rule that, if after sending a YES in one direction a node gets a YES from the other direction, he should forward it (note that as he sent a YES he already made a decision). If, after sending a YES in one direction, he gets a NO from the other, he should abort and forward the NO.

How does the coordinator know what the consensus is? After he sent the two YES votes (we don't need to consider the case where he sent two NOs), he must wait until he gets two answers (they should come simultaneously after N rounds). If one of them was a NO, he should broadcast an ABORT to all nodes (unless there is an even number of nodes and the N/2th node votes NO, he will not get two NO votes in round N ). If both were YES, he should broadcast a COMMIT to all nodes.

It takes N rounds for the votes to propagate around the ring. It then takes another round to broadcast the decision, so we have N+1 rounds in total.

The message complexity: 2 messages are sent each round that the messages "go around" the ring, and N-1 messages are sent during the broadcast round, so we have 3N + 1 messages (or maybe 1 more because a NO was still being forwarded on the last round, so 3N+2 if we're being picky).

This is not a very elegant solution. Possibly somebody with more time can find a better one?

Aufgabe 8 - Linear 2 Phase Commit

a)

Message exchanges in a sucessful 2PC run

b)

Message exchanges in a sucessful 2PC run

Aufgabe 9 - Decentralised 2 Phase Commit

a)

State diagram for the coordinator in distributed 2PC


State diagram for the client in distributed 2PC

b)

1-(1-P)^n, as any node failure can lead to blocking (in worst case).

c)

Same as b), because any one node can block the others by failing when eveyone else has voted "YES".

d)

3N: one round of N VOTE-REQs, one round of N YES/NOs, and one round of N COMMIT/ABORTs.

e)

N*(N-1): (N-1) YES/NOs from the coordinator and then (N-1) YES/NOs from each of the (N-1) other nodes

f)

3: a round of VOTE_REQs, a round of voting and a round of COMMIT/ABORT.

g)

2: one round for the coordinator's vote broadcast, and one round for everyone else to broadcast a vote.

Aufgabe 10 - RPC programming

a)

Work in progress.png

Diese Aufgabe wurde noch von niemandem gelöst und wartet noch immer auf einen Musterlöser.
Hast du dieses Fach bereits besucht? Hilf mit, die Qualität dieser Seite zu verbessern, indem du eine plausible Lösung für diese Frage notierst!

b)

Work in progress.png

Diese Aufgabe wurde noch von niemandem gelöst und wartet noch immer auf einen Musterlöser.
Hast du dieses Fach bereits besucht? Hilf mit, die Qualität dieser Seite zu verbessern, indem du eine plausible Lösung für diese Frage notierst!