Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-82133
URL: http://www.freidok.uni-freiburg.de/volltexte/8213/


Vater, Arne

Efficient coding schemes for file sharing networks

Effiziente Kodierverfahren für Filesharing-Netzwerke

Dokument1.pdf (6.531 KB) (md5sum: f5c279ee9e0ed9606f46c5febe1c280d)

Kurzfassung in Englisch

Peer-to-peer networks are commonly constituted by a large number of normal personal computers that are connected via Internet. They do not rely on centralized infrastructure, like servers for instance, to coordinate and to enable network-wide search, and furthermore each participant, called peer, has equal rights and responsibilities. One popular application for peer-to-peer networks is file sharing, in which a peer provides one or more files for download by other peers that in turn offer their own files as well. These networks are referred to as file sharing networks. Today, one of their fundamental techniques is the partitioning of the files in distribution, especially if a file is large. This way, a participant can redistribute each part immediately after downloading, and thus contribute to the original file's distribution even before having completed the file download itself.

The popular file sharing network BitTorrent combines this approach with incentives for participants to provide upload and has thereby become the most successful file sharing network so far. However, only minor attention is paid to optimizing the availability of all the file's parts. Due to participants leaving the network, single parts, called blocks, may get lost and thus obstruct the download of the remaining peers. To alleviate this problem in BitTorrent, blocks are chosen for transmission according to a policy that aims at providing the same amount of copies for each block within the network. Yet it is simple to construct scenarios in which blocks are completely lost, and in practice this happens regularly to unpopular files that cannot revert to a sufficient number of block copies.

An elegant solution to this problem is the usage of error redundant codes, each of which can substitute one arbitrary missing block. It is possible to exclusively use those codes during the distribution process and reconstruct the whole file later, after downloading has finished. This technique is known as Network Coding, and it is well-known that it maximizes the distribution flow in the network. A randomized variant proposed for file sharing systems is called Practical Network Coding. It uses random linear combinations of blocks as codes, and after gathering enough of them the original file can be decoded by a matrix operation.

In this work, a complexity model is used that allows to execute calculations on a constant number of file blocks or codes in main memory for free, while each read/write operation of one block on an unbounded disk storage is costly. In this model, all previously known network coding schemes suffer from quadratic read/write costs in the number of blocks that a file is partitioned into. Because of the speed gap between mass storage and main memory this is a severe bottleneck for efficient usage of coding in practical file sharing systems, especially for large files with numerous blocks. The necessary calculations pose only a minor task for modern computers, though.

A performance relation allows the analytical comparison of different file sharing systems, and a set of round models reflects the progression of a distribution process over time while participants join and leave the network. The models differ in each peer's knowledge of the future network structure, ranging from complete knowledge to none at all.

New coding schemes are presented that form a compromise between the optimal information flow of Network Coding and the low read/write overhead of uncoded block transfer schemes like BitTorrent. The overhead of the new coding technique Paircoding equals that of BitTorrent up to an almost constant factor, however, Paircoding achieves better data distribution. Further improvement is accomplished with the Treecoding scheme and its variants Tree Level Coding, Butterfly Coding and Tree Network Coding, but their read/write complexities increase by polylogarithmic factors in the number of blocks.

The analyses show that for certain classes of scenarios with small communication depth all new schemes achieve optimal information flow. Moreover, Tree Network Coding achieves optimal information flow in any scenario, like classic Network Coding does, but with reduced read/write complexity if the number of rounds is sublogarithmic in the number of blocks. Furthermore, it never exceeds the read/write complexity of Network Coding.

The coding schemes presented here form a performance hierarchy, in which the complexity tends to increase with the performance, showing a trade-off between file sharing performance and read/write complexity.


Kurzfassung in Deutsch

Peer-to-Peer-Netzwerke bestehen üblicherweise aus einer großen Anzahl normaler Personalcomputer die über das Internet miteinander verbunden sind. Für Koordination und netzweite Suche benötigen sie keine zentrale Infrastruktur, wie beispielsweise Server, und jeder Teilnehmer, genannt Peer, hat die gleichen Rechte und Pflichten. Eine weit verbreitete Anwendung von Peer-to-Peer-Netzwerken ist das Austauschen von Dateien. Hierbei stellt ein Peer eine oder mehrere Dateien den anderen Peers zum Download zur Verfügung, während diese anderen ihrerseits ihre Dateien anbieten. Diese Netzwerke werden File-Sharing-Netzwerke genannt. Heutzutage ist eines ihrer elementaren Verfahren die Partitionierung der zu verteilenden Dateien, insbesondere wenn diese groß sind. Auf diese Weise kann ein Teilnehmer direkt nach Erhalt eines Dateiteils diesen weiter verteilen und dadurch noch vor der eigenen Vervollständigung der Datei zu ihrer Verteilung beitragen.

Das populäre File-Sharing-Netzwerk BitTorrent kombiniert diesen Ansatz mit speziellen Anreizen für alle Teilnehmer bei der Weiterverteilung mitzuwirken und ist dadurch zum bisher erfolgreichsten File-Sharing-Netzwerk geworden. Allerdings wird auf optimale Verfügbarkeit aller Dateiteile kein besonderer Wert gelegt. Wenn Teilnehmer das Netzwerk verlassen können einzelne Dateiteile, genannt Blöcke, verloren gehen und so den Download anderer behindern. Um dieses Problem in BitTorrent abzuschwächen werden zu verteilende Blöcke nach einem Verfahren, genannt Policy, ausgewählt, sodass die Anzahl der Kopien von jedem Block im gesamten Netzwerk in etwa gleich ist. Trotzdem sind Szenarien, in denen Blöcke vollständig verloren gehen, einfach zu konstruieren, und in der Praxis kommt das auch regelmässig bei unpopulären Dateien vor, bei denen nicht auf eine ausreichende Anzahl von Blockkopien zurückgegriffen werden kann.

Eine elegante Lösung dieses Problems ist die Benutzung von fehlerkorrigierenden Codes, wobei jeder Code einen beliebigen fehlenden Block ersetzen kann. Es ist möglich während des Verteilungsprozesses nur solche Codes zu verwenden und erst nach Beendigung des Downloads die Originaldatei zu rekonstruieren. Dieses Verfahren wird Network-Coding genannt, und es ist bekannt, dass es den Informationsfluss im Netzwerk maximiert. Eine randomisierte Variante für File-Sharing-Systeme wird Practical-Network-Coding genannt. Es verwendet zufällige Linearkombinationen der Blöcke als Codes und nachdem genügend davon gesammelt sind kann die Originaldatei mittels einer Matrixoperation decodiert werden.

In dieser Arbeit wird ein Komplexitätsmodell benutzt, das kostenfreie Berechnungen auf einer konstanten Anzahl von Blöcken im Arbeitsspeicher erlaubt, während das Schreiben oder Lesen eines Blocks auf einem unbegrenzten Festplattenspeicher Kosten verursacht. In diesem Modell haben alle bisher bekannten Network-Coding-Verfahren quadratische Kosten in der Anzahl der Blöcke in die eine Datei partitioniert ist. Wegen des Geschwindigkeitsunterschieds zwischen Massenspeicher und Arbeitsspeicher erzeugt das einen Flaschenhals, der eine effiziente Nutzung von Codierungen in praktischen File-Sharing-Systemen verhindert, insbesondere für große Dateien mit vielen Blöcken. Die eigentlichen Berechnungen hingegen sind für moderne Computer keine große Herausforderung.

Eine Performanzrelation erlaubt den analytischen Vergleich zwischen verschiedenen File-Sharing-Verfahren, wobei Rundenmodelle den zeitlichen Verlauf eines Verteilungsprozesses abbilden, in dem Teilnehmer hinzukommen oder das Netzwerk verlassen. Die Modelle unterscheiden sich im Umfang der Informationen die jeder Peer über die zukünftige Netzwerkstruktur hat, angefangen mit vollständiger Information bis hin zu gar keiner.

Neue Codierungsverfahren werden vorgestellt, die einen Kompromiss zwischen dem optimalen Informationsfluss von Network-Coding und den geringen Schreib/Lese-Kosten von codierungsfreien Verfahren wie BitTorrent darstellen. Die Kosten des neuen Paircoding-Verfahrens entsprechen denen von BitTorrent bis auf einen fast konstanten Faktor, aber Paircoding erreicht einen besseren Informationsfluss. Weitere Verbesserungen werden durch das Treecoding-Verfahren und seine Varianten Tree-Level-Coding, Butterfly-Coding und Tree-Network-Coding erreicht, allerdings steigt ihre Schreib/Lese-Komplexität um einen polylogarithmischen Faktor in der Anzahl der Blöcke.

Die Analysen zeigen, dass für bestimmte Szenarioklassen mit geringer Kommunikationstiefe alle neuen Verfahren optimalen Informationsfluss erreichen. Darüber hinaus erreicht Tree-Network-Coding, ebenso wie klassisches Network-Coding, optimalen Fluss in beliebigen Szenarien, und das mit verringerter Schreib/Lese-Kom\-plexität falls die Anzahl der Runden sublogarithmisch in der Anzahl der Blöcke ist. Allerdings überschreitet es auch sonst niemals die Komplexität von Network-Coding.

Die vorgestellten Codierungsverfahren bilden eine Performanzhierarchie, wobei die Schreib/Lese-Komplexität mit der Performanz steigt. Daraus ergibt sich ein Konflikt zwischen diesen beiden Optimierungskriterien


SWD-Schlagwörter: Online-Algorithmus , Paralleler Algorithmus , Effizienter Algorithmus , Peer-to-Peer-Netz , Komplexität , Spärliche Codierung , BitTorrent
Freie Schlagwörter (deutsch): Netzwerkkodierung
Freie Schlagwörter (englisch): Efficient Algorithm , Peer-to-Peer Networks , Network Coding , Sparse Coding , BitTorrent
CCS Klassifikation F.2.2 , E.4 , C.2.4
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Schindelhauer, Christian (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 01.08.2011
Erstellungsjahr: 2011
Publikationsdatum: 05.08.2011
Indexliste