Error correcting codes have been studied extensively over the past half century in a variety of theoretical and practical contexts, most recently making their way into networking applications. This thesis focuses on two types of codes, identifying codes and rateless codes, and their applications in sensor and peer-to-peer networks. Intuitively, an identifying code is a set of vertices in a graph with the property that each vertex neighborhood in the graph has a unique intersection with the code. The identifying code problem involves finding the smallest identifying code for a given graph, and its general form has been shown to be NP-complete. We begin by drawing a reduction between the identifying codes problem and the well-studied set cover problem. The reduction is efficient enough to provide a general polynomial time approximation with tight performance guarantees for arbitrary directed graphs. Specifically, we provide a general hardness of approximation result, and demonstrate an algorithm that attains this bound within a small constant. We further generalize these results to robust identifying codes, whose identification property survives corruptions in the underlying graph, by linking them to the set multi-cover problem. We develop distributed as well as branch-and-bound novel algorithms for generating robust identifying codes. Finally, we study bounds on the number of disjoint identifying codes, a general problem motivated by considerations of energy balancing in sensor networks. In the second section of this work we consider the use of rateless codes within the context of maintaining fairness in a peer-to-peer network. Our architecture is designed to help overcome asymmetries in upload/download speeds that are typical in end-user dialup, broadband and cellular connections. By sharing encoded file data, users at remote locations can access information stored on their home computers, through multiple intermediaries, at rates often exceeding their home connection's upload capacity. We prove that our sharing approach guarantees two key properties: (i) asymptotic fairness, in that (even malicious) users are assigned idle bandwidth proportionally to their contributed bandwidth; and (ii) natural incentive to join and cooperate fairly in the system.
展开▼
