UW-Madison Logo

The ADvanced Systems Laboratory (ADSL)

Gray-box Systems

One of our earliest ideas was that of building gray-box systems. The driving force behind this idea is that in some scenarios it is challenging to change an existing system to have the exact functionality desired; surprisingly, however, in many cases it is still possible to realize the desired functionality without any change to said system, through a combination of measurement of the system plus knowledge (perhaps imperfect) of how the system operates. This ``gray box'' knowledge thus formed the center of the following line of research:
  • Information and Control in Gray-Box Systems (SOSP '01). Our original paper on the idea, and also the first SOSP paper from our group. We describe the fundamental approach, and highlight how it can be applied with three detailed case studies, substantially improving performance of both microbenchmarks and real applications.
  • Exploiting Gray-Box Knowledge of Buffer-Cache Contents (USENIX '02). We delve deeper into the idea that the page-replacement algorithms of an operating system can be understood through careful measurement, and build a novel tool (Dust) that fingerprints existing operating systems and determines how they perform replacement. We build a ``cache aware'' web server, improving performance significantly through gray-box replacement knowledge.
  • Controlling your PLACE in the File System with Gray-box Techniques (USENIX '03). We build a layer on top of a file system that enables applications to exert control over which files are placed near one another, and which ones far apart. The paper then shows how to utilize this control to improve web-server performance as well as build an improved file-system benchmarking tool.
  • Roobust, Portable I/O Scheduling with the Disk Mimic (USENIX'03). We show how detailed measurement of a storage device can be used to build an entirely empirical model of its behavior, which can then be used to develop a measurement-driven disk scheduler. Our I/O scheduler outperforms classical heuristic schedulers (such as C-LOOK or SSTF) substantially.
  • Transforming Policies into Mechanisms with Infokernel (SOSP '03) We take the gray-box approach to an extreme, developing a new kernel (the infokernel) which exposes more detailed information to applications, thus enabling more nuanced control of system behavior. For example, by showing applications which pages in memory are likely to soon be replaced and which are firmly entrenched in memory, applications can adjust their behavior to better exploit in-memory pages while also exerting influence over page-replacement decisions. Four cases studies (in memory management, file placement, I/O scheduling, and networking) show considerable performance improvements can be realized as a result.
  • Deploying Safe User-Level Network Services with icTCP (OSDI '04). One last pure gray-box paper focuses just on the networking stack. By exposing certain key pieces of TCP state information, and providing (safely) control over a few key variables, we show how many TCP extensions that previously required kernel modification can be safely and efficiently realized at kernel level.