Peer-to-Peer-Netzwerke: Algorithmen und Methoden

101
    6.2 Leaf-Set L eines Peers in Pastry . .............................. 102
    6.3 Die drei Nachbarschaftsklassen eines Pastry Peers . ............... 103
    6.4 Die Nachbarschaft eines Pastry Peers als Netzwerkgraph........... 104
    6.5 Routing-Algorithmus fur Pastry ................................ 105
    6.6 Einfugen eines Peers in das Pastry Netzwerk ..................... 107
    6.7 Beim Routing zuruckgelegte Distanzen in der Latenzmetrik. ....... 110
    6.8 Durchschnittliche Anzahl von Hops beim Routing . ............... 112
    6.9 Verteilung der Hop-Distanzen beim Routing . .................... 112
    6.10 Latenzzeiten beim Routing in Pastry verglichen mit den Latenzzeiten beim Routing in einem vollstandigem Netzwerk....... 113
    6.11 Gute der Routing-Tabelle von Pastry ............................ 114
    6.12 Ausschnitt der Nachbarschaft eines Peers mit ID 4227 ............. 116
    6.13 Publikation von Objekten im Tapestry-Netzwerk .................. 118
    6.14 Routing im Tapestry-Netzwerk ................................. 120

    7.1 Das Butterfly-Netzwerk BF(3) ................................. 127
    7.2 Die Butterfly-Kanten von Viceroy .............................. 130
    7.3 Links- and Rechtskanten des kontinuierlichen Graphen des Distance-Halving-Peer-to-Peer-Netzwerks ....................... 137
    7.4 Durch die Diskretisierung eines kontinuierlichen Graphen entsteht das Distance-Halving-Netzwerk . .............................. 138
    7.5 Das Prinzip der vielfachen Auswahl beim EinfUgen eines Peers. .... 139
    7.6 Routing mittels Linkskanten and Ruckwarts-Linkskanten im Distance-Halving-Netzwerk ................................... 141
    7.7 Ein alternativer Routing-Algorithmus mit Rechtskanten and Ruckwarts-Rechtskanten fur das Distance-Halving-Netzwerk....... 141
    7.8 Routing im Distance-Halving-Netzwerk mit Linkskanten........... 142
    7.9 Congestion-optimierter Suchalgorithmus fur das Distance-HalvingNetzwerk ................................................... 143
    7.10 Routing im Distance-Halving-Netzwerk mit Links- and Rechtskanten. 143
    7.11 Die Shuffle-Operation ........................................ 145
    7.12 Die Exchange-Operation ...................................... 145
    7.13 Die Shuffle-Exchange-Operation ............................... 146
    7.14 Anwendung der Shuffle- and Shuffle-Exchange-Operation.......... 147
    7.15 Das De-Bruijn-Netzwerk DB(4) ................................ 148
    7.16 Das De-Bruijn-Netzwerk fur 16 Knoten. Die Knoten sind sortiert auf dem Ring aufgetragen ..................................... 149
    7.17 Transformation des De-Bruijn-Graphen in ein Koorde-Peer-to-Peer- Netzwerk ................................................... 150
    7.18 Routing-Algorithmus fur Koorde ............................... 152
    8.1 Ein Beispiel eines Tries ....................................... 156
    8.2 Der Morse-Code als Beispiel fur einen Binar-Trie ................. 157
    8.3 Beispiel eines P-Grid-Netzwerks ............................... 158
    8.4 Eine einfach verkettete Liste ................................... 162
    8.5 Die Skip-Liste ............................................... 163
    8.6 Aufbau eines Skip-Graphen . .................................. 165
    8.7 Ein vollstandiger Skip-Graph .................................. 166
    8.8 Baumformige Struktur eines Skip-Graphen . ..................... 166
    8.9 Suche nach dem Schlusselwort f (Name-ID) in Skip-Net .......... 168
    8.10 Suche nach der Num-ID 111 in Skip-Net ........................ 169
    8.11 Rotations operation fur eine deterministische Version von Skip-Net.. . 171
    9.1 Haufigkeit der Ausgrade im Gnutella-Netzwerk (Messung im Marz 2001) [54] .................................................. 175
    9.2 Anzahl der Verbindungen von Internet-Routern (vertikale Achse), sortiert nach dem Rang (horizontale Achse) im Dezember 1998 [62]. 177
    9.3 Anzahl and Haufigkeit eingehender and ausgehender Links auf Web-Seiten im Mai 1999 [65] .................................. 178
    9.4 Small-World-Netzwerke ...................................... 180

    9.5 Die Lokal-Verbindungen in Kleinbergs Modell [70] ............... 181
    9.6 Die Lokal- and Fernverbindungen eines Knotens v in Kleinbergs Modell [70] ................................................. 182
    9.7 Einfugen eines Knotens im Small-World-Netzwerk Modell von Barabasi and Albert [63] (m = 2) .............................. 182
    9.8 Die Simple Switching-Operation ............................... 186
    9.9 Die 1-Flipper-Operation