Router Plugins: A Softward Architecture for Next Generation Routers

D. Decasper (ETH Zurich), Zubin Dittia (WUStL), Guru Parulker (WUStL), Bernhard Plattner (ETH Zurich), 1998

Summary. The authors propose a software framework for Extended Integrated Services Routers (EISR) that enables plugins, modules that implement some service such as packet scheduling, security, or IP options, to be dynamically loaded into a router and attached to currently flowing flows via very fast packet classifier algorithm. When compared to NetBSD implementation, adds only about 8% relative overhead.

More detail.

EISR: offers the following 4addt'l components:
  1. packet scheduler
  2. packet classifier
  3. security mechanisms
  4. QoS-based level 4 routing
These components have a relatively "fluid" implementation relative to the more "stable core" responsible for interacting with the network hardware and demultiplexing packets. Different implementations of the above components may need to coexist. The proposed framework addresses the requirements of these components: ease-of-replacement and co-existence.

Four specific goals of architecture:

  1. Modularity (implementation of specific algs come in the form of plugins.
  2. Extensibility (plugins can be dynamically loaded at runtime)
  3. Flexibility (plugins can be bound to specific flows; plugins can take the form of software modules, drivers or custom hardware)
  4. Performance (no data copying or context switching, no addt'l interrupt processing)
Target applications.

Why flows?: "Because the deployment of multimedia data sources and applications (e.g. real-time audio/video) will produce longer lived packet streams with more packets per session than is common in today's environment, an integrated services router arch should support the notion of flows and build upon it." Hmmm... wonder how much traffic this constitutes now? Wonder at what rate this is growing?

Control Path. Plugins implement a standard interface to allow for their creation, destruction, creating filters and binding flows. The user level Plugin Manager keeps track of plug in types. Upon creation, plugins register callbacks to the Plugin Control Unit which uses that callback to forward messages to the plugin instances. When packets come in, the Association Identification Unit determine which plugin is associated with the flow. User level RSVP/SSP route daemons are present.

Data Path. As packets proceed along the data path, they pass through gates - a point in the IP core where the flow of execution branches to an instance of a plugin. If the packet is the first in the flow, the gate will find the plugin instance associated with this flow by calling the AIU. The AIU will lookup the flow in the flow table. If no entry exists, the AIU performs a retrieves a Flow Index (FIX) from gate's filter table and then, using the FIX, retrieves the plugin from the flow table. The authors claim that current filters aren't adequate for a number of reasons:

The filter table is implemented as a DAG. Longest-prefix match is used to match the dest address, then src address, Matching function can be different at each DAG tree level depending upon the field type. "Inter-DAG" pointers optimize filter lookups for the same packet at different gates. The authors note that if many ambiquous filters must be resolved, the memory requirements can be "excessive" but suggest other algorithms for that scenario. Flow Table. At this level, because there are no wildcard fields in the flow typle, hashing can be used to implement lookups efficiently. Highly optimized. Performance. Worst-case flow lookup with 200% overload required 1.7us which the authors say is "very reasonable" (but no comparitive number is provided). Packet classification (filter table lookup) accomplished in 1.4us. Both the table lookup numbers are derived analytically. Overall packet processing overhead was increased by 7.89%.

Questions