ProgMP: Programmable MultiPath TCP Scheduling

0001₂ 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.

0010₂ Background: Multipath TCP Scheduling

What is Multipath TCP?

What is Multipath TCP Scheduling?

What happens at the receiver side?

Why is Multipath TCP Scheduling important?

0011₂ Research Papers that used ProgMP

The following research papers contributed to ProgMP or used ProgMP.

• Copy Bib 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, ACM/IFIP/USNIX Middleware 2017.
• Copy Bib Demo: Programming Application-defined Multipath TCP Schedulers by Alexander Frömmgen and Boris Koldehofe, ACM/IFIP/USNIX Middleware 2017.
• Copy Bib Multipath TCP Scheduling for Thin Streams: Active Probing and One-way Delay-awareness by Alexander Frömmgen, Jens Heuschkel, Boris Koldehofe, IEE ICC 2018.

0100₂ Scheduler Zoo

In the following, we provide illustrating scheduler examples, e.g., schedulers with different retransmission and redundancy strategies. More examples are available in our papers. 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());
}   

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;
  }
}

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());
    }
}

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;
        }
    }
}

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());
    }
}

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());
}

0101₂ Getting the Source

The source of our ProgMP runtime environment for the Linux kernel MPTCP implementation is available here. Feel free to contact us in case you experience any problems. A github version of the source is provided by joh2511 here. Separate patches for the receiver side and the one-way delay-estimations are available.

0110₂ 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!")

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);

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);

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

0111₂ FAQ

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

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

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

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

Why are all keywords in the language upper case?

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

Everything crashes...

1000₂ 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);
}

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.

1001₂ 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]

Be aware of potential Mininet pitfalls.

1010₂ 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

DROP(Q.POP());

FOREACH

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

IF

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

PRINT

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

RETURN

RETURN;

SET

SET(R1, 42);

VAR

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

VOID

VOID(5+9)

Built-in variables

ProgMP provides the following build-in variables:

Q

Q.TOP

QU

QU.TOP

RQ

CURRENT_TIME_MS

CURRENT_TIME_MS

R1 - R6

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

RANDOM

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)

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

USER

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

SEQ

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

LENGTH

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

PSH

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

Packet Queue Properties

Each packet queue has the following properties.

COUNT

Q.COUNT

EMPTY

FILTER

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

POP

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

TOP

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

GET(

QU.GET(2)

Subflow Properties

CWND

HAS_WINDOW_FOR(packet)

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

ID

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

IS_BACKUP

LOST_SKBS

RTT

RTT_VAR

SKBS_IN_FLIGHT

QUEUED

USER

SET_USER

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

Subflow List Properties

COUNT

EMPTY

FILTER

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

GET

MAX

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

MIN

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

SUM

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.