Patent Description:
<CIT> discloses a method of forwarding packets by a physical network switch, wherein the method assigns egress ports that connect the network switch to each particular next hop to a weighted - cost multipathing (WCMP) group associated with the particular next hop. The method assigns weights to each egress port in each WCMP group according to the capacity of each path that connects the egress port to the next hop associated with the WCMP group and normalizes the weights over a range of values. For each packet received at the network switch, the method identifies the WCMP group associated with a next hop destination of the packet. The method calculates a hash value of a set of fields in the packet header and uses the hash value to perform a range lookup in the identified WCMP group to select an egress port for forwarding the packet to the next hop.

The technology relates generally to routing packets in a network. In this regard, when a packet at a node in the network is to be transmitted, one or more processors at the node may select a next port to be used for transmitting the packet based on both static and adaptive routing parameters. For instance, a set of ports may be selected among a plurality of ports based on static weight configurations associated with each port of the plurality of ports. Then, the next port to be used for transmitting the packet may be selected among the set of ports based on estimated latency to the destination associated with each port of the set of ports under current network conditions.

<FIG> illustrates a network <NUM> according to aspects of the technology. As shown, the network <NUM> comprises a plurality of switches <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. Each of the switches <NUM>-<NUM> may be provided at a node of the network <NUM>, such as coupled to a server computing device or other computing device, for routing data packets to other nodes of the network <NUM>. While only a few switches <NUM>-<NUM> are shown, it should be understood that the network <NUM> may be expanded to include any number of switches, for example, to reach a greater number of nodes or locations, or to accommodate greater amounts of network traffic.

Each switch <NUM>-<NUM> may be coupled to one or more of the other switches in the network <NUM>, forming one or more routes. For example, a number of routes are shown between switch <NUM> and switch <NUM>. A packet may be transmitted between switch <NUM> and switch <NUM> via any of these routes. For instance, one route may include switches <NUM>, <NUM>, <NUM>, and <NUM>, another route may include switches <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, yet another route may include switches <NUM>, <NUM>, <NUM>, and <NUM>, and still another route may include switches <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, etc. Thus, some routes between switch <NUM> and switch <NUM> may require a packet to be transmitted via a greater number of hops than others. In this regard, the routes that require a minimal number of hops, such as those through switch <NUM> and switch <NUM> (e.g., <NUM> hops), may be referred to as "minimal routes" or "primary routes," and the routes that require a greater number of hops, such as those through switch <NUM> shown (e.g., <NUM> hops), may be referred to as "non-minimal routes" or "secondary routes.

The switches <NUM>-<NUM> may be coupled via data ports (not shown in <FIG>, examples are shown in <FIG>). Each switch <NUM>-<NUM> may include a predetermined number of data ports. The number of data ports may vary depending on, for example, a type of switch used. Some ports may be dedicated to downlink traffic (e.g., for transmitting data from switch <NUM> to switch <NUM>), while others may be dedicated to uplink traffic (e.g., for transmitting data from switch <NUM> to switch <NUM>). Alternatively or additionally, some ports may be dedicated to ingress while others may be dedicated to egress. The number of data ports may also dictate the number of links that may be established with other network devices, such as with other switches. In some instances, ports may be assigned weights based on the network topology, which is described further in reference to <FIG>.

Although only a few routes are shown connecting switch <NUM> to switch <NUM>, additional routes may be available. The additional routes may be formed by additional connections between the switches shown in <FIG>, or may involve additional switches not shown in <FIG>. Further, some of the routes shown may be active routes where all ports along the route are active, while others shown may be inactive routes where one or more ports along the route are inactive.

The switches <NUM>-<NUM> may be routers, chips, or any other type of device capable of receiving packets at a first port and transmitting the packets through a second port, and in many instances, capable of receiving and transmitting packets between multiple ports.

<FIG> illustrates an example of a switch, such as the switch <NUM>. The switch <NUM> may comprise one or more processors <NUM> and a memory <NUM> coupled to the one or more processors <NUM>. The memory <NUM> may include instructions <NUM> and data <NUM>. The switch <NUM> may further comprise a number of data ports, such as uplink data ports <NUM> and downlink data ports <NUM>.

The switch <NUM> may also include one or more forwarding tables <NUM>, one or more static weight configuration tables such as Weighted Cost Multi Path (WCMP) tables <NUM>, and network condition data <NUM>, which are described further in reference to <FIG> and <FIG>. For example, the forwarding tables <NUM> may include a number of entries, each listing a key and an action. As packets are received by the switch <NUM>, header information in those packets may be matched against the keys of the forwarding table <NUM> to determine a corresponding action (e.g., a next hop). The WCMP table <NUM> may, for example, include a weighting of each of the uplink data ports <NUM> (and/or downlink data ports <NUM>) on the switch <NUM>, and may be used to determine which port the packet should be transmitted through. The network condition data <NUM> may include real time or recent network congestion information at various data ports in the network <NUM>. While the forwarding table <NUM>, WCMP table <NUM>, and network condition data <NUM> are shown as being stored separately from the memory <NUM>, it should be understood that the forwarding table <NUM>, WCMP table <NUM>, network condition data <NUM>, instructions <NUM>, and/or data <NUM> may be stored in the same medium.

The one or more processors <NUM> may be any conventional processors, such as processors in commercially available routers. Alternatively, the processor may be a dedicated controller such as an ASIC or other hardware-based processor. The processor and memory may actually comprise multiple processors and memories that may or may not be stored within the same physical housing. For example, memory may be a hard drive or other storage media located in a server farm of a data center. Accordingly, references to a processor, memory, or computer will be understood to include references to a collection of processors, memories or computers that may or may not operate in parallel.

The memory <NUM> stores information accessible by the one or more processors <NUM>, including instructions <NUM> that may be executed or otherwise used by the processor <NUM>, and data <NUM>. The memory <NUM> may be of any type capable of storing information accessible by the processor, including a computer-readable medium, or other medium that stores data that may be read with the aid of an electronic device, such as a hard-drive, memory card, ROM, RAM, DVD or other optical disks, as well as other write-capable and read-only memories.

The instructions <NUM> may be any set of instructions to be executed directly (such as machine code) or indirectly (such as scripts) by the one or more processors <NUM>. For example, the instructions may be stored as computer code on the computer-readable medium. The instructions may be stored in object code format for direct processing by the processor, or in any other computer language including scripts or collections of independent source code modules that are interpreted on demand or compiled in advance.

For instance, although the system and method is not limited by any particular data structure, the data may be stored in computer registers, in a relational database as a table having a plurality of different fields and records, XML documents or flat files. The data may also be formatted in any computer-readable format. The data may comprise any information sufficient to identify the relevant information, such as numbers, descriptive text, proprietary codes, references to data stored in other areas of the same memory or different memories (including other network locations) or information that is used by a function to calculate the relevant data.

While the components of the switch <NUM> have been described with respect to a particular switch, it should be understood that a similar architecture may be imparted to any of the other switches of <FIG>. The switches in the network <NUM> may be configured the same, or may be configured differently. For instance, switches <NUM>-<NUM> may each include respective processors, memory storing instructions and data, forwarding tables, WCMP tables, network condition data, upload data ports, download data ports, etc. However, some of the switches <NUM>-<NUM> may have different number of data ports than other switches, and may make different connections and be part of different routes as other switches. As such, forwarding tables, WCMP tables, network condition data stored at each of the switches <NUM>-<NUM> may differ with respect to the data ports, connections, and routes available at each switch.

<FIG> illustrates an example routing according to aspects of the disclosure. The example of <FIG> shows selections performed in two stages. The routing may be performed by any switch of a network, for example by switch <NUM> of network <NUM>. For instance, the one or more processors <NUM> of the switch <NUM> may determine that a packet is to be transmitted to a destination, such as to a computing device coupled to switch <NUM>. The packet may originate from a computing device coupled to switch <NUM>, or may be received from another switch in the network <NUM>.

As shown in <FIG> and <FIG>, the one or more processors <NUM> may determine that a plurality of ports <NUM>-<NUM> may be used to transmit the packet to destination switch <NUM>. The one or more processors <NUM> may make such a determination by looking up the destination in a forwarding table, such as forwarding table <NUM>. As examples, port <NUM> of switch <NUM> may be on route R1 which further includes ports of switches <NUM>, <NUM>, and <NUM>; port <NUM> of switch <NUM> may be on route R5 which further includes ports of switches <NUM>, <NUM>, and <NUM>; and port <NUM> may be on route R6 which further includes ports of switches <NUM>, <NUM>, and <NUM>. Because these routes include the lowest number of hops, R1, R5, and R6 may be categorized as minimal routes or primary routes (denoted as "P"), and the corresponding ports <NUM>, <NUM> and <NUM> may be categorized as primary ports. In contrast, port <NUM> may be on route R4 which further includes ports of switches <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, and port <NUM> may be on route R7 which further includes ports of switches <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. Because routes R4 and R7 require a greater number of hops than routes R1, R5, and R6, routes R4 and R7 are may be categorized as non-minimal or secondary routes (denoted as "S"), and the corresponding ports <NUM> and <NUM> may be categorized as secondary ports. In some instances, the primary ports and the secondary ports may be stored in separate lists on the switch <NUM> or otherwise accessible by processors <NUM>.

The one or more processors <NUM> may additionally determine that one or more ports and/or routes at switch <NUM> are inactive. For example, processors <NUM> may determine that port <NUM> is inactive and thus route R0 including port <NUM> is also inactive, likewise, processors <NUM> may determine that ports <NUM> and <NUM>, and corresponding routes R2 and R3, are also inactive. As such, processors <NUM> may not consider ports <NUM> and <NUM> as options for transmitting the packet.

The one or more processors <NUM> may select a next port to be used for transmitting the packet to destination. In this regard, the one or more processors <NUM> may perform one or more selections based on both static and adaptive routing parameters. For instance as shown in <FIG>, in the first stage, the one or more processors <NUM> may perform a first selection <NUM> based on static parameters. The first selection <NUM> may be performed based on static weight configurations.

<FIG> shows an example static weight configuration in accordance with aspects of the disclosure. In particular, the configuration uses a Weighted Cost Multi Path (WCMP) flow distribution. For ease of illustration, only a few switches and connections from <FIG> are reproduced in <FIG>. However, it should be understood that the static weight configuration may be performed similarly for all connections between switches in the network <NUM>. Referring to <FIG>, switch <NUM> includes connection <NUM> to switch <NUM>, connection <NUM> to switch <NUM>, and connection <NUM> to switch <NUM>; switch <NUM> includes connection <NUM> to switch <NUM>, connection <NUM> to switch <NUM>, and connection <NUM> to switch <NUM>; and switch <NUM> includes connection <NUM> to switch <NUM>, connection <NUM> to switch <NUM>, and connection <NUM> to switch <NUM>.

Further, switch <NUM> may have <NUM> ports, and thus <NUM> links may be established between the switch <NUM> and the switches <NUM>-<NUM>. Because there are three switches <NUM>-<NUM>, and because <NUM> does not divide equally by <NUM>, there may be an uneven distribution of links among the switches <NUM>-<NUM> (e.g., uneven striping). For example, the connection <NUM> between the switch <NUM> and the switch <NUM> may comprise <NUM> links (e.g., coupled to ports <NUM>-<NUM> of the switch <NUM>), while the connections <NUM>, <NUM> between the switch <NUM> and each of the switches <NUM>, <NUM> may comprise <NUM> links (e.g., coupled to ports <NUM>-<NUM> and ports <NUM>-<NUM>, respectively, of the switch <NUM>).

This network topology may cause congestion in an Equal Cost Multiple Path (ECMP) flow distribution, where each connection is configured with equal static weight such that traffic is equally likely to be transmitted through each of the connections. For example, using ECMP, traffic is equally likely to transmit through the connection <NUM> including <NUM> links as the connection <NUM> including <NUM> links. Because each of the <NUM> links in connection <NUM> may have lower bandwidth than each of the <NUM> links in connection <NUM>, congestion may occur at the connection <NUM>.

Using WCMP flow distribution may ameliorate this problem and provide improved load balancing. With WCMP, each connection may be given a weight based on a number of links in the connection. For example and as shown, the connection <NUM> may be given a weight of <NUM>, while the connections <NUM> and <NUM> may each be given a weight of <NUM>. Thus, for example, <NUM> flows are transmitted over each of the links in connection <NUM>, <NUM> flows are transmitted over each of the links in connection <NUM> and <NUM> flows are transmitted over each of the links in connection <NUM>. In this regard, the switch <NUM> may avoid becoming oversubscribed, and therefore less likely to drop packets.

The weighting of the flows may be managed, for example, using a forwarding table and a WCMP table. <FIG> illustrates an example of the forwarding table <NUM> and the WCMP table <NUM> for switch <NUM>. The forwarding table <NUM> may include a number of entries <NUM>, <NUM>, <NUM>, each entry having a key and an action. The key may comprise a number of bits representing, for example, a destination address. The action may comprise information representing a next hop for each packet that is received with a destination matching a key. The WCMP table <NUM> may include a plurality of entries, with each entry identifying a port of the switch <NUM> through which received packets may be forwarded. The number of entries listing a particular port may vary depending on a weight assigned to that port. For example, the <NUM> links in the connection <NUM> coupled to ports <NUM>-<NUM> of the switch <NUM> were assigned a weight of <NUM>, as discussed above in connection with <FIG>. Accordingly, each of ports <NUM>-<NUM> may have <NUM> entries in the WCMP table <NUM>. Similarly, the <NUM> links in the connection <NUM> coupled to the ports <NUM>-<NUM> of the switch <NUM> were assigned a weight of <NUM>. Therefore, each of the ports <NUM>-<NUM> may have <NUM> corresponding entries in the WCMP table <NUM>.

Similar forwarding tables and WCMP tables may be stored or made accessible to each of the switches in the network <NUM> of <FIG>. For example, forwarding table <NUM> and WCMP table <NUM> for switch <NUM> may be configured similarly as forwarding table <NUM> and WCMP table <NUM> for switch <NUM>, except forwarding table <NUM> stores entries for ports of switch <NUM> and WCMP table <NUM> stores weights based on connections at switch <NUM>. In some instances where the primary ports and the secondary ports are stored in separate lists, a forwarding table and/or a WCMP table may be provided for the primary ports and another forwarding table and/or WCMP table may be separately provided for the secondary ports. While the foregoing description of <FIG> provides one example in which weighting of flows may be achieved, it should be understood that other hardware related weighting schemes may alternatively or additionally be used. For example, the hardware may be able to take a weight along with each port and implement a hash algorithm such that particular ports may be picked more often than others based on their weight.

Returning to <FIG>, the result of the first selection <NUM> includes <NUM> ports-port <NUM> on route R1, port <NUM> on route R5, port <NUM> on route R4, and port <NUM> on route R7. The first selection <NUM> may be configured to reduce the plurality of available ports to a set of a predetermined number of ports, or a predetermined faction/percentage of ports, etc. In the particular example shown, the predetermined number of ports resulting from the first selection <NUM> is <NUM>. In other examples, the result of the first selection may include fewer or more ports (or smaller or greater fraction/percentage). For example, if port selection is to be more heavily based on static weight configurations, the selection based on static weight configurations may be used to narrow down the ports to a smaller set, such as <NUM> or <NUM> ports. In contrast, if port selection is to be less heavily based on static weight configurations, the selection based on static weight configurations may be used to narrow down the ports to a larger set, such as <NUM> or more ports. Although the example result of the first selection <NUM> includes both primary ports and secondary ports, in other examples the result of the first selection <NUM> may include only primary ports or only secondary ports.

To ensure there are both primary ports and secondary ports in the result of the first selection <NUM>, optionally the selection performed based on static weight configurations may be separately performed for the primary ports and the secondary ports. Thus and as further shown in <FIG>, optionally a selection <NUM> may be performed based on weights assigned among the primary ports <NUM>, <NUM>, and <NUM>, resulting in the selection of primary ports <NUM> and <NUM>. A separate selection <NUM> may be performed based on weights assigned among the secondary ports <NUM> and <NUM>, resulting in the selection of secondary ports <NUM> and <NUM>. This way, the first selection <NUM> will result in both primary ports and secondary ports.

Next, in the second stage, the processors <NUM> may perform a second selection <NUM> based on adaptive parameters on the set of ports resulting from the first selection <NUM>. <FIG> illustrates example adaptive routing parameters <NUM>. The adaptive routing parameters <NUM> may include a plurality of entries, with each entry identifying a port of the switch <NUM> through which packets may be forwarded, such as ports <NUM>-<NUM> of <FIG>. For each port, the corresponding route may be identified, such as routes R0-R7 of <FIG>, as well as a length of each route, which may be considered the number of hops required to destination. Further as shown, network condition data, such as congestive data, may be provided for each route. The congestive data c1, c4, c5, c6, c7 may be provided in any appropriate format, such as numerical values representing the amount of traffic in front of a current data packet, percentages compared to a predetermined maximum level of congestion, or another format. For example, congestion for a particular data packet from an output port to reach destination may be calculated as q*H, where q is the amount of queue space taken at the output port, and H is the number of remaining hops to the destination. The adaptive routing parameters <NUM> may further include heuristic based offsets. For example, congestion for the data packet from the output port to destination may be expressed as q*H+b, where b is the offset. The offset may be based on any of a number of factors, such as those specific to a condition in a system or a network. Although <FIG> illustrates adaptive routing parameters <NUM> in a table format, the adaptive routing parameters may be provided in any format, such as logs, tables, graphs, etc..

The processors <NUM> may perform the second selection <NUM> based on these adaptive routing parameters. For instance, the processors <NUM> may determine an estimated latency for each route based on the length of the route, the congestive data along the route, and/or heuristic offsets for the route. By way of example, the processors <NUM> may determine the estimated latency for each route using a linear function of the adaptive routing parameters <NUM>.

The processors <NUM> may then select the next port to transmit the packet based on latency, and may make the selection from the set resulting from the first selection <NUM>. Thus as shown, the processors <NUM> may determine that route R7 has the lowest estimated latency amongst routes R1, R5, R4 and R7, and select port <NUM> for transmitting the packet. As also shown, where the first selection <NUM> resulted in a set of ports including both primary and secondary ports, the second selection <NUM> may be made from a set including both primary and secondary ports. Thus, a longer route may be chosen if its estimated latency is lower.

Once the next port is selected, the one or more processors <NUM> may route the packet through the next port. For example, the one or more processors <NUM> may route the packet through port <NUM> on its way to route R7. However, once the packet arrives on the next port of route R7, network conditions may have changed. As such, the processors of the next switch <NUM> on route R7 may re-evaluate the available ports and routes, and select the next port. For example, processors of the next switch <NUM> may perform similar selections as shown in <FIG>, although the available ports, routes, and connections may be different. Depending on the static and/or adaptive parameters, the next port selected by the next switch <NUM> may or may not cause the packet to continue on route R7. For example, the next port selected by processors of switch <NUM> may be switch <NUM>, thus continuing the packet's progress along route R7, or it may be switch <NUM>, and thus changing the path of the packet to route R4. By selecting the next port after each hop, the packet may be transmitted through the optimal port and route, thereby optimizing its transmission and the overall condition of the network.

<FIG> illustrates another example of routing packets according to aspects of the disclosure. The example of <FIG> shows selections performed in three stages. The routing may be performed by any switch of a network, for example by switch <NUM> of network <NUM>. <FIG> shows many similar features as <FIG>, which are labeled as such. However, the routing shown in <FIG> includes selections in three stages. In the first stage, the first selection <NUM> may be the same as described with reference to <FIG>, for example based on WCMP as described with reference to <FIG> and <FIG>. Thus, a first set of ports may result from the first selection <NUM>, which includes ports <NUM>, <NUM>, <NUM>, and <NUM>. Further, the first selection <NUM> may be separately performed for primary ports and secondary ports, via selections <NUM> and <NUM> as described with respect to <FIG>.

In the second stage, the second selection <NUM> of <FIG> may be performed differently from the second selection <NUM> of <FIG>. In the second selection <NUM>, routes of equal lengths are compared against each other. Thus, where the first selection <NUM> resulted in a set of routes that have different lengths, those with the same lengths are compared against each other during second selection <NUM>. For instance and as shown, selection <NUM> compares route R1 with route R5, each having a hop number of <NUM>, while selection <NUM> compares route R4 with route R7, each having a hop number of <NUM>. Since the lengths of routes in each comparison are equal, processors <NUM> may perform the second selections <NUM> and <NUM> based on only congestive conditions and/or heuristic offsets for these routes, such as described with reference to <FIG>. The second selection <NUM> may be configured to reduce the plurality of available ports to a set of a predetermined number of ports, or a predetermined fraction/percentage of ports, etc. In the particular example shown, the predetermined number of ports resulting from the second selection <NUM> is <NUM> for each route length (<NUM> ports resulting from selection <NUM> for routes with <NUM> hops and <NUM> ports resulting from selection <NUM> for routes with <NUM> hops). In other examples, the results of each of the second selections <NUM> and <NUM> may include fewer or more ports (or a smaller or greater fraction/percentage) than the example shown in <FIG>.

In the third stage, the processors <NUM> may perform a third selection <NUM> on the set of ports resulting from second selection <NUM>. In this regard, the processors <NUM> may determine an estimated latency for each route resulting from the second selection <NUM>, and choose the port along the route with the lowest latency. For example, processors <NUM> may determine that route R7 has the lowest estimated latency amongst routes R1 and R7, and select port <NUM> for transmitting the packet. As compared to <FIG>, because processors performing routing based on <FIG> do not need to estimate latency until the set of ports are further narrowed among routes of equal lengths, this may result in increased efficiency in determining the optimal route.

<FIG> is an example flow diagram <NUM> for routing using static and adaptive routing. Flow diagram <NUM> may be performed by one or more processors of one or more switch devices of <FIG>, such as one or more processors <NUM> shown in <FIG>. For example, processors <NUM> may receive data and make various determinations as shown in the flow diagram <NUM>.

Referring to <FIG>, at block <NUM>, it is determined that a packet is to be transmitted to a destination. For example as shown in <FIG> and <FIG>, processors <NUM> of switch <NUM> may determine that a packet is to be transmitted to a computing device coupled to switch <NUM>. The packet may originate from a computing device coupled to switch <NUM>, or received from another switch in the network.

At block <NUM>, a next port is selected to be used for transmitting the packet. For example and as shown in <FIG> and <FIG>, processors <NUM> of switch <NUM> may determine that a plurality of ports <NUM>-<NUM>, each leading to a respective route R0-R7, may be used to transmit the packet. Further as shown, processors <NUM> may determine that one or more of the ports and/or routes may be inactive.

The selections may be performed in two stages or more stages. In a first stage, a set of ports are selected among a plurality of ports based on a static weight configuration associated with each of the plurality of ports. For instance as shown in <FIG> and <FIG>, processors <NUM> of switch <NUM> may make a first selection based on static parameters. Processors <NUM> may use static weight configurations as shown in <FIG>, which may be stored in tables such as those shown in <FIG>. Further as shown in <FIG> and <FIG>, the first selection based on static parameters may be separately performed for primary ports and secondary ports.

In a second stage, the next port is selected among the set of ports based on a number of hops required to reach the destination from each port of the set of ports and based on an estimated latency from each port of the set of ports to the destination. For instance as shown in <FIG> and <FIG>, processors <NUM> of switch <NUM> may make a second selection based on adaptive parameters. Processors <NUM> may consider number of hops, congestion data, and heuristics such as those shown in <FIG>.

At block <NUM>, the packet is routed through the selected next port. For instance as shown in <FIG> and <FIG>, the packet may be transmitted through port <NUM>, to be transmitted through route R7. Once the packet reaches the next switch along route R7, the process of <FIG> may be repeated, which may result in selection of a next port that may or may not continue along route R7. Further, the process of <FIG> may be repeated until the packet reaches the destination.

The technology is advantageous because it provides efficient routing of packets in a network. By considering both static and adaptive routing parameters, the system may more effectively adapt to changing network conditions without losing sight of the static topology, such as link configurations downstream in the network. Further, by considering both static and adaptive routing parameters for a packet at each hop along a path to destination, routing paths for each packet may be optimized even as network conditions continue to change.

Claim 1:
A method (<NUM>), comprising:
determining (<NUM>), by one or more processors (<NUM>) of one or more switches (<NUM>-<NUM>) included in a network (<NUM>), that a packet is to be transmitted from a source switch (<NUM>) to a destination switch (<NUM>), wherein the one or more switches (<NUM>-<NUM>) are coupled to one another to form one or more routes, and wherein each switch (<NUM>-<NUM>) includes one or more ports;
selecting (<NUM>), by the one or more processors (<NUM>), a next port of a next switch among a plurality of ports (<NUM>-<NUM>) of one or more other switches (<NUM>-<NUM>, <NUM>-<NUM>, <NUM>) to be used for transmitting the packet, each port of the plurality of ports (<NUM>-<NUM>) being part of one or more routes, wherein selecting comprises:
selecting (<NUM>), by the one or more processors (<NUM>), a first set of ports (<NUM>, <NUM>, <NUM>, <NUM>) among the plurality of ports (<NUM>-<NUM>) based on a static weight configuration associated with each port of the plurality of ports (<NUM>-<NUM>);
selecting (<NUM>, <NUM>, <NUM>), by the one or more processors (<NUM>), a second set of ports (<NUM>, <NUM>) among the first set of ports (<NUM>, <NUM>, <NUM>, <NUM>) based on congestive conditions along routes requiring equal number of hops to reach the destination switch (<NUM>) from each port of the second set of ports (<NUM>, <NUM>); and
selecting (<NUM>), by the one or more processors (<NUM>), the next port among the second set of ports (<NUM>, <NUM>) based on an estimated latency to the destination switch (<NUM>) associated with each port of the second set of ports (<NUM>, <NUM>); and
routing (<NUM>), by the one or more processors (<NUM>), the packet through the selected next port of the next switch along a respective route of the selected next port.