The switch translates frame sequence numbers between CSNs and LSNs as frames pass through it. This is trivial in the common case of frames arriving in order: if the flow is outbound (merge), assign CSN flow.next; if it is inbound (split), assign LSN sink.next for the frame's destination sink. Figure 3 shows resequencing between CSNs and LSNs for a single peer connection to two servers.
 |
The frame ring and chains allow efficient handling of acks. For inbound flows, the sinks encode their outgoing acks as LSNs. To convert an LSN ack from sink to a CSN for the peer, the switch traverses the frame chain for sink from sink.una and examines each frame's lsn to determine if the ack covers it. The ack passed through to the peer is the CSN of the oldest frame not acknowledged by any sink s: min(s.una). For outbound flows, on receiving a CSN ack from the peer, the switch traverses the frame ring from flow.una to identify frames covered by the ack and update their source.una. The LSN ack passed through to each source is its source.una.
The difficult sequencing cases involve reordered or dropped packets, which create sequence holes. To allow ordered, reliable delivery at the receiver, the switch must pass any sequence holes through to the receiver's sequence space. For example, if an outbound frame's LSN frame.lsn > source.next for its source, then one or more frames from that source are delayed. The switch passes the gap through to the peer by assigning the frame CSN flow.next + (frame.lsn - source.next), marking the intervening frame entries starting at CSN flow.next as holes from that source, and updating flow.next and source.next. On the other hand, if frame.lsn < source.next, then this is a delayed frame that fills an existing hole. To identify the frame's CSN, follow the source's frame chain forward from source.hole to locate the hole. The switch then places the CSN in the frame before forwarding it to the the peer.
The more difficult case occurs when an inbound frame is delayed. Since the switch does not know which sink will receive a given delayed inbound frame, it must reserve an LSN in the local space for any sinkthat receives a frame numbered after a pending hole. For each inbound frame, assign the LSN as sink.next + h, where h is the number of pending holes created since the last frame sent to the destination sink. The common case h=0 is easily recognized with a check that sink.lastgap = flow.lastgap. Else h is the number of pending hole frames f with f.csn > sink.last; these are found by traversing the frame chain rooted at flow.hole. Note that each pending hole is visited exactly once for each destination sink that receives a frame while the hole is pending; inbound holes create at worst O(n) extra work within the switch.
When an inbound frame destined for sink arrives to fill a hole at CSN i, traverse the frame ring forward from i, visiting each entry. For each sink s, let f be the entry for the first non-hole frame encountered that was destined for s (if any frames were sent to s since the sequence gap opened at i). If s = sink, then redirect frame i to s. Else, send a null frame (redirect patch) to s to fill the gap in its local sequence space (see Figure 3 for an example). In each case, the LSN for the sent frame is f.lsn-h, where his the number of holes encountered before f in the traversal, including the hole at i. If no frame for sink is encountered before the end of the traversal (CSN flow.next), then redirect i to sink with LSN sink.next. Again, the number of redirect patches per hole grows with the number of frames arriving while the hole is pending, and is bounded by n-1 and w.