______________________
                   |          |          |    | Legend               |
                   |w1        |w2        |wi  |                      |
                   |          |          |    | [_] [_]packet stream |
                   V          V          V    |                      |
     congestion    .          .          .    | [*]    marked packet |
     token bucket| . |      | . |    __|___|  | ___                  |
               __|___|      | . |   |  |:::|  | \ /    policer       |
              |  |:::|    __|___|   |  |:::|  | /_\                  |
              |  +---+   |  +---+   |  +---+  |                      |
 bucket depth |    :     |    :     |    :    | /\     marking meter |
 controls the |    .     |    :     |    .    | \/                   |
    policer  _V_   .     |    :     |    .    |______________________|
         ____\ /__/\___________________________             downstream
        /[*] /_\  \/ [_] |    : [_] |    : [_] \            /->network
 class-/                 |    .     |    .      \          /    /--->
 ifier/T1               _V_   .     |    .       \        /    /
__,--.__________________\ /__/\___________________\______/____/ loss
  `--' T2   [*]  [_] [_]/_\  \/ [_] |    .  [*]   /      \    \-X--->
      \                             |    .       /        \-->
       \Ti                         _V_   :      /          \  loss
        \__________________________\ /__/\_____/            \-X--->
         [_]   [*]  [_] [*] [_]    /_\  \/ [_]

Figure 2: Bulk Congestion Policer Schematic

[conex-policing] explains how the operator or tenant would determine an appropriate allowance.

Optional Per-Flow policing:

A congestion policer could be designed to focus policing on the particular data flow(s) contributing most to the excess congestion-bit-rate. However bulk per-tenant congestion policing is sufficient to protect other tenants, then each tenant can choose per-flow policing if it wants.

FIFO forwarding:

If scheduling by traffic class is used in network buffers (for whatever reason), congestion policing can be used to isolate tenants from each other within each class. However, congestion policing will tend to keep queues short, therefore it is more likely that simple first-in first-out (FIFO) will be sufficient, with no need for any priority scheduling.

ECN marking recommended:

All queues that might become congested should support bulk ECN marking. For any non-ECN-capable flows or packets, the solution enables ECN universally in the outer IP header of an edge-to-edge tunnel. It can use the edge-to-edge tunnel created by one of the network virtualisation overlay approaches, e.g. [9, 10].

In the proposed approach, the network operator deploys capacity as usual—using previous experience to determine a reasonable contention ratio at every tier of the network. Then, the tenant contracts with the operator for the rate at which their congestion policer will allow them to contribute to congestion.

4. Performance Isolation: Intuition

4.1. Performance Isolation: The Problem

Network performance isolation traditionally meant that each user could be sure of a minimum guaranteed bit-rate. Such assurances are useful if traffic from each tenant follows relatively predictable paths and is fairly constant. If traffic demand is more dynamic and unpredictable (both over time and across paths), minimum bit-rate assurances can still be given, but they have to be very small relative to the available capacity, because a large number of users might all want to simulataneously share any one link, even though they rarely all use it at the same time.

This either means the shared capacity has to be greatly overprovided so that the assured level is large enough, or the assured level has to be small. The former is unnecessarily expensive; the latter doesn't really give a sufficiently useful assurance.

Round robin or fair queuing are other forms of isolation that guarantee that each user will get 1/N of the capacity of each link, where N is the number of active users at each link. This is fine if the number of active users (N) sharing a link is fairly predictable. However, if large numbers of tenants do not typically share any one link but at any time they all could (as in a data centre), a 1/N assurance is fairly worthless. Again, given N is typically small but could be very large, either the shared capacity has to be expensively overprovided, or the assured bit-rate has to be worthlessly small. The argument is no different for the weighted forms of these algorithms: WRR & WFQ).

Both these traditional forms of isolation try to give one tenant assured instantaneous bit-rate by constraining the instantaneous bit-rate of everyone else. This approach is flawed except in the special case when the load from every tenant on every link is continuous and fairly constant. The reality is usually very different: sources are on-off and the route taken varies, so that on any one link a source is more often off than on.

• In these more realistic (non-constant) scenarios, the capacity available for any one tenant depends much more on how often everyone else uses a link, not just how much bit-rate everyone else would be entitled to if they did use it.

For instance, if 100 tenants are using a 1Gb/s link for 1% of the time, there is a good chance each will get the full 1Gb/s link capacity. But if just six of those tenants suddenly start using the link 50% of the time, whenever the other 94 tenants need the link, they will typically find 3 of these heavier tenants using it already. If a 1/N approach like round-robin were used, then the light tenants would suddently get 1/4 * 1Gb/s = 250Mb/s on average. Round-robin cannot claim to isolate tenants from each other if they usually get 1Gb/s but sometimes they get 250Mb/s (and only 10Mb/s guaranteed in the worst case when all 100 tenants are active).

In contrast, congestion policing is the key to network performance isolation because it focuses policing only on those tenants that go fast over congested path(s) excessively and persistently over time. This keeps congestion below a design threshold everywhere so that everyone else can go fast. In this way, congestion policing takes account of highly variable loads (varying in time and varying across routes). And, if everyone's load happens to be constant, congestion policing converges on the same outcome as the traditional forms of isolation.

The other flaw in the traditional approaches to isolation, like WRR & WFQ, is that they actually prevent long-running flows from yielding to brief bursts from lighter tenants. A long-running flow can yield to brief flows and still complete nearly as soon as it would have otherwise (the brief flows complete sooner, freeing up the capacity for the longer flow sooner). However, WRR & WFQ prevent flows from even seeing the congestion signals that would allow them to co-ordinate between themselves, because they isolate each tenant completely into separate queues.

In summary, superficially, traditional approaches with separate queues sound good for isolation, but:

1. not when everyone's load is variable, so each tenant has no assurance about how many other queues there will be;
2. and not when each tenant can no longer even see the congestion signals from other tenants, so no-one's control algorithms can determine whether they would benefit most by pushing harder or yielding.

4.2. Why Congestion Policing Works

[conex-policing] explains why congestion policing works using numerical examples from a data centre and schematic traffic plots (in ASCII art). The bullets below provide a summary of that explanation, which builds from the simple case of long-running flows through a single link up to a full meshed network with on-off flows of different sizes and different behaviours:

• Starting with the simple case of long-running flows focused on a single bottleneck link, tenants get weighted shares of the link, much like weighted round robin, but with no mechanism in any of the links. This is because losses (or ECN marks) are random, so if one tenant sends twice as much bit-rate it will suffer twice as many lost bits (or ECN-marked bits). So, at least for constant long-running flows, regulating congestion-bits gives the same outcome as regulating bits;
• In the more realistic case where flows are not all long-running but a mix of short to very long, it is explained that bit-rate is not a sufficient metric for isolating performance; how often a tenant is sending (or not sending) is the significant factor for performance isolation, not whether bit-rate is shared equally whenever a source happens to be sending;
• Although it might seem that data volume would be a good measure of how often a tenant is sending, we then show why it is not. For instance, a tenant can send a large volume of data but hardly affect the performance of others — by being more responsive to congestion. Using congestion-volume (congestion-bit-rate over time) in a policer encourages large data senders to be more responsive (to yield), giving other tenants much higher performance while hardly affecting their own performance. Whereas, using straight volume as an allocation metric provides no distinction between high volume sources that yield and high volume sources that do not yield (the widespread behaviour today);
• We then show that a policer based on the congestion-bit-rate metric works across a network of links treating it as a pool of capacity, whereas other approaches treat each link independently, which is why the proposed approach requires none of the configuration complexity on switches that is involved in other approaches.
• We also show that a congestion policer can be arranged to limit bursts of congestion from sources that focus traffic onto a single link, even where one source may consist of a large aggregate of sources.
• We show that a congestion policer rewards traffic that shifts to less congested paths (e.g. multipath TCP or virtual machine motion). This means congestion policing encourages and ultimately forces end-systems to balance their load over the whole pool of bandwidth. The network can attempt to balance the load, but bulk congestion policing is particularly designed to encourage end-systems to do the job, either at the transport layer with multipath TCP [RFC6356] or at the application layer by moving virtual machines or choosing peer virtual machines in a similar way to BitTorrent.
• We show that congestion policing works on the pool of links, irrespective of whether individual links have significantly different capacities.
• We show that a congestion policer allows a wide variety of responses to congestion (e.g. New Reno TCP, Cubic TCP, Compound TCP, Data Centre TCP and even unresponsive UDP traffic), while still encouraging and enforcing a sufficient response to congestion from all sources taken together.
• Congestion policing can and will enforce a congestion response if a tenant persistently causes excessive congestion. This ensures that each tenant's minimum performance is isolated from the combined effects of everyone else. However, the purpose of congestion policing is not to intervene in everyone's rate control all the time. Rather it is encourage each tenant to avoid being policed — to keep the aggregate of all their flows' responses to congestion within an overall envelope and balanced across the network.

[conex-policing] also includes a section that gives guidance on how to estimate appropriate fill rates and sizes for congestion token buckets.

5. Design

The design involves the following elements, each detailed in the following subsections:

1. Trustworthy Congestion Signals at Ingress
2. Switch/Router Support
3. Congestion Policing
4. Distributed Token Buckets

5.1. Trustworthy Congestion Signals at Ingress

,---------.                                               ,---------.
|Transport|                                               |Transport|
| Sender  |   .                                           |Receiver |
|         |  /|___________________________________________|         |
|     ,-<---------------Congestion-Feedback-Signals--<--------.     |
|     |   |/                                              |   |     |
|     |   |\           Transport Layer Feedback Flow      |   |     |
|     |   | \  ___________________________________________|   |     |
|     |   |  \|                                           |   |     |
|     |   |   '         ,-----------.               .     |   |     |
|     |   |_____________|           |_______________|\    |   |     |
|     |   |    IP Layer |           |  Data Flow      \   |   |     |
|     |   |             |(Congested)|           ,-----.\  |   |     |
|     |   |             |  Network  |--Congestion-Signals--->-'     |
|     |   |             |  Device   |           |     |  \|         |
|     |   |             |           |           |Audit|  /|         |
|     `----------->--(new)-IP-Layer-ConEx-Signals-------->|         |
|         |             |           |           `-----'/  |         |
|         |_____________|           |_______________  /   |         |
|         |             |           |               |/    |         |
`---------'             `-----------'               '     `---------'

                             |         |    
  Legend:                    |c*wi     |wi  
  See previous figure        V         V    
                             .         .    
                             .       | . | deep bucket 
             _ _ _ _ _ _ _ _ _ _ _ _ |___|
            |                .       |:::|
            |_ _ _ _ _ _ _ |___|     |:::|
            |      shallow +---+     +---+  
worse of the|       bucket
 two buckets|               \____   ____/
    triggers|                    \ / both buckets
   policing V                     :  drained by 
           ___                    .  marked packets
___________\ /___________________/ \__________________
   [_] [_] /_\   [_]  [*]   [_]  \ /  [_]  [_]   [_]