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
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.
- 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
- Scalable, low stretch routing on flat names
- Guaranteed Scalability
- Guaranteed Low Stretch
- Flat Names
(i) Name Dependent Distributed Compact Routing Protocol : NDDisco
(ii)Distributed Name Resolution Module
(iii) Distributed Location Database to achieve name independence
Component 01 : Name Dependent Distributed Compact Routing Protocol (NDDisco)
|
Name Dependent : Assume the source knows the destination's current address, as opposed to just its name. NDDisco is based on a centralized algorithm.
- LANDMARKS
- VICINITY
- ADDRESSING
- ROUTING
- SHORT CUTTING HEURISTICS
- A landmark is a node to which all nodes know shortest paths. Landmarks will allow us to construct end-to-end routes of the form s --> 'l' --> t.
- Landmarsk give us source an approximate way to locate destination 't'.
- Landmarks are selected uniform-randomly by having each node decide locally and independently whether to become a landmark.
- Specically, each node picks a random number p uniform in [0; 1], and decides to become a landmark if p <sqrt(log n)=n.
- Thus, the expected number of landmarks is (n*sqrt((log n)/n))= sqrt(n log n) and by a Chernoff bound, there will be theta(nlog n)(w.h.p)
- Node v flips its landmark status only if n has changed by atleast a factor of 2 since the last flip.
if s and t are close , this will lead to poor approximation
|
- Each node 'v' learns shortest path to every node in its vicinity V(v).
- theta(sqrt(nlogn)) nodes closest to 'v'
These sizes ensure that each node has a landmark within its vicinity w.h.p., which is necessary for the stretch guarantee
|
- The address of node v is the identier of its closest landmark lv, paired with the necessary information to forward along lv--> v.
- Addresses are location-dependent, of course, but they are only used internally by the protocol
- Dynamically updated to reflect topology changes
the problem is that some nodes can be close to many nodes in the network, exploding their cluster size
|
NDDisco avoids this problem by having each node v store its vicinity (as defined above: the ~O(sqrt(n)) nodes closest to v) rather than its cluster. This enforces a bound on the number of routing table entries at each node for any network
- Disco adds routing on flat names on top of NDDisco.
- Disco is comprised of
- NDDisco,
- Name resolution, and
- 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
- Pick random neighbors in G(t) to build overlay
- Gossip in overlay to send address to n1/2 nodes
- 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
CHALLENGES
- How to select landmark nodes ?
- POLICY ?
- Ensure node's landmark is within it's own domain
- Landmark service provided by network service provider
- Routing in reverse direction from lv --->v : limitation on policy ?
- Policy routing can signicantly lengthen paths; routing through the landmark nearest to a destination many not provide a stretch guarantee for general policies, even when the route length is compared to the shortest policy compliant path