A systematic Characterization of Application Sensitivity to Network Performance

107
Poll Q0
Poll Q1
Poll Q2
Poll Q3
Poll Q4
Poll Q5
Poll Q6
Free buffer
Peer ACK
Rx check header
Rx check body
EnQ router in
Router In handler
EnQ IP output
Peer to peer start
DMA start handler
DMA generic start
DMA start body
DMA start header
0
10
20
30
40
50
60
70
80
90
100
110
120
130
SPINE IP Router Event Graph
Time (
µ
sec)
Event T
ype
Route
Packet 2
Route
Packet 1
Rt.
Pkt. 3
DMA
Packet 1
DMA
Packet 0
DMA
Packet 2
Receive
Packet 1
Receive
Packet 2
Receive
Packet 3
Figure 6.4: SPINE IP Router Event Plot
This figure plots events as they unfold in the SPINE IP router. Time is shown on the x-axis and event
types on the y-axis. A box is plotted at the point in time at each event occurrence. The width of the
box corresponds to the length of the event. The dashed rectangles correspond to higher-level packet
semantics: receiving a packet, routing it, and forwarding it over the PCI bus. The arrows trace the
causal relationships of a single packet as it moves through the system.
6. The I/O run-time sends the packet to the LANai card specified. In this case, the packet must
move over the I/O bus into the input queue of another LANai card.
7. The second LANai card does not need to forward the packet to any extensions; the address of
the output queue was known to the router extension. Thus, on finding the entire packet in the
I/O bus input queue, the I/O run-time invokes the wire-output routine.
8. If the extension can not route the packet, it can be sent to the kernel network stack for further
processing. Later, the host OS can route the packet to the appropriate card.
6.2.2
SPINE Event Processing
In this section, we show how SPINE event processing translates into overall performance.
The apparatus for our experiments is different than the one used in the rest of this thesis. We use a
cluster of 4 Intel Pentium Pro workstations (200MHz, 64MB memory, 512 KB L2 cache) running

---

108
Windows NT version 4.0. One node has four LANai cards and acts as the router. The Myricom
LANai adapters are on a 33 MHz PCI bus, and they contain 1MB SRAM card memory. The LANai
is clocked at 33 MHz, and has a wire rate of 160MB/s.
Figure 6.4 shows a real snapshot of the event processing. We used algorithms for forward-
ing table compression and fast IP lookup described in [79], and inserted one thousand routes into less
than 20KB of memory on the adapter. The event trace was collected while forwarding two million
packets at a maximum rate such that the percentage of dropped packets was less than 0.5%. The
average per-packet processing time, or
ý
, was 95
þ
s/packet.
In order to understand Figure 6.4, first recall that all SPINE processing is ultimately de-
composed into internal Active Message handlers. For example, when the IP router extension calls
the procedure to forward a message to a peer device, the run-time implements this functionality by
issuing a series of active messages to itself. Thus, event and handler invocation becomes synony-
mous. This approach not only simplifies the dispatcher, but it also exposes the natural parallelism
inherent in the operation.
The x-axis in Figure 6.4 represents time. The y-axis is an enumeration of event (handler)
types. The dark boxes represent time spent in event processing. The position of the boxes on the
x-axis shows the time a particular event took place. The position on the y-axis shows what event
was processed at that time. The width of the dark box shows the length of the event. For example,
during the period between 16 and 20 microseconds, the IP routing handler (Step 4 in Figure 6.3) was
running.
The events are ordered by type. The lower events are polls to the 7 input queues. The next
set (peer ACK and Free buffer) are LANai-to-LANai flow control over the PCI bus. Receiving over
the wire occupies the next 3 events, followed by only 2 events needed to route the packet. The final
5 events manage the DMA engine over the PCI bus.
Because SPINE breaks message processing into many tiny events, the event graph at first
appears to be a jumbled maze with little discernible structure. In reality however, Figure 6.4 shows
a regular, periodic pattern. The key to understanding the event graph is to recognize the high level
structure shown in Figure 6.3 emerging from the thicket of small events. From these patterns we can
deduce both the rate at which packets are processed, as well as the latency of a packet as it passes
through the system. The dashed rectangles in Figure 6.4 outline higher-level packet-processing steps.
Recall that to route an IP packet requires 3 high level operations: receiving the packet (step 3 in
Figure 6.3), determining the destination (routing, step 4 in Figure 6.3), and forwarding the packet to
an egress adapter (steps 5-6 in Figure 6.3).

---

109
The gap,
ÿ
, in terms of seconds per packet, is easily discernible via the period of new pro-
cessing steps in the event graph. The time between receiving packets 1, 2 and 3 in Figure 6.4 is
roughly 55
 
s. The period for other kinds of processing, such as routing and DMA, is similar. Thus,
we can conclude that we can route a new IP packet once every 55
 
s.
The latency,
¡
, or time it takes a single packet to move through the system, is observable
by tracing the path of a single packet. The arrows in Figure 6.4 trace the processing path of packet
2 as it is received, routed, and transferred to the egress adapter. From the graph we can see that the
latency of a packet through the input adapter is roughly 100
 
s. Note that the bandwidth and latency
are distinct due to overlap (as shown in Figure 6.4). The gap is determined by the most complex
operation, which is the DMA of the packet between the two LANai cards.
A large discrepancy exists between the average measured
ÿ
of 95
 
s/packet and the ob-
served times in Figure 6.4 of 55
 
s/packet. The key to understanding the missing 40 microseconds
is that Figure 6.4 does not show a typical event ordering; rather it is a best case ordering.
We have discovered by observing many event plots that the slightly lower priority of PCI
events in SPINE results in oscillations of event processing. Several incoming packets are serviced
before any outgoing packets are sent over the PCI. These oscillations break an otherwise smooth
packet pipeline. The system oscillates between the fast state of one-for-one receive-and-send, and the
slow state of receiving a few packets and draining them over PCI. In our pipelining model, this would
be modeled as a succession of occupancies followed by a several transfers, forming large pipeline
bubbles. The net result is that the average forwarding time increases from 55 to 95
 
s. We are cur-
rently investigating ways to improve the priority system of the SPINE dispatcher to eliminate this
effect.
A closer look at Figure 6.4 shows two key limitations of the SPINE architecture. First, a
general-purpose event scheduler may not always optimize performance. Second, the occupancies
needed to multiplex many hardware devices on a weak embedded processor are substantial.
SPINE was constructed to be general enough so that the natural parallelism of packet pro-
cessing would automatically be interleaved with user extensions. However, precise scheduling would
be possible if we a priori knew what sequence of events need to be processed, and thereby achieve
better overall performance. Indeed, many other projects [81, 103] have exploited this fact and de-
veloped firmware with a fixed event-processing schedule that is specialized for a specific message
abstraction or application. The lack of an efficient, static processing schedule may be an inherent
limitation of any general-purpose system.
The second weakness in the SPINE architecture is that the occupancy to multiplex many

---