際際滷

際際滷Share a Scribd company logo

Cowen2006 vrsn1

Download as PPT, PDF
Meenakshi Tripathi
Meenakshi Tripathi

The document presents a compact routing scheme that routes on power law graphs with additive stretch. It breaks the graph into a dense core and fringe. It uses known ultra-compact routing algorithms like Thorup-Zwick to route within trees covering the core and fringe. Node names are topology dependent and routing tables use O(e log2 n) bits. The scheme finds the highest degree node, grows a shortest path tree to define the core, and additional trees to cover the remaining fringe edges.

1 of 15
Download to read offline
Compact Routing on Power Law Graphs with Additive Stretch -Arthur Brady & Lenore Cowen Presented by Meenakshi Tripathi
2bestpowerpointtemplates.com BC Scheme Compact Routing with Additive Stretch on power-law graphs. Breaks graph into a dense core, of diameter d; the rest of the graph is called the fringe. Let e be the number of edges that need to be removed from the fringe to make it into a forest. Theorem. For any unweighted, undirected network, there is a routing scheme that uses O(e log2 n)-bit headers and routing tables, and has additive stretch d. Node names are topology dependent. Guarantees Additive stretch d Routing table sizes O(e log2 n)
BC Scheme find the highest-degree node in the graph (h) grow the shortest path tree rooted at it find the core, which is all nodes located within maximum distance d from the highest degree node (I) grow small number (e) of trees to cover all the edges that do not belong to the main tree and lie outside of the core (F) the larger d, the smaller e use known ultra-compact routing algorithms to route on these trees Constructed using a shortest path tree to route in the core, and e spanning trees in the fringe, and a distance labeling to choose between them. 3
Compact Routing on Trees Given a tree T = (V,E), let TZT table[u] be the local routing table assigned to vertex u & by TZT header[w] be the header assigned to vertex w, by the Thorup-Zwick tree routing scheme on T. Let dT (u, v) represent the length of the unique (u, v)-path in T. By Peleg in tree T, each vertex v of T is assigned an O(log2 n)-bit label lT(v), s.t. given the labels of any two vertices v,w in T, the distance d(v,w) b/w them can be computed exactly 4
Routing Scheme in Tree Let T = (V,E) be any tree with root r. 1.Initially, store a routing table TZT table[u] at each node u & let TZT header[w] be the header of node w by TZ scheme. 2. For each vertex u, add the label lT (u) to TZT table[u] to form TZTtable[u]. 3. For each vertex v, add the label lT(v) to TZT header[v] to form TZTheader[v]. 4. Routing decisions are same as the TZ tree-routing scheme 5
Routing Scheme in Tree Lemma: TZ uses O(log2 n)-bit headers, O(log2 n)- bit routing tables, and allows any vertex u, given the header of any destination v, to compute dT (u, v). dT(u, v) can be computed from lT(u) and lT(v) by Peleg scheme 6
Routing Scheme in Tree Define a set T of trees Ti to be the union of the following two sets: 1. a set of spanning trees {T' = T, T1, . . . , T|E'|} on G, constructed as follows: i < 1. For each edge uv E, Grow a single-source shortest path tree Ti rooted at u which includes uv. Increment i. 2. the connected components of TF , with each assigned an arbitrary root vertex. 7
Routing Scheme in Tree cfroute consists of four parts: 1)a preprocessing step, in which we construct temporary data structures using TZ, 2) a labeling step, in which nodes are assigned Headers 3) a storage step, in which a local routing table is constructed at each node 4) the routing procedure 8
Routing Scheme in Tree 1) Preprocessing : Process each tree Ti T using TZ. Let TZTitable[u]) be the routing table for node u in tree Ti, and let TZTiheader[v]) be the header assigned to node u in tree Ti. 2) Labeling : Assign to each vertex v a list of pairs (i, TZTiheader[v]) (ordered by increasing i), one for every tree Ti which contains v. 3) Storage : The routing table stored at each vertex u consists of a list of pairs (i, TZTitable[u]) (ordered by increasing i), one for every tree Ti which contains u 9
Routing Procedure Given Source vertex u to a destination v, routing using cfroute 1.For each tree Ti containing both u and v, extract lTi (u) from TZ'Titable[u], extract lTi(v) from TZTiheader[v] & compute dTi (u, v) according to the Peleg scheme. 2. Choose some tree Tj such that dTj (u, v) is minimized. 3. Route from u to v in Tj according to TZ. 10
Analysis of the routing procedure If dTF(u, v) > d(u, v) i.e. edge uv P, TF . Two cases exist 1. If u', v' F, then because u'v' TF , u'v' E', so the preprocessing routine of cfroute constructed a single-source shortest path tree Ti spanning G with source u (or v) dTi (u, u')+dTi (u', v) = d(u, u')+d(u', v). 2. Now assume that u' I or v' I (or both) edges u'v' P which are not in TF . P contains at least one vertex in I, so d(u, I) + d(I, v)<=|P| = d(u, v). Hence dT (u, v) <= dT (u, h) +dT (h, v) <= [d(u, I)+ d/2 ]+[ d/2 +d(I, v)] <= d(u, v)+d. 11
Hybrid Scheme Superimpose BC scheme and TZ scheme hence a hybrid scheme concatenate headers for both schemes, and store tables for both schemes at every node. Packet is routed using which results in a shorter path to its destination Better stretch than either the universal TZ scheme or BC scheme Stretch is min{(1, d), (3, 0)} & RT size O(n1/2 log2 n) bits. 12
Results 13
Results 14
15 THANKS

More Related Content

Cowen2006 vrsn1

  • 1. Compact Routing on Power Law Graphs with Additive Stretch -Arthur Brady & Lenore Cowen Presented by Meenakshi Tripathi
  • 2. 2bestpowerpointtemplates.com BC Scheme Compact Routing with Additive Stretch on power-law graphs. Breaks graph into a dense core, of diameter d; the rest of the graph is called the fringe. Let e be the number of edges that need to be removed from the fringe to make it into a forest. Theorem. For any unweighted, undirected network, there is a routing scheme that uses O(e log2 n)-bit headers and routing tables, and has additive stretch d. Node names are topology dependent. Guarantees Additive stretch d Routing table sizes O(e log2 n)
  • 3. BC Scheme find the highest-degree node in the graph (h) grow the shortest path tree rooted at it find the core, which is all nodes located within maximum distance d from the highest degree node (I) grow small number (e) of trees to cover all the edges that do not belong to the main tree and lie outside of the core (F) the larger d, the smaller e use known ultra-compact routing algorithms to route on these trees Constructed using a shortest path tree to route in the core, and e spanning trees in the fringe, and a distance labeling to choose between them. 3
  • 4. Compact Routing on Trees Given a tree T = (V,E), let TZT table[u] be the local routing table assigned to vertex u & by TZT header[w] be the header assigned to vertex w, by the Thorup-Zwick tree routing scheme on T. Let dT (u, v) represent the length of the unique (u, v)-path in T. By Peleg in tree T, each vertex v of T is assigned an O(log2 n)-bit label lT(v), s.t. given the labels of any two vertices v,w in T, the distance d(v,w) b/w them can be computed exactly 4
  • 5. Routing Scheme in Tree Let T = (V,E) be any tree with root r. 1.Initially, store a routing table TZT table[u] at each node u & let TZT header[w] be the header of node w by TZ scheme. 2. For each vertex u, add the label lT (u) to TZT table[u] to form TZTtable[u]. 3. For each vertex v, add the label lT(v) to TZT header[v] to form TZTheader[v]. 4. Routing decisions are same as the TZ tree-routing scheme 5
  • 6. Routing Scheme in Tree Lemma: TZ uses O(log2 n)-bit headers, O(log2 n)- bit routing tables, and allows any vertex u, given the header of any destination v, to compute dT (u, v). dT(u, v) can be computed from lT(u) and lT(v) by Peleg scheme 6
  • 7. Routing Scheme in Tree Define a set T of trees Ti to be the union of the following two sets: 1. a set of spanning trees {T' = T, T1, . . . , T|E'|} on G, constructed as follows: i < 1. For each edge uv E, Grow a single-source shortest path tree Ti rooted at u which includes uv. Increment i. 2. the connected components of TF , with each assigned an arbitrary root vertex. 7
  • 8. Routing Scheme in Tree cfroute consists of four parts: 1)a preprocessing step, in which we construct temporary data structures using TZ, 2) a labeling step, in which nodes are assigned Headers 3) a storage step, in which a local routing table is constructed at each node 4) the routing procedure 8
  • 9. Routing Scheme in Tree 1) Preprocessing : Process each tree Ti T using TZ. Let TZTitable[u]) be the routing table for node u in tree Ti, and let TZTiheader[v]) be the header assigned to node u in tree Ti. 2) Labeling : Assign to each vertex v a list of pairs (i, TZTiheader[v]) (ordered by increasing i), one for every tree Ti which contains v. 3) Storage : The routing table stored at each vertex u consists of a list of pairs (i, TZTitable[u]) (ordered by increasing i), one for every tree Ti which contains u 9
  • 10. Routing Procedure Given Source vertex u to a destination v, routing using cfroute 1.For each tree Ti containing both u and v, extract lTi (u) from TZ'Titable[u], extract lTi(v) from TZTiheader[v] & compute dTi (u, v) according to the Peleg scheme. 2. Choose some tree Tj such that dTj (u, v) is minimized. 3. Route from u to v in Tj according to TZ. 10
  • 11. Analysis of the routing procedure If dTF(u, v) > d(u, v) i.e. edge uv P, TF . Two cases exist 1. If u', v' F, then because u'v' TF , u'v' E', so the preprocessing routine of cfroute constructed a single-source shortest path tree Ti spanning G with source u (or v) dTi (u, u')+dTi (u', v) = d(u, u')+d(u', v). 2. Now assume that u' I or v' I (or both) edges u'v' P which are not in TF . P contains at least one vertex in I, so d(u, I) + d(I, v)<=|P| = d(u, v). Hence dT (u, v) <= dT (u, h) +dT (h, v) <= [d(u, I)+ d/2 ]+[ d/2 +d(I, v)] <= d(u, v)+d. 11
  • 12. Hybrid Scheme Superimpose BC scheme and TZ scheme hence a hybrid scheme concatenate headers for both schemes, and store tables for both schemes at every node. Packet is routed using which results in a shorter path to its destination Better stretch than either the universal TZ scheme or BC scheme Stretch is min{(1, d), (3, 0)} & RT size O(n1/2 log2 n) bits. 12

Editor's Notes

  • #3: Forest is a disjoint union of trees ; undirected graphs all of whose connected components are trees; Internet, both at the router- and AS-levels, has: heavy-tailed degree distributions (power-laws) small average shortest path lengths, as a consequence strong clustering A routing algorithm is compact if (definition): Node address and packet header sizes scale polylogarithmically Routing table sizes scale sublinearly Stretch is a constant (does not grow with the network size at all!)
  • #4: The scheme is the first scheme specialized for scale-free graphs; The algorithms are essentially static Topology pre-processing (pre-computation) costs are not considered ; Not possible for planar graphs (Gavoille, Peleg, x); Estimates on the Inter-AS graph would give a worst-case additive stretch of 1&apos; (and average stretch much smaller). ; Exact distance labeling yield additive stretch compact routing schemes. A distance labeling is an assignment of short (polylog n)-bit strings to vertices so that given the labels of two vertices their exact (or approximate) distance can be inferred. Exact distance labeling schemes are known for graphs with small separators or separators with small diameter. Distributed implementations are possible, but the bounds for the number of messages they need to generate in order to process a topology change are not considered
  • #5: By Peleg in tree Twith uniform edge weights
  • #12: Either d TF (u, v) = d(u, v), or