Publication
Theoretical Computer Science
Paper

The generalized packet routing problem

View publication

Abstract

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. © 1987.

Date

01 Jan 1987

Publication

Theoretical Computer Science

Authors

Topics

Share