Forwarding table reduction and multipath network forwarding

• US 7,801,125 B2
• Filed: 06/14/2005
• Issued: 09/21/2010
• 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: Ganesan, Elango, Edsall, Thomas, Gai, Silvano, Kreeger, Lawrence
• Primary Examiner(s): Hoang; Thai D
• Application Number:
  US11/152,991
• Publication Number:
  US 20060098589A1
• Time in Patent Office: 1,925 Days
• Field of Search: 370/389, 370/351, 370/400, 370/432, 370/390
• 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. A network comprising:

a plurality of edge switches that interface with a plurality of host devices, the plurality of host devices identified by Media Access Control (MAC) addresses, each edge switch containing a Remote MAC Table (RMT) that records a correspondence between MAC addresses of the host devices and hierarchical addresses of ports of the plurality of edge switches; and

a plurality of core switches that transfer data packets according to the hierarchical addresses, individual core switches containing switch forwarding tables that contain hierarchical addresses of switches in the network and do not contain MAC addresses of the plurality of host devices.

2. The network of claim 1, further comprising:

means for populating a switch forwarding table (“

SFT”

) of each active core switch and edge switch in a network with the switch address of every other active core switch and edge switch in the network;

means for populating a first local media access control (“

MAC”

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

means for populating a 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;

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

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

3. The network of claim 2, further comprising:

means 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”

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

4. The network of claim 3, further comprising:

means for indicating that the first port needs to receive frames in order.

5. The network of claim 4, further comprising:

means for receiving, by a core switch, the encapsulated packet; and

means for updating the SFT to indicate that frames should be forwarded to the first edge switch via STP.

6. The network of claim 5, further comprising means for sending a MAC notification frame from the first port to the second port indicating that the first port needs to receive frames in order.

7. The network of claim 3, further comprising:

means for receiving, by a second edge switch, the encapsulated frame; and

means for determining whether the second edge switch has a second local MAC table that includes the destination MAC address.

8. The network of claim 7, wherein it is determined that the second edge switch has a second local MAC table that includes the destination MAC address, further comprising:

means for adding the source MAC address and the hierarchical address of the encapsulated frame to a second remote MAC table of the second 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 second host device attached to a second port and having the destination MAC address.

9. The network of claim 8, further comprising:

means for returning a second frame from the second host device to the first host device via a least cost path, the second frame indicating the first host'"'"'s MAC address, the second host'"'"'s MAC address and the first port'"'"'s hierarchical address.

10. The network of claim 8, further comprising:

means for returning a MAC notification frame from the second port to the first port via a least cost path, the MAC notification frame comprising;

a hierarchical address of the second port;

the first host'"'"'s MAC address; and

the second host'"'"'s MAC address; and

means for updating the first remote MAC table to include the second host'"'"'s MAC address and the hierarchical address of the second port.

11. The network of claim 2, wherein the remote addresses include MAC addresses and hierarchical addresses.

12. The network of claim 11 further comprising, 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 when 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.

13. The network of claim 1, wherein the switch forwarding tables are populated according to a protocol that determines least cost and equal cost paths.

14. The network of claim 1, wherein entries of the switch forwarding tables are not aged out.

15. The network of claim 1, wherein the switch forwarding tables are depopulated in response to topology change notifications.

16. The network of claim 15, wherein the topology change notifications comprise negative MAC Notification (MN) frames.

17. The network of claim 1, further comprising:

means for populating a switch forwarding table (“

SFT”

) of each active core switch and edge switch in a network with the switch ID of every other active core switch and edge switch in the network, wherein the SFTs are populated according to a protocol that determines least cost and equal cost paths and wherein SFT entries are not aged out;

means for depopulating SFTs in response to topology change notifications;

means for populating a local media access control (“

MAC”

) table for each edge switch port with MAC addresses of attached local host devices; and

means for populating at least one remote MAC table of each edge switch in the network with remote hierarchical addresses and remote MAC addresses of remote host devices that have been communicating with at least one of the local host devices within a predetermined period of time.

18. The network of claim 17, wherein the switch IDs are unique within the network but are not unique outside of the network.

19. The network of claim 17, wherein each of the remote hierarchical addresses comprises a local ID corresponding to a remote port to which a remote host device is attached and a switch ID of an edge switch that includes the remote port.

20. The network of claim 19, wherein a local ID is unique only within each edge switch.

21. The network of claim 1 wherein a hierarchical address of a port contains a switch ID and a port ID.

22. The network of claim 21 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.