Routing and Scheduling for Time-Sensitive Networks

(Announced April 3, 2017)

A large class of embedded applications are dependent on predictable communications for accurate control (automotive, avionics) while also requiring enough bandwidth for less critical software (multimedia streaming). Time-Sensitive Networking is a set of standards under development by IEEE 802.1, which are becoming increasingly attractive for applications requiring connections with low-latency, high-bandwidth and availability. Three traffic classes are specified by TSN, namely time-triggered (TT), constrained bandwidth (CB), and best effort (BE), all providing support for a varying grade of criticality.  The most critical, TT, requires careful routing and scheduling in order to meet the application demands.
The goal of this project is to propose routing and scheduling tools for the TT and CB traffic, for a predefined network topology and application set. The applications will be taken from the streaming domain, where throughput is more important than latency, but latency is also constrained. One direction is to use constraint programming to define and solve the problem, but heuristics or integer linear programing may also be of use.

Prerequisites: 2 students. Knowledge of constraint programming or other optimization techniques is highly recommended. Some knowledge of packet switched networks (Ethernet), routing and scheduling techniques is a big plus.

References:

1. Time - Sensitive networking task Group: http://www.ieee802.org/1/pages/tsn.html
2. M. L. Raagaard, "Algorithms for the Optimization of Safety-Critical Networks", DTU M.Sc, Jan 2017.
3. JaCoP - Java Constraint Programming solver: http://jacopapi.osolpro.com

Software-defined Networking for Streaming Applications

(Announced April 3, 2017)

Software Defined Networks have been proposed as a way of virtualizing networks, the same way hypervisors can be used to virtualize hardware platforms. Streaming applications, defined as a communicating network of actors could benefit from abstracting their underlying communication infrastructure in several ways. For instance, actor mobility across processing nodes could be made transparent to the actors, by reconfiguring the network. OpenFlow (Open Networking Forum) is a protocol for SDN that seems to gain momentum, and several switches implementing it are already available for use. The goal of this project is to examine how OpenFlow can be used in the context of streaming applications, in particular for virtualizing the communication structure of the application. Further, assuming some mobility of functionality, examine how the reconfiguration of the network can be carried out, without significantly affecting the functionality or performance of the application.

In practice this would imply:

• proposing a method to program/configure the network for a given distribution of functionality (actors on nodes)

• evaluating the performance of the solution with SDN compared to a standard dynamic routing network

• a method for reconfiguring/updating the network when an actor moves to a different node

• evaluating the impact on performance of the reconfiguration

Prerequisites: 2 students. Knowledge of optimization techniques and C-programming is highly recommended. Knowledge of packet switched networks, routing and scheduling is a plus.

References:

1. OpenFlow website: https://www.opennetworking.org/sdn-resources/openflow
2. Durner, R., Blenk, A. and Kellerer, W., 2015, June. Performance study of dynamic QoS management for OpenFlow-enabled SDN switches. In Quality of Service (IWQoS), 2015 IEEE 23rd International Symposium on (pp. 177-182). IEEE.
3. Eker, J. and Janneck, J., 2003. CAL language report (Vol. 3). Tech. Rep. ERL Technical Memo UCB/ERL.

Contact person: Flavius Gruian

In order to deliver high quality output, modems have tight real-time requirements, typically defined in terms of minimum guaranteed throughput and/or maximum latency.

Embedded platforms for modems are expected to handle several streams at the same time, each with its own rate. Typically, functionality can be divided in jobs, i.e. minimal groups of communicating tasks that are started and stopped independently. The number of use-cases (i.e. combinations of simultaneously executing job instances) can be high.

In the approach being studied at ST-Ericsson in Eindhoven, the Netherlands, modem transceivers are modeled as data flow graphs [1]. 

The target hardware platform is a heterogeneous Multiprocessor System-On-Chip (MPSoC). 

On an MPSoC, transceivers share computation, storage, and  communication resources. This poses a particularly difficult problem for the scheduling of real-time applications: resource sharing leads to uncertainty about resource provision, and, consequently, uncertainty of the temporal behavior.

The overall scheduling  strategy proposed at ST-Ericsson [2] for this system mixes static (compile-time) and dynamic techniques (run time).

Intra-job scheduling (i.e scheduling of tasks that belong to the same job) is handled by means of static order, i.e., per job and per processor, a static ordering of actors is found that respects the Real-Time requirements while trying to minimize processor usage. Inter-job scheduling is handled by means of local Time Division Multiplex (TDM)  schedulers: per job and per processor a slice time duration S is allocated.

A tool is available that performs both mapping and temporal analysis of the mapped application.

A weakness of the current approach is that the data flow model is generated  manually, upon studying the actual application code. This means that the model may not actually conform to the actual implementation.

To bridge this gap between modeling and implementation, the model should be automatically extracted from the implementation code. For this to be possible, the implementation has to be specified in data flow. 

CAL  is a domain-specific language that provides useful abstractions for dataflow programming with actors. CAL has been used in a wide variety of applications and has been compiled to hardware and software implementations, and work on mixed HW/SW implementations is under way. 

The goals of this project are:

1. To show that CAL can be used to specify the inter-task communication behavior of a radio application running on an ST-Ericsson platform: this can be done by either adapting an existing radio implementation in CAL to the ST-Ericsson multiprocessor, or by re-implementing the task communication in an existing implementation of a radio application in the ST-Ericsson multiprocessor;
2. To show that a data flow analysis model can be generated from the CAL specification, and that this model can be analyzed by ST-Ericsson's data flow analysis tools;
3. To show that the CAL specification of the inter-task communication behavior can reuse algorithms already coded in C, using core intrinsics
4. To show that code using the ST-Ericsson runtime can be generated from the CAL specification.

The applicant preferably has a background in computer science, basic knowledge about signal processing, as well as good insights into compiler technology and embedded systems. 

The work is to be carried outing two phases: a first phase in Lund, for familiarization with the CAL language and associated tooling, And a second phase at the ST-Ericsson unit in Eindhoven, The Netherlands, for a minimum period of 6 months, under the local supervision of Orlando Moreira.

During the stay in Eindhoven, ST-Ericsson will grant a montlhy allowance to the applicant, to help with the costs of living in the Netherlands.

 [1] E. Lee and D. Messerschmitt  “Synchronous Data Flow”, Proceedings of the IEEE, 1987

[2] O. Moreira, F. Pereira, and M. Bekooij, “Scheduling Multiple Independent Hard-Real-Time Jobs on a Heterogeneous Multiprocessor”, Proceedings of the ACM Embedded Software (EMSOFT) Conference, Salzburg, Austria, 2007

[2] O. Moreira, et al, “Online Resource Management for a multiprocessor with a network-on-chip”, Proceedings of the ACM Symposium on Applied Computing, 2007

Contact person: Jörn W. Janneck