ProgMP: Programmable MultiPath TCP Scheduling

ProgMP is a programming model for Multipath TCP scheduling. It provides powerful abstractions to develop own application- and preference-aware schedulers. This page provides a getting started tutorial, scheduler examples, an overview of the extended socket API and the language primitives. Check out our paper on ProgMP (to appear) at ACM/IFIP/USENIX Middleware 2017 for more details. If you use ProgMP in scientific papers, please use the following citation.

A Programming Model for Application-defined Multipath TCP Scheduling

by Alexander Frömmgen, Amr Rizk, Tobias Erbshäußer, Max Weller, Boris Koldehofe, Alejandro Buchmann, Ralf Steinmetz

Download Paper

1. Getting Started

You are just 5 minutes away from your first Multipath TCP scheduler. We propose to use Ubuntu for the following steps:

  • Download our precompiled Linux Kernel.
  • Install the Kernel with dpkg -i linux-image-4.1.20-ProgMp.deb and reboot your system with the new Kernel (check the offical MPTCP Linux Kernel page for additional details).
  • Download the simple example scheduler and load it into the Kernel by calling this script with sudo python progmp_helper.py -f illustratingMinRtt.progmp (requires Python). Activate ProgMP with sysctl -w net.mptcp.mptcp_scheduler=rbs.
  • You are now using the loaded scheduler. Try out the new scheduler, e.g., by visiting a webpage which supports Multipath TCP.
  • Modify the scheduler to use the subflow with the minimum round-trip time variance by replacing MIN(sbf => sbf.RTT) with MIN(sbf => sbf.RTT_VAR) and renaming the scheduler from illustratingMinRTT to illustraingMinVariance at the top of the file. Load the new scheduler.
  • Congratulations! You just developed your first Multipath TCP scheduler.

2. Background: Multipath TCP Scheduling

What is Multipath TCP?

Multipath TCP allows you to use multiple subflows for a single Multipath TCP connection, e.g., to aggregate bandwidth of different network paths or handle a handover between WiFi and LTE. This article provides a good overview of today's commercial Multipath TCP application scenarios.

What is Multipath TCP Scheduling?

The Multipath TCP scheduler decides which packet should be transmitted on which subflow.

What happens at the receiver side?

The receiver ensures that packets are forwarded to the application in-order. Bad scheduling decisions might force the receiver side to wait for missing packets.

Why is Multipath TCP Scheduling important?

There are many good reasons. Consider, for example, a Multipath TCP connection with multiple heterogeneous subflows. Packets on a high delay subflow might force the receiver to wait and thereby slow down the connection.

3. Scheduler Examples

In the following, we provide illustrating scheduler examples, e.g., schedulers with different retransmission and redundancy strategies. More examples are available in our paper (to appear). Please contact us in case you want to add your scheduler to this list.

Illustrating Minimum RTT Scheduler

/*
 * Scheduler sending packets on the subflow with the lowest RTT which has cwnd.
 */
SCHEDULER illustratingMinRTT;

VAR sbfCandidates = SUBFLOWS.FILTER(sbf => sbf.CWND > sbf.SKBS_IN_FLIGHT + sbf.QUEUED AND !sbf.THROTTLED AND !sbf.LOSSY);

IF(sbfCandidates.EMPTY) { RETURN; }

IF (!RQ.EMPTY) {
  VAR sbfCandidate = sbfCandidates.FILTER(sbf => sbf.HAS_WINDOW_FOR(RQ.TOP) AND !RQ.TOP.SENT_ON(sbf)).MIN(sbf => sbf.RTT);
  IF (sbfCandidate != NULL) {
    sbfCandidate.PUSH(RQ.POP());
    RETURN;
  }
}

IF (!Q.EMPTY) {
  sbfCandidates.FILTER(sbf => sbf.HAS_WINDOW_FOR(Q.TOP)).MIN(sbf => sbf.RTT).PUSH(Q.POP());
}   
Download Example

Retransmission Handling

In the previous example, retransmissions were handled with the following code snippet.

/* Retransmission snippet */
IF (!RQ.EMPTY) {
  VAR sbfCandidate = sbfCandidates.FILTER(sbf => sbf.HAS_WINDOW_FOR(RQ.TOP) AND !RQ.TOP.SENT_ON(sbf)).MIN(sbf => sbf.RTT);
  IF (sbfCandidate != NULL) {
    sbfCandidate.PUSH(RQ.POP());
    RETURN;
  }
}
Download Example

Retransmissions, however, have a strong impact on the tail latency for many application scenarios. The following code snippet uses higher redundancy for retransmissions.

/* Retransmission on all subflows with cwnd */
IF (!RQ.EMPTY) {
    VAR retransmissionCandidates = sbfCandidates.FILTER(sbf => sbf.HAS_WINDOW_FOR(RQ.TOP) AND !RQ.TOP.SENT_ON(sbf));
    IF(!retransmissionCandidates.EMPTY) {
        FOREACH(VAR sbf IN retransmissionCandidates) {
            sbf.PUSH(RQ.TOP);
        }
        DROP(Q.POP());
    }
}
Download Example

The previous example might not use full redundancy, e.g., in case a retransmission is handled and only one subflow has unexhausted congestion window. The following code snippet uses full redundancy for retransmissions.

/* Retransmissions on all subflows */
IF (!RQ.EMPTY) {
    IF (!SUBFLOWS.FILTER(sbf => !RQ.TOP.SENT_ON(sbf)).EMPTY) {
        DROP( RQ.POP());
        RETURN;
    } ELSE {
        VAR retransmissionCandidates = sbfCandidates.FILTER(sbf => sbf.HAS_WINDOW_FOR(RQ.TOP) AND !RQ.TOP.SENT_ON(sbf));
        IF(!retransmissionCandidates.EMPTY) {
            FOREACH(VAR sbf IN retransmissionCandidates) {
                sbf.PUSH(RQ.TOP);
            }
            RETURN;
        }
    }
}
Download Example

Redundancy Flavors

In the previous section, we saw different redundancy flavors for retransmissions. Redundancy might be helpful even for non-retransmission packets, e.g., for thin, latency sensitive flows. The following scheduler specification is (nearly) similar to the existing redundant MPTCP scheduler.

/*
 * Redundant scheduler.
 */
SCHEDULER redundantScheduler;

VAR sbfCandidates = SUBFLOWS.FILTER(sbf => sbf.CWND > sbf.SKBS_IN_FLIGHT + sbf.QUEUED AND !sbf.THROTTLED AND !sbf.LOSSY);

/* handle retransmissions (see discussion above) */
...

FOREACH(VAR sbf IN sbfCandidates) {
    VAR skb = QU.FILTER(skb => !skb.SENT_ON(sbf)).TOP;
    /* are all QU packets sent on this sbf? */
    IF(skb != NULL) {
        sbf.PUSH(skb);
    } ELSE {
        sbf.PUSH(Q.POP());
    }
}
Download Example

The redundant scheduler faces a choice whether to prefer new packets or old packets. The following scheduler utilizes for redundant transmission only the subflows which are available at the moment when the packet is scheduled for the first time.

/*
 * Redundancy flavor.
 */
SCHEDULER redundancyFlavor;

VAR sbfCandidates = SUBFLOWS.FILTER(sbf => sbf.CWND > sbf.SKBS_IN_FLIGHT + sbf.QUEUED AND !sbf.THROTTLED AND !sbf.LOSSY);

IF(sbfCandidates.EMPTY) { RETURN; }

/* handle retransmissions (see discussion above) */
...

IF(!Q.EMPTY) {
    /* PUSH it on all currently available subflows */
    FOREACH(VAR sbf IN sbfCandidates) {
        sbf.PUSH(Q.TOP);
    }
    DROP(Q.POP());
}
Download Example

More examples...

... will follow soon.

4. Getting the source

We are currently preparing the code to make it publicly available. This might need a few weeks. Feel free to contact us.

5. Extended Socket API

ProgMP provides an extended Socket API and helper libraries for Python and C. The extended Socket API allows a configuration of the scheduler, e.g., by setting register values or packet properties.

Python Example

Download our Python library progmp.py for a convenient interaction with the scheduler. The following Python 2.7 example shows how to dynamically load and select a scheduler as well as how to configure the scheduler by setting registers and packet user properties.

import socket
from progmp import ProgMp

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("10.0.0.2", 8080))

schedulerName = "python_api_example"
with open("python_api_example.progmp", "r") as src:
	schedProgStr = src.read()
try:
	ProgMp.loadScheduler(schedProgStr)
except:
	print "Scheduler loading error."
	
try:
	ProgMp.setScheduler(s, schedulerName)
except:
	print "Scheduler not found, maybe no MPTCP?"
	
ProgMp.setUser(s, 2)
ProgMp.setRegister(s, Progmp.R1(), 5)
s.send("Multipath is awesome!")
Download Example

The scheduling API enables writing application-specific schedulers, e.g., a scheduler can use the provided information for a differentiated behavior. The following scheduler snippet shows a simple proof of concept.

PRINT("Scheduler called with R1=%d", R1);
PRINT("Q.TOP.USER = %d", Q.TOP.USER);
Download Example

C Example

Use progmp.c and progmp.h for a convenient interaction with the scheduler from C. The following example illustrates the most important features.

#include "progmp.h"
...
if (!progmp_load_scheduler(name, filename)) {
  printf("Error: Rules could not be loaded. See dmesg for more details.\n");
  return 1;
}
...
sock = socket(AF_INET, SOCK_STREAM, 0);
...
progmp_set_scheduler(sock, name);
progmp_set_register(sock, 1, 5);
...
progmp_remove_scheduler(name);
Download Example

The previous scheduler example (Download) might be used for a proof of concept.

6. FAQ

Why do we need an own programming model for MPTCP scheduling?

There are many reasons for a dedicated Domain Specific Language for Multipath TCP schedulers. We started the development of ProgMP after our first experiences with the redundant MPTCP scheduler, where we recurrently discussed small modifications and alternatives. The evaluation of these modifications was slowed down by the development effort towards new schedulers. We found the development of Multipath TCP schedulers is complex and error prone. Our discussions about alternative redundant schedulers showed that reasoning about schedulers is difficult and lacks suitable abstractions (answering questions such as: How would the scheduler behave if...?). Finally, the Multipath TCP community, e.g., on the mailing list, shows a strong interest in understanding and improving Multipath TCP scheduling.

In a nutshell:

  • Reasoning about (tuned) scheduler implementations in C is cumbersome (e.g., try to answer: What does the default scheduler do in case multiple packets are in the retransmission queue, but only subflows are available which...?)
  • Developing and evaluating novel schedulers requires detailed Kernel knowledge. Depending on the experience of the developer, this is a challenging and error prone task.
  • There is a huge, widely unexplored design space for application- and preference-aware MPTCP schedulers.
ProgMP enables non-Kernel experts to develop, evaluate and deploy own application- and preference-aware schedulers.

Something is missing (aka. I can't express my fancy scheduler ideas).

We are very curious about your concrete scenario. Please contact us, as we are constantly improving ProgMP.

What does RBS stand for (it appears quite often, e.g., in the proc file system)?

RBS was the development name of our system. We will change this to ProgMP.

My scheduler does not work as expected. How can I debug it?

We currently do not support interactive debugging, as timing is an important scheduling property. However, there are some tricks:

  • Use PRINT statements to analyze your scheduler, e.g., like this.
  • Check the statistics available in /proc/net/mptcp/rbs

Why are all keywords in the language upper case?

Notation matters! It helps to differentiate between keywords and other parts of your schedulers.

Loading my scheduler failed. Where can I get error messages?

Execute dmesg in your shell.

Everything crashes...

... please contact us providing details about your test setup and the used scheduler.

7. Pattern, Antipattern and Pitfalls

Print Statistics

Printing during scheduling might have a negative impact on the scheduling performance. We propose to limit the number of prints, e.g., based on a time intervals as shown below.

IF(R6 < CURRENT_TIME_MS) {
  VAR interPrintInterval = 200;
  SET(R6, CURRENT_TIME_MS + interPrintInterval);

  PRINT("Number of Subflows is %d", SUBFLOWS.COUNT);
}
Download Example

Pitfalls

ProgMP is designed for a convenient scheduler specification. However, with great power comes great responsibility. Small differences in scheduler specification might lead to fundamentally different scheduling behavior. In the following, we present a few pitfalls which illustrate some of the main concepts of ProgMP.

SUBFLOWS.FILTER(...).MIN(...).PUSH(Q.TOP);
/* The filter might evaluate to an empty list of subflows. Dropping the packet will lead to loss of unsent data. */
DROP(Q.POP());

A slightly modified version of the first example scheduler, for example, might lead to low throughput in case of retransmissions. The modification (removing the second RETURN statement and adding a ELSE to the next condition) might look like a reasonable simplification of the code.

...
IF (!RQ.EMPTY) {
  VAR sbfCandidate = sbfCandidates.FILTER(sbf => sbf.HAS_WINDOW_FOR(RQ.TOP) AND !RQ.TOP.SENT_ON(sbf)).MIN(sbf => sbf.RTT);
  sbfCandidate.PUSH(RQ.POP());
} ELSE IF (!Q.EMPTY) {
  sbfCandidates.FILTER(sbf => sbf.HAS_WINDOW_FOR(Q.TOP)).MIN(sbf => sbf.RTT).PUSH(Q.POP());
}   

More examples will follow soon.

8. Mininet Test Setup

Mininet allows simple network emulation experiments. You may use this Mininet script to test your schedulers. The script uses our Python API, so make sure to download it as well.

sudo python mininet_progmp_helper.py -f [mySchedulerFile]

9. Language and Concept Overview

The domain specific programming model relies on the following abstractions, which are provided as entities in the language. Most entities, such as the congestion control values and round-trip times, have a direct counterpart in the Linux Kernel network stack. The following list is not complete yet. We will update the list soon.

Each scheduler starts with the SCHEDULER keyword followed by its name and a terminating ;.

SCHEDULER myFirstScheduler;

Types

ProgMP uses an implicit type system. In most cases, the developer does not have to care about the underlying types. The following underlying types are used:

  • Boolean
  • Unsigned Integer
  • String
  • Subflow
  • Subflow List
  • Packet
  • Packet Queue

Statements

ProgMP supports the following statements:

DROP

Drops a packet. Be careful to not drop packets which were not sent so far.

DROP(Q.POP());

FOREACH

Loops over all items inside a list.

FOREACH(VAR sbf IN SUBFLOWS) {
  /* Do something */
}

IF

Executes code depending on a condition. The else branch is optional. Note that a condition which evaluates to NULL is treated as FALSE.

IF (SUBFLOWS.COUNT == 1) {
  PRINT("Exactly 1 subflow\n");
} ELSE {
  PRINT("More than 1 subflow\n");
}

PRINT

Print a message to the kernel console with an optional parameter (no lists supported as parameter). You may read the output using dmesg. Note that print statements have a strong impact on the performance and should only be used for debugging purposes.

PRINT("Hello world!\n");
PRINT("We have %d subflows.\n", SUBFLOWS.COUNT);

RETURN

Stops the execution of the scheduler.

RETURN;

SET

Sets a register to a value. If value is NULL, the register is not changed.

SET(R1, 42);

VAR

Declares a new variable. Variables can only be assigned once per scheduler execution (single assignment) and have an implicit type.

VAR x = 42;
VAR sbfs = SUBFLOWS.FILTER(sbf => sbf.CWND > 20);

VOID

Does nothing, but accepts a parameter. The parameter is evaluated (i.e., side effects might be triggered) but the result will be ignored. This statement is only used for measurements!

VOID(5+9)

Built-in variables

ProgMP provides the following build-in variables:

Q

Returns the sending queue packet list.

Q.TOP

QU

Returns the unacknowledged packet list.

QU.TOP

RQ

Returns the retransmission queue packet list.

CURRENT_TIME_MS

Returns the current time in milliseconds.

CURRENT_TIME_MS

R1 - R6

Returns the value of the register with the given number. Registers are integer variables that keep their values across scheduler executions. ProgMP provides a fixed set of 6 registers to limit memory consumption.

PRINT("R1 has the value %d.\n", R1);

RANDOM

Returns a random integer value.

SUBFLOWS

Returns the list of currently active subflows.

PRINT("Number of subflows is %d", SUBFLOWS.COUNT)

Packet Properties

Packets are chosen based on Q, QU or RQ. Each packet has the following properties.

SENT_ON(subflow)

Returns TRUE if the packet was already sent on the given subflow.

Q.TOP.SENT_ON(SUBFLOWS.MIN(sbf => sbf.RTT))

USER

Returns the user integer value of the packet, e.g., as set by the extended API.

PRINT("The top packet has %d as user property", Q.TOP.USER)

SEQ

Returns the sequence number of the packet.

PRINT("The top packet has the sequence number %d", Q.TOP.SEQ)

LENGTH

Returns the length of the packet.

PRINT("The top packet has a length of %d", Q.TOP.LENGTH)

PSH

Returns if the PUSH flag of the packet is set.

IF(Q.TOP.PSH) { PRINT("The top packet has a set PUSH flag"); }

Packet Queue Properties

Each packet queue has the following properties.

COUNT

Returns the number of packets in the list.

Q.COUNT

EMPTY

Returns TRUE if the packet list is empty.

FILTER

Returns a list with those packets for which the given condition evaluated to TRUE.

VAR packetsToSend = Q.FILTER(s => !s.SENT_ON(SUBFLOWS.GET(0)));

POP

Removes the first packet from the packet list and returns it. This is not possible on QU or a queue resulting from a FILTER expression of QU. Packets retained by POP have to be pushed or dropped explicitly. In particular, POP must not be used in conditions. POP requires two brackets, as shown in the example, to indicate that it causes side effects.

SUBFLOWS.GET(0).PUSH(Q.POP())

TOP

Returns the first packet of the packet list without modifying the underlying list.

SUBFLOWS.GET(0).PUSH(Q.TOP)

Subflow Properties

CWND

Returns the congestion window value of the subflow.

HAS_WINDOW_FOR(packet)

Returns TRUE if the subflow has sufficient flow control window to send the given packet.

IF(SUBFLOW.GET(0).HAS_WINDOW_FOR(Q.TOP)) {
...

ID

Returns the unqiue identifier of the subflow.

PRINT("Subflow %d has the minimum round-trip-time.", SUBFLOWS.MIN(sbf => sbf.RTT).ID)

IS_BACKUP

Returns TRUE if the subflow is marked as backup.

LOST_SKBS

Returns the number of lost packets of the subflow.

RTT

Returns the round-trip time of the subflow.

RTT_VAR

Returns the variance of the round-trip time of the subflow.

SKBS_IN_FLIGHT

Returns the number of packets of the subflow that are in flight.

QUEUED

Returns the number of packets of the subflow that are queued.

USER

Returns the user specified subflow property.

SET_USER

Sets the user specified subflow property.

SUBFLOWS.MIN(sbf => sbf.RTT).SET_USER(5)

Subflow List Properties

COUNT

Returns the number of subflows in the list.

EMPTY

Returns TRUE if the subflow list is empty.

FILTER

Returns a list with those subflows for which the given condition evaluated to TRUE.

VAR sbfs_with_small_rtt = SUBFLOWS.FILTER(s => s.RTT < 100);

GET

Returns the subflow with the given index. If the index exceeds the number of subflows in the list, NULL is returned. Check here for more details regarding NULL handling.

MAX

Returns the subflow of the list for which the given condition evaluates to the greatest value. Subflows for which the condition evaluates to NULL are ignored. Check here for more details regarding NULL handling.

If multiple subflows have the same, greatest value, only a single subflow is returned. In this case, it is not specified which subflow is returned. It is also not guaranteed that consecutive calls return the same subflow.

VAR sbfWithGreatestRtt = SUBFLOWS.MAX(sbf => sbf.RTT);

MIN

Returns the subflow of the list for which the given condition evaluates to the smallest value. Subflows for which the condition evaluates to NULL are ignored. Check here for more details regarding NULL handling.

If multiple subflows have the same, minimum value, only a single subflow is return. In this case, it is not specified which subflow is returned, neither that consecutive calls return the same subflow.

VAR sbfWithSmallestRtt = SUBFLOWS.MIN(s => s.RTT);

SUM

Returns the sum of the expression evaluated over all subflows in the list.

VAR rtt_sum = SUBFLOWS.SUM(s => s.RTT);

Operators

Values can be combined using comparison and arithmetic operators:

  • == Compares two integer values and returns TRUE if they are equal.
  • == NULL Returns TRUE if a value of any type is NULL.
  • != Compares two integer values and returns TRUE if they are unequal.
  • != NULL Returns TRUE if a value of any type is not NULL.
  • < Compares two integer values and returns TRUE if the first is less than the second one.
  • <= Compares two integer values and returns TRUE if the first is less than or equal the second one.
  • > Compares two integer values and returns TRUE if the first is greater than the second one.
  • >= Compares two integer values and returns TRUE if the first is greater than or equal the second one.
  • + Adds two integer values.
  • - Subtracts one integer value from another.
  • * Multiplies two integer values.
  • / Divides one integer value by another. Returns NULL if the right value is 0.
  • % Returns the remainder of a division. Returns NULL if the right value is 0.
  • AND Performs a logical AND operation on two boolean values. The second operand is not evaluated if the first one evaluates to FALSE.
  • OR Performs a logical OR operation on two boolean values. The second operand is not evaluated if the first one evaluates to TRUE.
  • ! Performs a logical NOT operation on a boolean value.

NULL handling

ProgMP handles NULL values gracefully and well-defined. In a boolean expression with AND or OR, NULL behaves like FALSE. All other expressions which contains NULL evaluate to NULL, e.g., 5 + NULL evaluates to NULL, NULL == FALSE evaluates to FALSE, and ! NULL evaluates to NULL. Early prototypes of ProgMP tried to avoid NULL. However, we found that schedulers became more complex and difficult to express without NULL.

A statement that uses a value as parameter that evaluates to NULL is not executed.

SUBFLOWS.GET(0).PUSH(Q.FILTER(s => FALSE).POP());

A statement that operates on a value that evaluates to NULL is not executed. This avoids, e.g., to accidentally remove a packet from Q in case a complex filter statement evaluates to FALSE.

SUBFLOWS.FILTER(sbf => FALSE).PUSH(Q.POP());

Acknowledgments

This work has been funded by MAKI to make the Internet more adaptive.

Contact

Feel free to contact Alexander Frömmgen for any comments and questions.