.png){kind=icon}
.png){kind=icon}
Return
Optimal oblivious path selection on the mesh
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2008.23.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In the oblivious path selection problem, each packet in the network independently chooses a path, which is an important property if the routing algorithm is to be independent of the traffic distribution. The quality of the paths is determined by the congestion, C, the maximum number of paths crossing an edge, and the dilation, D, the maximum path length. So far, the oblivious algorithms studied in the literature have focused on minimizing the congestion while ignoring the dilation. An open problem is to give algorithms for networks in which C and D can be controlled simultaneously. Here, we solve this problem for the d-dimensional mesh. We present an oblivious algorithm for which C and D are both within O(d(2)) of the optimal. The algorithm uses randomization and we show that the number of random bits required per packet is within O(d) of the minimum number of random bits required by any algorithm that obtains the same congestion. For a fixed d, our algorithm is asymptotically optimal.
Keywords:
oblivious routing
path stretch
network congestion
mesh topology
algorithm randomization
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K