Resource-Competitive Communication
Valerie Jean King, Jared Saia, Maxwell Young · arXiv (Cornell University) · 2012
Consider the general scenario where Alice wishes to transmit a message m to Bob. These two players share a communication channel; however, there exists an adversary, Carol, who aims to prevent the transmission of m by blocking this channel. There are costs to send, receive or block m on the channel, and we ask: How much do Alice and Bob need to spend relative to the adversary Carol in order to guarantee transmission of m? This problem abstracts many types of conflict in information networks including: jamming attacks in wireless sensor networks (WSNs) and distributed denial-of-service (DDoS) attacks on the Internet, where the costs to Alice, Bob and Carol represent an expenditure of energy or network resources. The problem allows us to quantitatively analyze the economics of information exchange in an adversarial setting and ask: Is communication cheaper than censoring communication? We answer this question in the affirmative. Specifically, in a time-slotted network with constant costs to send, receive and block m in a slot, if Carol spends a total of B slots trying to block m, then both Alice and Bob must be active for only O(B ' 1 + 1) = O(B .62 + 1) slots in expectation to transmit m, where ϕ = (1 + √ 5)/2 is the golden ratio. Surprisingly, this result holds even if (1) B is unknownto either player; (2) Carol knows the algorithms of both players, but not their random bits; and (3) Carol can attack using total knowledge of past actions of both players. In the spirit of competitive analysis, approximation guara ntees, and game-theoretic treatments, our approach represents another notion of relative performance that we call resource competitiveness. This new metric measures the worst-case performance of an algorithm relative to any adversarial strategy and pertains to scenarios where all network devices are resource-constrained. Here, we apply the resource-competitive results above to two concrete problems. First, we consider jamming attacks in WSNs and address the fundamental task of propagating m from a single device to all others in the presence of faults. Second, we examine how to mitigate application-level DDoS attacks in a wired client-server scenario.