Energy Efficient Adversarial Routing in Shared Channels

We investigate routing in networks modeled as a set of stations sharing a channel. Packets are injected continually into stations. Each packet needs to be delivered to its destination station via the channel, possibly passing through relay stations. A station must be switched on to receive a packet successfully transmitted on the channel. Each station manages its on/off schedule by a programmable mechanism. There is a bound on the number of stations that can be switched on simultaneously, called channel restraint. This system’s component is motivated by constraints on the amount of power available for the system. Packet injection is governed by an adversary restricted by injection rate, which is an upper bound on the average number of packets that can be injected per round, and burstiness, which is a maximum number of packets that can be injected in a round. We present deterministic distributed routing algorithms and assess their worst-case performance. A routing algorithm knows the number of stations and the channel restraint but does not know the adversary. One of the algorithms maintains bounded queues in all stations for the maximum injection rate of 1, subject only to the channel restraint of 3. This restraint is provably optimal: obtaining the same throughput with channel restraint of 2 is impossible. We give universal routing algorithms, subject to the minimum channel restraint of 2, that have latency polynomial in the number of stations n , for each fixed adversary of injection rate less than 1. An algorithm routes directly when each packet makes only one hop from the station into which it was injected straight to its destination. We present an algorithm routing indirectly with O(n) latency, for any fixed injection rate less than \(\frac{1}{2}\) , and another algorithm routing directly with O(n) latency, for any fixed injection rate less than \(\frac{1}{3}\) ; both algorithms with the channel restraint of 2. An algorithm is k -channel-oblivious if at most k stations are switched on in a round, and, for each station, the rounds when it is switched on are determined in advance. We give a k -channel-oblivious algorithm routing indirectly with O(n) packet delay, for adversaries of injection rates less than \(\frac{k-1}{n-1}\) , and show that no k -channel-oblivious algorithm exists that can keep queues bounded against adversaries with injection rates greater than \(\frac{k}{n}\) . We give a k -channel-oblivious algorithm routing directly that has \(O\bigl (\frac{n^2}{k}\bigr)\) latency, for adversaries with \(O\bigl (\frac{k^2}{n^2}\bigr)\) injection rates. We develop a k -channel-oblivious algorithm routing directly that maintains bounded queues for the \(\frac{k(k-1)}{n(n-1)}\) injection rate, and show that no k -channel-oblivious algorithm routing directly can keep queues bounded against adversaries with injection rates greater than \(\frac{k(k-1)}{n(n-1)}\) .