short computer networks review in 6 hours

Improving End-to-End Network Throughput Using Multiple Best Paths Routing in Software Defined Networking

Widhi Yahya, Achmad Basuki, Wildan Maulana S., Sabriansyah Rizqika Akbar, Adhitya Bhawiyuga

Information Centric Network Research Group Faculty of Computer Science

University of Brawijaya Malang, Indonesia

E-mail: [email protected], [email protected], [email protected], [email protected], [email protected]

Abstract— The use of shortest path algorithms for routing a packet in the network has a tendency to elect only one single best path, even though there are several paths that have same best path criteria. Using only one best path may cause a bottleneck in the networks. This paper proposes a method to utilize multiple best path based on link utilization in order to increase end-to-end network throughput. The method uses DFS (Depth-First Search) algorithm to find all available paths and elect the n best paths based on link utilization. To distribute the traffic across multiple selected best paths, the group action feature of Open vSwitch is utilized. The test result shows that the proposed method can outperform the Dijkstra’s shortest path algorithm in network throughput.

Keywords— Multipath, Routing, OpenFlow, Depth-First Search

I. INTRODUCTION The routing protocols play an important role in determining the best paths on the Internet packet delivery process. Some routing protocols utilized shortest path algorithm in determining the path for packet delivery. The algorithms implemented in the router control plane in the form of distributed application [1]. The most widely used shortest path algorithms are the Dijkstra and the Bellman fords. The term “shortest” in determining path brings a new problem. The shortest-path algorithm prunes the network topology become one shortest-path tree(SPT). On heavy network traffic, using one path would cause a bottleneck because the traffic is accommodated by a single path.

In the computer network, links and packet switching devices are kinds of resources that are used to move packets from source to destination. Pruning network topology into a single path, such as shortest-path could limit the use of available resources. This pruning process can have an impact on the network throughput. Some studies, [2][3], improve the network throughput by utilizing multipath routing. By using multipath routing, Multiple resources will accommodate a tremendous amount of traffic. Actually, in the current Internet routing protocol such as an OSPF, has already implemented multipath. But the OSPF multipath, called Equal Cost Multipath Technique (ECMP), activated only if equal cost path founded[4].

Development of new routing protocols in current network architecture meets reluctance because the control plane of network devices locked by the vendors. The Software Defined

Networking (SDN) paradigm which separates the control and the data plane, has realized more elastic control plane. The SDN control plane has an API that enables a network administrator to program and implement their protocols on the network switches. The communication between the control plane and the data plane takes place using the OpenFlow protocols (OFP). Having the global information of network topology is one of the important features of the SDN controllers. This information could be used to determine the best path[5].

The SDN paradigm stimulates the emergence of prototypes of new routing protocols. Some research attempts to build a new shortest-path based routing protocol such as [6], [7]. In the built-in protocol, modifications are made to conventional algorithms such as the Dijkstra’s and Floyd Warshall’s. However, when traffic is increased and cannot be handled by a single path, some alternative paths need to be selected. In the study [2], propose the use of alternative path if only the primary path(the best one) has reached its threshold. But in this study has not discussed how many alternative paths are selected and used. In subsequent research on multipath, [8], extend the Dijkstra shortest-path algorithm to find multiple paths. However, in the study, there is the possibility of finding only one path, if another path crossed a path that has been found in the first loop of the extended Dijkstra algorithm.

In this study, a multipath routing protocol is realized by selecting the multiple best path. The best path criteria are determined by using controller’s topology information and the real-time traffic information that derived from the Sflow application. Furthermore, the flows will be distributed to the multiple best paths to improve network throughput.

The remainder of this paper is organized as follows. Section 2 describes routing, multipath routing and recent research on multipath routing. The protocol design is defined in section 3. The section 4 and 5 represent the simulation and the simulation results respectively. The study conclusions are found in section 6.

II. MULTIPATH ROUTING IN SOFTWARE DEFINED NETWORKING On a computer network, the switching device refers to a

device that performs a process of moving packets from input port to the output port. The goal is to deliver packets from one host to another host. If necessary, The packet will traverse

2018 10th International Conference on Information Technology and Electrical Engineering (ICITEE)

978-1-5386-4739-4/18/$31.00 ©2018 IEEE 187

through multiple switching devices to go to the remote host. In this case, The routing protocols play a role in the establishment and the selection of paths in the packet delivery process.

The conventional routing protocols run in the network box as distributed applications. The routing protocols placed in the control plane of the network devices. The control plane must have the information and the abstraction of the network topology. This information obtained by using the advertisement message of routing application. Then, the information is processed with the routing algorithm to find the best path[1].

The commonly used algorithm in the routing protocols is the shortest path algorithm. This algorithm prunes the graph into a tree which has only one path from a source to destination(s). This algorithm omits the alternative network resources (link and network devices) in the process of delivering packets from a source to a destination. This mechanism can cause one shortest-path will suffer if a considerable measure of the flow passes.

The development of new protocols on the current network architecture is very complicated because of the limited (no) API to organize the data plane independently. Aiming at this problem, the software-defined network architecture has arisen as a solution. This paradigm proposed to enable network campus innovation by decoupling the data and the control plane. The control plane is the logic of how the packet is forwarded, while the data plane is where the forwarding process takes place. The centralized and programmable control plane drives innovation in computer network protocols. It also triggers research related to multipath routing.

In the study, [2], developed the multipath routing extend with rate adaptation, rerouting, and admission control. In this study path obtained by utilizing Depth First Search (DFS) algorithm, but has not specified the number of paths. The rerouting function is called if the traffic on the main path reaches 80%. Another study,[8], utilized Dijkstra algorithm to find multiple paths. The focus is on finding the disjoint path from the network topology.

Fig. 1. Group Table[9]

This study proposed a routing protocol that utilizes the n best path. The n best paths are obtained by using DFS algorithm. The best means the links with the least utilization.

The link information is derived from the Sflow application and the controller’s topology information. The Group entries are used to enable multiple actions for network flows.

III. PROTOCOL DESIGN In this section, we present our design architecture and

protocols. Fig 2. Illustrated the OpenFlow system architecture that separate control plane and data plane. The developed system uses OpenFlow 1.3 as communication protocols between the data plane and the control plane. The Openflow 1.3 has Group table features to enable multipath routing[10]. The control plane, also called the SDN controller, runs multipath routing based on DFS algorithm as pathfinding. The data plane is component where the pipeline process takes place. The current link traffic information is currently obtained from the Sflow application.

Fig. 2. Components of SDN Architecture

A. Multiple Path Searching In this study, the DFS (Depth-First Search) algorithm is

used in the path search process. The DFS is a graph algorithm that based on backtracking technique. The algorithm starts at the root, then travel to reach the leaves before backtracking process. The Fig. 3 shows the DFS algorithm.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:

DFS(G, src, dst) P array to store paths (p) stack initialized as (src, [src]) while stack is not empty pop stack, save to node, p for next in (G[node] – p) if next is dst append p + [next] to P else push (next, p + [next]) to stack end for end while return P end

Fig. 3. Path Searching Algorithm: DFS

In Fig 3, G denotes an adjacency matrix of a graph topology. The adjacency matrix is a matrix that stores the neighbouring information of a node in a topology. The algorithm will find all paths that can be passed from source node s to destination node d.

2018 10th International Conference on Information Technology and Electrical Engineering (ICITEE)

188

B. Link Cost Because the DFS algorithm assumes a topology as an

unweighted graph, a weighing mechanism is needed on the path that has found. In this study, link utilization is used as link weight. The link utilization is obtained through the following equation.

�������� � ����� ���������������� ���������������� The Bandwidth is the maximum bits that transmit per second. The traffic is the actual traffic statistics that is received from the Sflow application. The shortcoming of the equation is that all paths will produce the same weight (0) if there is no traffic in the network. Thus, the number of hops and bandwidth capacity in a path will be neglected. This study uses the following equation, to avoid this problem.

�� � ������� � � �� ������������������������������������� Let, w(l) denote the link weight. The w(l) is equal to the reference bandwidth Bref divided by available bandwidth. The value of Bref is 109 bits, while the available bandwidth is the bandwidth of a link B(l) minus traffic of a link T(l). The path weight is the total weight of all links on the path.

� �!�� � "�#$

���������������������������������������������%�

C. Selection of n-best paths The best path refers to the path with the least weight. First,

the path is sorted by the path’s weight in ascending order. Then select the top n path. n is defined by the administrator in the variable max_path of the program. Then Group Table and the action bucket features are used to forward flows into multiple ports. The Open vSwitch distribute flows among multiple paths using the hash algorithm.[11]

IV. SIMULATION TESTING The proposed multipath routing was implemented on

Mininet emulator. The OVS that support Openflow version 1.3 was used as the SDN switch. The Sflow agent was also enabled on the switch to collect traffic information on the network. Ryu was used as the SDN controller. The flows were generated by using Iperf.

Fig. 4. Topology 1

The functional testing of multipath routing was conducted

on topology 1. The topology 1 has three available paths from source(s) to destination(s). In accordance with the hypothesis, on the topology 1, will be proved that the multipath routing will utilize n best path. While the single path routing only uses a shortest-path. The performance testing was conducted in topology 2 which represents a part of the real network topology of research universities in Indonesia [12]. Topology 2 has a heterogeneous path capacity. In the topology 2, performed observation of multipath routing performance and compare it with the Dijkstra’s shortest-path algorithm.

Fig. 5. Topology 2: Java-Sumatera Campus Network Topology based on

Indonesia Higher Education and Research Network 2011

V. SIMULATION RESULT Fig. 6 shows the result of the test performed on the topology

1. Testing was conducted to find out the paths utilized by each routing protocol. In the testing process, 40 flows were generated from hosts in the switch 1 (s1) to the hosts in the switch 6 (s6). The BWM-NG application was used to monitor each link usage. The results show that the multipath routing mechanism could utilize 3 best paths, and the resulting throughput is higher than the shortest-path’s. The multipath routing could use all available resources (switching devices and links) to move packets from source to destination. On the contrary, the shortest-path routing limited to only use one best path.

TABLE I. MAX PATH VS CONVERGENCE TIME

Defined Max Path

Paths Found

Avg. Convergence

Time

Avg. First Packet RTT (ms)

2 2 2.71 1423.00 3 3 3.54 1545.33 4 4 4.51 1667.00 5 5 5.64 2229.33 Not Defined

11 22.50 Unreachable

2018 10th International Conference on Information Technology and Electrical Engineering (ICITEE)

189

In reality, it is possible in the network has various link capacities. So we propose performance testing on a topology that has various path capacities, as shown in topology 2. As a preliminary, the convergence time measurement was conducted. Convergence time is the time that required by the protocol to find all available paths from source to destination. The max_path was modified to observe its impact on the convergence time. The Table 1. shows that the increasing number of max_path affects the increasing of the convergence time.

Fig. 6. Throughput in Each Path of The Network Topology

Fig. 7. CDF of Throughput of 40 Clients

The convergence time also has an impact on the round trip time (RTT) which describes the time required by a packet to

cross from source to destination and then back to the source. In the SDN architecture, there are several factors influencing RTT include the path search time, the time required for the pipeline process, Packet In message from the OVS to the controller and Packet Out message from the controller to the OVS. The increasing number of paths leads to an increase in the value of the RTT experienced as a result of a large number of processes and messages occurring in the OVS. Moreover, the length of processing time on OVS can lead to the packet loss, as shown in the use of 11 paths. In table 1, it only indicates RTT for the first packet because the path search process and flow entry management performed on the first packet. The subsequent packet will follow entries that already installed in the OVS.

The throughput measurement, in the Fig. 7, was conducted to evaluate the capability of routing using multiple paths. In this testing section, 40 flow was generated using Iperf, from hosts in the switch (s1) and addressed to hosts in the switch (s14). The flows will cross the path with different capacities. In contrast to the test on topology 1, The comparison result of throughput does not significantly differ on topology 2. This result is due to the occurrence of a bottleneck on the link with a small capacity. The average throughput for multipath with DFS is 27.75Mbps, as for the shortest-path Dijkstra is 24.75Mbps. In DFS-based multipath, 40% of the flows has a throughput of below 20Mbps, and 37.5% of the flows have a throughput of over 30Mbps. While on Dijkstra's shortest-path, 22.5% of the flows have throughput below 20Mbps and only 17.5% of the flows have throughput above 30Mbps. Some traffic on multipath suffers because it passes through low capacity paths. In the Fig. 8 is an example of the selected path that shown in the controller’s log, on topology 2.

Fig. 8. Three Best-Selected Paths Shown in Controller Log

VI. CONCLUSIONS This research has implemented multipath routing based on

DFS algorithm and the n best paths selection function. The throughput measurement shows that multipath routing’s throughput is superior to single path routing in a controlled and homogeneous environment. In environments that have heterogeneous path capacities, the throughput is not significantly different. The testing results show that the number of paths affects the convergence and OVS processing time. An excessive amount of utilized paths, resulting in the packet loss due to timeout.

REFERENCES [1] K. W. R. James F. Kurose, Computer Networking: a Top-Down

Approach. 2012.

[2] S. N. Hertiana, “A Joint Approach to Multipath Routing and Rate Adaptation for Congestion Control in OpenFlow Software Defined Network,” page. 1–6, 2015.

[3] X. Lin, N. B. Shroff, dan S. Member, “Utility Maximization for

0

0.2

0.4

0.6

0.8

1

1.2

0 20 40 60 80 100

CD F(

% )

Throughput(Mbps)

Multipath ShortestPath

2018 10th International Conference on Information Technology and Electrical Engineering (ICITEE)

190

Communication Networks With Multipath Routing,” vol. 51, no. 5, page. 766–781, 2006.

[4] C. Villamizar, “OSPF Optimized Multipath (OSPF-OMP),” Internet Engineering Task Force, INTERNET-DRAFT, 1999. .

[5] N. Mckeown, T. Anderson, L. Peterson, J. Rexford, S. Shenker, dan S. Louis, “OpenFlow�: Enabling Innovation in Campus Networks,” vol. 38, no. 2, page. 69–74, 2008.

[6] J. Jiang, H. Huang, J. Liao, dan S. Chen, “Extending Dijkstra ’ s Shortest Path Algorithm for Software Defined Networking,” 2014.

[7] A. G. Furculita, M. V. Ulinic, A. B. Rus, dan V. Dobrota, “Implementation issues for Modified Dijkstra’s and Floyd-Warshall algorithms in OpenFlow,” Proc. - RoEduNet IEEE Int. Conf., 2013.

[8] Y. Chiang, C. Ke, Y. Yu, Y. Chen, dan C. Pan, “A Multipath

Transmission Scheme for the Improvement of Throughput over SDN,” page. 1247–1250, 2017.

[9] P. Goransson, C. Black, dan T. Culver, Software Defined Networks: A Comprehensive Approach. Morgan Kaufmann, 2016.

[10] Open Networking Foundation, “OpenFlow Switch Specification 1.3.0,” 2012.

[11] “Using OpenFlow — Open vSwitch 2.9.90 documentation.” .Available at: http://docs.openvswitch.org/en/latest/faq/openflow/. [Accessed: 17 May 2018].

[12] Nic.itb.ac.id. (2018). Inherent | ITB Network Information Center. [online] Available at: https://nic.itb.ac.id/inherent [Accessed: 23 Jan. 2018].

2018 10th International Conference on Information Technology and Electrical Engineering (ICITEE)

191