There were two things which motivated the following short narrative. First, burning the midnight oil
on trying to figure out proofs of the stability of packet switching algorithms with colleagues,
some (i.e. the algorithms -grin-) of which are quite a tough nut to crack.
Second, the simple satisfaction of applying undergraduate
computer science to claim that the general version of the problem that one is studying is
undecidable. Nothing in this short snippet is non obvious, and it is a direct consequence from
undecibility theory.
Q: What research do you do?
A: We try and solve problems which in general are undecidable. (Hide grin)
Jokes apart, here is something which I hope you find interesting...
Background: Packet Switching
A packet switch is a device, which switches packets
from N inputs and sends these packets to N outputs.
We will assume that packets arrive in a unit of time called a time-slot.
Most packet switches are built using a switching fabric called a crossbar. The crossbar
has the property that in any time-slot, at most one packet can be sent from every input and
at most one packet can reach every output, i.e. it can only select a matching [4] of inputs to
outputs. A packet switching algorithm decides which
amongst the many possible matchings should be selected. We call a switching algorithm
stable if it has certain "good" properties. The exact definition of a stable algorithm is
un-important for this discussion; details are in [5,6]. For this
discussion, we can think of a stable algorithm as one, which can transfer the offered
traffic load from the inputs to the outputs over the long term.
For example, there is an algorithm called the maximum weight matching algorithm [5], which is known to be stable. The maximum weight algorithm simply chooses the matching with the
largest weight, where the weight of an edge is the number of packets waiting at an input
i , and destined to an output j ; 1 <= i, j <= N.
Similarly a switching algorithm, which does not select any matching
(i.e. never transfers a packet from inputs to outputs) is not stable.
Switch Stability is Undecidable
The halting problem [1], states that, there can be no algorithm, which can decide for all
programs, whether that program will halt or not i.e.
the halting problem is un-decidable. (The halting problem is related to the more general Rice's theorem
[2] and Gödel's incompleteness theorem [3]). We can directly apply the halting problem to
packet switching.
Packet switching researchers tend to suggest different switching algorithms, and
show (amongst other properties) that such algorithms are stable.
Some algorithms can be easily shown to be stable; while stability is hard to
show for many other algorithms. It is interesting (and obvious) to note
that switch stability is un-decidable, i.e.
Theorem:
There is no procedure, which can decide for every switching algorithm,
whether it is stable or not.
Proof:
(Reductio-Ad-Absurdum)
Suppose that there was a procedure P(A) which takes switching algorithm
A as input, and could decide for all switching algorithms A,
whether A was stable or not. Consider the following switching algorithm A'.
Table: Switching Algorithm A'
If P(A') = not stable, then perform maximum_weight_matching for every timeslot.
If P(A') = stable, then dont perform any matching for every timeslot.
Is switching algorithm A', stable or not?
Case 1: Assume that A' is stable. In the first step of the algorithm,
A' executes the boolean procedure P on itself. So since P(A')= stable, it must be performing no
matching in every timeslot. Clearly then A' is not stable, which leads to a contradiction.
Case 2: Assume that A' is not stable. In the first step of the algorithm, A' executes
the boolean prodecure P on itself. So since P(A')= not stable, it must be performing the
maximum weight matching in every timeslot. Clearly then A' is stable, which again
leads to a contradiction.
Since, we get a contradiction in either case, this means that there can be no procedure P, which
for every switching algorithm A, can deduce whether A is stable or not.
Comments
Of course, the above switching algorithm appears contrived. However it is not hard
to demonstrate other switching algorithms which are not contrived and which
can be proven to be un-decidable, by converting any well known un-decidable
problems from other areas and representing it as part of a packet
switching algorithm.
"Achieving 100% Throughput in an Input-Queued Switch",
N. McKeown, A. Mekkittikul, V. Anantharam, J. Walrand,
IEEE Transactions on Communications, Vol.47, No.8, August 1999,pdf
"The throughput of data switches with and without speedup",
J.G. Dai, B. Prabhakar, Proceedings of the IEEE INFOCOM, 2:556-564,
Tel Aviv, Israel, March 2000, ps
If you notice any mistakes, please send me email at
sundaes@cs.stanford.edu
Last modified: Tue Dec 2nd 23:16:50 PDT 2003