Ensuring proper packet ordering in a cut-through and early-forwarding network switch
First Claim
1. A network switch comprising:
- a plurality of input ports configured to receive data forming one or more packets;
a plurality of output ports configured to convey the packets out of the switch, wherein each output port comprises a plurality of output queues;
a random access memory; and
data transport logic coupled between the input ports, the output ports, and the memory, wherein a first input port is configured to request cut-through routing from at least one destination output port in response to receiving data corresponding to a first packet that is a candidate for cut-through routing, wherein, in response to receiving a signal granting cut-through from the destination output port, the input port is configured to route the data corresponding to the first packet to the destination output port via the data transport logic, and wherein in response to not receiving the signal granting cut-through the input port is configured to store (a) the data to the shared memory via the data transport logic and (b) a packet identifier to one of the output queues, wherein, in response to not receiving the grant cut-through signal, the input port is configured to store a packet identifier on one of the destination port'"'"'s output queues, and wherein the first input port is configured to store a time value for each output port, wherein the time value corresponds to the last time that the first input port added a packet identifier to one of the destination output port'"'"'s output queues.
2 Assignments
0 Petitions
Accused Products
Abstract
A system and method for ensuring that packets are not switched out of order in a network switch capable of dynamically selecting different routing techniques. The network switch may include multiple input ports, multiple output ports, and a shared random access memory coupled to the input ports and output ports by data transport logic. The switch may route packets using cut-through routing or early-forwarding. To ensure that packets are not switched out of order, sequence numbers may be assigned to packets as the packets are received at one of the input ports. A different sequence may be used for each output port. The output port may also track sequence numbers by storing the number corresponding to the most recently received packets from each input port. The stored value may compared with a sequence number assigned to a packet to ensure that they are within one before allowing cut-through routing.
-
Citations
28 Claims
-
1. A network switch comprising:
-
a plurality of input ports configured to receive data forming one or more packets;
a plurality of output ports configured to convey the packets out of the switch, wherein each output port comprises a plurality of output queues;
a random access memory; and
data transport logic coupled between the input ports, the output ports, and the memory, wherein a first input port is configured to request cut-through routing from at least one destination output port in response to receiving data corresponding to a first packet that is a candidate for cut-through routing, wherein, in response to receiving a signal granting cut-through from the destination output port, the input port is configured to route the data corresponding to the first packet to the destination output port via the data transport logic, and wherein in response to not receiving the signal granting cut-through the input port is configured to store (a) the data to the shared memory via the data transport logic and (b) a packet identifier to one of the output queues, wherein, in response to not receiving the grant cut-through signal, the input port is configured to store a packet identifier on one of the destination port'"'"'s output queues, and wherein the first input port is configured to store a time value for each output port, wherein the time value corresponds to the last time that the first input port added a packet identifier to one of the destination output port'"'"'s output queues. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A network switch comprising:
-
a plurality of input ports configured to receive data forming one or more packets;
a plurality of output ports configured to convey the packets out of the switch, wherein each output port comprises a plurality of output queues;
a random access memory; and
data transport logic coupled between the input ports, the output ports, and the memory, wherein each input port has a plurality of sequences, wherein the first input port is configured to assign a sequence number to each received packet, wherein the sequence number accompanies the packet through the switch, wherein each output port is configured to store a last maximum sequence number (LMSN) for each input port register, wherein a first input port is configured to request cut-through routing from a first output port in response to receiving data corresponding to a first packet, and wherein the destination output port is configured to compare (a) the sequence number of the first packet with (b) the stored LMSN for the corresponding input port. - View Dependent Claims (10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28)
-
-
16. A network switch comprising:
-
a plurality of ports, wherein a first one of said ports is an input port configured to receive data forming a packet, wherein a second one of said ports is an output port configured to convey the packet out of the switch, wherein the output port comprises an output first-in first-out memory (FIFO);
a random access memory (RAM); and
a means for routing the data between the input port, the RAM, and the output port, wherein the means for routing is configured to either route the packet directly to the output FIFO by cut-through routing or route the packet to the RAM for either early forwarding or store and forward routing, wherein the means is configured to route the data from the input port to the output port in response to detecting a cut-through grant signal from the output port, wherein the means is configured to store the data to the RAM in response to not receiving the cut-through grant signal from the output port, wherein the input port is configured to store a time value for the output port, wherein the time value corresponds to the last time that the input port added a packet identifier to one of the output port'"'"'s output queues.
-
-
24. A method for switching packets in a network switch having a plurality input ports and output ports, the method comprising:
-
receiving data forming a first packet at a first input port, wherein the first packet is to be routed to at least a first output port; and
switching the packet by cut-through routing or early-forwarding, wherein cut-through routing is performed only if (a) no previous packets received at the first input port and destined for the first output port have not been received at the first output port, and (b) the first output port has resources available to handle the data.
-
Specification