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

---

Components of Disco

(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.

Components of NDDisco

• LANDMARKS
• VICINITY
• ADDRESSING
• ROUTING
• SHORT CUTTING HEURISTICS

---

01.LANDMARKS

• 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

---

02.VICINITY

• 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

---

03. ADDRESSING

• 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

---

04.ROUTING

• 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

Design a random overlay network organized around these groups which can efficiently distribute flat-name routing state

Adopt the idea of color-grouping of nodes from , but with sloppy grouping and routing schemes which are more amenable to a distributed setting.

---

SUMMARY

To build state

• Pick random neighbors in G(t) to build overlay
• Gossip in overlay to send address to n^{1/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

---

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