Products

I worked with Yoram Bernet, Ofer Bar, and Shreedhar Madhavapeddi on the architecture, design, and implementation of the Generic Packet Classifier in the Windows 2000 network stack. The GPC is a driver that provides packet classification services to kernel- or user-level network components.

A major component of the GPC is the Rhizome data structure, which stores patterns containing wildcards and which enables rapid (log-time) search for a pattern most-specifically matching a given key.

We have filed twelve patent applications on aspects of the GPC, ten of which have been issued so far: The GPC architecture, a generalization thereof, the Rhizome data structure, the incorporation of the Rhizome into the GPC, a specialized hash table, a specialized handle administrator with optimizations for multithreading, a database record allocator, a hysteresis system, and a handle-recycling system.

Windows 2000 Packet Scheduler

I worked with Yoram Bernet and Ofer Bar, along with Charlie Tai, Carol Bell, and Raj Yavatkar from Intel Corporation, on the architecture of the Packet Scheduler in the Windows 2000 network stack. The Packet Scheduler is a driver that enforces Quality-of-Service parameters for regulated network flows. We were issued a patent on this technology.

Architecturally, the Packet Scheduler is divided into three sub-components: The conformer, which determines the soonest time each packet can be sent without violating the specified traffic parameters; the shaper, which conditionally holds packets until their conformance time arrives; and the sequencer, which orders packets from multiple flows for transmission on the network.

Windows 2000 Single Instance Store (SIS)

I worked with Bill Bolosky, Scott Corbin, David Goebel, and Cedric Krumbein on the Single Instance Store component of Windows 2000. SIS is a file-system component that allows NT file systems to coalesce multiple identical files into a single file instance, while maintaining the names and semantics of separate files.

There are two sub-components of SIS: a file-system filter driver and a system service called the Groveler. The Groveler scans through files on a disk volume, looks for files with identical contents, and coalesces identical files by calling the SIS filter. To prevent interference with foreground applications, the Groveler uses a technique called progress-based regulation, which we described in a paper at the 17th SOSP. We have filed several patent applications on SIS, one of which has issued.

John Douceur's home page.