Oblivious Routing in
Wireless networks
Costas Busch
Rensselaer Polytechnic Institute
Joint work with:
Malik Magdon-Ismail and Jing Xi
1
Length of chosen path
Stretch=
Length of shortest path
stretch 
12
 1 .5
8
u shortest path
v
chosen path
2
source
destination
3
Pick random node
4
Pick random node
5
Pick random node
6
Pick random node
7
Pick random node
8
Pick random node
9
Pick random node
10
11
Problem: Big stretch
Adjacent nodes may follow long paths
12
An Impossibility Result
Stretch and congestion
cannot be minimized simultaneously
in arbitrary graphs
13
Example graph:
Each path has length ( n )
n paths
n nodes
Length 1
Source of
n packets
Destination
of all packets
14
Stretch = 1
Edge congestion = n
n packets in one path
15
Stretch = n
Edge congestion = 1
1 packet per path
16
Contribution
Busch, Magdon-Ismail, Xi [SPAA 2005]:
Oblivious algorithm for special graphs
embedded in the 2-dimensional plane
Constant stretch
Small congestion
stretch  O (1)
Cnode  O (Cnode logn )
*
*
Cedge  O (  Cedge
logn )
degree
17
Basic Idea
source
destination
18
Pick a random intermediate node
19
Construct path through intermediate node
20
Outline of Presentation
Introduction
Network Model
Oblivious Algorithm
Analysis
21
Network G
Surrounding area
A
22
Perpendicular bisector
x,y
space x
point
A
x,y
y
space
point
23
s
 (x , y ) 
x,y
x,y
A
space x
point
y
s
space
point
24
Area wideness:
  min  (x , y )
x ,y A
A
25
Coverage Radius R :
maximum distance from a space point
to the closest node
A
graph node
x
R
space point
26
For all pair of nodes
there exist
,  :
Euclidian distance:
u
distG (u ,v )


u ,v
u ,v
v
A
Shortest path length: distG (u ,v )
distG (u ,v ) 8
  1.6
u ,v
5
27
Consequences of
distG (u ,v )


u ,v
Max Euclidian distance
between adjacent nodes
u ,v 
u
1

edge v
(max transmission radius in wireless networks)
28
Consequences of
distG (u ,v )


u ,v
Min Euclidian Distance
between any pair of
nodes:
u ,v 
u
1
O ( r )2  nodes

v
r
29
Outline of Presentation
Introduction
Network Model
Oblivious Algorithm
Analysis
30
Every pair of nodes is assigned a default path
u
default path
z
v
default path
A
w
Examples: •Shortest paths
31
The algorithm
s
source
t
A
destination
32
Perpendicular bisector
s
t
A
33
Pick random space point y
s
t
A
y
34
Find closest node to point y
s
t
A
R y
w
35
Connect intermediate node
to source and destination
s
default
path
t
w
w
A
default
path
36
Outline of Presentation
Introduction
Network Model
Oblivious Algorithm
Analysis
37
Consider an arbitrary set of packets:
   1,,  N 
Suppose the oblivious algorithm gives paths:
P  p1,, pN 
38
We will show:
stretch  O 1
Cnode  O Cnode  logn 
*
optimal congestion
39
Theorem:
Proof:
stretch  O 1
Consider an arbitrary path
and show that:
p P
stretch ( p )  O 1
40
length ( p ) length (q1 )  length (q2 )
stretch ( p ) 

distG (s ,t )
distG (s ,t )
A
s
default
path 1
q
t
y
p
w
default
path q2
41
length (q1 )  length (q2 )
stretch ( p ) 
distG (s ,t )
when default paths are shortest paths
distG (s ,w )  distG (w ,t )
stretch ( p ) 
distG (s ,t )
we show this is constant
42
distG (s ,w )    s ,w     s , y  R      s ,t  R 
A
s
Default path
(shortest)
Similarly:
t
y
R
w
distG (s ,w )


s ,w
distG (w ,t )     s ,t  R 
43
distG (s ,t )    s ,t
s
A
t
distG (s ,t )


s ,t
44
distG (s ,w )  distG (w ,t ) 2   s ,t  R 
stretch ( p ) 

distG (s ,t )
  s ,t
For
 ,  , R constants:
stretch ( p )  O 1
End of Proof
45
Theorem:
C  O C *  logn 
denotes
Cnode
Cnode
*
46
Descargar

Languages and Finite Automata