Per-Flow State

Table 3: Frame ring entry.

frame.csn	CSN for this frame.
frame.lsn	LSN for this frame.
frame.source	Source node ID (outbound).
frame.sink	Sink node ID (inbound).
frame.ack	Has receiver acknowledged?
frame.hole	Is this frame a pending hole?
frame.link	CSN of next chain entry.

**Figure:** The Anypoint switch has one frame ring per flow, each of size w. In this example the ALRM redirects inbound frames to either sink A or sink B. The network has dropped CSN 1, so the switch inserts a gap of length 1 into each sink's LSN space. When CSN 1 arrives, the ALRM may direct the switch to deliver it to either A or B.
$\begin{figure} \centering {\small \epsfig{file=figs/frame_ring_new.eps, height=2in}\\ }\end{figure}$

The Anypoint switch maintains per-flow control state proportional to the number of unacknowledged frames. This state consists of a frame ring--a circular queue of w frame entries--and an endpoint table with an entry for each active set member, as shown in Figure 2. Table 2 summarizes the state in each endpoint table entry. The frame ring contains an entry for each active frame in the sliding window ranging from the oldest active frame (flow.left) to the highest numbered frame ( flow.left + w) eligible for transmission into the frame flow window. Entries become active as new frames arrive, and inactive as the left edge of the window passes them.

Table 4: Per-flow state variables.

flow.left	CSN of the oldest frame for which the sender is not known to have received an ack.
flow.una	CSN of the oldest frame for which the receiver is not known to have sent an ack.
flow.next	CSN of this flow's next frame.
lastgap	CSN of the newest hole (inbound).
hole	CSN of the oldest hole.

Every frame has a unique CSN; the ring entry for a frame may be retrieved in constant time by indexing from the frame's CSN in the obvious fashion. Table 3 summarizes the frame ring entry, and Table 4 summarizes per-flow state variables maintained to index the frame ring. CSNs are also used to link frame entries in frame chains in CSN order. For outbound flows, n frame chains link the frames from each source s, including the holes originating from s. The chain for each source s is rooted in s.una. For inbound flows, the nframe chains link the active frames destined for each sink, with a separate chain for pending sequence holes (see below). Every active frame is linked into exactly one chain.

Given these data structures, many aspects of state maintenance for the endpoint table, frame ring, and flow variables are straightforward. The discussion below focuses on the more interesting aspects.