Efficient algorithmic forwarding in fat-tree networks
First Claim
1. A switch, comprising:
- multiple physical ports, which are configured to receive and send packets over a packet network, the physical ports comprising an up-number of physical ports via which the switch connects to parent switches and a down-number of physical ports via which the switch connects to child switches or end-nodes, wherein a number of the child switches or end-nodes is larger than a number of the parent switches; and
forwarding circuitry, which is configured to;
compare between the down-number and the up-number, and when the down-number is larger than the up-number, define one or more nonphysical temporary ports in addition to the physical ports, wherein a number of the nonphysical temporary ports equals a difference calculated as the down-number minus the up-number;
assign respective first port numbers to the physical ports, and assign respective second port numbers, different from the first port numbers, to the nonphysical temporary ports;
receive a packet having a destination address via a physical port of the switch and select, based on a comparison between a subset of bits defining the destination address, and bits defining an identifier of the switch, an intermediate port for the packet from among both the physical ports and the nonphysical temporary ports; and
forward the received packet to a physical port corresponding to the intermediate port if the intermediate port is one of the physical ports, and, if the intermediate port is one of the nonphysical temporary ports, map the intermediate port to a mapped physical port, based on the first and second port numbers, and forward the received packet to the mapped physical port.
4 Assignments
0 Petitions
Accused Products
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.
24 Citations
18 Claims
-
1. A switch, comprising:
-
multiple physical ports, which are configured to receive and send packets over a packet network, the physical ports comprising an up-number of physical ports via which the switch connects to parent switches and a down-number of physical ports via which the switch connects to child switches or end-nodes, wherein a number of the child switches or end-nodes is larger than a number of the parent switches; and forwarding circuitry, which is configured to; compare between the down-number and the up-number, and when the down-number is larger than the up-number, define one or more nonphysical temporary ports in addition to the physical ports, wherein a number of the nonphysical temporary ports equals a difference calculated as the down-number minus the up-number; assign respective first port numbers to the physical ports, and assign respective second port numbers, different from the first port numbers, to the nonphysical temporary ports; receive a packet having a destination address via a physical port of the switch and select, based on a comparison between a subset of bits defining the destination address, and bits defining an identifier of the switch, an intermediate port for the packet from among both the physical ports and the nonphysical temporary ports; and forward the received packet to a physical port corresponding to the intermediate port if the intermediate port is one of the physical ports, and, if the intermediate port is one of the nonphysical temporary ports, map the intermediate port to a mapped physical port, based on the first and second port numbers, and forward the received packet to the mapped physical port. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method, comprising:
-
in a switch that comprises multiple physical ports that receive and send packets over a packet network, wherein the physical ports comprising an up-number of physical ports via which the switch connects to parent switches and a down-number of physical ports via which the switch connects to child switches or end-nodes, wherein a number of the child switches or end-nodes is larger than a number of the parent switches, comparing between the down-number and the up-number, and when the down-number is larger than the up-number, defining one or more nonphysical temporary ports in addition to the physical ports, wherein a number of the nonphysical temporary ports equals a difference calculated as the down-number minus the up-number; assigning respective first port numbers to the physical ports, and assigning respective second port numbers, different from the first port numbers, to the nonphysical temporary ports; receiving a packet having a destination address via a physical port of the switch, and selecting, based on a comparison between a subset of bits defining the destination address, and bits defining an identifier of the switch, an intermediate port for the packet from among both the physical ports and the nonphysical temporary ports; and forwarding the received packet to a physical port corresponding to the intermediate port if the intermediate port is one of the physical ports, and, if the intermediate port is one of the nonphysical temporary ports, mapping intermediate port to a mapped physical port, based on the first and second port numbers, and forwarding the received packet to the mapped physical port. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A switch, comprising:
-
multiple physical ports, which are configured to receive and send packets over a packet network, the physical ports comprising an up-number of physical ports via which the switch connects to parent switches and a down-number of physical ports via which the switch connects to child switches or end-nodes, wherein a number of the child switches or end-nodes is larger than or equal to a number of the parent switches; and forwarding circuitry, which is configured to; calculate a number of temporary ports as a difference of the down-number minus the up-number; compare between the down-number and the up-number, and when the down-number is larger than the up-number, define one or more nonphysical temporary ports in addition to the physical ports; assign respective first port numbers to the physical ports, and when the number of temporary ports is nonzero assign respective second port numbers, different from the first port numbers, to the nonphysical temporary ports; receive a packet having a destination address via a physical port of the switch and select, based on a comparison between a subset of bits defining the destination address, and bits defining an identifier of the switch, an intermediate port for the packet from among the physical ports or when the number of temporary ports is nonzero from among both the physical ports and the nonphysical temporary ports; and forward the received packet to a physical port corresponding to the intermediate port if the intermediate port is one of the physical ports, and, when the number of temporary ports is nonzero and the intermediate port is one of the nonphysical temporary ports, map the intermediate port to a mapped physical port, based on the first and second port numbers, and forward the received packet to the mapped physical port.
-
-
18. A method, comprising:
-
in a switch that comprises multiple physical ports that receive and send packets over a packet network, wherein the physical ports comprising an up-number of physical ports via which the switch connects to parent switches and a down-number of physical ports via which the switch connects to child switches or end-nodes, wherein a number of the child switches or end-nodes is larger than or equal to a number of the parent switches, calculating a number of temporary ports as a difference of the down-number minus the up-number; comparing between the down-number and the up-number, and when the down-number is larger than the up-number, defining one or more nonphysical temporary ports in addition to the physical ports; assigning respective first port numbers to the physical ports, and when the number of temporary ports is nonzero assigning respective second port numbers, different from the first port numbers, to the nonphysical temporary ports; receiving a packet having a destination address via a physical port of the switch, and selecting, based on a comparison between a subset of bits defining the destination address, and bits defining an identifier of the switch, an intermediate port for the packet from among the physical ports or when the number of temporary ports in nonzero from among both the physical ports and the nonphysical temporary ports; and forwarding the received packet to a physical port corresponding to the intermediate port if the intermediate port is one of the physical ports, and, when the number of temporary ports is nonzero and the intermediate port is one of the nonphysical temporary ports, mapping the intermediate port to a mapped physical port, based on the first and second port numbers, and forwarding the received packet to the mapped physical port.
-
Specification