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

---

NAME INDEPENDENT COMPACT ROUTING

Disco consists of : (i)Name Resolution

(ii) Distributed Name database

We build a distributed database which maps nodes' names to their addresses. The database requires the key properties that (1) any necessary query can be accomplished with low stretch, (2) the O~(n) per-node state bound is not violated, and (3) maintaining the state in the face of network dynamics requires little messaging. We adopt the idea of \color"-grouping of nodes from [2], but adapted with sloppy grouping and routing schemes which are more amenable to a distributed setting. We then design a random overlay network organized around these groups which can e efficiently distribute at-name routing state

---

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