Distributed, Self-stabilizing Placement of Replicated Resources in Emerging NetworksOverviewResource AllocationRequirementsResource Allocation ModelExample NetworkMultiple Resources?Yes.Notation (1/2)Notation (2/2)Optimizated Coloring (1/2)Optimized Coloring (2/2)Asynchronous Distributed Coloring Protocol (ADC)Local InformationStabilityColor Change Rule (1/2)Color Change Rule (2/2)Slide 18Distance PropagationCBF LagSlide 21Slide 22Slide 23Slide 24Asynchronous Color ChangeMonotonicitySlide 27Slide 28Slide 29Slide 30Livelock / DeadlockSlide 32Node State DiagramSlide 34Slide 35Slide 36Slide 37Convergence (1/3)Convergence (2/3)Convergence (3/3)Slide 41Quality of Approximation (1/3)Quality of Approximation (2/3)Quality of Approximation (3/3)PerformanceConvergence TimeColor Changes / NodeMessages / NodeMax d(x,ci) / doptMax d(x,ci) / dopt CDd(x) / dopt(x)Distributed, Self-stabilizing Placement of Replicated Resources in Emerging NetworksBong-Jun Ko, Dan RubensteinPresented by Jason WaddleOverview1. ProblemResource allocation in a network2. SolutionAsynchronous distributed coloring protocol3. Analysis1. Convergence2. Quality of approximation3. PerformanceResource Allocation•Distribute resources in a network fairly, homogenously – all resource types nearby each node–File replica distribution–Distributed computation–Channel allocation in wireless networksRequirements•Scalable•Dynamic•Asynchronous–Don’t assume coordinated clocks•Symmetric–Every node runs same algorithm, no special roles•Local–Nodes use only local information–Avoid long-distance communicationResource Allocation Model•Network: undirected connected graph G = (V,E) , |V| = n•Edge weights w(e) for e 2 E–Model latency•Colors = {c1, c2, …, ck}–Model resources•Vertex color function C : V ! –Assignment of resources to nodesExample Network105178210Multiple Resources?105178210Yes.105178210000Notation (1/2)•Distance d(x,y) = sum of weights on shortest path from x to y–symmetric•color of node x at time t: Ct(x)•distance to color at time t: dt(x,ci)–dt(x,ci) = minv {d(x,v) | Ct(v) = ci}–dt(x,Ct(x)) = 0–dt(x,ci) = 1 if no node has color ciNotation (2/2)•Distance to closest node of same color at time t: t(x)– t(x) = minv {dt(x,v) | Ct(x) = Ct(v) and v x}Optimizated Coloring (1/2)•Want to assign colors to optimize one of:–Minimize maxx maxi Ct(x) dt(x,ci)•So nobody has it bad–Minimize x i Ct(x) dt(x,ci)•Good on average–Maximize x t(x)•Separate resources of same typeOptimized Coloring (2/2)•These problems are NP-Hard even with global information–so we’ll approximateAsynchronous Distributed Coloring Protocol (ADC)•Decentralized asynchronous protocol•Each node–maintains information about colors of nearby nodes–changes its own color to contribute to optimization–without causing deadlock or livelockLocal Information•Nodes are working with old, possibly faulty information•d’t(x,ci) is the distance to the closest node with color ci that node x knows of•Similarly, ’t(x) is the nearest known node of the same colorStability•Node x is locally stable at time t if d’t(x,ci) · ’t(x) for all 1 · i · k–x perceives that all other colors closer to x than any other node of x’s color•Node x is stable at time t if dt(x,ci) · t(x) for all 1 · i · k–all other colors actually are closer to x than any other node of x’s color•The graph coloring is stable when all nodes are stableColor Change Rule (1/2)•Locally stable nodes don’t change color•a locally unstable node x will try to change to color ci that satisfies d’t(x,ci) ¸ d’t(x,cj) for all 1 · j · k–x changes to furthest color–increases ’t(x), decreases i d’t(x,ci)–does not increase maxi dt(x,ci)Color Change Rule (2/2)xyColor Change Rule (2/2)xyDistance Propagation•Use modified Bellman-Ford, Colored Bellman-Ford (CBF)–maintain distances for closest two nodes of each of the k colors–updates sent to neighbors when local distance estimates change•CBF messages quickly stop after graph becomes stable•Side-benefit: how to route to each color•How does it handle distance increases?CBF Lagxyd’(x,c1) = 5d’(x,c2) = 15CBF Lagxyd’(y,c1) = 5d’(y,c2) = 15CBF Lagxy5CBF Lagxy5CBFCBF Lagxyd’(x,c1) = 1d’(x,c2) = 55Asynchronous Color Change•Need to prevent livelock and deadlock•Need to guarantee progress–want t’(x) > t(x) when x changes color between times t and t’Monotonicity•Can show that t’(x) > t(x) when x changes from c1 to c2 if we have:1. there is a node other than x at distance ’t(x) from x that is color c1 at time t’–ensuring t(x) · ’t(x)2. there is no node of color c2 within distance ’t(x) of x at time t’–ensuring t(x,c2) > ’t(x)–Protocol should provide these guaranteesAsynchronous Color Change•3-way handshake to change color•Four types of messages1. request – x: I want to be color c22. accept – y: x change to c2 is OK3. reject – z: x change to c2 is not OK4. decision – x: I did not change to c2Asynchronous Color Change•When x wants to change from c1 to c2 i.e., when ’t(x) < d’t(x,c2)–x sends a request to all nodes at distance t(x) or less: x’s time disk–contains x, c1, c2, z of color c1–asks one c1 node, z, to stay c1–asks nobody to change to c2Asynchronous Color Change•When y receives request(x,c1,c2,z)•Reject if:–y is color c2–y=z (i.e., x thinks y is color c1) but y is not color c1•Accept otherwise, until y receives decision:–y prohibited from changing to c2–if y = z, y prohibited form changing from c1Asynchronous Color Change•if any node rejects, x aborts color change•if all nodes accept, c changes color•in both cases, x sends a decision message indicating the choiceLivelock / Deadlock•x and y are both color c1, both want to change color•just reject each other? prevent each other from improving: livelock•hold others’ request until they get their own accept/reject? deadlock•cannot just break ties– ’t(x) < d(x,y) < ’t(y)Livelock / Deadlock•Impose a strict ordering on nodes•Keep outstanding requests in three sets:–stalling: requests that don’t conflict–master: conflicting requests with higher priority–slave: conflicting requests less priorityNode State DiagramStalledMovingNode State DiagramStalledMovingrequest(y): if bad, rejectelse accept, y !
View Full Document
Unlocking...