Method and apparatus for robust packet distribution among hierarchical managed switching elements

• US 8,964,528 B2
• Filed: 08/26/2011
• Issued: 02/24/2015
• Est. Priority Date: 07/06/2010
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Casado, Martin, Koponen, Teemu, Thakkar, Pankaj, Lambeth, W. Andrew, Yip, Alexander, Amidon, Keith E., Ingram, Paul S.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US13/218,470
• Publication Number:
  US 20130058229A1
• Time in Patent Office: 1,278 Days
• Field of Search: 370/235, 370/256, 370/396, 370/397, 370/400, 370406-409, 370/428, 370/218, 370/392, 709/230, 709/238, 709/252, 709/201, 711/202, 711/216, 707/698, 707/700, 714/4.1
• US Class Current: 370/218
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

For a network that includes several managed edge switching elements and several managed non-edge switching elements that are for implementing a logical switching element, some embodiments provide a method of distributing packet processing across the several managed non-edge switching elements. The method receives a packet for processing through the logical switching element. Based on a determination that the packet needs to be processed by a managed non-edge switching element, the method determines a particular managed non-edge switching element of the several managed non-edge switching elements to forward the packet. The method forwards the packet to the particular managed non-edge switching element for the particular managed non-edge switching element to process the packet.

Claims

1. For a managed edge switching element in a network comprising a plurality of managed edge switching elements and a plurality of managed non-edge switching elements, a method of distributing packet processing across the plurality of managed non-edge switching elements, the method comprising:

receiving a packet at a sort of the managed edge switching element;

determining whether the packet needs to be processed by a managed non-edge switching element;

based on a determination that the packet needs to be processed by a managed non-edge switching element, identifying a particular managed non-edge switching element of the plurality of managed non-edge switching elements to which to forward the packet by;

performing a hash function based on the packet in order to generate a hash value for identifying the particular managed non-edge switching element; and

mapping the hash value against a range list comprising a plurality of hash value ranges that corresponds to the plurality of managed non-edge switching elements to identify a value that identifies the particular managed non-edge switching element; and

forwarding the packet to the particular managed non-edge switching element for the particular managed non-edge switching element to process the packet.

2. The method of claim 1, wherein each managed edge switching element of the plurality of managed edge switching elements is directly coupled to each of the plurality of managed non-edge switching elements.

3. The method of claim 1, wherein each managed non-edge switching element comprises a forwarding table that includes a set of forwarding entries for forwarding packets, including the received packet, in the network.

4. The method of claim 3, wherein the forwarding table of each managed non-edge switching element includes the same set of forwarding entries.

5. The method of claim 1, wherein the hash function is for generating a plurality of hash values that are each for identifying one managed non-edge switching element of the plurality of managed non-edge switching elements.

6. The method of claim 5, wherein the hash function is a first hash function, the method further comprising identifying a second hash function for generating a second plurality of hash values that are each for identifying a managed non-edge switching element of the plurality of managed non-edge switching elements.

7. The method of claim 6, wherein the second hash function is identified when a new managed non-edge switching element is added to the network, wherein the second hash function is further for generating a hash value for identifying the new managed non-edge switching element.

8. The method of claim 6, wherein the second hash function is identified when a failed managed non-edge switching element in the plurality of managed non-edge switching elements is removed from the network, wherein each of the second plurality of generated hash values are for identifying a managed non-edge switching element of the plurality of managed non-edge switching elements other than the failed managed non-edge switching element.

9. The method of claim 1, wherein the packet is a broadcast packet.

10. The method of claim 1, wherein the packet is a multicast packet.

11. The method of claim 1, wherein the plurality of managed non-edge switching elements comprises a plurality of software switching elements.

12. The method of claim 1, wherein the plurality of managed non-edge switching elements comprises a plurality of virtual switching elements.

13. The method of claim 1, wherein each managed edge switching element in the plurality of managed edge switching elements is directly coupled to at least one end host.

14. The method of claim 1, wherein each managed non-edge switching element in the plurality of managed non-edge switching elements is not directly coupled to an end host.

15. The method of claim 1, wherein determining whether the packet needs to be processed by a managed non-edge switching element comprises determining that the packet is an unknown packet.

16. The method of claim 15 further comprising performing a lookup on the packet based on a forwarding table, wherein the packet is determined as an unknown packet when the forwarding table does not include an entry that specifies an end host identifier that is specified in the packet.

17. The method of claim 16, wherein the end host identifier is a media access control (MAC) address.

18. For a managed edge switching element of a plurality of managed edge switching elements in a network further comprising a plurality of managed non-edge switching elements, a non-transitory computer readable medium storing a program which when executed by at least one processing unit distributes packet processing across the plurality of managed non-edge switching elements, the program comprising sets of instructions for:

receiving a packet at a sort of the managed edge switching element;

determining whether the packet needs to be processed by a managed non-edge switching element;

identifying, based on a determination that the packet needs to be processed, a particular managed non-edge switching element of the plurality of managed non-edge switching elements to which to forward the packet by;

performing a hash function based on the packet in order to generate a hash value for identifying the particular managed non-edge switching element; and

mapping the hash value against a range list comprising a plurality of hash value ranges that corresponds to the plurality of managed non-edge switching elements to identify a value that identifies the particular managed non-edge switching element; and

forwarding the packet to the particular managed non-edge switching element for the particular managed non-edge switching element to process the packet.

19. The non-transitory computer readable medium of claim 18, wherein each managed edge switching element of the plurality of managed edge switching elements is directly coupled to each of the plurality of managed non-edge switching elements.

20. The non-transitory computer readable medium of claim 18, wherein each managed non-edge switching element comprises a forwarding table that includes a set of forwarding entries for forwarding packets, including the received packet, in the network.

21. The non-transitory computer readable medium of claim 20, wherein the forwarding table of each managed non-edge switching element includes the same set of forwarding entries.

22. The non-transitory computer readable medium of claim 18, wherein the hash function is for generating a plurality of hash values that are each for identifying one managed non-edge switching element of the plurality of managed non-edge switching elements.

23. The non-transitory computer readable medium of claim 22, wherein the hash function is a first hash function, wherein the program further comprises a set of instructions for identifying a second hash function for generating a second plurality of hash values that are each for identifying a managed non-edge switching element of the plurality of managed non-edge switching elements.

24. The non-transitory computer readable medium of claim 23, wherein the second hash function is identified when a new managed non-edge switching element is added to the network, wherein the second hash function is further for generating a hash value for identifying the new managed non-edge switching element.

25. The non-transitory computer readable medium of claim 23, wherein the second hash function is identified when a failed managed non-edge switching element in the plurality of managed non-edge switching elements is removed from the network, wherein each of the second plurality of generated hash values are for identifying a managed non-edge switching element of the plurality of managed non-edge switching elements other than the failed managed non-edge switching element.

26. The non-transitory computer readable medium of claim 18, wherein the packet is a broadcast packet.

27. The non-transitory computer readable medium of claim 18, wherein the packet is a multicast packet.

28. The non-transitory computer readable medium of claim 18, wherein the plurality of managed non-edge switching elements comprises a plurality of software switching elements.

29. The non-transitory computer readable medium of claim 18, wherein the plurality of managed non-edge switching elements comprises a plurality of virtual switching elements.

30. The non-transitory computer readable medium of claim 18, wherein each managed edge switching element in the plurality of managed edge switching elements is directly coupled to at least one end host.

31. The non-transitory computer readable medium of claim 18, wherein each managed non-edge switching element in the plurality of managed non-edge switching elements is not directly coupled to an end host.

32. The non-transitory computer readable medium of claim 18, wherein the set of instructions for determining whether the packet needs to be processed by a managed non-edge switching element further comprises a set of instructions for determining that the packet is an unknown packet.

33. The non-transitory computer readable medium of claim 32, wherein the program further comprises a set of instructions for performing a lookup on the packet based on a forwarding table, wherein the packet is determined as an unknown packet when the forwarding table does not include an entry that specifies an end host identifier that is specified in the packet.

34. The non-transitory computer readable medium of claim 33, wherein the end host identifier is a media access control (MAC) address.