Network Calculus

Introduction

Network calculus is applied to deterministic queuing systems. It is always used to adjust delays and network buffer modules to meet the requirements of different networks and improve the QoS of the whole network. This concept or mathematic methods are usually applied in Flow Control to improve some fundamental performance bounds in communication networks.

This is a basic or brief tutorial of Network calculus. Anyone who works on network structure design or improving QoS and QoE (Quality of Entertainment) or even some network application developers could learn something from this article.

Contents of this Article

0. Definition of Network calculus
1. Basic keywords and definitions in Network calculus
   • Arrival Curves
   • Service Curves
   • Backlog, Delay Bounds, Output Flow, Greedy Shaper

Definition of Network Calculus

Network Calculus has thrown a deep sight into networking design area. Using this theory, we could calculate delays, buffer size, flow rate, etc. The Networking Calculus is based on Min-plus algebra. There are a lot of differences between traditional algebra theory and Min-plus algebra theory. The most considerable difference is the operation “addition” becomes “computation of the minimum”. And the following comparison could be a good example for this point.

The graph on the top one is a LTI Filter in conventional algebra using standard linear theory. If the input of the system is x(t)(t resembles a constant escaping time), the output of this simple circuit could be calculated by operation “convolution” and the output is:

The graph on the bottom is a model of Network Calculus Theory. A Linear System in Min-plus algebra is totally different.

• Input= arrived traffic in [0,t], x(t)
• System= a trunk of rate C: B(t)=Ct
• Output= Convolution of x(t) and B(t)

Basic Keywords and Definitions in Network Calculus

Arrival Curves

To ensure the data packages loss and circuit delay in specific networks, the most effective way is to control the data sources. And this could be done by using the definition of arrival curves. I am using equations to make it clearer.

According to the equations which are mentioned above, we could say that flow x is constrained by arrival curves α. And the following pictures and equations are about the most common Arrvial Curves.

The simplest arrival curves is “Affine Arrival Curve”.

Where r interpreted no more than r bits/sec and b means that data source is allowed to send b bits at once. Parameters b and r are called the burst tolerance (in units of data) and the rate (in units of data per time unit). So in this instance, the data source is sending packages constantly with the same data size. This could not be accomplished in the real life network and we could only use it as a model to understand the basic concept of “Arrival Curve”.

The most general arrival curve is called “Combining Leaky Buckets”. It represents the standard arrival curves in the Internet. While M means the maximum packet size, p interpreted the peak rate, b as the burst tolerance, and r as the sustainable rate.

Some properties of Arrival Curves are Listed

The operator is interpreted min-plus deconvolution.

Service Curves

When flows come to network nodes, these nodes need to process flows with some guarantees. And these guarantees could be shown by Service Curves in detail. We can express Service Curves with Min-Plus Convolution. Assuming there is a Flow x and it comes through a system S. The output of this system is y. We say that the system offers a Service Curve B. Commonly, there are two kinds of Service Curves. And guaranteed –delay node has Minimal Service Curves.

• Minimal Service Curve: For all t, exist some s, y(t)-x(s)>=B(t-s)
• Strict Service Curve: For any backlogged [s,t], y(t)-x(s)>=B(t-s)

Backlog, Delay Bounds, Output Flow, Greedy Shaper

Backlog

When flows are transferring in the network nodes, it should be some backlogs in the network which are have not received by ends. Network Calculus theory uses the vertical deviation between arrival curves and services curves to computing these backlogs. Imaging a flow, constrained by arrival curve α and it through a system offers with service curve β. Then the backlog is:

Delay

Flow is constrained by Arrival Curve α. And the system offers a service curve β to this flow.

Output Flow

Flow is constrained by Arrival Curve α. And the system offers a service curve β to this flow. The Output Flow is constrained by arrival curve:

Note

The passage is getting longer and longer. So I will put more instances of the implements of Network Calculus in the next post. So if you are interested in this theory, I strongly recommend you BOOKMARK it and you could follow it more easily.