Network Calculus (NC)

Introduction

Network Calculus (NC) appeared in the 90’s as a deterministic tool for the performance analysis of packet networks in a worst case scenario.

Communication networks can carry traffic from a wide variety of applications such as online radios and videoconferences. Each application demands different performance requirements, e.g., maximum end-to-end delay and minimum/maximum transmission rate. This scenario of traffic imposes the determination of performance measures and traffic filtering mechanisms, in order to avoid the monopolization of the network resources by one traffic flow.

Network Calculus: Definition and Main Idea

Network Calculus (NC) can be defined as a set of rules and results that can be used to compute bounds of performance parameters of communication networks. The most common parameters of interest are: end-to-end delay; maximum/minimum transmission rates and buffer usage.

NC is based on the idea that a detailed analysis of traffic flows is not required in order to specify a network performance, if the following conditions are satisfied:

  • Input flows have limited burstness;
  • Some service guarantee is provided.

The above conditions define a minimum system for the NC (Figure 1):

  • A filter to limit (or shape) the input traffic;
  • A network that can offer some service guarantee.
basicNCSystem

Figure 1

These conditions are directly related to the most fundamental concepts of Network Calculus: Regulation Curves and Service Curves.

Regulation Curves

Regulation curves represent filters that delay a given flow in order to limit its burstness.

Consider a function x : R → R+ ∪ {+∞} such that x(t) represents the cumulative amount of data that traverse a given point of a network in the interval (0,t]. Consider also that systems are empty at t = 0. Therefore,

  • x(t) is a non-decreasing function of t;
  • x(t) = 0, ∀t < 0.

Define F = {x: x(t1) ≥ x(t2), if t1t2, and x(t) = 0, ∀t < 0}. Thus x ∈ F.

Given x,σ ∈ F, function σ is a regulation curve of x if, s,t ∈ R with st,

x(t) - x(s) ≤ σ(t-s).

Considering additionally that x(0) = 0, this equation can also be written, as t ∈ R+:

x(t) ≤   inf  {x(s) + σ(t-s)}.
0 ≤ s ≤ t

In general in the NC literature, regulation curves are called “arrival curves” or “departure curves”, depending on if x represents the input flow or the output flow of a network. Here, it is used the term “regulation” to emphasize that both arrival and departure curves have the same meaning of burst limitation.

Regulation Curves: Example

The most common regulation curve in the literature is σ(t) = b + r·t, ∀t ≥ 0 (0, otherwise). “Leaky buckets” or “token buckets” are filters that satisfy this type of σ.

Consider a token bucket with regulation curve σ, input flow u, and output flow x as shown in Figure 2. Function u(t) represents a train of 1000 cells that arrives at the filter at t = 0. To satisfy the regulation curve, the token bucket delays half of the cells as shown in Figure 2.

 if t > 0;
 if t ≤ 0.
 if t > 0;
 if t ≤ 0.
500 + t,
0,
1000,
0,
{
{
σ(t) =
u(t) =
RegulationCurve

Figure 2

Service Curves

Service curves represent the amount of data for which a given network guarantee service.

Given functions x,y ∈ F. We say that β ∈ F is a service curve between x and y, if t ∈ R+, ∃s ∈ R+ such that st and y(t) ≥ x(s) + β(t-s). Case x(0) = 0, this equation can also be written as, t ∈ R+:

y(t) ≥   inf  {x(s) + β(t-s)}.
0 ≤ s ≤ t

Define the backlog of a system as the amount of data still in transit (between input and output points). Let s be the instant such that

x(s) + β(t-s) =
    inf  {x(s) + β(t-s)}.
0 ≤ s ≤ t

If, in the service curve definition, it is also required that the backlog at instant s is zero, i.e., x(s) = y(s), then we say that β is a strict service curve between x and y. In this case, t ∈ R+, ∃s ∈ R+ such that st and

y(t) - y(s) ≥ β(t-s).

Strict service curves are particularly important to represent multiplexing of flows of different priorities.

Define [x]+ = max{0, x}. The most common service curve in the literature is the “rate latency” curve defined as t ∈ R:

β(t) = R·[t - T]+.

Service Curves: Example

Consider functions x(t) and β(t) as shown in Figure 3 below. Define

f(t) =   inf  {x(s) + β(t-s)}.
0 ≤ s ≤ t

If y(t) is an output function of a network that offers a service curve β(t) to the input flow x(t), then, from the definition of Service Curve, y(t) must satisfy the inequality, t: y(t) ≥ f(t). Figure 3 (b) shows an example of y(t) that satisfies this inequality. Notice that, as expected for causal systems, y(t) also satisfy the inequality y(t) ≤ x(t), ∀t.

ServiceCurveExample
(a)
(b)


Figure 3

Performance Parameters: Definition and Bounds

Given a system with input flow x and output flow y, define:

  • Backlog at instant t - vertical deviation between x and y, i.e.,
    x(t) - y(t).
  • Virtual delay at instant t - horizontal deviation between x and y, i.e.,
    d(t) = inf {d ≥ 0: x(t) ≤ y(t+d)}.

From the concepts of regulation and service curves, it is possible to obtain bounds for the maximum delay and backlog between x and y, respectively D and W, and a regulation curve σy for y. We have

D = inf {d ≥ 0: σ(t) ≤ β(t+d), ∀t};
W = sup {σ(s) - β(s)};
s ≥ 0
  σy(t) = sup {σ(t+s) - β(s)}.
s ≥ 0

Bibliography: Notes

Network Calculus has its roots in [1-4]. The theory is mainly presented in [5-7], and a short introduction is found in [8-9].

NC appeared as a deterministic tool for the performance analysis of communication networks. However, there exist extensions in a stochastic context. For examples, see [10-14].

This website addresses mostly the deterministic Network Calculus. It is based mainly on [15-20].

In this section, just the basic ideas of Network Calculus were presented. For a more profound presentation of NC, it is necessary an introduction on dioid algebra. This is the subject of the next section: Dioid Algebra.

Bibliography

  1. R. L. Cruz. “A calculus for network delay, part I: Network elements in isolation,” IEEE Transaction on Information Theory, vol. 37, no. 1, pp. 114-131, January 1991. (pdf- Last access: November 22nd, 2012.)


  2. R. L. Cruz. “A calculus for network delay, part II: Network analysis,” IEEE Transaction on Information Theory, vol. 37, no. 1, pp. 132-141, January 1991. (pdf- Last access: November 22nd, 2012.)


  3. A. K. Parekh and R. G. Gallager. “A generalized processor sharing approach to flow control in integrated services networks: The single node case,” IEEE/ACM Transaction on Networking, vol. 1, no. 3, pp. 344-357, June 1993. (pdf- Last access: November 22nd, 2012.)


  4. A. K. Parekh and R. G. Gallager. “A generalized processor sharing approach to flow control in integrated services networks: The multiple node case,” IEEE/ACM Transaction on Networking, vol. 2, no. 2, pp. 137-150, April 1994. (pdf- Last access: November 22nd, 2012.)


  5. J.-Y. Le Boudec and P. Thiran.(2003, June) Network Calculus- A theory of deterministic queueing systems for the Internet. (pdf)- Last access: November 22nd, 2012.)


  6. J.-Y. Le Boudec, “Network Calculus made easy,” DI-EPFL, Lausanne, Switzerland, Tech. Rep. 96/218, CH-1015, December 1996. (CiteSeer)- Last access: November 22nd, 2012.)


  7. C.-S. Chang, Performance Guarantees in Communication Networks, ser. Telecommunication Networks and Computer Systems. London: Springer-Verlag, 2000.


  8. J.-Y. Le Boudec, P. Thiran and S. Giordano, “A short tutorial on Network Calculus I: Fundamental bounds in communication networks,” in IEEE International Symposium on Circuits and Systems (ISCAS’00). Geneva, Switzerland: IEEE, May 28-31 2000, pp. IV-93-IV-96. (CiteSeer)- Last access: November 22nd, 2012.)


  9. J.-Y. Le Boudec, P. Thiran and S. Giordano, “A short tutorial on Network Calculus II: Min-Plus system theory applied to communications networks,” in IEEE International Symposium on Circuits and Systems (ISCAS’00). Geneva, Switzerland: IEEE, May 28-31 2000, pp. IV-365-IV-368. (CiteSeer)- Last access: November 22nd, 2012.)


  10. M. Vojnovic and J.-Y. Le Boudec, “Elements of Probabilistic Network Calculus for Packet Scale Rate Guarantee Nodes,” in Invited Session on Network Calculus, Fifteenth International Symposium on Mathematical Theory of Networks and Systems. University of Notredame, Indiana, USA: August 2002. (Alternative pdf version)- Last access: November 22nd, 2012.)


  11. J. Liebeherr, S. D. Patek and A. Burchard, “Statistical Per-Flow Service Bounds in a Network with Aggregate Provisioning,” in Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03). San Francisco, California, USA: IEEE, 2003, v. 3, pp. 1680- 1690.


  12. K. Pandit, J. Schmitt and R. Steinmetz, “Network Calculus meets Queueing Theory- A simulation Based Approach to Bounded Queues,” in Twelfth IEEE International Workshop on Quality of Service (IWQoS'04). Montreal, Canada: IEEE, June 2004, pp. 114-120. (pdf)- Last access: September 3rd, 2009.


  13. Y. Jiang, “A Basic Stochastic Network Calculus,” in Special Interest Group on Data Communications (ACM SIGCOMM'06). Pisa, Italy: ACM, September 2006, pp. 123-134.


  14. C. Li, A. Burchard and J. Liebeherr, “A Network Calculus with Effective Bandwidth,” in IEEE/ACM Transactions on Networking. IEEE/ACM, December 2007, v. 15, no. 6, pp. 1442-1453.


  15. M. Daniel-Cavalcante, “Modelagem e Determinação de Parâmetros de Desempenho de Redes de Comunicações Através da Álgebra de Dióides,” Fevereiro 2008. Tese de Doutorado. Universidade Estadual de Campinas (UNICAMP), Campinas, Fevereiro 2008. (pdf)


  16. M. Daniel-Cavalcante and R. Santos-Mendes, “Dioid of Formal Power Series for the Determination of Performance Parameters of Communication Networks,” in 9th International Workshop on Discrete Event Systems (WODES'08). Invited Session “Max-Plus Algebra and Max-Plus Systems II”. Göteborg, Sweden: May 2008, p. 248-253. (pdf)


  17. M. Daniel-Cavalcante and R. Santos-Mendes, “Metodologia modular baseada em dióides para a modelagem de restrições de desempenho de redes de comunicações,” in Primeiro Encontro dos Alunos e Docentes do Departamento de Engenharia de Computação e Automação Industrial (EADCA'08). Campinas, SP, Brasil: 2008, p. 1-2.


  18. M. Daniel-Cavalcante, M. F. Magalhães and R. Santos-Mendes, “The Max-Plus algebra and the Network Calculus,” in 8th International Workshop on Discrete Event Systems (WODES'06). Ann Arbor, MI, USA: 2006, p. 433-438.


  19. M. Daniel-Cavalcante, M. F. Magalhães and R. Santos-Mendes. In: Commault, C. (Ed.); Marchand, N. (Ed). Positive Systems. Berlin, Germany: Springer Berlin/Heidelberg, October, 2006, v. 341/2006 in Lecture Notes in Control and Information Sciences, Chapter: Max-Plus: A Network Algebra, 2006, p. 375-382.


  20. M. Daniel-Cavalcante, R. Santos-Mendes, “A Álgebra Max-Plus e o controle de tráfego em elementos de redes de comunicações,” in XVI Congresso Brasileiro de Automática (CBA'06). Salvador, BA, Brasil: 2006, p. 2183-2188.


Back to top ↑

Last update: 2012-11-22

© 2009-2012 · Mabia Cavalcante