Guaranteed in-order packet delivery

摘要

Circuitry to provide in-order packet delivery. A packet descriptor including a sequence number is received. It is determined in which of three ranges the sequence number resides. Depending, at least in part, on the range in which the sequence number resides it is determined if the packet descriptor is to be communicated to a scheduler which causes an associated packet to be transmitted. If the sequence number resides in a first “flush” range, all associated packet descriptors are output. If the sequence number resides in a second “send” range, only the received packet descriptor is output. If the sequence number resides in a third “store and reorder” range and the sequence number is the next in-order sequence number the packet descriptor is output; if the sequence number is not the next in-order sequence number the packet descriptor is stored in a buffer and a corresponding valid bit is set.

主权项

1. A method, comprising:
(a) receiving a packet descriptor from an ingress island and a sequence number onto an egress island, wherein both the ingress island and the egress island are included in an island based network flow processor; (b) storing the packet descriptor in a buffer in a memory unit, wherein the memory unit comprises a plurality of buffers, wherein a register comprises a plurality of valid bits, wherein there is a one-to-one correspondence between the valid bits and the buffers, and wherein a head pointer points to one valid bit in the register; (c) setting the valid bit corresponding to the buffer in (b); (d) if the sequence number is in a first range then: (i) outputting all packet descriptors stored in the memory unit, and (ii) clearing all valid bits that are associated with the buffers that stored the packet descriptors; (e) if the sequence number is in a second range then: (i) outputting the packet descriptor received in (a), and (ii) clearing the valid bit that is associated with the buffer that stored the packet descriptor; and (f) if the sequence number is in a third range then: (i) if the head pointer points to a set valid bit then outputting the packet descriptor received in (a), clearing the valid bit associated with the buffer that stored the packet descriptor, incrementing the head pointer, and repeating (f), or (ii) if the head pointer does not point to a set valid bit then returning to (a).