Method and apparatus for reducing the required size of sequence numbers used in resequencing packets

A packet switch comprising:

• a plurality of interconnection networks, each of the plurality of interconnection network includes a plurality of interconnection network input ports and a plurality of interconnection network output ports, each of the plurality of interconnection input ports including an interconnection network sequencer, each of the plurality of interconnection network output ports including an interconnection network resequencer;
• a plurality of packet switch input interfaces coupled to the plurality of interconnection networks each of the plurality of packet switch input interfaces including a packet switch sequencer;
• and
• a plurality of packet switch output interfaces coupled to the plurality of interconnection networks, each packet switch output interface includes a packet switch resequencer.

A method comprising:

• maintaining a first packet switch sequence number for each of a plurality of output interfaces at each of a plurality of input interfaces of a packet switch;
• maintaining a first interconnection network sequence number for each of a plurality of output ports at each of a plurality of input ports of a plurality of interconnection networks;
• receiving a first packet at a first input interface;
• adding to the first packet the first packet switch sequence number maintained at the first input interface for a destination output interface of the first packet;
• forwarding the first packet to a particular one of the plurality of interconnection networks leading to the destination output interface;
• receiving the first packet at a first input port of the particular interconnection network;
• and
• adding to the first packet the first interconnection network sequence number maintained at the first input port for a destination output port to which the first packet is destined.

A method comprising:

• adding a first packet switch sequence number to a first packet;
• adding a first interconnection network sequence number to the first packet;
• maintaining a first output interconnection network sequence number at each output port;
• comparing the first interconnection network sequence number with the first output interconnection network sequence number;
• adding a second packet switch sequence number to a second packet;
• adding a second interconnection network sequence number to the second packet;
• receiving the first packet before the second packet at a first output port;
• and
• forwarding the second packet from the first output port before the first packet when the second interconnection network sequence number comes before the first interconnection network sequence number in a predefined sequence.

A method comprising:

• adding a first packet switch sequence number to a first packet;
• adding a first interconnection network sequence number to the first packet;
• maintaining a first output interconnection network sequence number at each output port;
• comparing the first interconnection network sequence number with the first output interconnection network sequence number;
• maintaining a first packet switch output sequence number at each output interface;
• and comparing the first packet switch sequence number with the first packet switch output sequence number;
• adding a second packet switch sequence number to a second packet;
• adding a second interconnection network sequence number to the second packet;
• receiving the first packet before the second packet at a first output interface;
• and
• forwarding the second packet from the first output interface before the first packet when the second packet switch number comes before the first packet switch number in a predefined sequence.

A packet switch comprising:

• a plurality of in-order delivery interconnection elements;
• a plurality of packet switch input interfaces coupled to the plurality of in-order delivery interconnection elements, each packet switch interface including a packet distributor to distribute packets in accordance with a packet distribution scheme across the plurality of in-order delivery interconnection elements and a packet switch sequencer to add a sequence number within a sequence number range to packets to be sent across the plurality of in-order delivery interconnection elements;
• and
• a plurality of packet switch output interfaces coupled to the plurality of in-order delivery interconnection elements, each packet switch output interface including a packet switch resequencer;
• wherein the plurality of in-order interconnection elements comprise n in-order delivery interconnection elements, and the packet distribution scheme includes sending packets to each of the interconnection elements m number of times in a distribution cycle for a particular packet switch output port, and the sequence number includes a binary representation of log2nm bits.

A packet switch comprising:

• a plurality of in-order delivery interconnection elements;
• a plurality of packet switch input interfaces coupled to the plurality of in-order delivery interconnection elements, each packet switch interface including a packet distributor to distribute packets in accordance with a packet distribution scheme across the plurality of in-order delivery interconnection elements and a packet switch sequencer to add a sequence number within a sequence number range to packets to be sent across the plurality of in-order delivery interconnection elements;
• and
• a plurality of packet switch output interfaces coupled to the plurality of in-order delivery interconnection elements, each packet switch output interface including a packet switch resequencer;
• wherein the plurality of in-order interconnection elements comprise n in-order delivery interconnection elements, and the packet distribution scheme includes sending packets to each of the interconnection elements m number of times in a distribution cycle for a particular packet switch output port, and the sequence number range includes at least mn different sequence numbers.

An apparatus comprising:

• means for maintaining a first packet switch sequence number for each of a plurality of output interfaces at each of a plurality of input interfaces of a packet switch;
• means for maintaining a first interconnection network sequence number for each of a plurality of output ports at each of a plurality of input ports of a plurality of interconnection networks;
• means for receiving a first packet at a first input interface;
• means for adding to the first packet the first packet switch sequence number maintained at the first input interface for a destination output interface of the first packet;
• means for forwarding the first packet to a particular one of the plurality of interconnection networks leading to the destination output interface;
• means for receiving the first packet at a first input port of the particular interconnection network;
• and
• means for adding to the first packet the first interconnection network sequence number maintained at the first input port for a destination output port to which the first packet is destined.

An apparatus comprising:

• means for adding a first packet switch sequence number to a first packet;
• means for adding a first interconnection network sequence number to the first packet;
• means for maintaining a first output interconnection network sequence number at each output port;
• means for comparing the first interconnection network sequence number with the first output interconnection network sequence number;
• means for adding a second packet switch sequence number to a second packet;
• means for adding a second interconnection network sequence number to the second packet;
• means for receiving the first packet before the second packet at a first output port;
• and
• means for forwarding the second packet from the first output port before the first packet when the second interconnection network sequence number comes before the first interconnection network sequence number in a predefined sequence.

An apparatus comprising:

• means for adding a first packet switch sequence number to a first packet;
• means for adding a first interconnection network sequence number to the first packet;
• means for maintaining a first output interconnection network sequence number at each output port;
• means for comparing the first interconnection network sequence number with the first output interconnection network sequence number;
• means for maintaining a first packet switch output sequence number at each output interface;
• and means for comparing the first packet switch sequence number with the first packet switch output sequence number;
• means for adding a second packet switch sequence number to a second packet;
• means for adding a second interconnection network sequence number to the second packet;
• means for receiving the first packet before the second packet at a first output interface;
• and
• means for forwarding the second packet from the first output interface before the first packet when the second packet switch number comes before the first packet switch number in a predefined sequence.

A packet switch comprising:

• a plurality of in-order delivery interconnection elements;
• a plurality of packet switch input interfaces coupled to the plurality of in-order delivery interconnection elements, each packet switch interface including a packet distributor to distribute packets in accordance with a packet distribution scheme across the plurality of in-order delivery interconnection elements and a packet switch sequencer to add a sequence number within a sequence number range to packets to be sent across the plurality of in-order delivery interconnection elements;
• and
• a plurality of packet switch output interfaces coupled to the plurality of in-order delivery interconnection elements, each packet switch output interface including a packet switch resequencer;
• wherein each of the in-order delivery interconnection elements comprise an in-order delivery interconnection network including a second set of sequence numbers;
• and
• wherein the plurality of in-order interconnection elements comprise n in-order delivery interconnection elements, and the packet distribution scheme includes sending packets to each of the interconnection elements m number of times in a distribution cycle for a particular packet switch output port, and the sequence number includes a binary representation of log2nm bits.

A packet switch comprising:

• a plurality of in-order delivery interconnection elements;
• a plurality of packet switch input interfaces coupled to the plurality of in-order delivery interconnection elements, each packet switch interface including a packet distributor to distribute packets in accordance with a packet distribution scheme across the plurality of in-order delivery interconnection elements and a packet switch sequencer to add a sequence number within a sequence number range to packets to be sent across the plurality of in-order delivery interconnection elements;
• and
• a plurality of packet switch output interfaces coupled to the plurality of in-order delivery interconnection elements, each packet switch output interface including a packet switch resequencer;
• wherein each of the in-order delivery interconnection elements comprise an in-order delivery interconnection network including a second set of sequence numbers;
• and
• wherein each of the packet distributors includes a data structure including a set of indicators to indicate which of the interconnection elements were previously selected to, or remain available to receive one of the packets in a current distribution cycle, wherein a particular interconnection element is only selected a predetermined number of times in the current distribution cycle.