Introduction
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:
- A. (1) Each input considers outputs'
cells that are the most preferred by the input.
(2) A matched input transfers output's
most preferred cell.
In addition, JPM admits two other interpretations:
- B. (1) Same as A.1. (2) A matched input
transfers the most preferred cell belonging to the output, according
to input's preference list.
- C. (1) Each input considers only cells
requested by their outputs, i.e., the most preferred cells by the
outputs. (2) Same as A.2.
Problem
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.
Fix
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.
Example
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).
Acknowledgements
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