Packet switch with enqueue structure for odering packets

A packet switch comprising:

• egress ports;
• an ingress port configured to receive packets in a sequential order and generate enqueue records corresponding to the packets, each of the enqueue records including a posted pass flag indicating whether a corresponding packet is permitted to be routed through the packet switch ahead of a posted packet preceding the corresponding packet in the sequential order based on a permissive passing rule, at least one of the enqueue records including a flow control flag having fewer data bits than a transaction identifier of the corresponding packet for controlling packet flow through the packet switch;
• an enqueue structure coupled to the ingress port and comprising an enqueue queue and an enqueue memory, the enqueue queue comprising:
• an ordered queue configured to store based on the sequential order older enqueue records corresponding to packets stored in the ingress port, the enqueue memory configured to store based on the sequential order newer enqueue records corresponding to packets stored in the ingress port;
• and
• dedicated storage units configured to store a copy of the oldest enqueue record stored in the enqueue memory corresponding to a posted packet stored in the ingress port and a copy of the oldest enqueue record stored in the enqueue memory corresponding to a completion packet stored in the ingress port;
• an enqueue controller coupled to the enqueue structure and configured to determine a routing order for routing the packets from the ingress port to the egress ports based on the enqueue records and a set of ordering rules including the permissive passing rule that indicates whether a subsequent packet is permitted to be routed through the packet switch ahead of a previous packet preceding the subsequent packet in the sequential order based on a packet type of the previous packet and a packet type of the subsequent packet, a prohibitive passing rule that indicates whether a subsequent packet is prohibited from being routed through the packet switch ahead of a previous packet preceding the subsequent packet in the sequential order, and a requisite passing rule that indicates when a subsequent packet is required to be routed through the packet switch ahead of a previous packet preceding the subsequent packet in the sequential order when the previous packet is blocked;
• and
• a switch fabric coupled to the ingress port and the egress ports, the switch fabric configured to route the packets from the ingress port to the egress ports in the routing order.

A method of routing packets through a packet switch, the method comprising:

• receiving packets at an ingress port of a packet switch in a sequential order;
• storing the packets in the ingress port;
• generating enqueue records corresponding to the packets, each of the enqueue records including a pass flag indicating whether a corresponding packet is permitted to be routed through the packet switch ahead of another packet preceding the corresponding packet in the sequential order based on a permissive passing rule;
• storing older enqueue records into an enqueue queue based on the sequential order;
• storing newer enqueue records into an enqueue memory based on the sequential order;
• storing a copy of the oldest enqueue record stored in the enqueue memory and corresponding to a posted packet into the enqueue queue;
• storing a copy of the oldest enqueue record stored in the enqueue memory and corresponding to a completion packet into the enqueue queue;
• determining a routing order for routing the packets from the ingress port to egress ports based on the enqueue records stored in the enqueue queue and a set of ordering rules including the permissive passing rule that indicates whether a subsequent packet is permitted to be routed through the packet switch ahead of a previous packet preceding the subsequent packet in the sequential order based on a packet type of the previous packet and a packet type of the subsequent packet, a prohibitive passing rule that indicates whether a subsequent packet is prohibited from being routed through the packet switch ahead of a previous packet preceding the subsequent packet in the sequential order and a requisite passing rule that indicates when a subsequent packet is required to be routed through the packet switch ahead of a previous packet preceding the subsequent packet in the sequential order when the previous packet is blocked;
• and
• routing the packets from the ingress port to the egress ports in the routing order.