A Simple Method for Balancing Network Utilization and Routing Quality for Oblivious Routing
- Yuxi Li, Department of Computing Science, University of Alberta
- Janelle Harms, Department of Computing Science, University of Alberta
- Robert Holte, Department of Computing Science, University of Alberta
Applegate and Cohen [3] design demand oblivious
routing schemes that achieve low oblivious ratio with no or
approximate knowledge of trafc demands. We investigate the
quality of oblivious routing with respect to path dispersion, which
is concerned with the number of paths; and path variation, which
is concerned with how far the paths are from the shortest paths
and the variation of path lengths. The results show the dispersion
and the variation are high in general. We propose a penalty
method to improve the quality of oblivious routing. The penalty
method strikes a good balance between the conicting objectives
of minimizing the oblivious ratio and optimizing the quality of
oblivious routing.
Moreover, we apply the simple penalty method to the problem
of minimizing the maximum link utilization given a trafc matrix.
With the penalty method, we can achieve almost the same
maximum link utilization, and improve the quality of routing
to almost perfect, i.e. one or two paths that are very close to the
shortest paths between each pair of nodes.
Citation
Y. Li,
J. Harms,
R. Holte.
"A Simple Method for Balancing Network Utilization and Routing Quality for Oblivious Routing". ICCCN, pp 71-76, September 1995.
| Keywords: |
balancing, quality, routing |
| Category: |
In Conference |
BibTeX
@incollection{Li+al:ICCCN95,
author = {Yuxi Li and Janelle Harms and Robert Holte},
title = {A Simple Method for Balancing Network Utilization and Routing
Quality for Oblivious Routing},
Pages = {71-76},
booktitle = {},
year = 1995,
}Last Updated: June 04, 2007
Submitted by Staurt H. Johnson 
