Martin Karsten - Research Overview

I am generally interested in finding the simplest possible approaches to building software systems. Complexity is anathema to robustness, security, analyzability, and ultimately scalability and performance. The goal of my research is to 1) find basic patterns for the design of software and system infrastructure, and 2) to redesign and rebuild existing systems using a modular composition of basic building blocks. I expect that this approach leads to a better charting of the infrastructure-software design space and results in systems that are easier to analyze and verify and ultimately, systems that just work better (faster, more efficient, more reliable, etc.)

System Software

The overall focus of my work in this area is on system-level infrastructure software, in particular runtime systems. Examples of runtime systems are operating system kernels, virtual machine hypervisors, user-level threading systems, programming language runtimes, etc. The high-level research objectives are the following:

• Simplicity - System-level software is often cumbersome and difficult to comprehend. The presumed reasons for this are twofold: a) Production-level software is bound by compatibility requirements. b) Performance improvements are often realized by implementing dedicated software artifacts with limited scope. The resulting complexity negatively interacts with a).
• Performance - Performance ultimately requires efficiency and scalability. Efficiency can be translated into performance gains or energy savings. Scalability is paramount to utilize the continuing increase of the number of available processor cores. A particular challenge is improving performance without sacrificing simplicity.
• Structure - A typical current software stack has many incarnations of similar functionality in various layers, but the structural commonalities and differences between different layers are not well understood and documented. If this replication is truly necessary, is it possible to re-use functionality by sharing code/mechanisms used with different policies at different layers?

Publications

• technology: Contributions to the Linux Kernel
• software: libfibre - user-level threading runtime
• software: KOS - an experimental operating system kernel
• Towards Dynamic Green-Sizing for Database Servers (6th ADMS Workshop in conjunction with VLDB 2015)
• Towards Adaptive Resource Allocation for Database Workloads (6th ADMS Workshop in conjunction with VLDB 2015)
• Work-Stealing, Locality-Aware Actor Scheduling (IEEE IPDPS 2018)
• Workload-Aware CPU Performance Scaling for Transactional Database Systems (ACM SIGMOD 2018)
• User-level Threading: Have Your Cake and Eat It Too (ACM SIGMETRICS 2020)
• Kernel vs. User-Level Networking: Don't Throw Out the Stack with the Interrupts (ACM SIGMETRICS 2024)

Network Architecture

The basic goal is to find a basic formalism (a type of language) to precisely describe essential network functionality, such as forwarding, routing, and naming/discovery. Given that even basic concepts such as name and address lack a precise and commonly agreed definition, it is high time that networking is put on a theoretically sound footing. Ideally, such a language would also permit code generation and verification and thereby ease the deployment of new communication protocols and services.

Publications

• On the Feasibility of Core-Rooted Path Addressing (IEEE/IFIP NOMS 2016)
• An Axiomatic Basis for Communication (ACM Sigcomm 2007, ACM HotNets V 2006)

Network Service

The quality of the network service determines what end-to-end transport services can be offered to applications. In past work, I have studied edge-based load control, fine-grained scheduling with low overhead, and innovative packet scheduling approaches. I keep an interest in the area, in particular buffer management and feedback-based load control.

Projects

• Non-Intrusive Delay Differentiation

Other Publications

• Approximation of Generalized Processor Sharing with Interleaved Stratified Timer Wheels (IEEE/ACM ToN 2010)
• SI-WF²Q: WF²Q Approximation with Small Constant Execution Overhead (IEEE Infocom 2006)
• Packet Marking for Integrated Load Control (IEEE/IFIP IM 2005)

Network Software

I have designed, built, and evaluated system-level network software.

Publications

• Group Unicast for the Real World (ACM NOSSDAV 2008)
• Modelling and Improving Group Communication in Server Operating Systems (MASCOTS 2006)
• Collected Experience from Implementing RSVP (IEEE/ACM ToN 2006)
• Efficient Operating System Support for Group Unicast (ACM NOSSDAV 2005)

Other Research

• On the Relevance of Adversarial Queueing Theory in Practice (2014)
• Simulation of Adversarial Scenarios in OMNeT++ -- Putting Adversarial Queueing Theory from Its Head to Feet (2013)
• The Efficacy of Centralized Flow Rate Control in 802.11-based Wireless Mesh Networks (2013)
• Towards Practical Communication in Byzantine-Resistant DHTs (2013)
• Mechanisms for Centralized Flow Rate Control in 802.11-based Wireless Mesh Networks (2012)
• Dynamic Service Placement in Shared Service Hosting Infrastructures (2010)
• Practical Robust Communication in DHTs Tolerating a Byzantine Adversary (2010)
• A Heuristic for Fair Correlation-Aware Resource Placement (2009)
• Multipath Load Balancing in Multi-hop Wireless Networks (2005)
• A Modular Approach to Mobile QoS Signaling Motivation, Design & Implementation (2004)
• Pre-Waterloo Research
  

Other Technology Transfer

• My RSVP performance evaluation has been used for RFC 4094 - Analysis of Existing Quality-of-Service Signaling Protocols.
• My work on edge-based load control has been used for RFC 5559 - Pre-Congestion Notification (PCN) Architecture.
• My open source RSVP implementation has been used in a number of academic and industrial research projects. This includes projects related to IP QoS, billing, and GMPLS signalling.
• I have worked as a technical consultant in the telecommunications and the financial industry.

last updated Oct 24, 2024 - Martin Karsten