EFFICIENT ALGORITHMIC FORWARDING IN FAT-TREE NETWORKS

• US 20170187614A1
• Filed: 12/28/2015
• Published: 06/29/2017
• Est. Priority Date: 12/28/2015
• Status: Active Grant

• Current Assignee: Mellanox Technologies Limited (NVIDIA Corporation)
• Original Assignee: Mellanox Technologies TLV Ltd. (NVIDIA Corporation)
• Inventors: Rabenstein, Itamar, Haramaty, Zachy, Zahavi, Eitan
• Granted Patent: US 10,284,465 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 49/3045 Virtual queuing

Abstract

A switch includes multiple physical ports and forwarding circuitry. The physical ports are configured to receive and send packets over a network. The forwarding circuitry is configured to assign first port numbers to the physical ports, and second port numbers to temporary ports defined in addition to the physical ports, to receive a packet having a destination address via a physical port, to select, based on the destination address, an egress port number for the packet from among the first and second port numbers, to forward the packet to a physical port corresponding to the egress port number if the egress port number is one of the first port numbers, and, if the egress port number is one of the second port numbers, to map a temporary port associated with the egress port number to a mapped physical port and to forward the packet to the mapped physical port.

Claims

1. A switch, comprising:

multiple physical ports, which are configured to receive and send packets over a packet network; and

forwarding circuitry, which is configured to assign respective first port numbers to the physical ports, to assign respective second port numbers to one or more temporary ports defined in addition to the physical ports, to receive a packet having a destination address via a physical port of the switch, to select, based on the destination address, an egress port number for the packet from among the first and second port numbers, to forward the packet to a physical port corresponding to the egress port number if the egress port number is one of the first port numbers, and, if the egress port number is one of the second port numbers, to map a temporary port associated with the egress port number to a mapped physical port and to forward the packet to the mapped physical port.

2. The switch according to claim 1, wherein the switch connects to a first number of parent switches, and further connects to a second number of child switches or end-nodes, in a Fat-Tree network using the physical ports, and wherein the forwarding circuitry is configured to assign the second port numbers based on a difference between the first number and the second number.

3. The switch according to claim 2, wherein the switch resides in a given level of the Fat-Tree network, and wherein the forwarding circuitry is configured to select the egress port number based at least on the given level.

4. The switch according to claim 1, wherein the forwarding circuitry is configured to select the egress port number by applying a bit-group extraction operation to the destination address.

5. The switch according to claim 1, wherein in response to receiving an indication that sending packets via the physical port to which the temporary port is mapped fails, the forwarding circuitry is configured to map the temporary port to an alternative, operative physical port.

6. The switch according to claim 1, wherein the physical ports are connected to the network via output interfaces of the switch having respective interface numbers, wherein the interface numbers are an order permutation of the first numbers, and wherein the forwarding circuitry is configured to map the temporary port to a physical port that connects to an output interface having an interface number equal to a first number associated with the mapped physical port.

7. The switch according to claim 1, wherein the switch further comprises a fallback forwarding database (FDB), wherein the forwarding circuitry is configured to select the egress port number by applying to the destination address a bit-group extraction operation, and in response to detecting that a result of the bit-group extraction operation is invalid, to select the egress port number using the fallback FDB.

8. The switch according to claim 1, wherein the forwarding circuitry is configured to select the egress port by extracting a bit-group comprising one or more bits of the destination address.

9. A method, comprising:

in a switch that comprises multiple physical ports that receive and send packets over a packet network, assigning respective first port numbers to the physical ports, and assigning respective second port numbers to one or more temporary ports defined in addition to the physical ports;

receiving a packet having a destination address via a physical port of the switch, and selecting, based on the destination address, an egress port number for the packet from among the first and second port numbers; and

forwarding the packet to a physical port corresponding to the egress port number if the egress port number is one of the first port numbers, and, if the egress port number is one of the second port numbers, mapping a temporary port associated with the egress port number to a mapped physical port and forwarding the packet to the mapped physical port.

10. The method according to claim 9, wherein the switch connects to a first number of parent switches, and further connects to a second number of child switches or end-nodes, in a Fat-Tree network using the physical ports, and wherein assigning the second port numbers comprises setting the second port numbers based on a difference between the first number and the second number.

11. The method according to claim 10, wherein the switch resides in a given level of the Fat-Tree network, and wherein selecting the egress port number comprises choosing the egress port number based at least on the given level.

12. The method according to claim 9, wherein selecting the egress port number comprises choosing the egress port number by applying a bit-group extraction operation to the destination address.

13. The method according to claim 9, and comprising, in response to receiving an indication that sending packets via the physical port to which the temporary port is mapped fails, mapping the temporary port to an alternative, operative physical port.

14. The method according to claim 9, wherein the physical ports are connected to the network via output interfaces of the switch having respective interface numbers, wherein the interface numbers are an order permutation of the first numbers, and wherein mapping the temporary port comprises mapping the temporary port to a physical port that connects to an output interface having an interface number equal to a first number associated with the mapped physical port.

15. The method according to claim 9, wherein the switch further comprises a fallback forwarding database (FDB), wherein selecting the egress port number comprises deriving the egress port number by applying to the destination address a bit-group extraction operation, and, in response to detecting that a result of the bit-group extraction operation is invalid, selecting the egress port number using the fallback FDB.

16. A packet network, comprising:

one or more non-leaf switches; and

multiple leaf switches, which are connected to the non-leaf switches and are also connected to end-nodes that are assigned non-contiguous addresses, wherein at least one of the leaf switches is connected to a respective number of end-nodes and is configured to receive a packet from a first end-node that is destined to a second end-node having a destination address, and to select a port via which to forward the packet, by extracting from the destination address a group of one or more bits representing an integer in a range determined by the number of end-nodes.

17. The packet network according to claim 16, wherein the at least one of the leaf switches is configured to extract the group of the one of more bits by applying to the destination address at least one operation selected from a list consisting of a bit-shifting operation and a bit-masking operation.

18. A method, comprising:

in a packet network that comprises multiple leaf switches and one or more non-leaf switches, wherein each of the leaf switches connects to a respective number of end-nodes, assigning non-contiguous addresses to the end-nodes attached to the leaf switches;

receiving in one of the leaf switches a packet from a first end-node that is destined to a second end-node having a destination address; and

selecting a port of the one of the leaf switches via which to forward the packet, by extracting from the destination address a group of one or more bits representing an integer in a range determined by the number of end-nodes.

19. The method according to claim 18, wherein extracting the group of the one of more bits comprises applying to the destination address at least one operation selected from a list consisting of a bit-shifting operation and a bit-masking operation.