Browsing by Subject "Network Coding"
Now showing 1 - 8 of 8
Results Per Page
Sort Options
Item A Packet Scheduling Mechanism for Wireless Peer-to-Peer Content Distribution(2013-11-26) Liu, YaoThis thesis studies the problem of content distribution in wireless peer-to-peer networks with selfish nodes. In this problem a group of wireless nodes need to exchange a set of files over a lossless broadcast channel. Each node aims to maximize its own download rate and minimize its upload rate. We propose a distributed protocol that provides incentives for selfish nodes to participate in the content exchange. Our protocol does not require any exchange of money and reputation and hence can be easily implemented without additional infrastructure. Then, we will analyze the performance of our protocol by focusing on the import\-ant case in which the system contains two files that need to be distributed. We derive a closed-form expression of Nash Equilibrium and characterize the corresponding system performance in discrete time. Furthermore, we propose a distributed mechanism where the strategy of each node is only based on the observed history of the system and not on the private information of other nodes. We also study the performance characteristics of the systems that employ network coding to facilitate data exchange. We show that, due to the free rider problem network coding does not necessary improve the performance of the system and, in some cases, may lead to worse system performance. We propose a novel approach to this problem based on random coding. The performance of the network coding algorithms is validated by performing extensive simulation study.Item Application of network coding for VLSI routing(2009-05-15) Nemade, Nikhil PanditThis thesis studies the applications of the network coding technique for intercon- nect optimization and improving the routability of Very-large-scale integration (VLSI) designs. The goal of the routing process is to connect the required sets of sources and sinks while minimizing the total wirelength and reducing congestion. Typically, chip interconnects include multiple sinks and are routed through intermediate nodes. The main idea of the network coding technique is to enable the intermediate nodes to generate new signals by combining the signals received over their incoming wires. This is in contrast to the traditional approaches, in which an intermediate node can only forward the incoming signals. This thesis attempts to explore the possible ben- efits of the network coding technique for reducing the total wirelengh and mitigating congestion in VLSI designs. The contribution of the thesis is three-fold. First, we extend the Hanan?s theo- rem for multi-net rectilinear coding networks. Second, we propose several exact and heuristic solutions for finding near-optimal routing topologies that utilize network coding techniques. Next, we perform extensive simulation study to evaluate the ad- vantage of network coding over the traditional approaches. The simulations help to identify routing instances where the network coding techniques are expected to be beneficial. Finally, we evaluate the potential benefits from network coding in practical settings by analyzing its performance on the International Symposium on Physical Design (ISPD) benchmarks. Our results show that while network coding shows upto 2.43% improvement on unconstrained rectilinear grids, it shows upto 4.34% improvement in cases with con- straints along the grid. In addition, it shows an improvement upto 8.4% in cases involving congestion reduction and also improves routing performance on ISPD rout- ing benchmarks.Item Design and Implementation of Physical Layer Network Coding Protocols(2010-10-12) Maduike, Dumezie K.There has recently been growing interest in using physical layer network coding techniques to facilitate information transfer in wireless relay networks. The physical layer network coding technique takes advantage of the additive nature of wireless signals by allowing two terminals to transmit simultaneously to the relay node. This technique has several performance benefits, such as improving utilization and throughput of wireless channels and reducing delay. In this thesis, we present an algorithm for joint decoding of two unsynchronized transmitters to a modulo-2 sum of their transmitted messages. We address the problems that arise when the boundaries of the signals do not align with each other and when their phases are not identical. Our approach uses a state-based Viterbi decoding scheme that takes into account the timing offsets between the interfering signals. As a future research plan, we plan to utilize software-defined radios (SDRs) as a testbed to show the practicality of our approach and to verify its performance. Our simulation studies show that the decoder performs well with the only degrading factor being the noise level in the channel.Item Direct Information Exchange in Wireless Networks: A Coding Perspective(2011-10-21) Ozgul, DamlaThe rise in the popularity of smartphones such as Blackberry and iPhone creates a strain on the world's mobile networks. The extensive use of these mobile devices leads to increasing congestion and higher rate of node failures. This increasing demand of mobile wireless clients forces network providers to upgrade their wireless networks with more efficient and more reliable services to meet the demands of their customers. Therefore, there is a growing interest in strategies to resolve the problem and reduce the stress on the wireless networks. One strategy to reduce the strain on the wireless networks is to utilize cooperative communication. The purpose of this thesis is to provide more efficient and reliable solutions for direct information exchange problems. First, algorithms are presented to increase the efficiency of cooperative communication in a network where the clients can communicate with each other through a broadcast channel. These algorithms are designed to minimize the total transmission cost so that the communication will be less expensive and more efficient. Second, we consider a setting in which several clients exchange data through a relay. Our algorithms have provable performance guarantees. We also verify the performance of the algorithms in practical settings through extensive simulations.Item Hardware Prototyping of Two-Way Relay Systems(2012-10-19) Wu, QiongIn this thesis, I conduct the hardware prototyping of a two-way relay system using the National Instruments FlexRIO hardware platform. First of all, I develop several practical mechanisms to solve the critical synchronization issues of the systems, including Orthogonal Frequency-Division Multiplexing (OFDM) frame synchronization at the receiver, source to source node synchronization, and handshaking between the sources and relay nodes. Those synchronization methods control the behavior of the two source nodes and the relay node, which play critical roles in the two-way relay systems. Secondly, I develop a pilot-based channel estimation scheme and validate it by showing the successful self-interference cancellation for the two-way relay systems. In particular, I experiment the self-interference cancellation technique by using several channel estimation schemes to estimate both source to relay channels and relay to source channels. Moreover, I implement the physical layer of a 5 MHz OFDM scheme for the two-way relay system. Both the transmitter and receiver are designed to mimic the Long Term Evolution (LTE) downlink scenario. The physical layer of the transmitter has been implemented in Field-Programmable Gate Arrays (FPGAs) and executed on the hardware board, which provides high throughput and fundamental building blocks for the two-way relay system. The physical layer of receiver is implemented in the real-time controller, which provides the ?exibility to rapidly recon?gure the system. Finally, I demonstrate that the 5MHz OFDM based two-way relay system can achieve reliable communications, when the channel estimation and system synchronization can be correctly executed.Item Improving Network Reliability: Analysis, Methodology, and Algorithms(2010-07-14) Booker, Graham B.The reliability of networking and communication systems is vital for the nation's economy and security. Optical and cellular networks have become a critical infrastructure and are indispensable in emergency situations. This dissertation outlines methods for analyzing such infrastructures in the presence of catastrophic failures, such as a hurricane, as well as accidental failures of one or more components. Additionally, it presents a method for protecting against the loss of a single link in a multicast network along with a technique that enables wireless clients to efficiently recover lost data sent by their source through collaborative information exchange. Analysis of a network's reliability during a natural disaster can be assessed by simulating the conditions in which it is expected to perform. This dissertation conducts the analysis of a cellular infrastructure in the aftermath of a hurricane through Monte-Carlo sampling and presents alternative topologies which reduce resulting loss of calls. While previous research on restoration mechanisms for large-scale networks has mostly focused on handling the failures of single network elements, this dissertation examines the sampling methods used for simulating multiple failures. We present a quick method of nding a lower bound on a network's data loss through enumeration of possible cuts as well as an efficient method of nding a tighter lower bound through genetic algorithms leveraging the niching technique. Mitigation of data losses in a multicast network can be achieved by adding redundancy and employing advanced coding techniques. By using Maximum Rank Distance (MRD) codes at the source, a provider can create a parity packet which is e ectively linearly independent from the source packets such that all packets may be transmitted through the network using the network coding technique. This allows all sinks to recover all of the original data even with the failure of an edge within the network. Furthermore, this dissertation presents a method that allows a group of wireless clients to cooperatively recover from erasures (e.g., due to failures) by using the index coding techniques.Item Network and Index Coding with Application to Robust and Secure Communications(2011-02-22) El Rouayheb, Salim Y.Since its introduction in the year 2000 by Ahlswede et al., the network coding paradigm has revolutionized the way we understand information flows in networks. Traditionally, information transmitted in a communication network was treated as a commodity in a transportation network, much like cars on highways or fluids in pipes. This approach, however, fails to capture the very nature of information, which in contrast to material goods, can be coded and decoded. The network coding techniques take full advantage of the inherent properties of information, and allow the nodes in a network, not only to store and forward, but also to "mix", i.e., encode, their received data. This approach was shown to result in a substantial throughput gain over the traditional routing and tree packing techniques. In this dissertation, we study applications of network coding for guarantying reliable and secure information transmission in networks with compromised edges. First, we investigate the construction of robust network codes for achieving network resilience against link failures. We focus on the practical important case of unicast networks with non-uniform edge capacities where a single link can fail at a time. We demonstrate that these networks exhibit unique structural properties when they are minimal, i.e., when they do not contain redundant edges. Based on this structure, we prove that robust linear network codes exist for these networks over GF(2), and devise an efficient algorithm to construct them. Second, we consider the problem of securing a multicast network against an eavesdropper that can intercept the packets on a limited number of network links. We recast this problem as a network generalization of the classical wiretap channel of Type II introduced by Ozarow and Wyner in 1984. In particular, we demonstrate that perfect secrecy can be achieved by using the Ozarow-Wyner scheme of coset coding at the source, on top of the implemented network code. Consequently, we transparently recover important results available in the literature on secure network coding. We also derive new bounds on the required secure code alphabet size and an algorithm for code construction. In the last part of this dissertation, we study the connection between index coding, network coding, and matroid linear representation. We devise a reduction from the index coding problem to the network coding problem, implying that in the linear case these two problems are equivalent. We also present a second reduction from the matroid linear representability problem to index coding, and therefore, to network coding. The latter reduction establishes a strong connection between matroid theory and network coding theory. These two reductions are then used to construct special instances of the index coding problem where vector linear codes outperform scalar linear ones, and where non-linear encoding is needed to achieve the optimal number of transmission. Thereby, we provide a counterexample to a related conjecture in the literature and demonstrate the benefits of vector linear codes.Item Network Coding in Distributed, Dynamic, and Wireless Environments: Algorithms and Applications(2012-02-14) Chaudhry, MohammadThe network coding is a new paradigm that has been shown to improve throughput, fault tolerance, and other quality of service parameters in communication networks. The basic idea of the network coding techniques is to relish the "mixing" nature of the information flows, i.e., many algebraic operations (e.g., addition, subtraction etc.) can be performed over the data packets. Whereas traditionally information flows are treated as physical commodities (e.g., cars) over which algebraic operations can not be performed. In this dissertation we answer some of the important open questions related to the network coding. Our work can be divided into four major parts. Firstly, we focus on network code design for the dynamic networks, i.e., the networks with frequently changing topologies and frequently changing sets of users. Examples of such dynamic networks are content distribution networks, peer-to-peer networks, and mobile wireless networks. A change in the network might result in infeasibility of the previously assigned feasible network code, i.e., all the users might not be able to receive their demands. The central problem in the design of a feasible network code is to assign local encoding coefficients for each pair of links in a way that allows every user to decode the required packets. We analyze the problem of maintaining the feasibility of a network code, and provide bounds on the number of modifications required under dynamic settings. We also present distributed algorithms for the network code design, and propose a new path-based assignment of encoding coefficients to construct a feasible network code. Secondly, we investigate the network coding problems in wireless networks. It has been shown that network coding techniques can significantly increase the overall throughput of wireless networks by taking advantage of their broadcast nature. In wireless networks each packet transmitted by a device is broadcasted within a certain area and can be overheard by the neighboring devices. When a device needs to transmit packets, it employs the Index Coding that uses the knowledge of what the device's neighbors have heard in order to reduce the number of transmissions. With the Index Coding, each transmitted packet can be a linear combination of the original packets. The Index Coding problem has been proven to be NP-hard, and NP-hard to approximate. We propose an efficient exact, and several heuristic solutions for the Index Coding problem. Noting that the Index Coding problem is NP-hard to approximate, we look at it from a novel perspective and define the Complementary Index Coding problem, where the objective is to maximize the number of transmissions that are saved by employing coding compared to the solution that does not involve coding. We prove that the Complementary Index Coding problem can be approximated in several cases of practical importance. We investigate both the multiple unicast and multiple multicast scenarios for the Complementary Index Coding problem for computational complexity, and provide polynomial time approximation algorithms. Thirdly, we consider the problem of accessing large data files stored at multiple locations across a content distribution, peer-to-peer, or massive storage network. Parts of the data can be stored in either original form, or encoded form at multiple network locations. Clients access the parts of the data through simultaneous downloads from several servers across the network. For each link used client has to pay some cost. A client might not be able to access a subset of servers simultaneously due to network restrictions e.g., congestion etc. Furthermore, a subset of the servers might contain correlated data, and accessing such a subset might not increase amount of information at the client. We present a novel efficient polynomial-time solution for this problem that leverages the matroid theory. Fourthly, we explore applications of the network coding for congestion mitigation and over flow avoidance in the global routing stage of Very Large Scale Integration (VLSI) physical design. Smaller and smarter devices have resulted in a significant increase in the density of on-chip components, which has given rise to congestion and over flow as critical issues in on-chip networks. We present novel techniques and algorithms for reducing congestion and minimizing over flows.