The majority of today’s communication networks rely on a layered protocol architecture that sepa- rates physical aspects, medium access control, and routing. While physical layer implementations are under constant development, most protocols on the network layer concerned with routing are built around two well-studied approaches: distance vector [1, 2] and link state [3] – both allowing for efficient distributed implementations. The functional principle of such protocols is to determine the shortest path according to some metric from a source of traffic to the respective destination. However, they inherently lack support for concurrent paths, i.e., only the best path is chosen along which traffic is forwarded. As a consequence, these protocols are generally suboptimal in terms of throughput. Instead of finding a single best path, routing can also be considered as the process of determining an optimal set of paths from source to destination which supports a specific input rate. The question arises why most routing protocols are designed in this suboptimal way. The an- swer to this question is, that lack of concurrent paths is not solely due to restrictions of the routing protocols but in particular due to the inability of network and transport layer protocols to support concurrent forwarding paths. Using multiple paths results in packets arriving out of order at the destination Depending on the transport layer protocol in use, this might interfere with congestion control mechanisms. In case of the transmission control protocol (TCP), packets arriving out of order cause duplicate acknowledgements for the next data byte1 that is expected. When the sender receives duplicate acknowledgements, it assumes a mild congestion along the forwarding path and cuts the transmit rate in half. If duplicate acknowledgements are not caused by congestion but are due to differing delays along multiple paths, TCP wrongly reduces the sender’s rate. This situa- tion can quickly result in awful data rates prohibiting any useful application. As a result, it is not sufficient to design a multipath-aware routing protocol. Instead it would be necessary to hide from the transport layer that more than one path is used – or, alternatively, design new transport layer protocols. The latter is not an option since virtually any communication relies on one of two trans- port layer protocols: the stateless and unreliable user datagram protocol (UDP) and its stateful and reliable counterpart TCP. Updating these protocols is very difficult since new versions must remain fully backward compatible. This single-path view in today’s networks leads to another restriction: The best next-hop of a packet is determined according to a node’s routing table before that packet is sent. This approach prohibits to take advantage of a broadcast medium. Consider a wireless network where each node has in general more than one neighbor in transmit range. According to the actual routing table and the destination as indicated by a packet’s destination IP address, a node determines the best next hop for that packet. Afterwards, the packet is enveloped in a new link layer header with the next hop’s hardware address as immediate destination and sent over the wireless link. It might happen that the intended next hop does not receive the packet but some other neighbors do. Eventually, one of those successful receivers would be the next hop of a suboptimal route to the destination. Consequently, it would be beneficial if one of those nodes would forward the frame. However, this does not happen since the packet was explicitly addressed to best next hop – all other neighbors would discard it. The possibility that other nodes forward overheard packets is known as wireless broadcast advantage and is to the best of our knowledge not exploited by any packet network so far. Towards a coded wireless mesh network we started to implement a set of user space processes that allow fully transparent access to the network. This is achieved by creating a virtual link layer network interface that can be used just like a wired network interface. For higher layer protocols, starting at the address resolution protocols of IP and IPv6, the wireless network remains hidden. We believe that remaining oblivious to any higher layer protocols is a key strategy for successful deployment of network coding. With this in mind we designed set of coding and acknowledgement schemes that allow for oblivious intrasession network coding at the lowest layer possible without directly modifying device drivers or hardware. The remainder of this report is organized as follows: We start with a brief introduction to finite field arithmetics in Section 2 and investigate the impact of different field sizes on decoding probability, overhead, and computational complexity. Section 3 introduces the network model for the theoretic discussion of coding operations. Afterwards, coding on unidirectional data flows is described in Section 4 and extended to bidirectional data flows in Section 5. The acknowledgement scheme used by our protocol is formally presented in Section 6 by means of time discrete Markov chains. This also includes numerical results on the expected performance. Finally, Section 7 gives some remarks on practical design issues not covered in the formal description.     «

The majority of today’s communication networks rely on a layered protocol architecture that sepa- rates physical aspects, medium access control, and routing. While physical layer implementations are under constant development, most protocols on the network layer concerned with routing are built around two well-studied approaches: distance vector [1, 2] and link state [3] – both allowing for efficient distributed implementations. The functional principle of such protocols is to determine the shor...     »