Method and computing device for shaping traffic across a wide area network

A method for shaping traffic across a wide area network is disclosed. The method involves advertising a data rate limit across a wide area network (WAN) from a first node, measuring the rate of data received at a WAN interface of the first node, and, if the measured rate of data received at the WAN interface of the first node exceeds a maximum threshold, advertising a reduced data rate limit across the WAN, and, if the measured rate of data received at the WAN interface of the first node is below a minimum threshold, advertising an increased data rate limit across the WAN.

BACKGROUND

Modern businesses with distributed branches, such as banks or retail locations, are typically interconnected via an enterprise wide area network (WAN). The WAN can be implemented as a physical network or can be implemented in software (e.g., SD-WAN) and can consist of several hubs with each hub having hundreds or thousands of nodes. For example, an enterprise WAN of a bank might have an east coast hub to which hundreds of bank branches along the east coast are connected and a west coast hub to which hundreds of banks branches along the west coast are connected. An east coast bank branch connected to the east coast hub can forward data to other east coast bank branches or to west coast branches by routing data over the east coast hub and west coast hub. Because data is forwarded over hubs before being forwarded to branches, bandwidth limitations at the hubs can cause bottlenecks throughout the network.

SUMMARY

In an embodiment, a method for shaping traffic across a wide area network is disclosed. The method involves advertising a data rate limit across a wide area network (WAN) from a first node, measuring the rate of data received at a WAN interface of the first node, and, if the measured rate of data received at the WAN interface of the first node exceeds a maximum threshold, advertising a reduced data rate limit across the WAN, and, if the measured rate of data received at the WAN interface of the first node is below a minimum threshold, advertising an increased data rate limit across the WAN.

In another embodiment, a data rate limit is advertised to all nodes communicatively coupled to the first node.

In another embodiment, the method further involves advertising the data rate limit to a second node, wherein the advertising to the second node is triggered when data is first received from the second node by the first node.

In another embodiment, the measured rate of data is a dampened measurement determined by averaging a plurality of consecutive measurements.

In another embodiment, advertising the data rate limit by the first node comprises sending Border Gateway Protocol notification messages to nodes communicatively coupled to the first node.

In another embodiment, notification messages sent to nodes of a first tenant advertise a first data rate limit and notification messages sent to nodes of a second tenant advertise a second data rate limit.

In another embodiment, if the first node is receiving more data from the first tenant than the second tenant, advertising a lower data rate limit in the notification messages sent to nodes of the first tenant than the data rate limit advertised in the notification messages sent to nodes of the second tenant.

In another embodiment, if the reduced data rate limit is below a minimum threshold, the reduced data rate limit is not advertised.

In another embodiment, advertising a reduced data rate limit and advertising an increased data rate limit comprises advertising a percent change from the data rate limit.

In another embodiment, upon receiving an initial data transmission from a second node at the first node, advertising a reduced data rate limit to all nodes communicatively coupled to the first node.

In another embodiment, a computing device for shaping traffic across a wide area network is disclosed. The computing device includes a memory and processor, the memory containing instructions that, when executed by the processor, cause the processor to perform steps involving advertising a data rate limit across a wide area network (WAN) from a first node, measuring the rate of data received at a WAN interface of the first node, and if the measured rate of data received at the WAN interface of the first node exceeds a maximum threshold, advertising a reduced data rate limit across the WAN, and if the measured rate of data received at the WAN interface of the first node is below a minimum threshold, advertising an increased data rate limit across the WAN.

In another embodiment, a data rate limit is advertised to all nodes communicatively coupled to the first node.

In another embodiment, wherein the steps performed further involve advertising the data rate limit to a second node, wherein the advertising to the second node is triggered when data is first received from the second node by the first node.

In another embodiment, the measured rate of data is a dampened measurement determined by averaging a plurality of consecutive measurements.

In another embodiment, advertising the data rate limit by the first node comprises sending Border Gateway Protocol notification messages to nodes communicatively coupled to the first node.

In another embodiment, notification messages sent to nodes of a first tenant advertise a first data rate limit and notification messages sent to nodes of a second tenant advertise a second data rate limit.

In another embodiment, if the first node is receiving more data from the first tenant than the second tenant, advertising a lower data rate limit in the notification messages sent to nodes of the first tenant than the data rate limit advertised in the notification messages sent to nodes of the second tenant.

In another embodiment, if the reduced data rate limit is below a minimum threshold, the reduced data rate limit is not advertised.

In another embodiment, advertising a reduced data rate limit and advertising an increased data rate limit involves advertising a percent change from the data rate limit.

In another embodiment, upon receiving an initial data transmission from a second node at the first node, advertising a reduced data rate limit to all nodes communicatively coupled to the first node.

Other aspects and advantages of embodiments of the present invention will become apparent from the following detailed description taken in conjunction with the accompanying drawings.

DETAILED DESCRIPTION

FIG. 1illustrates a software-defined wide area network (SD-WAN)100. As illustrated, the SD-WAN includes multiple interconnected nodes102,104. Nodes can be configured to send data and to receive data transmissions. For simplicity of explanation herein, nodes from which data originates are referred to as “sender nodes”102and nodes that receive the data are referred to as “receiver nodes,” but each node can be configured to send and receive data in practice. Nodes that interconnect sender nodes and forward data over an SD-WAN are referred to as “hubs”104. “Hubs” are configured as gateways to an SD-WAN and are managed by SD-WAN controllers106, which perform virtualization of WAN functionality. In order to provide redundancy, redundant hubs can be used and the nodes of the SD-WAN can be communicatively coupled using an N×N configuration (e.g., each node is coupled to every other node). For example, the node at Seattle Branch office-2001 is communicatively coupled to both Seattle hubs and can send data to either Seattle hub. A sender node can forward data to a recipient node in the SD-WAN by sending the data to a hub to which the sender node is communicatively coupled and the hub can forward the data along to a hub to which the recipient node is communicatively coupled. For example, in order to send data to New York Branch office-1, a node at Seattle Branch office-2001 would send data to one of the redundant Seattle hubs, the hub would forward the data to one of the redundant New York hubs as directed by an SD-WAN controller, and the New York hub would forward the data to a node at New York Branch office-1. In another embodiment, a node at Seattle Branch office-2001 is communicatively coupled to a node at New York Branch office-1 such that data can be sent directly from the node at Seattle Branch office-2001 to the node at New York Branch office-1 without being forwarded to a Seattle hub or a New York hub.

Multiple sender nodes can send data to a receiver node simultaneously.FIG. 2Aillustrates two sender nodes202communicatively coupled to a receiver node204via the Internet210. The illustrated configuration is an example of the connection configuration between branch offices and hubs as illustrated inFIG. 1. InFIG. 2A, each node is configured with an uplink and/or downlink connection208. An uplink is a connection from a node to a WAN cloud (e.g., via the Internet) and a downlink is a connection from the WAN cloud to the node. A connection can be both an uplink and a downlink if bi-directional data flow is supported. For example, the connections between nodes inFIG. 2Acan facilitate traffic flowing from the sender nodes to the receiver node as well as from the receiver node to the sender nodes. InFIG. 2A, if data is sent from the sender nodes to the receiver node (as indicated by the arrows), then the receiver node must have sufficient bandwidth to receive the data or else the data will be dropped. For example,FIG. 2Billustrates a scenario in which the two sender nodes202ofFIG. 2Asimultaneously send data to the receiver node204. The uplink and downlink connections208each have a 1 Gb bandwidth. If both sender nodes send data at a rate of 1 Gbps (e.g., the maximum rate given their bandwidth), then the receiver node would need a 2 Gb connection to receive all of the data. However, because the receiver node only has a 1 Gb connection, data in excess of 1 Gb will be dropped. When data is dropped, a sender node may attempt to re-send the dropped data thus further exacerbating the problem. In other circumstances, where a sender node has a data quota, re-sending the dropped data may not be possible if the data quota is already met.

To prevent data from being dropped, a known solution is to place nodes in groups and create a policy that defines and limits a maximum threshold at which bandwidth can be used to be applied to the group. However, a node needs to be placed in a group before a policy can be applied to the node, which prevents automatic management (e.g., limiting bandwidth usage) of nodes as the nodes join the SD-WAN.

An alternative known solution to prevent data from being dropped is to apply bandwidth shaping on a local egress interface of a node. However, shaping on a local egress interface requires additional processing by a node and, because the shaping is performed by a node independent of other nodes, coordinated shaping among nodes coupled to the same hub is not possible.

In accordance with an embodiment of the invention, a method for shaping traffic across a wide area network is disclosed. The method involves advertising a data rate limit across a WAN from a first node, measuring the rate of data received at a WAN interface of the first node, and, if the measured rate of data received at the WAN interface of the first node exceeds a maximum threshold, advertising a reduced data rate limit across the WAN, and, if the measured rate of data received at the WAN interface of the first node is below a minimum threshold, advertising an increased data rate limit across the WAN. For example, when a receiver node (e.g., a first node) initializes, the receiver node advertises a data rate limit across a WAN to second nodes, such as sender nodes communicatively coupled to the receiver node. In an embodiment, nodes can be directly coupled to each other and, thus, a node can transition between being a sender node and a receiver node in accordance with the flow of traffic. Once data is being received from the sender nodes, the receiver node measures its own bandwidth usage at its WAN interface and advertises a reduced data rate limit or an increased data rate limit as needed. Because the first node is measuring its own bandwidth utilization, the first node can take the rate at which it is receiving data from all nodes communicatively coupled to the first node into consideration when determining a data rate limit to advertise. For example, rather than just arbitrarily advertising a data rate limit that is half of the downlink rate of the first node to three connected nodes, the first node can advertise a data rate limit that is an equal division of the total downlink capacity of the first node to each other node (e.g., one third of the total downlink capacity). Additionally, when a second node is initialized and communicatively coupled to the first node, the first node can advertise the data rate limit directly to the second node. For example, when a new sender node (e.g., a second node) is communicatively coupled to the receiver node, the new sender node will not know the advertised data rate limit for the receiver node. The receiver node can advertise the data rate limit directly to the new sender node. Accordingly, the new sender node can be initialized without first adding the new sender node to a group and applying a policy (e.g., as in known techniques). In another embodiment, the advertisement of the data rate limit to the new sender hub is triggered when the receiver node receives an initial data transmission from the new sender node. Thus, the receiver node does not need to consume bandwidth to advertise the data rate limit until the new sender node begins sending data.

FIG. 3is a graph of bandwidth utilization300recorded by periodically measuring the rate of data received at a WAN interface. In an embodiment, the rate of data can be measured and recorded on a defined interval310. For example, inFIG. 3, four measurements are recorded per second. To dampen a measurement, measurements over several consecutive intervals can be averaged together to determine a dampened measurement. The number of intervals averaged together can be defined by setting a dampening count. For example, inFIG. 3, to dampen measurements over one second intervals, the damping count would be set to four.

Advertised Data Rate Limit

FIG. 4Aillustrates the scenario ofFIG. 2Bin which the receiver node204has been modified to advertise a reduced data rate limit412when a measured rate of data received by the WAN interface of the receiver node (not shown) exceeds a maximum threshold. In the scenario ofFIG. 4A, the sender nodes are each a “second node” as described in accordance with the technique for shaping traffic across a WAN. In an embodiment, the maximum threshold can be defined by a user as a fixed rate (e.g., 312 kbps), as a percentage of the total bandwidth utilization (e.g., 50%), as a percent change from the current data rate limit (e.g., a 5% reduction), or by other techniques for defining a threshold. If both sender nodes202send data at a maximum rate, then the combined data will exceed the bandwidth of the connection of the receiver node. Accordingly, the receiver node advertises a reduced data rate limit to the sender nodes. When the rate of data received is measured again, if the rate of data received still exceeds the maximum threshold, then the receiver node can advertise an even more reduced data rate limit to the sender nodes. The receiver node can continue to further reduce the advertised data rate limit until the rate of data received no longer exceeds the maximum threshold.

Alternatively, if the rate of data received is measured and falls below a minimum threshold, then the receiver node can advertise an increased data rate limit to the sender nodes until the rate of data received exceeds the maximum threshold again (or until the data rate limit returns to a maximum amount equal to one hundred percent of downlink).FIG. 4Billustrates the scenario in which the measured rate of data received at the WAN interface of a receiver node (not shown) is below a minimum threshold. If both sender nodes202are sending data, but the combined data rate limit is less than the minimum threshold, then the receiver node204advertises an increased data rate limit414to the sender nodes. When the rate of data received is measured again, if the sender nodes are still not sending at a rate in excess of the minimum rate, then the receiver node advertises a further increased data rate limit to the sender nodes. The receiver node can continue to further increase the data rate limit until the rate of data received is either no longer below a minimum threshold or the data rate limit cannot be further increased (e.g., when the data rate limit has been raised to one hundred percent of the connection).

Before advertising a data rate limit, connection properties and a data rate limit can be configured at a receiver node.FIG. 5is an example of the configuration profile500at a receiver node. The configuration profile includes, a maximum threshold, a minimum threshold, a percent change, a poll interval, a dampening count, and an enable variable. The maximum threshold sets the value or percentage of a downlink connection of the receiver node that can be in use before advertising of a reduced data rate limit occurs. In the example ofFIG. 5, when 50% or more of the downlink connection of the receiver node is in use, advertising of a reduced data rate limit occurs. The minimum threshold sets the value or percentage of the downlink connection of the receiver node that must be in use. If usage drops below the minimum threshold, advertising of an increased data rate limit occurs. In the example ofFIG. 5, if usage drops below 20%, then advertising of an increased data rate limit occurs. The percent change defines the increment by which the advertisement increases or reduces the data rate limit. In the example ofFIG. 5, if a data rate limit needs to be advertised, the advertised data rate limit will be a 10% change from the current data rate limit. The poll interval sets the frequency with which the rate of data received is measured. In the example ofFIG. 5, the poll interval is set to five and so the rate of data received is measured on five second intervals. The damping count is the number of poll intervals to wait before determining if the rate of data received exceeds the maximum threshold or is below the minimum threshold. In the example ofFIG. 5, the damping count is set to one so a single measurement where the rate of data received exceeds the maximum threshold or is below the minimum threshold would trigger advertising of a new data rate limit. The enable variable allows for the above described technique to be turned on or turned off. In the example ofFIG. 5, the enable variable is set to true so the technique is enabled.

When a receiver node determines a data rate limit, the receiver node communicates the data rate limit to sender nodes. In an embodiment, the data rate limits can be communicated using an extension of a Border Gateway Protocol (BGP) in BGP notification messages.FIG. 6is a further example of a configuration profile600of a receiver node. In the example, a link on a WAN interface is identified (e.g., vni-0/0.1) and a maximum threshold and a minimum threshold are communicated. In the example ofFIG. 6, the maximum threshold is communicated as an input-rate of 500 mbps (500,000 kbps) and the minimum threshold is communicated as a minimum input rate of 1 mbps (1000 kbps).

In addition to advertising a data rate limit to all sender nodes, different data rate limits can be advertised to sender nodes on a tenant by tenant basis. A tenant refers to a user to whom multiple nodes can belong. For example, each business in a multi-tenant office building can be a tenant and computers within each office can be sender nodes belonging to each tenant.FIG. 7Aillustrates two sender nodes702belonging to a first tenant750A and one sender node702belonging to a second tenant750B communicatively coupled to a receiver node704via connections708to the Internet710. In an embodiment, if both sender nodes belonging to the first tenant send data at a maximum rate and the sender node belonging to the second tenant sends data at a maximum rate, then the combined rate at which data is sent may exceed the bandwidth of the receiver node. However, rather than advertise a reduced data rate limit to all sender nodes evenly, the receiver node can advertise a reduced data rate limit712to sender nodes proportional to the use by each tenant. Accordingly, the data rate limit for sender nodes of the tenant using less of the bandwidth of the receiver node will receive a higher advertised data rate limit than the sender nodes of the tenant using more of the bandwidth of the receiver node. The amount of bandwidth used by each tenant can be determined using known techniques for determining usage. For example, a greater reduced data rate limit can be advertised to sender nodes determined to belong to the first tenant (e.g., 25% of the total downlink bandwidth) than to the sender node determined to belong to the second tenant (e.g., 50% of the total downlink bandwidth) because the first tenant is using a greater portion of the downlink connection of the receiver node than the second tenant.

FIG. 7Billustrates the configuration asFIG. 7Awhen the rate of data received at the WAN interface of the receiver node is below a minimum threshold. If the sender nodes belonging to the first tenant are sending more data than the sender node belonging to the second tenant (e.g., individually or combined), then the data rate limit for the sender nodes belonging to the first tenant can be increased at a slower rate than the data rate limit for the sender node belonging to the second tenant. Accordingly, the increased data rate limit714advertised to sender nodes of the tenant using less bandwidth of the receiver node will receive a higher advertised data rate limit than the sender nodes of the tenant using more bandwidth of the receiver node.

When a sender node receives an advertised rate from a receiver node, the sender node configures an egress interface used for forwarding data to the receiver node to have a data rate limit as advertised by the receiver node. For example, if a sender node forwards data to a receiver node via interface vni-0/0 and receives an advertised data rate limit of 710000 kbps, then the sender node will configure interface-0/0 to use a data rate limit of 710000 kbps. In an N×N configuration, a sender node can be communicatively coupled to many receiver nodes and can receive advertised data rate limits from each of the receiver nodes. In order to configure a port for each advertised data rate limit, the sender node may configure and store a configuration profile for a number of ports equal to the number of receiver nodes communicatively coupled to the sender node. However, due to memory or other limitations, a sender node may be limited in the number of different ports it can configure and store. For example, a sender node may only be able to configure and store configuration profiles for 98 different ports. Because only 98 different port configurations can be stored, if more than 98 receiver nodes advertise a data rate limit, then data rate limits will be ignored. For example, if a 99thdata rate limit is advertised to the sender node by a new receiver node, then the sender node would not be able to accommodate the 99thdata rate limit.

In order to accommodate data rate limits for all receiver nodes, rate slabbing can be used. Rate slabbing may involve dividing the bandwidth of an uplink connection of a sender node into a number of data rate limits called “slabs”. The number of slabs can be equal to the maximum number of configuration profiles the sender node can store, but a smaller number of slabs can be used as well. When the sender node receives an advertised data rate limit, the sender node can select a slab by mapping the advertised data rate limit to a slab data rate limit. In an embodiment, a data rate limit can be mapped to a slab data rate limit by rounding down to the closest slab data rate limit.FIG. 8illustrates an exemplary truncated list800of rate slabs802. In the example, the rate slabs correspond to a 1 GB port, but the bandwidth can vary with the port speed and uplink bandwidth configured on the sender node in accordance with an embodiment of the invention. In the example ofFIG. 8, each rate slab corresponds to a different data rate limit. For example, rate slab 1 corresponds to a data rate limit of 383 kbps, while rate slab 98 corresponds to a data rate limit of 906,317 kbps (approx. 906 mbps). In an embodiment, a sender node using the list of slabs shown inFIG. 8would use a data rate limit of 708464 kbps when sending data to a receiver node advertising a data rate limit of 710000 kbps because a data rate limit of 710000 kbps rounds down to 708464 kbps, which is the data rate limit of slab 93. Accordingly, a large number of advertised data rate limits can be accommodated by mapping the advertised data rate limits to slabbed data rate limits.

FIG. 9is a flow chart diagram of a method for shaping traffic across a wide area network. At block902, a data rate limit is advertised across a WAN from a first node. In an embodiment, the data rate limit is advertised as a rate at which data can be received and is a predefined value. At block904, the rate of data received at a WAN interface of the first node is measured. In an embodiment, the rate of data received at a WAN interface of the first node is measured on a defined interval and can be measured on a per tenant basis. In another embodiment, a measurement of the rate at which data can be received is determined by a plurality of consecutive measurements. At decision point906, if the measured rate of data received by the WAN interface of the first node exceeds a maximum threshold, then, at block908, a reduced data rate limit is advertised across the WAN. In an embodiment, the reduced data rate limit is advertised as a percent change from the data rate limit and can be advertised to all nodes communicatively coupled to the first node at once. For example, if two nodes are communicatively coupled to the first node, then a notification can be sent to both nodes simultaneously advertising the reduced data rate limit. If, at decision point906, the measured rate of data received at the WAN interface of the first node does not exceed a maximum threshold, then the technique moves to decision point910. At decision point910, if the measured rate of data received at the WAN interface of the first node is not below a minimum threshold, the technique can return to block904or wait a period of time (e.g., a period of time defined by the poll interval ofFIG. 5) and, if the measured rate of data received by the WAN interface of the first node is below a minimum threshold, then, at block912, an increased data rate limit is advertised across the WAN. In an embodiment, the increased data rate limit is advertised as a percent change from the data rate limit and can be advertised to all nodes communicatively coupled to the first node at once.

FIG. 10is a block diagram of a computer1000that includes a processor1002, memory1004, and a communications interface1006. The processor may include a multifunction processor and/or an application-specific processor. Examples of processors include the PowerPC™ family of processors by IBM and the x86 family of processors by Intel. The memory within the computer may include, for example, a non-transitory storage medium such as read only memory (ROM), flash memory, RAM, and a large capacity permanent storage device such as a hard disk drive. The communications interface enables communications with other computers via, for example, the Internet Protocol (IP). The computer executes computer readable instructions stored in the storage medium to implement various tasks as described above.

It should also be noted that at least some of the operations for the methods may be implemented using software instructions stored on a non-transitory computer-readable storage medium for execution by a computer. As an example, an embodiment of a non-transitory computer-readable storage medium includes a computer useable storage medium configured to store a computer readable program that, when executed on a computer, causes the computer to perform operations, as described herein.