'''Dis'''tributed '''Co'''mpact 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''

 ||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''' ||

----

 ||'''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