Forwarding database cache

• US 6,438,130 B1
• Filed: 06/28/2001
• Issued: 08/20/2002
• Est. Priority Date: 06/28/2001
• Status: Expired due to Term

• Current Assignee: Mellanox Technologies TLV Ltd. (NVIDIA Corporation)
• Original Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Inventors: Crupnicoff, Diego, Webman, Alon, Kagan, Michael, Gabbay, Freddy
• Primary Examiner(s): LUTHER, WILLIAM A
• Application Number:
  US09/892,852
• Time in Patent Office: 418 Days
• Field of Search: 370/389, 370/351, 370/395.1, 370/395.52, 370/395.5, 370/395, 370/53, 370/395.6, 370/392, 370/387, 370/367, 370/396-397, 370/400, 370/401, 370/419, 370/420, 370/436, 359/120, 359/121, 359/123, 359/124, 359/115, 359/117, 359/118, 359/128
• US Class Current: 370/392
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

A device for switching packets in a network includes a switching core and a plurality of ports, coupled to pass the packets from one to another through the switching core. The ports include, with respect to each packet among the packets switched by the device, a receiving port, coupled to receive the packet from a packet source, and a destination port, to which the packet is passed for conveyance to a packet destination. The ports also include one or more cache memories, respectively associated with one or more of the ports, each of the cache memories being configured to hold a forwarding database cache for reference by the receiving port with which the cache memory is associated in determining the destination port of the packet.

Claims

1. A device for switching packets in a network, comprising:

a switching core;

a plurality of ports, coupled to pass the packets from one to another through the switching core, the ports comprising, with respect to each packet among the packets switched by the device, a receiving port, coupled to receive the packet from a packet source, and a destination port, to which the packet is passed for conveyance to a packet destination; and

one or more cache memories, respectively associated with one or more of the ports, each of the cache memories being configured to hold a forwarding database cache for reference by the receiving port with which the cache memory is associated in determining the destination port of the packet.

2. A device according to claim 1, wherein the packets comprise respective packet addresses, and wherein the forwarding database cache comprises entries indicating the destination port for each of a selected plurality of the packet addresses.

3. A device according to claim 2, wherein the packet addresses comprise media access control (MAC) addresses.

4. A device according to claim 2, wherein the entries in the forwarding database cache are arranged in one or more tables, which are indexed by a segment of the packet addresses.

5. A device according to claim 4, wherein the segment of the packet addresses comprises a predetermined number of the least significant bits of the packet addresses.

6. A device according to claim 4, wherein the one or more tables comprise at least two tables.

7. A device according to claim 2, wherein each of the entries comprises a target field, corresponding to at least a portion of one of the packet addresses with which the entry is associated, and wherein the target field is compared to the portion of the packet addresses to determine that a cache hit has occurred, whereupon the receiving port reads the destination port from one of the tables.

8. A device according to claim 7, wherein when the cache hit does not occur with respect to one of the packets, the destination port is read from a forwarding database outside the cache memory.

9. A device according to claim 8, wherein the destination port read from the forwarding database outside the cache memory is entered in the cache in place of a least recently used one of the entries having a given index.

10. A device according to claim 1, wherein the forwarding database cache comprises one or more tables comprising entries to which the receiving port refers the packets that it receives, each such entry comprising a target field and a data value indicating the destination port to which the packet should be passed when the packet matches the target field.

11. A device according to claim 10, wherein at least some of the entries further comprise a force-hit flag, such that when the force-hit flag is set in the entry to which the packet is referred, the packet is passed to the destination port indicated by the entry even when the packet does not match the target field.

12. A device according to claim 11, wherein the entries in at least one of the one or more tables are configurable so that the data value for all of the entries can be set to indicated the same destination port, and wherein the force-hit flag of all of the entries can be set so that all of the packets received at the receiving port are passed to the same destination port.

13. A device according to claim 12, wherein the one or more cache memories comprise a multiplicity of cache memories respectively associated with a multiplicity of the ports, and wherein the entries in the multiplicity of the cache memories can be set so that all of the packets received at the multiplicity of the ports are passed to the same destination port.

14. A device according to claim 13, and comprising a host processor, coupled to the destination port so as to receive the packets from the multiplicity of the ports, and to process the packets so as to route them through the network.

15. A device according to claim 1, and comprising a device memory, configured to hold a forwarding database, from which information is read for caching in the one or more cache memories.

16. A method for switching packets in a network, comprising:

providing a forwarding database containing information indicating a destination port for each of the packets that is received at one of a plurality of ports of a switch in the network;

copying a subset of the information in the forwarding database to a forwarding database cache in a cache memory associated with each of one or more of the ports of the switch;

reading the information from the cache memory at one of the ports, responsive to receiving one of the packets at the port, in order to determine the destination port for the packet; and

passing the packet through the switch to the destination port.

17. A method according to claim 16, wherein the packets comprise respective packet addresses, and wherein the information contained in the forwarding database indicates the destination port for each of the packet addresses, and wherein copying the subset of the information comprises saving in the cache memory the destination port indicated in the forwarding database for each of a selected plurality of the packet addresses.

18. A method according to claim 17, wherein the packet addresses comprise media access control (MAC) addresses.

19. A method according to claim 17, wherein the forwarding database cache comprises one or more tables, and wherein reading the information comprises reading an entry from the tables that is indexed by a segment of one of the packet addresses.

20. A method according to claim 19, wherein reading the entry from the tables comprises reading the entry that is indexed by a predetermined number of the least significant bits of the packet addresses.

21. A method according to claim 19, wherein each of the entries comprises a target field, corresponding to at least a portion of the packet addresses, and wherein reading the information comprises comparing the target field of the indexed entries in each of the tables to the portion of the packet addresses in the packet in order to determine that a cache hit has occurred, and reading the destination port from the cache when the cache hit has occurred.

22. A method according to claim 21, wherein copying the subset of the information comprises, when the cache hit does not occur, reading the destination port from the forwarding database and entering the destination port read from the forwarding database into the cache in place of a least recently used one of the indexed entries.

23. A method according to claim 19, wherein the one or more tables comprise at least two tables.

24. A method according to claim 19, wherein the forwarding database cache comprises one or more tables comprising entries, each such entry including a target field and a data value indicating the destination port, and wherein reading the information comprises comparing the packet to the target field, and passing the packet comprises passing the packet to the destination port indicated by the entry when the packet matches the target field.

25. A method according to claim 24, wherein at least some of the entries further comprise a force-hit flag, such that when the force-hit flag is set in one of the entries, passing the packet comprises passing the packet to the destination port indicated by the entry even when the packet does not match the target field.

26. A method according to claim 25, and comprising setting the destination port for all of the entries in the cache to the same one of the ports, and setting the force-hit flag of all of the entries so that all of the packets received at the receiving port are passed to the same destination port.

27. A method according to claim 26, wherein the one or more cache memories comprise a multiplicity of cache memories respectively associated with a multiplicity of the ports, and wherein setting the destination port and the force-hit flag comprises setting the destination port and the force-hit flag in the multiplicity of cache memories so that all of the packets received at the multiplicity of the ports are passed to the same destination port.

28. A method according to claim 27, and comprising coupling a host processor to the destination port so as to receive the packets from the multiplicity of the ports, and processing the packets using the host processor so as to route the packets through the network.