Forwarding table reduction and multipath network forwarding

• US 8,532,099 B2
• Filed: 09/17/2010
• Issued: 09/10/2013
• Est. Priority Date: 10/22/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kreeger, Lawrence, Edsall, Thomas, Ganesan, Elango, Gai, Silvano
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): LOPATA, ROBERT J
• Application Number:
  US12/885,339
• Publication Number:
  US 20110007741A1
• Time in Patent Office: 1,089 Days
• Field of Search: 370254-256, 370/351, 370/352, 370/389, 709/238
• US Class Current: 370/389
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

Increased usage of network links is provided and smaller forwarding tables are required. A combination of STP and Multipath methods may be implemented in a network. Frames may be forwarded between switches not only according to MAC addresses, but also according to switch IDs and local IDs. Switch IDs do not need to be globally unique, but should be unique within a particular network. Local IDs need only be unique within a particular switch. Some preferred implementations allow frames to be delivered in order to devices requiring in-order delivery. Preferably, core switches need only learn the switch IDs of each core switch and each edge switch, and the appropriate exit port(s) corresponding to each switch. Preferably, the forwarding tables of each edge switch indicate the addresses of each device attached to that edge switch, the address of each device that is in communication with an attached device and the address of every other switch in the network.

Claims

1. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

interfacing with a plurality of host devices, the plurality of host devices identified by Media Access Control (MAC) addresses; and

maintaining a first Remote MAC Table (RMT) that records a correspondence between MAC addresses of the host devices and hierarchical addresses of ports of a plurality of edge switches, wherein the apparatus is a first edge switch of the plurality of edges switches; and

populating a switch forwarding table (“

SFT”

) of the first edge switch with a switch address of every other active core switch and edge switch in a network, wherein data packets are transferred according to the hierarchical addresses.

2. The apparatus as recited in claim 1, at least one of the processor or the memory being further adapted for:

populating a first local media access control (“

MAC”

) table in the first edge switch with MAC addresses of local host devices attached to a first port of the first edge switch;

populating the first remote MAC table in the first edge switch with remote addresses of remote host devices that are attached to other ports and that have been communicating with at least one of the local host devices;

receiving a frame from a first host device via the first edge switch; and

determining whether a destination MAC address indicated in the frame is included in the first remote MAC table.

3. The apparatus as recited in claim 1, wherein a plurality of core switches transfer data packets according to the hierarchical addresses, individual core switches each containing a switch forwarding table (SFT) that contains hierarchical addresses of switches in the network and do not contain MAC addresses of the plurality of host devices.

4. The apparatus as recited in claim 3, wherein a SFT of each active core switch and a SFT of other edge switches in the plurality of edge switches are populated with the switch address of every other active core switch and edge switch in the network.

5. The apparatus as recited in claim 2, at least one of the processor or the memory being further adapted for:

encapsulating the frame with the first port'"'"'s hierarchical address to create an encapsulated frame; and

flooding the encapsulated frame according to the spanning tree protocol (“

STP”

) if it is determined that the destination MAC address indicated in the frame is not included in the first remote MAC table.

6. The apparatus as recited in claim 2, at least one of the processor or the memory being further adapted for:

if it is determined that the destination MAC address indicated in the frame is included in the first remote MAC table, obtaining a hierarchical address corresponding to the destination address from the first remote MAC table and sending the frame to the hierarchical address, the hierarchical address identifying a port of an edge switch of the network.

7. The apparatus as recited in claim 2, wherein the remote addresses include MAC addresses and hierarchical addresses.

8. The apparatus as recited in claim 1, wherein entries of each SFT are not aged out.

9. The apparatus as recited in claim 1, wherein each SFT is depopulated in response to topology change notifications.

10. The apparatus as recited in claim 9, wherein the topology change notifications comprise negative MAC Notification (MN) frames.

11. The apparatus as recited in claim 2, at least one of the processor or the memory being further adapted for:

sending an indication that the first port needs to receive frames in order.

12. The apparatus as recited in claim 1 wherein a hierarchical address of a port contains a switch ID and a port ID.

13. The apparatus as recited in claim 12 wherein the switch ID is unique within the network and the port ID is unique within a given switch, but is not unique within the network.

14. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

interfacing with a plurality of host devices, the plurality of host devices identified by Media Access Control (MAC) addresses; and

maintaining a first Remote MAC Table (RMT) that records a correspondence between MAC addresses of the host devices and hierarchical addresses of ports of a plurality of edge switches, wherein the apparatus is a first edge switch of the plurality of edges switches;

receiving a frame from a first host device via a first port of the first edge switch;

determining whether a destination MAC address indicated in the frame is included in the first remote MAC table;

encapsulating the frame with the first port'"'"'s hierarchical address to create an encapsulated frame; and

flooding the encapsulated frame using a spanning tree protocol (“

STP”

) according to whether it is determined that the destination MAC address indicated in the frame is included in the first remote MAC table.

15. The apparatus as recited in claim 14, at least one of the processor or the memory being further adapted for:

populating the first remote MAC table in the first edge switch with remote addresses of remote host devices that are attached to other ports and that have been communicating with at least one of the local host devices.

16. The apparatus as recited in claim 14, at least one of the processor or the memory being further adapted for:

populating a switch forwarding table (“

SFT”

) of the first edge switch with the switch address of every other active core switch and edge switch in a network.

17. An apparatus, comprising:

means for interfacing with a plurality of host devices, the plurality of host devices identified by Media Access Control (MAC) addresses; and

means for maintaining a first Remote MAC Table (RMT) that records a correspondence between MAC addresses of the host devices and hierarchical addresses of ports of a plurality of edge switches, wherein the apparatus is a first edge switch of the plurality of edges switches;

means for receiving a frame from a first host device via a first port of the first edge switch;

means for determining whether a destination MAC address indicated in the frame is included in the first remote MAC table; and

means for obtaining a hierarchical address corresponding to the destination address from the first remote MAC table and sending the frame to the hierarchical address if it is determined that the destination MAC address indicated in the frame is included in the first remote MAC table, the hierarchical address identifying a port of an edge switch of the network.

18. The apparatus as recited in claim 17, further comprising:

means for encapsulating the frame with the first port'"'"'s hierarchical address to create an encapsulated frame; and

means for flooding the encapsulated frame using a spanning tree protocol (“

STP”

) if it is determined that the destination MAC address indicated in the frame is not included in the first remote MAC table.

19. The apparatus as recited in claim 17, further comprising:

means for receiving an encapsulated frame from a second one of the plurality of edge switches, the encapsulated frame including a source MAC address, a destination MAC address, and a hierarchical address;

means for determining whether a first local MAC table includes the destination MAC address;

means for adding the source MAC address and the hierarchical address of the encapsulated frame to the first remote MAC table of the first edge switch;

means for removing the hierarchical address from the encapsulated frame to form a decapsulated frame; and

means for forwarding the decapsulated frame to a host device having the destination MAC address.

20. A method, comprising:

maintaining a first Remote Media Access Control (MAC) Table that records a correspondence between MAC addresses of a plurality of host devices and hierarchical addresses of ports of a plurality of edge switches, wherein the apparatus is a first edge switch of the plurality of edges switches;

receiving a frame from a first host device via a first port of the first edge switch;

determining whether a destination MAC address indicated in the frame is included in the first remote MAC table;

encapsulating the frame with the first port'"'"'s hierarchical address to create an encapsulated frame; and

flooding the encapsulated frame using a spanning tree protocol (“

STP”

) according to whether it is determined that the destination MAC address indicated in the frame is included in the first remote MAC table.