The generalized packet routing problem (Q580964)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The generalized packet routing problem |
scientific article |
Statements
The generalized packet routing problem (English)
0 references
1987
0 references
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 obtan 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.
0 references
parallel and distributed computation
0 references
expander graphs
0 references
efficient packet routing
0 references
communication networks
0 references
permutation packet routing
0 references
token distribution problem
0 references
load balancing problem in distributed systems
0 references