Oblivious routing with limited buffer capacity

摘要

The problem of oblivious routing in fixed connection networks with a limited amount of space available to buffer packets is studied. We show that for an n processor network with a constant number of connections and a constant number of buffers any deterministic pure source-oblivious strategy realizing all partial permutations requires Ω(n) time. The consequence of this result for well-known networks is discussed.