Multi-user resource-sharing problem for the Internet

Abstract

In this thesis we study a series of multi-user resource-sharing problems for the Internet, which involve distribution of a common resource among participants of multi-user systems (servers or networks). We study concurrently accessible resources, which for end-users may be exclusively accessible or non-exclusively. For all kinds we suggest a separate algorithm or a modification of common reputation scheme. Every algorithm or method is studied from different perspectives: optimality of protocols, selfishness of end users, fairness of the protocol for end users. On the one hand the multifaceted analysis allows us to select the most suited protocols among a set of various available ones based on trade-offs of optima criteria. On the other hand, the future Internet predictions dictate new rules for the optimality we should take into account and new properties of the networks that cannot be neglected anymore.

In this thesis we have studied new protocols for such resource-sharing problems as the backoff protocol, defense mechanisms against Denial-of-Service, fairness and confidentiality for users in overlay networks. For backoff protocol we present analysis of a general backoff scheme, where an optimization is applied to a general-view backoff function. It leads to an optimality condition for backoff protocols in both slot times and continuous time models. Additionally we present an extension for the backoff scheme in order to achieve fairness for the participants in an unfair environment, such as wireless signal strengths. Finally, for the backoff algorithm we suggest a reputation scheme that deals with misbehaving nodes. For the next problem -- denial-of-service attacks, we suggest two schemes that deal with the malicious behavior for two conditions: forged identities and unspoofed identities. For the first one we suggest a novel most-knocked-first-served algorithm, while for the latter we apply a reputation mechanism in order to restrict resource access for misbehaving nodes. Finally, we study the reputation scheme for the overlays and peer-to-peer networks, where resource is not placed on a common station, but spread across the network. The theoretical analysis suggests what behavior will be selected by the end station under such a reputation mechanism.

Tässä väitöskirjassa tutkimme useita Internetin resurssienjako-ongelmia, jotka liittyvät yhteisten resurssien käyttöön ja jakamiseen monen käyttäjän järjestelmissä. Tutkimme rinnakkain käytettäviä resursseja, jotka voidaan antaa käyttäjille omaan tai jaettuun käyttöön. Ratkaisuna ehdotamme joko uutta algoritmia tai muutoksia olemassaoleviin tunnettuihin mainejärjestelmiin. Kaikkia algoritmeja tutkitaan useammasta näkökulmasta: protokollien optimaalisuus, käyttäjien itsekkyys, protokollan reiluus käytäjiä kohtaan. Tämä monikantainen analyysi mahdollistaa sopivimman protokollan valinnan, ottaen huomioon erilaiset optimointikriteerit. Toisaalta, tulevaisuuden verkkoratkaisut määrittelevät uusia optimointisääntöjä, sekä verkkojen uusia ominaisuuksia, jotka molemmat pitää ottaa tulevaisuudessa huomioon.