Multipath scheduling

Today I mostly worked on my current research project, a simulator of multipath multistream scheduling algorithms.

Multipath scheduling is needed when you want to transmit data over several concurrent paths: which piece of data should be sent on which path? This problem has been made visible by Multipath TCP, since the Linux implementation includes several schedulers that can be changed at runtime. Several new schedulers for MPTCP are being proposed in the academic literature every year: the original LowRTT and its evaluation, Delay-Aware Packet Scheduling, BLocking ESTimation, Earliest Completion First, and many others.

All these algorithms mostly differ in the objective function they try to optimize or in assumptions that can be made for specific data flows (e.g. video streaming traffic). However, they all adopt the semantic of TCP, which transports a single flow of data. I am interested in extending the problem for several streams (have you heard of QUIC?) that need to be scheduled on multiple paths. Instead of a single optimisation problem, you now end up with several concurrent streams, where each stream wants to complete as soon as possible!

Writing a simulator

The goal of my simulator is to quickly obtain an intuition on the behaviour of scheduling algorithms: it provides a graphical and animated visualisation of what's going on over time. The simulator also allows for more in-depth exploration, for instance comparing the completion times of streams for different scheduling algorithms.

Below is a screenshot of the current simulator: it is not very pretty because that's not its goal! The streams are represented by vertical bars whose size equals the amount of data remaining to be transmitted, and the darker parts represent in-flight data. Below are two paths, each modelled as a packet queue with a constant-rate service (link capacity) and a fixed propagation time.

I am writing this simulator in Python thanks to salabim: this is a really well designed, easy-to-use and well-documented simulation framework. I had an initial simulation prototype working in less than one day, and it took only an additional day to add graphical visualisation. One of the reasons it's so easy to use is thanks to Python: I didn't want to spend days implementing complex algorithms in NS-3, even though it would be much more realistic. At the same time, salabim is reasonably fast once you disable logging and visualisation.

After working with salabim some more, I did find some limitations: the programming style around salabim is fine for small simulations, but quickly becomes a mess for larger projects. All examples use lots of global variables, which encourages you to write all your code in one file (after all, this is how salabim itself is developed with its 15k lines in a single file...)