Managing routing information for tunnel endpoints in overlay networks

• US 9,686,180 B2
• Filed: 09/04/2014
• Issued: 06/20/2017
• Est. Priority Date: 11/05/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Edsall, Thomas J., Sinha, Satyam, Yadav, Navindra, Doddapaneni, Krishna, Matus, Francisco M., Chu, Kit Chiu
• Primary Examiner(s): Mered, Habte
• Application Number:
  US14/477,791
• Publication Number:
  US 20150124822A1
• Time in Patent Office: 1,020 Days
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• 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 12/4645 Details on frame tagging routing of packets H04L45/00; support for virtual LAN H04L49/354
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/74 : Address processing for routing
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 : using hashing
• CPC Class Codes: H04L 47/125 : by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 49/70 : Virtual switches
• CPC Class Codes: H04L 51/214 : using selective forwarding
• CPC Class Codes: H04L 61/2503 : Translation of Internet protocol [IP] addresses
• CPC Class Codes: H04L 61/2592 : using tunnelling or encapsulation
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers

Abstract

Systems, methods, and non-transitory computer-readable storage media for managing routing information in overlay networks. A first tunnel endpoint in an overlay network may receive an encapsulated packet from a second tunnel endpoint. The encapsulated packet may have been encapsulated at the second tunnel endpoint based on another packet originating from a source host that is associated with the second tunnel endpoint. The encapsulated packet can include a source host address for the source host and a source tunnel endpoint address for the second tunnel endpoint. The first tunnel endpoint can then update a lookup table based on an association between the source host address and the source tunnel endpoint address.

Claims

1. A method comprising:

receiving, at a first tunnel endpoint in an overlay network, an encapsulated packet from a second tunnel endpoint, the encapsulated packet having been encapsulated at the second tunnel endpoint based on a packet originating from a source host associated with the second tunnel endpoint, wherein the encapsulated packet comprises a source host address for the source host and a source tunnel endpoint address for the second tunnel endpoint; and

updating a lookup table at the first tunnel endpoint based on an association between the source host address and the source tunnel endpoint address, wherein updating the lookup table further comprises;

determining whether an entry for the source host address exists in the lookup table, and

when the entry for the source host address exists in the lookup table and the source host address is associated with a tunnel endpoint address different from the source tunnel endpoint address in the lookup table, updating the entry for the source host address in the lookup table based on the association between the source host address and the source tunnel endpoint address.

2. The method of claim 1, wherein the source tunnel endpoint address is an Internet protocol (IP) address and the source host address is a media access control (MAC) address.

3. The method of claim 1, wherein the overlay network is a virtual extensible local area network (VXLAN) and the tunnel endpoint is a virtual tunnel endpoint (VTEP).

4. The method of claim 1, wherein the encapsulated packet further comprises a destination host address for a destination host, the method further comprising:

based on the destination host address, determining whether the destination host is associated with the first tunnel endpoint,

wherein the lookup table is updated only when it is determined that the destination host is associated with the first tunnel endpoint.

5. The method of claim 4, wherein the encapsulated packet is one of a broadcast packet or a multicast packet.

6. The method of claim 1, wherein updating the lookup table further comprises:

when the entry for the source host address does not exist in the lookup table, inserting a new entry in the lookup table based on the association between the source host address and the source tunnel endpoint address.

7. The method of claim 1, wherein updating the lookup table further comprises:

when the entry for the source host address exists in the lookup table and the source host address is associated with the source tunnel endpoint address in the lookup table, not modifying the entry for the source host address in the lookup table.

8. The method of claim 1, wherein updating the lookup table further comprises:

setting a hit bit in the lookup table, the hit bit being associated with the source host address.

9. The method of claim 8, further comprising:

performing maintenance on the lookup table by;

determining whether the hit bit is set;

when it is determined that the hit bit is not set, deleting the entry for the source host address from the lookup table; and

clearing the hit bit.

10. The method of claim 9, wherein the maintenance is performed on the lookup table periodically according to a predetermined schedule.

11. The method of claim 1, further comprising:

receiving, at the first tunnel endpoint, an outbound packet from a host associated with the first tunnel endpoint, the outbound packet comprising a destination host address;

based on the lookup table, determining a destination tunnel endpoint address that is associated with the destination host address;

transmitting the outbound packet from the first tunnel endpoint to the destination tunnel endpoint address.

12. The method of claim 11, further comprising:

prior to transmitting the outbound packet, encapsulating the outbound packet with an overlay network header.

13. The method of claim 11, wherein the destination tunnel endpoint address is an IP address and the destination host address is a MAC address.

14. A system comprising:

a processor; and

a non-transitory computer-readable storage medium storing instructions which, when executed by the processor, cause the processor to perform operations comprising;

receiving, at a first tunnel endpoint in an overlay network, a packet from a source host associated with the first tunnel endpoint, the packet comprising a destination host address, a source host address and a source tunnel endpoint;

based on a lookup table, determining a destination tunnel endpoint address that is associated with the destination host address, wherein the first tunnel endpoint is configured to update the lookup table with an association between a host address and a tunnel endpoint address by determining whether an entry of the source host address exists in the lookup table and the source host address is associated with a tunnel endpoint address different from the source tunnel endpoint address in the lookup table, and updating the entry of the source host address in the lookup table based on the association between the source host address and the source tunnel address when the first tunnel endpoint receives an incoming encapsulated packet comprising the source host address and the tunnel endpoint address;

encapsulating the packet with a header comprising the destination tunnel endpoint address to yield an encapsulated packet; and

transmitting the encapsulated packet from the first tunnel endpoint to the destination tunnel endpoint address.

15. The system of claim 14, wherein the destination tunnel endpoint address is an IP address and the destination host address is a MAC address.

16. The system of claim 14, wherein the overlay network is a VXLAN and the tunnel endpoint is a VTEP.

17. The system of claim 14, wherein the first tunnel endpoint is further configured to update the lookup table with the association between the host address and the tunnel endpoint address only when the incoming encapsulated packet, received by the first tunnel endpoint, is destined for a host that is associated with the first tunnel endpoint.

18. A non-transitory computer-readable storage medium storing instructions which, when executed by a processor, cause the processor to perform operations comprising:

receiving, at a first tunnel endpoint in an overlay network, an encapsulated packet from a second tunnel endpoint, the encapsulated packet having been encapsulated at the second tunnel endpoint based on a packet originating from a source host associated with the second tunnel endpoint, wherein the encapsulated packet comprises a source host address for the source host, a source tunnel endpoint address for the second tunnel endpoint, and a destination host address for a destination host;

based on the destination host address, determining whether the destination host is associated with the first tunnel endpoint, and

when it is determined that the destination host is associated with the first tunnel endpoint, updating a lookup table at the first tunnel endpoint based on an association between the source host address and the source tunnel endpoint address, wherein updating the lookup table further comprises;

determining whether an entry of the source host address exists in the lookup table and when the source host address is associated with a tunnel end point address different from the source tunnel endpoint address in the lookup table, updating the entry of the source host address in the lookup table based on the association between the source host address and the source tunnel address.