Method and apparatus for a configurable packet routing, buffering and scheduling scheme to optimize throughput with deadlock prevention in SRIO-to-PCIe bridges

A method for bridging between a Serial RapidIO® (SRIO) port and a PCI Express® (PCIe) port, the method comprising:

• handling packets on an ingress flow with an ingress port, said ingress port selected from the group consisting of said Serial RapidIO® (SRIO) port and said PCI Express® (PCIe) port, said ingress port operatively coupled to a plurality of virtual output queues, and said plurality of virtual output queues operatively coupled to a circular-reorder queue;
• selecting said plurality of virtual output queues for storing said packets on said ingress flow based on packet priority, packet critical request flow, and packet flow identification;
• handling packets on an egress flow in said circular-reorder queue, said circular-reorder queue having a last-free-location pointer to a first open location in said circular-reorder queue, a next-to-send-location pointer to a first occupied location in said circular-reorder queue, a first-free-location pointer to a second open location in said circular-reorder queue, a last-packet-enqueued-location pointer to a second occupied location in said circular-reorder queue, and wherein said circular-reorder queue stores an acknowledgement identification for each of said packets, the handling packets in said circular-reorder queue further comprising:
• positioning said first-free-location pointer in said circular-reorder queue;
• receiving a packet on said egress flow;
• enqueuing said packet at said first-free-location pointer position in said circular-reorder queue;
• positioning said next-to-send-location pointer in said circular-reorder queue at said first-free-location-pointer position in said circular-reorder queue;
• dequeuing said packet at said next-to-send-location pointer position and assigning said acknowledgment identification to said packet;
• transmitting to a link partner said dequeued packet and said acknowledgment identification;
• receiving from said link partner a link-response signal related to said transmitted dequeued packet and said acknowledgment identification;
• and
• when said link-response signal is a packet accept for said transmitted dequeued packet and said acknowledgment identification then moving said first-free-location pointer in said circular-reorder queue one step and moving said next-to-send-location pointer position one step in said circular-reorder queue;
• when said link-response signal is a packet retry for said transmitted dequeued packet and said acknowledgment identification then not moving said next-to-send-location pointer in said circular-reorder queue.

A method for bridging between a Serial RapidIO® (SRIO) port and a PCI Express® (PCIe) port, the method comprising:

• handling packets on an ingress flow with an ingress port, said ingress port selected from the group consisting of said Serial RapidIO® (SRIO) port and said PCI Express® (PCIe) port, said ingress port operatively coupled to a plurality of virtual output queues, and said plurality of virtual output queues operatively coupled to a circular-reorder queue;
• selecting said plurality of virtual output queues for storing said packets on said ingress flow based on packet priority, packet critical request flow, and packet flow identification;
• handling packets on an egress flow in said circular-reorder queue, said circular-reorder queue having a last-free-location pointer to a first open location in said circular-reorder queue, a next-to-send-location pointer to a first occupied location in said circular-reorder queue, a first-free-location pointer to a second open location in said circular-reorder queue, a last-packet-enqueued-location pointer to a second occupied location in said circular-reorder queue, and wherein said circular-reorder queue stores an acknowledgement identification for each of said packets, the handling packets in said circular-reorder queue further comprising:
• receiving in said circular-reorder queue one or more packets on said egress flow in an order;
• enqueuing said one or more packets in said order;
• positioning said first-free-location pointer in said circular-reorder queue at a location where a new packet may be enqueued;
• maintaining in said circular-reorder queue said next-to-send pointer;
• dequeuing from said circular-reorder queue at said next-to-send-location pointer a packet for transmission and assigning said packet for transmission an acknowledgment identification;
• transmitting said packet to a link partner;
• receiving from said link partner a link-response signal related to said transmitted packet;
• and when said link-response signal is a packet accept for said transmitted packet then moving said first-free-location pointer in said circular-reorder queue one step;
• when said link-response signal is a packet retry for said packet transmitted then moving said next-to-send-location pointer in said circular-reorder queue to said packet transmitted.

A method bridging between a Serial RapidIO® (SRIO) port and a PCI Express® (PCIe) port, the method comprising:

• handling packets on an ingress flow with an ingress port, said ingress port selected from the group consisting of said Serial RapidIO® (SRIO) port and said PCI Express® (PCIe) port, said ingress port operatively coupled to a plurality of virtual output queues, and said plurality of virtual output queues operatively coupled to a circular-reorder queue;
• selecting said plurality of virtual output queues for storing said packets on said ingress flow based on packet priority, packet critical request flow, and packet flow identification;
• receiving in said circular-reorder queue, said circular-reorder queue having a last-free-location pointer to a first open location in said circular-reorder queue, a next-to-send-location pointer to a first occupied location in said circular-reorder queue, a first-free-location pointer to a second open location in said circular-reorder queue, a last-packet-enqueued-location pointer to a second occupied location in said circular-reorder queue, and wherein said circular-reorder queue stores an acknowledgement identification for each of said packets, a plurality of packets wherein for each packet in said plurality of packets there is an associated flow identification and wherein a first packet is a first received packet in said plurality of packets and wherein a last packet is a last received packet in said plurality of packets;
• receiving a mode signal for re-ordering said circular-reorder queue;
• and
• when said mode signal is a higher signal then sequentially searching in order from said first packet to said last packet for a packet having a higher flow identification than said first packet and when said higher flow identification packet is found moving said higher flow identification packet to a position of said first packet and sequentially moving said first packet and any intervening packets between said first packet and one less than said higher flow identification packet one position toward said last packet;
• when said mode signal is a highest signal then sequentially searching in order from said first packet to said last packet for a packet having a highest flow identification and when said highest flow identification packet is found moving said highest flow identification packet to a position of said first packet and sequentially moving said first packet and any intervening packets between said first packet and one less than said highest flow identification packet one position toward said last packet.

An apparatus for bridging between a Serial RapidIO® (SRIO) port and a PCI Express® (PCIe) port, the apparatus comprising:

• a circular-reorder queue for handling packets on an egress flow, said circular-reorder queue having a plurality of memory locations, a last-free-location pointer to a first open location in said circular-reorder queue, a next-to-send-location pointer to a first occupied location in said circular-reorder queue, a first-free-location pointer to a second open location in said circular-reorder queue, a last-packet-enqueued-location pointer to a second occupied location in said circular-reorder queue, and wherein said circular-reorder queue stores an acknowledgement identification for each of said packets on said egress flow;
• a plurality of pointers to one or more of said plurality of memory locations in said circular-reorder queue;
• an ingress port for keeping track of packet arrival order in a stream of packets on an ingress flow, said ingress port selected from the group consisting of said Serial RapidIO® (SRIO) port and said PCI Express® (PCIe) port, said ingress port operatively coupled to a plurality of virtual output queues, and said plurality of virtual output queues operatively coupled to said circular-reorder queue;
• and
• an ingress transport layer module, said ingress transport layer module selects said plurality of virtual output queues for packet storage for said ingress flow based on packet priority, packet critical request flow, and packet destination port;
• wherein said circular-reorder queue is further configured to perform packet reordering when various flows are backpressured.

An apparatus for bridging between a Serial RapidIO® (SRIO) port and a PCI Express® (PCIe) port, the apparatus comprising:

• an ingress port, said ingress port selected from the group consisting of said Serial RapidIO® (SRIO) port and said PCI Express® (PCIe) port for handling packets on an ingress flow;
• a plurality of virtual output queues, said virtual output queues operatively coupled to one or more queuing blocks, said one or more queuing blocks operatively coupled to at least one circular-reorder queue which handles packets on an egress flow, said circular-reorder queue having a last-free-location pointer to a first open location in said circular-reorder queue, a next-to-send-location pointer to a first occupied location in said circular-reorder queue, a first-free-location pointer to a second open location in said circular-reorder queue, a last-packet-enqueued-location pointer to a second occupied location in said circular-reorder queue;
• one of said virtual output queues allocated to a logical layer packet manager;
• all but the one of said virtual output queues allocated to a user defined interface;
• and
• an ingress transport layer module, said ingress transport layer module selects said plurality of virtual output queues for packet storage for said ingress flow based on packet priority, packet critical request flow, and packet destination port.