DHT - Revision history

Oepen: /* Schlüssel-Wert-Paare */

2010-08-23T18:58:09Z

Schlüssel-Wert-Paare

← Older revision		Revision as of 18:58, 23 August 2010
Line 7:		Line 7:

	Das besondere Kennzeichen von Kademlia ist der gemeinsame virtuelle Adreßraum für Knoten-IDs und Schlüssel mit 160 Bit Breite. Damit eine Information im Netzwerk gefunden werden kann, wird ihr Hashwert (der Schlüssel) als Schlüssel-Wert-Paar auf mehreren Knoten mit einer zum Schlüssel ähnlichen ID gespeichert. Ein Knoten, der den dort gespeicherten Schlüssel sucht, kann das den Wert des Schlüssel-Wert-Paars enthalten und anhand dessen bestimmen, von welchem Netzwerkknoten er die Information erhalten kann.<br><br>		Das besondere Kennzeichen von Kademlia ist der gemeinsame virtuelle Adreßraum für Knoten-IDs und Schlüssel mit 160 Bit Breite. Damit eine Information im Netzwerk gefunden werden kann, wird ihr Hashwert (der Schlüssel) als Schlüssel-Wert-Paar auf mehreren Knoten mit einer zum Schlüssel ähnlichen ID gespeichert. Ein Knoten, der den dort gespeicherten Schlüssel sucht, kann das den Wert des Schlüssel-Wert-Paars enthalten und anhand dessen bestimmen, von welchem Netzwerkknoten er die Information erhalten kann.<br><br>
	http://www.informatik.com/[http://www.online-poker-spielen.biz/ poker spielen] <br>

	== XOR-Metrik ==		== XOR-Metrik ==

UzumakiNaruto at 23:37, 25 June 2010

2010-06-25T23:37:42Z

← Older revision		Revision as of 23:37, 25 June 2010
Line 1:		Line 1:


	== Überblick ==		== Überblick ==

Line 9:		Line 7:

	Das besondere Kennzeichen von Kademlia ist der gemeinsame virtuelle Adreßraum für Knoten-IDs und Schlüssel mit 160 Bit Breite. Damit eine Information im Netzwerk gefunden werden kann, wird ihr Hashwert (der Schlüssel) als Schlüssel-Wert-Paar auf mehreren Knoten mit einer zum Schlüssel ähnlichen ID gespeichert. Ein Knoten, der den dort gespeicherten Schlüssel sucht, kann das den Wert des Schlüssel-Wert-Paars enthalten und anhand dessen bestimmen, von welchem Netzwerkknoten er die Information erhalten kann.<br><br>		Das besondere Kennzeichen von Kademlia ist der gemeinsame virtuelle Adreßraum für Knoten-IDs und Schlüssel mit 160 Bit Breite. Damit eine Information im Netzwerk gefunden werden kann, wird ihr Hashwert (der Schlüssel) als Schlüssel-Wert-Paar auf mehreren Knoten mit einer zum Schlüssel ähnlichen ID gespeichert. Ein Knoten, der den dort gespeicherten Schlüssel sucht, kann das den Wert des Schlüssel-Wert-Paars enthalten und anhand dessen bestimmen, von welchem Netzwerkknoten er die Information erhalten kann.<br><br>
			http://www.informatik.com/[http://www.online-poker-spielen.biz/ poker spielen] <br>

	== XOR-Metrik ==		== XOR-Metrik ==

Cremeriu: /* Weiterführende Links */

2006-01-26T18:01:52Z

Weiterführende Links

← Older revision		Revision as of 18:01, 26 January 2006
Line 108:		Line 108:
	== Weiterführende Links ==		== Weiterführende Links ==

	Die erste Anlaufstation zum Verständnis der Funktionsweise von Kademlia ist das Paper von		Die erste Anlaufstation zum Verständnis der Funktionsweise von Kademlia ist das Paper von Petar Maymounkov and David Mazieres:
			* [http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf ''Kademlia: A of Peer to peer information system Based on the XOR Metric''] (englisches PDF)

Cremeriu: /* Schlußfolgerung */

2006-01-26T18:00:53Z

Schlußfolgerung

← Older revision		Revision as of 18:00, 26 January 2006
Line 104:		Line 104:
	Kademlia eignet sich demnach besonders für sehr dynamische Netze und kann mit einer hohen Effizienz des Datenverkehrs aufwarten.<br>		Kademlia eignet sich demnach besonders für sehr dynamische Netze und kann mit einer hohen Effizienz des Datenverkehrs aufwarten.<br>
	Diese Eigenschaften haben wahrscheinlich auch zu der derzeitigen Verbreitung geführt (Overnet, eMule, BitTorrent, …).		Diese Eigenschaften haben wahrscheinlich auch zu der derzeitigen Verbreitung geführt (Overnet, eMule, BitTorrent, …).


			== Weiterführende Links ==

			Die erste Anlaufstation zum Verständnis der Funktionsweise von Kademlia ist das Paper von

Cremeriu: /* Rest-Container */

2006-01-26T17:59:37Z

Rest-Container

← Older revision		Revision as of 17:59, 26 January 2006
Line 88:		Line 88:
	<br>		<br>

	== ~~Rest-Container~~ ==		== Schlußfolgerung ==

	Hohe Verbreitung (Overnet, eMule, BitTorrent, …)
			Suchaufwand praktisch identisch: O(log n)
	Eigenschaften gut formal nachweisbar
			Höherer Aufwand für Kademlias Routingtabellen
			Keine Beachtung der Distanz von virtuellen Nachbarknoten im Netzwerk – leistet nur Pastry
			Gleicht Nichtbeachtung von Netzwerkkosten durch Schlüssel-Wert-Paar-Caching aus
			Bei Knotenausfall: Schlüsselsuche in Kademlia ohne Latenzsteigerung durch parallele Anfragen
			Besondere Eignung für sehr dynamische Netze
			Hohe Effizienz des Datenverkehrs


			Kademlia realisiert eine Suchfunktion in einem strukturierten Peer-To-Peer-Netz mit logarithmischer Komplexität, was für DHT-Ansätze allgemein typisch ist.<br>
			Im Vergleich mit anderen DHTs ist der Aufwand für Kademlias Routingtabellen / "k-Buckets" höher, aber z.B. für den Einsatz als Protokoll für Filesharing ist dieser Mehraufwand zu vernachlässigen.<br>
			Kademlia bezieht die realen Netzwerkkosten nicht mit ein - Nachbarn im erzeugten Netz können also im Trägernetz weit voneinander entfernt oder sehr verschieden angebunden sein. Dieser Nachteil wird jedoch durch das Caching der Schlüssel-Wert-Paare ausgeglichen. Diese Eigenschaft führt überdies dazu, daß bei Suchanfragen in Kademlia auch beim Ausfall vieler beteiligter Knoten keine wesentliche Latenzsteigerung zu erwarten ist.<br>
			Kademlia eignet sich demnach besonders für sehr dynamische Netze und kann mit einer hohen Effizienz des Datenverkehrs aufwarten.<br>
			Diese Eigenschaften haben wahrscheinlich auch zu der derzeitigen Verbreitung geführt (Overnet, eMule, BitTorrent, …).

Cremeriu: /* Rest-Container */

2006-01-26T17:41:59Z

Rest-Container

← Older revision		Revision as of 17:41, 26 January 2006
Line 80:		Line 80:
	Im zweiten Schritt wird mit STORE auf diesen Knoten das Paar abgelegt.<br>		Im zweiten Schritt wird mit STORE auf diesen Knoten das Paar abgelegt.<br>
	Die Knoten, die ein Paar erhalten haben, kümmern sich fortan selbsttätig darum, dieses auf neu ins Netzwerk gekommenen Knoten, die noch näher am Schlüssel des Paares liegen als sie selbst, abzulegen.<br>		Die Knoten, die ein Paar erhalten haben, kümmern sich fortan selbsttätig darum, dieses auf neu ins Netzwerk gekommenen Knoten, die noch näher am Schlüssel des Paares liegen als sie selbst, abzulegen.<br>
			<br>

			== Aktualität von Schlüssel-Wert-Paaren ==

			Um veraltete Verweise zu verhindern, verfallen Schlüssel-Wert-Paare nach 24 Stunden im Netzwerk durch einen Zeitstempel. Dementsprechend müssen diese Paare vom Inhaber der dem Schlüssel entsprechenden Information auch alle 24 Stunden wieder neu mit STORE in das Netzwerk eingebracht werden.<br>
			Weiterhin speichern die Knoten, auf denen die Schlüssel-Wert-Paare gespeichert sind, diese im Stundentakt neu im Netzwerk ab - um sicherzustellen, daß diese Paare stets auf mindestens "k" Knoten gespeichert sind, da in der Zwischenzeit sich möglicherweise andere Knoten, die dasselbe Paar gespeichert hatten, vom Netz gegangen sein könnten.<br>
	<br>		<br>

Cremeriu: /* Publizierung von Schlüssel-Wert-Paaren */

2006-01-26T17:37:30Z

Publizierung von Schlüssel-Wert-Paaren

← Older revision		Revision as of 17:37, 26 January 2006
Line 77:		Line 77:
	== Publizierung von Schlüssel-Wert-Paaren ==		== Publizierung von Schlüssel-Wert-Paaren ==

			Um ein Schlüssel-Wert-Paar im Netzwerk abzulegen, wird zuerst ein FIND_NODE nach dem entsprechenden Schlüssel durchgeführt, um die "k" nächsten Knoten zu bestimmen.<br>
	Um ein Schlüssel-
			Im zweiten Schritt wird mit STORE auf diesen Knoten das Paar abgelegt.<br>
	Finden der „k“ nächsten Knoten zum Schlüssel durch FIND_NODE
			Die Knoten, die ein Paar erhalten haben, kümmern sich fortan selbsttätig darum, dieses auf neu ins Netzwerk gekommenen Knoten, die noch näher am Schlüssel des Paares liegen als sie selbst, abzulegen.<br>
	STORE des Schlüssel-Wert-Paares auf diesen „k“ Knoten
			<br>
	Inhaber von Paaren speichern Paare bei Bemerken auf neuen Knoten, die näher am Schlüssel liegen als sie selbst



	== Rest-Container ==		== Rest-Container ==

Cremeriu: /* Rest-Container */

2006-01-26T17:35:15Z

Rest-Container

← Older revision		Revision as of 17:35, 26 January 2006
Line 60:		Line 60:
	"i" ist für dieses Verfahren ein systemweiter Paramter, der in der Praxis mit <math>i = 3</math> angegeben ist.		"i" ist für dieses Verfahren ein systemweiter Paramter, der in der Praxis mit <math>i = 3</math> angegeben ist.
	<br><br>		<br><br>


			== Bootstrapping ==

			Ein dem Netzwerk beitretender Knoten hat anfangs keine Kenntnis über das Netzwerk - und demnach keine Knoten in seinen "k-Buckets". Um dem Netzwerk beizutreten, generiert er nun seine eigene Knoten-ID mit einer konsistenten Hashfunktion. Auf irgendeine - nicht durch Kademlia selbst spezifierte - Weise muß der Knoten nun einen Erstkontakt mit einem Knoten aus dem Netzwerk erhalten.<br><br>
			Diesen Knoten fügt er dann in seine "k-Buckets" ein und führt ein FIND_NODE nach seiner eigenen Knoten-ID durch, um seine nächsten Nachbarn kennenzulernen und seine "k-Buckets" zu füllen. Dies hat gleichzeitig den positiven Effekt, daß sich der neue Knoten im Netzwerk bekannt macht.<br>
			<br>


			== Schlüsselsuche mit FIND_VALUE ==

			Nach dem gleichen Schema wie bei der Knotensuche mit FIND_NODE wird hier nach einem Schlüssel gesucht. Der Knoten startet also eine parallele Anfrage und bekommt in der Regel die "k" nächsten Knoten zurück - besitzt jedoch einer der angefragten Knoten das gesuchte Schlüssel-Wert-Paar, bricht die Suche ab.<br>
			Abschließend prüft der Anfragende noch, ob die ihm bekannten "k" nächsten Knoten zum Schlüssel alle das Schlüssel-Wert-Paar besitzen und speichert dieses gegebenenfalls auf ihnen.<br>
			<br>

			== Publizierung von Schlüssel-Wert-Paaren ==

			Um ein Schlüssel-
			Finden der „k“ nächsten Knoten zum Schlüssel durch FIND_NODE
			STORE des Schlüssel-Wert-Paares auf diesen „k“ Knoten
			Inhaber von Paaren speichern Paare bei Bemerken auf neuen Knoten, die näher am Schlüssel liegen als sie selbst

Cremeriu: /* Operationen */

2006-01-26T17:26:01Z

Operationen

← Older revision		Revision as of 17:26, 26 January 2006
Line 52:		Line 52:
	STORE		STORE
	-> Abspeichern eines Schlüssel-Wert-Paares auf einem Knoten		-> Abspeichern eines Schlüssel-Wert-Paares auf einem Knoten
	<br>		<br><br>

	== Knotensuche mit FIND_NODE ==		== Knotensuche mit FIND_NODE ==

Cremeriu: /* Operationen */

2006-01-26T17:25:49Z

Operationen

← Older revision		Revision as of 17:25, 26 January 2006
Line 52:		Line 52:
	STORE		STORE
	-> Abspeichern eines Schlüssel-Wert-Paares auf einem Knoten		-> Abspeichern eines Schlüssel-Wert-Paares auf einem Knoten
	~~<br>~~<br>		<br>


	== Knotensuche mit FIND_NODE ==		== Knotensuche mit FIND_NODE ==