Energy Efficient Adversarial Routing in Shared Channels
share
We investigate routing on multiple access channels when packets are injected continually and the system is subject to an energy cap understood as a bound on the number of stations that can be switched on in a round. Performance of algorithms is assessed in adversarial models of packet injection that determine upper bounds on injection rates and burstiness. The algorithms we develop are distributed and deterministic, and their performance bounds are in the worst-case sense. We consider the impact of using control bits in messages, along with routed packets, on the performance of routing. We show that it is possible to obtain packet latency as low as O(n) when a constant fraction of the stations has to be switched off in each round, and also that it is possible to have polynomial packet latency for energy caps of only 2, without using control bits in messages. We give an algorithm that maintains bounded queues for injection rate 1 and which requires the energy cap of only 3, and show that obtaining the same quality of routing with the energy cap of 2 is impossible.
READ FULL TEXT