Skip to main content

ATM and MPLS: the networks behind the classic network calculus examples

· 12 min read
PhD candidate, LyRIDS (ECE) × CEDRIC (Cnam)

Network calculus grew up in the 1990s, when the networks that promised quality of service were ATM and, a little later, IP with IntServ, DiffServ and MPLS. That is why its textbooks speak of cells, leaky buckets, virtual circuits and label-switched paths. This post explains those networks just enough to read the classic examples, and shows that the same ideas reappear in TSN and DetNet.

ATM1990sfixed cellsvirtual circuit (VPI/VCI): set up with call admission control, same path for every cellEnd systemsegments into53-byte cellsUNIGCRA policingATM switchswap VPI/VCIATM switchswap VPI/VCIEnd systemarrival curve enforcedservice curve per hopMPLSfrom 1997labelled packetslabel-switched path (LSP), e.g. set up by RSVP-TE with a bandwidth reservationIP networkIngress LERFEC, push labelLSRswap labelEgress LERpop labelIP networkedge policing: arrival curveper-class service: aggregates
Figure 1. ATM and MPLS have the same structure: a path fixed in advance, traffic checked at the entry, and a label swapped at every hop. Network calculus attaches an arrival curve to the entry and a service curve to each hop.Source: own drawing, after the Wikipedia articles on Asynchronous Transfer Mode and Multiprotocol Label Switching.

1. Why these two networks​

Both networks fix the path before the data flows, check the traffic at the entry, and switch on a short label instead of a full address. Each of those choices maps onto a network calculus object:

Network choiceNetwork calculus object
A traffic contract checked at the entryAn arrival curve, enforced by a policer or a greedy shaper
A fixed path through known switchesA concatenation of service curves
Admission control before the circuit or path is set upA check that the delay and backlog bounds still hold
Classes sharing a queueAggregate multiplexing and residual service

The standard textbook by Le Boudec and Thiran uses the ATM generic cell rate algorithm among its first examples of arrival curves, and its second chapter applies the theory to IntServ and DiffServ [5]. The deterministic networking post summarises IntServ and DiffServ.

2. ATM in brief​

Asynchronous Transfer Mode is a cell-switching standard of the ITU-T and ANSI, designed in the late 1980s for the broadband ISDN. It aimed to carry voice, video and data on one network [1]. Its main features:

  • Fixed cells of 53 bytes: a 5-byte header and a 48-byte payload. Small, equal cells keep queuing delay and delay variation low. At 155 Mbit/s a 1500-byte packet occupies the link for about 77 µs, and on a 1.544 Mbit/s T1 line for about 7.8 ms, far too long for voice to wait behind several of them. The 48-byte payload was a political compromise between the 64 bytes proposed by the United States and the 32 bytes proposed by Europe [1].
  • Connection-oriented. A virtual circuit is set up before any cell is sent. It is either permanent, configured by the operator, or switched, set up by signalling for each call. When a switched circuit is requested, the network performs call admission control: it checks that a route exists with enough resources for the requested traffic [1].
  • Label swapping. Each cell carries a virtual path identifier (VPI) and a virtual channel identifier (VCI). Every switch replaces them with the values for the next link. The values change from hop to hop, but the circuit, and so the path, stays the same for every cell [1].
  • Adaptation layers (AAL1, AAL2, AAL5, …) adapt services such as circuit emulation, variable-rate media and data to the cell stream [1].
ATM cell header at the UNI: 5 bytes, followed by a 48-byte payloadGFC4VPI8 bitsVCI16 bitsPT3HEC8 bitsCLP40 bitsMPLS label stack entry: 4 bytes, one per label, between the layer-2 and IP headersLabel20 bitsTC3TTL8 bitsS32 bits
Figure 2. The two headers, drawn to scale. Blue: the label that identifies the circuit or path at this hop, rewritten at every switch. Orange: the fields that carry a priority or loss class.Source: own drawing from the field lists in the Wikipedia articles on ATM (cell structure) and MPLS (operation).

Service categories​

When a circuit is set up, each switch on it learns the traffic contract of the connection [1]:

CategoryContractTypical use
CBR, constant bit ratePeak cell rate (PCR)Circuit emulation, voice
VBR, variable bit rate (real-time and non-real-time)Sustainable cell rate (SCR), PCR, maximum burst size (MBS)Compressed video, bursty data
ABR, available bit rateA guaranteed minimum rateData that adapts to feedback
UBR, unspecified bit rateNone: whatever capacity remainsBest effort

Most categories also define a cell delay variation tolerance (CDVT). It states how much cells may bunch together after crossing earlier equipment [1].

3. The ATM contract as an arrival curve​

At the user–network interface (UNI), and between networks, ATM polices each circuit against its contract. The reference algorithm is the Generic Cell Rate Algorithm, GCRA(TT, τ\tau), where TT is the nominal spacing between cells and τ\tau the tolerance [1][3].

Two equivalent flowcharts of the generic cell rate algorithm: the virtual scheduling algorithm with a theoretical arrival time, and the continuous-state leaky bucket
Figure 3. The generic cell rate algorithm in its two equivalent forms. The virtual scheduling version keeps a theoretical arrival time (TAT). The continuous-state leaky bucket keeps a bucket level X. A cell that arrives too early (before TAT − τ, or with X above τ) is non-conforming.Source: GCRA.JPG by Graham Fountain, after the figure in ITU-T I.371 Annex A, from the Wikipedia article “Generic cell rate algorithm”, Wikimedia Commons, Public domain.

The virtual scheduling form reads almost like a definition of an arrival curve. A cell is conforming if it does not arrive more than τ\tau before its theoretical time, and each conforming cell pushes the theoretical time TT further. A cell stream is GCRA(TT, τ\tau)-conforming if and only if it has the staircase arrival curve

α(t)=⌈t+τT⌉ cells,t>0,\alpha(t) = \left\lceil \frac{t + \tau}{T} \right\rceil \text{ cells}, \qquad t > 0,

which is upper-bounded by the token bucket γr,b\gamma_{r,b} with r=1/Tr = 1/T cells per second and b=1+τ/Tb = 1 + \tau/T cells [5]. This is the staircase of the arrival curves post, where the tolerance τ\tau plays the role of the jitter JJ.

VBR: two buckets, one concave curve​

A VBR connection is policed by two GCRAs at once, one on the peak rate and one on the sustainable rate [1][3]:

Flowcharts of the dual generic cell rate algorithm testing a cell against both the peak cell rate and the sustainable cell rate
Figure 4. The dual GCRA used for VBR connections. A cell must conform to both a test against the peak cell rate (PCR) and a test against the sustainable cell rate (SCR).Source: Dual LBC.JPG by Graham Fountain, from the Wikipedia article “Generic cell rate algorithm”, Wikimedia Commons, Public domain.
Cells of a VBR connection: a burst of MBS cells spaced 1/PCR apart, then a gap so that the next burst starts MBS/SCR after the first
Figure 5. The worst case allowed by a VBR contract: a burst of MBS cells at the peak rate, 1/PCR apart, then a pause, so that bursts repeat every MBS/SCR.Source: Variable Bit Rate.JPG by Graham Fountain, from the Wikipedia article “Generic cell rate algorithm”, Wikimedia Commons, Public domain.

A stream that passes both tests has the minimum of the two curves as its arrival curve. Write the burst tolerance of the sustainable-rate test as BT=(MBS−1) (1/SCR−1/PCR)BT = (MBS - 1)\,(1/SCR - 1/PCR) and ignore the CDVT. The arrival curve, in cells, is then

α(t)=min⁡(1+PCR⋅t,  1+SCR (t+BT)).\alpha(t) = \min\bigl(1 + PCR \cdot t,\; 1 + SCR\,(t + BT)\bigr).

This concave, two-piece curve has the same shape as the IntServ traffic specification min⁡(M+pt, b+rt)\min(M + p t,\, b + r t) and as the curves used for TSN streams. Only the units changed.

Worked example​

Take a VBR circuit with PCR=100 000PCR = 100\,000 cells/s, SCR=10 000SCR = 10\,000 cells/s and MBS=50MBS = 50 cells. Then BT=49×(10−4−10−5)=4.41BT = 49 \times (10^{-4} - 10^{-5}) = 4.41 ms, so

α(t)=min⁡(1+100 000 t,  45.1+10 000 t) cells.\alpha(t) = \min(1 + 100\,000\,t,\; 45.1 + 10\,000\,t) \text{ cells}.

Suppose each switch guarantees the circuit a rate-latency service with R=20 000R = 20\,000 cells/s (about 8.5 Mbit/s of cells) and T=1T = 1 ms. The two pieces of α\alpha meet at θ=44.1/90 000≈0.49\theta = 44.1 / 90\,000 \approx 0.49 ms. The largest horizontal distance between α\alpha and β\beta lies at that kink, which gives the delay bound

d=T+MR+(b−M)(p−R)(p−r) R=1+0.05+1.96≈3.01 ms,d = T + \frac{M}{R} + \frac{(b - M)(p - R)}{(p - r)\,R} = 1 + 0.05 + 1.96 \approx 3.01 \text{ ms},

with M=1M = 1, b=45.1b = 45.1, p=PCRp = PCR and r=SCRr = SCR. Using only the token bucket would give T+b/R≈3.26T + b/R \approx 3.26 ms, so the peak rate saves a quarter of a millisecond. The backlog bound is the largest vertical distance. It occurs at t=Tt = T: α(1 ms)=55.1\alpha(1\text{ ms}) = 55.1 cells, about 2.9 kB. The fundamental bounds post derives both distances in general.

Cumulative arrival curve A and departure curve D; the horizontal distance between them is the delay and the vertical distance the backlog
Figure 6. The two distances behind every bound. The horizontal distance d between the arrival curve A and the departure curve D is the delay; the vertical distance b is the backlog.Source: Horizontal and vertical deviation.svg by MarcBoyerONERA, from the Wikipedia article “Network calculus”, Wikimedia Commons, CC BY-SA 3.0.

Policing and shaping in practice​

A cell that breaks the contract is either dropped or tagged by setting its cell loss priority (CLP) bit, so that a congested switch drops it first [1]. Dropping single cells wastes capacity, because one lost cell ruins a whole AAL5 packet. Switches therefore use early or partial packet discard to drop whole packets [1]. On the sending side, the network interface shapes the cell stream so that it conforms before it reaches the UNI [1]. In network calculus this is the greedy shaper: shaping a flow to its own arrival curve does not increase its worst-case delay bound.

4. MPLS in brief​

An MPLS cloud: customer routers outside, label edge routers on the border of the cloud, label switch routers inside
Figure 7. An MPLS cloud. Customer routers (outside) connect to label edge routers on the border (red), which push and pop labels. Label switch routers inside the cloud (blue) forward on the label alone.Source: MPLS-cloud.svg by Tule-hog, from the Wikipedia article “Multiprotocol Label Switching”, Wikimedia Commons, CC0.

Multiprotocol Label Switching, standardised by the IETF in RFC 3031, forwards packets on a short label instead of the destination address [2][4]. It grew out of IP switching over ATM and Cisco's tag switching, and the IETF working group was formed in 1997 [2]. MPLS kept what made ATM attractive, connection-oriented paths and traffic engineering, while dropping cells and ATM signalling. Modern links are fast enough that a full 1500-byte packet no longer causes a significant queuing delay: about 1.2 µs at 10 Gbit/s [1][2].

  • The ingress label edge router (LER) assigns each packet to a forwarding equivalence class (FEC) and pushes a label [2].
  • Each label switch router (LSR) looks up the label, swaps it, and forwards the packet [2].
  • The egress LER pops the label and forwards plain IP [2].
  • The sequence of labels forms a label-switched path (LSP), much like a permanent virtual circuit in ATM, but independent of any layer-2 technology [2].
  • Labels are distributed by LDP, or by RSVP-TE when a path with a bandwidth reservation is needed [2].
  • Each label stack entry has a 20-bit label, a 3-bit traffic class (TC) for QoS, a bottom-of-stack bit and a TTL (Figure 2). Labels can be stacked, which is how VPNs and tunnels nest [2].

MPLS is now used mostly for traffic engineering, DiffServ quality of service and VPNs [2].

5. MPLS in network calculus terms​

An LSP is a fixed path. Its end-to-end service is the min-plus convolution of the per-hop service curves. "Pay bursts only once" applies to it directly, as in the concatenation post.

Two servers in sequence: input A enters the first server, its output X enters the second, whose output is D
Figure 8. Two servers in sequence, the elementary picture behind an LSP or an ATM circuit: the output X of the first server is the input of the second.Source: Network Calculus -- Sequence of servers.svg by MarcBoyerONERA, from the Wikipedia article “Network calculus”, Wikimedia Commons, CC BY-SA 4.0.

A TC class is an aggregate. In an MPLS core, packets are queued by traffic class, not by LSP, so a flow shares its queue with every other flow of its class. This is the setting of aggregate multiplexing. It is also where a classic warning comes from. For a network of FIFO aggregates, as in a DiffServ or MPLS core, the known general delay bound holds only if utilisation stays below roughly 1/(h−1)1/(h-1), where hh is the longest path in hops [6]. Per-flow reservation at the edge, as with RSVP-TE, keeps each aggregate within its budget.

DetNet reuses MPLS. One of the two DetNet data planes is MPLS. Labels identify the DetNet flow, and a control word carries the sequence number used for packet replication and elimination [7]. The IETF DetNet post describes the architecture.

6. Then and now​

ATMMPLSTSNDetNet
Unit53-byte cellPacket with a label stackEthernet frameIP or MPLS packet
PathVirtual circuit (VPI/VCI)Label-switched pathStream on a configured pathDetNet flow on an explicit route
Traffic contractPCR, SCR, MBS, CDVTReserved bandwidth (RSVP-TE) or classTraffic specification (token bucket)Traffic specification
Entry checkGCRA policing at the UNIPolicing at the ingress LERPSFPIngress policing and shaping
Admission controlCall admission control (PNNI)Traffic-engineering reservationSRP, RAP or CNCController plane
Network calculus viewStaircase or two-piece arrival curveConcatenation and aggregatesArrival curves, shaper service curvesSame, across L2 and L3 segments

The vocabulary changed, but the structure did not: a contract at the edge, a known path, and a check before admission. This is why the bounds derived for ATM in the 1990s carry over to TSN and DetNet with only a change of units.

References​

  1. Wikipedia, "Asynchronous Transfer Mode." Article
  2. Wikipedia, "Multiprotocol Label Switching." Article
  3. Wikipedia, "Generic cell rate algorithm." Article
  4. E. Rosen, A. Viswanathan, R. Callon, Multiprotocol Label Switching Architecture, RFC 3031, January 2001. RFC Editor
  5. J.-Y. Le Boudec, P. Thiran, Network Calculus: A Theory of Deterministic Queuing Systems for the Internet, LNCS 2050, Springer, 2001, Chapters 1 and 2. Online edition
  6. A. Charny, J.-Y. Le Boudec, "Delay Bounds in a Network with Aggregate Scheduling," Quality of Future Internet Services (QofIS), LNCS 1922, Springer, 2000.
  7. B. Varga, J. Farkas, L. Berger, A. Malis, S. Bryant, J. Korhonen, Deterministic Networking (DetNet) Data Plane: MPLS, RFC 8964, January 2021. RFC Editor