Forwarding table reduction and multipath network forwarding

• US 20060098589A1
• Filed: 06/14/2005
• Published: 05/11/2006
• 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
• Granted Patent: US 7,801,125 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• 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 method of forwarding frames in a network, comprising:

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;

populating a first local media access control (“

MAC”

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

populating a first remote MAC table 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; and

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

2. The method of claim 1, wherein it is determined that the destination MAC address indicated in the frame is not included in the first remote MAC table, further comprising:

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”

).

3. The method of claim 1, wherein the remote addresses include MAC addresses and hierarchical addresses.

4. The method of claim 1, wherein the SFTs are populated according to a protocol that determines least cost and equal cost paths.

5. The method of claim 1, wherein SFT entries are not aged out.

6. The method of claim 1, further comprising the step of depopulating SFTs in response to topology change notifications.

7. The method of claim 2, further comprising the step of indicating that the first port needs to receive frames in order.

8. The method of claim 2, further comprising:

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

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

9. The method of claim 6, wherein the topology change notifications comprise negative MN frames.

10. The method of claim 7, further comprising:

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

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

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

adding the source MAC address and the hierarchical address of the encapsulated frame to a second remote MAC table of the second edge switch;

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

forwarding the decapsulated frame to a second host device attached to a second port and having the destination MAC address.

12. The method of claim 10, further comprising the step of 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.

13. The method of claim 10, further comprising:

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

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

14. The method of claim 10, further comprising the step of sending a MAC notification frame from the first port to the second port indicating that the first port needs to receive frames in order.

15. A network, 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 a switch ID is 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.

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

17. The network of claim 15, 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.

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