Version 18 (modified by 13 years ago) ( diff ) | ,
---|
Lets get rid of HIERARCHY ... Make way for DHT networks !!!
Distributed Compact Routing
- Routes over arbitrary names rather than location-dependent addresses (hierarchy independent)
- Disco: Distributed Compact Routing
- Flexible mobility
- Flexible multi-homing
- Easier management
Why Disco |
For general networks, the common scaling technique is hierarchy: routing is performed over high-level aggregate units until it reaches the destination's unit, at which point routing proceeds at a finer granularity. For example, the Internet routes at the level of IP prefixes to a destination domain, and then over an intra-domain routing protocol to a subnet.
Problem with Hierarchy
- First, it can have arbitrarily high stretch, defined as the ratio of route length to the shortest path length. Simultaneously guaranteeing scalability and low stretch on arbitrary networks is a nontrivial problem which no deployed routing protocols achieve.
- Location dependent addressing complicating mobility, management and multi-homing
SOLUTION
- Scalable, low stretch routing on flat names
Requirements
- Guaranteed Scalability
- Guaranteed Low Stretch
- Flat Names
APPROACHES
- NAME DEPENDENT COMPACT ROUTING
- NAME INDEPENDENT COMPACT ROUTING
NAME INDEPENDENT COMPACT ROUTING Disco consists of :
(i)Name Resolution (ii) Distributed Name database
Distributed database which maps node names to their addresses
The database requires the key properties that
- any necessary query can be accomplished with low stretch,
- the O~(n) per-node state bound is not violated, and
- maintaining the state in the face of network dynamics requires little messaging
Adopt the idea of color-grouping of nodes from , but with sloppy grouping and routing schemes which are more amenable to a distributed setting. Design a random overlay network organized around these groups which can efficiently distribute flat-name routing state
To build state |
- Pick random neighbors in G(t) to build overlay
- Gossip in overlay to send address to n1/2 nodes
To route from s to t |
- Check V(s). If t isn’t there, then...
- w = node in both V(t) and G(t)
- Route to w and from there to t via NDDisco: provable stretch ≤ 7
- Subsequent packets follow NDDisco: stretch ≤ 3
Note:
See TracWiki
for help on using the wiki.