Fault tolerant managed switching element architecture

• US 8,913,483 B2
• Filed: 08/26/2011
• Issued: 12/16/2014
• Est. Priority Date: 07/06/2010
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Pfaff, Benjamin L., Jackson, Ethan J., Koponen, Teemu, Thakkar, Pankaj
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US13/218,468
• Publication Number:
  US 20130058208A1
• Time in Patent Office: 1,208 Days
• Field of Search: 370/217, 370/231, 370/235, 370254-256, 370/390, 370/400, 370406-408, 370/432, 370/218, 370/392, 370/428, 709/223, 709/224, 709/238, 709/239, 709/252, 709/201, 711/216, 711/202, 707/698, 707/700, 714/4.1
• US Class Current: 370/218
• CPC Class Codes: G06F 11/07 Responding to the occurrence of a fault, e.g. fault tolerance
• CPC Class Codes: G06F 15/17312 Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion routing on a LAN H04L45/00
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/036 Updating the topology between route computation elements, e.g. between OpenFlow controllers
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/76 Routing in software-defined topologies, e.g. routing between virtual machines
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 49/00 Packet switching elements
• CPC Class Codes: H04L 49/1546 using pipelined operation
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/70 : Virtual switches
• CPC Class Codes: H04L 61/5007 : Internet protocol [IP] addresses

Abstract

In a hierarchical switching architecture that includes at least one lower level managed switching element that connects to several higher level managed switching elements, some embodiments provide a method of identifying a higher level managed switching element to which the lower level managed switching element forwards a packet for further processing. The method computes a value based on a set of attributes of the packet. The method identifies a record from a hierarchy traversal table based on the computed value. The record specifies (1) a first higher level managed switching element as a primary higher level managed switching element and (2) a second higher level managed switching element as a secondary higher level managed switching element. The primary and secondary higher level managed switching elements are for forwarding the packet for further processing. The method forwards the packet to one of the higher level managed switching elements.

Claims

1. In a hierarchical switching architecture comprising at least one lower level managed switching element (LLMSE) that connects to a plurality of higher level managed switching elements (HLMSEs), a method of identifying a HLMSE to which the LLMSE forwards a packet for further processing, the method comprising:

performing a hash function based on the packet to generate a hash value;

identifying a record for a particular HLMSE from a hierarchy traversal table by comparing the hash value against a range list that matches ranges of hash values to HLMSEs, the record specifying a first physical HLMSE as a primary HLMSE for the particular HLMSE and a second physical HLMSE as a secondary HLMSE for the particular HLMSE, said HLMSEs for receiving the packet from the LLMSE for processing when the LLMSE does not have a flow entry to forward the packet to a destination of the packet;

determining whether the first physical HLMSE specified by the record has failed;

when the first physical HLMSE has not failed, forwarding the packet to the first physical HLMSE; and

when the first physical HLMSE has failed, forwarding the packet to the second physical HLMSE.

2. The method of claim 1, wherein performing the hash function is based on a set of fields of the packet.

3. The method of claim 2, wherein the set of fields of the packet includes a source media access control (MAC) address.

4. The method of claim 2, wherein the set of fields of the packet includes a destination media access control (MAC) address.

5. The method of claim 2, wherein the set of fields of the packet includes a source Internet Protocol (IP) address.

6. The method of claim 2, wherein the set of fields of the packet includes a destination Internet Protocol (IP) address.

7. The method of claim 1 further comprising:

receiving information associated with a third physical HLMSE; and

when the first physical HLMSE has failed, updating the identified record of the hierarchy traversal table by specifying the third physical HLMSE as the primary HLMSE for the record.

8. The method of claim 1 further comprising:

receiving information associated with a third physical HLMSE; and

when the first physical HLMSE has failed, updating the hierarchy traversal table by;

specifying the second physical HLMSE as the primary HLMSE for the record; and

specifying the third physical HLMSE as the secondary HLMSE for the record.

9. The method of claim 1, wherein the record is a first record, wherein the first physical HLMSE that is specified as the primary HLMSE for the first record is specified as the secondary HLMSE for a second record of the hierarchy traversal table.

10. The method of claim 9, wherein the packet is a first packet, wherein the method further comprises identifying the second record for a second different packet from the LLMSE.

11. The method of claim 1 further comprising determining that the packet needs further processing by a HLMSE, wherein the record is identified in order to identify the particular HLMSE for processing the packet forwarded by the LLMSE.

12. The method of claim 11, wherein the packet is determined to need further processing when the packet is a multi-recipient packet.

13. The method of claim 12, wherein the multi-recipient packet is a broadcast packet.

14. The method of claim 12, wherein the multi-recipient packet is a multicast packet.

15. A non-transitory machine readable medium storing a program for execution by at least one processing unit of a managed edge switching element (MESE) that connects to a plurality of managed non-edge switching elements (MNESEs) in a hierarchical switching architecture, the program for identifying a MNESE to which the MESE forwards a packet for further processing, the program comprising sets of instructions for:

performing a hash function based on the packet to generate a hash value;

identifying a record for a particular MNESE from a hierarchy traversal table by comparing the hash value against a range list that matches ranges of hash values to MNESEs, the record specifying a first physical MNESE as a primary MNESE and a second physical MNESE as a secondary MNESE for the particular MNESE, said MNESEs for receiving the packet from the MESE for processing when the MESE does not have a flow entry to forward the packet to a destination of the packet;

determining whether the first physical MNESE specified by the record has failed;

when the first physical MNESE has not failed, forwarding the packet to the first physical MNESE; and

when the first physical MNESE has failed, forwarding the packet to the second physical MNESE.

16. The non-transitory machine readable medium of claim 15, wherein the set of instructions for performing the hash function is based on a set of fields of the packet.

17. The non-transitory machine readable medium of claim 16, wherein the set of fields of the packet includes a source media access control (MAC) address.

18. The non-transitory machine readable medium of claim 16, wherein the set of fields of the packet includes a destination media access control (MAC) address.

19. The non-transitory machine readable medium of claim 16, wherein the set of fields of the packet includes a source Internet Protocol (IP) address.

20. The non-transitory machine readable medium of claim 16, wherein the set of fields of the packet includes a destination Internet Protocol (IP) address.

21. The non-transitory machine readable medium of claim 15, wherein the program further comprises sets of instructions for:

receiving information associated with a third physical MNESE; and

when the first physical MNESE has failed, specifying the third physical MNESE as a primary MNESE to replace the failed first physical MNESE.

22. The non-transitory machine readable medium of claim 15, wherein the program further comprises sets of instructions for:

receiving information associated with a third physical MNESE; and

when the first physical MNESE has failed, updating the hierarchy traversal table by;

specifying the second physical MNESE as the primary MNESE for the record; and

specifying the third physical MNESE as the secondary MNESE for the record.

23. The non-transitory machine readable medium of claim 15, wherein the record is a first record, wherein the first physical MNESE that is specified as the primary MNESE for the first record is specified as the secondary MNESE for a second record of the hierarchy traversal table.

24. The non-transitory machine readable medium of claim 23, wherein the packet is a first packet, wherein the program further comprises sets of instructions for identifying the second record for a second different packet from the MESE.

25. The non-transitory machine readable medium of claim 15, wherein the program further comprises a set of instructions for determining that the packet needs further processing by a MNESE, wherein the record is identified in order to identify the particular MNESE for processing the packet forwarded by the MESE.

26. The non-transitory machine readable medium of claim 25, wherein the packet is determined to need further processing when the packet is a multi-recipient packet.

27. The non-transitory machine readable medium of claim 26, wherein the multi-recipient packet is a broadcast packet.

28. The non-transitory machine readable medium of claim 26, wherein the multi-recipient packet is a multicast packet.