Session Management Algorithms for Solving K-Token Dissemination Using Network Coding
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Computer systems and networks (MPCSN), MSc
Publicerad
2014
Författare
GARCÍA, GUILLERMO BARREDO
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
In this thesis report we consider k-token dissemination algorithms that makes use of network coding. The k-token dissemination problem consists of propagating a total number of k tokens to all nodes in the network. The tokens are distributed between one or more nodes before the algorithm is executed, and the final goal is that all nodes must eventually have the same set of k-tokens. Network coding is a recent technique that, implemented in a proper way, helps to save bandwidth and improves the speed of distributed computation. The network model consists of a network that can change completely from round to round, therefore the nodes do not know anything about their neighbours. Moreover, when a node broadcasts a message, it does not know which are the receivers, thus, it is not possible for the nodes to know which are the tokens that their neighbours need. By using network coding, the time needed to achieve the final goal (all nodes possess the same k tokens) is drastically reduced in comparison to a simple random forwarding algorithm, which, as its name infers, randomly broadcasts the tokens possessed by a node. We study the session management problem, and present two algorithms to solve it. The problem consists of limiting the total number of sessions that concurrently coexist in the system. In the context of dissemination problems and network coding, we consider a session as an index according to which the information is codded by the session initiator. Since in dynamic networks nodes can crash and recover, we wish to allow sessions to accomplish their tasks, while limiting the amount of overall system resources in use. We propose solutions for the session management problem, and by that facilitate the solution of the k-token dissemination problem in dynamic networks. By solving the session management problem, we can also solve the k-token dissemination problem in a more robust way, in the sense that the algorithms can deal with several types of failures, such as, crashes and crashes-recoveries.
Beskrivning
Ämne/nyckelord
Datavetenskap (datalogi) , Informations- och kommunikationsteknik , Computer Science , Information & Communication Technology