## 5 Dynamic Bandwidth Allocation
### Dynamic Bandwidth Allocation Adjustment
```
1 let \(s_{t,p,f}\) denote the sending traffic rate of flow \(f\) should be limited at the sender for tenant \(t\) on path \(p\);
2 let \(r_{t,p,f}\) denote the receiving traffic rate of flow \(f\) should be limited at the receiver for tenant \(t\) on path \(p\);
3 let \(b_{t,l}\) denote the bandwidth allocated to tenant \(t\) on link \(l\);
4 let \(C_{l}\) denote the capacity of link \(l\);
5\(g_{t,l}\Leftarrow\) the bandwidth guarantee on demand on \(l\) of tenant \(t\);
6\(p\Leftarrow\) get all the mapped paths from Path Collector;
7\(collect()\)\(\dagger\)
8 collect VM-to-VM flows traversing on each link;
9\(\dagger\)
10 periodically(\(\dagger\) for a path \(p\) in \(P\)do
11 a link \(l\in p\) collect()
12\(t_{l}\Leftarrow\) the tenants set on link \(l\);
13\(nt_{l}\Leftarrow\) total tenants on link \(l\);
14\(ft_{l,l}\Leftarrow\) the VM-to-VM flows set belong to tenant \(t\) on link \(l\);
15\(nf_{t,l}\Leftarrow\) total VM-to-VM flows be tenant on link \(l\);
16\(b_{t,l}\Leftarrow\frac{C_{l}-\sum_{t}\,n_{l}\,s_{l}}{nt_{l}}+g_{t,l}\);
17\(r_{t,p,f}\Leftarrow\frac{n_{l}\,s_{l}}{nt_{l}}\);
18\(s_{t,p,f}\Leftarrow r_{t,p,f}\);
19\(\dagger\)
20\(b_{t,l}^{shadow}\Leftarrow\) max-min-allocation\((f_{t,l},b_{t,l}^{shadow})\);
21 for tenant \(t\) in \(t_{l}\)do
22\(r_{t,p,f}^{shadow}\Leftarrow\) max-min-allocation\((f_{t,l},b_{t,l}^{shadow})\);
23 set \(r_{t,p,f}\Leftarrow r_{t,p,f}^{shadow}\);
24 if flow \(f\) is untaggedthen
25 set \(s_{t,p,f}\Leftarrow r_{t,p,f}\);
26 else
27\(k\Leftarrow\) count the active flows having the same destination with the flow \(f\);
28 set \(s_{t,p,f}\Leftarrow\frac{r_{t,p,f}}{k}\);

### VN Type Variation

In the former section, we classify the VN as either blocking or non-blocking network. Regarding non-blocking VN, its endpoints are unnecessary to be attached with functioning congestion control, thereby reducing the CPU overhead of the physical server where VMs reside. However, it is very likely that the type of VN can convert from non-blocking to blocking during the dynamic redundant bandwidth allocation. Though we can take measures to maintain the non-blocking characteristic when allocating redundant bandwidth, it would be contradictory to the VDC-based fairness. Fortunately, it is also possible that some blocking VNs convert to non-blocking network as result of dynamic bandwidth adjustment. Hence, we make congestion control as a triggered manner, by inspecting the VN type in case of bandwidth adjustment, dynamically booting or shutting down the congestion control work at endpoints. We use the maximum flow problem to determine the VN type. First, we select one VM in VN as dst node at the right side and add a source node src at the left side of the other VMs. Then, we add edges from src to these VMs, and assign the bandwidth demand of the corresponding VM as weight of an edge. Thus, it transforms to seeking the maximum flow from src to dst. We iterate this procedure for all other VMs, if the maximum flow is lower than the receiving bandwidth of the dst node, respectively, we consider that the VN type is non-blocking. Otherwise it is blocking. We take the Edmonds-Karp [29] algorithm as an implementation for computing the maximum flow in \(O\left(VE^{2}\right)\) time. Hence, the total time complexity for determining the VN type is \(O(V^{2}E^{2})\). ## 6 Bandwidth Guarantees Enforcement

In Section 5, for the purpose of fully utilizing the network resources, efforts have been made to allocate link bandwidth among tenants in a work-conserving way. However, the tenants have a right to send more traffic than the bandwidth they are allocated with, leading to degradation of network performance. For achieving network performance isolation among tenants, we avoid bandwidth contention on the intermediate links by dynamically limiting the traffic sending rate at the source. Even so, there still exists inevitable congestions for blocking VN in that multiple VMs belonging to one tenant may communicate to the only VM of the same tenant at their full speeds.