As described in the paper, during each phase, JPM performs a stable matching driven by the outputs. At the end of each phase cells are transferred from inputs to outputs according to the match. The description in the paper gives room to interpretation of (1) what cells are considered by the inputs in granting the requests, and (2) what cells are actually transferred. Our intended interpretation was the following: In addition, JPM admits two other interpretations:


As it was intended, JPM does not work correctly when (1) there are more cells destined to the same output enqueued at the same input, and when (2) the relative order of these cells in the input preference list is different from their relative order in the output preference list (this is also true for interpretation B). This was pointed out by Balaji Prabhakar. For a detailed counterexample by Balaji Prabhakar and Ashish Goel click here.

Independent work done by Chuang, Goel, McKeown, and Prabhakar includes the results in our paper; their paper is available as CSL-TR-98-758. Subsequently, and motivated by a counterexample given by Balaji Prabhakar (similar to the example we use below) we have arrived at the following change to our algorithm.

Note: Assuming interpretation C the algorithm works. However, the proof, as described in the paper has a gap, as it does not handle the case when a cell is not transferred, and no more preferred cells by either the input or output are transferred. For a complete proof click here.


After the matching is done swap the matched cell in the input preference list with the cell destined to the same output that is the most preferred by that input.

Note: This change does not affect the example, the complexity claims and the main body of the proofs presented in the paper. However, in addition we need to show that this fix indeed enforces the basic assumption on which our proofs are constructed. For the proof click here.


For clarity consider the following example. Assume that input x of a switch with outputs a, b, and c holds the following three cells a.2, b.1, and a.1 (in this order). In the cell notation the letter represents the output to which the cell is destined, while the number represents the order of the cell in the output preference list.

Next assume that during a matching phase outputs a and b request their most preferred cells from input x, i.e., a.1 and b.1, respectively. (Note that while a.1 is the most preferred cell by output a, the cell destined to a that is the most preferred by input x is a.2)

Among outputs a and b the input x will grant the request to the output with the most preferred cell according to the x's preference list. This will be output a because the cell destined to a that is the most preferred by x (i.e., a.2) appears before the cell destined to output b which is the most preferred by x (i.e., b.1).

Once this matching is done cells a.1 and a.2 are swapped and a.1, which is the most preferred cell by output a, is transferred to a. As a result, after the transfer, the preference list of input x will be b.1, a.2 (in this order).


We are very thankful to Balaji Prabhakar and Ashish Goel for pointing out the above problem, as well as for providing the counterexample.
Ion Stoica
Last modified: Sat Aug 8 16:43:36 EDT 1998