Quality of service: token bucket, DiffServ, MPLS and SDN
Quality parameters, the token bucket with proof of the bounds on traffic and delay, service disciplines, IntServ and DiffServ, MPLS label switching, software-defined networks and network slicing.
The Internet treats all packets the same way, but not all services have the same needs: a phone call tolerates some loss but not delays beyond 150 ms, a file transfer the opposite, the control of a remote robot requires small, guaranteed delays. Quality of service (QoS) is the set of techniques for giving different guarantees to different flows. In this lesson we look at the token bucket with the proof of the bound on traffic and on delay, queue service disciplines, the IntServ and DiffServ architectures, MPLS label switching and software-defined networks.
What is guaranteed
The parameters of a flow are bandwidth, end-to-end delay, its variability (jitter) and loss. Propagation delay is fixed; what can be controlled is the delay in queues (lesson on queues). To give guarantees two things must be done: describe the traffic a flow will inject, and serve the queues so as to meet the commitments.
The token bucket
A flow is described with a token bucket with parameters 
and 
: a bucket of capacity fills with tokens at a rate of tokens per second; every byte transmitted consumes a token, and if the bucket is empty one must wait. The flow can thus send bursts of up to bytes, but on average no more than bytes per second.
Theorem. The traffic 
leaving a token bucket in any interval of duration 
satisfies
![\[ A(t) \le b + r\,t \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-2641972172fa7add872ce741ae5478f2_l3.png "Rendered by QuickLaTeX.com")
Proof. At the start of the interval the bucket holds at most tokens. During the interval at most 
arrive. Every byte transmitted consumes a token, so the bytes transmitted cannot exceed the tokens available, 
. ∎
Theorem. If a flow conforming to the bucket 
is served by a link guaranteeing it at least rate 
, the queuing delay does not exceed 
.
Proof. The worst case is a burst of bytes arriving all at once with an empty queue: the last byte must wait for the earlier ones to be transmitted, i.e. . After the burst, data arrives at most at rate 
, more slowly than it is served, so the queue cannot exceed the initial one. ∎
The same bucket, placed at the network edge, serves as a shaper (which delays excess packets) or a policer (which drops them or marks them as less important).
Service disciplines
- FIFO: first come, first served. Simple, but an aggressive flow delays all the others.
- Priority: several queues, and the highest-priority non-empty one is always served. Excellent for voice, but low-priority flows can starve.
- Weighted fair queuing (WFQ) and its efficient approximations such as deficit round robin: each flow has a queue and a weight
, and receives at least the fraction 
of the capacity. This is what makes it possible to guarantee the rate 
of the previous theorem.
Against swelling queues (bufferbloat) active queue management schemes such as CoDel are also used, dropping or marking packets before the queue is full, to signal congestion early to TCP (lesson on TCP).
IntServ and DiffServ
The IntServ architecture reserved resources for every single flow along the whole path: strict guarantees, but every router had to remember millions of flows, and it never worked at scale. DiffServ instead classifies packets at the network edge into a few classes, written in 6 bits of the IP header: for example “expedited forwarding” (EF) for voice, “assured forwarding” (AF) with various levels, “best effort” for the rest. Internal routers treat each class with its own queue and priority, without knowing the flows. This is what operators use today to separate telephony, television and Internet on the same network.
MPLS
In operators’ networks packets are often forwarded not by looking at the IP address but at a short label added at the network entrance: this is MPLS (multiprotocol label switching). Each router looks the label up in a small table, replaces it with the next one and forwards the packet along a label-switched path set up in advance. The advantage is no longer so much speed as control: the operator can route traffic on paths other than the shortest ones to balance load (traffic engineering), set up backup paths that can be activated in 50 ms, and build virtual private networks that separate customers on the same infrastructure.
Software-defined networks
In traditional routers every device decides on its own with routing protocols. Software-defined networks (SDN) separate the control plane, which decides the paths, from the data plane, which forwards packets: a central controller, a program that sees the whole network, installs forwarding rules in the devices’ tables (with protocols such as OpenFlow). The network becomes programmable: its behaviour can be changed with software instead of reconfiguring device by device. Together with network function virtualisation (NFV), which replaces dedicated appliances with programs on ordinary servers, it is the basis of data-centre networks and of the 5G core, where the same physical infrastructure is divided into “slices” (network slicing) with different guarantees for different services.
