METHOD AND SYSTEM FOR ROUTING PACKETS

• US 20150131663A1
• Filed: 11/14/2013
• Published: 05/14/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
• Granted Patent: US 9,118,607 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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, a packet, wherein the packet comprises a destination Internet Protocol (IP) address;

determining, using the destination IP address, 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 a plurality of network devices in a spine tier, wherein each of the plurality of network devices in the spine tier comprises a non-overlapping portion of a routing table, wherein the non-overlapping portion of the routing table on the second network device comprises a route for the 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 the 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 destination IP address;

sending the first rewritten packet to the second network device;

performing, by the second network device using the destination IP address, a routing table lookup, wherein the 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 third network device to which the packet is to be sent;

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

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

sending the second rewritten packet to the third network device;

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

sending the third rewritten packet from an interface on the third network device to an external network device, wherein the interface is associated with the third MAC address,

wherein the first network device and the third network device are not in the spine tier.

2. The method of claim 1, further comprising:

receiving, at a border gateway protocol (BGP) controller, a new route from the external network device;

replacing a next-hop IP address in the new route with the second IP address to obtain a modified new route;

determining that the modified new route should be stored on second network device using at least a portion of the IP address in the new route; and

sending the modified new route to the second network device.

3. The method of claim 1, wherein determining the first IP address further comprises using a supernet table, wherein the supernet table comprises a plurality of entries, wherein each of the plurality of entries comprises a non-overlapping IP address range and a corresponding one of the plurality of network devices in the spine tier.

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

5. 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, the first IP address;

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

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

sending the fourth rewritten packet to the second network device;

performing, by the second network device using the second destination IP address, a routing table lookup to determine a fourth IP address corresponding to the first network device to which the packet is to be sent;

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

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

sending the fifth rewritten packet to the first network device;

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

sending the sixth rewritten packet from a second interface on the firth network device.

6. The method of claim 1, wherein the non-overlapping portions of the routing table comprise a full Internet routing table.

7. A system, comprising:

a plurality of leaf network devices comprising a first network device and a third network device;

a plurality of spine network devices, wherein a second device is one of the plurality of spine network devices;

wherein each of the plurality of spine network devices comprises a non-overlapping portion of a routing table;

wherein each of the plurality of leaf network devices is connected to each of the plurality of spine network devices,

wherein none of the plurality of leaf network devices are connected to each other;

wherein none of the plurality of spine network devices are connected to each other;

wherein the first network device is configured to;

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

determine, using the destination IP address, a first IP address of the second network device to which the packet is to be sent;

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

rewrite the 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 destination IP address;

send the first rewritten packet to the second network device;

wherein the second network device is configured to;

perform, using the destination IP address, a routing table lookup, wherein the 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 the third network device to which the packet is to be sent;

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

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

send the second rewritten packet to the third network device;

wherein the third network device is configured to;

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

send the third rewritten packet from an interface on the third network device to an external network device, wherein the interface is associated with the third MAC address.

8. The system of claim 7, further comprising:

a BGP controller, wherein the BPG controller is operatively connected to the plurality of spine network devices and is configured to update the non-overlapping portions of the routing table on each of the plurality of spine network devices.

9. The system of claim 7, further comprising:

a BGP controller, wherein the BPG controller is operatively connected to the plurality of spine network devices and is configured to;

receive a new route from the external network device;

replace a next-hop IP address in the new route with the second IP address to obtain a modified new route;

determine, using at least a portion of the IP address in the new route, that the modified new route should be stored on the second network device; and

send the modified new route to the second network device.

10. The system of claim 7, wherein the first network device is one selected from a group consisting of a switch and a router.

11. The system of claim 7, wherein the external network device is a router.

12. The system of claim 7, wherein the egress table comprises an egress table entry, wherein the egress table entry comprises the second MAC address, the third MAC address, and the interface on the third network device.

13. The system of claim 7, wherein the first network device further comprises a supernet table, wherein the supernet table comprises a supernet table entry, and wherein the supernet table entry comprises non-overlapping IP ranges corresponding to the non-overlapping portions of the routing table and the first IP address.

14. The system of claim 7, wherein the non-overlapping potion of the routing table on the second network device comprises a route entry, wherein the route entry comprises a route corresponding to the destination IP address and the second IP address.

15. The system of claim 14, wherein the second network device is further configured to perform the routing table lookup by determining a longest prefix match (LPM) of the destination IP address of the packet.

16. 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, a packet, wherein the packet comprises a destination Internet Protocol (IP) address;

determining, using the destination IP address, 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 a plurality of network devices in a spine tier, wherein each of the plurality of network devices in the spine tier comprises a non-overlapping portion of a routing table, wherein the non-overlapping portion of the routing table on the second network device comprises a route for the 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 the 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 destination IP address;

sending the first rewritten packet to the second network device;

performing, by the second network device using the destination IP address, a routing table lookup, wherein the 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 third network device to which the packet is to be sent;

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

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

sending the second rewritten packet to the third network device;

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

sending the third rewritten packet from an interface on the third network device to an external network device, wherein the interface is associated with the third MAC address,

wherein the first network device and the third network device are not in the spine tier.

17. The non-transitory computer readable medium of claim 16, the method further comprising:

receiving, at a border gateway protocol (BGP) controller, a new route from the external network device;

replacing a next-hop IP address in the new route with the second IP address to obtain a modified new route;

determining that the modified new route should be stored on second network device using at least a portion of the IP address in the new route; and

sending the modified new route to the second network device.

18. The non-transitory computer readable medium of claim 16, wherein determining the first IP address further comprises using a supernet table, wherein the supernet table comprises a plurality of entries, wherein each of the plurality of entries comprises a non-overlapping IP address range and a corresponding one of the plurality of network devices in the spine tier.

19. The non-transitory computer readable medium of claim 16, wherein performing the routing table lookup further comprises determining a longest prefix match (LPM) for the destination IP address.

20. The non-transitory computer readable medium of claim 16, the method 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, the first IP address;

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

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

sending the fourth rewritten packet to the second network device;

performing, by the second network device using the second destination IP address, a routing table lookup to determine a fourth IP address corresponding to the first network device to which the packet is to be sent;

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

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

sending the fifth rewritten packet to the first network device;

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

sending the sixth rewritten packet from a second interface on the firth network device.