Übungen zur Vorlesung Betriebssysteme
Blatt 7

Ein FunkLAN funktioniert mit 1000-Bit-Paketen auf 56kbps (kilobits pro Sekunde). Es hat Collision Detection (CD; ein Teilnehmer spürt, wenn zwei Paketen überlappen) und Retransmission (ein Teilnehmer, der versucht hat ein Paket los zu schicken und herausgefunden hat, dass es mit einem anderen Paket von einem anderen Teilnehmer kollidiert hat, wartet einige Zeit und versucht wieder, das Paket zu broadcasten).

  1. Wie lang dauert es, ein Paket zu broadcasten? (Dies heisst: Frame-Time oder Frame-Zeit)

  2. Sei es, dass für alle Teilnehmer die durchschnittliche Zeit zwischen Zeitpunkten, an denen ein bestimmter Teilnemher ein Paket broadcastet, 100 Sekunden ist. Wie viele Teilnemher theoretisch maximal kann das Netz unterstützen?

  3. Sei es, dass die Retransmissionszeit (die Zeit zwischen Versuche, ein Paket ohne Kollisionen zu broadcasten) für alle Versuche für alle Teilnehmer genau diegleiche ist. Sei es weiter, dass an einem Zeitpunkt viele Teilnehmer versuchen, ein Paket zu broadcasten (ohne Erfolg, da die Pakete kollidieren).

    1. Wie würde das Verhalten des Netzes weiter aussehen?

    2. Wie kann man ein anderes, vielleicht zufriedenstellenderes, Verhalten in dieser Situation über ein anderes Verfahren erschöpfen?

  4. Sei es, dass man unendlich viel Teilnehmer hat und die Teilnehmer broadcasten Pakete, ein Wahrscheinlichkeitsverteilung folgend, mit eine Mean-Rate von S (erfolgreiche) Paketen pro Frame-Zeit.

    1. Wie gross könnte S (vernünftig) sein?

    2. Was passiert, wenn S grösser als dieser (vernünftige) Wert ist?

    Sei es, dass die Verteilung ein Poisson-Verteilung ist. Auch, dass Retransmission angewendet ist; d.h., die Mean-Rate für Versuche G ist und G≥S. Die Poisson-Verteilung lautet:

    Pr[k] = ( G^k*e^(-G)) / k!

    wobei k die Anzahl von Paketen ist und Pr[k] die Wahrscheinlichkeit ist, dass k Pakete in einer bestimmten Frame-Zeit generiert worden sind

    1. Was ist die Wahrscheinlichkeit innerhalb einer bestimmten Frame-Zeit, dass kein Paket generiert ist?

    2. Was ist der Erwartungswert für die Anzahl von Paketen, die in 2-mal die Frame-Zeit generiert worden sind?

    Sei die Frame-Zeit t. Sei es, dass ein Paket P um T broadcastet worden ist. Es könnte um eine Zeit t0 mit T - t < t0 < T ein Paket los geschickt worden sein und dieses Paket würde mit dem Paket P kollidieren. Das gleiche für ein Paket, die um t1 mit T < T1 < T + t loss geschickt worden ist. Also, in der Zeit T -t bis T +t mit Länge 2.t ist das Paket "verletzbar".

    1. Was ist die Wahrscheinlichkeit, dass kein anderes Paket von einem anderen Teilnehmer in diesem Zeitraum los geschickt worden wird? (Sei dieser Wert P0.)

    2. Allerdings ist S = G.P0. Wie sieht der Graph von G (Versuche pro Frame-Zeit) gegen S (die Anzahl von erfolgreich geschickten Pakete pro Frame-Zeit) aus?

    3. Was muss G sein, um den maximalen Wert von S zu erreichen? Was ist die maximale Wert von S? (Dies heisst: Channel-Utilisation.)