Signaled Receiver Processing

Jose' Carlos Brustoloni, Bell Labs, Lucent Technologies
jcb@research.bell-labs.com

Many operating systems, including FreeBSD and several other Unix variants, 
process incoming packets at software interrupt level, at a priority higher 
than that of any application. Input protocol processing is not scheduled and 
is charged to the interrupted application, even if that application is 
unrelated to the received packets. This leads to two undesirable consequences.
First, high receive loads (for example, due to a server hot spot or a denial 
of service attack) can make the system unable to process any application 
("receive livelock" [1]). Second, CPU schedulers cannot make quality of 
service guarantees.

Lazy receiver processing (LRP) [2] has been proposed as a solution for
scheduling and correctly charging the costs of input protocol processing.
LRP requires early demultiplexing, i.e., that either the network interface 
card or its driver examine packet headers and enqueue each packet in the 
corresponding "network interface channel". Protocol processing occurs as 
follows: (1) When an application issues a receive call on a UDP socket, 
the application dequeues packets from the corresponding channel, processes 
them, and copies them to the user buffer; (2) A kernel thread, scheduled at 
the same priority as  the receiving application, asynchronously dequeues TCP 
packets from a channel, processes them, and enqueues them in the corresponding
socket, where they stay until the application issues a matching receive call.

LRP has four drawbacks. First, it does not support functionality present in 
many contemporary systems. For example, in FreeBSD, each packet may be dropped,
modified, or grabbed by a succession of modules (e.g., firewall, network 
address translation (NAT), RSVP) before the packet is accepted by the host
or forwarded. LRP ignores such modules, and therefore can make it quite hard 
to preserve full compatibility. Second, LRP does not properly acknowledge that
some protocol processing is ill-suited for scheduling as a time-sharing 
process. For example, should firewall or IP forwarding processes be penalized 
for their CPU consumption? Third, LRP uses for TCP processing kernel threads, 
which are not supported by many systems, including FreeBSD. Fourth, LRP gives 
to each application little control on when the application's packets are 
processed. For example, a receiving application cannot anticipate or delay its
TCP processing. 

To address LRP's mentioned drawbacks, I propose signaled receiver processing 
(SRP). I implemented SRP on Eclipse/BSD, a derivative of FreeBSD that provides
hierarchical proportional sharing of each system resource. SRP assigns a 
pseudo-socket to each case in the original input protocol implementation where
delivery is not to a user application (e.g., firewall, NAT, RSVP, but not TCP 
or UDP). System initialization spawns a privileged process for each such 
socket, and grants to the process a certain minimum share of the CPU (e.g., as
long as firewall is busy, it gets no less than x % of the CPU). Each such 
process opens and reads the corresponding socket. The read does not return; 
thereafter the system uses the process for scheduling the corresponding 
protocol, with a certain minimum CPU guarantee. SRP also adds an unprocessed 
input queue (UIQ) to every socket. SRP's early demultiplexing function (EDF)
checks each case as in the original input protocol implementation and enqueues
the packet in the UIQ of the first matching socket after that specified by 
EDF's skip argument. Certain protocols or modules (e.g., firewall) use the 
skip argument to pass a packet to subsequent input processing cases, as would
be the case in the original implementation.

When EDF enqueues a packet, it also signals SIGUIQ to the processes that have 
that socket open. The default SIGUIQ action is to dequeue packets from the
UIQ, process them, and then put them in the regular socket receive queue.
However, a process can catch SIGUIQ and defer input protocol processing until 
later (when the process issues a receive call). In either case, protocol
processing is scheduled and charged to the correct processes. No kernel threads
are needed.