Oblivious routing with limited buffer capacity
Danny Kriz̧anc · Journal of Computer and System Sciences · 1991
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.