Polytechnic University

Other

Jinsoo Park

Hung-Hsiang Jonathan Chao

Packets out-of-sequence problem can be solved by using a window flow control scheme that can dispatch traffic at the cell level, in a round robin fashion, as evenly as possible. Each VOQ at the input port has a sequence head pointer that is used to assign sequence numbers (SN) to the cells. Also a sequence tail pointer is available at each VOQ that is used to acknowledge and limit the amount of cells that can be sent to the output ports based on the window size of the scheme. Each VIQ at the output port has a sequence pointer or sequence number (SN) pointer that indicates to the VIQ which cell to wait for. Once the VIQ receives the cell that the SN pointer indicated, the output port sends an ACK packet back to the input port. By using sequence numbers and the relevant pointers, the packet out-of-sequence problem is solved.

Maintaining packet sequence using cell flow control

To avoid packet out-of-sequence problems, while providing good load balancing, each input port of a switch monitors the outstanding number of packets for each flow group. If there is an outstanding packet in the switch fabric, the following packets of the same flow group should follow the same path. If there is no outstanding packet of the same flow group in the switch fabric, the (first, and therefore subsequent) packets of the flow can choose a less congested path to improve load balancing performance without causing an out-of-sequence problem. To avoid HOL blocking without requiring too many queues, an input module may include two stages of buffers. The first buffer stage may be a virtual output queue (VOQ) and second buffer stage may be a virtual path queue (VPQ). At the first stage, the packets may be stored at the VOQs, and the HOL packet of each VOQ may be sent to the VPQ. By allowing each VOQ to send at most one packet to VPQ, HOL blocking can be mitigated dramatically.

Packet sequence maintenance with load balancing, and head-of-line blocking avoidance in a switch

Practical packet reassembly in large, multi-plane, multi-stage switches is possible by using a scheduling technique called dynamic packet interleaving. With dynamic packet interleaving scheduling, if more than one packet is contending for the same output link in a switch module, an arbiter in the switch module gives priority to a partial packet (i.e., to a packet that has had at least one cell sent to the queue). The number of reassembly queues required to ensure reassembly is dramatically reduced (e.g., to the number of paths multiplied by the number of scheduling priorities). Deadlock may be avoided by guaranteeing (e.g., reserving) at least one cell space for all partial packets.

Packet reassembly and deadlock avoidance for use in a packet switch

To use the memory space more effectively, cell memory can be shared by an input link and all output links. To prevent one flow from occupying the entire memory space, a threshold may be provided for the queue. The queue threshold may accommodate the RTT delay of the link. Queue length information about a downstream switch module may be sent to an upstream switch module via cell headers in every credit update period per link. Cell and/or credit loss may be recovered from. Increasing the credit update period reduces the cell header bandwidth but doesn't degrade performance significantly. Sending a credit per link simplifies implementation and eliminates interference between other links.

Switch module memory structure and per-destination queue flow control for use in a switch

Packet-level multicasting may be used to avoid the cell header and the memory size problems. One or more multicast control cells may be appended before one or more data cells of a multicast packet to carry multicast bitmap information. The control cell may be stored at the cell memory. This approach is suitable for a multi-plane, multi-stage packet switch.

Growing community of inventors

Leonia, NJ, United States of America

Jinsoo Park