Contact: Ludovic Thomas, Stéphan Plassart.
Time-sensitive networks are used for safety-critical systems in planes, satellites or even power plants. Their significance has been increasing over the years and they are now used in many more applications, ranging from autonomous cars, automated manufacture (industry 4.0) to 5G backbone networks. While traditional public networks aim at improving the mean service performances (mean ping, mean throughput), time-sensitive networks provide guarantees for the worst case (e.g. guarantee of a maximal latency, guarantee of a minimal throughput, guarantee of no loss, …).
To validate this guarantees and obtain the certification of the system from the certification authorities, performance bounds such as end-to-end latency and buffer occupation are obtained with deterministic analysis tools, based on Network Calculus [1]. The LCA2 laboratory of EPFL has developed several tools based on Network Calculus for computing performance bounds of time-sensitive networks.
Time sensitive networks are made of transmission links and switches. If several packets are waiting to be transmitted by a switch on the same transmission link, the output port of the switch often selects the next packet to be served based on a first-come, first-served principle. This FIFO scheduling (First-In, First-Out) is the most prominent technology today in time-sensitive networks because it is easy to implement.
But the FIFO scheduling policy has one serious drawback: it does not always guarantee the stability of the network. When a network becomes unstable, the latency of the network diverges, congestion occur and packets are lost. This can have catastrophic consequences for the people in the plane, in the car, etc. One might think that the instability can be prevented as long as the load (defined as the ratio between the input traffic and the throughput capacity) is below 100%. This is unfortunately not the case with the FIFO policy. Two papers from Andrews [2,3] show that for any load (even as close to 0 as desired), there exists at least one network that is unstable at this load. This seminal result has serious consequences for the design of time-sensitive networks.
The goal of the project is to validate that the networks proposed by Andrews are indeed unstable. A first goal will be to use the LCA2 analysis tools on the Andrews’ networks and to check that they all conclude to the absence of latency bounds. Depending on the evolution of the project, a second goal could be to use a Discrete Event Simulator (DES) such as ns-3 or INET on the Andrew’s networks and to validate that the simulations diverge.
Profile: Good knowledge of computer networks, programming skills using e.g. Python. Other Languages (C++, Java) are a plus.
[1] https://en.wikipedia.org/wiki/Network_calculus
[2] https://doi.org/10.1016/S0196-6774(03)00096-8
[3] https://doi.org/10.1145/1541885.1541894