Paper Info
Title
Oblivious Routing on d-Dimensional Meshes
Abstract
We give new upper and lower bounds for oblivious permutation routing on d-dimensional meshes (d 1) of side length n. We present O nd 2 log n algorithms for d 2 using queue-size 6. Further we present optimal O nd 2 algorithms using unlimited queue-size. For odd d the presented algorithm is a d-bend algorithm. We further show that for odd d an algorithm which for every packet restrict the bends to the minimal number (at most d 1) needs at least Ω n d 1 2 steps.
Year
Venue
Keywords
2001
SIROCCO
permutation routing,oblivious routing,d-dimensional meshes,upper and lower bounds
Field
DocType
Citations 
Link-state routing protocol,Polygon mesh,Oblivious routing,Dynamic Source Routing,Computer science,Path vector protocol,Destination-Sequenced Distance Vector routing,Computer network,Distance-vector routing protocol
Conference
2
PageRank 
References 
Authors
0.39
14
1
Name
Order
Citations
PageRank
Andre Osterloh1104.49