Deadline-aware Bulk Transfer Scheduling in Best-effort SD-WANs

Journal Title
Journal ISSN
Volume Title
Wide area networks (WANs) that connect geo-distributed datacenters enable online applications to provide a diversity of services to their users in various locations throughout the world. Inter-datacenter (inter-DC) traffic constitutes a significant portion of today’s world-wide traffic while utilizing dedicated lines that are in different networks than the Internet, making it a very expensive communication. Consequently, inter-DC network providers are keen to minimize their expenses while guaranteeing the quality of service to their customers. As a result, scheduling available resources is of paramount importance to increase the efficacy of these networks for both their providers and customers. In this regard, software-defined wide area networks (SD-WAN) seem to be a promising solution to mitigate legacy WAN’s restrictions such as lack of a global view. While conventional multi-protocol label switching (MPLS) tunnelling has proven to be a practical approach to guarantee performance, its significant service price can be a drawback. Utilizing Internet best-effort paths is a cheap and viable alternative. However, to utilize these paths, we have to take their capacity fluctuations into account to avoid over-allocation. In this thesis, we first characterize and estimate the fluctuations in short and long periods using statistical analysis and machine learning. Next, we take the estimated capacities into account and consider the problem of scheduling bulk transfer requests over best-effort SD-WANs to maximize the gained profit from successful transmissions. Furthermore, we propose an approximate algorithm with a significant computational advantage over our exact algorithm with an approximation ratio that only depends on the number of overlapping requests with the same profit to bandwidth ratio. Finally, we provide a thorough mathematical analysis of the approximate algorithm, as well as simulation and experimental results to evaluate our proposed algorithm’s performance. The results show that our algorithm can improve the inter-DC provider’s profit by an average of 60% while reducing ISP service costs by an average of 15%.
Inter-DC, Resource Scheduling, SD-WAN, SDN
Hosseini Bidi, S. A. (2021). Deadline-aware Bulk Transfer Scheduling in Best-effort SD-WANs (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from