Compact Routing Schemes and Applications

Succinct Graph Structures and Their Applications Ulpana Summer 2024 Class 3: Routing Schemes

Compact Routing Schemes A distributed protocol to deliver packets from any node of a network to any other node. ?(?) Forward a message from source to destination through a chain of intermediate nodes ? ? ? Each node makes a decision on the next hop based on the header of the msg and its routing-table

Routing Schemes Preprocessing phase: computes for each vertex ? Label ?(?) (address of ?) Routing table ?(?) ?(?) ? Routing phase, for every vertex ?: Input: Header (? ? ), routing table ?(?) Output: Next-hop (port number of ?) Header: ?(?) ? ? Objective: small-space labels and routing tables small-stretch paths

Routing Schemes: Two Extreme Solutions Label ?(?) = ??(?) Routing table ?(?) Header: ?(?) Destination ?1 ?2 Next-Hop ?1 ?2 ? ?1 ?2?3 ?4 ?? ?3 Tables of linear size

Routing Schemes: Two Extreme Solutions ? Header (u v): [? = ?0,?1, ,? = ?] Headers of linear size Header: [? = ?0,?1, ,? = ?] Goal: Poly-log header size Sublinear routing tables Must resort to approx. distances ?

The Best One Can Hope For* *Under Girth Conjecture Routing Schemes define paths and distances between all pairs Last Class: Erdos girth conjecture implies (?1+1 ?) space for (2? 1) stretch For stretch 2? 1, there must be a vertex ? with ? ? = (?1/?)

History of Routing Schemes Stretch Space Labels ?(1) Total space ?(?1+1/?) ?(?2/3) Peleg, Upfal 89 (unweighted) ?(?) Cowen, 99 3 ?(?1/2) ?(?1/?) Eliam, Gavoille, Peleg 98 5 ?(?2) Awerbuch, Peleg 92 ?(??/?) Thorup-Zwick 01 ?? ? ?(??/?) Thorup-Zwick 01 + Handshaking* ?? ? *sourceand destination agree on ?(1) bits

Outline Routing schemes for trees with space ?(deg logn) Routing schemes for trees with space ?(1) Routing schemes for general graphs with: Space (routing tables): ?(n1/?) Stretch: 4? 3

Interval Routing [Santoro, Khatib 85] DFS numbering Label is a range of DFS numbers ? ? = ??? ? ,??? ? ? : last visited descendant of ? 1 ? Routing table ? ? = { ? ? ? ?(?)} 2 8 7 Example: 3 6 ? ? : 2,6 9 10 11 ? ? : { 1,11 , 3,5 ,[6,6]} 4 5

Interval Routing 1 ? ? = [3,5] ? ? = { 1,11 , 9,9 , 10,10 ,[11,11]} ? 1 = { 2,5 , 7,7 , 8,11 } 2 8 7 ? ? 2 = { 3,5 ,[6,6]} 3 6 ? Each ? ? requires ?(deg ? log n) bits 4 5 9 10 11

Improved Routing Schemes for Trees [TZ01] Labels of ?(log2?) bits Routing tables of ?(log?) bits Tool: Heavy Light Tree Decomposition (Sleator and Tarjan) Recursive partitioning of tree into a collection of vertex-disjoint paths

Heavy-Light Tree Decomposition Define the heavy child of node u to be the (unique) child of largest subtree. The remaining children are light ? Note: for every light-child ? of ? it holds: ? T w |T u |/2 ? An edge (?,?) is light (heavy) if ? is light (heavy)

Heavy-Light Tree Decomposition Thm 1: There exists an ?(?) time algorithm that computes a path ? ? whose removal breaks ? into vertex-disjoint sub-trees ?1, ,? s.t: ?? ? ? 2and ? is connected via an edge to each ?? ? Proof: simply go to heavy-child on each step ? The HL decomposition is given by applying recursivelyThm .1

Heavy-Light Tree Decomposition Observation 1: paths ?? = {?1, ,? } cover all heavy edges Observation 2: any path from root to node ? contains ?(log?) light edges Proof: the path can interacts with ?(log?) path in ??

Improved Routing Scheme for Trees Preprocessing algorithm: DFS numbering Heavy-light decomposition Label ? ? : 1. ?(log ?) light-edges on the path from root to ? 2. ???(?) ? Routing table ? ? : 1.[??? ? ,??? ? ] 2. Parent of ? 3. Heavy child of ?

Improved Routing Scheme for Trees Label ? ? :?(log ?) light-edges on the path to ?+ ???(?) Routing table ? ? : ??? ? ,??? ? ? , parent of ?, heavy child of ? Routing Alg. at node ? (target v): 1. If ? ? ? , forward to parent 2. If ?,? ?(?), forward to ? ? 3. Forward to heavy child ? Label space: ? log2 ? Table space: ?(log ?)

From Trees to General Graphs: Tree Covers Tree Covers: a family of trees T = { ?1, ,? } such that: For every ?,? there is a tree ?? ? containing low-stretch path between them. From routing on general graphs to routing on trees with stretch TZ DO implicitly defines a tree-cover with the following properties: Each vertex belongs to ?(?1/?) trees Every pair of vertices ?,? has a tree ?? such that ????,? (2? 1)??(?,?)

Short Recut of TZ Distance Oracles Preprocessing algorithm: ? = ?0 ?1 ?? 1 where ?? ?????? ?? 1 ,? 1/? Pivot ??? closest vertex to ? in ??, ? ?,? {0, ,? 1} Bunch ??? { ? ?? ??+1 ? ?,? < ?(?,??+1? )} ,? {0, ,? 2} ?? 1? = ?? 1 Store in hash-table distances between ? and every vertex in ? ? = ???(?) Query algorithm: Let ? be min value such that ?? ? ?(?). Last class: ???,?? ? + ???? ? ,? ?? ? ??(?,?)

Bunches A0= A1= A2= p2(v) v p1(v) ??? { ? ?? ??+1 ? ?,? < ?(?,??+1? )} *Slide taken from Uri Zwick presentation 19

Approximate Routing Schemes for General Graphs Labels of ?(? log2?) bits Tables of ?(??1/?log2?) bits Stretch 4? 3 Definition for vertex ?: ?? shortest-path tree rooted at ? Routing scheme for ??: L u,Tw and ?(?,??) for every ?

Approximate Routing Schemes for General Graphs Preprocessing algorithm: Compute the bunches and pivots of TZ oracles. For every node ?:?0? , ,?? 1(?), ?(?) ?? (?) Label ? ? = { L u,T?0? , ,L u,T?? 1? } Routing tables ? ? = ? ???(?,??) ? ?:?? ? ,?(?) Let ? be min value such that ?? ? ?(?) ?

? wants to send a message to ? Using ?(?) and ?(?) computes i = min ??? ?(?) ? = ?? (?) ? Forms an header: ? = (?? ? ,? ? ) ? Claim: For every ? ?(?,?,??), ? ? ? ? ?:?? ? ,?(?) Every intermediate ? compute next-hop based on ?(?,??) and ?(?,??) ?

Approximate Routing Schemes for General Graphs ?(? log2?) bits Label ? ? = { L u,T?0? , ,L u,T?? 1? } Routing ? ? = ? ???(?,??) ?(??1/?log2?) bits ?? (?) Stretch: ???,?? ? + ???? ? ,? ?? ? ??(?,?) ? ? ?

Lemma: If ??? ?(?) then ??? ? ? for every ? ?(?,?,??) Assume ? ? ?,?,??(the other case is solved similarly) Let ? be the largest index s.t ??? ?? ??+1 Note: ??? = ??(?) ? = ??(?) ? ??? ? ? ? ?,??? < ?(?,??+1? ) ? ?,??? = ? ?,? + ? ?,??? < ?(?,??+1? ) ? ? ? ?,??+1? ? ?,? + ?(?,??+1? ) ??? ?(?)