[Mobile Internet Technology] Multi-Hop Networks – Routing

 Multi-Hop Networks – Routing

Notes from RWTH Aachen University course 
“Mobile Internet Technology” Summer semester 2020
professor: Drik Thißen

Multi-Hop Networks – Routing

Mobile internet access

• Typical structure:

  1. WLAN: via APs
     • restricted to some geographical region (LAN)
  2. Wi-Fi communities
     • No dedicated (專用的) distributed system
     • Mobility support is much harder

  \(\Rightarrow\) Wireless distributed system

Multihop networks

Mobile Ad-hoc Network (MANET)

• enhancement of ad-hoc
  • no APs
  • devices act as routers
• Mobility causes changing connection structure
  \(\Rightarrow\) self-configuring network

Wireless Mesh Network (WMN)

• defined in 802.11s
• static as well as mobile nodes as routers (usually static)

Routing

• Important topic for MANET and WMN
  • Usefulness depends on ability to forward data
    • wireless link characteristics
    • medium access protocol
  • additional challenges:
    • node mobility
    • link interference

Distance Vector

• Periodic exchange information with neighbors
  • destination and costs
• Selection of shortest path
• Slow convergence
• Inefficient: too much changes in topology

Link State

• Periodic exchange local information
• Routers get a complete map
• Overhead: frequent flooding
• Inefficient: restricted bandwidth

---

• Problems:
  1. Dynamic topology
     • link changing
     • link quality
     • node changing
  2. Asymmetric connections
  3. Redundant links
  4. Limited performance of mobile devices and wireless links
  5. Interference
• Requirements:
  1. Self-starting, self-organizing
  2. Dynamic topology maintenance
  3. minimum traffic overhead
  4. rapid route convergence
  5. low consumption of CPU, memory and bandwidth
  6. scalable to large number of nodes
• Metrics
  Measuring usefulness of a path
  • hop-count is not suitable
    • asymmetric link
    • data loss rate
    • data rate

Expected Transmission Count (ETX)

• Expect number of transmission required
• \[\text{ETX}=\frac{1}{\text{FDR}\cdot\text{RDR}}\]
  \(\text{FDR}:\) Forward Delivery Ratio
  \(\text{RDR}:\) Reverse Delivery Ratio
• Each node sends probe packets every \(t\) seconds and wait for ACKs

Expected Transmission Time (ETT)

• Enhancement: considering packet size and data rate
• \[\text{ETT}=\text{ETX}\cdot\frac{S}{B}\]
  \(S:\) average packet size
  \(B:\) bandwidth

Weighted Cumulative ETT (WCETT)

• Enhancement: consider interference
• trade-off between low loss / high data rate and channel diversity
• \[\text{WCETT}(p)=(1-\beta)\sum_{e\in p}\text{ETT}(p)+\beta\cdot \max_{j\in C}\{X_j(p)\}\]
  \(p:\) path in the network
  \(C:\) set of edge labels
  \(j:\) channel number
  \(\beta:\) tuning parameter

Routing Algorithm

Reactive

• high latency
• low overhead

Dynamic Source Routing (DSR)

• Path Discovering

  • Search for a path to the destination if packets are sent
  1. Broadcast a RREQ (route request) with destination address and ID (flooding)
  2. If a station receive a control packet
     • If the packet is received for the first time (first seen ID)
       • append its own address
       • (random delay) broadcast
     • If the packet has been received before
       • discard
     • If a station has the searched destination address
       • return RREP (rout reply)
       • backward learning of the rout from destination to source

• Path Maintenance

  • when sending a packet, fill in the whole path information
    • As IP header option
  • After sending a packet:
    • Wait for ACK
    • listen into the medium if other stations forward the packet
    • Request for ACK
  • If a station encounters problems \(\Rightarrow\) inform the sender

• Modification of DSR

  • Nodes could sense the medium to learn about the topology
  • Restriction of flooding \(\Rightarrow\) defining a maximum “range” of the request messages (IP’s TTL)
  • Caching
    • speedup
    • reduce flooding

  \(\Rightarrow\) but reply storms \(\Rightarrow\) use random delays

• Advantages

  • No periodic updates \(\Rightarrow\) low overhead
  • caching \(\Rightarrow\) fast
  • several redundant paths

• Disadvantages

  • high delay
  • Large header information
  • Flooding of route request
  • need to avoid collisions between RREQ packets
  • may pollut other caches

Ad-hoc On-demanding Distance Vector (AODV)

• popular
• assumes symmetric links
  • receive a RREQ \(\Rightarrow\) send RREP traveling along the reverse path (from RREQ)
• Main difference to DSR:
  • no source routing \(\Rightarrow\) routing tables
    • smaller headers
    • not active for a time \(\Rightarrow\) deleting the entry
    • hello messages are sent periodically
• Sequence numbers are added
  • avoid loops

Proactive

• Low latency
• high overhead

Optimized Link State Routing (OLSR)

• Link State Routing: knowledge about local link costs is broadcasted
• Optimized: reduce flooding by broadcasting only to a reduced number of nodes
  • only forwarded by its multipoint relays
  • Each node selects a minimum dominating set of multipoint relays
• Each node transmits its neighbor list in periodic beacons

link state protocol + topology control

Destination Sequence Distance Vector (DSDV)

• manages a distance table
• exchanged on changes
• Each node assigns a sequence number
  • correct order
  • avoid loops and inconsistencies
• slow down of changes
  • Delay of an update if the path probably is not stable (based on the stored time)

---

Multipath routing

• enhancement: using different paths simultaneously
• Increase fault tolerance
• Higher throughput
• Idea: don’t discard duplicates of RREQs \(\Rightarrow\) calculate disjoint paths

802.11s Routing

• WLAN Mesh Network
• Changes:
  • TTL to avoid loops
  • Sequence number: flooding
  • New frame types e.g. RTX/CTX (ready/clear to switch)
• Algorithm: Hybrid Wireless Mesh Protocol
  • Tree-based DSDV
    • If root portal is presented
      \(\Rightarrow\) maintain a distance vector routing tree
  • Radio Metric AODV (RM-AODV)
    • Identify best-metric path with arbitrary path matrixes
    • Aggregate multiple path requests in one message
    • No route caching
    • Allows for periodic path maintenance and proactive maintenance of routes to popular destinations

No optimized routing algorithm known for all situations