Notes on the "Starvation in End-to-End Congestion Control" paper.

One question to the impossibility theorem is whether "oracular"
knowledge of MinRTT would make a difference.

Let's assume for simplicity that we're on a network where all packets
must be of the same length L. Define MinRTT as the minimum RTT that a
sender could see if it had a way to mark a packet as "priority" and
make it skip any queue. (This is sometimes how, I think, textbook
discussions of Vegas talk about discovering the MinRTT.) Give all
senders oracular knowledge of MinRTT. On an ideal path, MinRTT = Rm +
L / C. On a path with jitter, MinRTT = Rm + L / C + {minimum
non-congestive delay}.

The trick here, and maybe this is where the authors' thinking will be
different, is that an evil network can't decide to non-congestively
delay *every packet* by the same amount and still exclude that from
the MinRTT value that it (oracularly) informs the flow about. I'm not
claiming this is the only way to define it, but there's at least some
"gut sense" where this seems like the right way to define MinRTT -- it
really is the min RTT.

Given that, here's my CCA:

  1. Send one packetpair. On an ideal path, the first packet will be
  acked after MinRTT, and the second after (MinRTT + L / C). Call this
  second value RTT2.

  2. Wait for the second ACK, then compute C' ← L / (RTT2 -
  MinRTT). On an ideal path, C' = C.

  3. Send a packetpair, and then after waiting (L / C') seconds, send
  an infinite stream of packets every (L / C') seconds. On an ideal
  path, the first packet will be acked after exactly MinRTT, and every
  subsequent packet exactly RTT2 after it was sent. The number of
  packets outstanding will oscillate around RTT2 / (L/C').

  4. If any violation of the "ideal path" measurements is observed,
  the CCA switches to a "silly" cwnd=10 mode.

This is a 1-efficient delay-convergent scheme with δmax = 0, and dmax
= dmin = Rm + 2 L / C.

For Theorem 1, let's pick Rm = 0, s = 10, D = 1 μs. Also L = 10 kbit.

Step 1: Choose C1, C2 s.t. C2 >= 10 C1 and dmax1=(Rm + 2 L / C1) is
within epsilon of dmax2=(Rm + 2 L / C2). (With epsilon = (D - 2δmax)/2
= D/2 = 500 ns, per the last step of the proof.)

Then C1 can be 40 Gbps (leading to dmax=dmin=500 ns) and C2 = 400 Gbps
(leading to dmax=dmin=50 ns). MinRTT for the ideal path with rate C1
(i.e., L/C1) is 250 ns, and MinRTT for C2 is 25 ns.

Step 2: The scheme is 100%-efficient, so this follows trivially.

Step 3: Set C=C1+C2=440 Gbps and Rm = 0. The question here is, how do
you persuade one sender to send at 40 Gbps when it has oracular
knowledge of the path's MinRTT, without it observing a violation of
"ideal path" behavior? I couldn't find a way to do this if MinRTT is
defined as above. The closest I could think of was to impose a +225 ns
non-congestive delay on every packet from flow#1, but if this is truly
the minimum delay, then that flow's MinRTT would be 248 ns and the two
senders would still send at the same rate as each other (this is just
like increasing Rm for that flow). By contrast, if you want to keep
MinRTT = Rm + L/C, at least one future packet would have to be
zero-delayed by non-congestive jitter, which (I think) would be
observed as a violation of ideal path behavior.

(And if the bottleneck parameter being shared oracularly is not MinRTT
but "queue occupancy," does the whole problem go away in a much easier
way?)