Vorlesung Sommersemester 2002

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fachbereich Mathematik/Informatik

1Algorithm. Grundlagen des Internets27. Mai 2002

Christian Schindelhauer

Vorlesung Sommersemester 2002

Algorithmische Grundlagen des Internets (VI)

Christian [email protected]


Fachbereich Mathematik/InformatikAG Meyer auf der Heide





Fairness und Effizienz von AIMDDas Modell

o n Teilnehmer, Rundenmodell

o Teilnehmer i hat Datenrate xi(t)

o Anfangsdatenrate x1(0), …, xn(0) gegeben

o Feedback nach Runde t: y(t) = 0, falls

y(t) = 1, falls

o Jeder Teilnehmer aktualisiert in Runde t+1:

xi(t+1) = f(xi(t),y(t))

Increase-Strategie f0(x) = f(x,0)

Decrease-Strategie f1(x) = f(x,1)

o Wir betrachten lineare Funktionen:





Fairness und Effizienz von AIMDDas Modell

o Wir betrachten lineare Funktionen:

o Interessante Spezialfälle: MIMD: Multiplicative Increase/Multiplicative Decrease

AIAD: Additive Increase/Additive Decrease

AIMD: Additive Increase/Multiplicative Decrease





Fairness und Effizienz

o Effizienz Last:

Maß

o Fairness: Für x=(x1, …, xn):

1/n ≤ F(x) ≤ 1 F(x) = 1 ↔ absolute Fairness Skalierungsunabhängig Kontinuierlich, stetig, differenzierbar Falls k von n fair, Rest 0, dann F(x) = k/n





Konvergenz

o Konvergenz unmöglich

o Bestenfalls Oszillation um Optimalwert

Oszillations-amplitude A

Einschwingzeit T





AIADAdditive Increase/Additive Decrease





MIMDMultiplicative Increase/Multiplicative

Decrease





AIMDAdditive Increase/Multiplicative

Decrease





Effiziente lineare Funktionen

o X(t) > K

aD ≤ 0 → bD ≤ 1

aD > 0 → bD < 0

o X(t) < K

aI ≥ 0 → bI ≥ 1

aI < 0 → nicht möglich





o Fairness von x(t) = (x1(0), …, xn(0)) konvergiert gegen 1, d.h.

für

o Es gilt für c=a/b:

o Beweis?

Fairness (I)





Beweis! (1)

o Es gilt:

o Substitution

o Dann ist: und





Beweis! (2)

o Zu zeigen:

o Warum gilt diese Gleichung?





Beweis! (3)

o Warum gilt diese Gleichung?

wobei





o Es gilt:

o D.h. Fairness nimmt mit c=a/b zu. Für c=0 ist F(x(t+1))= F(x(t)) Für c>0 ist F(x(t+1))> F(x(t)), falls F(x(t)) ≠ 1 Für c<0 ist F(x(t+1))< F(x(t))

o Daher aI/bI ≥ 0 und aD/bD ≥ 0

Also, aI,bI,aD,bD ≥ 0

o Aus Effizienz:

aD ≤ 0 → bD ≤ 1, heißt also aD = 0 → bD ≤ 1,

aD > 0 → bD < 0 entfällt.

aI ≥ 0 → bI ≥ 1,

• es muß aI > 0, da sonst Fairness nicht zunimmt (siehe MIMD)

o Führt zu AIMD

Fairness (II)





Fairness (III)





TCP-Datenrate

o AIMD-Probingstrategie verursacht Verlustrate

o = verlorene Segmente / verschickte Segmente

o Mittlere Datenrate B = Bytes/Sek und Fehlerrate interagieren:

Erhöhung der Datenrate erhöht die Verlustrate Höhere Verlustrate verringert die Datenrate

o Experimente zeigen für Segmentlänge MSS und Umlaufzeit RTT:





TCP-DatenrateDer statische Fall

o Verfügbare Bandweite = n

o Durchschnittliche Datenrate:

B = 3/4 n

o Nach n/2 Runden Verlust: 1

o Ergibt:

o also





TCP-DatenrateEin stochastische Modell

o Paket geht mit W‘keit p verloren

o Anzahl fehlerfreier übertragener Pakete X ist exponentiell verteilt:

o Erwartete fehlerfreie Paketmenge : O(1/p) Rundenanzahl bis Datenratenhalbierung: O(1/p½) Erwartete Datenrate: O(1/p½) Aber: Welcher konstanter Faktor?

o Experimentell: (für verwandtes Modell bewiesen):





2. Kapitel

Der Web-Graph





Eigenschaften des WWW

o WWW: Speicher für Informationen Neues Medium Nicht geplant, unkoordiniert

• Im Gegensatz zu Stromnetz, Telefon, Straßen, Eisenbahn Trotzdem Gesetzmäßigkeiten Selbstorganisation Ändert sich dauernd

o Analyse der Webstruktur ermöglicht Bessere Suchmaschinen Automatisch erzeugte Webverzeichnisse Gezielte Suchdienste Filter





Der Webgraph

o GWWW:

Statische HTML-Seiten sind Knoten Links sind gerichtete Kanten

o Ausgrad eines Knoten: Anzahl Links auf einer Webseite

o Eingrad eines Knoten: Anzahl der Links zu einer Webseite

o Gerichteter Pfad von Knoten u zu Knoten v: Folge der Webseiten, um von u zu v durch Links zu kommen

o Ungerichteter Pfad (u=w0,w2,…,wm-1,v=wm) von Knoten u zu Knoten v: Für alle i:

Von wi zu wi+1 existiert Link oder umgekehrt

o Starke (schwache) Zusammenhangskomponente: Knotenmenge, in der (un-)gerichteter Pfad von jedem Knoten zu

jedem anderen existiert





Ein-/Ausgradverteilung

o Ein-/ und Ausgrade sind Paretoverteilt, d.h. Ein/Ausgrad i erscheint mit Häufigkeit ~ 1/iα

o Experimentell überprüft von Kumar et al 97: 40 Mio Webseiten Barabasi et al 99: Domain *.nd.edu + Webseiten im Abstand 3 Broder et al 00: 204 Mio Webseiten (Scan Mai+Okt. 1999)





Ein-/Ausgradverteilung von Gn,p (I)

o Zufallsgraph Gn,p:

n Knoten Jede gerichtete Kante erscheint mit unabhängiger W’keit p

o Kann der Webgraph durch Gn,p beschrieben werden?

o Erwarteter Ein/Ausgrad in Gn,p = (n-1)p

Da durchschnittl. Grad in GWWW konstant, wähle

Betrachte feste Webseite r• Sei X die Anzahl der Links auf r

• Sei Xi =1 wenn Link nach i existiert, sonst 0

• Dann ist P[Xi=1]=p und P[Xi=0]=1-p





Ein-/Ausgradverteilung von Gn,p (II)

o Untersuche W’keit, dass mindestens k Links erscheinen

1. Versuch: Markovs Ungleichung

Es gilt

Dann ist:

Kein Widerspruch zu Paretoverteilung





Ein-/Ausgradverteilung von Gn,p (III)

o Untersuche W’keit, dass mindestens k Links erscheinen

2. Versuch: Chebyshevs Ungleichung

Es gilt, da alle Xi unabhängig:

Dann ist:

Kein Widerspruch zu Paretoverteilung





Ein-/Ausgradverteilung von Gn,p (IV)

3. Versuch: Chernoff Schranke

Für unabhängig Zufallsvariablen Xi und mit

Dann ist für

Damit ist für die W‘keit ≤

Für alle n Knoten ist diese W‘keit damit ≤

Widerspricht Paretoverteilung





Pareto-Verteilung (I)

o Diskrete Paretoverteilung für x {1,2,3,…}

mit konstanten Faktor

Es gilt

o Heavy-Tail-Eigenschaft: Nicht alle Momente E[Xk] sind definiert Erwartungswert existiert, gdw, α>2 Varianz und E[X2] definiert, gdw. α>3 E[Xk] definiert, gdw. α>k+1

o Dichtefunktion der kontinuierlichen Paretoverteilung für x>x0





Pareto-Verteilung (I)

o Beispiele für Paretoverteilungen

Pareto 1897: Privatvermögen in Bevölkerung Yule 1944: Wortlängen in Sprachen Zipf 1949: Größe von Städten Länge gewisser Molekülketten Dateilängen in Unix-Filesystem ….

Zugriffshäufigkeit von Webseiten Besuchshäufigkeit einzelner Websurfer auf einer

bestimmten Seite …





Zusammenhangskomponenten

o Starke und schwache Zus.-komponenten sind Paretoverteilt

o Riesige schwache Zus.-Kompontente mit 91% aller Seiten

o Größte starke Zus.Komponente nur 28% Durchmesser ≥ 28 Wo ist der Rest?





Ein Bild des Webgraphen

Weberfassung durch Altavista Mai+Oktober 1999:

Documents

Vorlesung Sommersemester 2002