Sage Journals: Discover world-class research

Abstract

Recently, there has been a surge of the video services over the Internet. However, service providers still have difficulties in providing high-quality video streaming due to the problem of scheduling efficiency and the wide fluctuations of end-to-end delays in the existing multi-path algorithms. To solve these two problems affecting video transmission quality, networks are expected to have the capability of dynamically managing the network nodes for satisfying quality-of-service requirements, which is a challenging issue for media streaming applications. Against this changing network landscape, this article proposes a dynamic and adaptive multi-path routing algorithm under three constraints (packet loss, time delay, and bandwidth) that are based on software-defined network for centralized routing computations and real-time network state updating in multimedia applications. Compared with related multi-path routing proposals, dynamic and adaptive multi-path routing makes efficient use of the latest global network state information achieved by the OpenFlow controller and calculates the optimal routes dynamically according to the real-time status information of the link. Moreover, our proposed algorithm can significantly reduce the computational overhead of the controller while completing a fine-grained flow balance. Experimental results show that dynamic and adaptive multi-path routing significantly outperforms other existing scheduling approaches in achieving a 35%–70% improvement in quality-of-service.

Keywords

OpenFlow dynamic and adaptive multi-path routing packet loss rate

Introduction

With the rapid development of the Internet, the demand for video data is increasing dramatically, and video streaming usually occupies a large share of the network bandwidth.¹ When link congestion occurs over the network, there will be a lot of packet loss or even critical traffic disruptions on the link.² For the traditional single-path routing, the bandwidth resources of the other links beyond the transport path are idle in the process of transmitting video streaming, which can’t be fully utilized. With the increase of network devices, the Internet access technology has made great progress, and there are a lot of reachable paths among the nodes, which makes multi-path transmission possible.³ Compared with single-path routing, multi-path routing has emerged as the technology of choice in the Internet, which can achieve traffic engineering in the form of load balancing.³ In particular, it can use multiple paths to transmit the video traffic across the Internet, which can effectively utilize the bandwidth of the idle link and improve the reliability of video transmission.⁴ However, as video data are undergoing rapid growth on the Internet, the underlying data network that supports multimedia applications needs major improvements to avoid being the bottleneck for the changing video traffic.⁵ To address these issues and challenges, a promising network architecture with a more intelligent and efficient video transmission system is urgently needed.

OpenFlow can remedy the deficiencies of the traditional network. It decouples the control and forwarding layers in the routing.⁶ This separation of control and data forwarding allows more sophisticated data management and customized services to be applied through the software-defined network (SDN) controller to optimize network performance.⁶ In addition, it enables the network to be programmable and application-aware, and provides the ability to control the behavior of the entire network.¹ Due to its flexibility and programmability, it can expand the new routing module on the basis of existing algorithms for facilitating efficient video streaming to heterogeneous clients and fulfilling the different quality-of-service (QoS) requirements of the service provisioning strategy.¹ Hence, we propose a dynamic and adaptive multi-path routing (DAMR) under three constraints for adaptive video unicast, relying on SDN. This article differs from existing QoS algorithms^2,4,5,7–10 because we offer a new adaptive scheduling scheme for obtaining the optimal routes and the best network utilization, which considers more than two constraints, with the Lagrange relaxation based aggregated cost (LARAC) algorithm.¹¹

Naturally, there will be an extra cost for the video transmission from one client to another client using unicast routing (point-to-point). For unicast routing, this is mainly in finding a feasible path between two clients under the given constraints.² To this end, the constrained shortest path (CSP) algorithm is a relatively general algorithm for Internet-based multimedia applications, which considers the delay as the only constraint and the two metrics of jitter and packet loss as the cost parameters.⁶ However, this scheme is not necessarily guaranteed to compute the best path that satisfies the delay constraint in a variety of traffic types. Thus, in this article, we consider three constraint parameters on the basis of the existing algorithms, which can calculate the result of the path close to the true value.

There are, hence, three contributions of this article.

We propose DAMR based on SDN for video transmission to meet the three constraint requirements of delay, packet loss, and bandwidth.

We present a scheduling algorithm for optimizing the link weights, which achieves the theoretical minimum delay and reduces the computational overhead of the controller.

We present a method of aggregating bandwidth resources from the perspective of the application layer, which can optimize the link weights and utilize the network resources more efficiently.

The rest of this article is organized as follows. The related literature is surveyed in the “Related work” section. The “System architecture” section introduces the system architecture of this proposed algorithm in detail, by describing the functions of several main modules and analyzing the principle of the designed architecture based on SDN. We apply the proposed architectures and propose and analyze the DAMR routing algorithm in the “Scheme for DAMR routing” section. We present the results of some experiments in the section “Experimental results” to show the performance of the proposed algorithm in terms of delay, packet loss rate, and throughput of the link in the network. Finally, the “Conclusion and future directions” section draws some conclusions.

Related work

Some other researchers have worked on multi-path routing over an OpenFlow network. Wang and Crowcroft¹² and Xue et al.¹³ both focused on multi-constrained path (MCP) problems and came up with improved path selection algorithms. Egilmez et al.⁶ presented an optimized framework for QoS routing with the help of SDN, which collects information about the network state to calculate the routing paths and dynamically change the network routing. However, they did not mention a multi-path routing algorithm in their article. Chen et al.¹⁴ provided two algorithms for the CSP problem, but the performance was not better than that in Chemeritskiy and Smelansky¹⁵ due to the slower running time. In Sahhaf et al.,⁴ the authors proposed an algorithm, called equal-cost multi-path routing (ECMP), which can allocate the end-to-end traffic to different transmission paths by using a randomized method. Nevertheless, this algorithm cannot achieve a higher throughput. In Bredel et al.,¹⁶ the authors proposed the Round Robin Multi-Path algorithm to choose different transmission paths from all the end-to-end paths. In Egilmez et al.,⁶ the authors proposed a multi-path routing algorithm based on OpenFlow that does not aggregate network bandwidth resources effectively or take account of the capabilities of the network. Wang and Crowcroft¹² proposed a method of multi-path routing under traffic congestion based on dynamic optical networks, which is not based on an SDN. Chen et al.¹⁴ proposed a strategy of multi-path transmission control protocol routing based on SDN, which uses the controller to calculate multiple shortest paths between the two nodes. The data stream is divided into a corresponding number of data sub-flows. Also, the controller generates and sends flow tables to an openflow switch along multiple paths. Their research indicates that that method did not succeed in achieving higher network throughput, for the reasons that those algorithms only achieve part of the information of network topology and traffic distribution, which constitutes a lack of flexibility in the routing scheduling and real-time parameter acquisition of the global network state. Thus, this will lead to a decline in the network throughput.

In Chiesa et al.,¹⁷ multi-path routing is proposed to aggregate network bandwidth resources more effectively, which can solve the link congestion problem and improve the network throughput. Furthermore, the results showed that a multi-path video streaming mechanism can be more cost-effective than a single-path mechanism from the perspective of the overall capacity of the video streaming.¹⁷ Our approach differs from theirs in considering three constraints as parameters for the optimization of the link weights.

System architecture

In the current Internet architecture, it is difficult to dynamically and adaptively reconfigure as many different routing paths as possible on a per-flow basis. For example, when a packet arrives at a router, it checks its routing-table entries, and forwards it according to predefined rules configured by network administrators. OpenFlow offers a new paradigm to mostly remedy this deficiency, by allowing us to define different routing rules associated with data flows so that the partitions of the network’s layout and traffic flows can be instantly modified, as in the SDN environment. The switches in the SDN-based network all run the OpenFlow protocol. All of these switches connect to a central controller. The controller can acquire the real-time network status from the data plane (the server and a client) such as the delay, the packet loss rate, and the available bandwidth. Next, it will analyze the collected QoS parameters and calculate the video streaming scheme depending on the bandwidth aggregation policy. The proposed controller, depicted in Figure 1, offers various interfaces and functions, some of which have been part of a router in the traditional Internet model.

Figure 1.

System architecture.

In Figure 1, the underlying network supports the OpenFlow protocol, which is mainly composed of three parts: the routing module, the measurement module, and the controller module. The routing module, based on the floodlight controller, can provide the state information of the global network, and is also responsible for calculating the optimal path and available bandwidth for each flow. It interoperates with the topology module, which can acquire the network topology and update the topology in real time. Once the network status fails to meet the requirements of the given QoS parameters, it is required that the bandwidth aggregation module recalculate the routing. Meanwhile, the controller generates and sends the flow table to the corresponding switches.

Figure 1 depicts the two main interfaces: the Controller–Switch interface and the Controller–Application interface. The function of the former is that the controller attaches to a network of switches with a secure OpenFlow protocol to send flow tables associated with data flows, to discover the network topology, and to receive traffic status information. The latter one is that the controller provides an open (non-real time), secure interface to the application service providers to make reservations of new data partitions and even to define new routing rules associated with the partitions.

The controller module is responsible for managing and monitoring the network state information of the global network for better utilization of network resources by using the OpenFlow protocol to communicate with the data plane. Moreover, it generates and sends the flow tables to an OpenFlow switch depending on a request message sent by a client. Its main function modules are as follows:

The controller checks the current network status using the Link Layer Discovery Protocol (LLDP) and maintains global topology information. In our implementation, the controller will first send an LLDP packet to all the switches that are connected via a $Packet_out$ message. These switches will send LLDP packets to all the ports after the message is received. If an OpenFlow switch receives LLDP packets, it sends the link information between the two switches to the controller through the $Packet_in$ message. After the controller receives the $Packet_in$ message with LLDP, it can analyze which switches are connected directly to each other, and construct the global topology. Moreover, if the client keeps sending request messages, our experiment follows the recommendations (i.e. 7% of the average Floodlight capacity) to minimize mutual interference between the processes (Mininet, Floodlight, and client). In contrast, the application layer is connected with the Northbound-application programming interface, and includes several key modules as follows:

Network monitoring is crucial for network management, such as traffic statistics and traffic monitoring in terms of the current network status, including information about link congestion, available bandwidth, time delay, and packet loss rate based on the OpenFlow protocol. Also, this module has the ability to entirely monitor the network topology and routing status, and modify in a timely fashion the path selection according to any changes in the network state. In this article, we use the controller to obtain the link information with a regular sampling method. We can get s bytes in a port through a cycle of T with sampling switches. Therefore, we can obtain the approximate link bandwidth, namely, $s / T$ . The delay in forwarding a packet is mainly considered in the link delay, depending on the time stamp method, and the average time delay is the ratio of the total time of the received data packet to the number of the periodic statistics. After collecting the monitoring information, the system starts the congestion control module to resolve the problem of how to avoid congestion and detect congestion according to the congestion level.

The routing module is responsible for collecting the information about the global network status for the controller and calculating the traffic assignment value of multiple paths, which can provide the best routing policy for the application layer.

The bandwidth aggregation module is responsible for collecting the information from the monitoring module, and calculating the routing of bandwidth aggregation depending on the monitoring information.

The path management module is responsible for path provisioning and path calculation. Path provisioning interacts with the switches to handle the OpenFlow messages and manages the service provisioning schemes. Upon receiving a $Packet_in$ message, it parses the message and forwards the information to the path calculation component for path computation. The other one is responsible for calculating the service provisioning scheme for each client and obtaining the current network status upon receiving the task from path provisioning.

Scheme for DAMR routing

This section presents an optimization algorithm of DAMR to design an OpenFlow controller which makes full use of network resources and avoids network congestion, reducing effectively the packet loss rate in the transmission process.

DAMR routing module

DAMR is the key module of our proposed system; it aggregates bandwidth based on the monitoring information and avoids the data packet loss caused by link failures or link congestion, thus ensuring the reliability of the transmission. The data flow will be dynamically allocated to multiple effective paths between any two nodes, making network resource utilization balance better. This will reduce the congestion caused by data transmission to a great extent, which decreases the packet loss rate and the end-to-end delay correspondingly.¹⁷

In an OpenFlow network, the controller can get the network topology and link information and discover information about the congestion and idle links, providing the basis for the realization of a multi-path algorithm. Due to the programmable controller, the implementation of the multi-path algorithm is more flexible and diversified, which can ensure the scalability of the existing OpenFlow framework by extending the requested module.

An OpenFlow network topology is described by a directed graph $G (V, E)$ , where V is the set of nodes in the network and E is the set of links or paths. $R_{st}$ represents the set of all links between source node s and destination node t. Each link $r \in R_{st}$ is characterized by three associated positive metrics: $f_{C} (r)$ , $f_{D} (r)$ , and $f_{B} (r)$ , defined as follows

f_{C} (r) = \sum_{(_{i},_{j}) \in r} c_{ij}

(1)

f_{D} (r) = \sum_{(_{i},_{j}) \in r} d_{ij}

(2)

f_{B} (r) = \sum_{(_{i},_{j}) \in r} b_{ij}

(3)

In these formulas, $c_{ij}$ , $d_{ij}$ , and $b_{ij}$ denote the cost, time delay, and available bandwidth of routing from node i to j, respectively. In our case, we choose the cost metric to be the weighted sum of the packet loss measure and the delay variation, as follows

c_{ij} = (1 - β) g_{ij} + β p_{ij} 0 ⩽ β ⩽ 1

(4)

where $g_{ij}$ and $p_{ij}$ denote the delay variation (jitter) and the packet loss for the path $(i, j)$ ; $β$ is the scale factor. For large $β$ , the route selection will be more sensitive to the packet losses. In contrast, for small $β$ , the route selection will be more sensitive to the delay variation.

The objective function is as follows

r^{*} = ar g_{r} \min {f_{C} (r) ∣ r \in R_{st}, f_{D} (r) ⩽ d_{\max} \land f_{B} (r) ⩽ b_{\max}}

(5)

where $d_{\max}$ and $b_{\max}$ denote the maximum time delay requirement and the maximum bandwidth requirement of the QoS, respectively. The goal of this algorithm is to find that path with the least cost that satisfies the two constraints of delay and bandwidth. The main idea of the proposed algorithm is that the optimization problem is transformed to a linear function by using the objective function parameters converted by the constraint conditions, and so its solving process is simple, thus the time complexity of obtaining an optimal or a better solution is reduced.

The algorithm in this article is responsible for calculating the aggregation bandwidth depending on the real-time monitoring information and periodic scheduling strategy, which can optimize the link weight. Moreover, our proposed algorithm can identify the matching rules locally and determine whether the packet is forwarded or dropped when congestion occurs. This can reduce the overhead caused by the controller monitoring the network continuously compared with other multi-path routing algorithms. To observe the controller induced overhead, we measured the delay of the first packet received by host 4. It was 0.014 ms. However, the second one dropped to 0.004 ms, indicating that our approach can reduce the overhead of processing the packets by the controller in Table 1.

Table 1.

The overhead of the controller.

Test method	Processing time for the first packet (ms)	Processing time for the second packet (ms)
ECMP	0.8	1.2
DAMR	0.014	0.004

ECMP, equal-cost multi-path routing; DAMR, dynamic and adaptive multi-path routing.

DAMR routing

Traditionally, switching and routing designs are the main modules of a network based on distributed approaches for robustness.¹⁸ In SDN networks, one video is streaming between any two end nodes s and t through the shortest path calculated by the controller based on path cost. That is, at first, the two flows are routed on the shortest path. If the shortest path does not satisfy the time delay constraint, they will have an opportunity to be rerouted on a feasible path calculated by the routing module based on the path delay. Due to packet losses and bursts of traffic, dynamic changes in the network topology will occur accordingly. Thus, the above factors will have some negative effects on the performance of the network. To solve this kind of problem, the controller updates the forwarding table based on the flow table’s mechanism that the flow table is sent by the controller in batches. Also, a new topology and a new configuration flow table are calculated by the controller according to the algorithm in this article. During the updating process, the controller first removes the matching flow tables that do not satisfy the delay constraint. Meanwhile, the switch will send the $Packet_in$ message to the controller only when it is asked to do so by the controller or when there is no appropriate entry in the switch’s flow table. After receiving the information, the controller does not reply to the switch immediately. However, the controller queries the QoS parameter information of each link in the underlying network for providing the policy of bandwidth aggregation in real time.

Furthermore, it is important to guarantee the performance of the flow transmission depending on the policy of bandwidth aggregation, which can adjust the routing algorithm in a timely fashion, dynamically, to ensure the high reliability and adaptability of the flow transmission.

Proposed solution

We provide three algorithms. The first two are proposed for network view update and routing scheduling, and the other algorithm is designed for the packet loss rate. These algorithms not only give solutions to the optimization problems but also present the required messaging mechanisms to update dynamically the network topology for the optimal transmission path.

Algorithm 1 . The update of the network view is mainly based on the statistical functions of OpenFlow. The counter of the flow table in the switch is able to record the status information of the network, such as the bytes sent and received, the transmission errors, and the transmission duration times. This algorithm optimizes the network topology and performs link information updates; the UPDATE procedure handles the related events. Also, this algorithm is run by the controller in the control plane and calls the monitor module by the interfaces. Assuming that the given delay value and all types of flow are pre-defined, the controller employs the proposed algorithm so that updated network and QoS parameters of the link are generated and sent through the interface. In this algorithm, the network update procedure gets the latest link-state information from the underlying network and updates the link information for different flow types based on the given constraints, as discussed in the “System architecture” section. Then, the link-state information is sent to the controller through the OpenFlow protocol. In parallel, the UPDATE procedure checks whether there is a route failure or a periodic update coming from the controller. If there is, the update procedure is restarted.

Algorithm 2 . This algorithm is run by the controller and deals with the $Packet_in$ packet sent by the OpenFlow switch. Then, the controller makes forwarding decisions according to the routing decision. If there is a FORWARD decision from the same Cluster and different switch ports, the controller calls the monitor module to acquire the QoS parameters of the link state for calculating the optimal path. Otherwise, the controller will call the doFlood module. For the doFlood module, this module creates the $Packet_out$ message and sets the action list based on the message, and then sends it to the switch. If there are no feasible routes, then a failure route will be rerouted to the feasible path. In parallel, the UPDATE procedure keeps the network state information up-to-date by periodically collecting topology and resource data from the OpenFlow switch. It also provides the routing of aggregated bandwidth resource and sends it to the controller. If a link failure or link congestion occurs, the routing module is restarted to re-optimize the network routing.

Algorithm 1: Network topology update algorithm
/All unfinished flow in the network/ Data: $F < - {f_{u}}$ Link_state_old /old network topology / Result:Link_state_new Link_state_new = $ϕ$ ; /Initialization/ whilefinFdo Calculate f current time delay, available bandwidth and packet loss rate; /* path $(f)$ is the path transmission function/ ifLink in path $(f)$ then iff in Link_state_oldthen Calculate the available bandwidth; else Output the new topology; Calculate the QoS* of new flow; else Rerouting;

Algorithm 1: Network topology update algorithm

/*All unfinished flow in the network*/
Data:

F < - {f_{u}}

Link_state_old /*old network topology */
Result:Link_state_new
Link_state_new =

ϕ

; /*Initialization*/
whilefinFdo
Calculate f current time delay, available
bandwidth and packet loss rate;
/* path

(f)

is the path transmission function*/
ifLink in path $(f)$ then
iff in Link_state_oldthen
Calculate the available bandwidth;
else
Output the new topology;
Calculate the QoS of new flow;
else
Rerouting;

Algorithm 2: Network routing algorithm
/All new flow in the network/ Data: $F < - {f_{n}}$ Link_state /the state information of the link/ Result:Route Fetch the information of monitor module; Deal with the packet of packet_in; whilepacket_indo ifSwitch is in the same Clusterthen ifSwitch is in the same portthen Call the doFlood function; else Calculating the routing by calling the monitor module; else Call the doFlood function;

Algorithm 2: Network routing algorithm

/*All new flow in the network*/
Data:

F < - {f_{n}}

Link_state /*the state information of the link*/
Result:Route
Fetch the information of monitor module;
Deal with the packet of packet_in;
whilepacket_indo
ifSwitch is in the same Clusterthen
ifSwitch is in the same portthen
Call the doFlood function;
else
Calculating the routing by calling the monitor module;
else
Call the doFlood function;

In the following, we analyze the complexity of this algorithm. We assume that there are a total of s switches and that m flows need to be transmitted in the network, and that each transmission path contains n links and there are r available paths during the operation service. Then, the time complexity of all available transmission paths based on each flow is $O (n s^{2})$ . Correspondingly, the total time complexity is $O (mn s^{2} r)$ .

Algorithm 3 . This algorithm is a sub-module of the monitoring module. It is in charge of collecting the information about the underlying network. Here, we calculate the packet loss rate based on the link port. The algorithm can ensure the accuracy and real time of the measurement by a periodic update. Moreover, we can calculate the packet loss rate of every flow so as to obtain the optimal route according to Algorithm 3. All symbols and variables used in this article are summarized in Table 2.

Algorithm 3: Packet loss rate algorithm
Data:The QoS parameters collected by the controller Result:dropPackage srcMaxBandwidth = Math.max(srcRBandwidth, srcSBandwidth); dstMaxBandwidth = Math.max(dstRBandwidth, dstSBandwidth); bandwidth = Math.max(srcSBandwidth, dstRBandwidth); bytes =srcRByte + srcSByte + dstRByte + dstSByte; drop =srcRDropped + srcSDropped + dstRDropped + dstSDropped; ifbytes == 0 then dropPackage = 0; else dropPackage = drop/bytes;

Algorithm 3: Packet loss rate algorithm

Data:The QoS parameters collected by the controller
Result:dropPackage
srcMaxBandwidth = Math.max(srcRBandwidth,
srcSBandwidth);
dstMaxBandwidth = Math.max(dstRBandwidth,
dstSBandwidth);
bandwidth = Math.max(srcSBandwidth,
dstRBandwidth);
bytes =srcRByte + srcSByte + dstRByte +
dstSByte;
drop =srcRDropped + srcSDropped +
dstRDropped + dstSDropped;
ifbytes == 0 then
dropPackage = 0;
else
dropPackage = drop/bytes;

Table 2.

Notation and variables.

Notations	Description
srcRBandwidth	Source Port Receive bandwidth
srcSBandwidth	Source Port Send bandwidth
dstRBandwidth	Destination Port Receive bandwidth
dstSBandwidth	Destination Port Send bandwidth
srcMaxBandwidth	Source Port Max bandwidth
dstMaxBandwidth	Destination Port Max bandwidth
bandwidth	The Link bandwidth
srcRDropped	The number of packets lost when Source port receives packets
srcSDropped	The number of packets lost when Source port sends packets
srcRByte	Source Port Receive bytes
srcSByte	Source Port send bytes
dstRByte	Destination Port Receive bytes
dstSByte	Destination Port Send bytes
dropPackage	Packet loss rate

The implementation process of the scheduling algorithm

According to the above analysis, we designed the whole flowchart for the algorithm proposed in this article. It is shown in Figure 2. The scheduling algorithm in this article aims to find the optimal routes for traffic flows such that the delay, packet loss, and throughput at the links are minimized. Thus, we determine how to minimize the maximum utilization of the links in the network. The proposed algorithm adopts link weights for optimizing the network topology. In the proposed algorithm, we add the routing module as application to the floodlight controller, which enables the SDN network to choose the routing automatically according to the topology. Furthermore, the algorithms have been implemented as an SDN routing on the Mininet (version 2.1.0)¹⁹ simulator. The following is a description of the flowchart in Figure 3.

Figure 2.

The whole flowchart of the algorithm.

Figure 3.

The flowchart of the routing module.

When the program starts, we first judge whether there is an optimal path to find, and the controller queries the QoS parameters of the underlying network periodically. Here, the query period of the controller is set to 5 s for monitoring the information from the underlying layer based on the perspective of OpenvSwitch.

When a packet arrives at the controller, the controller first calculates all the accessible paths and the available bandwidth of each path. Then, we will use the path with the maximum available bandwidth as the flow transmission path. If the path satisfies the delay constraint, it will be the optimal path and the flows of video streaming will not be rerouted. Otherwise, the controller needs to find the optimal path by using the DAMR algorithm. If no optimal path exists, because there is no path that satisfies the delay constraint, we won’t reroute any of them. Otherwise, if an optimal path exists, the controller obtains the QoS information from the monitor module and calculates the link weights between each pair of nodes. Then, the controller updates the link-state status information of each link on the path where the flow is located. For obtaining the routing path, we can obtain the link-state information of each link, such as the connected nodes and ports, stored in clusters by using the topology management module from the floodlight controller. Moreover, we can also obtain the full path from the source node to the destination node by traversing each node and its connected nodes. Meanwhile, we can obtain the optimal path that satisfies the delay constraint. The flowchart of the routing module is shown in Figure 3.

Experimental results

In this section, we apply the simulation experiment platform of Mininet and floodlight to confirm the effectiveness of the proposed DAMR and compare it with single-path and ECMP transmission methods.

Experimental environment

We used Mininet¹⁹ to create our network topology and set 100 Mbps for all links using it, as shown in Figure 4.Also, all nodes in the dynamically generated topology were connected to a remote controller, Foodlight1.2 version.²⁰ The controller is in charge of the flow control, such as route calculation and rerouting decision. We set the period of the controller to be 5 s for monitoring the underlying network, and deployed different flows on the controller to confirm the performance of DAMR based on our network topology. The test items include the delay, the throughput, and the packet loss rate.

Figure 4.

The experimental topology structure.

Furthermore, the proposed algorithm is compared with a single-path algorithm and an ECMP method based on the global network in this article. Single-path algorithms, such as those of Dijkstra and Bellman–Ford, have been widely used in the routing of today’s data networks. Moreover, it selects a part of the paths to transfer video streaming based on the additive cost property (e.g. hop counts). In contrast, the ECMP algorithm allocates the traffic equally to multiple equal-cost paths and involves all the links of the network. Although ECMP can improve the throughput and reliability of the link to some extent compared with single-path, this algorithm cannot effectively utilize the available bandwidth, due to hash collision. Also, this algorithm cannot change the proportions of the flow distribution according to changes in the link status. Furthermore, DAMR outperforms ECMP. The reason is that ECMP only allows equal-cost shortest paths to be selected for an even distribution of the traffic, and does not attempt to make changes in the link costs, which makes it difficult to map the right paths, whereas the DAMR applies multi-path technology to make use of the available capacity and minimizes the cost of video transmission, which leads to a guaranteed QoS. To validate the performance of the three algorithms, we conducted many experiments based on three different methods and analyze the results in this article.

Delay comparison

We first examine the performance of the time delay, as shown in Figure 5(a). Different strategies of the application lead to different traffic distributions in each route, which results in the differences in the time delay. At the beginning of the experiment, the time delays, as measured by the three methods, are all on the rise due to the arrival of the first data flow. Also, the openflow switch first sends the first data packet to the floodlight controller. Next, the controller sends and installs the flow tables to the openflow switch after calculating the routing by the routing module.

Figure 5.

The experimental results.

Moreover, the delay of some packets may increase with path switchings by using the multi-path methods. From Figure 5(a), the delay of single-path is the most volatile due to network congestion. Therefore, this will lead to the loss of a data packet and the network performance degrading for certain links. Compared with single-path, although ECMP can reduce the time delay to some extent, it produces more jitter for long durations and destabilizes the performance of the network. In general, our proposed DAMR algorithm on the whole is smooth and without jitter, which shows its superiority compared with ECMP and single-path due to its ability to make full use of the aggregated path capacity per flow and to provide a bandwidth guarantee.

Packet loss rate comparison

The packet loss rate was tested in the same test environment, as shown in Figure 5(b). As can be seen from the graph, the fluctuation of the packet loss rate is relatively smooth and less than 10% when using the DAMR method because it makes full use of idle paths to transmit the video, which reduces the adverse effects of congestion caused by a single link during the whole process of video transmission. From Figure 5(b), we can analyze that more packet loss may be observed on other types of flow on the shared route. At the beginning of the experiment, it produces high packet loss rate due to the occupancy time of generating the flow table by using three different methods. Compared with single-path, ECMP can reduce the packet loss rate to some extent, but it suffers from great fluctuations and leads to an obvious decline in the network performance over the whole of the experimental process.

To minimize the adverse effects of video transmission, DAMR is proposed to solve the shortage of bandwidth resources and can dynamically change the network topology to realize resource transmission in a multi-path environment. From the whole of the experimental results, the packet loss is related with the network link state. Compared with DAMR, single-path routing only considers one path between a source node and a destination, which lacks fault tolerance. In addition, DAMR outperforms ECMP and single-path. The basic reason for this lies in the fact that multi-path data transmission can effectively choose an optional path from multiple available paths, which can avoid network congestion and reduce the packet loss rate of video transmission to some extent.

Therefore, the packet loss rate in the process of data transmission by using the DAMR method is also significantly reduced.

Throughput comparison

In Figure 5(c), there are great fluctuations due to network congestion or path switchings using the three approaches. Compared with single-path and ECMP, DAMR can transmit data via multiple paths, which indirectly increases the total bandwidth of the system and also increases the system throughput. In addition, although the ECMP algorithm can improve the throughput, its performance is not stable on the whole.

When there is an absence of congestion in the network links, the three methods can achieve the same performance. When congestion occurs, the DAMR algorithm has good adaptability to tackle the variation in bandwidth and can guide part of the traffic to links that are less loaded or even not congested at all, which can improve the utilization of network resources.

The multi-path problem can be formulated as finding multiple paths to meet a certain aggregate bandwidth requirement with minimum cost. For DAMR, we focus on unicast algorithms for ensuring end-to-end QoS, without considering multicast algorithms. In addition, we have proposed an effective solution based on multi-path transmission that can dynamically adjust the flow forwarding path according to the link status over SDNs.

Finally, note that the x-axis of Figures 5(a), 5(b), and 5(c) stands for simulation time in these experiments.

Conclusion and future directions

In this article, we provided an overview of DAMR mechanisms under the three constraints of CSP over SDNs. DAMR makes full use of the advantage of OpenFlow centralized control, which can realize the optimization of resource allocation. In addition, it can effectively aggregate bandwidth resources for optimizing the link weights by making full use of optimization theory. From the experimental results, the proposed algorithm can overcome the computational overhead of the controller and effectively adapt to dynamic changes of the network. Therefore, it can improve the link utilization and user service quality.

Next, we will extend this research to the condition of there being different priorities for different flows, such as prioritizing a specific flow and implementing different QoS strategies, which can satisfy the constraint of bandwidth or delay of traffic flow.

Footnotes

Acknowledgements

The authors would like to express their sincere gratitude for the anonymous reviewers’ helpful comments.

Handling Editor: Vinod Kumar Verma

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China under grant nos. 61671081 and 61720106007, the Beijing Natural Science Foundation under grant no. 4172042, and the 111 project (B18008), and the Fundamental Research Funds for the Central Universities under grant no. 2018XKJC01.

References

Xue

Chen

Gong

et al . Demonstration of OpenFlow-controlled network orchestration for adaptive SVC video manycast. IEEE T Multimedia 2015; 17: 1617–1629.

Kim

Sharma

Lee

et al . Automated and scalable QoS control for network convergence. In: INM/WREN’10 proceedings of the 2010 internet network management conference on research on enterprise networking, San Jose, CA, 27 April 2010, pp.1–1. Berkeley, CA: USENIX Association.

Singh

Das

Jukan

A survey on Internet multipath routing and provisioning. IEEE Commun Surv Tut 2015; 17(4): 2157–2175.

Sahhaf

Tavernier

Colle

et al . Adaptive and reliable multipath provisioning for media transfer in SDN-based overlay networks. Comput Commun 2017; 106: 107–116.

Luo

Zeng

et al . An adaptive multi-path computation framework for centrally controlled networks. Comput Netw 2015; 83: 30–44.

Egilmez

Civanlar

Tekalp

AM.

An optimization framework for QoS-enabled adaptive video streaming over OpenFlow networks. IEEE T Multimedia 2013; 15(3): 710–715.

van Der Pol

Boele

Dijkstra

et al . Multipathing with MPTCP and OpenFlow. In: SC companion: high performance computing, networking storage and analysis, Salt Lake City, UT, 10–16 November 2012. New York: IEEE.

Frossard

De Martin

Civanlar

MR.

Media streaming with network diversity. Proceedings of the IEEE 2008; 96(1): 39–53.

Zhang

Tang

Wang

et al . Reliable adaptive multipath provisioning with bandwidth and differential delay constraints. In: Proceedings IEEE INFOCOM, San Diego, CA, 14–19 March 2010. New York: IEEE.

10.

Jinyao

Hailong

Qianjun

et al . HiQoS: An SDN-based multipath QoS solution. China Commun 2015; 12(5): 123–133.

11.

Juttner

Szviatovski

Mecs

et al . Lagrange relaxation based method for the QoS routing problem. In: Proceedings of the twentieth annual joint conference of the IEEE computer and communications society, Anchorage, AK, 22–26 April 2001. New York: IEEE.

12.

Wang

Crowcroft

Quality-of-service routing for supporting multimedia applications. IEEE J Sel Area Comm 1996; 14(7): 1228–1234.

13.

Xue

Zhang

Tang

et al . Polynomial time approximation algorithms for multi-constrained QoS routing. IEEE/ACM T Netw 2008; 16(3): 656–669.

14.

Chen

Song

Sahni

Two techniques for fast computation of constrained shortest paths. IEEE/ACM T Netw 2008; 16(1): 105–115.

15.

Chemeritskiy

Smelansky

. On QoS management in SDN by multipath routing. In: International science and technology conference (modern networking technologies), Moscow, Russia, 28–29 October 2014, pp.1–6. New York: IEEE.

16.

Bredel

Bozakov

Barczyk

et al . Flow-based load balancing in multipathed layer-2 networks using OpenFlow and multipath-TCP. In: Proceedings of the third workshop on hot topics in software defined networking, Chicago, IL, 22 August 2014, pp.213–214. New York: ACM.

17.

Chiesa

Kindler

Schapira

Traffic engineering with equal-cost-multipath: an algorithmic perspective. IEEE T Netw 2017; 25: 779–792.

18.

Karbassian

et al . Situation-aware multipath routing and wavelength reassignment in a unified packet-circuit OpenFlow network. In: Optical fiber communication conference and exposition and the national fiber optic engineers conference, Anaheim, CA, 17–21 March 2013. New York: IEEE.

19.

Mininet. http://mininet.github.io/

20.

http://www.projectfloodlight.org/download/