********************************************************
Eliminating receiver livelock in the interrupt-driven kernel.
********************************************************

This is clearly a "new idea" paper. The authors identified a problem of a
receiver livelock and proposed a new solution to it. The receiver livelock
occurs when the system is not making any measurable progress, because it
spends all its time handling network interrupts associated with receiving
of packets from the network. Even though the system spends time processing
the packets, the packets do not get further up in the protocol
stack.  This happens because the protocol stack code runs at a lower
priority than the device driver code, and so it never gets to run, because
the device is always busy.  Therefore, the system wastes its effort on
processing the packets that will eventually get dropped anyway.  Several
possible ways of solving this problem is to use polling or to do
processing of the entire packet at the device IPL.  The problem with
polling is that even though it is effective at times of high overload, it
may add unnecessary latency to packet processing times when the system is
not very busy.  The problem with the second solution is that it may cause
starvation of other parts of the system, such as those responsible for
packet transmission and I/O.

The authors offered the following solution for the receiver livelock
problem:

1. They use a hybrid interrupt-polling design, where interrupts are used
to initiate polling. The  polling thread cycles through networking tasks
in a round-robin fashion, and enables interrupts when no more work is
left.

2. To ensure fairness for other processes in the system, polling thread is
subject to quotas - it has to stop processing the incoming packets after a
certain number of them have been processed.

3. The IP queue is eliminated at all - the polling thread does processing
on the packet from beginning to end to make sure that the packet into
which it has invested time is not dropped. 

I think that eliminating the IP queue is not necessarily a good
idea. While eliminating the queue reduces overhead associated with queue
management, it also removes a layer of insulation from bursts of
traffic.  When input traffic flows in at a constant high rate it makes
sense to process each packet to completion and drop the excess incoming
packets on the device level. However, when there is a burst of incoming
packets it may make more sense to spend little time processing each packet
and throw them onto the queue. This way the system will be able to
"save" more packets from being dropped at the device, and when the burst
ends it can offload the packets that are waiting at the IP queue.  End
systems often experience bursty traffic, because TCP traffic is by nature
bursty. However, a router in the middle of the network may experience
constant-rate traffic from aggregated TCP streams (unless the TCP traffic
is self-similar).

My main criticism to the experimental section is that the duration of each
trial was very short - the client system sent only 10000 packets. It might
be the case that because the experiment was so short, the system was able
to deliver such high throughput, because it accumulated packets in memory. 

Even though I think that the authors provided a good solution to receiver
livelock problem, it seems that in reality it would be difficult to use
their solution, because it requires a lot of tuning, depending on what
applications are running on the machine. It is not something that one can
just use on any system. For example, the system has to do different things
depending on whether or not there are any user processes running on the
system.  I think that the solution would be more practical if the authors
designed some mechanism that would allow the system to dynamically change
the settings depending on how the system is used.

Overall the paper was very interesting to read - it shows that the authors
studied the problem very carefully. 
Eliminating Receive Livelock in an Interupt-Driven Kernel

Interrupts come in from devices (clock, disk, network, serial line);
they are, by default, higher in priority.  But there is actually a
gate in between the interrupts and the CPU, so you can set things so
that only items with higher priority than what you set are let
through.

They describe a packet forwarding application.  The network interrupt
places packets into one of several queues (IP, ARP, ...).  The
protocol processor (later) takes from these queues, does some
processing and puts the data into other queues, like for FTP, telnet,
screend.  These queues are socket-connected to daemons (usually),
which process the data and send it into another queue, for output.

Disadvantage of polling:
latency if there is lots of data.
wasted CPU time, if there is little data, because you keep probing.

They add a counter to see how much time is being spent in interrupt
handling to make sure enough time is being spent 

Do we buy their assertion that once you start a packet you should
always carry it through to completion?

For figure 6.2, it would have been interesting if they had
instrumented the kernel to show that the kernel was really spending
all of its time processing the network interrupts.  They don't really
show this.