Method and system for routing packets

• US 9,118,604 B2
• Filed: 12/09/2013
• Issued: 08/25/2015
• Est. Priority Date: 11/14/2013
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Arista Networks, Inc.
• Inventors: Brar, Jagwinder Singh, Premji, Ariff
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): LOPATA, ROBERT J
• Application Number:
  US14/100,727
• Publication Number:
  US 20150131654A1
• Time in Patent Office: 624 Days
• Field of Search: 370/351, 370/389, 370/392
• US Class Current: 1/1
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 45/72 Routing based on the source address
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/748 using longest matching prefix

Abstract

A system for routing packets that includes leaf network devices, spine network devices, and a border gateway protocol controller to perform a method for routing packets in a network. The method includes receiving packets at a leaf device and, using the destination IP address of the packet to determine to which spine network device the packet is to be sent. The spine network devices each include a non-overlapping portion of a routing table. The spine network devices include functionality to determine a route for the packet based on its destination IP address, to determine to which leaf network device the packet is to be sent, and to send the packet to the discovered leaf network device. The leaf network device that receives the packet includes functionality to, based on the destination MAC address of the packet, determine out of which leaf network device interface to send the packet.

Claims

1. A method for routing packets, the method comprising:

receiving, at an interface of a first network device of a plurality of network devices in a leaf tier, a first packet, wherein the first packet comprises a first destination Internet Protocol (IP) address and wherein each of the plurality of network devices comprises a supernet table and a non-overlapping portion of a routing table;

determining, using the first destination IP address and the supernet table, a first IP address of a second network device to which the packet is to be sent, wherein the second network device is one of the plurality of network devices in the leaf tier, wherein the supernet table comprises a plurality of entries, wherein each of the plurality of entries comprises a non-overlapping IP address range and specifies a corresponding one of the plurality of network devices in the leaf tier, and wherein the non-overlapping portion of the routing table on the second network device comprises a route for the first packet;

determining, by the first network device, a first media access control (MAC) address of the second network device using the first IP address;

rewriting, by the first network device, the first packet to obtain a first rewritten packet, wherein the first rewritten packet comprises the first MAC address as a destination MAC address of the first rewritten packet and the first destination IP address;

sending the first rewritten packet to a third network device, wherein the third network device is not in the leaf tier;

determining, by the third network device using the destination MAC address of the first rewritten packet, to forward the first rewritten packet from the third network device to the second network device;

sending the first rewritten packet to the second network device;

performing, by the second network device using the destination MAC address of the first rewritten packet, a first MAC pointer table lookup to determine that a first routing table lookup is to be performed using the first destination IP address of the first rewritten packet;

performing, by the second network device, the first routing table lookup, wherein the first routing table lookup comprises using the non-overlapping portion of the routing table on the second network device to determine a second IP address corresponding to a first external network device to which the packet is to be sent;

determining, by the second network device, a second MAC address of the first external network device using the second IP address;

rewriting the first rewritten packet to obtain a second rewritten packet, by the second network device using the second MAC address, wherein the second rewritten packet comprises the second MAC address as a destination MAC address of the second rewritten packet and the first destination IP address;

sending the second rewritten packet from a first interface on the second network device to the first external network device, wherein the first interface is associated with the second MAC address.

2. The method of claim 1, further comprising:

receiving, at the interface of the first network device, a second packet, wherein the second packet comprises a second destination IP address;

performing, by the first network device, a second routing table lookup, wherein the second routing table lookup comprises using the non-overlapping portion of the routing table on the first network device to determine a third IP address corresponding to a second external network device to which the second packet is to be sent;

determining, by the first network device using the third IP address, a third MAC address corresponding to the second network device;

rewriting the second packet to obtain a third rewritten packet, wherein the third rewritten packet comprises the third MAC address as the destination MAC address of the third rewritten packet and the second destination IP address;

sending the third rewritten packet to the third network device;

determining, by the third network device using the destination MAC address of the third rewritten packet, to forward the third rewritten packet from the third network device to the second network device;

sending the third rewritten packet to the second network device;

performing, by the second network device using the destination MAC address of the third rewritten packet, a second MAC pointer table lookup to determine a fourth MAC address corresponding to the second external network device;

rewriting the third rewritten packet to obtain a fourth rewritten packet, wherein the fourth rewritten packet comprises the fourth MAC address as the destination MAC address of the fourth rewritten packet and the second destination IP address;

sending the fourth rewritten packet from a second interface of the second network device, wherein the second interface of the second network device is associated with the fourth MAC address.

3. The method of claim 1, further comprising:

receiving, at the interface of the first network device, a second packet, wherein the second packet comprises a second destination IP address;

determining, using the second destination IP address and the supernet table, the first IP address of the second network device to which the packet is to be sent, wherein the second network device is one of the plurality of network devices in the leaf tier and wherein the non-overlapping portion of the routing table on the second network device comprises a route for the second packet;

determining, by the first network device, the first MAC address of the second network device using the first IP address;

rewriting, by the first network device, the second packet to obtain a third rewritten packet, wherein the third rewritten packet comprises the first MAC address as the destination MAC address of the third rewritten packet and the second destination IP address;

sending the third rewritten packet to the third network device;

determining, by the third network device using the destination MAC address of the third rewritten packet, to forward the third rewritten packet from the third network device to the second network device;

sending the third rewritten packet to the second network device;

performing, by the second network device using the destination MAC address of the third rewritten packet, a second MAC pointer table lookup to determine that a second routing table lookup is to be performed using the second destination IP address of the third rewritten packet;

performing, by the second network device, the second routing table lookup, wherein the second routing table lookup comprises using the non-overlapping portion of the routing table on the second network device to determine a third IP address corresponding to a second external network device to which the third rewritten packet is to be sent;

determining, by the second network device using the third IP address, a third MAC address corresponding to a fourth network device, wherein the fourth network device is one of the plurality of network devices in the leaf tier and wherein the fourth network device comprises an interface of the fourth network device connected to the second external network device;

rewriting the third rewritten packet to obtain a fourth rewritten packet, wherein the fourth rewritten packet comprises the third MAC address as the destination MAC address of the fourth rewritten packet and the second destination IP address;

sending the fourth rewritten packet to the third network device;

determining, by the third network device using the destination MAC address of the fourth rewritten packet, to forward the fourth rewritten packet from the third network device to the fourth network device;

sending the fourth rewritten packet to the fourth network device;

performing, by the fourth network device using the destination MAC address of the fourth rewritten packet, a third MAC pointer table lookup to determine a fourth MAC address corresponding to the second external network device;

rewriting the fourth rewritten packet to obtain a fifth rewritten packet, wherein the fifth rewritten packet comprises the fourth MAC address as the destination MAC address of the fifth rewritten packet and the second destination IP address;

sending the fifth rewritten packet from the interface of the fourth network device, wherein the interface of the fourth network device is associated with the fourth MAC address.

4. The method of claim 1, further comprising:

receiving, at the interface of the first network device, a second packet, wherein the second packet comprises a second destination IP address;

performing, by the first network device, a second routing table lookup, wherein the second routing table lookup comprises using the non-overlapping portion of the routing table on the first network device to determine a third IP address corresponding to a second external network device to which the second packet is to be sent;

determining, by the first network device using the third IP address, a third MAC address corresponding to a second external network device;

rewriting the second packet to obtain a third rewritten packet, wherein the third rewritten packet comprises the third MAC address as the destination MAC address of the third rewritten packet and the second destination IP address;

sending the third rewritten packet from a second interface of the first network device, wherein the second interface of the first network device is associated with the third MAC address.

5. The method of claim 1, further comprising:

receiving, at the integrated composite router, routing table information from a plurality of external network devices, wherein routing table information comprises routes;

constructing, from the received routing table information, the routing table;

distributing one of the non-overlapping portions of the routing table to each of the plurality of network devices in the leaf tier.

6. The method of claim 1, wherein performing the first routing table lookup further comprises determining a longest prefix match (LPM) for the first destination IP address.

7. The method of claim 1, wherein the routing table is a full Internet routing table.

8. An integrated composite router, comprising:

a plurality of leaf network devices comprising a first network device and a second network device, wherein the leaf network devices are connected to a third network device and wherein each of the plurality of leaf network devices comprise a supernet table and a non-overlapping portion of a routing table;

wherein the first network device is configured to;

receive, at an interface of the first network device, a first packet, wherein the first packet comprises a first destination Internet Protocol (IP) address;

determine, using the first destination IP address and a supernet table of the first network device, a first IP address of the second network device to which the packet is to be sent, wherein the supernet table of the first network device comprises a plurality of entries, wherein each of the plurality of entries comprises a non-overlapping IP address range and specifies a corresponding one of the plurality of leaf network devices;

determine, by the first network device, a first media access control (MAC) address of the second network device using the first IP address;

rewrite, by the first network device, the first packet to obtain a first rewritten packet, wherein the first rewritten packet comprises the first MAC address as a destination MAC address of the first rewritten packet and the first destination IP address;

send the first rewritten packet to a third network device, wherein the third network device is not in the leaf tier;

wherein the second network device comprises the non-overlapping portion of the routing table on the second network device which comprises a route for the first packet, and wherein the second network device is configured to;

perform, using the destination MAC address of the first rewritten packet, a first MAC pointer table lookup to determine that a first routing table lookup is to be performed using the first destination IP address of the first rewritten packet;

perform the first routing table lookup, wherein the first routing table lookup comprises using the non-overlapping portion of the routing table on the second network device to determine a second IP address corresponding to a first external network device to which the packet is to be sent;

determine a second MAC address of the first external network device using the second IP address;

rewrite the first rewritten packet to obtain a second rewritten packet, using the second MAC address, wherein the second rewritten packet comprises the second MAC address as a destination MAC address of the second rewritten packet and the first destination IP address;

send the second rewritten packet from a first interface on the second network device to the first external network device, where the first interface on the second network device is associated with the second MAC address; and

wherein the third network device comprises a forwarding table and is configured to;

determine, using the destination MAC address of the first rewritten packet and the forwarding table, to forward the first rewritten packet from the third network device to the second network device;

send the first rewritten packet to the second network device.

9. The integrated composite router of claim 8,

wherein the first network device is further configured to:

receive, at the interface of the first network device, a second packet, wherein the second packet comprises a second destination IP address;

perform, by the first network device, a second routing table lookup, wherein the second routing table lookup comprises using the non-overlapping portion of the routing table on the first network device to determine a third IP address corresponding to a second external network device to which the second packet is to be sent;

determine, by the first network device using the third IP address, a third MAC address corresponding to the second network device;

rewrite the second packet to obtain a third rewritten packet, wherein the third rewritten packet comprises the third MAC address as the destination MAC address of the third rewritten packet and the second destination IP address; and

send the third rewritten packet to the third network device;

wherein the second network device is further configured to;

perform, using the destination MAC address of the third rewritten packet, a second MAC pointer table lookup to determine a fourth MAC address corresponding to the second external network device;

rewrite the third rewritten packet to obtain a fourth rewritten packet, wherein the fourth rewritten packet comprises the fourth MAC address as the destination MAC address of the fourth rewritten packet and the second destination IP address; and

send the fourth rewritten packet from a second interface of the second network device, wherein the second interface of the second network device is associated with the fourth MAC address; and

wherein the third network device is further configured to;

determine, using the destination MAC address of the third rewritten packet, to forward the third rewritten packet from the third network device to the second network device; and

send the third rewritten packet to the second network device.

10. The integrated composite router of claim 8, further comprising a fourth network device of the plurality of leaf network devices;

and

wherein the first network device is further configured to;

receive, at the interface of the first network device, a second packet, wherein the second packet comprises a second destination IP address;

determine, using the second destination IP address and the supernet table, the first IP address of the second network device to which the packet is to be sent, wherein the second network device is one of the plurality of network devices in the leaf tier and wherein the non-overlapping portion of the routing table on the second network device comprises a route for the second packet;

determine, by the first network device, the first MAC address of the second network device using the first IP address;

rewrite, by the first network device, the second packet to obtain a third rewritten packet, wherein the third rewritten packet comprises the first MAC address as the destination MAC address of the third rewritten packet and the second destination IP address;

send the third rewritten packet to the third network device;

wherein the second network device is further configured to;

perform, using the destination MAC address of the third rewritten packet, a second MAC pointer table lookup to determine that a second routing table lookup is to be performed on the second destination IP address of the third rewritten packet;

perform the second routing table lookup, wherein the second routing table lookup comprises using the non-overlapping portion of the routing table on the second network device to determine a third IP address corresponding to a second external network device to which the third rewritten packet is to be sent;

determine, using the third IP address, a third MAC address corresponding to a fourth network device, wherein the fourth network device is one of the plurality of network devices in the leaf tier and wherein the fourth network device comprises an interface of the fourth network device connected to the second external network device;

rewrite the third rewritten packet to obtain a fourth rewritten packet, wherein the fourth rewritten packet comprises the third MAC address as the destination MAC address of the fourth rewritten packet and the second destination IP address;

send the fourth rewritten packet to the third network device;

wherein the third network device is further configured to;

determine, using the destination MAC address of the third rewritten packet, to forward the third rewritten packet from the third network device to the second network device;

send the third rewritten packet to the second network device;

determine, using the destination MAC address of the fourth rewritten packet, to forward the fourth rewritten packet from the third network device to the fourth network device;

send the fourth rewritten packet to the fourth network device; and

wherein the fourth network device is configured to;

perform, using the destination MAC address of the fourth rewritten packet, a third MAC pointer table lookup to determine a fourth MAC address corresponding to the second external network device;

rewrite the fourth rewritten packet to obtain a fifth rewritten packet, wherein the fifth rewritten packet comprises the fourth MAC address as the destination MAC address of the fifth rewritten packet and the second destination IP address;

send the fifth rewritten packet from the interface of the fourth network device, wherein the interface of the fourth network device is associated with the fourth MAC address.

11. The integrated composite router of claim 8, wherein the first network device, the second network device, and the third network device each comprise an application specific integrated circuit (ASIC).

12. The integrated composite router of claim 11, wherein the first network device, the second network device, and the third network device are integrated in a single physical device.

13. The integrated composite router of claim 11, wherein each of the ASICs is configured to perform the functionality of one selected from a group consisting of a layer two (L2) switch and a multi-layer switch.

14. The integrated composite router of claim 8, wherein the third network device is one of a plurality of spine network devices and wherein each of the network devices in the plurality of leaf network devices is connected to each of the devices in the plurality of spine devices.

15. The integrated composite router of claim 8, wherein each leaf network device in the plurality of leaf network devices comprises a host routes table, wherein the host routes table comprises a host routes table entry, and wherein the host routes table entry of the first network device comprises the first IP address and the first MAC address.

16. The integrated composite router of claim 8,

wherein the second leaf network device comprises an egress table,

wherein the egress table comprises a plurality of egress table entries,

wherein one of the plurality of egress table entries comprises an egress MAC address and specifies an egress interface,

wherein the second MAC address is the egress MAC address,

wherein the first interface of the second network device is the egress interface, and

wherein sending the second rewritten packet from the first interface on the second network device comprises using the egress table and the second MAC address to identify the one of the plurality of egress table entries.

17. The integrated composite router of claim 8, wherein the second network device further comprises a MAC pointer table, wherein the MAC pointer table comprises a MAC pointer table entry, and wherein the MAC pointer table entry comprises the destination MAC address of the first rewritten packet and a pointer to an instruction that enables the re-writing of destination MAC addresses of packets.

18. The integrated composite router of claim 8, further configured to:

receive a new route from the first external network device;

identify a leaf network device that comprises the non-overlapping portion of the routing table in which to store the route;

store the new route in the identified leaf device.

19. A non-transitory computer readable medium comprising instructions, which when executed by a processor, perform a method for routing packets, the method comprising:

receiving, at an interface of a first network device of a plurality of network devices in a leaf tier, a first packet, wherein the first packet comprises a first destination Internet Protocol (IP) address and wherein each of the plurality of network devices comprises a supernet table and a non-overlapping portion of a routing table;

determining, using the first destination IP address and the supernet table, a first IP address of a second network device to which the packet is to be sent, wherein the second network device is one of the plurality of network devices in the leaf tier, wherein the supernet table comprises a plurality of entries, wherein each of the plurality of entries comprises a non-overlapping IP address range and specifies a corresponding one of the plurality of network devices in the leaf tier, and wherein the non-overlapping portion of the routing table on the second network device comprises a route for the first packet;

determining, by the first network device, a first media access control (MAC) address of the second network device using the first IP address;

rewriting, by the first network device, the first packet to obtain a first rewritten packet, wherein the first rewritten packet comprises the first MAC address as a destination MAC address of the first rewritten packet and the first destination IP address;

sending the first rewritten packet to a third network device, wherein the third network device is not in the leaf tier;

determining, by the third network device using the destination MAC address of the first rewritten packet, to forward the first rewritten packet from the third network device to the second network device;

sending the first rewritten packet to the second network device;

performing, by the second network device using the destination MAC address of the first rewritten packet, a first MAC pointer table lookup to determine that a first routing table lookup is to be performed using the first destination IP address of the first rewritten packet;

performing, by the second network device, the first routing table lookup, wherein the first routing table lookup comprises using the non-overlapping portion of the routing table on the second network device to determine a second IP address corresponding to a first external network device to which the packet is to be sent;

determining, by the second network device, a second MAC address of the first external network device using the second IP address;

rewriting the first rewritten packet to obtain a second rewritten packet, by the second network device using the second MAC address, wherein the second rewritten packet comprises the second MAC address as a destination MAC address of the second rewritten packet and the first destination IP address;

sending the second rewritten packet from a first interface on the second network device to the first external network device, wherein the first interface is associated with the second MAC address.

20. The non-transitory computer readable medium of claim 19, further comprising:

receiving, at the interface of the first network device, a second packet, wherein the second packet comprises a second destination IP address;

performing, by the first network device, a second routing table lookup, wherein the second routing table lookup comprises using the non-overlapping portion of the routing table on the first network device to determine a third IP address corresponding to a second external network device to which the second packet is to be sent;

determining, by the first network device using the third IP address, a third MAC address corresponding to the second network device;

rewriting the second packet to obtain a third rewritten packet, wherein the third rewritten packet comprises the third MAC address as the destination MAC address of the third rewritten packet and the second destination IP address;

sending the third rewritten packet to the third network device;

determining, by the third network device using the destination MAC address of the third rewritten packet, to forward the third rewritten packet from the third network device to the second network device;

sending the third rewritten packet to the second network device;

performing, by the second network device using the destination MAC address of the third rewritten packet, a second MAC pointer table lookup to determine a fourth MAC address corresponding to the second external network device;

rewriting the third rewritten packet to obtain a fourth rewritten packet, wherein the fourth rewritten packet comprises the fourth MAC address as the destination MAC address of the fourth rewritten packet and the second destination IP address;

sending the fourth rewritten packet from a second interface of the second network device, wherein the second interface of the second network device is associated with the fourth MAC address.