DART: Scalable Ad hoc

Routing
DART: Dynamic Address RouTing

Michalis Faloutsos

Joint work with:

Jakob Eriksson
Srikanth Krishnamurthy

M. Faloutsos 1
The Future of Ad Hoc Networks
Meganode ad hoc networking
• Pockets of wireless connectivity
• Consumer owned networks
• Large scale sensor networks
Commercial interest: Starbucks, cell phone companies
Interoperate and exploit wires where available
Plug-n-play operation, zero-configuration.

M. Faloutsos 2
 Why on Earth...?
Overthrowing governments? Who knew what Internet
would become?
Rural networks DIY networking

Theater-wide military networks

Developing countries
Civil disobedience
Networked society
Protecting civil liberties
Ubiquitous and free connectivity?
Internet 2.0?
Consumer owned
Free speech
networking
Circumventing copyrights?
M. Faloutsos 3
Because we can!
Question: Are We Ready For This?
Current Ad Hoc networks do not scale!
• Only to a few hundred nodes!
• Reactive (AODV/DSR): Routing relies on flooding!
• Proactive (DSDV): Keeping track of all nodes: O(N)
Even wireline networks have problems:
• Internet was not designed for mobility!

M. Faloutsos 4
DART Could Be It!

Our approach replaces node address with two

numbers:
• Node identifier - static.
• Routing address - dynamic.
Address indicates current network location
Distributed lookup table maps identifier to
current routing address.

M. Faloutsos 5
DART: a Novel Networking Approach

application application
(P2P networking, Chord, Pastry etc)
transport transport

network network
(DART)
link link

physical physical

The basic idea: separate node identity from address

Address indicates location in the network topology
Not an overlay: an alternative routing layer

Paper appeared at IPTPS 2003 Poster at ICNP 2003

Different name there: PeerNet Paper to appear at INFOCOM 2004

M. Faloutsos 6
Roadmap
DART
• Address allocation
• Routing
• Node Lookup
Simulation Results
Related work
Conclusion

M. Faloutsos 7
 The Status Quo: Proactive Routing
10.48.11.x
10.48.x.x Proactive routing: do
routing before you need it
In Internet: scaling thru
10.x.x.x address aggregation
10.48.2.x
With mobility: you can’t
aggregate addresses
Keep state per node O(N),
10.100.x.x and updates for all

M. Faloutsos 8
The Status Quo: Reactive

Reactive routing: search when you need a path

Do nothing ahead of time
Route discovery: flood the whole network
Optimizations can’t help:Incremental flooding, caching of routes
M. Faloutsos 9
DART: The Overview

Basic idea: permanent nodeID =/= transient address

The address reflects network location
It is a proactive routing scheme, distance vector
Consequences:
• Routing is simplified: address tells me where you are
• Nodes with similar addresses are “near” each other
Challenges:
• Address allocation: When I move, change the address
• ID to Address mapping: Given an ID, find the address

M. Faloutsos 10
Overview: How DART Works

A new node finds a legitimate address:

• Through overhearing periodic routing updates.
If the node moves, it gets a new address.
Nodes exchange routing tables periodically
DART provides lookup: (nodeID, address)
• Not similar to typical Distr. Hash Tables!
Each node registers and updates its entry

M. Faloutsos 11
Address Space as Binary Tree

Prefix Tree

Addresses as leaves in a virtual binary tree

Prefix Tree: a prefix: 00x, 0xx etc
Prefix Subgraph: subgraph induced by prefix
M. Faloutsos 12
DART Address Invariant

All nodes within any given subtree are able

to communicate using only nodes in that
subtree.

M. Faloutsos 13
Managing Dynamic Addresses

Maintain a unique address for every node.

Ensure that all prefix subgraphs are connected
(Address Invariant)
Minimize communication overhead
Require no centralized sources infrastructure.
Minimize required address size (in bits)
• Keep prefixes small

M. Faloutsos 14
Basic Operation

Joining node picks an address with a prefix

common with one of its neighbors.
The routing table is consulted to ensure that the
address invariant is met
Efficient use of address space: shorter prefixes
Maximize connectivity within prefix graph
• Robustness, reduction of overhead

M. Faloutsos 15
Address Allocation Example

When a node joins, it picks an address

that shares a prefix one of its neighbors.

M. Faloutsos 16
Several Subtleties Exist
When nodes move, who is in charge
• Left most node in address tree
• Id of this node “characterizes” subtree or network
Should we try to balance the tree proactively?
• We tried, made things complicated
• Per-need balancing seems to work well
Merging of networks
• Network with “lowest” id wins
Clever assignment of ids to “stable” static nodes will help
things

M. Faloutsos 17
Routing with DART

M. Faloutsos 18
Routing is simplified

If you know the address, life is sweet

Proactive operation
Distance vector style
Nodes keep track of prefixes
• Best hop neighbor per prefix
Routing table has O(logN) entries!
• See next slide

M. Faloutsos 19
How Routing Works in DART

Scalability through information abstraction

Check destination address one bit a time
Route packet to the appropriate prefix subtree
•Routing state: O(log N) for a well balanced tree

M. Faloutsos 20
An example

Routing table of node with address 100

• 0xx : node at 011
• 11x: null
• 101: node at 101
Compare packet address with each row and forwarded
accordingly
M. Faloutsos 21
Node Look Up

What if we don’t know the address?

M. Faloutsos 22
 Node Lookup Table
Maps node identity -> current routing address.
Uses existing routing layer state only.
Upon connection establishment, current routing
address of destination is looked up in table.
Hierarchy of tables, local -> global, ensures
scalability.

M. Faloutsos 23
 Look Up Preliminaries
Id space address space
Node is associated with
three values
A • Id of node, say A
Hash(A)
• Current address of node
addr(A)
• Hashed address of node A
Hash(A)

M. Faloutsos 24
How The Look-Up Works

Node with Address Hash(A)

ID: B responsible for node with ID A
ID: - Node(A) updates his entry
Addr: Hash(A) • To whoever is at Hash(A)
Look up = routing to Hash(A)
For B to talk to node id A
ID: A • Compute Hash(A)
Addr: X
• Query node at Hash(A)
Hash(A): ID space -> Address space

M. Faloutsos 25
Subtle Issues of Look Up

What if no node has address Hash(A)?

• the node whose address is closer to this address is
responsible for the mapping
The system is push based:
• Each node wants to keep its mapping accurate
• Trade off: freq of update: accuracy vs overhead
Many ideas for improving accuracy:
• Add locality: nodes far away need to have the
significant bits right
• Nodes can cache information

M. Faloutsos 26
Other Characteristics of DART

Efficient scalable support for multicasting and

anycasting
• Exploit the virtual address tree to “establish” a
multicast tree
Loop-free routing
• Efficient loop-avoidance (log N bits per entry)

M. Faloutsos 27
Performance Evaluation

Scalability needs REALLY large simulations

N nodes : 10<N<4000:
• uniformly distributed, node density above 6.
Mobility: random way point model:
• Move - pause - pick new destination - move, moving
in straight lines

M. Faloutsos 28
Simulations

Performed using two simulators:

• Home-grown for speed and scalability.
• ns-2 for comparisons and accuracy.
Wireless nodes, with omnidirectional
antennae.

M. Faloutsos 29
 Routing Table Size Scales
Superbly!
Simulation Results log(N) 2*log(N)

30
Routing Table
2 log N
Routing Table Size (entries)

20

log N
10

0
10 100 1000 10000
Network Size (nodes)
Network Size Yes, 10,000

Extremely small average routing table size < 2*log N.

About 15 routing entries for 4000 nodes!

M. Faloutsos 30
Does DART Increase Path
Lengths?
Return Trip Long Direction Short Direction

0.6

0.5
Path Stretch (%)

0.4

0.3

0.2

0.1

0
125 250 375 500 625 750 875 1000
Network Size (nodes)

The average path stretch is LOW, 30-35%.

Recall that 25% stretch is common in Internet

M. Faloutsos 31
Simulating Large Networks

Ns-2 doesn’t scale to large wireless simulations.

Simulated 400-node networks.
Vary Connection Establishment Frequency: CEF
Arguably, CEF increases in larger networks.
Also, CEF depends on traffic patterns.

M. Faloutsos 32
Overhead vs. CEF
DART AODV DSR

3500000

3000000 AODV
Overhead (packets)

2500000

2000000
DSR
1500000

1000000

500000
DART
0
0.1 1 10 100
Connection Establishment Frequency (conn/s)

DART overhead is not significantly affected by CEF.

Reactive protocols suffer when CEF increases.

M. Faloutsos 33
Throughput vs. CEF
DART AODV DSR

8000

7000

6000
Throughput (packet)

5000

4000

3000

2000

1000

0
0.1 1 10 100
Connection Establishment Frequency (conn/s)

DART outperforms AODV/DSR when connection

establishment frequency > 3.
CEF = 3 means one connection/node every 2 mins.
M. Faloutsos 34
Related Work

Hierarchical routing (Kleinrock, Kamoun ‘77)

Clustering based routing: Landmark, LANMAR,
Clusterhead, Hierarchical State Routing, MMWN, etc.
Georouting: LAR, DREAM, Grid, etc.
Distributed Hashtables: Chord, Plaxton routing (overlays)
Routing in unstable networks, K. Fall, Intel, sigcomm’03
Regions as a new paradigm, Sollins, MIT, FDNA’03
FARA from ISI/MIT, Clark, Braden,Falk,Pingali,Faber
Safari from Rice, Johnson, Riedi et al
Virtual Ring Routing, Caesar et al Sigcomm 06
M. Faloutsos 35
Conclusions

DART is a scalable alternative to current ad hoc

routing approaches.
Time to re-evaluate our network architecture
• Future networks: beyond the Internet
Our approach: a new network layer
• Address =/= identity
• Proactive routing
Simulations of DART are very promising.

M. Faloutsos 36
Future Work

Improve on all aspects of the protocol.

Port simulation code to Linux kernel
• For real-world testing with Linksys basestations
Add security and policy considerations.

M. Faloutsos 37
My Areas of Research
Data Mining the Internet (Karagiannis, Siganos)
• Topology: models and patterns [ToN 03] [Netw/ing05]
• Traffic: model and predict behavior [GI 01] [Infocom 04]
• BLINC: traffic classification in the dark: [IMC 04] [SIGCOMM 05]
Modeling and Improving BGP (G. Siganos, Y. He)
• NEMECIS: safeguarding BGP graph[Infocom 04] [GI 01]
DART: A radical network layer for ad hoc [IPTPS 03]
[Infocom 04] [TON 06]
Ad hoc network protocols (Law)
• Multicasting and power efficient broadcast [ICNP 03] [Netw/ing05]
Modeling mobility and cellular networks (Jobin) [Infocom 04]
Cooperative Diversity (Jakllari) work in progress
M. Faloutsos 38
 Late Breaking News: Poisson Returns
Poisson distributions
appear at the backbone
High speed and large
aggregation of sources
seem to change the
behavior!
[Karagiannis et al Infocom ‘04]

Distr. Of interarrival times of packets

In an OC48 backbone line from CAIDA
M. Faloutsos 39
Thank you

More details than you will ever need:

www.cs.ucr.edu/~michalis

M. Faloutsos 40
NEMECIS: Validating BGP Policy

A tool to analyze and validate BGP policy

Motivation: robust BGP = healthy Internet
Delivers: advice/alert in configuring and
troubleshooting BGP policy and routing
Key idea: use all inputs
• IRR dbases, Routeviews, routing updates
For more: www.cs.ucr.edu/~siganos/nemecis.html
[Siganos et al. Infocom’04]

M. Faloutsos 41
 NEMECIS: Two Loops of Functionality

Configuration Actual BGP Routing

Routing Tables - Routes
Information Updates
Intended Declared Policy (in RPSL-
Policy Database)

Human
Administrator NEMECIS
-Detecting misconfigurations
-Detecting illegitimate routing
Misconfiguration Alert

Illegal routing Alert

Loop 1: Configuration - Loop 2: Routing

M. Faloutsos 42
M. Faloutsos 43
 Some Terminology

Routing address - a fixed length binary string.

Address Prefix, aka Prefix - a sequence of bits taken from the
most significant end of a binary address string.
Prefix Subgraph - The graph induced from the current network
graph by the set of nodes that have a given prefix.
M. Faloutsos 44
The Routing Table

Thanks to the invariant, routing is scalable.

Each node keeps log N routing entries.

M. Faloutsos 45