Certain embodiments presented herein relate to load balancing of data transmissions among a plurality of paths between endpoints (EPs) coupled to virtual switches. In particular, between the virtual switches there may be a number of physical paths for the data to be communicated between the EPs. Each path may have a different congestion level. Certain embodiments relate to selecting a path of the plurality of paths between EPs to communicate data between the EPs based on the congestion levels associated with each of the plurality of paths. In certain embodiments, a virtual switch determines a congestion level of each of the plurality of paths, selects a path of the plurality of paths based on the determined congestion level, and sets source port information of network packets to correspond to the selected path so that the network packets are communicated along the selected path.

BACKGROUND

Networks (e.g., data center networks) generally employ multi-rooted topologies that are characterized by a large degree of multipathing between physical machines (e.g., physical servers) within the networks. For example, physical servers of a network may be connected with each other using a plurality of switches that provide alternative physical paths for network packet forwarding between the physical servers. A physical server may utilize one of the physical paths to send to a second physical server a flow of network packets, which can comprise one or more network packets being passed from a source (e.g., the physical server) to a destination (e.g., the second physical server). Network packets (i.e., traffic) may not be evenly distributed across the different paths, which may cause over-utilization of one path and under-utilization of another. Load balancing of network packets between paths is important to spread the network packets as evenly as possible among the paths to reduce congestion and improve network performance overall.

SUMMARY

Herein described are one or more embodiments of a method for performing congestion-aware load balancing in a network. The method includes receiving, by a virtual switch, a packet sent by a source endpoint and destined for a destination endpoint. The packet includes a header including a source address field, a destination address field, and a source port field. The source address field includes a source address of the source endpoint. The source port field includes a source port of the source endpoint. The destination address field includes a destination address of the destination endpoint. The method further includes selecting, by the virtual switch, a first path of a plurality of paths coupling the virtual switch with the destination endpoint. The first path is selected based on congestion state information associated with each of the plurality of paths. The method further includes modifying, by the virtual switch, the source address field of the header to include a source address of the virtual switch instead of the source address of the source endpoint. The method further includes modifying, by the virtual switch, the destination address field of the header to include a destination address of a second virtual switch coupled to the destination endpoint instead of the destination address of the destination endpoint. The method further includes modifying, by the virtual switch, the source port field of the header based on the selected first path. The method further includes sending, by the virtual switch, the modified packet to the destination endpoint such that the packet is forwarded via the first path based on values of the source address field, the destination address field, and the source port field of the header of the modified packet.

Also described herein are embodiments of a non-transitory computer readable medium comprising instructions to be executed in a computer system, wherein the instructions when executed in the computer system perform a method described above for performing congestion-aware load balancing in a network.

Also described herein are embodiments of a computer system, wherein software for the computer system is programmed to execute the method described above for performing congestion-aware load balancing in a network.

DETAILED DESCRIPTION

Embodiments presented herein relate to load balancing of network packets among a plurality of physical paths (e.g., including cables, wires, switches, etc.) between endpoints (EPs) coupled to virtual switches. Each path may have a different congestion level, where a more congested path may take longer to send network packets. Accordingly, embodiments presented herein relate to selecting a path to send network packets based on the congestion levels associated with each of the plurality of paths. In certain embodiments, a virtual switch determines a congestion level of each of the plurality of paths between EPs, selects a path based on the determined congestion level, and sets source port information of network packets to correspond to the selected path so that network packets are communicated along the selected path.

FIG. 1is a block diagram of a network100in which one or more embodiments of the present invention may be implemented. It should be understood that network100may include additional and/or alternative components than that shown, depending on the desired implementation. Network100includes a plurality of end points (EPs)102. As shown, network100includes EP102aand EP102b, however network100may include additional EPs102. An EP (e.g., EP102) may refer generally to an originating node (“source endpoint”) or terminating node (“destination endpoint”) of a flow of network packets. In practice, an endpoint may be a physical computing device (e.g., physical server, physical host), virtualized computing instance (e.g., virtual machine, container (such as a Docker container), data compute node, isolated user space instance, or other logical compute node) supported by a physical computing device, etc.

Network100further includes a plurality of virtual switches106that are configured to route network packets in network100, such as by performing layer-3 router functions, layer-2 switching, gateway functions, bridge functions, etc. As shown, network100includes virtual switch106aand virtual switch106b, however network100may include additional virtual switches106. Virtual switches106may be implemented by a hypervisor running on a host. One or more EPs102and virtual switches106may reside on the same physical computing device, or on different computing devices.

EPs102send network packets to other EPs102via virtual switches106. In particular, each EP102may be coupled to a corresponding virtual switch106. For example, as shown, EP102autilizes corresponding virtual switch106ato communicate network packets on network100. Further, as shown, EP102butilizes corresponding virtual switch106bto communicate.

In certain embodiments, the network100is a non-overlay network in which network packets would be encapsulated using a tunnelling protocol. Encapsulating a packet may include adding certain header information to the packet, such as addresses (e.g., internet protocol (IP) addresses), while keeping the original packet as a payload of the encapsulated packet. Encapsulating a packet maintains the information of the original packet. In the network system as presently described, virtual switches106may route packets based on header information in the packet without overlay network encapsulation. For example, EP102amay generate a packet to send to EP102b(e.g., an application running on EP102b). The packet may include a header and a payload. The payload may include application data for EP102b. The header may include a layer-2 header, a layer-3 header, a layer-4 header, etc. In particular, the header may include a tuple indicating a source address corresponding to the address (e.g., media access control (MAC) or IP address) of EP102a, a destination address corresponding to the address of EP102b, a source port corresponding to the port of EP102a, a destination port corresponding to the port of EP102b, and/or a protocol used for the packet. While network overlays using tunnel encapsulation can provide many benefits such as programmability, multi-tenancy, network isolation, etc., it also requires controllers and other components, adds to the overall complexity of the network topology, and increases bandwidth requirements due to stacked headers on every packet.

The term “layer-2” generally refers to a data link layer (e.g., Media Access Control (MAC) or Ethernet layer), “layer-3” to a network layer (e.g., Internet Protocol (IP) layer), and “layer-4” to a transport layer (e.g., Transmission Control Protocol (TCP) layer) in the Open System Interconnection (OSI) model, although the concepts described herein and referred to simply as “MAC” and “IP” may be applicable to corresponding layers in may be applicable to corresponding layers in other networking models. The term “packet” may refer generally to a group of bits that can be transported together, and may be in another form, such as “frame”, “message”, “segment”, etc.

As discussed, EP102amay communicate on network100via virtual switch106a. Accordingly, virtual switch106areceives the packet from EP102aand routes the packet over network100to EP102b.

As discussed, there may be a plurality of paths between EPs102. In particular, there may be a plurality of paths between virtual switches106associated with each of EPs102. For example, as shown, virtual switch106ais coupled via two separate paths to switches140and150. Further, virtual switch106bis also coupled via two separate paths to switches140and150. Therefore, there are two paths as shown between EP102a/virtual switch106aand EP102b/virtual switch106b: one path via switch140and the other path via switch150. Depending on the network topology, switch140or150may be a ToR switch, aggregate switch, spine switch, etc. Although two alternative paths are shown inFIG. 1for simplicity, the number of paths depends on the number of inter-connected switches and the topology of network100, such as a multi-rooted topology (e.g., leaf-spine topology, fat-tree topology, etc.). Further, there may be additional switches connecting EP102a/virtual switch106aand EP102b/virtual switch106bthan that shown inFIG. 1.

Embodiments presented herein relate to selecting a path of the plurality of paths to communicate network packets between EPs/virtual switches based on congestion levels associated with the paths. Further, as discussed, certain embodiments presented herein may be used for non-overlay network. For example, in certain embodiments, a virtual switch may be configured to modify network packets in a non-overlay network.

Path Congestion

In practice, network packets may be unevenly spread among different paths in a network such as network100, which may cause congestion and performance degradation. In some embodiments, equal cost multipath routing (ECMP) is used as a data plane load balancing mechanism to try and spread network packets more uniformly across multiple paths with equal costs (e.g., equal number of hops for each path between EPs). In some embodiments, ECMP switches use a simple, hash-based load balancing scheme to assign each new flow of network packets to one of the available paths at random. ECMP may be implemented in custom silicon (e.g., application-specific integrated circuit (ASIC)), which may lack flexibility to update the load balancing scheme. Further, ECMP is congestion-agnostic and does not protect against oversubscription of paths that causes performance degradation. For example inFIG. 1, links180-186connecting different pairs of switches may have different congestion levels.

In certain embodiments, ECMP does not consider different congestion levels, and therefore, flows of network packets may be assigned to paths that are congested, which may potentially delay network packet transmission. For example, link180may be congested, while link184may not be congested. In ECMP, data between the virtual switch106aand virtual switch106bmay be transferred on the path via switch140including link180with congestion instead of on the path via switch150including link184.

In some embodiments, control plane load balancing mechanisms may be used to address the shortcomings of ECMP. In such embodiments, instead of selecting paths at random, a central controller is deployed in network100to collect statistics from, and push forwarding rules to, virtual switches106and switches140and150to implement control plane load balancing. However, since a central controller is required, control plane mechanisms are relatively slow due to high control loop latency and incapable of handling highly volatile traffic.

In some embodiments, host-based approaches may be used to address the shortcomings of ECMP. For example, a modified version of transmission control protocol (TCP) called multipath TCP (MPTCP) may be used to establish multiple subflows between endpoints to split flows of network packets over different paths. Subflows may refer to a subset of the network packets of a flow. However, certain host-based approaches may require changes to all the endpoints, such as modifying the TCP/IP stack of all EPs102in network100in the case of MPTCP. Such changes are usually challenging (and impossible in some cases), especially when EPs102are running different operating systems, or controlled by different entities.

Accordingly, certain embodiments presented herein provide approaches to load balancing based on congestions levels in a network that overcome such deficiencies. For example, certain embodiments provide techniques for performing load balancing based on congestion levels of a network that may be implemented by a virtual switch106. Such embodiments may not necessitate modifications to EPs102, or even the modification of intermediate switches140and150. Further, unlike control plane load balancing mechanisms, embodiments presented herein do not necessitate deployment of a central controller to perform congestion monitoring and push forwarding rules to intermediate switches.

In certain embodiments, virtual switch106amay perform path learning to learn the possible paths for transmitting network packets to virtual switch106b. For example, in network100, virtual switch106amay implement a background daemon (e.g., modeled after Paris traceroute) to send periodic probe packets to all other virtual switches106in network100to collect “traceroute” like information (e.g., pathtrace information) about all interfaces (e.g., intermediate switches) along each of the plurality of paths between virtual switch106aand each of the other virtual switches106. For example, the pathtrace information for a path may include the address information (e.g., IP address) of each interface along the path. For example, virtual switch106amay receive pathtrace information for a first path via switch140to virtual switch106band for a second path via switch150to virtual switch106b.

The routing of network packets on a particular path may be based on the values of the header information associated with the packet. Therefore, changing even one of the values may change the path over which the packet is routed. In order for a source virtual switch106to transmit a network packet to a particular destination virtual switch106, the source address (e.g., IP address), destination address (e.g., IP address), and destination port field information of the packet may be fixed. In particular, the value of the field for the source address is the source address of the source virtual switch, the value of the field for the destination address is the destination address of the destination virtual switch, and the value of the field for the destination port is the port used by the destination virtual switch.

However, in certain embodiments, the value of the field for the source port of the packet may be altered by the source virtual switch106, as the source virtual switch106may choose a source port to use for communication. Accordingly, the value of the source port field in a packet sent by the source virtual switch106may be altered to change the routing of the packet, meaning the path over which the packet is routed may be changed. Accordingly, in certain embodiments, a source virtual switch106is configured to set a particular source port value for the source port field of a header of a packet to transmit to a destination virtual switch106in order to select the path associated with the source port for transmitting the packet.

Virtual switch106amay utilize the path learning technique described, along with changing source port information of network packets, to learn a plurality of paths between virtual switch106aand virtual switch106b. For example, virtual switch106amay send the discussed periodic probe packets to virtual switch106bwith different source port values for the source port field of a header of different probe packets, but the same source address, destination address, destination port, and protocol field values for each probe packet and store a mapping of the collected pathtrace information to the source port value for the source port field for each path. In some embodiments, the pathtrace information may be stored as a hash to an identifier, such as a path identifier. If virtual switch106receives pathtrace information for a source port value that is different than the pathtrace information already stored at virtual switch106, virtual switch106either adds a new mapping of the collected pathtrace information to a source port value if the source port value is not already stored as mapped to pathtrace information, or updates the pathtrace information in the stored mapping of the pathtrace information to the corresponding source port value.

In certain embodiments, virtual switch106amay determine the congestion level of each learned path. The congestion level may comprise one or more of a round trip time (RTT), or other suitable congestion level indication. Virtual switch106amay then store information mapping source port numbers to corresponding pathtrace information (e.g., path identifier) and congestion level information. The mapping may be stored as a table, hash, etc. The information may be referred to as congestion state information.

In certain embodiments, a virtual switch106amay rely on capabilities of intermediate switches140or150, such as Explicit Congestion Notification (ECN) that facilitates end-to-end notification of congestion level information in a network. Detailed information of ECN may be found in the Internet Engineering Task Force (IETF) Request for Comments number3168and entitled “The Addition of Explicit Congestion Notification (ECN) to IP,” which is incorporated herein in its entirety by reference. Although ECN is described as an example, it should be understood that any other suitable packet marking approach may be used.

FIG. 2illustrates example operations200for performing path learning using ECN to determine congestion level of paths in an overlay network.

At210, virtual switch106aperforms path learning to learn the paths between the virtual switch106aand virtual switch106band a mapping between source port numbers and pathtrace information for each path, as discussed. At215, virtual switch106amodifies packets to transmit to the virtual switch106band includes a different source port number associated with each of the learned plurality of paths in different packets. At220, virtual switch106asends the packets to virtual switch106b.

At225, switches (e.g., virtual switches106, intermediate switches140,150, etc.) along each path receive the packets. At230, each switch determines if a link the switch is forwarding a given packet on is congested. If at230, the switch determines the link is not congested, the operations200proceed to240. Otherwise, if the switch determines the link is congested, the switch includes congestion information of the link in the given packet. For example, the switch may include information in the packet such as a flag indicating congestion or not. In some embodiments, a packet may travel through a plurality of switches along a path. Accordingly, if a packet already includes congestion information from one switch, and another intermediate switch determines there is congestion on another link, the other intermediate switch may add additional information to the packet about the congestion, may not add additional information.

At240, the switches send the packets to virtual switch106b. At245, virtual switch106breceives the packets. At250, virtual switch106bsends feedback information (e.g., destination to source feedback information) to virtual switch106athat includes the congestion information and information about the path travelled by the packet (e.g., source port number of the received packet).

At255, virtual switch106areceives the feedback information. At260, virtual switch106aupdates/stores the congestion information as mapped to the corresponding pathtrace information and source port number.

In another example, instead of or in addition to using ECN as indicative of congestion level, virtual switch106amay use measured RTT for each path as a measure of congestion level of the path.

FIG. 3illustrates example operations for performing path learning using RTT measurement to determine congestion level of paths.

At310, similar to210, virtual switch106aperforms path learning to learn the paths between virtual switch106aand virtual switch106bas discussed. At315, similar to215, virtual switch106atransmits packets including a different source port number associated with each of the learned plurality of paths in different packets and includes a transmit (Tx) timestamp in each packet to virtual switch106b.

At325, virtual switch106breceives the packets. At330, virtual switch106bgenerates acknowledgement (ACK) packets acknowledging receipt of the packets from virtual switch106a. Virtual switch106bincludes in each ACK packet information about the path travelled by the packet (e.g., source port number of the received packet) and the corresponding Tx timestamp. At335, virtual switch106btransmits the ACK packets to virtual switch106a. At340, virtual switch106areceives the ACK packets and calculates the time differences between each Tx timestamp and the time each ACK is received as the RTT for the path associated with the source port number in the ACK packet. At345, virtual switch106astores the RTT as indicative of the congestion level for the path associated with the source port number, destination address, source address, and destination port. In some embodiments, the closer that the timestamping and acknowledgment is performed to hardware network interface controllers (NICs), the more accurately the RTT reflects actual network latency for the path as it does not include latency introduced by a software stack at the transmitter and the receiver.

In certain embodiments, virtual switch106amay select a path of a plurality of paths for transmitting a network packet to virtual switch106b, respectively, based on the congestion level associated with each of the plurality of paths. In some embodiments, virtual switch106amay select the path that has the lowest congestion level to transmit the packet.

In certain embodiments, load balancing, or selecting a path for transmitting packets from a particular virtual switch106to another may be done on any granularity level. For example, different paths may be selected for each packet, each flow, or each flowlet. A flowlet may refer to a group or burst of packets within a flow. In some embodiments, load balancing may be performed at the flowlet level, such as to avoid or ameliorate packet reordering issues associated with transport layer protocols such as TCP.

FIG. 4illustrates example operations for performing load balancing at a flowlet level. At405, virtual switch106areceives a network packet from EP102ato transmit to EP102b. At410, virtual switch106adetermines if the network packet belongs to a new flowlet or a current flowlet between EP102aand EP102b. For example, if there is no existing flow between EP102aand EP102bthat the network packet corresponds to, then the network packet belongs to a new flow, and accordingly, a new flowlet. If there is an existing flow between EP102aand EP102bthat the network packet corresponds to, virtual switch106adetermines if the network packet belongs to the current flowlet. In particular, if the network packet is received by virtual switch106afrom EP102awithin a threshold time period (e.g., predetermined time period in seconds, based on estimated RTT in the network100, etc.) of virtual switch106areceiving the last packet from EP102aof the current flowlet, the network packet belongs to the current flowlet. Otherwise, the network packet belongs to a new flowlet. All subsequent packets that are received by the virtual switch106aof the flow that do not exceed the threshold time period are also considered part of the same flowlet. A larger threshold time period may reduce packet reordering.

If at410, virtual switch106adetermines the received network packet is part of the current flowlet, at415, virtual switch106amay transmit the network packet on the same path as the network packets of the current flowlet. If at410, virtual switch106adetermines the received network packet is part of a new flowlet, at420, virtual switch106amay determine a path of a plurality of paths to transmit the network packet based on congestion levels associated with the plurality of paths. Then, at425, virtual switch106amay transmit the network packet on the determined path. In some embodiments, virtual switch106amay keep track of the time between receiving packets of flowlets using counters. In some embodiments, virtual switch106amay further keep track of the paths associated with flowlets by associating an identifier with each flowlet and storing the identifier in the mapping to source port numbers, such as in the stored congestion state information.

Certain embodiments presented herein may be implemented independent of any configuration of end-user guest virtual machines (e.g., acting as EPs102) by configuring virtual switches106to split a network flow into multiple uncongested paths in a manner independent of the guest virtual machines. In particular, the logic for splitting flows into flowlets may be implemented at the source and destination virtual switches106. In such embodiments, a flow may be divided into flowlets arbitrarily, and not contingent upon any threshold time period between packets.

For example, in some embodiments, each TCP segmentation offload (TSO) segment of a flow may be treated as a flowlet. In some embodiments, if flowlets arrive out of order at the destination virtual switch because of the different paths taken, the destination virtual switch may reorder the flowlets before delivering them to the destination endpoint (e.g., guest virtual machine). This allows the destination virtual switch to hide the out-of-order arrival from the destination protocol stack (e.g., TCP/IP stack) of the destination endpoint, preventing the destination protocol stack from slowing down the source protocol stack at the source endpoint due to the out-of-order delivery.

As discussed, in certain embodiments, a source virtual switch106is configured to set a particular source port value for a source port field of a header of a packet to transmit to a destination virtual switch106in order to select the path associated with the source port value/number for transmitting the packet.

Unlike in an overlay network, virtual switches106in a non-overlay network are not configured to encapsulate packets. Instead, virtual switches106may typically be configured to forward network packets received from EPs102as is, including the header information generated by EPs102. As discussed, without changing the header information of a network packet (e.g., the source port field) the network packet may only be able to travel on one path, instead of a particular path based on congestion level. Accordingly, certain embodiments described herein modify the function of virtual switches106to allow virtual switches106to change header information of a network packet to select a path of a plurality of paths to send the network packet based on the congestion level of the plurality of paths.

FIG. 5illustrates example operations500for modifying a packet to select a path to transmit the packet in a network (e.g., non-overlay network).

At505, virtual switch106areceives a network packet from EP102ato transmit to EP102b. At510, virtual switch106aselects a path to send the network packet to virtual switch106bassociated with EP102bbased on the congestion level of the plurality of paths. At515, virtual switch106areplaces the original header information in the packet with modified header information. In particular, virtual switch106areplaces the source address included in the source address field of the header of the packet with the source address of virtual switch106a(e.g., the hypervisor implementing virtual switch106a), the destination address included in the destination address field of the header of the packet with the destination address of virtual switch106b(e.g., the hypervisor implementing virtual switch106b), the destination port included in the destination port field of the header of the packet with a fixed value in the ephemeral port range (e.g., where the fixed value is known by the virtual switch106b), and the source port number included in the source port field of the header of the packet with the source port number associated with the selected path, such as based on congestion state information stored at virtual switch106a. In some embodiments, the virtual switch106bdetermines that the packet is a modified packet based on the destination port field including the fixed value. Further, at520, virtual switch106aplaces a portion of the original header information including the original source address, destination address, destination port, and source port information included by EP102ain the packet in a TCP options field of the packet. At525, virtual switch106athen transmits the modified packet to EP102b. The packet travels over the selected path based on the modified header information of the packet. At530, virtual switch106breceives the packet and extracts the original source address, destination address, destination port, and source port information from the TCP options field of the packet. In some embodiments, the virtual switch106bdetermines that the received packet has a destination port field including the fixed value and is therefore a modified packet. Accordingly, in some embodiments, the virtual switch106bextracts the original header information (e.g., at530) and replaces the modified header information (e.g., at535) based on the value of the destination port field of the received packet. At535, virtual switch106breplaces the modified header information (e.g., source address field, destination address field, destination port, and source port field) with the original header information (e.g., source address field, destination address field, destination port, and source port field) from the TCP options field. At540, virtual switch106bsends the packet to EP102bbased on the original header of the packet. Accordingly, virtual switches106can select a path for transmitting a network packet by selecting a source port number to include in a header of the packet.

Embodiments described herein may be deployed in a virtual switch of a hypervisor leading to intelligent path selection from the first point of entry of traffic. For example, there could be multiple ECMP paths from the virtual switch onwards, each path using a different physical NIC. In scenarios where all physical NICs connect to the same layer-3 next-hop and path diversity starts beyond the first-hop switch (e.g., ToR switch), examples of the described herein may be implemented in the NIC driver/hardware or on the first-hop switch at faster speeds than in the virtual switch software. Compared to conventional approaches that require advanced switch architectures, examples of the described herein may be performed in the edge hypervisor (e.g., entirely in software) and scale to any number of hops between sources and destinations.