TU Wien:Peer-to-peer Systems VU (Bessler)/Mögliche Pruefungsfragen 2010-01-20

What is meant by content-centric routing in P2P networks?

Its founding principle is that a communication network should allow a user to focus on the data he or she needs, rather than having to reference a specific, physical location where that data is to be retrieved from.

This approach comes with a wide range of benefits such as content caching to reduce congestion and improve delivery speed, significantly simpler configuration of network devices (since end points are moot), and building security (both authentication and ciphering) into the network and at the data level.

This approach may pose problems for certain types of web activities, for instance VoIP and instant messaging. But the VoCCN paper explains that VoIP is still possible. [1] --NonSense 23:43, 18. Jan. 2010 (CET)

Content is usually addressed through unstructured identifiers derived from the content with a hash function. Consequently, data is no longer addressed by location (the address of the server) but by the data itself. With multiple copies of a data item, queries may locate any one of those copies. Thus, Peer-to-Peer systems locate data based on content in contrast to location-based routing in the Internet. (R.Steinmetz and K. Wehrle, "Peer-to-Peer Systems and Applications", pp. 10-11, Springer, Berlin Heidelberg, 2005) --NonSense 17:09, 23. Feb. 2010 (CET)

Indirection principle in P2P networks?

• was fehlt hier noch? Konnte im Mahlmann nichts finden... --E0525176 11:45, 22. Feb. 2010 (CET)
• nothing found neither in Peer-to-Peer Systems and Applications nor in web --NonSense 17:36, 23. Feb. 2010 (CET)
• 1.Overview 07.10.2009: Folien 12-13
• Indirection in space
  • different from IP adressing
  • logical (content-based) IDs, routing to thouse IDs: "Content-addressable" network
• Indirection in Time
  • send and receive are temporally independent: rendez-vous
  • persistence guaranteed via soft state:
  • "publisher" requests TTL on storage
  • republishes as needed
• Metaphor: Distributed Hash Table

How does the i3 service work?

• konnte im Mahlmann nur das Kapitel 12.1 IP-Multicast finden, ist nicht aber das, was wir suchen, oder? --E0525176 11:57, 22. Feb. 2010 (CET)
• 6.Application Layer Multicast and Load Balancing 18.11.2009: Folien 14-15
• i3 = Internet Indirection Infrastructure
• the i3 service provides support for mobility, multicast, anycast and service composition
• goal: decouple the act of sending a packet from receiving it
• concept
  • logical identifier id (channel, topic...)
  • consumers subscribe to id by inserting triggers t(id, addr), where addr is IP address or another identifier for the destination of the packet
  • publisher sends packets p(id, data)
• a node sends p(id, data): at the node responsible for id, i3 will search for a trigger t(id, addr) and forward data to addr; i3 ids are matched with those in triggers using longest prefix matching
• i3 realizes application layer multicast
• for most structured P2Ps a conceptual interface can be defined to route messages between peers and to notify higher layer when the destination node has been reached
• Advantage: describe higher level application protocols (i3, DHT, scribe, etc...)

How i3 works [2], i3 paper [3], another i3 paper[4] --NonSense 17:50, 23. Feb. 2010 (CET)

Compare Node Degree vs. Network Diameter in different P2P

• Der Grad eines Netzwerks ist die maximale Anzahl von Nachbarn eines Peers und der Durchmesser ist die Länge des längsten aller kürzesten Pfade zwischen zwei Peers im zugehörigen Verbindungsgraphen des Netzwerks.
• Bezeichne im Folgenden d den Grad eines Netzwerks. Somit besitzt ein Peer höchstens d direkte Nachbarn und höchstens d i Nachbarn in Distanz kleiner gleich i.
• Damit ein Netzwerk den Durchmesser k besitzt, muss $d^{k}\geq N$gelten, woraus $k\geq {\frac {log(N)}{log(d)}}$folgt. Es gibt also einen Trade-Off zwischen Grad und Durchmesser eines Netzwerks.
• Um zum Beispiel einen konstanten Durchmesser c zu erreichen, muss ein Netzwerk mindestens den Grad n^(1/c) besitzen. Auf der anderen Seite impliziert ein konstanter Grad, dass das Netzwerk mindestens einen Durchmesser von Ω(log n) haben wird.
• CAN mit einem polynomiellen Durchmesser und einem konstanten Grad nicht sonderlich effizient
• Chord, Pastry und Tapestry sind mit logarithmischem Grad und Durchmesser nicht optimal
• Gnutella hat sehr kleinen Grad und kleinen Diameter--NonSense 22:14, 3. Mär. 2010 (CET)
• ein effizientes Peer-to-Peer-Netzwerk mit konstantem Grad und logarithmischem Durchmesser:
  • Viceroy
  • Distance-Halving Netzwerk und Koorde (reduzieren nochmals den Grad und verwenden eine einfachere Netzwerkstruktur als Viceroy)
  • alle drei verwenden verteilte Hash-Tabellen für die Zuordnung von Daten zu Peers
• die Umsetzung der verteilten Hash-Tabellen geschieht dabei weitgehend wie im Chord-Netzwerk, d.h., Peers und Daten werden eindeutige Positionen in einem eindimensionalem Raum zugewiesen, welcher als Ring betrachtet wird. Ein Datum wird jeweils von demjenigen Peer verwaltet, das der Position des Datums in aufsteigender Zählrichtung auf dem Ring folgt

--E0525176 09:25, 24. Feb. 2010 (CET)

Small world models, preferential attachment (Barabasi & Albert)

• 2.Unstructered P2P networks 14.10.2009: Folien 13-16
• Milgramexperiment (1967)
  • copies of a letter to a friend were distributed to random persons in Nebraska (with destination person name, town)
  • each person had to forward the letter only to their friends
  • the letter came to destination after approx. 6 hops !!!
• due to this experiment, social networks have small diameter and large clustering coefficient -> described as "small world networks"
  • where clustering coefficient is defined as avg(C(i))
    • $C(i)={\frac {|\{(j,k)\in E|j,k\in N(i)\}|}{d(i)(d(i)-1)}},N(i)=\{j|(i,j)\in E\},d(i)=|N(i)|$
• The model of Watts and Strogatz
  • based on the observation, that in social networks a clique occures much more frequently than for example in random graphs
    • clique: complete part of a graph (vollständiger Teilgraph); a set S of nodes, where each node in the set S is connected with each node in the same set S
  • tries to build a small world network (between order and chaos)
    • start with ring in which each node links to the node k/2 hops away (on both right and left side)
      • this is similar to Pastry, but without the set M of local neighbours and without the routing table
    • replace with probability p an original link with another link to a random node
    • that means, if p=0, the network does not change; but if p=1, the network is fully random organized
    • but by p=0.1, many of the before existing cliques stay unchanged and thanks to the new random edges, the diameter heavy decreases
    • result: the diameter decreases
    • disadvantage: homogeneous degree, does not model well small world
• Better small world models: Kleinberg Model
  • Kleinberg indicated, that the Miligramexperiment was based on Intuition: each participant decided, who should be the next participant (node) to minimize the hops
  • a lattice nxn and defined distance between
  • two nodes with coordinates (i,j) and (k,l)
    • $d((i,j),(k,l))=|k-i|+|l-j|$
  • Zusätzlich zu den Lokal-Verbindungen erhält jeder Knoten noch einige Kanten zu weiter entfernten Knoten, die dann als Abkürzungen beim Routing dienen. Diese Verbindungen werden als Fern-Verbindungen bezeichnet. Durch eine vorsichtige Wahl dieser Fern-Verbindungen mittels einer über dem Abstand gewichteten Wahrscheinlichkeitsverteilung konnte Kleinberg zeigen, dass in diesen Graphen jedes Paket mit O(log^2 n) Schritten zum Ziel gesendet werden kann. Das Modell von Kleinberg ist insbesondere in der Auswahl der Fernverbindungen komplexer und flexibler als das Modell von Watts und Strogatz.
  • two arbitrary nodes u and v are connected by an edge with probability
    • $[d(u,v)]^{-r}$ -> inverse r-th power distribution
  • Kleinberg shows that there is a decentralized algorithm that constructs a path between any two nodes of length O(log^2 n), only if r=2
  • if r<>2 the length polynomial (sublinear) with n
  • the decentralized algorithm is: choose a contact (next node) as close as possible to the target in terms of lattice distance!
• preferential attachment (Barabasi & Albert)
  • einen völlig anderen Weg zum Aufbau eines Small-World-Netzwerks gehen Barabasi und Albert
  • Ausgehend von einem kleinen Startgraphen werden sukzessive Knoten mit jeweils m Kanten eingefügt.
  • Nun wird Paretos Beobachtung verwendet: ”rich gets richer“ . So wählt ein neuer Knoten seine Nachbarn mit einer Wahrscheinlichkeit, die proportional zum Grad dieser Knoten ist. Somit erhalten Knoten, die bereits einen hohen Grad haben, mehr neue Kanten (und damit einen noch höheren Grad) als Knoten mit geringem Grad.
  • Es zeigt sich, dass das entstehende Netzwerk einen logarithmischen Durchmesser besitzt und dass die Gradverteilung einer Pareto-Verteilungmit Exponent 2,9 +/- 0,1 genügt.

--E0525176 13:47, 22. Feb. 2010 (CET)

Explain the notions Pareto- and scale free distribution

• 2.Unstructered P2P networks 14.10.2009: Folien 7, 11-12
• distribution of the node degree
  • So gesehen handelt es sich in der Häufigskeitsverteilung der Ausgrade (Anzahl der Nachbarn) nicht um ein Resultat eines Algorithmus, sondern um ein soziales Phänomen
  • Pareto-Verteilungen besitzen die so genannte Heavy Tail-Eigenschaft. Damit wird beschrieben, dass für große Werte die Wahrscheinlichkeiten im Vergleich zu Poisson-Verteilungen oder geometrischen Verteilungen nur sehr langsam abnehmen.
  • Power law ${\textstyle p(d)=c*d^{-1.4},0<d\leq 7}$ avg(d) =2.2, var(d)=1.63
  • Power law or Pareto distribution (Fritz Pareto) is a heavy tail distribution, encountered in Internet, and social networks
• real world power law (scale free) distributions
  • TBD: ist hier die Zipf-Verteilung aus Mahlmann gemeint?
  • Definition: if probability that a node interacts with d other nodes is: TBD

--E0525176 14:36, 22. Feb. 2010 (CET)

Properties of Gnutella network topologies

• 2.Unstructered P2P networks 14.10.2009: Folien 17
• wie auch bei Napster handelt es sich bei Gnutella um ein File-Sharing-Netzwerk. Im Gegensatz zu Napster ist Gnutella jedoch ein Peer-to-Peer-Netzwerk, das ohne zentrale Strukturen auskommt.
• das Problem von Bootstrapping wird in Gnutella folgendermaßen umgesetzt:
  • beim erstmaligen Aufruf eines Gnutella-Clients wird eine mit der Software gelieferte Liste von Peers bzw. IP-Adressen verwendet
  • diese werden der Reihe nach durchprobiert, bis ein gerade aktiver Peer gefunden wird
  • von diesem aus werden die nächsten Nachbarn und deren Nachbarn bis zum k-nächsten Nachbarn abgefragt
  • aus diesen Rückmeldungen aktiver Peers wird eine eigene Liste von Gnutella Peers aufgebaut
  • hat ein Peer erst eine solche Liste gewonnen, so wird diese gespeichert und beim nächsten Start anstelle (oder zusätzlich) zu der in der Software gespeicherten verwendet um sich in das Netzwerk einzubinden.
• das Protokoll, das auf TCP-Verbindungen aufbaut, benutzt die fünf Nachrichtentypen: Ping, Pong, Query, QueryHit und Push
• The Gnutella P2P network has
  • high clustering coefficient
  • low diameter
  • power law node degree distribution
• the creation of this topology is through self organization
• with respect to path length, the model Barabasi-Albert best approximates Gnutella
• im Gegensatz zu Napster liegt hier zum ersten Mal ein echtes Peer-to-Peer-Netzwerk vor, das vollständig ohne zentrale Kontrollmechanismen auskommt
• die Vorteile von Gnutella beruhen auf der verteilten Netzwerkstruktur
• Gnutella ist extrem robust und praktisch unangreifbar
• die zufällige Netzwerkstruktur ist auch sehr gut skalierbar, d.h., viele Knoten können ohne Einbußen in der Leistungsfähigkeit aufgenommen werden
• das Hauptproblem ist, dass durch die tiefenbeschränkte Suche nur in einem Teilnetzwerk nach der Zieldatei gesucht wird. Ist die gesuchte Datei unter den Peers weit verbreitet, dann wird sie schnell und zuverlässig gefunden. Selten vorhandene Dateien werden nur gefunden, wenn sie zufällig von einem Peer im lokalen Umfeld bereitgestellt werden
  • dieses Problem könnte man durch Erhöhung des TTL-Eintrags umgehen, wenn dadurch nicht der zweite Nachteil von Gnutella noch verschärft würde
• dies ist das Nachrichtenaufkommen bei einer Suche. Da es völlig unklar ist, wo sich eine gesuchte Datei befindet, muss zwangsweise eine genügend große Teilmenge aller Peers befragt werden, um zumindest einen Großteil der Dateien im Netzwerk auffindbar zu machen.
• Es gibt eine Reihe von Verbesserungvorschläagen, um das Nachrichtenaufkommen zu verringern. Eine Möglichkeit besteht zum Beispiel darin, Random Walks anstelle von Broadcasts für die Suche zu verwenden. Bei einem Random-Walk wird eine Nachricht nicht an alle Nachbarn, sondern nur an einen zufälligen weitergereicht. Auf diese Weise wird die Suche weiter in das Netzwerk hineingereicht, ohne das Nachrichtenaufkommen stark zu erhöhen.
• Ein weiterer Vorschlag ist die passive Replikation von Information entlang eines Pfads. Hierbei werden Ergebnislisten gespeichert, und neue Anfragen nach demselben Dokument können dann sofort ohne weitere Suchnachrichten beantwortet werden.

--E0525176 09:51, 24. Feb. 2010 (CET)

Chord Routing

• 3. Structured P2P Principles, Chord 21.10.2009: Folien 15
• a search is always forwarded to the closest peer
• Um die verteilte Hash-Tabelle in einem Netzwerk zu realisieren, genügt ein Minimum an Routing-Information: Jeder Peer muss lediglich seinen Vorgänger und Nachfolger auf dem Chord-Ring kennen.
• Die Suche nach einem Datum kann dann einfach entlang der Ringstruktur geschehen, in dem die Suchanfrage solange weitergeleitet wird, bis der erste Peer erreicht wird, dessen Hash-Wert größer als der des gesuchten Datums ist.
• Abgesehen davon, dass diese Art der Suche recht viel Zeit, nämlich linear in der Anzahl der Peers, benötigt, ist ein solches Ringnetzwerk auch nicht sehr fehlertolerant. Schon beim Ausfall zweier Peers zerfällt ein Ring in zwei Zusammenhangskomponenten.
• Um diese beiden Probleme zu beheben, besitzt jeder Peer des Chord-Netzwerks neben Zeigern auf seinen Vorgänger und Nachfolger auf dem Chord-Ring noch so genannte Finger-Zeiger m.
• in a Chord ring of size m bit, any peer maintains up to m fingers, i.e. routing shortcuts
• the i-th finger of peer ${\textstyle Px}$ points to the successor of ${\textstyle x+2^{i-1}}$
• Ex.: The peer ${\textstyle P01}$ has its fingers at

  

  • $P11=succ(1+\{1,2,4,8\})$
  • $P23=succ(1+16)$
  • $P34=succ(1+32)$
  • $P66=succ(1+64)$
• very often the first fingers point to the direct successor
• m=7 => every peer has up to 7 fingers or O(log N) different fingers
• Damit ist die Chord-Datenstruktur sehr kompakt: Jeder Peer besitzt mit hoher Wahrscheinlichkeit lediglich eine Nachbarschaft logarithmischer Größe. Somit ist die im Chord-Netzwerk von einem Peer zu verwaltende Nachbarschaftsinformation auch im Fall von sehr vielen Netzwerkteilnehmern noch überschaubar gering.
• Das Vorgehen bei der Suche ist denkbar einfach: Ein Peer p, der nach einem Datum x mit Position $h'(x)=id$auf dem Chord-Ring sucht, überprüft zunächst, ob er das Datum x selbst verwaltet. Ist dies nicht der Fall, wird die Suchanfrage über einen der Finger-Zeiger an einen anderen Peer weitergeleitet. Hierbei wird immer der Finger-Zeiger gewählt, der am nächsten an die Postion $h'(x)=id$auf dem Chord-Ring zeigt und gleichzeitig noch vor der Position id liegt. Auf diese Weise wird die Anfrage an den letzten Peer p′ vor Position id des Chord-Rings geleitet. Der Nachfolger von p′ ist dann der für das Datum x verantwortliche Peer.

--E0525176 15:25, 22. Feb. 2010 (CET)

Describe the stabilize procedure in Chord

• 3. Structured P2P Principles, Chord 21.10.2009: Folien 19
• Beim Einfügen eines neuen Peers p [n+1] der Zuständigkeitsbereich des für die Position h (p [n+1]) des Chord-Rings verantwortlichen Peers p i zwischen p i und p [n+1] aufgeteilt wird. Um dies zu initiieren, muss Peer p [n+1] also zunächst Peer p i kontaktieren. Dies geschieht ausgehend von einem beliebigen, Peer p [n+1] bereits bekannten, Peer mit Hilfe des Such-Algorithmus und benötigt mit hoher Wahrscheinlichkeit lediglich O(log n) Nachrichten.
• Wurde der Bereich des Chord-Rings aufgeteilt und p [n+1] in die Ringstruktur eingebunden, gilt es noch die Finger-Zeiger anzupassen. Hier müssen einerseits die ausgehenden Finger-Zeiger von p [n+1] aufgebaut werden und andererseits Finger-Zeiger von Peers aktualisiert werden, die in den Bereich zwischen p [n+1] und seinem Vorgänger auf dem Chord-Ring zeigen. Betrachten wir zunächst die Finger-Zeiger von p [n+1]. Wir haben bereits gesehen, dass ein Peer mit hoher Wahrscheinlichkeit nur O(log n) verschiedene Finger-Zeiger besitzt, so dass das Anpassen der Finger-Zeiger von p [n+1] mit hoher Wahrscheinlichkeit mit O(log^2 n) Nachrichten geschehen kann.
• Die Frage, wie viele Nachrichten für das Anpassen der auf p [n+1] zeigenden Peers notwendig sind, ist schwieriger zu beantworten. Wir überlegen uns zunächst, wie viele Peers auf p [n+1] zeigen werden. Das folgende Lemma liefert eine obere Schranke für diesen Wert:
  • Die Anzahl der Peers, die einen Finger-Zeiger auf einen Peer p besitzen, ist im Erwartungswert (log n) und mit hoher Wahrscheinlichkeit beschränkt durch O(log^2 n).
• Wenden wir uns wieder der Anzahl benötigter Nachrichten zum Einfügen eines neuen Peers p [n+1] zu. Wir wissen jetzt, dass mit hoher Wahrscheinlichkeit nicht mehr als O(log^2 n) Peers auf p [n+1] zeigen werden. Diese Peers gilt es nun effizient über den neuen Netzwerkteilnehmer p [n+1] zu benachrichtigen. Wir nutzen aus, dass die O(log^2 n) Peers in O(log n) zusammenhängenden Bereichen liegen und betrachten zunächst nur einen dieser Bereiche. Um einen Peer in diesem Bereich zu benachrichtigen, können wir den Suchalgorithmus verwenden. Um dann die weiteren O(log n) Peers dieses Bereichs zu informieren, sind nur O(log n) weitere Nachrichten erforderlich, wenn die Nachricht entlang des Chord-Rings weitergeleitet wird. Des Weiteren ist der Aufwand zur Anpassung des jeweiligen Finger-Zeigers konstant. Somit benötigen wir O(log n) Nachrichten für die Anpassung der Finger-Zeiger aller Peers eines dieser Bereiche. Da es insgesamt O(log n) dieser Bereiche gibt, werden mit hoher Wahrscheinlichkeit O(log^2 n) benötigt, um alle auf p [n+1] zeigenden Finger-Zeiger anzupassen. Durch unsere Überlegungen ergibt sich folgendes Theorem:
  • Um einen neuen Peer in Chord einzufügen, genügen mit polynomiell hoher Wahrscheinlichkeit O(log^2 n) Nachrichten.

--E0525176 16:04, 22. Feb. 2010 (CET)

What are the advantages and disadvantages of proximity neighbor selection (PNS) routing?

• 3. Structured P2P Principles, Chord 21.10.2009: Folien 22

• TBD missing terms (copy&paste)

• until now, the path length bound was the number of hops
• what about path latency ? Not considered by standard Chord
• Unser Ziel ist es, Routing-Zeiten im Netzwerk zu reduzieren. Um dies zu erreichen, werden wir versuchen, die Chord-Verbindungsstruktur dahingehend zu optimieren, dass die Finger-Zeiger der Peers zu möglichst latenznahen Peers führen — also Peers, die im Underlay-Netzwerk, dem Internet, nicht weit entfernt sind.
• improvement: Proximity neighbor selection (PNS, [Gummadi et al])
• slight modified setup of Chord fingers: instead to choose the next peer following the pointer p+2i mod m, choose among the next k nodes the one with smallest latency (ping), e.g. k=16
• Das Routing in Chord bleibt bei Verwendung von Proximity-Neighbor-Selection unverändert: In jedem Schritt wird derjenige Peer ausgewählt, der dem Ziel nächsten liegt, ohne dieses zu überschreiten. Experimente zeigen, dass es in der Praxis genügt, jeweils den latenznahesten aus k = 16 Peers zu wählen, anstatt alle in Frage kommenden Peers zu betrachten.
• what is the latency?
  • assume & is the average of a uniform distributed latency per routing hop
  • there are h= O(log N) hops
  • for the last h-th hop to destination, there exists one alternative, with avg latency, for the hop h-1 the latency
  • in total considering the response latency
• Conclusion: with PNS, the total latency is quite independent of N !
• für nähere Informationen, siehe: Mahlmann (Seite 93, bis "5.4 Zusammenfassung und Vergleich")

--E0525176 09:45, 23. Feb. 2010 (CET)

What are the main functions of the key based routing API

• 3. Structured P2P Principles, Chord 21.10.2009: Folien 26-28
• low API used to route messages between peers and to notify higher layer when the destination node has been reached
• void route (key->K, msg->M, nodehandle->hint)
  • hint: optional, specify first hop node
• Forward (key->K, msg->M, nodehandle->nextHopNode)
  • upcall that notifies the higher layer that the message has to be forwarded to nextHopNode
  • qpplication my overwrite all parameters
• Deliver (key->K, msg->M)
  • upcall at the destination peer
• Nodehandle[] local lookup(key->K, int->num, boolean->safe)
  • returns a list of next hop nodes
  • if safe=true, the returned number is higher than ; of faulty nodes
• nodehandle [] neighborSet (int->num)
  • up to num neighbors to the local node (in the hash space) are returned
• replicaSet(key->k, int->max rank)
  • returns a set of up to max rank nodehandles on which replicas of the object at key k can be stored
• update(nodehandle->n, bool->joined)
  • upcall to notify the application that node n has joined or left the neighbor set
• boolean range (nodehandle->N, rank->r, key <->lkey, key->rkey
  • provides the range of keys for which the node currently replica root is

Explain the Kademlia network structure

• 4. Structured P2P networks: Structured P2P networks: CAN, Kademlia, P-Grid 28.10.2009: Folie 17-18
• identifier space [0-2m-1], m=160 bits
• Mapping
  • proposed to use hash function sha1(.), e.g. node_ID=sha1(node_IP)
• Distance between nodes and objects uses XOR metric d(x, y) = x y
  • e.g:x=00110011, y=01000001 d(x,y) = 01110010 = 2+16+32+64 = 114
• Routing table
  • each bit of the node ID contains a list of node entries (node ID, IP address, port etc.)
  • each list forms a k-bucket with maximally n nodes
  • e.g, table for ID=110: 3 bits, 3 buckets: (000, 001, 010), (100, 101) and (111)
  • only the longest connected nodes are selected among the k candidates for a bucket
• erhalten Peers durch Anwenden einer Hash-Funktion auf die IP-Adresse eine ID (und einen Zeitparameter)
• jeder Peer unterhält Kanten zu den k-nächsten Peers bezüglich der XOR-Metrik auf diesen IDs
• die XOR-Metrik ist definiert als: XOR-Distanz(A, B) = A ⊕ B
• die bitweise XOR wird also als ganze Zahl interpretiert. Somit führen die 160-Bit-Adressen zu 2160 verschiedenen Adressen.
• Für jedes Abstandsintervall ${\textstyle d\in [2^{i},2^{i+1}-1]}$ für ${\textstyle i\in \{0,\ldots ,159\}}$unterhält jetzt jeder Peer k Nachbarn, wobei diese nach dem Least-Recently-Used-Prinzip ausgewählt werden
• Damit wird bei näherer Betrachtung genau das Plaxton-Routing-Netzwerk benutzt
  • hierbei wird das binäre Alphabet genutzt und k Nachbarn aus der primären Nachbarschaft gewählt
  • neben dem Verzicht auf weitere Zeiger ist der Hauptunterschied, dass die IDs alle 24 Stunden erneuert werden, so dass alte Zeiger nicht aktualisiert werden müssen, sondern nach 24 Stunden einfach gelöscht werden können
• der Grad von Kademlia ist daher maximal 160*k. Wenn die Routing-Tabelle korrekt aktualisiert worden ist, dann kann man nach einem Datum suchen, indem man wie beim Plaxton-Routing mit jedem Routing-Schritt ein Bit der Adresse anpasst. Die Suche nach einem Datum ist daher nach O(log n) Sprüngen erfolgreich. Das Kademlia-Netzwerk hat somit einen erwarteten Durchmesser von O(log n).
• der Unterhalt von Kademlia ist extrem einfach. Benachbarte Peers tauschen ihre Information über Nachbarn aus. Finden sich so nähere Nachbarn, wird der Link auf diese gesetzt und die Verbindung zu den entfernteren beendet. Mit diesem selbstorganisierenden Algorithmus repariert sich das Peer-to-Peer-Netzwerk.

--E0525176 10:05, 24. Feb. 2010 (CET)

Consider the new RELOAD internet draft. What is the difference to DHT protocol such as Chord?

• TBD see RELOAD draft

Pastry routing and locality

• 5. DHT Protocols Pastry & Tapestry 11.11.2009: Folien 5-11, 14
• zum Nachlesen in Mahlman: Routing auf Seiten 102-105, Lokalität auf Seiten 108-111
• Prefix routing: given the routing table of the current node, send the message to the node from the routing table that has the longest common prefix with the destination ID
• if there is no matching node, table cell remains empty
• parameter b, $2^{b}$ is the base
• parameter L number of symbols, e.g. L= 8 (3*8=24 bit IDs)
• the leaf-set consists of L nodes
  • each node maintains IP addresses of L/2 nodes numerically closest larger node IDs L/2 nodes with smaller nodeIDs, respectively
    • routing efficiency/robustness
    • fault detection (keep-alive)
    • application-specific local coordination
  • Example: leaf set of noded 303 is (L=4): 213,222, 321,323
    • in the neighbourhood of the destination, routing switches from prefix to another mechanism: leaf set nodes
• Neighbour nodes
  • set of M nodes, |M|=2b
  • lowest latency (or geographical near)
  • not used for routing
• Example: Peer preceives a query for peer q
  • 1. First, check if q is in p‘s leaf set, then route to its target,
  • 2. Otherwise, it is routed to a node in ps routing table whose common prefix with q is at least one bit longer (1011)
  • 3. If neither 1. nor 2. are fulfilled, the query is sent to a node in the node state, which shares the same number of digits with q as p does, but is numerically closer to q

--E0525176 10:53, 24. Feb. 2010 (CET)

Pastry versus Tapestry

• 5. DHT Protocols Pastry & Tapestry 11.11.2009: Folie 25
• same routing principle: Plaxton, Rajamaran and Richa (PRR). Dieses stellt eine Verallgemeinerung von Routing auf dem Hypercube dar, wobei die entstehende Kommunikationslatenz nur konstant größer ist als die auf dem schnellsten Pfad.
• Pastry
  • Die eigentliche algorithmische Beschreibung ist ungenau (zum Beispiel die Bestimmung der Menge M latenznaher Peers), und experimentelle Verifikation ersetzt hier analytische Untersuchungen.
    • uses heuristics (also in routing) instead of exact methods
    • combined prefix and leaf-set routing instead of clean model and analytical results
    • good implementations
    • robust through Leaf-Set
    • lässt sich praktisch besser umsetzen und ist durch die Einführung der Leaf-Sets sehr robust.
    • routing Table only for short-cuts, Leaf-set is enough for correct routing
• Tapestry
  • sehr nahe am Originalverfahren von Plaxton et al. gehalten und daher analytisch gut verstanden: Tapestry hat nachweisbare Performanzeigenschaften, wenn die Annahmen zutreffen.
    • analytical model, proven performance
    • consistent routing table
    • not completely self-organizing

--E0525176 09:56, 23. Feb. 2010 (CET)

Explain consistent hashing

• 3. Structured P2P Principles, Chord 21.10.2009: Folien 9-10
• consistent hashing was introduced in 1997 as a way of distributing requests among a changing population of web caches
• consistence ensures that the addition or removal of one cache does not significantly change the mapping of keys to caches
• in contrast, in most traditional hash tables, a change in the number of caches causes nearly all keys to be remapped
• Theorem „Consistent Hashing“
  • for any set of N nodes and K items, with high probability:
    • each nodes is responsible for at most ${\frac {(1+\epsilon )*K}{N}}$ items
    • when an (N+1)-st node joins or leaves the network, responsibility for only $O({\frac {K}{N}})$ items changes
• Verteilte Hash-Tabellen werden von CAN und Choord auf andere Weite umgesetzt
• Meldet sich nun ein neuer Peer im CAN an, so wird eines der Rechtecke in der Mitte halbiert, und der bisher Verantwortliche und der neue Peer erhalten je eine Hälfte. Somit bleibt die Zuordnung von Daten anderer Peers von dieser Einfügeoperation unberührt. Diese Eigenschaft wird Konsistenz genannt. Daher verwendet man für verteilte Hash-Tabellen mitunter auch den Begriff Consistent Hashing.
• Wenn die Hash-Funktion die Daten gleichmäßig auf das Quadrat verteilt, muss nur noch gewährleistet werden, dass den Peers gleich große Bereiche zugewiesen werden, um die Daten gleichmäßig auf die Peers zu verteilen.
• TBD: sollte mMn von jemandem einer Review unterzogen werden... --E0525176 11:04, 24. Feb. 2010 (CET)

How does P-Grid achieve load balancing?

• 4. Structured P2P networks: Structured P2P networks: CAN, Kademlia, P-Grid 28.10.2009: Folie 29
• Es beruht auf der Verwendung eines binären Suchbaums und der geeigneten Verteilung der Peers in dieser Datenstruktur
• a peer is associated with a path if other peers are not on the path
  • therefore peers are only on the leaves
• local load balancing idea
  • the paths (and the tree structure) are negotiated between neighboring peers in self-organized way:
    • if the neighoring subtree has different content size, then peers can move from the smaller to the larger content subtree
• Daher strebt P-Grid an, die Anzahl der Peers in einem Teilbaum proportional zu den dort gespeicherten Daten zu verteilen. Wenn also das Verhältnis $r=m_{0}/m_{1}$ der Datenmenge zweier benachbarter Teilbäume bekannt ist, dann kann man Peers gemäß der Wahrscheinlichkeit p, die sich aus der Gleichung $p/(1-p)=r$ ergibt, auf den linken Teilbaum verteilen und mit der Gegenwahrscheinlichkeit auf den rechten. Beim Einfügen muss nur noch beachtet werden, dass der andere Teilbaum nicht leer ist. Hierzu muss jeder Peer mindestens einen Peer aus dem anderen Teilbaum finden. Dieser Prozess wird durch das so genannnte Boot-Strapping gelöst.
• Da Peers nur in den Blättern des Netzwerkbaums liegen, sind die Pfadlängen des Baumes dynamisch. Im Idealfall ist die Anzahl der Peers proportional zu der Anzahl der Dateneinträge. Das wird durch P-Grid nicht garantiert. Außerdem müssen sämtliche Peers fortwährend überprüfen, inwieweit sich die Baumstruktur geändert hat. Um die Balancierung zu sichern, wird außerdem eine kontinuierliche Rebalancierung durchgeführt. Hierzu hat jeder Peer eine Minimal- und eine Maximalauslastung. Peers, die überlastet sind, versuchen die Daten auf den Nachbarbaum abzuwälzen. Wie bei der Defragmentierung von CAN wird dadurch der Baum an dieser Stelle kürzer.
• Die freien oder freigewordenen Peers suchen fortwährend nach überlasteten Peers. Ist ein solcher gefunden worden, so teilen sie bei diesem Peer den Baum weiter auf.

--E0525176 11:18, 24. Feb. 2010 (CET)

Lookup in Tapestry, consistency and surrogate routing

• 5. DHT Protocols Pastry & Tapestry 11.11.2009: Folien 26-36
• TBD: Lookup in Tapestry
• Peers, die Daten bereitstellen, werden in Tapestry Storage-Server genannt. Da ein Datum von mehreren Storage-Servern bereitgestellt werden kann, gibt es zusätzlich zu den Storage-Servern so genannte Root-Peers, die für bestimmte Objekte verantwortlich sind.
• TBD: Consistency (Mahlmann, Seiten 117-119)
• Surrogate Routing
  • Ein bislang vernachlässigtes Problem ist, dass die von MapRoots(ψ) gelieferten Peer IDs unter Umständen gar nicht im Netzwerk existieren. Dies ist sogar wahrscheinlich, da der Namensraum nur sehr dünn besetzt ist, um Kollisionen zu vermeiden. Ein anderes Problem sind die dadurch entstehenden Löcher in den Routing-Tabellen.
  • Die Lösung für dieses Problem wurde von den Tapestry-Autoren Surrogate-Routing genannt (übersetzt etwa: Ersatz-Wegewahl) und funktioniert wie folgt:
  • Wie zuvor wird schrittweise versucht, den Root-Server zu erreichen. Stößt man dabei auf ein Loch an der Stelle (z, j) der Routing-Tabelle eines Peers, so wird stattdessen nach (z, j+1) weitergeleitet. Handelt es sich auch dabei um ein Loch in der Routing-Tabelle, wird jeweils das nächst höhere j ∈ B gewählt und nach dem Erreichen der größten Ziffer aus B wird mit der Ziffer 0 fortgefahren. Dieser Vorgang wird so lange wiederholt, bis der gesuchte Peer erreicht wurde oder der aktuelle Peer keine Einträge in höheren Levels und nur den einen, über den er erreicht wurde, im aktuellen Level seiner Routing-Tabelle hat. Es gilt nun folgendes Theorem über das Verhalten des Surrogate-Routing:
    • Wenn Eigenschaft 1 (Konsistenz) gilt, dann wird durch Surrogate-Routing ein eindeutiger Peer erreicht, egal von wo im Netzwerk das Routing startet.
  • Surrogate-Routing benötigt für insgesamt n Peers höchstens O(log n) Hops, um das gewünschte Ziel zu erreichen, da mit jedem Schritt eine Ziffer an die gesuchte ID angepasst wird und mit hoher Wahrscheinlichkeit lediglich die ersten O(log n) Level der Routing-Tabellen mit Einträgen besetzt sind.

--E0525176 10:44, 23. Feb. 2010 (CET)

Scribe, join, lookup

• 6.Application Layer Multicast and Load Balancing 18.11.2009: Folien 7-13
• Scribe: Tree based multicast
  • Scribe [Castro, Druschel, Kermarec, Rowstron, 2002] is a application layer multicast system based on a pastry DHT
  • each multicast tree is based on a unique group and grpID, managed by the root node of that ID
  • Scribe supports multiple multicast sources per group
  • Scribe offers a simple API to applications
    • create(credentials, groupId) creates a group with groupId; Throughout, the credentials are used for access control
    • join(credentials, groupId, messageHandler) causes the local node to join the group with groupId; all multicast messages for that group are passed to the specified message handler
    • leave(credentials, groupId) causes the local node to leave the group with groupId
    • multicast(credentials, groupId, message) causes the message to be multicast within the group with groupId.
• when a node joins the group:
  • Jeder Peer, der sich einer Gruppe anschließen möchte, sendet einen Lookup zu dem Root-Peer, der die Group-ID verwaltet. Sobald auf dieser Route ein Peer gefunden wird, der zum Multicast-Baum dieser Gruppe gehört, wird der Pfad zu diesem Peer zum Multicast-Baum dieser Gruppe hinzugefügt. Die Information wird dann mittels dieses Baumes verteilt.
  • a join message is sent to grpID
  • each node on the path to grpID checks whether it is already a „forwarder“ of that group
  • if not, it creates an entry for grp, adds the preceeding node as child, forwards the message
  • if yes, accepts the preceeding node as a child, terminates forwarding the message.
• Reparatur und Kontrolle
  • Da der Multicast-Baum wie der Rest des Peer-to-Peer-Netzwerks den dauernden Veränderungen durch hinzukommende oder verschwindende Peers ausgesetzt ist, bedarf es einer ständigen Kontrolle, ob der Multicast-Baum noch intakt ist. Hierzu werden so genannte Herzschläge ausgesandt, das sind Kontrollnachrichten, die der Knoten, der die Group-ID verwaltet, an alle weiteren Knoten des Baums verschickt und weiterleitet. Wurde also ein Teil des Baums abgetrennt, so kann dies durch das Ausbleiben dieser regelmäßigen Kontrollnachrichten festgestellt werden. Der Multicast-Baum wird dann dadurch repariert, dass der Aufbaualgorithmus erneut ausgeführt wird.
• TBD: lookup, in Mahlmann nicht gefunden...

Distance Halving network has a route length of 2*log(n)+3. Explain!

• 7.Constant degree P2P networks 25.11.2009: Folien 7
• how many hops has a route between nodes x and y, |x-y| =d in DH network?
  • go from x and y using left-arcs
  • at each step the distance d becomes d/2 until 2 neighbours (linked) are found
  • since the intervals are > 1/(2n)
  • # Steps $<1/2k<1/(2n)$
  • $k<1+log(n)$
  • considering the path backwards+ 1 hop in the middle
  • route length: $2*log(n)+3$
• note we used only left-arcs
  • possibly there is congestion at the left side nodes
• TBD: sollte ggf. erweitert werden...

Draw a de Brujin Network with 8 nodes DB(3)

• TBD Folien-Verweis
• TBD: ist in Mahlmann auf den Seiten 144-148 sehr anschaulich erklärt, ich wage es nicht, hier sinvoll zusammenzufassen

--E0525176 12:28, 23. Feb. 2010 (CET)

What are the pros and cons of application layer multicast

• 6.Application Layer Multicast and Load Balancing 18.11.2009: Folien TBD

• TBD

How does the virtual server concept for load balancing work?

• 6.Application Layer Multicast and Load Balancing 18.11.2009: Folien 29-30
• each node is represented by a number of virtual nodes called virtual servers VS
• theory of consistent hashing suggests having O(log n) VS per node
• virtual servers can be transferred from overloaded (heavy) to light nodes
  • the light node does not become heavy
  • the transferred virtual server is the lightest to make the heavy node light
  • if no virtual server is heavy enough to make the heavy node light, transfer the heaviest virtual server
• how do they find each other?
  • randomly contacting other nodes
  • directories with information about heavy and light nodes
• TBD: ggf. Erweiterung notwendig, konnte im Mahlmann nichts finden...

--E0525176 12:34, 23. Feb. 2010 (CET)

How can a DHT use replication for load balancing?

• 6.Application Layer Multicast and Load Balancing 18.11.2009: Folien 31
• Definitions
  • replica invariance in Pastry: independent of node insertion, failures, Pastry maintains r replicas at the numerically (ID) closest nodes (among the leaf set)
  • replica set R: a set of nodes storing a certain item
  • any node of R can answer queries for reading the item
• basically, replica sets are proposed for fault tolerance, but they can be used to relief hot spots
• this only works, however, if nodes in the replica set are on paths towards the item ID and are only hit by a fair share of the queries
  • leaf set in Pastry, Predecessors on paths in Kademlia are good choices
  • successor list in Chord is a bad choice as they are not hit by queries
• TBD: braucht ggf. Erweiterung, konnte im Mahlmann nichts finden...

--E0525176 12:39, 23. Feb. 2010 (CET)

How would an adversary organize a Sybil attack on a DHT net?

• 12.Security issues in P2P (1) 09.12.2009: Folien 8-10
• Sybil: character of a book, schizophrenic woman with 16 personalities (names)
• Sybil attack: a malicious node creates multiple virtual nodes with different IDs that participate to the network
  • Hierzu gibt sich ein Peer als eine Vielzahl virtueller Peers aus und wird dadurch an mehreren Stellen im Netzwerk aktiv.
  • the group occupies a certain ID (hash) domain, including replicas
  • the group tries to fill in the routing table of the attacked node with own entries
  • the group controls all outgoing messages of the attacked node (eclipse attack)
• similar attacks can be performed by a coalition of bad nodes
• Sybil attacks include widely used systems like Google, eBay, SETI@HOME, and Tor
• the Sybil attack is an efficient attack against Peer-to-Peer and other decentralized networks
• Potential Goals
  • helps to perform other attacks and to position a node for particular attacks like Route Table Poisoning
  • attack connectivity of the network
  • attack replica set
  • in case of majority votes, be the majority
  • Außerdem können durch eine Sybil-Attacke Anfragen im Netzwerk weitestgehend observiert werden. Das Netzwerk kann absichtlich verlangsamt oder gar ganz zerstört werden. Natürlich lässt sich mittels einer Sybil-Attacke auch einen Denial- of-Service-Angriff starten.

--E0525176 13:00, 23. Feb. 2010 (CET)

What is Onion routing used for? How does it work?

• 13.Privacy protection (in P2P) 16.12.2009: Folien 14-18
• by: David Goldschlag, Michael Reed, and Paul Syverson "Principle of Chaum-Mixes"
• Das Ziel ist jeweils der Schutz der Anonymität von Sender und Empfänger einer Nachricht. Die Angreifer sind in der Lage, den Nachrichtenverkehr zwischen den Teilnehmern im Internet zu beobachten. Zusätzlich soll die übermittelte Nachricht geheim gehalten werden.
• suppose, clients want to perform anonymous communication
  • deliverer wishes to keep its identity secret
  • encryption is not enough: even the existence of communication exchange between parties needs to be hidden
• Onion Routing möchte also schon das Vorhandensein der Kommunikation möglichst gut verschleiern. Hierzu werden eine Reihe von hilfreichen Servern verwendet. Außerdem wird vorausgesetzt, dass eine Reihe von Nachrichten andauernd versendet wird. Auf diese Weise soll sichergestellt werden, dass der gefährdete Nachrichtenverkehr im Hintergrundrauschen untergeht.
• Onion Routing is based on layered-encryption
• the term is a metaphor for the operation of such routers as the packets is peeled like an onion
• Onion routers (ORs) do not mix or delay packets
• they usually operate with simple FIFO or round robin (between flows) queues
• pad message to constant length at each hop
• Onion routing:
  • a Node W that wishes to send a message m to a node Z selects a path (W, X, Y, Z), X, Y are relay servers
  • W can encrypt both the message and the next hop information recursively using public keys: a node only knows who sent the message and who it should send to, e.g.:
    • W encrypts m with the public key (PK) of Z, the result is encrypted with PK of Y, …finally with the PK of X and sends it to X
• W’s identity as originator is not revealed
• decrypted message contains
  • expiration time for the onion (against replay attacks)
  • next routing node
  • two function/key pairs (cryptographic operation (F) and key(K)
    • forward direction
    • backward direction
• the destination node Z does not know who the originatoris (W)
• how to answer to this message ?
• reply onion: Z->Y->X->W
• software The Onion Router (TOR) http://www.torproject.org/

--E0525176 13:15, 23. Feb. 2010 (CET)

What is the Chaum Mix used for? How does it work and how can it be attacked?

• 13.Privacy protection (in P2P) 16.12.2009: Folien 21
• Assumption
  • packets change appearance -> re-encryption
• Mix
  • concept by David Chaum (1981)
  • a mix is a re-router that does not directly forward messages
  • a mix first collects a number of messages and then sends them out in random order
  • an attacker observing a mix cannot tell which incoming messages is which outgoing message („escape through re-ordering“)
  • Example: Treshold Mix, Timed Mix
• Attack:
  • an n-1 attack is an active attack
  • basic idea:
    • the attacker inserts messages and degrades the anonymity set
  • attack situation:
    • n messages arrived at mix
    • n-1 messages are from the attacker
  • the mix fires
    • attacker knows its n-1 messages, can identify the other one
  • basic attack is against a threshold mix, but a strong attacker could also delay messages towards a timed mix

Zusaetzliche Literatur

• in der Bibliothek der TU kann man sich das Buch "Ralf Steinmetz Klaus, Wehrle (Eds.) Peer-to-Peer Systems and Applications" kapitelweise online herunterladen, ich konnte es nur im tu-lan, per vpn von zuhause aus ging es bei mir nicht
• in diesem Buch ist zusaetzliche Information vorhanden, der VO-Stoff ist mMn dort abgedeckt
• auf der HP der LVA gibt es ein Skriptum zu einem anderem Buch, dieses ist eher zur Uebersicht gut, konzentriert sich auf Beweise und Erwartungswerte (gute Quelle, falls notwendig)

Prüfungen

Prüfung am 20.01.2010

Zur Prüfung kamen folgende Fragen: 4; 7; 11; 12; 14; 16; 17; 22; 26. --E0525176 09:19, 18. Feb. 2010 (CET)