XORs in The Air: Practical Wireless Network Coding

XORs in The Air: Practical Wireless Network Coding

September 11–15, 2006, Pisa, Italy | Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, Jon Crowcroft
This paper introduces COPE, a new architecture for wireless mesh networks that improves throughput by mixing (i.e., coding) packets from different sources. COPE inserts a coding shim between the IP and MAC layers, which identifies coding opportunities and benefits from them by forwarding multiple packets in a single transmission. The design is rooted in network coding theory, which allows routers to mix information content in packets before forwarding them. Prior work on network coding is mainly theoretical and focuses on multicast traffic, while COPE addresses unicast traffic, dynamic and bursty flows, and practical issues in network coding integration. COPE exploits the broadcast nature of wireless channels, allowing nodes to overhear packets and store them for a short time. Nodes also broadcast reception reports to inform neighbors of stored packets. When a node transmits, it uses knowledge of neighbors' heard packets to perform opportunistic coding, XORing multiple packets and transmitting them as a single packet if each intended nexthop can decode the encoded packet. This extends COPE beyond two flows and allows it to XOR more than a pair of packets. COPE's design is based on two key principles: (1) embracing the broadcast nature of wireless channels and (2) employing network coding. The paper evaluates COPE on a 20-node wireless network, showing that it significantly increases throughput. Gains vary from a few percent to several folds depending on traffic patterns, congestion levels, and transport protocols. COPE's performance is studied in various topologies, including chain, "X", cross, and wheel. Theoretical analysis shows that COPE's maximum coding gain is 2, and with opportunistic listening, it can achieve unbounded gains. The paper also discusses the interaction between coding and MAC protocols, showing that COPE can achieve Coding+MAC gains of up to 4. COPE's implementation includes a packet coding algorithm that prioritizes packets of similar lengths, maintains virtual queues for small and large packets, and ensures packets are decoded correctly. It also includes a pseudo-broadcast mechanism that leverages 802.11 unicast for reliability and backoff. COPE also handles packet reordering and ensures TCP packets are delivered in order. The paper presents experimental results showing that COPE increases throughput by 3-4x in congested environments with UDP traffic, and up to 70% in mesh networks connected to the Internet. In environments with hidden terminals, TCP throughput improvements are limited, while UDP gains are higher due to the Coding+MAC effect. The results demonstrate that COPE significantly improves wireless throughput, especially in scenarios with high congestion and bursty traffic.This paper introduces COPE, a new architecture for wireless mesh networks that improves throughput by mixing (i.e., coding) packets from different sources. COPE inserts a coding shim between the IP and MAC layers, which identifies coding opportunities and benefits from them by forwarding multiple packets in a single transmission. The design is rooted in network coding theory, which allows routers to mix information content in packets before forwarding them. Prior work on network coding is mainly theoretical and focuses on multicast traffic, while COPE addresses unicast traffic, dynamic and bursty flows, and practical issues in network coding integration. COPE exploits the broadcast nature of wireless channels, allowing nodes to overhear packets and store them for a short time. Nodes also broadcast reception reports to inform neighbors of stored packets. When a node transmits, it uses knowledge of neighbors' heard packets to perform opportunistic coding, XORing multiple packets and transmitting them as a single packet if each intended nexthop can decode the encoded packet. This extends COPE beyond two flows and allows it to XOR more than a pair of packets. COPE's design is based on two key principles: (1) embracing the broadcast nature of wireless channels and (2) employing network coding. The paper evaluates COPE on a 20-node wireless network, showing that it significantly increases throughput. Gains vary from a few percent to several folds depending on traffic patterns, congestion levels, and transport protocols. COPE's performance is studied in various topologies, including chain, "X", cross, and wheel. Theoretical analysis shows that COPE's maximum coding gain is 2, and with opportunistic listening, it can achieve unbounded gains. The paper also discusses the interaction between coding and MAC protocols, showing that COPE can achieve Coding+MAC gains of up to 4. COPE's implementation includes a packet coding algorithm that prioritizes packets of similar lengths, maintains virtual queues for small and large packets, and ensures packets are decoded correctly. It also includes a pseudo-broadcast mechanism that leverages 802.11 unicast for reliability and backoff. COPE also handles packet reordering and ensures TCP packets are delivered in order. The paper presents experimental results showing that COPE increases throughput by 3-4x in congested environments with UDP traffic, and up to 70% in mesh networks connected to the Internet. In environments with hidden terminals, TCP throughput improvements are limited, while UDP gains are higher due to the Coding+MAC effect. The results demonstrate that COPE significantly improves wireless throughput, especially in scenarios with high congestion and bursty traffic.
Reach us at info@study.space
[slides] XORs in the Air%3A Practical Wireless Network Coding | StudySpace