Die Einheit MB für Megabyte wird nicht einheitlich verwendet. Je nach Kontext beschreibt sie \(10^6 = 1000000\) oder \(2^{10} = 1048576\) Bytes (siehe Wikipedia). Im Netzwerkkontext und zur Angabe der Speicherkapazität von Festplatten beschreibt ein MB meist \(10^6\) Bytes, weshalb im Folgenden dieser Wert zu Grunde gelegt wird. Gbps steht für Gigabit pro Sekunde, misst also die Datenrate. 1 Gbps sind \(10^9\) Bits (nicht Bytes!) oder \(125\) MB pro Sekunde.
1 TB sind \(10^{12}\) Bytes oder \(8 \cdot 10^{12}\) Bits, 24 Stunden sind \(24 \cdot 60 \cdot 60\) Sekunden. Der Transport von 1 TB in 24 Stunden entspricht also einer Datenrate von \(8 \cdot 10^{12} / 24 \cdot 60 \cdot 60\) Bits pro Sekunde oder knapp 93 Mbps. Gängige DSL Anschlüsse bieten eine Datenrate von 16 Mbps, der WLAN Standard 802.11g bis zu 54 Mbps.
2000 Server mit jeweils 500 GB Speicherkapazität speichern zusammen \(10^6\) GB oder 1 Petabyte Daten. Bei einem Transport über zehn Stunden ergibt sich eine Datenrate von \(8 \cdot 10^{15} / 10 \cdot 60 \cdot 60\) Bits pro Sekunde, also gut 222 Gbps oder knapp ein vierzigstel der Datenrate eines im Jahr 2001 gelegten transatlantischen Glasfaserkabels.
Zur Berechnung von Prüfbits ist die folgende Hilfsfunktion nützlich, die zählt, wie viele Einsen eine Zeichenkette aus Nullen und Einsen enthält.
def count_ones(s):
count = 0
for i in range(0, len(s)):
if s[i] == '1':
count = count + 1
return count
Mit ihrer Hilfe können wir die Funktion add_checksum definieren,
indem wir ihr Ergebnis modulo zwei an die Eingabe anhängen.
def add_checksum(s):
return s + str(count_ones(s) % 2)
Zur Überprüfung verwenden wir ebenfalls count_ones, um zu testen, ob
die Anzahl der Einsen in der Eingabe gerade ist. Falls nicht, haben
wir einen Übertragungsfehler erkannt.
def is_valid(s):
return count_ones(s) % 2 == 0
Die folgenden Beispielaufrufe zeigen das Verhalten der definierten
Funktionen. Wenn der Funktion is_valid das Ergebnis von add_checksum
übergeben wird, liefert sie True zurück. Der zweite Aufruf von
valid ändert die Eingabe an einer Stelle, der dritte an zwei
Stellen. Die erste Änderung wird erkannt, die zweite nicht.
>>> add_checksum('101010')
'1010101'
>>> is_valid('1010101')
True
>>> is_valid('1010001')
False
>>> is_valid('1000001')
True
Neben der in der vorherigen Aufgabe implementierten Hilfsfunktion
count_ones ist die folgende Funktion hilfreich, die die
Binärdarstellung einer natürlichen Zahl als Zeichenkette liefert.
def binary(n):
if n == 0:
return '0'
else:
bin = ''
while n > 0:
bin = str(n % 2) + bin
n = n // 2
return bin
Wir können nun die Prüfsumme berechnen, indem wir die Funktion
binary auf das Ergebnis von count_ones anwenden und gegebenenfalls
führende Nullen ergänzen.
def add_block_checksum(s,n):
checksum = binary(count_ones(s) % (2**n))
return s + ('0' * (n - len(checksum))) + checksum
Zur Überprüfung einer Prüfsumme können wir diese Funktion auf das Anfangsstück der Eingabe anwenden, das der ursprünglichen Nachricht entspricht und dann vergleichen, ob wir das selbe Ergebnis erhalten.
def is_valid_block(s,n):
message = s[0:len(s)-n]
return s == add_block_checksum(message,n)
Wir können bei \(n = 2\) bis zu drei Einsen in Nullen umwandeln und den so entstehenden Übertragungsfehler erkennen.
>>> add_block_checksum('10110100101',2)
'1011010010110'
>>> is_valid_block('1011010010110',2)
True
>>> is_valid_block('1001010010110',2)
False
>>> is_valid_block('1000010010110',2)
False
>>> is_valid_block('1000000010110',2)
False
>>> is_valid_block('1000000000110',2)
True
Im letzten Fall bleibt der Übertragungsfehler also unerkannt. Dies geschieht auch dann, wenn die Anzahl der Einsen gleich bleibt:
>>> is_valid_block('1111110000010',2)
True
Auch Übertragungsfehler in der Prüfsumme können unerkannt bleiben, wenn es zu ihr passende Übertragungsfehler in der Nachricht gibt:
>>> is_valid_block('1011011010111',2)
True
Hier wurde sowohl in der Prüfsumme als auch in der Nachricht eine Null in eine Eins umgewandelt, ohne dass dies erkannt wird.
Um blockweise Prüfsummen zu berechnen fügen wir der Nachricht zunächst
Nullen hinzu, wenn ihre Länge noch kein Vielfaches der Blockgröße
ist. Dann verwenden wir die Funktion add_block_checksum in einer Schleife
für jeden Block. Obwohl die Anzahl der Schleifendurchläufe vorab
bekannt ist, verwenden wir eine while-Schleife, um die Zählvariable
index in jedem Schritt um die Blockgröße b hochzuzählen.
def add_block_checksums(s,b,n):
mod = len(s) % b
if mod > 0:
s = s + ('0' * (b - mod))
index = 0
message = ''
while index < len(s):
message = message + add_block_checksum(s[index:index+b],n)
index = index + b
return message
Zur Überprüfung wenden wir is_valid_block in einer Schleife auf jeden Block
an und brechen ab, wenn wir einen Fehler gefunden haben.
def has_valid_blocks(s,b,n):
index = 0
valid = True
while valid and index < len(s):
valid = is_valid_block(s[index:index+b+n],n)
index = index + b + n
return valid
Es ist nun deutlich schwieriger durch zielloses Manipulieren einen unentdeckten Übertragungsfehler zu erzeugen.
>>> add_block_checksums('1100101100011011111011011',6,2)
'1100101111000111101111011011010010000001'
>>> has_valid_blocks('1100101111000111101111011011010010000001',6,2)
True
>>> has_valid_blocks('1100101111000111100011011011010010000001',6,2)
False
>>> has_valid_blocks('1100101111011111100011011011010010000001',6,2)
False
>>> has_valid_blocks('1100101111011111100011011011010010011101',6,2)
False
Zur Implementierung von encode durchlaufen wir die Eingabe in einer
Zählschleife und fügen dabei der Ausgabe jedes Zeichen dreimal hinzu.
def encode(s):
code = ''
for i in range(0,len(s)):
code = code + s[i] * 3
return code
Zur Dekodierung verwenden wir die Funktion count_ones, die wir schon
zur Implementierung von Prüfsummen verwendet haben. Diesmal
durchlaufen wir die Eingabe in einer bedingten Schleife um die
Zählvariable in Dreierschritten hochzuzählen.
def decode(s):
msg = ''
index = 0
while index < len(s):
if count_ones(s[index:index+3]) >= 2:
msg = msg + '1'
else:
msg = msg + '0'
index = index + 3
return msg
Die folgenden Aufrufe zeigen das Kodieren sowie das Dekodieren mit keinem, einem oder zwei Übertragungsfehlern. Im letzten Fall schlägt die Fehlerkorrektur fehl, da zu viele Einsen im letzten Block in Nullen umgewandelt wurden.
>>> encode('101101')
'111000111111000111'
>>> decode('111000111111000111')
'101101'
>>> decode('111000111111000101')
'101101'
>>> decode('111000111111000001')
'101100'
Wir betrachten das folgende Netzwerk aus den Hosts A, B, C und D.
A --- B
| |
C --- D
Zu Beginn speichert jeder Host in seiner Routing-Tabelle nur eine Verbindung mit Kosten Null zu sich selbst.
Danach könnte zum Beispiel A seine Information an B und C schicken. Die Routing-Tabelle von B sähe danach wie folgt aus.
Ziel über Entfernung
------ ------ ------------
B B 0
A A 1
Angenommen, D schickt nun seine Tabelle an seine Nachbarn B und C. Dann wird die Tabelle von B wie folgt erweitert.
Ziel über Entfernung
------ ------ ------------
B B 0
A A 1
D D 1
Wenn B nun seinerseits diese Information an seine Nachbarn verschickt, kann A die folgende Tabelle aufbauen.
Ziel über Entfernung
------ ------ ------------
A A 0
B B 1
D B 2
Der Eintrag für A wird nicht übernommen, da schon ein kürzerer Weg bekannt ist. Sobald A eine Nachricht von C erhält, wird seine Tabelle wie folgt komplettiert.
Ziel über Entfernung
------ ------ ------------
A A 0
B B 1
D B 2
C C 1
Die anderen Hosts berechnen ihre Tabellen analog, zum Beispiel mit den folgenden Ergebnissen.
Ziel über Entfernung
------ ------ ------------
B B 0
A A 1
D D 1
C A 2
Ziel über Entfernung
------ ------ ------------
C C 0
A A 1
D D 1
B D 2
Ziel über Entfernung
------ ------ ------------
D D 0
A B 2
B B 1
C C 1
Angenommen, nun würde die Verbindung zwischen A und B getrennt. Diese beiden Hosts erhalten nun keine Nachrichten mehr voneinander, so dass sie sich nicht mehr als Nachbarn betrachten. Dadurch ändern sich mit der Zeit die Routing-Tabellen aller Hosts wie folgt.
Ziel über Entfernung
------ ------ ------------
A A 0
B C 3
D C 2
C C 1
Ziel über Entfernung
------ ------ ------------
B B 0
A D 3
D D 1
C D 2
Ziel über Entfernung
------ ------ ------------
C C 0
A A 1
D D 1
B D 2
Ziel über Entfernung
------ ------ ------------
D D 0
A C 2
B B 1
C C 1
Wird nun zum Beispiel auch noch die Verbindung zwischen A und C getrennt, ist A vom Rest des Netzwerkes abgeschnitten. Normalerweise merken das die anderen Hosts und entfernen entsprechene Routen aus ihrer Tabelle. Im ungünstigen Fall, dass zum Beispiel C die Nachricht von D bekommt, dass dieser A über zwei Hops erreichen kann, bevor C selbst die Nachricht verbreitet hat, dass es A nicht mehr erreicht, kann es jedoch zum sogenannten count to infinity problem kommen.
Dabei speichert C nun ab, dass es A über D mit Entfernung 3 erreichen kann, woraufhin D notiert, dass es A über C mit Entfernung 4 erreichen kann, woraufhin C notiert, dass es A über D mit Entfernung 5 erreichen kann und so weiter. Es gibt verschiedenen Mechanismen, dieses Problem zu vermeiden, die wir hier aber nicht weiter besprechen.
from datetime import datetime
print("Wie ist Deine Adresse?")
frm = input()
print("An welche Adresse willst Du schicken?")
to = input()
print("Betreff?")
subject = input()
print("Nachricht eingeben (mit zwei Leerzeilen beenden):")
text = ""
blank = False
line = input()
while not blank or line != "":
text = text + line + "\n"
blank = line == ""
line = input()
print("From: <" + frm + ">")
print("To: <" + to + ">")
print("Subject: " + subject)
print("Date: " + datetime.now().isoformat())
print()
print()
print(text)
Das folgende python-Programm gibt eine Multiplikationstabelle für das kleine Einmaleins aus.
n = 10
print("<table>")
for i in range(0,n):
print(" <tr>")
for j in range(0,n):
print(" <td>" + str((i+1)*(j+1)) + "</td>")
print(" </tr>")
print("</table>")
Für n = 3 ergibt sich die folgende Ausgabe, die wir in eine
HMTL-Datei kopieren können, um die Tabelle im Browser anzusehen.
<table>
<tr>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
<tr>
<td>2</td>
<td>4</td>
<td>6</td>
</tr>
<tr>
<td>3</td>
<td>6</td>
<td>9</td>
</tr>
</table>
Sie wird in etwa wie folgt angezeigt.
| 1 | 2 | 3 |
|---|---|---|
| 2 | 4 | 6 |
| 3 | 6 | 9 |