advertisement

On Redundant Multipath Operating System Support for Wireless Mesh Networks

33 %
67 %
advertisement
Information about On Redundant Multipath Operating System Support for Wireless Mesh Networks

Published on June 24, 2008

Author: ralucam

Source: slideshare.net

Description

This is the talk I gave at WiMesh 2008, the third IEEE Workshop on Wireless Mesh Networks. WiMesh is co-located with SECON 2008.
advertisement

On Redundant Multipath Operating System Support for Wireless Mesh Networks Presented by Raluca Musaloiu-E. Johns Hopkins University Yair Claudiu Michael That’s Nilo Amir Danilov Kaplan Me Rivera

SMesh story

Redundant multipath routing is an essential service for increasing reliability in wireless mesh networks.

Redundant multipath is not natively supported by current operating systems.

Spines Spines Spines User space Kernel space Spines

A cost effective wireless mesh deployment requires low-cost mesh nodes.

TCP Throughput (Mbps) 11.0 9.9 8.8 7.7 6.6 5.5 4.4 CPU limitation! 3.3 2.2 2 2 2 1.1 2 2 0 1 hop 2 hops 3 hops 4 hops 5 hops Overlay

We present a minimally invasive mechanism to support redundant multipath routing in kernel-space. User space Control Kernel space Data routing

We present a minimally invasive mechanism to support redundant multipath routing in kernel-space. User space Control Module for Kernel space Data routing multipath

TCP Throughput (Mbps) 11.0 9.9 10 8.8 7.7 6.6 5.5 4.4 5 3.3 3 2.2 3 2 2 2 2 1.1 2 2 0 1 hop 2 hops 3 hops 4 hops 5 hops Overlay Redundat Multipath

Architecture

1 2 No To route, 3 Source consider Node 1 4 Node 2 entry point, 5 6 in addition to destination 7 address. Client 1 Fig. 1. The routes to a mobile client (m

1 2 Node 5 routing rules 3 Source Destination Next-Hop(s) Node 1 client 1 6 … … 4 Node 2 client 1 6, 7 5 … … 6 7 Client 1 Node 5 We use Fig. 1. The routes to a mobile client (multipath routing). multiple an overlay network to increase the reliability of the end- Node 3 to-end path. End-System-Multicast [14] and Spines [3] also route through an application router to support overlay multicas routing Node 2 without infrastructure support. Other work has looked into operating system support for tables. wireless ad-hoc routing protocols. Chakeres and Belding Node 1 showed in [9] an in-kernel design and implementation of the ad-hoc AODV protocol using Netfilter modules, and showed performance improvement compared to user-level ad-hoc pro- clienttocols. Kawadia et al. [16] proposed a complete architecture 1 clientto2support ad-hoc protocols in-kernel and a generic ad-hoc support library for user-level programs to control different ad- .... hoc protocols. SMesh [4] recently showed how overlay multicast can be used in wireless mesh networks to provide fast handoff to unmodified 802.11 clients that connect transparently using DHCP. SMesh allows multiple access points to service the client during handoff, as it works in ad-hoc mode. In SMesh packets sent by the mobile client are diverted from the kerne to the Spines user-level overlay router. Multicast trees are

1 2 Node 5 routing rules 3 Source Destination Next-Hop(s) Node 1 client 1 6 … … 4 Node 2 client 1 6, 7 5 … … 6 7 Client 1 Node 5 Each route may Fig. 1. The routes to a mobile client (multipath routing). have an overlay network to increase the reliability of the end- to-end path. End-System-Multicast [14] and Spines [3] also route through an application router to support overlay multicas multiple Node 1 without infrastructure support. Other work has looked into operating system support for next-hops. wireless ad-hoc routing protocols. Chakeres and Belding Destination Next-hops showed in [9] an in-kernel design and implementation of the ad-hoc AODV protocol using Netfilter modules, and showed client 1 6, 7 performance improvement compared to user-level ad-hoc pro- tocols. Kawadia et al. [16] proposed a complete architecture client 2 3 to support ad-hoc protocols in-kernel and a generic ad-hoc support library for user-level programs to control different ad- ... ... hoc protocols. SMesh [4] recently showed how overlay multicast can be used in wireless mesh networks to provide fast handoff to unmodified 802.11 clients that connect transparently using DHCP. SMesh allows multiple access points to service the client during handoff, as it works in ad-hoc mode. In SMesh packets sent by the mobile client are diverted from the kerne to the Spines user-level overlay router. Multicast trees are

Fig. 2. Architecture.

Implementation

0 78 15 16 23 24 31 Encode entry IHL TOS Total length Version Identification (IPID) Fragment offset node in the Flags TTL Protocol Header checksum packet’s Source IP IP header. Destination IP Options and padding

0 78 15 16 23 24 31 Encode entry IHL TOS Total length Version Identification (IPID) Fragment offset node in the Flags TTL Protocol Header checksum packet’s Source IP IP header. Destination IP Options and padding

0 78 15 16 23 24 31 Encode entry IHL TOS Total length Version Identification (IPID) Fragment offset node in the Flags TTL Protocol Header checksum packet’s Source IP IP header. Destination IP Options and padding

# iptables -A PREROUTING -t mangle -m u32 --u32 quot;2&0xFFFF=35quot; -j MARK --set-mark 35 Use policy routing and define multiple routing tables. # ip rule add fwmark 35 table 35

CONFIG_IP_ROUTE_MULTIPATH # ip route add 10.233.59.169/32 table 35 nexthop via 10.0.11.32 dev eth1 nexthop via 10.0.11.33 dev eth1 Use MULTIHOP Netfilter MULTIHOP module.

Fig. 3. Implementation in Linux.

5

5

IPID: 5 TOS 5

IPID: 5 TOS 5

IPID: 5 TOS 5 IPID: 5 TOS

IPID: 5 TOS 5 IPID: 5 TOS

5

Evaluation

One router 1 5 nodes wireless 2 “line” setup 17 nodes wireless 3 testbed

Rate 24 Mbps Transmission power 50 mW Retransmission limit 7 VoIP stream 64 Kbps

We route up to 50 duplex VoIP streams 1 before the CPU is saturated. Overlay 4 streams 512 Kbps Kernel 50 streams 6.4 Mbps Native kernel routing 60 streams 7.6 Mbps Pkts/s (sent + received) Pkts/s (sent + received) 400 800 1600 3200 4000 5000 6000 7000 400 800 1600 3200 4000 5000 6000 7000 1 100 Overlay Overlay Kernel Kernel Kernel without Multipath Kernel without Multipath 0.8 80 Loss rate (%) CPU Load 0.6 60 0.4 40 0.2 20 0 0 24 8 16 32 40 50 55 60 64 70 24 8 16 32 40 50 55 60 64 70 # of VoIP streams (each direction) # of VoIP streams (each direction)

2 TCP Throughput (Mbps) 11.0 10 9.9 8.8 7.7 With one wireless 6.6 5 5.5 hop, we get 10 Mbps 4.4 3 in a “line” setup. 3.3 3 2 2.2 2 2 2 1.1 2 2 0 1 hop 2 hops 3 hops 4 hops 5 hops Overlay Kernel

3 Overlay Kernel multipath 10 10 10 28 28 28 5 hops 5 hops 5 hops 9 9 26 9 26 26 4 hops 4 hops 4 hops 25 25 25 8 8 3 hops 8 3 hops 3 hops 24 24 24 2 hops 2 hops 2 hops 7 7 7 36 36 36 33 33 33 32 Throughput (Mbps) Throughput (Mbps) 32 32 Throughput (Mbps) 6 6 6 1 hop 1 hop 1 hop 31 Router ID 31 31 Router ID Router ID 5 5 5 4 4 4 3 3 3 2 2 2 1 1 1 0 0 0 0 50 100 150 200 250 300 0 20 40 60 80 100 120 140 50 100 150 200 250 300 0 20 40 60 80 100 120 140 160 Time (s) Time (s) Time (s) Time (s) TCPFig. 8. TCPOverlay (moving). throughput: throughput: Overlay (moving). TCP Fig. 9. TCP throughput: Kernel (moving). Fig. 8. Fig. 9. throughput: Kernel (moving). Results are close to the “line” topology 100 100 between the client and client and the Internet. Each (one-way) streams between the the Internet. Each (one-way) as stream of 64 Kbps. We monitored the averagethe average CPU90 a rate has a rate of 64 Kbps. We monitored CPU 90 ( 8.5 Mbps for one hop). ure 4) (Figure 4) and the(Figure 5). (Figure 5). The top x-axis80 load and the loss rate loss rate The top x-axis 80 e corresponding number of number of packets/sec. shows the corresponding packets/sec. 70 70 erstandunderstand overhead of our kernel our kernel approach,60 To better the better the overhead of approach, Percentage of packets Percentage of packets 60 ded an additional additional kernel routing without without50 we included an scenario: scenario: kernel routing 50 ead of Netfilterof Netfilter rules required by our scheme. We40 the overhead rules required by our scheme. We 40

Redundant multipath routing is important in WMN. We can support it with minimal changes in Linux kernel. SMesh is available as open-source at www.smesh.org.

Thanks

Questions

Add a comment

Related pages

On Redundant Multipath Operating System Support for ...

On Redundant Multipath Operating System Support for Wireless Mesh Networks Yair Amir1, Claudiu Danilov2, Michael A. Kaplan1, Raluca Musaloiu-Elefteri˘ 1 ...
Read more

On Redundant Multipath Operating System Support for ...

... for redundant multipath routing in ... System Support for Wireless Mesh Networks . ... Multipath Operating System Support for ...
Read more

On Redundant Multipath Operating System Support for ...

1. On Redundant Multipath Operating System Support for Wireless Mesh Networks Presented by Raluca Musaloiu-E ...
Read more

On Redundant Multipath Operating System Support for ...

On Redundant Multipath Operating System Support for Wireless Mesh Networks Amir, Y.; Danilov, C.; Kaplan, M.A.; Musaloiu-Elefteri, R.; Rivera, N. Low ...
Read more

On Redundant Multipath Operating System Support for ...

On Redundant Multipath Operating System Support for ... in a wireless mesh system, ... IEEE Annual Communications Society Conference on ...
Read more

On Redundant Multipath Operating System Support for ...

Publication » On Redundant Multipath Operating System Support for Wireless Mesh Networks.
Read more

SMesh

The SMesh Wireless Mesh Network (accepted version) ... On Redundant Multipath Operating System Support for Wireless Mesh Networks
Read more

Nilo Rivera - Johns Hopkins University

... , a seamless wireless mesh network for ... On Redundant Multipath Operating System Support for ... Rivera IEEE Workshop on Wireless Mesh ...
Read more

WiMesh 2008 - Trac - University of Wisconsin–Madison

About WiMesh 2008. Third IEEE Workshop on Wireless Mesh Networks ... On Redundant Multipath Operating System Support for Wireless Mesh Networks;
Read more