Democritus University of Thrace (DUTH)
Distributed management of competitive access to common resources using algorithmic game theory
Abstract
dc:descriptionThe Internet is today an inextricable part of daily personal, educational and business activity, turning any problems in its operation or availability into a significant interruption of these activities and their users. The resources offered by the Internet (capacity, coverage) are continuously increasing but at the same time the users and their demands are increasing at an even larger pace. If measures for the efficient and fair management of the network resources are not taken, the Internet will cease to be able to support new users and applications with high quality. Internet users operate in an independent manner, by creating data flows (sending and receiving network packets) which satisfy their demands. Each user prefers for his needs to be served in the best possible way but the resources of the network are shared and finite, making it often impossible to provide the best service to everyone. This leads to users competing amongst themselves for access to the network resources and its services. Whenever the demands placed on the services by the users exceed the capacity of the services, a means of selecting which users and to which degree they will be served is required. In the case of the Internet, the resources are network capacity, the demands of the users are requests for transferring network packets and the functionality of selecting which users are served and how they are served is generally referred to as Quality of Service (QoS). One feature of the Internet which significantly affects the possible solutions to providing QoS is its decentralized structure: there exists no central authority which is responsible for the whole operation of the network and which could centrally perform the resource allocation. Instead, resources are allocated locally at each network node to the users which access it. In this work, we address the issue of managing competitive access to common resources through the use of algorithmic game theory. This approach is validated by the competitive, selfish and independent nature of the users. Additionally, in the case of QoS provision for the Internet, our solutions have to be distributed in order to be applicable. Specifically, we start by proposing the Prince mechanism for distributing network flow throughput in a (MaxMin-resembling) fair manner. We then propose an efficient data structure and algorithm set for implementing Prince on a network router queue. We continue by providing the theoretical description and first simple experimental implementation of PacketEconomy, a network economy where each flow is modelled as a population of rational network packets, and these packets can self-regulate their access to network resources by mutually trading their positions in router queues. This theoretical model is then adapted to the OMNET++ simulator and via thorough experimentation we present the validation of the efficacy of our solution in a realistic context. Applying the same principles of game-theoretic analysis to realistic service provision problems, we also study an Internet-based VoIP service access problem in the context of the prevention of SPIT (SPam over Internet Telephony).
Degree
thesis:*- Grantor dc:publisher
- Democritus University of Thrace (DUTH)
- Year dc:date
- 2016
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Koutsiamanis, Remous-Aris
- Κουτσιαμάνης, Ρέμους-Άρης
Subjects
dc:subject × 18- Αλγόριθμοι
- Δίκτυα υπολογιστών
- Αλγοριθμική θεωρία παιγνίων
- Διαχείριση πόρων
- Ανταγωνιστική πρόσβαση
- Algorithm
- Computer networks
- Algorithmic game theory
- Resource management
- Competitive access
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/37381