Connectivity segment coloring

• US 9,602,392 B2
• Filed: 12/18/2013
• Issued: 03/21/2017
• Est. Priority Date: 12/18/2013
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Tessmer, Alexander, Singh, Ram Dular, Chandrashekhar, Ganesan
• Primary Examiner(s): Beharry, Noel
• Assistant Examiner(s): Mak, Rodrick
• Application Number:
  US14/133,524
• Publication Number:
  US 20150172132A1
• Time in Patent Office: 1,189 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• 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/037 Routes obligatorily traversing service-related nodes
• CPC Class Codes: H04L 45/16 Multipoint routing

Abstract

A novel method for fully utilizing the multicast or broadcast capability of a physical network is provided. The method identifies segments of the network within which broadcast traffic, multicast traffic, or traffic to unknown recipients (BUM traffic) is allowed or enabled. The identified segment encompasses parts of the network that the BUM traffic is able reach while excluding parts of the network nodes that the BUM traffic is unable to reach. Each identified segment includes network nodes that are interconnected by physical network hardware that supports BUM traffic. The method identifies multiple BUM traffic segments in a given network that each supports its own BUM traffic. The different BUM traffic segments are interconnected by physical network hardware that does not support BUM network traffic. Each identified segment is assigned an identifier that uniquely distinguishes the identified segment from other identified segments.

Claims

1. A network comprising:

a group of network nodes, each network node in the group having connectivity under a particular protocol with other network nodes in the group, each network node having a unique node identifier, wherein the network nodes in the group query each other for a group identifier for identifying said group, wherein each network node in the group that fails to receive a response before a time-out condition for its query generates a candidate group identifier, wherein the generated candidate group identifier of a particular network node is adopted as the group identifier when the particular network node responds to queries from other network nodes in the group, wherein said query and response are conducted by using the connectivity under the particular protocol; and

a set of network connections for allowing communication between nodes in the group with nodes not in the group, wherein the set of network connections does not support the connectivity under the particular protocol.

2. The network of claim 1, wherein a particular network node in the group of network nodes having a highest ranking unique node identifier generates the adopted group identifier.

3. The network of claim 2, wherein the generated group identifier is based on the subnet address of the particular network node.

4. The network of claim 1, wherein the unique node identifier of a network node is the network node'"'"'s media access control (MAC) address.

5. The network of claim 1, wherein using the connectivity under the particular protocol comprises sending the query as a broadcast message.

6. The network of claim 5, wherein using the connectivity under the particular protocol comprises sending the response as a broadcast message.

7. The network of claim 1, wherein the connectivity supports broadcast, unknown unicast, or multicast (BUM) network traffic.

8. The network of claim 7, wherein the set of network connections does not support BUM network traffic.

9. A method for operating a network, the network comprising a group of network nodes, each network node in the group having connectivity under a particular protocol with other network nodes in the group, each network node having a unique node identifier, the method comprising:

at a node in the group, querying other nodes of the network for a group identifier for identifying said group; and

when the node fails to receive a response before a time-out condition, generating a candidate group identifier,

wherein a particular candidate group identifier generated by a particular network node in the group is adopted as the group identifier when the particular network node responds to queries from other network nodes in the group,

wherein the query and response are conducted by using the connectivity under the particular protocol,

wherein the network further comprises a set of network connections for allowing communication between nodes in the group with nodes not in the group, wherein the set of network connections does not support the connectivity under the particular protocol.

10. The method of claim 9, wherein the particular network node in the group of network nodes has a highest ranking unique node identifier.

11. The method of claim 10, wherein the generated group identifier is based on the subnet address of the particular network node.

12. The method of claim 9, wherein the unique node identifier of a network node is the network node'"'"'s media access control (MAC) address.

13. The method of claim 9, wherein using the connectivity under the particular protocol comprises sending the query as a multicast message.

14. The method of claim 13, wherein using the connectivity under the particular protocol comprises sending the response as a multicast message.

15. The method of claim 9, wherein the connectivity supports broadcast, unknown unicast, or multicast (BUM) network traffic.

16. The method of claim 15, wherein the set of network connections does not support BUM network traffic.

17. A non-transitory computer readable medium storing a computer program for execution by one or more processing units, the program for operating a network, the network comprising a group of network nodes, each network node in the group having connectivity under a particular protocol with other network nodes in the group, each network node having a unique node identifier, the computer program comprising sets of instructions for:

at a node in the group, querying other nodes of the network for a group identifier for identifying said group; and

when the node fails to receive a response before a time-out condition, generating a candidate group identifier,

wherein a particular candidate group identifier generated by a particular network node in the group is adopted as the group identifier when the particular network node responds to queries from other network nodes in the group,

wherein the query and response are conducted by using the connectivity under the particular protocol,

wherein the network further comprises a set of network connections for allowing communication between nodes in the group with nodes not in the group, wherein the set of network connections does not support the connectivity under the particular protocol.

18. The non-transitory computer readable medium of claim 17, wherein the particular network node in the group of network nodes has a highest ranking unique node identifier.

19. The non-transitory computer readable medium of claim 18, wherein the generated group identifier is based on the subnet address of the particular network node.

20. The non-transitory computer readable medium of claim 17, wherein the unique node identifier of a network node is the network node'"'"'s media access control (MAC) address.

21. The non-transitory computer readable medium of claim 17, wherein using the connectivity under the particular protocol comprises sending the query as one of a broadcast, multicast, or unknown unicast (BUM) message.

22. The non-transitory computer readable medium of claim 21, wherein using the connectivity under the particular protocol comprises sending the response as one of a broadcast, multicast, or unknown unicast (BUM) message.

23. The non-transitory computer readable medium of claim 17, wherein the connectivity supports broadcast, unknown unicast, or multicast (BUM) network traffic.

24. The non-transitory computer readable medium of claim 23, wherein the set of network connections does not support BUM network traffic.