The generalized packet routing problem

The problem of efficient packet routing is central to the area of communication networks. The special case of permutation packet routing has been extensively studied in the past. While optimal algorithms for permutation routing exist, they do not ‘scale up’ to give optimal solutions for the general case. Using a novel technique we obtain an optimal algorithm for the general packet routing problem. The core of our solution is an algorithm for a generalized version of the token distribution problem. This result has direct applications to the solution of the load balancing problem in distributed systems.

Authors

• David Peleg
• Eli Upfal

Keywords

• Parallel and distributed computation
• communication
• expander graphs