Router Plugins A Software Architecture for Next Generation Routers Dan Decasper’, Zubin Dittia2, Guru Parulkar2, Bernhard Plattner’ [danlplattner] @ tik.ee.ethz.ch, [zubinlguru] @ arl.wustl.edu I Computer Eng ineering and Networks Laboratory, ETH Zurich, Switzerland Phone: +41-l -632 7019 Fax: +41-l -632 1035 *Applied Research Laboratory, Washington University, St. Louis, USA Phone: +l -314-935 4586 Fax: +l -314-935 7302 1. ABSTRACT Present day routers typically employ monolithic operating systems which are not easily upgradahle and extensible. With the rapid rate of protocol development it is becoming increasingly important to dynamically upgrade router software in an incre- mental fashion. We have designed and implemented a high performance, modular, extended integrated services router software architecture in the NetBSD operating system kernel. This architecture allows code modules, called plugins, to be dynamically added and configured at run time. One of the novel features of our design is the ability to bind different plugins to individual flows; this allows for distinct plugin implementations to seamlessly coexist in the same runtime environment. High performance is achieved through a carefully designed modular architecture; an innovative packet classification algorithm that is both powerful and highly efficient; and by caching that exploits the flow-like character- istics of Internet traffic. Compared to a monolithic best-effort kernel, our implementation requires an average increase in packet processing overhead of only 8 % , or 500 cycles/2.lms per packet when run- ning on a P61233. 1.1 Keywords High performance integrated services routing, modular router architecture, router plugins 2. INTRODUCTION New network protocols and extensions to existing protocols are being deployed on the Internet. New functionality is being added to modern IP routers at an increasingly rapid pace. In the past, the main task of a router was to simply forward packets based on a destination address lookup. Modern routers, however, incorporate several new services: Parmlsswn tc make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies we not made or distributed for profit or commsrciel adven- tege and that ccpws bear this notice and the full citatocn on the first page. To copy otherwwe. tc republish. tc pest on servers or to redwtribute to ksts. requ~ree prior specihc permission and/or a fee. SIGCOMM ‘98 Vsncouvar. B.C. 0 ,998 ACM 1~58113.003.1/98/~8...S5.00 Figure 1. : Best Effort vs Extended Integrated Services Router (EISR) l Integrated/differentiated Services l Enhanced routing functionality (level 3 and level 4 rout- ing and switching, QoS routing, multicast) l Security algorithms (e.g. to implement virtual private networks (VPN)) l Enhancements to existing protocols (e.g. Random Early Detection (RED)) l New core protocols (e.g. 1~~6 [S]) Figure 1 contrasts the software architecture of our proposed Extended Integrated Services Router (EISR) with that of a conventional best-effort router. A typical EISR kernel features the following important additional components: a packet scheduler, a packet classifier, security mechanisms, and QoS-based routingLevel 4 switching. Various algorithms and implementations of each component offer specific advantages in terms of performance, feature sets, and cost. Most of these algorithms undergo a constant evolution and are replaced and upgraded frequently. Such networking subsystem components are characterized by a relatively “fluid” implementation, and should be distinguished from the small part of the network subsystem code that remains relatively stable. The stable part (called the core) is mainly responsible for interacting with the network hardware and for demultiplexing packets to specific modules. Different implementations of the EISR components outside of the core often need to coexist. For example, we might want to use one kind of packet scheduling on one interface, and a different kind on another. In this paper, we propose a software architecture and present an implementation which addresses these requirements. The specific goals of our framework are: l Modularity: Implementation of specific algorithms come in the form of modules called plugins’. 229
`
`Juniper Ex. 1014-p. 1
`Juniper v Implicit
`
`

`

`Extensibility: New plugins can be dynamically loaded at run time. Flexibility: Instances of plugins can be created, config- ured, and bound to specific jlows. Plugins can be all- software modules, or they can be software drivers for specialized custom hardware. Performance: The system should provide for a very efficient data path, with no data copying, no context switching, and no additional interrupt processing. The overhead of modularity should not seriously impact per- formance. Our proposed framework has been implemented in the NetBsn UNIX kernel. This platform was selected because of its portability (all major hardware platforms are supported), efficiency, and extensive documentation. In addition, we found state-of-the-art implementations on this platform for 1~~6 [13] and packet schedulers [27, 51 that could be integrated into our framework. We envision several applications for our framework. First, our architecture fits very well into the operating system of small and mid-sized routers. It is particularly well suited to the implementation of modern edge routers that are responsible for doing flow classification, and for enforcing the configured profiles of differential service flows. This kind of enforcement can be done either on a per-application flow basis, or on a generalized class-based approach (e.g. CBQ [ll]). Our implementation supports both models efficiently. Our framework is also very well suited to Application Layer Gateways (ALGS), and to security devices like Firewalls. In both situations, it is very important to be able to quickly and efficiently classify packets into flows, and to apply different policies to different flows: these are both things that our architecture excels at doing. Yet another application of our framework is for network management applications, which typically need to monitor transit traffic at routers in the network, and to gather and report various statistics thereof. For such applications, it is important to be able to quickly and easily change the kinds of statistics being collected, and to do this without incurring significant overhead on the data path. Finally, while our proposed framework is very useful in real-world implementations, its modularity and extensibility also make it an invaluable tool for researchers. We plan to release all of our code in the public domain and we will attempt to incorporate several core portions into the standard NetBSD distribution tree. A note on our use of the word ‘plugin’ (instead of ‘module’) is in order. In the web browser world, a plugin is a software module that is dynami- cally linked wtth the browser and is responsible for processing certain types of application streams (or flows). In a similar fashion, our router plugins are kernel software modules that are dynamically loaded into the kernel and are responsible for performing certain specific functions on specified network flows. The main contributions of our work are: l An innovative, modular, extensible, and flexible EISK networking subsystem architecture and implementation that introduces only 8% more overhead than a best-effort kernel. l A very fast packet classifier algorithm which provides highly competitive upper bounds for classification times. With a very large number of filters (in the order of 50000), it classifies 1~~6 packets in 24 memory accesses, and is much faster for smaller numbers of filters. l Implementations of plugins for two state-of-the-art packet schedulers: Deficit Round Robin (DRR, [23]) for fair queuing, and the Hierarchical Fair Service Curves (H-FSC, [27]) scheduler for class-based packet schedul- ing; Implementation of plugins for IP security [2]. There are a few commercial attempts that we are aware of which follow similar lines. The latest versions of Cisco’s Internet OS (IOS, [6]) claims to fulfill some of the requirements, but since it’s a commercial operating system, there is no easy access for the research community and these claims are not verifiable. Microsoft’s Routing and Remote Access Service for Windows NT (RRAS, previously referred to as “Steelhead” [ 18, 191) is an attempt to implement router functionality under Windows NT. RRAS exports an API and allows third party modules to implement routing protocols like OSPF and SNMP agents in user space. The API does not provide an interface to the routing and forwarding engines, and the platform offers no integrated services components. A few research projects attempt to achieve some of the goals mentioned above [12, 20, 211. Most of them are focused on the implementation of modular end-system networking subsystems instead of routing architectures. Scout from the University of Arizona is a particularly interesting project based on the x-kernel that implements an operating system targeted at network appliances (including routers). It comes with router components implementing simple QoS support. Since the whole operating system is implemented from scratch, most of the provided functionality is over- simplified and does not provide the large feature set that is found in mature implementations. We discuss these related approaches in more detail in [7]. In Section 3, we describe our architecture and explain how it achieves modularity, extensibility, and flexibility while maintaining high-performance. In Section 4, we describe the implementation of a module called the Plugin Control Unit (PCU), which is responsible for all control path interactions with plugins. Section 5 outlines the implementation of the Association Identification Unit (AIU), which is used by almost all other components in our design. The AIU implements an innovative algorithm for packet classification which efficiently maps packets to code modules (plugins). In Section 6, we elaborate on example plugins (packet schedulers) which we implemented or adapted for our environment. Section 7 presents performance results from our implementation, and Section 8 summarizes our ideas. 230
`
`Juniper Ex. 1014-p. 2
`Juniper v Implicit
`
`

`

`3. OVERALL ARCHITECTURE The primary goal of our proposed architecture was to build a modular and extensible networking subsystem that supported the concept of flows, and the ability to select implementations of components based upon flows (in addition to simple static configurations). 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 architecture should support the notion of flows and build upon it. In particular, the locality properties of flows should be effectively exploited to provide for a highly efficient data path. Our plugin framework features: l Dynamic loading and unloading of plugins at run time into the networking subsystem. Plugins are code mod- ules which implement a specific EISR functionality (e.g. packet scheduling). NetBSD offers a simple yet powerful mechanism which allows modules to be loaded into the kernel which is used to load our plugins into the kernel. Once a plugin is loaded, it is no different from any other kernel code. What is required for our system is a compo- nent which glues the individual plugins to the network- ing subsystem, and which provides a control-path interface used by other kernel components (possibly also other plugins) and user space daemons to talk to the plugin. In our system, this component is called the Plugin Control Unit (PCU). The PCU hides some of the implementation specific details from the individual plu- gins and allows them to access the system in a simple yet flexible fashion. l Creation of individual instances of plugins for maximal flexibility. An instance is a specific run-time configura- tion of an individual plugin. It is often very desirable to have multiple instances of one and the same plugin con- currently in the kernel. For example, consider packet scheduling. A packet scheduler can work with different configurations on different network interfaces. State-of- the-art packet schedulers are usually hierarchical, with possibly different modules working on different levels of the scheduling hierarchy. Among the nodes of the same level, modules are specifically configured, which means that they coexist in our framework as plugin instances. In order to provide a simple and unified interface for the allocation of multiple instances of one and the same plugin, the plugins must respond to a set of standardized messages. By standardizing this message set and imple- menting it in all plugins, we guarantee interoperability among different plugins and provide a simple configura- tion interface. l Efficient mapping of individual data packets to flows, and the ability to bind flows to plugin instances. Sets of flows are specified using jilters. For example, a filter might match all TCP traffic from the network 129.0.0.0 to the host 192.94.233.10. Filters can also match individ- ual end-to-end application flows. Filters are specified as six-tuples: <source address, destination address, protocol, source port, destination port, incoming interface> Any of the fields in the six tuple may be wildcarded. Additionally, for network addresses, a prefix mask may be used to partially wildcard the corresponding field. For instance, for the above example, the filter specification would read: <129.*.*.*, 192.94.233.10, TCe *, *, *> Clearly, the filter for an end-to-end application flow would have all fields (except perhaps the incoming interface) fully specified. We will see later in this section that a packet matching a particular filter will be passed to the plugin instance that has been bound to that filter. This will be shown to happen whenever the packet reaches a “gate” in the IP stack; a gate can be thought of as the entry point for a plugin. l Overall high performance. High performance is guaran- teed only in part through a fully kernel space implemen- tation which prevents costly context switches. We identified two other critical properties which, when com- bined, guarantee high performance even in a highly modular environment: the flow-like nature of most inter- net traffic, and the ability to classify packets into flows quickly and efficiently. As we show below, the filter lookup to determine the right plugin instance to which a packet should be passed happens only for the first packet of a burst. Subsequent packets get this information from a fast flow cache which temporarily stores the informa- tion gathered by processing the first packet. The filter lookup itself is efficiently implemented using a Directed Acyclic Graph (DAG). We elaborate on these techniques later in this section, and also in section 5. l Easy integration with custom hardware for high perfor- mance processing of specialized tasks. This is enabled by plugins which are software drivers for hardware that implements the desired functionality. For example, a plugin could control hardware engines for tasks such as packet classification or encryption. In order to describe our framework, we first look at the different components and how they interact in the control path. In the Section 3.2, we will look at the data path, and how individual packets are processed by our architecture. 3.1 The Control Path Figure 2 shows the architecture of our system and the control communication between different components. A description of the different components follows: . IPv4/IPv6 core: The IPv4/1pv6 core consists of a stream-lined IPV~/IPV~ implementation which contains the (few) components required for packet processing which do not come in the form of dynamically loadable modules. These are mainly functions that interact with network devices. The core is also responsible for demul- tiplexing individual packets to plugins as we will show in the next section. There are no plugin related control path interactions with the IP core. 231
`
`Juniper Ex. 1014-p. 3
`Juniper v Implicit
`
`

`

`involves the following steps: Figure 2. : System Architecture and Control Path l Plugins: Figure 2 shows four different types of plugins - plugins implementing IPVG options, plugins for packet scheduling, plugins to calculate the best-matching prefix (BMP, used for packet classification and routing), and plugins for IP security. Other plugin types are also possi- ble: e.g., a routing plugin, a statistics gathering plugin for network management applications, a plugin for con- gestion control (RED), a plugin monitoring TCP conges- tion backoff behaviour, a tirewall plugin. Note that all plugins come in the form of dynamically loadable kernel l Plugin Control Unit (PCU): The PCXJ manages plugins, and is responsible for forwarding messages to individual plugins from other kernel components, as well as from user space programs (using library calls). l Association Identification Unit: The Association Iden- tification Unit (AIU) implements a packet classifier and builds the glue between the flows and plugin instances. The operation of the AKJ will become clear when we describe the data path in the next subsection. l Plugin Manager: The Plugin Manager is a user space utility used to configure the system. It is a simple appli- cation which takes arguments from the command line and translates them into calls to the user-space Router Pfugin Library which we provide with our system. This library implements the function calls needed to config- ure all kernel level components. In most cases, the plugin manager is invoked from a configuration script during system initialization, but it can also be used to manually issue commands to various plugins. We show an example of how the Plugin Manager is used in Section 6. l Daemons: The RSVP [31], SSP [I] (a simplified version of RSVP), and route daemon are linked against the Router Plugin Library to perform their respective tasks. We implemented an SSP daemon for our system, and are cur- rently in the process of porting an RSVP implementation. After a reboot, the system has to be configured before it is ready to receive and forward data packets. Configuration involves the selection of a set of plugins. Since a selection does not necessarily apply to all packets traversing the router, a definition of the set of packets which should be processed by each individual plugin instance is required. This configuration can be done either by a system administrator, or by executing a script. Configuration Loading a plugin: Using the modload command, which is part of the NetBSD distribution, plugins are loaded into the kernel. On loading, they register themselves with the PCU by providing a callback function. This function is used to send messages to the plugin. There are messages for creating and freeing instances of the plugin and for binding plugin instances to flows. Also, plugin develop- ers can define an arbitrary number of plugin specific messages. Once the callback function for a plugin has been registered, the PCU can forward these configuration messages to the plugin. Creating an instance of a plugin: Using the Plugin Manager application, configuration messages can be sent to specified plugins. Typically, these messages ask the plugin to create an instance of itself. In case of a packet scheduling plugin for example, the configuration information could include the network interface the plugin should work on. Creating filters: Once a plugin has been configured and an instance has been created, it is ready to be used. What has to be defined next is the set of datagrams which should be passed to the instance for processing. This is done by binding one or more flows to the plugin instance. To specify the set of flows that are supposed to be handled by a particular plugin instance, the Plugin Manager or one of the user space daemons (RSVP or SSP) can create filters through calls to the AIU. Recall (from earlier in this section) that a filter is a specification for the set of flows it matches. Binding flows to instances: Next, the binding between filters and plugin instances must be established. Each fil- ter in the AIU is associated with a pointer to a plugin instance; this pointer is set by making another call to the AIU to do the binding. Now the system is ready to process data packets. We will show in the next subsection how data packets are matched against filters and how they get passed to the appropriate instances. 3.2 The Data Path Data packets in our system are passed to instances of plugins which implement the specific functions for processing the packets. Since data path mechanisms are applied to every single packet, it is very important to optimize their performance. Given a packet, our architecture should be able to quickly and efficiently discover the set of instances that will act on the packet. The data path interactions are shown in Figure 3.Before we can explain the sequence of actions, we have to introduce the notion of a gate. A gate is a point in the IP core where the flow of execution branches off to an instance of a plugin. From an implementation point of view, gates are simple macros which encapsulate function calls to the AIU that will return 232
`
`Juniper Ex. 1014-p. 4
`Juniper v Implicit
`
`

`

`Figure 3. : System Architecture and Data Path the correct plugin instance which is to be used for processing the packet. In many cases, these macros can avoid a function call to the AIU altogether, thereby permitting a more efficient implementation. Gates are placed wherever interactions with plugins need to take place. For example, sometimes after a packet is received by the hardware, IP security processing has to be done if the system is configured as entry point into a virtual private network. In our system, IP security functions are modularized and come in the form of plugins. A gate is inserted into the IP core code in place of the traditional call to the kernel function responsible for 1~~6 security processing. In our current implementation, we use gates for 1~~6 option processing, IP security, packet scheduling, and for the packet filter’s best-matching prefix algorithm. To follow the various data path interactions, it is important to get a basic understanding of the operation of the AIU. The AIU is responsible for maintaining the binding between flows and plugin instances. It makes use of a special data structure called a flow table to cache flows. Flow tables allow for very fast lookup times for arriving packets that belong to cached flows. In the AIU, all flows start out being uncached (i.e., they do not have an entry in the flow table). If an incoming packet belongs to an uncached flow, its lookup in the flow table data structure will fail (i.e., there is a cache miss). In this case, the packet needs to be looked up in a different data structure that we call a filter table. Filter tables store the bindings between filters and plugins for each gate. The filter table lookup algorithm finds the most specific matching filter (described later) that has been installed in the table, and returns the corresponding plugin instance. Usually, filter table lookups are much slower than flow table lookups. An entry for a flow in the flow table serves as a fast cache for future lookups of packets belonging to that flow. Each flow table entry stores pointers to the appropriate plugins for all gates that can be encountered by packets belonging to the corresponding flow. The processing of the first packet of a new flow with II gates involves II filter table lookups to create a single entry in the flow table for the new flow. If a cached flow remains idle (i.e., no new packets are received) for an extended period, its cached entry in the flow table data structure may be removed (or replaced by a different flow). In this case, if the flow becomes active again, the first packet that is received would again result in a cache miss, which would again cause a new cache entry to be created in the flow table so that subsequent packets can benefit from faster lookup times. Section 5.1 describes a very fast filter table lookup implementation based on directed acyclic graphs (DAB). Section 5.2 describes our flow table implementation, which is based on hashing. As an example, consider the steps involved in processing an IPV~ packet (see numbers l-6 in Figure 3). Uncached flow processing involves the following sequence of events and actions: 0. Packet arrival: When a packet arrives, it gets passed to the IP core by the network hardware. As it makes its way through the core, it may encounter multiple gates. 1. Encountering a gate: Assume that the packet has reached the gate where IP security processing will be handled. The task of this gate is to find the plugin instance which is responsible for applying security pro- cessing (authentication and/or encryption) to the packet. 2. Discovering the right instance: The gate makes a call to the AIU. The parameters of the call are a pointer to the packet and an identification of the gate issuing the call. In our case, we would identify the IP security gate as the caller. 3. Packet classification: The AIU first does a lookup in the flow table, and finds that there is no cached entry avail- able for the flow. Consequently, it performs a lookup in the filter table corresponding to the IP security gate. The resulting plugin instance pointer is returned to the call- ing gate (“SEC2” in Figure 3). Note that since this packet classification step performed by the AIU is the most expensive step in the whole cycle, an efficient packet classification scheme and implementation is important. 4. Caching of the instance pointer: Before the AIU returns the instance pointer to the gate, it stores the pointer in the flow table. Note that entries in the flow table are identified by the same six tuple used to specify filters, but without masks or wildcards (all fields have fully specified values). In other words, a flow table entry unambiguously identifies a particular flow. In our example, the pointer to the SEC2 plugin is stored in the row of the flow table which corresponds to our packet’s flow. 5. Returning the instance pointer: The instance pointer found is returned to the gate. 6. Calling the instance: The gate calls the plugin instance, passing the packet as an argument. 7. Repeating the cycle: When the call returns, the IP stack continues processing the packet, until it encounters another gate, in which case the same cycle repeats. This cycle is executed only for the first packet arriving on an 233
`
`Juniper Ex. 1014-p. 5
`Juniper v Implicit
`
`

`

`uncached flow. Subsequent packets follow a faster path because of the cached entry in the flow table. Note that in our system, we have created optimized implementations of both the flow and filter tables, allowing for high performance on both the cached and uncached paths. These implementations are described in Section 5. Cached flow processing involves the following sequence: l Processing at the first gate: When a packet from a cached flow encounters the first gate, the AIU is called to request the plugin instance. This time, the pointer to the instance requested is already in the flow table. The flow table is looked up efficiently, and the plugin instance pointer corresponding to the calling gate is returned. No filter table lookups are required. l Associating the packet with a flow index: Together with the instance requested, the AIU returns a pointer to the row in the flow table where the information associ- ated with the flow is stored. This pointer is called the flow index (HX), and is stored in the packet’s mbuf’. The instance is then called to process the packet, following which the IP stack passes the packet on to the next gate. l Processing at subsequent gates: Once the packet has made its way past the first gate, the AIU does not have to be called upon to classify the packets at the remaining gates. Macros implementing a gate can retrieve the instance pointers cached in the flow table by accessing the FIX stored in the packet. This allows us to pass pack- ets to the appropriate instances in a very efficient manner using an indirect function call instead of a “hardwired” function call. We show in section 7 that this does not imply significant performance penalties. Our architecture implements a highly modular system with minimal performance overhead. Our architecture is scalable to a very large number of gates since the number of gates matters only for the first packet arriving on a (uncached) flow. But even for the first packet, fast retrieval of the instance is possible with the DAG based packet classification algorithm that is used to implement the filter tables in our system (see Section 5). 4. PLUGINS AND THE PLUGIN CONTROL UNIT (PCU) Depending on the type of network software component that is implemented by a plugin, it can be very simple (e.g., a dozen lines of code for an IP option plugin) or very complex (e.g., a state-of-the-art packet scheduler). Each plugin in our framework is identified by a 32 bit plugin code. The upper 16 bits of the code identify the plugin type. The plugin type refers to the specific network software component it implements; thus, there is a direct correspondence between a gate in our architecture and the plugin type. Whenever a packet enters a gate, it will be passed to a registered plugin of the appropriate type. There can potentially be multiple ’ The mbuf is a data structure that is used to store packets and packet related information efficiently in BSD derived operating system kernels. plugins of the same type that have been registered identified by the lower 16 bits of the plugin code; in this case, flow filters that have been installed for the corresponding plugin type are used to pick the right plugin to which the packet should be passed. Our implementation currently supports four types of plugins, corresponding to different network functions: IP options, IP security, Packet Scheduling, and Longest-prefix Matching (used as part of the packet classifier that is present in the AIU). In the future, we plan to also add support for a Routing plugin, which would allow routing table lookups to be based on the flow classification that is performed by the AIU. Other plugins that are envisioned include a plugin for statistics gathering (useful for network monitoring/ management), a plugin for congestion control mechanisms (e.g., RED), a plugin monitoring TCP congestion backoff behaviour, and a plugin for firewall functions. Doubtless, additional plugin types will be introduced by third parties once we have released our code into the public domain. We will discuss the implementation of two example plugins in Section 6. Plugins must fulfill two important requirements: they have to register a callback function with the PCU when they are loaded into the kernel, and that callback function must reply to a set of messages. As mentioned earlier, these messages fall into two categories: standardized messages, and plugin- specific messages. The set of standardized messages include: create-instance: Creates an instance of a plugin. This results in the allocation of a data structure that will be used to store configuration and run-time information for that instance. A function to handle a data packet (the main packet processing function which is called at the gate) must be specified and functions which are called by the AIU on removal of an entry in the flow or filter table can optionally be specified. free-instance: Removes all instance specific data struc- tures. A freed instance can no longer be used by the ker- nel and all references to it are removed from the flow table and the filter table. register-instance: Registers a plugin instance with the AIU, and binds that instance to a filter that has to be sup- plied as a parameter. The same instance may be regis- tered multiple times with the AIU with different filter specifications. This message would result in a call to a registration function that is published by the AIU. deregister-instance: Removes the binding between a specified filter in the AIU and the plugin instance. The PCU itself is a very simple component (200 lines of C code) managing a table for each plugin type to store the plugin’s names and callback functions. Once loaded into the kernel, plugins register their callback function thro