DETERMINISTIC MANY-TO-MANY HOT POTATO ROUTING

We consider algorithms for many-to-many hot potato routing. in hot pot ato (deflection) routing, a packet cannot be buffered, and is therefor e always moving until it reaches its destination. We give optimal and nearly optimal deterministic algorithms for many-to-many packet routin g in commonly occurring networks such as the hypercube, meshes, and to ri of various dimensions and sizes, trees, and hypercubic networks suc h as the butterfly. All these algorithms are analyzed using a charging scheme that may be applicable to other algorithms as well. Moreover, all bounds hold in a dynamic setting in which packets can be injected at arbitrary times.