REPOSITORY > RESULTS

Doctoral dissertation

Dynamic network coding-aware routing in wireless networks

Author(s): Erik Pertovt (Author), Mihael Mohorčič (Supervisor), Aleš Švigelj (Co-Supervisor)

Thesis defense date: 17.12.2015

Organization: MPŠ - Mednarodna podiplomska šola Jožefa Stefana

PID: 20.500.12556/ReVIS-15062

Views: 2 | Downloads: 0

Abstract

Opportunistic network coding is an approach recently investigated for increasing the network throughput and thus enhancing the performance of wireless mesh networks. The benefits of network coding can further be improved when routing decisions are made with the awareness of coding. Typically, the goal of network coding-aware routing is to find and exploit routes with new coding opportunities and thus increase the network throughput.
The aim of this dissertation is to show that the coding awareness along with the information of the measured traffic coding success can be efficiently used for congestion avoidance, thus indirectly increasing the coding gain and the network throughput. We propose a new proactive routing procedure called Congestion-Avoidance Network Coding-Aware Routing (CANCAR), in which the most loaded node is detected and prevented from saturation by diverting some of the least-coded traffic flows around this node. By doing so, CANCAR enables: 1) even higher coding gain achieved by the remaining well-coded traffic flows on the node, 2) possibly better encoding of the diverted non-coded or less-coded traffic flows along the alternative routes, and 3) lower traffic loads traversing the currently most loaded node and its neighborhood.
In the dissertation, we first present the basic principles of opportunistic network coding in wireless mesh networks. We show the benefits of using network coding in theoretical topologies and present COPE network coding procedure, which exploits coding opportunities that occur on a per-hop basis between nodes. Furthermore, we present the basics and classification of dynamic routing procedures in wireless mesh networks, as well as the benefits of network coding-aware routing with an overview and evaluation of the prior work. In the latter, coding opportunities are computed based on the given topology and temporal traffic in the network to discover paths with more coding opportunities. Most of the proposed schemes are based on on-demand (i.e., reactive) source routing paradigm, requiring firstly the acquisition of the routing information obtained by a route discovery protocol, which introduces additional delay, making these routing schemes suited for rather sparse and static communication patterns.
As an alternative solution, we propose a novel routing procedure called CANCAR, which explores the actually measured coding success in various traffic flows. By detecting high traffic in the network and discriminating between well and poorly-coded traffic flows in congested area of the network, it primarily facilitates rerouting of poorly-coded traffic away from most loaded parts of the network and thus avoiding the congestion and increasing the number of coding opportunities in the network. The proposed implementation of CANCAR is based on table-driven (or proactive) per-hop routing, which is better suited for dense communication patterns. For the routes calculation, Dijkstra’s link-state routing algorithm with ETX additive metric for link cost is used as conventional routing. We consider COPE as a reference underlying network coding procedure also used by CANCAR, although the latter can be used with other opportunistic network coding algorithms.
We evaluated the CANCAR routing procedure in a modular network coding simulation model, which enables using various traffic patterns. In the model, the key functionalities for the performance evaluation from the routing point of view are implemented, including a novel model of packet transmission via wireless link, developed for consideration of the wireless link characteristics in investigation of network layer procedures, where the number of simulation events needs to be as low as possible to keep the simulation complexity at a manageable level. This is particularly important in studies requiring very intensive traffic loads, such as in case of network coding procedures.
The performance of CANCAR is evaluated on the results of network goodput, the node coding gain, the number of encoded packets, coding opportunities in flows and coding opportunities on nodes. We quantify the benefits of CANCAR over the network coding with the conventional coding unaware routing. The simulation results obtained in a small reference network topology and in larger synthetically generated network topologies show that the proposed routing procedure CANCAR combined with the well-known COPE network coding avoids network congestion and provides higher coding gains, thus achieving significantly higher throughput and enabling higher traffic loads.

Attachments

Cite this work