Transcript Exploration of Path Space using Sensor Network Geometry

Exploration of Path Space using
Sensor Network Geometry
Ruirui Jiang, Xiaomeng Ban, Mayank Goswami,
Wei Zeng, Jie Gao, Xianfeng David Gu
Stony Brook University
Prob1: Scalable Multipath Routing
• Deliver data using multiple (disjoint) paths
– Improving throughput
– Lower delay
– Improving data security
t
s
• Encode data and send different segments along
different paths
• Q: How to generate multiple paths?
k Node Disjoint Paths
• Centralized solutions
– Flow algorithm, node disjoint paths, O(n3)
• Distributed solutions
– Only exist for 2 node disjoint paths.
– Relaxation: braided multi-paths.
– High discovery costs.
Prob2: Fast Recovery from Failures
• Sudden node or link failure
– Link quality fluctuates.
– Unpredictable inference, e.g., hidden terminal
problem
– 802.15.4 networks interfering with WiFi [MT 08]
– Jamming attacks
• Q: how to quickly generate an alternative
path?
R. Musaloiu-E, A. Terzis, Minimising the effect of WiFi interference in 802.15.4 wireless
sensor networks, International Journal of Sensor Networks, 3(1):43-54, 2008.
Prior Work
• IP fast re-routing schemes
– Avoid loop?
• Path splicing [SIGCOMM 08]
– Perturb edge weights
– Compute multiple shortest path trees for each
root
– Switch to another SPT under in-transit failures
– Storage requirement is too high for sensornet.
Motiwala, Elmore, Feamster, Vempala, Path splicing, SIGCOMM Comput.
Commun,. Rev., 2008
Understanding of the Path Space
• Where are the paths connecting source and
destination?
• How to quickly find them?
• How to minimize storage/computation costs?
• Multipath routing using greedy routing?
– Find an embedding, route to the neighbor closer
to destination.
Our Solution: Using Circular Domains
• Our previous work: deform a network into
circular domain [IPSN’09].
• Greedy routing guarantees delivery.

Circular Domains are not Unique
• Embedding into a circular domain is not unique,
they differ by a Möbius transformation.

8
Main Idea: Use Different Metrics
• Find multiple paths:
– Embed to a circular domain D.
– Apply Mӧbius transformation f on D: f(D)
– Find greedy routing in f(D).
– Goal: find disjoint paths.
• Recover from link failure:
– Apply a Mӧbius transformation f on D: f(D)
– Goal: greedy routing on f(D) does not use the
broken link.
Outline
1. Mӧbius transformation
2. Explain the idea in a continuous domain
– Theoretical guarantee
3. Implementation issues on a discrete network
4. Simulation results
Möbius Transform
• Möbius transform
– Conformal: maps circles to circles
– Four basic elements: translation, dilation, rotation,
inversions.
a, b, c, d are 4 complex
numbers, ad ≠ bc
11
Outline
1. Mӧbius transformation
2. Explain the idea in a continuous domain
– Theoretical guarantee
3. Implementation issues on a discrete network
4. Simulation results
Greedy Paths in Different Circular
Domains
• Generate disjoint paths using different
transformations
t
f1
s
t
s
Greedy Paths in Different Circular
Domains
• Generate disjoint paths using different
transformations
f2
s
t
s
t
Isn’t This Just Routing along Arcs?
• One can greedily route along an arc. [NN, 03]
– But there is no guarantee of delivery!
• Our method follows an arc, which is actually
the greedy route in another circular domain.
– Delivery is always guaranteed.
Nath and Niculescu, Routing on a curve, SIGCOMM Comput. Commun. Rev., 2003.
Networks with Holes
• When a circular arc route hits a hole, it is
diverted along the boundary
– Two paths can converge on the boundary
s
t
Finding Disjoint Paths
• Each hole defines two angle ranges
• Inside each range there can only be one path
• Goal: find a max number of paths.
Finding Disjoint Paths
– Project all intervals on a unit circle
– Order the endpoints angularly.
– Adjacent endpoints define canonical segments.
– Remove canonical segments NOT covered by any
range
Finding Disjoint Paths
• Greedy algorithm:
– For each segment as the starting segment,
– Choose it, move clockwise.
– Choose the first one not in conflict
– Ex: choose 5.
Finding Disjoint Paths
• Greedy algorithm:
– Different starting segments give different solns.
– Take the solution with maximum # segments
• Theorem: GREEDY is optimal.
Outline
1. Mӧbius transformation
2. Explain the idea in a continuous domain
– Theoretical guarantee
3. Implementation issues on a discrete network
4. Simulation results
Preprocessing Into a Circular Domain
• Embed the network into a circular domain
– Follows [IPSN’09]
– Compute a triangulation locally
– Non-triangular faces are “holes”
– Nodes locally compute curvature
– Modify edge lengths iteratively
– When converge, obtain the requested embedding
• Distributed, gossip-style algorithm.
How to compute a Mӧbius
Transformation?
• Uniquely determined by mapping 3 points z1,
z2, z3, to w1, w2, w3, respectively.
• I.e., mapping one circle to another circle
How to compute a Mӧbius
Transformation?
• New metric can be locally determined.
p
t
f1
s
p
t
s
Generate Multiple Paths
• No holes:
– Evenly spread the tangent vectors of the paths at
source and dest.
– Heuristic
– Bounded degree.
• With holes:
– Know: locations & sizes of holes
– Very limited global info
s
t
How to Apply the Mӧbius
Transformation in Routing?
• A packet carries the four parameters a, b, c, d
as a matrix.
• Composition of 2 transformations is simply
matrix multiplication
Recovery from Temporary Link Failure
• We compute a Möbius transformation
– S.t. the broken link is NOT on the greedy path.
– Make big jumps
27
Recovery from Temporary Link Failure
• Map the “live” neighbor p to be on the
straight path
– On-demand recovery of in-transit failures.
– Möbius transform attached to packet.
t
f1
p
s
p
t
s
28
Simulation Results
• Relatively dense network:
– 1K nodes, avg deg ≈ 20.
• Multi-path routing
– Compare with centralized flow algorithm.
– Vary parameter m: # paths we seek.
– Check # disjoint paths we got
– Compare with the OPT.
Multipath Routing Results
Max # disjoint
paths
Simulation Results for Recovery from
Failures
• Regional failure
– Inside a geometric region: prob[failure] = p1.
– Outside a geometric region: prob[failure] = p2.
– p1> p2.
• Compare with
– Greedy routing with geographical coordinates
– Greedy routing in a circular domain
– Recovery with Möbius transformation
– Recovery with random walk.
Simulation Results for Recovery from
Failures
• Circular + Möbius > Circular + RandWalk >
Circular >> Geographical + RandWalk ≈
Geographical
Random walk makes local,
random steps and is likely
trapped inside the failure
region
p1=0.8 p2=0
Simulation Results for Recovery from
Failures
• Success rate: Circular + Möbius > Circular +
RandWalk > Circular
p1 p2
Consistently better
by making big jumps
Circular + Circular +
Möbius RandWalk Circular
Conclusion and Future Work
• Regulating a sensor network shape
– Helps to explore path space with limited global
info
• Open problem: bridging the gap
– Provable results in the continuous space
– Heuristic methods in the discrete network
Questions & Comments?