Browsing by Subject "network coding"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
Item Delay-aware Scheduling in Wireless Coding Networks: To Wait or Not to Wait(2012-02-14) Ramasamy, SolairajaWireless technology has become an increasingly popular way to gain network access. Wireless networks are expected to provide efficient and reliable service and support a broad range of emerging applications, such as multimedia streaming and video conferencing. However, limited wireless spectrum together with interference and fading pose signi cant challenges for network designers. The novel technique of network coding has a significant potential for improving the throughput and reliability of wireless networks by taking advantage of the broadcast nature of wireless medium. Reverse carpooling is one of the main techniques used to realize the benefits of network coding in wireless networks. With reverse carpooling, two flows are traveling in opposite directions, sharing a common path. The network coding is performed in the intermediate (relay) nodes, which saves up to 50% of transmissions. In this thesis, we focus on the scheduling at the relay nodes in wireless networks with reverse carpooling. When two packets traveling in opposite directions are available at the relay node, the relay node combines them and broadcasts the resulting packet. This event is referred to as a coding opportunity. When only one packet is available, the relay node needs to decide whether to wait for future coding opportunities, or to transmit them without coding. Though the choice of holding packets exploits the positive aspects of network coding, without a proper policy in place that controls how long the packets should wait, it will have an adverse impact on delays and thus the overall network performance. Accordingly, our goal is to find an optimal control strategy that delicately balances the tradeoff between the number of transmissions and delays incurred by the packets. We also address the fundamental question of what local information we should keep track of and use in making the decision of of whether to transmit uncoded packet or wait for the next coding opportunity. The available information consists of queue length and time stamps indicating the arrival time of packets in the queue. We could also store history of all previous states and actions. However, using all this information makes the control very complex and so we try to find if the overhead in collecting waiting times and historical information is worth it. A major contribution of this thesis is a stochastic control framework that uses state information based on what can be observed and prescribes an optimal action. For that, we formulate and solve a stochastic dynamic program with the objective of minimizing the long run average cost per unit time incurred due to transmissions and delays. Subsequently, we show that a stationary policy based on queue lengths is optimal, and the optimal policy is of threshold-type. Then, we describe a non-linear optimization procedure to obtain the optimal thresholds. Further, we substantiate our analytical ndings by performing numerical experiments under varied settings. We compare systems that use only queue length with those where more information is available, and we show that optimal control that uses only the queue length is as good as any optimal control that relies on knowing the entire history.Item Delay-sensitive Communications Code-Rates, Strategies, and Distributed Control(2012-02-14) Parag, ParimalAn ever increasing demand for instant and reliable information on modern communication networks forces codewords to operate in a non-asymptotic regime. To achieve reliability for imperfect channels in this regime, codewords need to be retransmitted from receiver to the transmit buffer, aided by a fast feedback mechanism. Large occupancy of this buffer results in longer communication delays. Therefore, codewords need to be designed carefully to reduce transmit queue-length and thus the delay experienced in this buffer. We first study the consequences of physical layer decisions on the transmit buffer occupancy. We develop an analytical framework to relate physical layer channel to the transmit buffer occupancy. We compute the optimal code-rate for finite-length codewords operating over a correlated channel, under certain communication service guarantees. We show that channel memory has a significant impact on this optimal code-rate. Next, we study the delay in small ad-hoc networks. In particular, we find out what rates can be supported on a small network, when each flow has a certain end-to-end service guarantee. To this end, service guarantee at each intermediate link is characterized. These results are applied to study the potential benefits of setting up a network suitable for network coding in multicast. In particular, we quantify the gains of network coding over classic routing for service provisioned multicast communication over butterfly networks. In the wireless setting, we study the trade-off between communications gains achieved by network coding and the cost to set-up a network enabling network coding. In particular, we show existence of scenarios where one should not attempt to create a network suitable for coding. Insights obtained from these studies are applied to design a distributed rate control algorithm in a large network. This algorithm maximizes sum-utility of all flows, while satisfying per-flow end-to-end service guarantees. We introduce a notion of effective-capacity per communication link that captures the service requirements of flows sharing this link. Each link maintains a price and effective-capacity, and each flow maintains rate and dissatisfaction. Flows and links update their respective variables locally, and we show that their decisions drive the system to an optimal point. We implemented our algorithm on a network simulator and studied its convergence behavior on few networks of practical interest.Item Design and Analysis of Low Complexity Network Coding Schemes(2012-02-20) Tabatabaei-Yazdi, SeyedIn classical network information theory, information packets are treated as commodities, and the nodes of the network are only allowed to duplicate and forward the packets. The new paradigm of network coding, which was introduced by Ahlswede et al., states that if the nodes are permitted to combine the information packets and forward a function of them, the throughput of the network can dramatically increase. In this dissertation we focused on the design and analysis of low complexity network coding schemes for different topologies of wired and wireless networks. In the first part we studied the routing capacity of wired networks. We provided a description of the routing capacity region in terms of a finite set of linear inequalities. We next used this result to study the routing capacity region of undirected ring networks for two multimessage scenarios. Finally, we used new network coding bounds to prove the optimality of routing schemes in these two scenarios. In the second part, we studied node-constrained line and star networks. We derived the multiple multicast capacity region of node-constrained line networks based on a low complexity binary linear coding scheme. For star networks, we examined the multiple unicast problem and offered a linear coding scheme. Then we made a connection between the network coding in a node-constrained star network and the problem of index coding with side information. In the third part, we studied the linear deterministic model of relay networks (LDRN). We focused on a unicast session and derived a simple capacity-achieving transmission scheme. We obtained our scheme by a connection to the submodular flow problem through the application of tools from matroid theory and submodular optimization theory. We also offered polynomial-time algorithms for calculating the capacity of the network and the optimal coding scheme. In the final part, we considered the multicasting problem in an LDRN and proposed a new way to construct a coding scheme. Our construction is based on the notion of flow for a unicast session in the third part of this dissertation. We presented randomized and deterministic polynomial-time versions of our algorithm.Item On Combining Duty-cycling with Network Coding in Flood-based Sensor Networks(2012-02-14) Chandanala, Roja RamaniNetwork coding and duty-cycling are two popular techniques for saving energy in wireless sensor networks. To the best of our knowledge, the idea to combine these two techniques, for even more aggressive energy savings, has not been explored. One explanation is that these two techniques achieve energy efficiency through conflicting means, e.g., network coding saves energy by exploiting overhearing, whereas dutycycling saves energy by cutting idle listening and, thus, overhearing. In this thesis, we thoroughly evaluate the use of network coding in duty-cycled sensor networks. We propose a scheme called DutyCode, in which a MAC protocol implements packet streaming and allows the application to decide when a node can sleep. Additionally, a novel, efficient coding scheme decision algorithm, ECSDT, assists DutyCode to reduce further energy consumption by minimizing redundant packet transmissions, while an adaptive mode switching algorithm allows smooth and timely transition between DutyCode and the default MAC protocol, without any packet loss. We investigate our solution analytically, implement it on mote hardware, and evaluate it in a 42-node indoor testbed. Performance evaluation results show that our scheme saves 30-46% more energy than solutions that use network coding, without using duty-cycling.