MIT4: 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 sturcture
    \(\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
  • 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 maintainance
    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)

  • Expecte 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 Maintainance

    • 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
  • 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 torence
  • 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 protal is presented
        \(\Rightarrow\) maintain a distance vector routing tree
    • Radio Metric AODV (RM-AODV)
      • Identify best-metric path with arbitrary path matrics
      • Aggregate multiple path requests in one message
      • No route caching
      • Allows for periodic path maintainance and proactive maintainance of routes to popular destinations

No optimized routing algorithm known for all situations

Select a repo