1. Introduction
MANY large-scale applications in various science, engineering, and business domains require fast and reliable transfer of big data over long distances for remote operations. High-performance networks (HPNs), which feature high link bandwidths and are capable of performing advance bandwidth reservation, have emerged as a promising solution for the unprecedented requirement of big data transfer. Such networks provision dedicated channels with reserved bandwidth using circuit-switching infrastructures as exemplified by UltraScience Net [1] and CHEETAH [2], or IP-based tunneling techniques as exemplified by OSCARS [3] of ESnet and AL2S [4] of Internet2. Typically, the bandwidth scheduler in HPNs is responsible for computing an appropriate network path and allocating link bandwidths to meet a user’s data transfer request based on the network topology and bandwidth availability [5], [11], [13], [18].
Considering the sheer volume of data transfer, an increasing number of real-life bandwidth reservation systems adopt multipath routing instead of single-path routing to improve data transfer throughput. However, multi-path routing also introduces extra overhead to both the control plane and the data plane of a network [19]. Multipath routing could be either link or node disjoint, with varying complexity in different circumstances. Particularly, node-disjoint paths are able to establish multiple completely independent data channels between source and destination, and hence can effectively increase transmission bandwidth and reliability [17]
Many problems on single-path bandwidth scheduling have been proved to be NP-complete [31], which sheds light on the difficulty of multi-path routing. For example, several studies have shown that the problems with multiple constrained paths (MCP) are generally NP-complete [20], [21]. Furthermore, finding disjoint paths with a single constraint is also an NP-hard problem [22]–[26]. The two-path routing problem with reliability consideration is NP-hard in the strong sense, as opposed to the ordinary NP-completeness of the single-path problem [27].
Multipath routing improves throughput in general, but also introduces non-negligible overhead to both the control plane and the data plane of an HPN. Especially for variable paths, it frequently requires path switching between adjacent time slots, and performing an excessive number of path switchings not only degrades transport performance but also increases implementation complexity. Furthermore, if one user request takes up too many paths (resources), it may cause a serious fairness issue to others. Therefore, to find a good tradeoff between high throughput, system overhead, transport robustness, and ease of implementation, we consider two node-disjoint paths in this work.
We formulate a generic problem of bandwidth scheduling with two variable node-disjoint paths (BS-2VNDP) to support big data transfer in HPNs. In BS-2VNDP, we consider two cases with two variable paths of either fixed or variable bandwidth, referred to as 2VPFB and 2VPVB, or 2VPFB/VB for brevity. Note that using variable paths during a data transfer session requires some support from the network infrastructure to perform path switching, which may incur a certain switching delay [TeX:] $$\tau.$$ Therefore, we further divide 2VPFB/VB into two cases where the path switching delay is negligible [TeX:] $$(i.e., \tau=0 )$$ and non-negligible [TeX:] $$(i.e., , \tau \neq 0 ),,$$ referred to as 2VPFB/VB-0 and 2VPFB/VB-1, respectively. We prove that all of these four problems with different combinations of bandwidth variability and switching delay negligibility are NP-complete, and design a heuristic approach for each. For performance comparison, we also design several other heuristic algorithms based on a greedy strategy. We implement and test these bandwidth scheduling algorithms in both simulated and real-life networks, and extensive results show that the proposed Imp2VPFB-0, Imp2VPFB-1, and Imp2VPVB-1 algorithms achieve about 10–20%, 12–35%, and 5% performance improvement on average over Greedy2VPFB- 0, Greedy2VPFB-1, and Greedy2VPVB-1 in comparison, respectively.
The rest of this paper is organized as follows. We provide a survey of related work on multi-path bandwidth scheduling in Section II. We formulate the BS-2VNDP problem variants and conduct complexity analysis in Section III. In Section IV, we present the algorithm design with detailed explanations. Extensive simulations are conducted and described in Section V. We conclude our work in Section VI.
II. RELATED WORK
Different problems regarding multiple disjoint paths have been extensively studied for decades in various contexts. We provide below a survey of such efforts that are closely related to our work.
Several researchers studied the problem of finding maximum combined bandwidth in node-disjoint paths. In [25], Dahshan proved that such problems with node-disjoint paths in communication networks are NP-complete, and proposed a solution using a maximum-cost variant of Dijkstra’s algorithm and a virtual-node representation to obtain maximum-bandwidth node-disjoint paths. In [24], Shen et al. discussed the problem of finding a pair of edge- or node-disjoint paths with maximum combined bandwidth, including widest pair of disjoint paths coupled (WPDPC) and widest pair of disjoint paths decoupled (WPDPD). They proved that both versions of the problem are NP-complete, and provided exact solutions using ILP and two approximate solutions. In [30], a link-disjoint or node-disjoint multi-path routing strategy is developed using two colored trees, red and blue, rooted at a designated node called the drain. The paths from a given source to the drain on these two trees are linkdisjoint or node-disjoint. This approach requires every node to maintain only two preferred neighbors for each destination, one on each tree. In [29], a distributed distance-vector algorithm is used to find multiple node-disjoint paths including the shortest path in a computer network.
Most of the aforementioned work considers static networks for path computing, and the routes computed in such static networks correspond to those computed in a single time slot in dynamic networks with time-varying link bandwidths across multiple time slots. There also exist several efforts on bandwidth scheduling in dynamic HPN networks, [31], [32], [36], [38]. In [35], Zuo et al. investigated the problem of scheduling as many concurrent bandwidth reservation requests as possible over different paths in an HPN while achieving the average earliest completion time (ECT) and the average shortest duration (SD) of scheduled BRRs. These two problems were proved to be NP-complete, and heuristic algorithms were proposed. In [37], Zuo et al. considered two generic types of bandwidth reservation requests concerning data transfer reliability: (i) To achieve the highest data transfer reliability under a given data transfer deadline, and (ii) to achieve the earliest data transfer completion time while satisfying a given data transfer reliability requirement. Optimal scheduling algorithms with optimality proofs are proposed.
In [31], [32], Lin and Wu investigated single-path bandwidth scheduling with an exhaustive combination of different path and bandwidth constraints: i) Fixed path with fixed bandwidth (FPFB), ii) fixed path with variable bandwidth (FPVB), iii) variable path with fixed bandwidth (VPFB), and iv) variable path with variable bandwidth (VPVB). These four problems have the same objective to minimize the data transfer end time for a given transfer request with a pre-specified data size. To support big data transfer, our work extends single-path routing to multi-path routing to minimize the data transfer end time and achieve a higher quality of service (QoS). Note that multi-path routing could be leveraged from software-defined networking (SDN) technologies to realize complex network operations and control [12], [18]. For example, in [12], Aktas et al. used SDN to provide data transport service control and resource provisioning to meet different QoS requirements from multiple coupled workflows sharing the same service medium. They presented a flexible control and a disciplined resource scheduling approach for data transfer. In [16], Hou et al. studied bandwidth scheduling with two fixed node-disjoint paths for concurrent data transfer. In this work, we consider variable paths to achieve a higher resource utilization than fixed paths.
III. PROBLEM FORMULATION
In this section, we firstly show the scheduling network model, followed by the problem definition and complexity analysis.
A. Network Model
The topology of an HPN can be represented as a graph G(V,E) with [TeX:] $$|V|$$ nodes and[TeX:] $$|E|$$ links, where each link [TeX:] $$l \in E$$ maintains a list of residual bandwidths specified as a segmented constant function of time. We use a 3-tuple of time-bandwidth (TB) [TeX:] $$\left(t_{l}[i], t_{l}[i+1], b_{l}[i]\right)$$ to denote the residual bandwidth [TeX:] $$b_{l}[i]$$ of link l during the i-th time-slot (i.e., the time interval [TeX:] $$\left.\left[t_{l}[i], t_{l}[i+1]\right]\right), i=0,1,2, \cdots, T_{l}-1,$$ where [TeX:] $$T_{l}$$ is the total number of time-slots on link l.
Before path computing, we combine the TB lists of all links to build an aggregated TB (ATB) list, where we store the residual bandwidths of all links in each intersected time-slot. As shown in Fig. 1, we create a set of new time slots by combining the time slots of all links, and then map the residual bandwidths of each link to the ATB list in each new time slot. We denote the ATB list as [TeX:] $$\left(t[0], t[1], b_{0}[0], b_{1}[0], \cdots, b_{|E|-1}[0]\right), \cdots \left(t[T-1], t[T], b_{0}[T-1], b_{1}[T-1], \cdots, b_{|E|-1}[T-1]\right),$$ where T is the total number of new time-slots after the aggregation of TB lists of [TeX:] $$|E|$$ links. Without loss of generality, we set the smallest time-slot to be 1 time unit.
B. Problem Definition
We define a generic problem of BS-2VNDP as follows [5].
Definition 1: BS-2VNDP: Given a graph G(V,E) of an HPN with an ATB list for all links, and a user request that specifies source [TeX:] $$v_{s},$$ destination [TeX:] $$v_{d},$$ and data size [TeX:] $$\delta,$$ we wish to find
An aggregated TB list by combining two individual TB lists.
two variable node-disjoint paths for the transfer of data size [TeX:] $$\delta$$ from [TeX:] $$v_{s} \text { to } v_{d}$$ such that the data transfer end time is minimized, or equivalently, sum of the bandwidths of these two paths is maximized.
In BS-2VNDP, we consider two cases based on the bandwidth variability of each path, as defined below [5].
Definition 2: 2VPFB: Given the above network model and user request, the goal is to find two variable node-disjoint paths from [TeX:] $$v_{s} \text { to } v_{d},$$ each of which has a fixed bandwidth across different time-slots, such that the data transfer end time is minimized.
Definition 3: 2VPVB: Given the above network model and user request, the goal is to find two variable node-disjoint paths from [TeX:] $$v_{s} \text { to } v_{d},$$ each of which could have variable bandwidths across different time-slots, such that the data transfer end time is minimized.
In 2VPFB/2VPVB, considering the path switching delay [TeX:] $$\tau,$$ we further consider two different types of service models: i) The path switching delay is negligible [TeX:] $$(i.e., \tau=0 ),,$$ referred to as 2VPFB-0/2VPVB-0, and ii) the path switching delay is not negligible [TeX:] $$(i.e., \tau>0 ),,$$ referred to as 2VPFB-1/2VPVB- 1. Note that path switching may happen between two adjacent time slots, either at the end of one time-slot or at the beginning of its succeeding time-slot. Generally, it should be performed at the time slot with a lower bandwidth because the data transfer process is suspended during the period of path switching.
For illustration, we provide an example network in Fig. 2, which has seven nodes, a pair of which are designated as source and destination, and eleven links, each of which has residual bandwidths across two time-slots starting from time point 0 as labeled on the link. The other parameters include data size [TeX:] $$\delta=19$$ units and path switching delay [TeX:] $$\tau=0.1$$ unit of time.
In 2VPFB-0, the optimal solution is shown in Fig. 3(a). In the first time-slot, we find two node-disjoint paths: [TeX:] $$p_{1}[0]: v_{s}-v_{2}-v_{3}-v_{d}$$ (with maximum bandwidth of 6 in time-slot 0), and [TeX:] $$p_{2}[0]: v_{s}-v_{1}-v_{4}-v_{d}$$ (with bandwidth of 4, which is also the maximum in the current network except
An example HPN with link bandwidths.
the nodes in use). In the second time-slot, we also find two node-disjoint paths with the maximum bandwidth in the current network: [TeX:] $$p_{1}[1]: v_{s}-v_{2}-v_{5}-v_{d}$$ (with maximum bandwidth of 10), and [TeX:] $$p_{2}[1]: v_{s}-v_{1}-v_{3}-v_{4}-v_{d}$$ (with bandwidth of 7). Obviously, the transfer of data [TeX:] $$\delta=19$$ cannot be completed in time-slot 0, so data transfer will continue to time-slot 1. Since we consider fixed bandwidth (i.e., the bandwidth remains constant during the entire data transfer period), the available bandwidth of [TeX:] $$p_{1}[1] \text { and } p_{2}[1]$$ is the same as that of [TeX:] $$p_{1}[0] \text { and } p_{2}[0],$$ respectively. Therefore, sum of bandwidths in both time-slots is the same as [TeX:] $$\beta=6+4=10.$$ For data size [TeX:] $$\delta=19,$$ the total data transfer end time is 19/10 = 1.9.
In 2VPFB-1, the optimal solution is shown in Fig. 3(b), where the two node-disjoint paths and the sum of their respective bandwidths are the same as in 2VPFB-0. Since both of the time-slots have the same fixed bandwidth on each path, the path switching could be performed either at the end of the first time-slot (i.e., time interval [0.9, 1]), or at the beginning of the second timeslot (i.e., time interval [1, 1.1]). For data size [TeX:] $$\delta=19,$$ the data transfer end time is calculated as [TeX:] $$9 / 10+0.1+10 / 10=2.$$
In 2VPVB-0, the optimal solution is shown in Fig. 3(c). In the first time-slot, we find two node-disjoint paths: [TeX:] $$p_{1}[0]:v_{s}-v_{2}-v_{3}-v_{d}$$ (with maximum bandwidth of 6), and [TeX:] $$p_{2}[0]:v_{s}-v_{1}-v_{4}-v_{d}$$ (with bandwidth of 4, which is also the maximum in the current network except the nodes in use). The sum of bandwidths in the first time-slot is [TeX:] $$\beta[0]=6+4=10.$$ In the second time-slot, we also find two node-disjoint paths: [TeX:] $$p_{1}[1]: v_{s}-v_{2}-v_{5}-v_{d}$$ (with maximum bandwidth of 10), and [TeX:] $$p_{2}[1]: v_{s}-v_{1}-v_{3}-v_{4}-v_{d}$$ (with bandwidth of 7, which is also the maximum in the current network except the nodes in use). Sum of the bandwidths in the second time-slot is [TeX:] $$\beta[1]=10+7=17.$$ For data size [TeX:] $$\delta=19,$$ the data transfer end time is 10/10 + 9/17 = 1.53.
In 2VPVB-1, the optimal solution is shown in Fig. 3(d), where the two node-disjoint paths and sum of their respective bandwidths are the same as in 2VPVB-0. Since sum of path bandwidths in the first time-slot is smaller than that in the second time-slot, the path switching of both paths should be performed at the end of the first time-slot (i.e., time interval [0.9, 1]). For data size [TeX:] $$\delta=19,$$ the data transfer end time is 9/10 + 0.1 + 10/17 = 1.59.
C. Problem Complexity Analysis
The 2VPFB/VB-0 and 2VPFB/VB-1 problems as formulated are more general than their counterparts in static networks with constant link bandwidths [22]–[25], [27].
Illustration of 2VPFB-0/1 and 2VPVB-0/1: (a) 2VPFB-0, (b) 2VPFB-1, (c) 2VPVB-0, and (d) 2VPVB-1.
To analyze the computational complexity of these problems, we first introduce the WPDPC problem, as defined and proved to be NP-complete in [24].
Definition 4: WPDPC: given a network with a fixed bandwidth for each link, does there exist two disjoint paths [TeX:] $$P_{1}$$ and [TeX:] $$P_{2}$$ from [TeX:] $$v_{s} \text { to } v_{d},$$ such that the sum of the bandwidths of these two paths is greater than or equal to X?
WPDPC is to compute two edge-/node-disjoint paths with the largest sum of bandwidths in a single time slot, which is a special case of our problems using two disjoint variable paths across multiple time slots, as detailed below.
C.1 Complexity of 2VPFB-0
We have the following theorem for the complexity of 2VPFB-0.
Theorem 1: 2VPFB-0 is NP-complete.
Proof: We first show that [TeX:] $$2 \mathrm{VPFB}-0 \in N P.$$ The decision version of 2VPFB-0 is as follows: Given the network model and user request, are there two variable node-disjoint paths from [TeX:] $$v_{s} \text { to } v_{d},$$ each of which has a fixed bandwidth across different time-slots, such that the data transfer end time is no larger than a given bound T without considering the path switching delay? Given two variable node-disjoint paths from [TeX:] $$v_{s} \text { to } v_{d},$$ we can identify the available fixed bandwidth of these two paths and further check whether the data transfer end time is no larger than T. Obviously, the above process can be done in polynomial time, so [TeX:] $$2 \mathrm{VPFB}-0 \in N P.$$
The NP-hardness of 2VPFB-0 could be established through proof-by-restriction. We consider a special case of 2VPFB-0 where the bandwidth of each link keeps the same across all timeslots. Obviously, any instance of WPDPC could be mapped to the above special case of 2VPFB-0, and such mapping could be done in polynomial time. If we could find two paths satisfying WPDPC, these two paths could also satisfy 2VPFB-0 [TeX:] $$(t=\delta / X),$$ and vice versa [TeX:] $$(X=\delta / t).$$ Therefore, 2VPFB-0 is at least as hard as WPDPC.
Since a special case of 2VPFB-0 is NP-complete, so is the general 2VPFB-0 problem with time-varying link bandwidths. Proof ends.
C.2 Complexity of 2VPFB-1
We have the following lemma for the complexity of 2VPFP-1.
Lemma 1: 2VPFB-1 is NP-complete.
Proof: We prove the NP-completeness of 2VPFB-1 by showing that 2VPFB-0 is a special case of 2VPFB-1. This is straightforward as we can restrict 2VPFB-1 to 2VPFB-0 by only considering those problem instances where the path switching delay is negligible [TeX:] $$(i.e., \tau=0 )..$$ Since 2VPFB-0 is NP-complete, so is 2VPFB-1.
C.3 Complexity of 2VPVB-0
We have the following lemma for the complexity of 2VPVB-0.
Lemma 2: 2VPVB-0 is NP-complete.
Proof: Similar to the proof of Theorem 1, we can prove the NP-completeness of 2VPVB-0 by showing that the WPDPC problem [244] is a special case of 2VPVB-0. We restrict 2VPVB- 0 to WPDPC by only considering those problem instances where the bandwidth of each link remains constant across all timeslots. In other words, there is no need to switch paths between any adjacent time-slots. Hence, WPDPC is a special case of 2VPVB-0 when the network is static with constant link bandwidths. Since WPDPC is NP-complete [24], so is 2VPVB-0.
C.4 Complexity of 2VPVB-1
We have the following lemma for the complexity of 2VPVB-1.
Lemma 3: 2VPVB-1 is NP-complete.
Proof: The NP-completeness of VPVB-1 has been established in [31] by showing that FPVB, which is NP-complete, is a special case of VPVB-1. Obviously, 2VPVB-1 is a more general version of VPVB-1 that computes multiple concurrent VPVB-1 paths.
IV. DESIGN OF SCHEDULING ALGORITHMS
The NP-completeness of 2VPFB/VB-0/1 indicates that there does not exist any polynomial-time optimal algorithm unless P = NP. Therefore, we focus on the design of heuristic algorithms for 2VPFB/VB-0/1.
The NP-completeness of 2VPFB/VB-0/1 indicates that there does not exist any polynomial-time optimal algorithm unless P = NP. Therefore, we focus on the design of heuristic algorithms for 2VPFB/VB-0/1.
A. Heuristic Scheduling Algorithms for 2VPFB-0
In 2VPFB-0, we compute two node-disjoint paths in time-slot [TeX:] $$[0, i], i \leq T-1,$$ each of which is allowed to use different routes with zero path switching delay across different time-slots, while the bandwidth must be fixed.
A.1 Greedy Algorithm for 2VPFB-0
We design a polynomial-time greedy algorithm, Greedy2VPFB-0, whose pseudocode is provided in Algorithm 1. The algorithm computes two variable node-disjoint path sets [TeX:] $$(i.e., p_{1} and p_{2} )$$ with fixed bandwidth, on which data of size [TeX:] $$\delta$$ has the earliest transfer end time (i.e., maximum sum of fixed bandwidths). Each path set is composed of paths [TeX:] $$p_{1}[i] \text { and } p_{2}[i]$$ from [TeX:] $$v_{s} \text { to } v_{d}$$ with maximum bandwidth [TeX:] $$\beta_{1}[i] \text { and } \beta_{2}[i]$$ using Dijkstra’s algorithm at different time-slots. The bandwidths of [TeX:] $$p_{1} \text { and } p_{2}$$ are [TeX:] $$\beta_{1}=\min \left(\beta_{1}[0], \cdots, \beta_{1}[i]\right) \text { and } \beta_{2}=\min \left(\beta_{2}[0], \cdots, \beta_{2}[i]\right),$$ respectively. The algorithm checks if the data of size [TeX:] $$\delta$$ can be concurrently transferred by the path-pair during the time-slot range [0, i] (i.e., time interval [t[0], t[i+1]]). If paths in these two path sets could not finish the data transfer, we move onto the next time slot; otherwise, we compute the transfer end time [TeX:] $$t_{\mathrm{end}}.$$ At the end, [TeX:] $$t_{\mathrm{end}}$$ is returned. If [TeX:] $$t_{\mathrm{end}}=\infty,$$ it means that we could not finish the data transfer of size [TeX:] $$\delta$$ within T time slots. Note that the data size to be transferred by each path set is proportional to its bandwidth during the data transfer period.
Since the time complexity of Dijkstra’s algorithm is [TeX:] $$O\left(|V|^{2}\right),$$ the time complexity of Greedy2VPFB-0 is [TeX:] $$O\left(T \cdot|V|^{2}+T\right)$$ in the worst case, where T is the total number of new time slots in the ATB list.
A.2 Improved Algorithm for 2VPFB-0
In Greedy2VPFB-0, for a given data size , the bandwidths of path sets [TeX:] $$p_{1} \text { and } p_{2}$$ are determined by the bandwidths of the
bottleneck paths, namely the paths with the least available bandwidths among all paths in [TeX:] $$p_{1} \text { and } p_{2},$$ respectively. Although the bandwidth of each path is maximized in each time-slot, there is no guarantee that the concurrent transfer end time by the pathpair for data size is minimized from a global perspective. Since the bandwidth of each path during transfer period [0, i] is fixed, it may not be always optimal to start data transfer immediately, for example, when the path bandwidths in the preceding timeslots are much smaller than those in the succeeding time-slots during the transfer period. In this case, we may start the data transfer at the beginning of some time-slot after time-slot 0 to improve Greedy2VPFB-0, referred to as Imp2VPFB-0.
The pseudocode of Imp2VPFB-0 is provided in Algorithm 2. For a given time-slot i, Imp2VPFB-0 computes the widest pathpair from [TeX:] $$v_{s} \text { to } v_{d}$$ in the time-slot i, and then repeatedly checks if the given data can be transferred during time-slot [j, i], [TeX:] $$i \geq j \geq 0.$$ If there exists certain j such that the data of size can be transferred during time-slot [j, i] (i.e., time interval [TeX:] $$[t[j], t[i+1]]),$$ the data transfer start time is t[j] and the data transfer end time is computed as shown in Line 12 of Algorithm 2; otherwise, Imp2VPFB-0 increases i by 1. The earliest data transfer end time [TeX:] $$t_{\mathrm{end}}$$ is returned at the end.
The same as in Greedy2VPFB-0, the data size to be transferred by each path set in Imp2VPFB-0 is also proportional to its bandwidth during the data transfer period. Since the time complexity of Dijkstra’s algorithm is [TeX:] $$O\left(|V|^{2}\right),$$ the complexity of Imp2VPFB-0 is [TeX:] $$O\left(T \cdot|V|^{2}+T^{2}\right)$$ in the worst case.
B. Heuristic Scheduling Algorithms for 2VPFB-1
For 2VPFB-1, the path-switching delay is not negligible. Since each path set (such as [TeX:] $$p_{1} \text { and } p_{2}$$ ) has a fixed bandwidth, a path switching with a delay [TeX:] $$\tau>0$$ could occur either at the end of one time-slot or at the beginning of its succeeding time-slot. Since data transfer is suspended during the period of path switching, it may not be always beneficial to perform path switching between two adjacent time-slots. In the extreme case
where [TeX:] $$\tau$$ is sufficiently large, any path switching would cause a negative impact on the performance, and therefore 2VPFB-1 reduces to 2FPFB. In this paper, we assume that [TeX:] $$\tau$$ is a constant and smaller than the length of any time-slot on the ATB list.
B.1 Greedy Algorithm for 2VPFB-1
We design a polynomial-time greedy algorithm, Greedy2VPFB-1, whose pseudocodes is provided in Algorithm 3. Firstly, it computes the node-disjoint path pair with the maximum bandwidth, i.e., [TeX:] $$p_{1}[i] \text { and } p_{2}[i],$$ in every time-slot, [TeX:] $$i=0,1, \cdots, T-1.$$ During time slot [0, i], the bandwidths of [TeX:] $$p_{1} \text { and } p_{2} \text { are } \beta_{1}=\min \left(\beta_{1}[0], \cdots, \beta_{1}[i]\right) \text { and } \beta_{2}=\min \left(\beta_{2}[0], \cdots, \beta_{2}[i]\right).$$ Each path may perform a path switching at every adjacent time-slot to use the path pair with the maximum bandwidths. There are i path switchings during the data transfer, and the total switching delay is [TeX:] $$\tau.$$ i. The maximum amount of transferred data by path pair [TeX:] $$p_{1} \text { and } p_{2}$$ concurrently during the time-slot range [0, i] with i path switchings is [TeX:] $$\left(\beta_{1}+\beta_{2}\right) \cdot(t[i+1]-t[0]-\tau \cdot i).$$ If it is greater than or equal to the data size , then the data transfer is completed.
Since the time complexity of Dijkstra’s algorithm is [TeX:] $$O\left(|V|^{2}\right),$$ the complexity of Greedy2VPFB-0 is [TeX:] $$O\left(T \cdot|V|^{2}\right)$$ in the worst case.
B.2 Improved Algorithm for 2VPFB-1
Greedy2VPFB-1 starts data transfer immediately at time point t[0] and performs path switching in every adjacent timeslot, neither of which may not be always optimal. The improved algorithm for 2VPFB-1, referred to as Imp2VPFB-1, varies the transfer start time and, meanwhile, reduces the number of path switchings between different time-slots to improve the performance. The pseudocode of Imp2VPFB-1 is provided in Algorithm 4.
In Line 3, it initializes [TeX:] $$t_{\mathrm{end}}=\infty$$ (transfer end time for ), [TeX:] $$k_{1}=0$$ (the path-switching time of [TeX:] $$p_{1} \text { ) and } k_{2}=0$$ (the pathswitching time of [TeX:] $$\left.p_{2}\right).$$
In Lines 6–12, during time slot [p, q], under the condition of fixed bandwidth, it optimizes the first path [TeX:] $$p_{1}$$ so that the number of path-switchings is minimized. For a certain transfer start time-slot p and a certain transfer end time-slot j, we can optimize path [TeX:] $$p_{1}$$ such that it has the minimum number of path switchings during time slot [p, q]. In Line 6, we firstly compute the maximum available fixed bandwidth [TeX:] $$\beta_{1}[p, q] \text { of } p_{1}$$ during the time slot range [p, q] with q - p times of path switchings in the worst case, which can be used as a reference value to decide if we should perform a path switching between any two adjacent time-slots. We use [TeX:] $$p_{1}[j]$$ to denote path [TeX:] $$p_{1}$$ with the maximum bandwidth in time-slot j, and its bandwidth in the next timeslot j + 1 is denoted as [TeX:] $$\beta_{1}^{\prime}[j+1] . \text { If } \beta_{1}^{\prime}[j+1]==\beta_{1}[j+1]$$ or [TeX:] $$\beta_{1}^{\prime}[j+1] \geq \beta_{1}[p, q]$$ then there is no need to perform path switching between time slot j and j + 1 (i.e., we keep the [TeX:] $$p_{1}[j]$$ in the time-slot j + 1 and let [TeX:] $$p_{1}[j+1]=p_{1}[j]$$). Otherwise, it switches path [TeX:] $$p_{1}[j]$$ to path [TeX:] $$p_{1}[j+1]$$ with the widest bandwidth in time-slot j +1, and increases the number of switchings [TeX:] $$k_{1}$$ on path [TeX:] $$p_{1}$$ by 1.
In Lines 13–16, in each time-slot j, after deleting [TeX:] $$p_{1}[j],$$ it computes a node-disjoint path set [TeX:] $$p_{2}[j],$$ which forms [TeX:] $$p_{2}$$ with the maximum bandwidth. Then, we optimize path [TeX:] $$p_{2}$$ by reducing the number of path-switchings [TeX:] $$k_{2}$$ during time slot [p, q] using the method adopted for [TeX:] $$p_{1}$$ previously.
After that, the path-switching counts [TeX:] $$k_{1} \text { and } k_{2}$$ are minimized for paths [TeX:] $$p_{1} \text { and } p_{2}$$ during transfer period [p, q]. Note that generally, the number of path-switchings and the path-switching time points of two path sets [TeX:] $$p_{1} \text { and } p_{2}$$ are different.
In Lines 17–22, if the maximum amount of concurrently transferred data [TeX:] $$\left(\beta_{1}[p, q] \cdot\left((t[q+1]-t[p])-\tau \cdot k_{1}\right)+\beta_{2}[p, q]\right..$$ [TeX:] $$\left.\left((t[q+1]-t[p])-\tau \cdot k_{2}\right)\right) \geq \delta,$$ we can obtain the data transfer end time [TeX:] $$t_{\mathrm{end}}^{\prime} . \text { If } t_{\mathrm{end}}^{\prime}t_{\mathrm{end}},$$ it updates [TeX:] $$t_{\mathrm{end}}$$ with the smaller [TeX:] $$t_{\mathrm{end}}^{\prime}.$$ After iterating through all time slots, we have the earliest
transfer end time [TeX:] $$t_{\mathrm{end}}.$$
Since the time complexity of Dijkstra’s algorithm is [TeX:] $$O\left(|V|^{2}\right),$$ the complexity of Imp2VPFB-1 is [TeX:] $$O\left(T^{3} \cdot|V|^{2}\right)$$ in the worst case.
C. Heuristic Scheduling Algorithm for 2VPVB-0
For 2VPVB-0, the path-switching delay is negligible, so we can perform path switching at any adjacent time slots without affecting the transfer time. We design a greedy approach, Greedy2VPVB-0, whose pseudocode is provided in Algorithm 5. It computes two node-disjoint paths [TeX:] $$p_{1} \text { and } p_{2}$$ with the shortest transfer time (i.e., the maximum sum of variable bandwidths) for the transfer of data size . Each path is composed of a set of paths from source [TeX:] $$v_{s}$$ to destination [TeX:] $$v_{d}$$ with the maximum bandwidth in respective time-slots. In each timeslot i, it computes two node-disjoint paths [TeX:] $$p_{1}[i] \text { and } p_{2}[i]$$ from [TeX:] $$v_{s} \text { to } v_{d},$$ with the maximum bandwidth [TeX:] $$\beta_{1}[i] \text { and } \beta_{2}[i]$$ using Dijkstra’s algorithm, and checks if the data of size can be concurrently transferred during the time-slot range [0, i] (i.e., time interval [t[0], t[i + 1]]). If it can finish the data transfer, it com-
putes the transfer end time [TeX:] $$t_{\mathrm{end}}$$ by path-pair [TeX:] $$\left(p_{1} \text { and } p_{2}\right);$$ otherwise, it repeatedly increases i by 1. If the data can be completely transferred during time-slots [0, i], the maximum number of path switchings needed is i in the worst case, which does not affect the transfer time. The data size to be transferred over each path is also proportional to its bandwidth during the data transfer period.
Since the time complexity of Dijkstra’s algorithm is [TeX:] $$O\left(|V|^{2}\right),$$ the time complexity of Greedy2VPVB-0 is [TeX:] $$O\left(T \cdot|V|^{2}\right)$$ in the worst case.
We would like to point out that an improved algorithm for 2VPVB-0 is not designed. For 2VPVB-0, it is obvious that the data transfer should start at t[0] since the path-switching delay is negligible without further delay for changing bandwidths.
D. Heuristic Scheduling Algorithms for 2VPVB-1
For 2VPVB-1, the path-switching delay is non-negligible. Moreover, performing a path switching at different time points (i.e., at the end of one time-slot or at the beginning of its succeeding time-slot) may lead to different performances if the path bandwidths are different across two adjacent time-slots. It is favorable to perform path-switching in the time-slot with a smaller bandwidth between two adjacent time slots, as data transfer is suspended during the period of path switching.
D.1 Greedy 2VPVB-1 Algorithm
We design a polynomial-time greedy algorithm, Greedy2VPVB-1, whose pseudocode is provided in Algorithm 6. Starting from time-slot 0 to T - 1, in each time-slot i, it computes two nodedisjoint paths [TeX:] $$p_{1}[i] \text { and } p_{2}[i]$$ with the maximum bandwidths [TeX:] $$\beta_{1}[i] \text { and } \beta_{2}[i]$$ using Dijkstra’s algorithm, respectively. Taking path [TeX:] $$p_{1}$$ as an example, path-switching in time-slot i falls in several cases: i) When [TeX:] $$\beta_{1}[i] \geq \beta_{1}[i-1] \text { and } \beta_{1}[i] \geq \beta_{1}[i+1],$$ it does not perform path-switching and the transferred data size is [TeX:] $$\beta_{1}[i] \cdot(t[i+1]-t[i]), \text { ii) when } \beta_{1}[i]\beta_{1}[i-1]$$ and [TeX:] $$\beta_{1}[i]\beta_{1}[i+1],$$ there are two path switchings (i.e., both the beginning and the end of time-slot i), and the transferred data
size is [TeX:] $$\beta[i] \cdot(t[i+1]-t[i]-2 \cdot \tau),$$ and iii) when [TeX:] $$\beta_{1}[i]>\beta_{1}[i-1] \text { and } \beta_{1}[i]\beta_{1}[i+1],$$ it performs the path switching at the end of time-slot i, and when [TeX:] $$\beta_{1}[i]\beta_{1}[i-1]$$ and [TeX:] $$\beta_{1}[i]>\beta_{1}[q+1],$$ it performs path switching at the beginning of time-slot i. The transferred data size in both subcases of case iii) above is [TeX:] $$\beta[i] \cdot(t[i+1]-t[i]-\tau).$$ On path [TeX:] $$p_{2},$$ it performs path switching between two adjacent time-slots in the same way.The data size to be transferred by each path is also proportional to its bandwidth during the data transfer period. The time complexity of Greedy2VPVB-1 is [TeX:] $$O\left(T \cdot\left(|V|^{2}+T\right)\right).$$
D.2 Improved Algorithm for 2VPVB-1
In Greedy2VPVB-1, we perform path switching in the timeslot with lower bandwidth, but frequent path switchings may cause a considerable overhead. We design an improved algorithm to reduce the number of path switchings, referred to Imp2VPVB-1, whose pseuducode is provided in Algorithm 7.
In Line 3, it initializes the number of path-switchings in each time slot for each path. We use [TeX:] $$k_{1}[i] \text { and } k_{2}[i]$$ to denote the number of path switchings on [TeX:] $$p_{1}[i] \text { and } p_{2}[i]$$ in time slot i, respectively. We also use [TeX:] $$\delta^{\prime}$$ to denote the remaining data size at time point [TeX:] $$t[i]$$ (i.e., the beginning of time-slot i), and use [TeX:] $$\delta^{\prime}[j]$$ to denote the size of data transferred in time-slot j.
In Lines 4–32, it iterates through each time slot and check if the data transfer can be finished.
While in Lines 5–19, for each i, it checks if the remainder data size can be transferred in this time slot. If data transfer can be completed in time-slot i, it computes the transfer end time according to different path-switching scenarios: i) When the path-switching time of two paths in time-slot i is the same [TeX:] $$\text { (i.e., } k_{1}[i]=k_{2}[i],$$ the transfer time is updated to
[TeX:] $$t t=t[i]+k_{1}[i] \cdot \tau+\delta^{\prime} /\left(\beta_{1}[i]+\beta_{2}[i]\right),$$ ii) when the number of path-switchings of [TeX:] $$p_{1}[i]$$ is larger than the number of pathswitchings of [TeX:] $$\left.p_{2}[i] \text { (i.e., } k_{1}[i]>k_{2}[i]\right),$$ the transfer time is updated to [TeX:] $$t t=t[i]+k_{1}[i] \cdot \tau+\delta^{\prime} /\left(\beta_{1}[i]+\beta_{2}[i]\right),$$ and iii) when the number of path-switchings of [TeX:] $$p_{1}[i]$$ is smaller than the number of path-switchings of [TeX:] $$\left.p_{2}[i] \text { (i.e., } k_{1}[i]k_{2}[i]\right),$$ the transfer time is updated to [TeX:] $$t t=t[i]+k_{2}[i] \cdot \tau+\delta^{\prime} /\left(\beta_{1}[i]+\beta_{2}[i]\right).$$ Since path switching may be performed at the end of one time-slot or at the beginning of its preceding time-slot, the value of [TeX:] $$k_{1}[i]$$ and [TeX:] $$k_{2}[i]$$ could be 0, 1, 2 (the value could be 0 and 1 if i is the first or the last transfer time-slot). In Fig. 4, we illustrate different path switching cases in time-slot 1 for [TeX:] $$p_{1},$$ where the number of path switchings [TeX:] $$k_{1}[1]$$ is 0, 1, 1, and 2 in Figs. 4(a), 4(b), 4(c), and 4(d), respectively. For convenience, we set the time-slot to be 1 time unit, and path-switching delay to be 0.1 time unit.
If the data movement can be completed before time point
Illustration of path switchings in time slot 1 on [TeX:] $$p_{1}:\left(\text { a) } k_{1}[1]=0\right.,$$ (b) [TeX:] $$k_{1}[1]=1,(\mathrm{c}) k_{1}[1]=1, \text { and }(\mathrm{d}) k_{1}[1]=2.$$
[TeX:] $$t[i+1]$$ (i.e., in time-slot i), we compute the remaining data size [TeX:] $$\delta^{\prime}$$ at time point t[i] and the transfer end time according to both the path-switching counts of the two node-disjoint paths:
i) when [TeX:] $$k_{1}[i]=k_{2}[i],$$ the concurrent transfer end time is [TeX:] $$t t=t[i]+k_{1}[i] \cdot \tau+\delta^{\prime} /\left(\beta_{1}[i]+\beta_{2}[i]\right);$$
ii) when [TeX:] $$k_{1}[i]>k_{2}[i], \text { then } t t=t[i]+k_{1}[i] \cdot \tau+\left(\delta^{\prime}-\left(k_{1}[i]-\right.\right.\left.\left.k_{2}[i]\right) \cdot \beta_{2}[i]\right) /\left(\beta_{1}[i]+\beta_{2}[i]\right);$$
iii) when [TeX:] $$k_{1}[i]k_{2}[i], \text { then } t t=t[i]+k_{2}[i] \cdot \tau+\left(\delta^{\prime}-\left(k_{2}[i]-\right.\right.\left.\left.k_{1}[i]\right) \cdot \beta_{1}[i]\right) /\left(\beta_{1}[i]+\beta_{2}[i]\right).$$
In Line 21, if the data transfer has not yet been completed in time-slot i, it continues to transfer in the next time-slot i + 1. We compute the maximum amount of data to be transferred in time-slot [i, i + 1] by analyzing possible path-pairs and their switching schemes. We first define several notations to facilitate the explanation of our path switching scheme:
[TeX:] $$p_{1}[i], p_{2}[i]$$ Two node-disjoint paths with maximum bandwidth in the current time-slot i.
[TeX:] $$\beta_{1}[i], \beta_{2}[i]$$ Bandwidth of [TeX:] $$p_{1}[i] \text { and } p_{2}[i],$$ respectively.
[TeX:] $$\beta_{1}[i+1], \beta_{2}[i+1]:$$ Bandwidth of [TeX:] $$p_{1}[i+1] \text { and } p_{2}[i+1],$$ respectively.
[TeX:] $$p_{1}^{\prime}[i+1]:$$ Path with the widest bandwidth after deleting [TeX:] $$p_{2}[i]$$ in time slot i + 1.
[TeX:] $$p_{2}^{\prime}[i+1]$$ Path with the widest bandwidth after deleting [TeX:] $$p_{1}[i]$$ in time slot i + 1.
[TeX:] $$\beta_{1}^{\prime}[i+1]$$ Bandwidth of path [TeX:] $$p_{1}^{\prime}[i+1].$$
[TeX:] $$\beta_{2}^{\prime}[i+1]$$ Bandwidth of path [TeX:] $$p_{2}^{\prime}[i+1].$$
[TeX:] $$\operatorname{data}[i, i+1]$$ Amount of data movement during time-slot [TeX:] $$[i, i+1].$$
To improve the bandwidths of path-pair in time-slot i+1 and avoid path switching delay between these two time-slots, we design six different types of path switching schemes between time-slot i and i + 1 as shown in Table 1, and select the one with the largest amount of data movement [TeX:] $$\operatorname{data}[i, i+1].$$ For each scheme, the amount of data movement [TeX:] $$\operatorname{data}[i, i+1]$$ is calculated as the sum of transferred data by two paths during time-slot [i, i + 1].
In Table 1, we consider the following path switching scenarios:
i) When the bandwidth sum of two paths retains their originally computed value in time-slot i+1, we further consider two cases: Type 1 keeps both originally computed paths invariable in i+1 time-slot while Type 2 exchanges two paths in i + 1 time-slot.
When path [TeX:] $$p_{1}$$ does not switch between time-slot i and i+1 (i.e., in time-slot i + 1, we still use path [TeX:] $$p_{1}[i],$$ although the bandwidth of this path may be changed), we reduce the path switching delay of [TeX:] $$p_{1}$$ and further consider two cases: Type 3 computes a new path [TeX:] $$p_{2}^{\prime}[i+1]$$ disjoint from [TeX:] $$p_{1}[i]$$ while Type 4 keeps originally computed path [TeX:] $$p_{2}[i+1]$$ invariable in i + 1 time-slot.
iii) When path [TeX:] $$p_{2}$$ does not switch between time-slot i and i+1 (i.e., in time-slot i + 1, we still use path [TeX:] $$p_{2}[i]$$ , although the bandwidth of this path may be changed), we reduce the path switching delay [TeX:] $$p_{2}$$ and further consider two cases: Type 5 computes a new path [TeX:] $$p_{1}^{\prime}[i+1]$$ disjoint from [TeX:] $$p_{2}[i]$$ while Type 6 keeps originally computed path [TeX:] $$p_{1}[i+1]$$ invariable in i + 1 time-slot.
In each case, we compute the amount of moved data data[i, i+1] during time-slot [i, i+1]. The calculation formulas are provided in Table 1. After comparing the amount of moved data data[i, i + 1] in all these schemes, we select an optimal scheme with the largest amount of moved data during time-slot [i, i + 1].
In Lines 22–31, according to the selected path switching scheme, we compute the number of path switchings on each path in time-slots i and i + 1 for the next round of calculation.
Since the time complexity of Dijkstra’s algorithm is [TeX:] $$O\left(|V|^{2}\right),$$ the time complexity of Imp2VPVB-1 is [TeX:] $$O\left(T \cdot|V|^{2}+T^{2}\right),$$ where T is the total number of new time slots in the ATB list, and [TeX:] $$|V|$$ is the number of nodes.
V. PERFORMANCE EVALUATION
For performance evaluation, we implement the proposed algorithms and conduct i) proof-of-concept experiments on an emulated SDN testbed based on the Mininet [6] system, and ii) extensive simulations in randomly generated networks as well as a real-life HPN topology.
Different path switching schemes.
A. Experiment-based Performance Evaluation
A.1 Mininet Testbed Setup
The Mininet emulation tool has been widely used for constructing a virtual network topology [9]. It is also suitable for evaluating the performance of scheduling algorithms as the overhead introduced by the scheduling process in Mininet emulation is marginal compared to the scheduling algorithm running time, and is almost negligible in large cases [11].
Based on the Mininet system, we emulate each switch in the virtual network topology using a virtual instance of Open vSwitch [7], and choose OpenDaylight [8] as the OpenFlow controller, which is a Java-based modular open platform for customizing and automating networks of any size and scale. We deploy a small virtual network testbed emulating a 7-site wide-area network, as shown in Fig. 5. On this testbed, we set the bandwidth capacity of each link between two OpenFlow switches to be 10 Gb/s, and the path switching delay is measured to be [TeX:] $$\tau=0.1$$s.
A.2 Performance Comparison
A.2.a Illustration of a Scheduling Instance. For illustration, we first conduct a scheduling experiment on the emulated testbed over a period of total 4 time slots, among which the smallest one is of 1 time unit. The available bandwidths of the network links across [0, 3] time slots are provided in Table 2.
In this experiment, one bulk data transfer request [TeX:] $$r_{0-6}$$ with data size [TeX:] $$\delta=G b i t s,$$ source [TeX:] $$s_{0},$$ and destination [TeX:] $$s_{6}$$ is submitted. We calculate two node-disjoint paths using different algorithms in deferent scheduling models, i.e., 2VPFB-0, 2VPFB-1, and
A Mininet emulated network testbed.
2VPVB-1. The corresponding scheduling results are provided in Tables 3, 4, and 5, respectively.
From Table 3, we observe that the proposed Imp2VPFB-0 algorithm outperforms Greedy2VPFB-0 by 20% in the scheduling model of 2VPFB-0 in terms of earliest completion time (ECT).
From Table 4, we observe that the proposed Imp2VPFB-1 algorithm outperforms Greedy2VPFB-1 by 25% in the scheduling model of 2VPFB-1 in terms of ECT.
From Table 5, we observe that the proposed Imp2VPVB- 1 algorithm outperforms Greedy2VPVB-1 by about 3% in the scheduling model of 2VPFB-1 in terms of ECT. Note that Imp2VPVB-1 only reduces the number of switching times compared with Greedy2VPVB-1.
Link bandwidths in Gb/s across [0,3] time slots on the network testbed in Fig. 5.
Scheduling results of different algorithms for request [TeX:] $$r_{0}-6$$ in the scheduling model of 2VPFB-0 on the testbed.
Scheduling results of different algorithms for request [TeX:] $$r_{0}-6$$ in the scheduling model of 2VPFB-1 on the emulated network testbed.
Scheduling results of different algorithms for request [TeX:] $$r_{0}-6$$ in the scheduling model of 2VPVB-1 on the emulated network testbed.
A.2.b Performance EvaluationWith Varying Data Sizes. For a thorough performance evaluation, we conduct more emulationbased experiments with varying data sizes on the testbed. Each of these experiments spans across total 10 time slots, among which, the smallest one is of 1 time unit, and the link bandwidth between any two switches is initialized to be the link capacity of 10 Gb/s, as determined by each switch’s line card speed. The available bandwidths of the network links across [0, 9] time slots are provided in Table 6.
We repeat the scheduling experiments under different data sizes increasing from 10 Gbits to 100 Gbits with a step of 10 Gbits. The transfer end time measurements in different scheduling models are plotted in Figs. 6, 7, and 8, respectively. In all these experiments, we observe that the proposed algorithms consistently outperform the other algorithms in comparison.
B. Simulation-based Performance Evaluation
B.1 Simulation Setup
For performance evaluation, we generate a set of networks containing different numbers of nodes and links of random bandwidths within an appropriate range. We randomly select a source node [TeX:] $$v_{s}$$ and a destination node [TeX:] $$v_{d}$$ in each network. There are 100 time slots in total and the start time [TeX:] $$t[0]=0.$$ The link bandwidths follow a normal distribution: [TeX:] $$b=b_{\max } \cdot e^{-\frac{1}{2}(x)^{2}},$$ where [TeX:] $$b_{\max }$$ is set to be 100 Gb/s, which is the capacity of most production backbone networks nowadays, and x is a random variable within the range of [0, 1].
We investigate the scheduling performance of the proposed algorithms as network size scales up in Section V.B.2, and as both network size and data volume increase simultaneously, as faced by many big data applications, in Section V.B.3.
Link bandwidths in Gb/s across [0, 9] time slots on the emulated network testbed in Fig. 5.
Performance comparison for 2VPFB-0 as data sizes vary on the testbed.
Performance comparison for 2VPFB-1 as data sizes vary on the testbed.
Performance comparison for 2VPVB-1 as data sizes vary on the testbed.
B.2 Evaluation of Scheduling Performance for 2VPFB-0/1 and 2VPVB-1 with Varying Network Sizes
For performance evaluation, we randomly generate 15 different large-scale networks, indexed from 1 to 15, as shown in Table 7. In these randomly generated networks, we set the data volume for transfer to be 1000 GByte. In each of these network instance, we run Greedy2VPFB-0/1, Imp2VPFB-0/1, Greedy2VPVB-1, and Imp2VPVB-1 for 10 times with different random seeds, and measure each algorithm’s average performance and standard deviation.
For 2VPFB-0/1, we plot the mean and standard deviation of the data transfer end time obtained by Greedy2VPFB-0/1 and Imp2VPFB-0/1 in Figs. 9 and 10, respectively. We observe that Imp2VPFB-0/1 achieve about 10–20% and 12–35% performance improvement on average over Greedy2VPFB-0/1, respectively.
We also evaluate the performance of Greedy2VPVB-1 and Imp2VPVB-1 for 2VPVB-1 in the same set of networks, and plot the performance measurements in Fig. 11. We observe that Imp2VPVB-1 also consistently outperforms Greedy2VPVB-1 in all the cases with about 5% performance improvement.
We would like to point out that bandwidth is the dominating factor that determines data transfer end time for a given data volume in a given network. We notice that the algorithm performance improvement for 2VPVB-1 is less significant than 2VPFB-0/1. This is because Greedy2VPVB-1 has already considered maximum data transfer in every time slot, and Imp2VPVB-1 only reduces the number of path switchings between different time-slots, hence yielding a limited performance gain. For 2VPFB-0, Imp2VPFB-0 may postpone data transfer to a later time-slot to use a higher bandwidth than Greedy2VPFB- 0; while for 2VPFB-1 with path-switching delay, Imp2VPFB-1 further reduces the number of path switchings between different time-slots to improve the performance over Greedy2VPFB-0.
B.3 Evaluation of Scheduling Performance for 2VPFB-0/1 and 2VPVB-1 With Varying Network Sizes and Data Volumes
We randomly generate 15 different large-scale networks. The data size to be transferred varies within a range from 1000 Gbytes to 3000 Gbytes.
For 2VPFB-0/1, in each of these 15 large-scale networks and for each data size, we run Imp2VPFB-0/1 and Greedy2VPFB- 0/1 for 10 times, and plot the average data transfer end time in Figs. 12 and 13. We observe that Imp2VPFB-0/1 outperforms Greedy2VPFB-0/1 in all of the cases with about 10–20% and 12–35% performance improvement on average, respectively.
We also evaluate the performance of Imp2VPVB-1 and Greedy2VPVB-1 for 2VPVB-1 in the same set of networks, and plot their performance measurements in Fig. 14. Similarly, Imp2VPVB-1 outperforms Greedy2VPVB-1 in all the cases with about 5% performance improvement. Since Greedy2VPVB-1 has already considered maximum data transfer in every time slot, and Imp2VPVB-1 attempts to reduce the number of path switchings, the performance gain is limited.
These simulation results show that transfer end time is largely determined by data volume, not network size, and are qualitatively similar to those in Section V.B.2.
B.4 Performance Comparison for 2VPFB-0/1 and 2VPVB-1 in ESnet5
To further evaluate the performance of the proposed algorithms, we conduct scheduling experiments using the topology of a real-life HPN, ESnet5 of U.S. Department of Energy [34], with 57 nodes and 65 links, as shown in Fig. 15. We vary the vol
Index of 15 large-scale simulated networks.
Performance comparison for 2VPFB-0 as network size vary.
Performance comparison for 2VPFB-1 as network size vary.
Performance comparison for 2VPVB-1 as network size vary.
Performance comparison of the algorithms for 2VPFB-0 in large networks as both data size and network size vary.
Performance comparison of the algorithms for 2VPFB-1 in large networks as both data size and network size vary.
Performance comparison of the algorithms for 2VPVB-1 in large networks as both data size and network size vary.
ume of data within a range from 1150 GBytes to 2750 GBytes in the experiments. The corresponding performance measurements for 2VPFB-0/1 in ESnet are plotted in Figs. 16 and 17, and the performance measurements for 2VPVB-1 in ESnet are plotted in Fig. 18. These results show that the improved algorithms consistently achieve better performance than greedy heuristic algorithms.
Again, the simulation results from ESnet show that data size is the dominating factor that determines transfer end time in a given network, and are qualitatively similar to those in Section V.B.2.
Performance comparison for 2VPFB-0 in ESnet5.
Performance comparison for 2VPFB-1 in ESnet5.
Performance comparison for 2VPVB-1 in ESnet5.
VI. CONCLUSION
We investigated a bandwidth scheduling problem with two variable node-disjoint paths of fixed and variable bandwidth in dedicated networks, in each of which, we further considered two subcases according to the negligibility of path switching delay. We proved these four problem variants to be NP-complete, and designed a heuristic for each. The performance superiority of the proposed heuristics was verified by extensive simulation results in a large set of simulated and real-life networks in comparison with greedy strategies. It is of our future interest to incorporate and test these scheduling algorithms in the control plane of existing HPNs.