Research

Interests

Methods

    Network Virtualization Technologies
    Virtual Network Embedding
    In-Network Processing
    Distributed Systems
    Routing
    (Mixed-) Integer Programming
    Approximation Algorithms
    Structural Graph Theory
    Manual Verification: Theorem Provers
    Automated Verification: Modelchecking

Projects

UNIFY Project (since 2014)

I take part in the EU FP7 Integrated Project UNIFY and will contribute in the design of the service description language and in service-chain optimization.
Today, rigid network control limits the flexibility of service creation. We pursue full network and service virtualization to enable rich and flexible services and operational efficiency. The UNIFY consortium researches, develops and evaluates means to orchestrate, verify and observe end-to-end service delivery from home and enterprise networks through aggregation and core networks to data centres.
UNIFY project homepage

VirtuCast: Optimal Virtualized In-Network Processing (since 2013)

In-network processing allows for the resource efficient deployment of communication tasks as e.g. multicast. Due to the ongoing effort to fully virtualize networks, including network nodes based on e.g. Network Functions Virtualization (NFV), new optimization opportunities arise. We have initiated the study of where to place processing functionality and how to route data in a joint fashion, such that bandwidth can be traded off with node resources. We have coined this problem the Constrained Virtual Steiner Arborescence Problem (CVSAP). CVSAP poses a novel optimization model for several communication services ranging from optical multicast in backbone networks to message aggregation in sensor nodes. Further applications are geo-replication of services in ISP networks and Big Data applications in data centers.

We have devised a novel single-commodity flow integer formulation for CVSAP that can be solved efficiently using branch-and-cut. While even realistically sized instances can be solved near optimally within one hour, the formulation also enables a range of polynomial-time heuristics which find high-quality solutions with high efficacy in minutes.
publications project homepage

Temporal Virtual Network Embedding Problem (since 2012)

The Temporal Virtual Network Embedding Problem (TVNEP) extends the classical Virtual Network Embedding Problem (VNEP) by introducing a temporal dimension: for each virtual network request a duration and a time interval is given in which it must be embedded. The TVNEP asks for finding suitable resources to embed the requests together with a feasible schedule, i.e. to find start and end times of the requests such that resource allocations are feasible at any point in time.

We have developed multiple Mixed Integer Programming formulations to obtain (near-) optimal solutions to this problem. For facilitating such exact methods, we have developed different state-space as well as symmetry reductions. We show that
publications project homepage

Publications

Virtual Network Embedding Problem
Network Updates
Virtualized In-Network Processing
Service Chaining & Network Functions Virtualization
Clear Selection

Conferences

    An Approximation Algorithm for Path Computation and Function Placement in SDNs
Guy Even, Matthias Rost, Stefan Schmid
23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2016, Helsinki, Finland, July 2016
pre-proceedings (pdf)         slides (pdf)         bibtex
   
    Transiently Secure Network Updates
Arne Ludwig, Szymon Dudycz, Matthias Rost, Stefan Schmid
ACM SIGMETRICS 2016, Antibes Juan-Les-Pins, France, June 2016
ACM download         slides (pdf)         bibtex
   
    Stitching Inter-Domain Paths over IXPs
Vasileios Kotronis, Rowan Klöti, Matthias Rost, Panagiotis Georgopoulos, Bernhard Ager, Stefan Schmid, Xenofontas Dimitropoulos
ACM SIGCOMM SOSR 2016, Santa Clara, California, USA, March 2016
slides (pdf)         bibtex
   
    Investigating the Potential of the Inter-IXP Multigraph for the Provisioning of Guaranteed End-to-End Services
Vasileios Kotronis, Rowan Klöti, Matthias Rost, Panagiotis Georgopoulos, Bernhard Ager, Stefan Schmid, Xenofontas Dimitropoulos
SIGMETRICS 2015 (poster), Portland, Oregon, USA, June 2015
ACM download         bibtex
   
    It's About Time: On Optimal Virtual Network Embeddings under Temporal Flexibilities
Matthias Rost, Stefan Schmid and Anja Feldmann
28th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Phoenix, Arizona, USA, May 2014
IEEE Xplore         slides (pdf)         bibtex
   
    VirtuCast: Multicast and Aggregation with In-Network Processing
  Matthias Rost, Stefan Schmid
  17th International Conference On Principles Of DIstributed Systems (OPODIS) 2013, Nice, France, December 2013
  springer link         slides (pdf)         project homepage         bibtex

Journals

    It's a Match!: Near-Optimal and Incremental Middlebox Deployment
Tamás Lukovszki, Matthias Rost, Stefan Schmid
ACM SIGCOMMM Computer Communication Review (CCR), 46.1, January 2016.
  ACM Digital Library         bibtex
   
    Network service chaining with optimized network function embedding supporting service decompositions
Sahel Sahhaf, Wouter Tavernier, Matthias Rost, Stefan Schmid, Didier Colle, Mario Pickavet, Piet Demeester
Computer Networks, Elsevier
  ScienceDirect         bibtex
   
    Beyond the Stars: Revisiting Virtual Cluster Embeddings
Matthias Rost, Carlo Fürst and Stefan Schmid
ACM SIGCOMMM Computer Communication Review (CCR), 45.3, July 2015.
  ACM download         bibtex         talk at Télécom-ParisTech, September 2015 (pdf)

Workshops

    Good Network Updates for Bad Packets: Waypoint Enforcement Beyond Destination-Based Routing Policies
  Arne Ludwig, Matthias Rost, Damien Foucard, and Stefan Schmid.
  13th ACM Workshop on Hot Topics in Networks (HotNets), Los Angeles, CA, USA, November 2014
  ACM download         bibtex
   
    Unifying the Programmability of Cloud and Carrier Infrastructure
  Pontus Skoldstrom, Balazs Sonkoly, Mario Kind, Fritz-Joachim Westphal, Wolfgang John, Jokin Garay, Eduardo Jacob, Janos Elek, David Jocha, Robert Szabo, Wouter Tavernier, George Agapiou, Antonio Manzalini, Matthias Rost, Nadi Sarrar, and Stefan Schmid.
  European Workshop on Software Defined Networking (EWSDN), Budapest, Hungary, September 2014

Technical Reports

    Service Chain and Virtual Network Embeddings: Approximations using Randomized Rounding
  Matthias Rost and Stefan Schmid
  arxiv:1604.02180 [cs.NI], April 2016         bibtex
   
    An Approximation Algorithm for Path Computation and Function Placement in SDNs
  Guy Even, Matthias Rost and Stefan Schmid
  arxiv:1603.09158 [cs.NI], March 2016         bibtex
   
    KuVS Prize for the Best Master Thesis 2014: `Optimal Virtualized In-Network Processing with Applications to Aggregation and Multicast'
  Matthias Rost, Stefan Schmid, Andreas Bley and Anja Feldmann
  2015 International Conference on Networked Systems (NetSys), Cottbus, Germany, March 2015
  Summary of my Master Thesis (made available on the USB Proceedings of NetSys 2015)         bibtex         slides (pdf)         NetSys homepage
   
    Investigating the Potential of the Inter-IXP Multigraph for the Provisioning of Guaranteed End-to-End Services
  Vasileios Kotronis, Rowan Klöti, Matthias Rost, Panagiotis Georgopoulos, Bernhard Ager, Stefan Schmid, Xenofontas Dimitropoulos
  ETH Zurich, Laboratory TIK, February 2015.
  pdf         bibtex
   
    The Constrained Virtual Steiner Arborescence Problem: Formal Definition, Single-Commodity Integer Programming Formulation and Computational Evaluation
  Matthias Rost, Stefan Schmid
  arXiv:1310.0346 [cs.NI], October 2013         bibtex

Invited Talks at Conferences

    A Compact MIP for Aggregation and Multicast Trees under Flexible Routing and Function Placement
  Matthias Rost, Stefan Schmid
  22nd International Symposium on Mathematical Programming (ISMP), Pittsburgh, Pennsylvania, USA, July 2015
  Cluster: Combinatorial Optimization, Session: Routing and Facility Location
  slides (pdf)         Session Information
   
    KuVS Prize for the Best Master Thesis 2014: `Optimal Virtualized In-Network Processing with Applications to Aggregation and Multicast'
  Matthias Rost, Stefan Schmid, Andreas Bley and Anja Feldmann
  2015 International Conference on Networked Systems (NetSys), Cottbus, Germany, March 2015
  Summary of my Master Thesis (made available on the USB Proceedings of NetSys 2015)         bibtex         slides (pdf)         NetSys homepage

Master Thesis

    Optimal Virtualized In-Network Processing with Applications to Aggregation and Multicast
Advisors: Stefan Schmid, Andreas Bley, Anja Feldmann
Technische Universität Berlin, January 2014
pdf         slides (pdf)         data & solver (tar.gz, 493MB, 3,7 GB unpacked)         bibtex         TU Berlin News (German)
   
    Awarded with the Best Master Thesis Prize 2014 by the  Communication and Distributed Systems Group Special Interest Group (KuVS)

Unpublished

    The Informal Guide to the Virtual Network Embedding MIP Creator (VNetEMC)
pdf         (source of the VNetEMC can be made available)

Other Talks (Conference talks see above)

    FG INET Retreat, September 2016
Integer Linear Programming Primer
slides (pdf)         example data (tar.gz, 2.3 KB)
 
    Hosted by Tamaś Lukvoszki, Eötvös Loránd University, Budapest, February 2016
Beyond the Stars: Revisiting Virtual Cluster Embeddings
slides (pdf)
 
    Hosted by Petr Kuznetsov, Télécom ParisTech, September 2015
Beyond the Stars: Revisiting Virtual Cluster Embeddings
slides (pdf)
 
    NetAlgs seminar (hosted by Guy Even, organized by Boaz Patt-Shamir), Tel Aviv University, March 2015
VirtuCast
slides (pdf)
 
    Lehrstuhl für Kommunikationsnetze (hosted by Wolfgang Kellerer), TU München, August 2014
VirtuCast / Temporal Virtual Network Embedding Problem
slides (pdf)
 
    International Computer Science Institute (hosted by Robin Sommer), UC Berkeley, May 2014
VirtuCast / Temporal Virtual Network Embedding Problem
slides (pdf)
 
    Arizona State University (hosted by Andrea Richa), May 2014
VirtuCast / Temporal Virtual Network Embedding Problem
slides (pdf)
 
    ViNO project meeting (hosted by Stefan Schmid), TU Berlin, February 2014
VNetEMC / VirtuCast / Temporal Virtual Network Embedding Problem
slides (pdf)
 
    BigFoot project meeting , EURECOM (hosted by Pietro Michiardi), December 2013
VirtuCast
slides (pdf)

Bio

Work

since 01/2014 Research Assistant at FG INET , Technische Universität Berlin
11/2011 - 12/2013 Student Research Assistant at FG INET , Technische Universität Berlin
04/2009 - 09/2010 Tutor at the computer science department of Freie Universität Berlin
08/2007 - 02/2009 Student Software Developer at IVU Traffic Technologies AG (C/C++, PL/SQL)

Teaching (Research Assistant)

10/2015 - 03/2016 Introduction to Programming (Einführung in die Prorgammierung) at Technische Universität Berlin
10/2014 - 03/2015 Introduction to Programming (Einführung in die Prorgammierung) at Technische Universität Berlin
04/2014 - 09/2014 Internet Measurement Seminar at Technische Universität Berlin

Teaching (Tutor)

9/2011 Computer Architecture (for pupils) at Freie Universität Berlin Berlin
9/2010 Computer Architecture (for pupils) at Freie Universität Berlin Berlin
04/2010 - 09/2010 Non-sequential Programming at Freie Universität Berlin Berlin
10/2009 - 03/2010 Operating Systems and Computer Networks at Freie Universität Berlin Berlin
04/2009 - 09/2009 Computer Architecture at Freie Universität Berlin Berlin

Education

04/2010 - 01/2014 Computer Science (M.Sc.) at Technische Universität Berlin
Thesis: 'Optimal Virtualized In-Network Processing with Applications to Aggregation and Multicast'
10/2010 - 09/2013 Mathematics (B.Sc.) at Freie Universität Berlin
10/2009 - 09/2010 Computer Science (M.Sc.) at Freie Universität Berlin
10/2006 - 09/2009 Computer Science (B.Sc.) at Freie Universität Berlin
Thesis: 'Modellierung und Lösung von Evakuierungsproblemen mittels Netzwerkflüssen'
             ('Modeling and Solving Evacuation Problems using Network Flows')

Awards & Grants

March 2016 BMBF grant as part of the   Software Campus Program
March 2015 Best Master Thesis Prize 2014 by the   Communication and Distributed Systems Special Interest Group (KuVS) (a part of the   German Informatics Society and the   Information Technology Society)
10/2010-3/2013 Scholarship from the German National Academic Foundation (Studienstiftung des deutschen Volkes)
June 2006 DPG-Buchpreis 2006 from the German Physical Society (Deutsche Physikalische Gesellschaft) in recognition for outstanding achievements in physics

Contact

Address
Matthias Rost
MAR 4-4
Room 4.031
Marchstr. 23
10587 Berlin
 
Office Hours by appointment
 
E-Mail mrost -at- inet.tu-berlin.de
">info