This 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.

As the rapid evolution of the technology and the network communication, people can share the multimedia content more easily through the Internet. And devices for accessing the Internet include not only the desktop computers but also cell phones, PDAs, and computers on the vehicles. Vehicular ad-hoc networks, which allow mobile users to access the Internet with the computers on cars is one of the most promising technology in the near future. Through VANET, vehicles can not only share the traffic information to avoid accidents, but also exchange the multimedia content through the peer to peer sharing technology. In this thesis we propose using the network coding technology to encode/decode the file blocks in VANET, clustering the vehicles according to their mobility, and combining the ROMSGP and modifying the priority method of the VANETCODE scheme in order to enhance the overall performance of VANETs.

The imperfections of the propagation channel due to channel fading and the self-generated noise from the RF front-end of the receiver cause errors in the received signal in electronic communication systems. When network coding is applied, more errors occur because of error propagation due to the inexact decoding process. In this dissertation we present a system called Partial Network Coding with Cooperation (PNC-COOP) for wireless ad hoc networks. It is a system which combines opportunistic network coding with decode-and-forward cooperative diversity, in order to reduce this error propagation by trading off some transmission degrees of freedom. PNC-COOP is a decentralized, energy efficient strategy which provides a substantial benefit over opportunistic network coding when transmission power is a concern. The proposed scheme is compared with both opportunistic network coding and conventional multi-hop transmission analytically and through simulation. Using a 3-hop communication scenario, in a 16-node wireless ad hoc network, it is shown that PNC-COOP improves the BER performance by 5 dB compared to opportunistic network coding. On average, it reduces the energy used by each sender node around 10% and reduces the overall transmitted energy of the network by 3.5%. When retransmission is applied, it is shown analytically that PNC-COOP performs well at relatively low to medium SNR while the throughput is comparable to that of opportunistic network coding. The effectiveness of both opportunistic network coding and PNC-COOP depends not only on the amount of network coding but also on other factors that are analyzed and discussed in this dissertation. / Graduation date: 2011 / Access restricted to the OSU Community at author's request from May 12, 2011 - May 12, 2012

The 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.

We study the application of network coding in periodic safety broadcasting in Vehicular Ad hoc Networks. We design a sub-layer in the application layer of the WAVE architecture. Our design uses rebroadcasting of network coded safety messages, which considerably improves the overall reliability. It also tackles the synchronized collision problem stated in the IEEE 1609.4 standard as well as congestion problem and vehicle-to-vehicle channel loss. We study how massage repetition can be used to optimize the reliability in combination with a simple congestion control algorithm. We analytically evaluate the application of network coding using a sequence of discrete phase-type distributions. Based on this model, a tight safety message loss probability upper bound is derived. Completion delay is defined as the delay that a node receives the messages of its neighbour nodes. We provide asymptotic delay analysis and prove a general and a restricted tighter asymptotic upper bound for the completion delay of random linear network coding. For some safety applications, average vehicle to vehicle reception delay is of interest. An instantly decodable network coding based on heuristics of index coding problem is proposed. Each node at each transmission opportunity tries to XOR some of its received original messages. The decision is made in a greedy manner and based on the side information provided by the feedback matrix. A distributed feedback mechanism is also introduced to piggyback the side information in the safety messages. We also construct a Tanner graph based on the feedback information and use the Belief Propagation algorithm as an efficient heuristic similar to LDPC decoding. Layered BP is shown to be an effective algorithm for our application. Lastly, we present a simple experimental framework to evaluate the performance of repetition based MAC protocols. We conduct an experiment to compare the POC-based MAC protocol with a random repetition-based MAC.

We study the application of network coding in periodic safety broadcasting in Vehicular Ad hoc Networks. We design a sub-layer in the application layer of the WAVE architecture. Our design uses rebroadcasting of network coded safety messages, which considerably improves the overall reliability. It also tackles the synchronized collision problem stated in the IEEE 1609.4 standard as well as congestion problem and vehicle-to-vehicle channel loss. We study how massage repetition can be used to optimize the reliability in combination with a simple congestion control algorithm. We analytically evaluate the application of network coding using a sequence of discrete phase-type distributions. Based on this model, a tight safety message loss probability upper bound is derived. Completion delay is defined as the delay that a node receives the messages of its neighbour nodes. We provide asymptotic delay analysis and prove a general and a restricted tighter asymptotic upper bound for the completion delay of random linear network coding. For some safety applications, average vehicle to vehicle reception delay is of interest. An instantly decodable network coding based on heuristics of index coding problem is proposed. Each node at each transmission opportunity tries to XOR some of its received original messages. The decision is made in a greedy manner and based on the side information provided by the feedback matrix. A distributed feedback mechanism is also introduced to piggyback the side information in the safety messages. We also construct a Tanner graph based on the feedback information and use the Belief Propagation algorithm as an efficient heuristic similar to LDPC decoding. Layered BP is shown to be an effective algorithm for our application. Lastly, we present a simple experimental framework to evaluate the performance of repetition based MAC protocols. We conduct an experiment to compare the POC-based MAC protocol with a random repetition-based MAC.

No description available.

Network coding is a promising technology that many researchers have advocated due to its potentially significant benefits to improve the efficiency of data transmission. In this thesis, we use simulations to evaluate the performance of different network topologies using network coding. By comparing the results with networks without network coding, we confirm that network coding can improve the network throughput. It also has a potential to decrease the end to end delay and improve the reliability. However, there are tradeoff (between delay and reliability) when network coding is used, and some limitations which we summarize. Finally, we have also implemented network coding to a three-dimensional underwater network by using parameters that truly reflect the underwater channel. Our performance evaluations show a better throughput and end-to-end delay but not the PDR (Packet Delivery Rate) in the underwater topology we used.

This dissertation devotes itself to algorithmic approaches to the problem of scalable multicast with network coding. Several original contributions can be concluded as follows. We have proved that the scalable multicast problem is NP-hard, even with the ability to perform network coding at the network nodes. Several approximations are derived based on different heuristics, and systematic approaches have been devised to solve those problems. We showed that those traditional routing methods reduce to a special case in the new network coding context. Two important frameworks usually found in traditional scalable multicast solutions, i.e. layered multicast and rainbow multicast, are studied and extended to the network coding scenario. Solutions based on these two frameworks are also presented and compared. Suprisingly, these two distinctive approaches in the traditional sense become connected and share a similar essence of data mixing in the light of network coding. Cases are presented where these two approaches become equivalent and achieve the same Performance. We have made significant advances in constructing good solutions to the scalable multicast problem by solving various optimization problems formulated in our approaches. In the layered multicast framework, we started with a straight-forward extension of the traditional layered multicast to the network coding context. The proposed method features an intra-layer network coding technique which is applied on different optimized multicast graphs. Later on, we further improved this method by introducing the inter-layer network coding concept. By allowing network coding among data from different data layers, more leverage is gained when optimizing the network flow, thus higher performance is achieved. In the rainbow multicast framework, we choose uneven erasure protection (UEP) technique as the practical way of constructing balanced MDC, and optimize this MDC design using the max-flow information of receivers. After the MDC design is finalized, a single linear network broadcast code is employed to deliver MDC encoded data to receivers while satisfying the individual max-flow of all the receivers. Although this rainbow multicast based solution may sacrifice the performance in some cases, it greatly simplifies the rate allocation problem raised in the layered multicast framework. The use of one single network code also makes the network codes construction process a lot clearer. Extensive amount of simulation is performed and the results show that network coding based scalable multicast solutions can significantly outperform those traditional routing based solutions. In addition to the imaginary linear objective function used in the simulation, the practical convex objective function and real video data are also used to verify the effectiveness of the proposed solutions. The role of different parameters in the proposed approaches are analyzed, which gives us more guidelines on how to fine-tune the system. / Thesis / Doctor of Philosophy (PhD)

Network coding allows each node in a network to perform some coding operations on the data packets and improve the overall throughput of communication. However, network coding cannot be done unless there are enough packets to be coded so at times it may be advantageous to wait for packets to arrive. We consider a scenario in which two wireless nodes each with its own buffer communicate via a single access point using network coding. The access point first pairs each data packet being sent from each node and then performs the network coding operation. Packets arriving at the access point that are unable to be paired are instead loaded into one of the two buffers at the access point. In the case where one of the buffers is empty and the other is not network coding is not possible. When this happens the access point must either wait for a network coding opportunity, or transmit the unpaired packet without coding. Delaying packet transmission is associated with an increased waiting cost but also allows for an increase in the overall efficiency of wireless spectrum usage, thus a decrease in packet transmission cost. Conversely, sending packets un-coded is associated with a decrease in waiting cost but also a decrease in the overall efficiency of the wireless spectrum usage. Hence, there is a trade-off between decreasing packet delay time, and increasing the efficiency of the wireless spectrum usage. We show that the optimal waiting policy for this system with respect to total cost, under phase-type packet arrivals, is to have a separate threshold for the buffer size that is dependent on the current phase of each arrival. We then show that the solution to this optimization problem can be obtained by treating it as a double ended push-out queueing theory problem. We develop a new technique to keep track of the packet waiting time and the number of packets waiting in the two ended push-out queue. We use the resulting queueing model to resolve the optimal threshold policy and then analyze the performance of the system using numerical approach. / October 2016