TU Darmstadt / ULB / TUprints

Quality of Availability for Widely Distributed and Replicated Content Stores

On, Giwon (2004)
Quality of Availability for Widely Distributed and Replicated Content Stores.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
On-Giwon-PhD-Thesis.pdf
Copyright Information: In Copyright.

Download (921kB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Quality of Availability for Widely Distributed and Replicated Content Stores
Language: English
Referees: Encarnacao, Prof. Dr. Jose Luis ; Huss, Prof. Dr. Sorin ; Kangasharju, Prof. Dr. Jussi
Advisors: Steinmetz, Prof. Dr. Ralf ; Georganas, Prof. Ph.D Nicolas D.
Date: 17 August 2004
Place of Publication: Darmstadt
Date of oral examination: 1 June 2004
Abstract:

As the Internet continues to experience a tremendous expansion in number of users and services today, the importance of satisfying service availability becomes recently one of the most critical factors for the success of "Internet services" such as the World Wide Web, peer-to-peer file sharing and digital audio/video streaming. In this thesis, we take an availability-centric view on end-to-end service Quality of Service (QoS) and investigate service availability for large-scale content distribution and replication systems in wide-area internetworks such as the Internet. The main focus is on issues of providing availability guarantees, i.e., delivering target level of service availability with guarantees for all individual users of services running on top of the above systems. Specifically, the thesis aims at the development of concept and framework for technically realizing the availability-centred QoS approach, on the one hand, and of decision strategies for content replication in order to provide availability guarantee for the large-scale Internet-based services, on the other hand. In particular, we tackle the replica selection and placement problem and study the effectiveness of realistic replication strategies on the achieved service availability in the Internet. There are several contributions that this thesis makes. The first contribution is the concept of Quality of Availability (QoA) which enables one to treat availability as a controllable and observable QoS parameter. On the basis of this concept, three refinements of the existing availability definition have been investigated (decoupled, differentiated and fine-grained) in order to enable a more quantitative specification and evaluation of the service availability. For a technical realization of the QoA concept, we have developed a QoA framework in which users can specify their service requirements in terms of QoA and the requirements are mapped into the low-level replication specification. Additionally, the QoA framework offers QoA metrics and mechanisms to control the QoA guarantee. The second contribution is an evaluation of the replication techniques used to resolve the replica placement problem for different content distribution and replication system models. We have tackled the replica placement problem and investigated specifically the effects of the degree of replication, the granularity and location of replicas on overall service availability achieved by the selected placements. We divided the placement problem into two sub-problems, (1) the static full server replica placement in content delivery network (CDN)-like replicated systems and (2) the dynamic partial data replica placement in peer-to-peer (P2P) systems. For solving the static full server replica placement problem, we first modelled the content distribution and replication system as a stochastic graph and then developed several ranking-based heuristics and an exact state enumeration algorithm for improving and guaranteeing service availability of the system. By simulating the behaviour of the proposed algorithms, we found that the location of replicas is a relevant factor for the service availability. Even though the QoA improvement could be achieved by increasing replica numbers, replicas' placement and their dependability affected the QoA more significantly. In the case of the dynamic replica placement problem in P2P-based content distribution and replication systems, we took the intermittent connectivity of peers of the system explicitly into account. We modelled the system as a dynamic stochastic graph where each node (peer) goes up and down according to its assigned up-time probability. We considered different time scales for replica creation so that replicas could be created either proactively at the service initialization phase, or on-the-fly during the service running phase. We re-used the placement heuristics used for solving the static replica placement problem and modified them slightly so that they are fully decentralized, assume no global information about the system condition or network topology, and work in a cooperative way to replicate content on-the-fly. To quantitatively study the effectiveness of the used heuristics, we developed an event-driven simulation framework which captures the data access model as well as peers' dynamic behaviour. The simulation results indicated that the cooperative placement heuristics offer, in general, better QoA than non-cooperative local placement approach, while all of them induce approximately the same amount of replacement cost in terms of the number of replacements. The third contribution is a new approach for determining replica placements in large-scale content distribution and replication systems, which always provides an availability guarantee for all service requesting entities in a content distribution and replication system. For the first time, we suggested an admission control-based replica placement scheme that solves the static replica placement problem in a polynomial time, with respect to the size of the input system. Through a simulative study, we have experimentally evaluated the admission control-based algorithm with random and power-law graphs of different sizes. Our results show that the placement achieved by the admission control-based algorithm always provides a QoA guarantee, and that the upper bound of the replication degree (i.e., replica numbers) required for delivering QoA guarantees is about 27% and 37% of the total nodes in the random and power-law graph, respectively. As far as we know this is the first time that the admission control concept has been integrated with a replica placement scheme that solves the problem in a polynomial time while offering service availability guarantees.

Alternative Abstract:
Alternative AbstractLanguage

Mit dem rasanten Wachstum des Internet, hinsichtlich der Anzahl von Diensten und Anwendern, dehnen sich "Internet-Dienste" wie World Wide Web, Peer-to-Peer Datenaustausch, digitale Audio/Video-Uebertragung großflächig aus. Eine der wichtigen Anforderungen, die die Benutzer dieser Internet-Dienste häufig erwarten, liegt darin, dass sich die Dienste auf einer akzeptierbaren Qualitätsebene bewegen sollen. Die Qualität eines Dienstes kann anhand des Durchsatzes, der Verfügbarkeit, der Sicherheit, usw. spezifiziert werden. Dienstgüte (Quality of Service, QoS) ist der Schlüsselansatz dafür, Ressourcenzusicherung und Dienstgarantien für viele vernetzte Multimedia- und andere Dienste sicherzustellen. Bisher jedoch konzentrierte sich die Aufmerksamkeit im QoS-Bereich hauptsächlich auf die Leistung, wie Leistungsoptimierung und -garantien. Während die QoS-Unterstützung bezüglich der Uebertragungscharakteristiken für viele Internet-Dienste (insbesondere für die Soft-Echtzeit-Dienste) weiterhin wichtig ist, nimmt eine völlig andersartige Benutzeranforderung an Bedeutung zu: "wie verfügbar" ein bestimmter Dienst und dessen Daten sind. Im Rahmen von QoS ist das Thema der Verfügbarkeit noch nicht so detailliert untersucht worden. In der vorliegenden Arbeit wird die Darstellung über QoS auf die Verfügbarkeit zentriert. Dabei betrachtet die Arbeit den Problemkreis der Ende-zu-Ende-Dienstverfügbarkeit für die Internet-Dienste, insbesondere für weitverteilte und replizierte Content-Stores. Die Arbeit stellt zuerst ein Konzept (genannt Quality of Availability, QoA) und ein dementsprechendes Bezugssystem vor, die zusammen die Verfügbarkeit als einen neuen, steuerbaren und beobachtbaren QoS-Parameter betrachten und somit die Spezifizierung und die Evaluierung der Verfügbarkeitsanforderungen in unterschiedlichen Dienstklassen unterstützen. Dieses Bezugssystem umfasst ein Modell für Spezifikation und Verwaltung von Ressourcen, das hin-sichtlich der Dienstverfügbarkeit die Zuordnung der von den Endnutzern definierten Dienstanforderungen und die Mechanismen zur garantierten Verfügbarkeit von Ressourcen-Allokationen ermöglicht. Auf der Basis des QoA-Konzepts und der dabei verfeinerten Notationen von Verfügbarkeit wurde speziell das Problem der Replikaplatzierung in weitverteilten und replizierten Content-Stores detailliert betrachtet. Der Fokus liegt dabei auf den Replikationsmechanismen und -strategien, die sowohl die Verbesserung der Verfügbarkeitsguten als auch die Bereitstellung der Verfügbarkeitsgarantien für alle individuellen Benutzer der Dienste unterstützen und ermöglichen. Es wurde untersucht, wie die Anzahl, Granularitat und Lokation der Replikate die Dienstverfügbarkeit beeinflussen, die durch ausgewählte Replikaplatzierungen erreicht werden kann. Abhängig von der Replikaerzeugungszeit und der Granularitat der zu replizierenden Contents wurde das Problem der Replikaplatzierung in zwei Problemdomanen geteilt: die statische Platzierung von Content-Server-Replikaten in Content-Delivery-Network (CDN) Systemen und die dynamische Platzierung von Daten-Replikaten in Peer-to-Peer (P2P) Systemen. Zur Lösung des statischen Platzierungsproblems der Serverreplikate wurden die Content-Stores als ein parametrisierter, stochastischer Graph modelliert. Als Platzierungsalgorithmen wurden eine Reihe von Heuristiken und eine exakte, zustandaufzahlungs-basierte Methode entwickelt, die sich jeweils für die Verbesserung und die Gewährleistung der Dienstverfügbarkeit der Systeme eignen. Durch eine Simulationsstudie und eine quantitative Evaluierung der erreichten Replikationsgüten wurde gezeigt, dass die Lokation von Replikaten und deren Verlässlichkeit ein relevanter Faktor für die Verfügbarkeitgute ist. Weiterhin wurde gezeigt, dass die Heuristiken im Gegensatz zur exakten Methode im Allgemeinen keine Garantie hinsichtlich der Dienstverfügbarkeit abliefern. Im Fall des Problems der dynamischen Replikaplatzierung in P2P-basierten Content-Stores wurde die zeitweilige Konnektivitat von Peers ausführlich berücksichtigt. Die P2P-Systeme wurden dann als ein dynamischer, stochastischer Graph modelliert, wobei jeder Knoten und jede Kante gemaß der zugeordneten Ausfallswahrscheinlichkeit ausfallen bzw. erreichbar werden. Für die Erzeugung von Replikaten wurden zwei unterschiedliche Zeitphasen eingefügt, so dass Replikate entweder proaktiv bei der Initialisierung oder `on-the-fly' während der Laufzeit der Dienste erzeugt werden können. Die zur Lösung dieses dynamischen Platzierungsproblems entwickelten Heuristiken sind rangordnungs-basiert und unterscheiden sich grundsätzlich dadurch, ob sie bei der Entscheidung der Platzierung miteinander kooperativ arbeiten oder nicht. Zur quantitativen Evaluierung wurde ein ereignisbasiertes Simulationssystem entwickelt, das neben einer Einstellungsmöglichkeit replikations-relevanter Parameter die Verwendung unterschiedlicher Netzwerktopologien ermöglicht. Das Simulationsergebnis beleuchtet die Wichtigkeit der kooperativen Platzierung in P2P-Systemen: die kooperativen Heuristiken haben hinsichtlich der Dienstverfügbarkeit eine höhere Güte als das typische nicht-kooperative Platzierungsverfahren, während die durchschnittlichen Replikationskosten für alle benutzten Platzierungsverfahren annähernd gleich waren. Als ein weiteres Problem der Replikaplatzierung wurde ein Lokationsproblem untersucht, bei welchem die Ressourcen beschränkt sind. Dabei soll die als Lösung ausgewählte Platzierung von Replikaten die angeforderte Verfügbarkeitgüte für alle Benutzer immer gewährleisten. Der entwickelte Lösungsansatz integriert das Konzept der Zugangskontrolle (Admission Control) und die Replikaplatzierung derart, dass das Problem in polynomieller Laufzeit gelöst werden kann und Garantien bezüglich der Dienstverfügbarkeit gemacht werden konnen. Im Rahmen einer Simulationsstudie mit unterschiedlichen Netzwerktopologien und Graphengroßen wurde der Algorithmus bezüglich der Effizienz sowie der Umsetzbarkeit experimentell evaluiert. Die Arbeit leistet somit einen wichtigen Beitrag, um Garantien bezüglich der Verfügbarkeit von Internet-Diensten und deren Daten in weitverteilten Netzen wie z.B. dem Internet zu ermöglichen.

German
Uncontrolled Keywords: Replication, Distributed Systems, Availability, Quality of Service
Alternative keywords:
Alternative keywordsLanguage
Replication, Distributed Systems, Availability, Quality of ServiceEnglish
URN: urn:nbn:de:tuda-tuprints-4747
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:21
Last Modified: 08 Jul 2020 22:49
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/474
PPN:
Export:
Actions (login required)
View Item View Item