Welcome to UT-Austin! - University of Texas at Austin

Multi-hop DT A new routing protocol Simon S. Lam The University of Texas at Austin (Based on joint work with Chen Qian) Keynote, IEEE ICNP, October 31, 2012 Delaunay triangulation (DT)? A set of point in 2D Multi-hop DT (Simon S. Lam) 2 A triangulation of S Circumcircle of this triangle is not empty Multi-hop DT (Simon S. Lam) 3 Delaunay triangulation of S

Circumcircle of every triangle is empty Multi-hop DT (Simon S. Lam) 4 Greedy forwarding in a DT always succeeds to find a destination node destination Theorem and proof for nodes in 2D [Bose & Morin 2004] Each node is source identified by its coordinates in 2D

Multi-hop DT (Simon S. Lam) 5 DT in d-dimensional Euclidean space DT definition generalized from 2D 2D d-dimensional triangle simplex empty circumcircle empty circumhypersphere In any dimension, the DT of S is a graph, denoted by DT(S) neighbors in the graph are called DT neighbors

Multi-hop DT (Simon S. Lam) 6 Greedy forwarding in a DT always succeeds to find a node closest to a destination location Theorem and proof for location nodes in a ddimensional Euclidean space, d 2 [Lee & Lam source 2006] Node coordinates may be arbitrary Multi-hop DT (Simon S. Lam) 7

Distributed system model of DT A set S of nodes in a d-dimensional Euclidean space Each node assigns itself coordinates in the space to be used as the nodes identifier u knows v means u knows vs coordinates Each node is a communicating state machine a nodes state is set of nodes it knows protocol messages it sends and receives No need to think about d-dimensional objects Multi-hop DT (Simon

S. Lam) 8 A distributed DT Cu set of nodes u knows DT(Cu ) Nu local DT computed by u neighbors of u in DT(Cu ) The distributed DT is correct iff, for all u S, local info Nu = set of us neighbors in global DT, DT(S) Multi-hop DT (Simon S. Lam)

9 Node u finds nodes and computes its local DT f g i e How does u l j search? h a d When does u k stop?

b c u DT(Cu) Cu={u, a, b, c, d} Nu={a, b, c} Multi-hop DT (Simon S. Lam) 10 Application to Layer 2 routing Layer 2 network represented by an arbitrary graph of nodes and physical links (connectivity graph) Minimal assumptions: graph each is connected

physical link is bidirectional How to make use of distributed DT? Multi-hop DT (Simon S. Lam) 11 Extension - Multi-hop DT Connectivity graph j nodes and physical links i h g b a c

In a multi-hop DT, e d DT graph neighbors can be f a physical link that is not a DT edge 01/26/2020 directly connected multiple hops apart and communicate via a virtual link Multi-hop DT (Simon S. Lam) 12

Each node has a forwarding table Each entry in the j forwarding table is a 4tuple ih g a c a-d, to provide the path a-b-c-d,

for the DT edge b e each node stores a tuple, f e.g., d node b stores directions 01/26/2020 Multi-hop DT (Simon S. Lam) 13 In a multi-hop DT, each node u maintains tuples in its forwarding table F u

as soft state state of node u Cu = set of destination nodes in tuples of Fu Nu = set of neighbors in DT(C node usu)local DT Multi-hop DT (Simon S. Lam) 14 A multi-hop DT is correct iff 1. for all u S, Nu = set of us neighbors in DT(S) (the distributed DT is correct)

2. for every DT edge (u, v), there exists a unique k-hop path between u and v in the forwarding tables of nodes in S 01/26/2020 Multi-hop DT (Simon S. Lam) 15 MDTs 2-step greedy forwarding node u receives a packet with destination greedy stepd 1 ye a physical neighbor v closest to d ? s to v greedy step no 2

yes a DT neighbor w closest to d ? w no node u is closest to d transmit forward to (using a tuple in forwarding table) Multi-hop DT (Simon S. Lam) 16 MDTs 2-step greedy example destination k j

Source c, dest. k At node c, physical i h g b a c neighbor closest to k is b c transmits msg to b e source d f

MSG 01/26/2020 Multi-hop DT (Simon S. Lam) 17 2-step greedy example (cont.) Node b is a local minimum with multi-hop DT neighbor destination j k i h b MSG

a c e source d 01/26/2020 j closest to k node b forwards msg to j by transmitting it to e g node e forwards msg to j by transmitting it to h does not perform greedy step 1 f h transmits msg to j j finds itself closest to k

Multi-hop DT (Simon S. Lam) 18 In a correct multi-hop DT MDTs 2-step greedy forwarding provides guaranteed delivery to a node that is closest to the destination location Theorem and proof [Lam and Qian 2011] We next present a join protocol for nodes to construct a correct multihop DT 01/26/2020 Multi-hop DT (Simon S. Lam) 19 MDT join protocol: initial step Given: a correct j

multi-hop DT of S node a boots up i h g b a c e d f to join S, a needs to find the closest node in S It

must be a neighbor of a in the DT of S{a} Multi-hop DT (Simon S. Lam) 20 2-step greedy in existing DT finds node closest to a a sends JOIN_ req to b j with as location as destination i It is greedily forwarded h JOIN_req

a g JOIN_req b c e d 01/26/2020 f to node c which is closest to a Each node along the path of JOIN_req stores a forwarding

tuple for the path Multi-hop DT (Simon S. Lam) 21 Closest node c found c sends JOIN_ rep to a j along the reverse path i h g NB_req b a c

e JOIN_rep d Node a begins an iterative search f a sends NB_req to c Multi-hop DT (Simon S. Lam) 22 Finding more DT neighbors j c adds a to its set C c i h

g b a c NB_rep Set of as new e d c recomputes DT(C ) c f neighbors in DT(Cc) is Nac = { j, d } c sends NB_rep(N c) a to a

01/26/2020 Multi-hop DT (Simon S. Lam) 23 Iterative search by node u repeat for distributed DT [Lee and Lam 2006] for all x Nunew do node x remove x from Nunew receive NB_req from u send NB_req to x Cx = Cx {u}

receive NB_rep(Nux) compute DT(Cx) ; update Nx Cu = Cu {Nux} compute DT(Cu); update Nu update Nunew new until is empty new Nu Nu Nux = u s neighbors in DT(Cx) send NB_rep (Nux) to u (successfully joined) new neighbors that have not been sent a NB_req Multi-hop DT (Simon S. Lam)

24 Path to a multi-hop DT neighbor Node a has learned j j i h g b a NB_req NB_req c e d

f from node c a sends NB_req a-c path has been established c-j: the existing multi-hop DT is correct; a forwarding path exists between c and j The virtual link a-j is 25 set up Multi-hop DT (Simon S. Lam) 25 Physical-link shortcut j received NB_req and

NB_rep j i h sends NB_rep to a At any intermediate node along the reverse path j-h-e-c-b if a node (h in this g b a c e f d Tuples for a and j in nodes

b, c, and e will time out example) finds that dest. a is a physical neighbor, the msg is transmitted directly to a h updates its tuple for a and j Multi-hop DT (Simon S. Lam) 26 When join protocol terminates the multi-hop DT of S{u} is u} is correct For a single join Theorem and proof [Lam and Qian 2011] Theorem also holds for concurrent joins that are independent A correct multi-hop DT can be

constructed by nodes joining serially Multi-hop DT (Simon S. Lam) 27 Concurrent events Two practical problems 1. 2. At network initialization, all nodes join concurrently to construct a correct multi-hop DT Dynamic topology changes occurring at a high rate (churn) nodes Links MDT solution - Each node runs the iterative

search protocol repeatedly and asynchronously (controlled by a timer) Multi-hop DT (Simon S. Lam) 28 Initialization - Accuracy vs. time concurrent joins of 300 nodes in 3D, ave. msg delay =15 ms Each node has run iterative search 2 or 3 times accuracy=1 correct MDT 10 sec TO Multi-hop DT (Simon S. Lam) 29 Convergence to a correct multi-hop DT

300 nodes in 3D join concurrently, 50 experiments max. no. = 6 Multi-hop DT (Simon S. Lam) 30 Convergence to a correct multi-hop DT 700 nodes in 3D join concurrently, 50 experiments max. no. = 8 Multi-hop DT (Simon S. Lam) 31 Achieving 100% routing success rate is faster 300 nodes in 3D join concurrently, 50 experiments Multi-hop DT (Simon S. Lam)

32 Achieving 100% routing success rate is faster 700 nodes in 3D join concurrently, 50 experiments max. no. = 4 Multi-hop DT (Simon S. Lam) 33 500 simulation experiments 300 - 1500 nodes in 3D and 2D, ran on some difficult graphs Convergence to a correct multihop DT in every experiment Conjecture. The iterative search protocol when run repeatedly by a set of nodes is self-stabilizing. No

proof, but no counter example has been found in simulations What assumptions are needed? Multi-hop DT (Simon S. Lam) 34 Churn - Accuracy vs. time 300 nodes in 3D, churn rate = 20 nodes/second from time 0 to 5 sec, ave. msg delay = 15 ms correct multihop DT Each node has run iterative search 2 or 3 times churn stopped 10 sec TO

Multi-hop DT (Simon S. Lam) 35 Msg cost/node/sec vs. churn rate 300 nodes in 3D, ave. msg delay =15 ms This message cost depends more on TO interval than on churn rate TO interval should be adaptive 10 sec TO per iterative search Multi-hop DT (Simon S. Lam) 36 Comparison of 5 protocols in 2D Routing stretch vs. e

log scale 300 nodes with inaccurate coordinates, static topologies, density = 9.7 only for packets delivered by GPSR Multi-hop DT (Simon S. Lam) 37 Initialization msg cost vs. N log scale

node density = 12 MDT costs do not increase with N Multi-hop DT (Simon S. Lam) 38 Virtual vs. physical coordinates log scale inaccurate physical coordinates VPo D Multi-hop DT (Simon S. Lam)

39 Multi-hop DT - overview Nodes in a d-dimensional Euclidean space Each node assigns itself coordinates in the space any connectivity graph, bidirectional links MDT protocols 2-step greedy forwarding Join protocol each node runs iterative search once Leave and failure protocols for repairing node states after a single leave or failure Maintenance protocol each node runs optimized iterative search periodically to repair node states Network initialization by concurrent Multi-hop DT (Simon S. Lam) 40 joins

MDT protocols performance An efficient and effective search method for nodes to construct and maintain a correct multi-hop DT fast convergence 2-step greedy forwarding provides guaranteed delivery to a node closest to a given location basis for a DHT scalable and highly resilient to dynamic topology changes every node runs the same protocols no special nodes Multi-hop DT (Simon S. Lam) 41 Routing applications in layer 2 Wireless routing for nodes with inaccurate coordinates in 2D or 3D

Lowest routing stretch compared to other geographic routing protocols Wired or wireless routing using virtual coordinates VPoD and GDV provide end-to-end routing cost close to that of shortest path routing Finding a node closest to a location in a virtual space Delaunay DHT highly resilient to churn Multi-hop DT (Simon S. Lam) 42 References

P. Bose and P. Morin. Online routing in triangulations. SIAM Journal on Computing, 2004. D.-Y. Lee and S. S. Lam. Protocol design for dynamic Delaunay triangulation. Technical Report TR-06-48, UTCS, December 2006; an abbreviated version in Proceedings IEEE ICDCS, June 2007. S. S. Lam and C. Qian. Geographic Routing in ddimensional Spaces with Guaranteed Delivery and Low Stretch. In Proceedings of ACM SIGMETRICS, June 2011; revised version to appear in IEEE/ACM Trans. Networking. C. Qian and S. S. Lam. Greedy Distance Vector Routing. In Proceedings of IEEE ICDCS, June 2011. C. Qian and S. S. Lam. ROME: Routing On Metropolitanscale Ethernet. In Proceedings of IEEE ICNP, 2012. Multi-hop DT (Simon S. Lam) 43

The end Multi-hop DT (Simon S. Lam) 44

Recently Viewed Presentations

  • Chapter 7.3

    Chapter 7.3

    The idea behind integration by parts is to break a difficult integral into a more manageable one. To use this formula, choose part of the integrand to represent ? and part to represent ?? ... The acronym LIPET can be...
  • Smarter Balanced Accessibility MITCH AULAKH Overview Where are

    Smarter Balanced Accessibility MITCH AULAKH Overview Where are

    Universal Tools. Universal tools are access features of the assessment that are either provided as digitally-delivered components of the test administration system or separate from it.. Available to all students. Embedded (in the test system) and Non-Embedded (not in the...
  • INTRODUCERE - UTCluj

    INTRODUCERE - UTCluj

    Cele mai răspândite sunt combinaţiile pentru sodiu şi potasiu: silicaţi, halogenuri, azotaţi, sulfaţi şi carbonaţi. Litiul este puţin răspândit, iar rubidiul şi cesiul sunt elemente rare. Combinaţii mai răspândite în natură : sarea gemă (NaCl), salpetru de Chile (NaNO3), salpetru...
  • SecPAL: A security policy language to support grid on demand ...

    SecPAL: A security policy language to support grid on demand ...

    Can't express some customer needs (distributed mgt, fine-gained trusts, delegations, revocation etc) Composition of policies is problematic. Token<->Policy semantic differences exacerbate the situation. Mapping tables often needed for attribute translation or binding to local attributes. Typically support only limited name/attribute...
  • Slice Sampling Radford M. Neal The Annals of

    Slice Sampling Radford M. Neal The Annals of

    Radford M. Neal. The Annals of Statistics (Vol. 31, No. 3, 2003) Introduction. Sampling from a non-standard distribution. Metropolis algorithm is sensitive to choice of proposal distribution. Proposing changes that are too small leads to inefficient random walk.
  • Diapositive 1 - Free

    Diapositive 1 - Free

    Arial Calibri Baskerville Old Face Times New Roman Wingdings 2 Wingdings Thème Office Feuille Microsoft Office Excel 97-2003 Graphique Diapositive 1 Introduction Leading Causes of Years of Life Lived with Disability Functional Outcomes in USA Diapositive 5 Schizophrenia and Bipolar...
  • Describe the different types of muscle contraction. There

    Describe the different types of muscle contraction. There

    Example: lifting barbell in bicep curl Eccentric muscle actions produce force while the muscle is lengthening - it is the resistance of the movement. Example: lowering barbell from bicep curl Isometric muscle actions produce force, but there is no change...
  • Tapping into your leadership skills

    Tapping into your leadership skills

    Definition. Leadership is a process that unifies diverse groups of people to work effectively as a team toward common purpose under varied and often difficult circumstances, through: