The Click Modular Router

Summary. Click is an architecture for building flexible, configurable routers. Click's novel features include

• pull processing
• explicit queues
• flow-based router context

More Detail

Architecture.

• Click modules called elements.
Elements each have an elment class that determine their behavior. Elements have...
• Input and output ports.
Ports can be either push or pull.
• Elements also have a Configuration string
passed in from the configuration script to the element class.

Click includes a simple language for configuring a topology and has a preprocessor that catches intuitively incorrect configurations (push port connected to a pull port, for example).

Click packets are "moved" from element to element via virtual function call -- they are not copied. Further, click is copy-on-write.

Scheduling. Since packets handoff is just a virtual function call, a click CPU scheduler cannot stop processing at an arbitrary point; elements must cooperatively decide to do so.

Queues. Unlike many other systems (System V Streams, Scout), queues are explicit rather than implicit within each element. This allows configurations that might be difficult to arrange otherwise: single queue feeding multiple interfaces, etc.. Haven't yet figured out how to schedule CPU time among competing push and pull paths. Currently, use Linux default scheduling and a work list, a list to which Click can defer processing that gets processed once every 8 packets, to schedule processing. Authors note that ideally scheduling should be handled by one mechanism.

Push and pull processing. In systems without, packets might be pushed to interfaces busy sending and the router loses the ability to affect that packet later (drop, modify priority, etc.). Click has a generic mechanism called packet upstream notification that enables upstream pull elements to be notified when a packet is ready. This is enabled by click's support for flow based router context. The topology graph can be queried as to what elements are downstream,upstream, etc.. Filters can be passed to stop processing (ie, return all downstream elements until queues).

Limitations. Difficult to share things not oriented to packet flow such as router tables. Large elements required when control or data flow doesn't match packets (802.1d, for example).

Implementation.Click runs in a linux bottom-half handler (code too lengthy to run at interrupt but not naturally associated with a single user process). Click gets control when a packet arrives, when an interface becomes ready to send, or when a timer expires. Click uses the /proc filesystem to communicate with user processes (can change policy dynamically, record stats, etc.).

The authors implemented several of examples: a diff serv router (I believe it was a border router because it tagged and prioritized packets), IP router, ethernet switch, a number of RED routers each with slightly different variants of RED.

Performance. Can forward 10% slower than Linux kernel alone. Slowdown due to packet handoff to each element meaning that more elements makes a slower router. Has a 73,000 (64-byte) packets IP forwarding rate (faster than some cheap commercial routers).

Related work. Other composable packet processing modules:

• x-kernel.
  • Like click, has a graph of processing nodes.
  • Tailored to vertial paths rather than horizontal.
  • Acyclic.
  • Have "session" nodes -- no analog in Click.
• Scout.
  • More suited to router than x-kernel.
  • No session nodes and acyclic partially supported.
  • Execution centered on paths
  • Has support for inter-node communication other than packet flow.
  • "More interesting" scheduler.
• System V STREAMS
  • Implicit queueing.
  • Each module must be prepared for downstream module to fill up.
  • Modules with multiple input/output ports must do their own scheduling.
  • Tendency toward distributed scheduling and queueing logic conflicts with routers' needs for precise control.
• Router plug-ins.
  • Only partially configurable; does not allow control over path itself.
  • Allows processing modules to be inserted at any of several gates.
• Active networking initiative.
  • "Click allows a trusted user to change any aspect of routing; active networking allows untrusted packets to decide how they should be routed. The two approaches are complimentary."