METHODS AND APPARATUS FOR VALIDATION OF EQUAL COST MULTI PATH (ECMP) PATHS IN A SWITCH FABRIC SYSTEM

• US 20120170575A1
• Filed: 12/29/2010
• Published: 07/05/2012
• Est. Priority Date: 12/29/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Mehra, Ashwani Kumar
• Granted Patent: US 8,780,896 B2
• Time in Patent Office: Days
• US Class Current: 370/359
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

An apparatus includes a replication engine of a switch module of a multi-stage switch. The replication engine is configured to receive a first validation packet from an input port of the switch module. The replication engine is configured to determine multiple output ports of the switch module to which a data packet can be sent to reach a destination device associated with the first validation packet. The replication engine is configured to define multiple second validation packets based on a number of output ports from the multiple output ports such that each second validation packet from the multiple second validation packets is uniquely associated with an output port from the multiple output ports. The replication engine is configured to send the multiple second validation packets to an output module configured to forward each second validation packet from the multiple second validation packets to its associated output port.

Claims

1. An apparatus, comprising:

a replication engine of a switch module of a multi-stage switch, the replication engine configured to receive a first validation packet from an input port of the switch module, the replication engine configured to determine a plurality of output ports of the switch module to which a data packet can be sent to reach a destination device associated with the first validation packet,

the replication engine configured to define a plurality of second validation packets based on a number of output ports from the plurality of output ports such that each second validation packet from the plurality of second validation packets is uniquely associated with an output port from the plurality of output ports, the replication engine configured to send the plurality of second validation packets to an output module configured to forward each second validation packet from the plurality of second validation packets to its associated output port.

2. The apparatus of claim 1, wherein the replication engine is configured to send the plurality of second validation packets to the output module such that the output module can use a header portion of each second validation packet from the plurality of second validation packets as an input to a hash function to determine to which output port from the plurality of output ports to forward each second validation packet from the plurality of validation packets.

3. The apparatus of claim 1, wherein each second validation packet from the plurality of second validation packets is configured to verify a different data path through the multi-stage switch between a source device and the destination device.

4. The apparatus of claim 1, wherein the replication engine is configured to query a reverse hash lookup table to determine a unique header to append to each second validation packet from the plurality of second validation packets.

5. The apparatus of claim 1, wherein the replication engine is configured to send the plurality of second validation packets to the output module via a processing module.

6. The apparatus of claim 1, wherein the multi-stage switch is a Clos network.

7. A non-transitory processor-readable medium storing code representing instructions to cause a processor to:

receive a first validation packet at a switch module of a distributed switch;

determine a number of output ports from a plurality of output ports of the switch module to which a data packet can be sent to reach a destination edge device associated with the first validation packet;

define a set of second validation packets based on the number of output ports from the plurality of output ports, each second validation packet from the set of second validation packets is uniquely associated with an output port from the plurality of output ports of the switch module to which the first validation packet can be sent; and

send each second validation packet from the set of second validation packets to its associated output port.

8. The non-transitory processor-readable medium of claim 7, wherein each second validation packet from the set of second validation packets is configured to verify a different data path through the distributed switch between a source edge device and the destination edge device.

9. The non-transitory processor-readable medium of claim 7, wherein the code representing instructions to cause the processor to determine includes code representing instructions to cause the processor to determine the number of output ports of the switch module to which the data packet can be sent based on a destination identifier of the first validation packet.

10. The non-transitory processor-readable medium of claim 7, further comprising code representing instructions to cause the processor to:

append a header to each second validation packet from the set of second validation packets such that a replication engine uses a set of values of the header of each second validation packet from the set of second validation packets as an input to a hash function to assign each second validation packet from the set of second validation packets to its associated output port.

11. The non-transitory processor-readable medium of claim 7, wherein the switch module is a first switch module, the first switch module being operatively coupled to a plurality of second switch modules via the plurality of output ports.

12. The non-transitory processor-readable medium of claim 7, wherein the set of second validation packets includes a number of second validation packets equal to the number of output ports from the plurality of output ports to which the data packet can be sent to reach the destination edge device associated with the first validation packet.

13. The non-transitory processor-readable medium of claim 7, further comprising code representing instructions to cause the processor to:

process each second validation packet from the set of second validation packets in a data packet processing pipeline prior to executing the code representing instructions to cause the processor to send each second validation packet from the set of second validation packets to its associated output port.

14. An apparatus, comprising:

a hash engine of a switch module of a multi-stage switch, the hash engine configured to receive a plurality of validation packets defined based on the switch module receiving a single validation packet at an input port,

the hash engine configured to forward each validation packet from the plurality of validation packets to a different output port from a plurality of output ports based on an output of a hash function, a header portion of each validation packet from the plurality of validation packets being an input to the hash function, the header portion of each validation packet from the plurality of validation packets being defined from a reverse hash table lookup having an association between (1) a hash function input that results in a hash function output of an identifier of an output port from the plurality of output ports and (2) the identifier of that output port from the plurality of output ports.

15. The apparatus of claim 14, wherein a number of validation packets from the plurality of validation packets is equal to a number of output ports from the plurality of output ports.

16. The apparatus of claim 14, wherein the header portion of each validation packet from the plurality of validation packets is an internet protocol (IP) 5-tuple.

17. The apparatus of claim 14, wherein the switch module is part of a first stage of the multi-stage switch, each output port from the plurality of output ports being operatively coupled to a switch module of a second stage of the multi-stage switch.

18. The apparatus of claim 14, wherein the multi-stage switch is a Clos network.

19. The apparatus of claim 14, wherein each validation packet from the plurality of validation packets is configured to verify a different data path through the multi-stage switch between a source edge device and a destination edge device.

20. The apparatus of claim 14, wherein a value of the header portion of each validation packet from the plurality of validation packets is different from a value of the header portion of each remaining validation packet from the plurality of validation packets.