Beyond Jain's Fairness Index: Setting the Bar For The Deployment of Congestion Control Algorithms

https://www.cs.cmu.edu/~rware/assets/pdf/ware-hotnets19.pdf

• Key idea: deploy new congestion control algorithms on the Internet

• Deployment threshold: inter-CCA

  • What happens when a new CCA is deployed on a network with flows using some legacy CCA. Is the new CCA impact on the status quo acceptable?

• Past effort: "fairness", "friendliness"

  • Fair: if it maximizes every users utility function given limited link capacity

    • End host CCA, with users as flows, aim to maximize utility per-flow by ensuring every flow sharing the same bottleneck link gets equal bandwidth

    • Looking at the throughput ratio between competing CCAs or by computing Jain's Fairness Index (JFI)

      • [1: perfectly meeting expected fair allocation; 0: unfair]

      • Does not account for the demand of each job: amount of resources a flow uses when operating in absence of contention

      • Thus look at Max-min fairness

    • Problem:

      • Ideal-Driven Goalposting: impractically high requirements (Cubic is not even fair to itself!)

      • Throughput-Centricity: ignore other important figures of merit for good performance, such as latency, flow completion time, or loss rate.

      • Assumption of balance: fairness metric cannot tell whether the outcome is biased for or against the status quo.

        • I.e. Jain's Fairness Index: equal score to --> "takes" and "leaves" larger share

        • status quo: whether or not the new algorithm damages the performance of existing traffic

  • Mimicry: new algorithms replicate properties of TCP-Reno (e.g., driving throughput as a function of the loss rate) in order to be 'friendly' to legacy, Reno-derived TCPs

    • Binds new algorithms to repeating the often undesirable idiosyncrasies of Reno

• Now: advocate for new approach --> limiting harm caused by the new algorithm on the status quo

  • More practical, future proof, and handles a wider range of quality metrics

Limitation of fairness

• Assumption of Balance: values the performance outcome of both the new CCA and the existing, deployed CCA

• Beta: most users use

• Alpha: brand new algoithm

• It should be perfectly acceptable to deploy alpha if alpha is the one receiving unfair treatment - no users other than user A, who chose to use alpha, would be impacted negatively

Limitation of Mimicry:

• Two mimicry based approaches are

  • TCP-Friendly Rate Control (TFRC)

    • 
    • p: the link loss rate

    • describes TCP Reno's average sending rate over time

  • RTT-biased Allocation

    • grant more throughput to connections with low RTTs than to hose with higher RTTs

• Binds new algorithms to replicate the often undesirable idiosyncrasies of the deployed CCA

  • TFRC limit new CCAs to achieve high throughput

  • RTT-based: RTT-based algorithm might be better?

Harm

• 1: maximally harmful, 0: harmless

• x = demand

• y = performance after introduction of a competitor connection

• Metric "more is better", i.e. throughput, QoE --> harm =
• Metric "less is better", i.e. latency, flow completion time --> harm =
• Harm is

  • Multi-metric

  • Demand-aware

  • Status-quo biased

  • Practical

  • Future-proof

• If the amount of harm caused by flows using a new algorithm α on flows using an algorithm β is within a bound derived from how much harm β flows cause other β flows, we can consider α deployable alongside β.

• Formulation:

  • Worse case bounded harm might have some problems: falling to the lowest common denominator (too loose)

    • 
  • Equivalent bounded harm: focus on a pair of workload w and w* in a legacy network where all services using beta. We want to switch the service with workload w* to use alpha. With equivalent bounded harm, alpha would be acceptable iff (alpha, w*) does no more harm to (beta, w) than (beta, w*) would

    • 
    • Too strict to serve as a threshold

  • Symmetric bounded harm

    • 
    • 'do unto other flows as you would have other flows do to you'