# Balancing the QOS and Security in Dijkstra Algorithm by SDN Technology

Jinjing Zhao, Ling Pang, Xiaohui Kuang, Rong Jin

► To cite this version:

Jinjing Zhao, Ling Pang, Xiaohui Kuang, Rong Jin. Balancing the QOS and Security in Dijkstra Algorithm by SDN Technology. 15th IFIP International Conference on Network and Parallel Computing (NPC), Nov 2018, Muroran, Japan. pp.126-131, 10.1007/978-3-030-05677-3_11. hal-02279549

HAL Id: hal-02279549

https://inria.hal.science/hal-02279549

Submitted on 5 Sep 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Balancing the QOS and Security in Dijkstra
Algorithm by SDN Technology

JinJing Zhao¹, Pang Ling¹, Kuang Xiaohui¹, Jin Rong²

¹National Key Laboratory of Science and Technology on Information System
Security, Beijing 100101, China

²Beijing Space Information Relay and Transmission on Technology Centre,
Beijing 100094, China
misszhaojinjing@hotmail.com
lingpang313@yahoo.com

**Abstract.** Dijkstra algorithm is widely used in a lot of common network routing protocols. We consider the problem of quality of service (QoS) and the Security features of the network routing area using software defined networks (SDN). The SDN framework enables an efficient decoupled implementation of dynamic routing protocols which could aware the communication network status. In this work we consider the varying delay status of the communication network along with other network security parameters. The routing problem is formulated as a multi-constrained shortest path problem. A new improved Dijkstra algorithm is presented named as QS-Dijkstra. The implement and experiment show that QS-Dijkstra algorithm is able to minimize traffic routing through vulnerable links while satisfying the QoS constraints of the network.

# 1. Introduction

Dijkstra algorithm is widely used in a lot of common network routing protocols, like OSPF and IS-IS. The main idea of Dijkstra algorithm is how to find a shortest path from a source node to a destination node in a network. So each network link has a cost value to present its status, and this cost is used to calculate the shortest path. In the practice, the link cost is defined as a static cost value in OSPF protocol, as the reference bandwidth divided by interface bandwidth or simply as 1 to reduce the shortest path weight to a hop count. The reason is that it's a very easy way in practice. But as the value of the link cost, it could not cover the feathers and status of the link.

In this work we present a practical way to calculate a more reasonable link cost in Dijkstra algorithm and consider the problem of QoS and the security features of the network routing procedure using SDN technology [1-3]. The SDN framework provides an approach to calculate the shortest path between source and destination based on dynamic link statuses through SDN's high network monitoring capability. A lot of useful link information, like link type, link ownership, interface bandwidth, transition delay and historical record, can be collected and computed by the SDN controller to enable more safe, reliable and efficient paths. In this way, we can consider the varying
delay status of the communication network along with other network security parameters and get a presence of a passive/active adversary in the network routing area.

The remainder of this paper is organized as follows: double constrained shortest path problem is discussed and the derivation of QoS constraints and related cost metrics are presented in Section 2, the implementation details are provided in Section 3, Section 4 investigates the performance of the proposed framework. Conclusions and final remarks are discussed in Section 5.

## 2. System model

Consider a graph representation of the communication network. $G(V, E, \omega)$ is a weighted undirected graph model and describes an $N$ nodes and $E$ links network. The node set is $V = \{v_1, ..., v_N\}$, and the edge set is $E = \{e_{ij} | i, j = 1, 2, ..., N\}$. The weight $\omega_{ij}$ on the edge $e_{ij}$ is defined as the cost of the link. In this article, the interplaying between QOS and security features is concerned in the network routing process. The security metrics of the link between nodes $i$ and $j$ could include these features as:

1) History $L_{ij}H$: a link that was previously targeted by an attacker in a particular time could be more likely to be attacked again.

2) Security installed measures $L_{ij}S$: a link with high encryption is typically hard to be listened or hijacked. So $L_{ij}S$ values are dependent on the pre-installed and pre-configured security measures of nodes of the link.

3) Bandwidth $L_{ij}B$: A link with high bandwidth is more difficult to be congested by data flow.

4) Ownership $L_{ij}O$: a self-owned or in the same domain channel is more secure than a shared or leased channel by other domains.

The vulnerability metric $L_{ij}M$ should reflect the attributes that make a link more secure.

$$L_{ij}M = L_{ij}H * (\alpha L_{ij}S + \beta L_{ij}B + \gamma L_{ij}O) \quad (2)$$

Where $\alpha$, $\beta$, and $\gamma$ are the weights of $L_{ij}S$, $L_{ij}B$ and $L_{ij}O$ depending on the impact importance of the considered security parameters.

Assume every link $e_{ij} \in E$ has two weights $c_{ij} > 0$ and $d_{ij} > 0$ ($c_{ij}$ is cost and $d_{ij}$ means delay). For source and destination nodes $(s, t)$, let $P_{st}$ denote the set of paths from $s$ to $t$. Further, for any path $p$ define

$$c(p) = \sum_{(i,j) \in p} L_{ij} M \quad (3)$$

$$d(p) = \sum_{(i,j) \in p} d_{ij} \quad (4)$$

The routing problem seeks to find the paths between $s$ and $t$ nodes with minimum link cost $c(p_{st})$, which satisfies $d(p_{st}) \le T_{max}$. This is a typical NP problem named constrained shortest path (CSP) [4-5], which can be solved by the Lagrangian Relaxation Based Aggregated Cost (LARAC) algorithm [6].

## 3. Implementation

The architecture of SDN network comprised of Floodlight controller and Mininet switches. In the floodlight controller, applications can be written in Java and can
interact with the built-in controller modules via a JAVA API. Other applications can be written in different languages and interact with the controller modules via the REST API. And the controller allows the implementation of built-in modules that can communicate with their implementation of the OpenFlow controller (i.e OpenFlow Services). The controller, on the other hand, can communicate with the switches via the OpenFlow protocol through the abstraction layer present at the forwarding hardware.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** QS-Dijkstra Algorithm Implementation. The algorithm is separated into two parts; a controller function which is implemented in Floodlight using Java, and a switch function implemented in Mininet using Python.</figcaption></figure>

We propose a Vulnerable-Link Avoidance Dijkstra (QS-Dijkstra) algorithm to capture the problem of best-effort avoiding vulnerable links while maintaining the delay constraint. QS-Dijkstra algorithm uses the previously-defined vulnerability metric in equation (2) to arrive at a set of feasible paths between source node *s* and destination node *t*.

The flowchart of the QS-Dijkstra algorithm that is implemented is shown in Fig. 1. The algorithm is separated into two parts, the switch side and the controller side. The algorithm of the controller side performs the following tasks:

1) Listening to messages from switches and calculating *link-delay* value of each link, and then constructing the *link-delay* cost matrix.

2) Calculating the *link-vulnerability* cost matrix according to the metric developed in formula (2); this matrix can be modified and calibrated by network operators or managers.

3) Running a *topology-update* thread, and checking the *link-vulnerability* cost matrix updates every $T_s$; if a change is detected, the controller recalculates the routing
paths.

4) Calculating the routing paths based on the link cost metrics of interest, and updating the flow table of each switch by advertise a PACKET OUT message to switches.

The main function of the algorithm in the switches side is to collect the values of *link-delays* for the directly connected switches. This is done through an independent thread responsible for periodically testing the link between that switch and all connected switches with higher ID. The sampling time is parametric and is tuneable by the network managers; in our simulation environment, *Tsd* is set to 60 seconds. Link delay testing is done 3 times every *Tsd* and the average value is then compared with the last known value. If the new delay is significantly different from the previous value, the switch updates the controller accordingly.

# 4. Simulation and Results

We build two large scale network environment with the same topology and route information. One is running the Dijkstra routing protocol, the other is for QS-Dijkstra. In order to reach a high performance, in each environment, we use the high-performance workstation with 10 Intel Xeon Westmere EP six-core processors. Whose maximum process speed could reach 11.251Tflops. Thus, the whole network includes 260 routers and a controller. For every node, we pick a random number from [1,10] for its connection number. And the commercial network flow generator Spirent TestCentre is chosen to generate some popular network application data, like http, IP, TCP, UDP. And it sends the same packets to the two networks synchronously.

<figure><img src="image_3.png" /><figcaption>**Fig. 8.** The Number of Transmitted Packets on Un-Safe Links. There are 20 links which have very high vulnerable level.</figcaption></figure>

In this test case, the link cost and link delay is randomized in the [0 – 100]. The maximum path delay constraint *T* still set as 1000 seconds. After calculating the link vulnerability metric, there are 20 links which have very high vulnerable level. We sampled the packets number transmitted through these links every 200 seconds and calculate the average value on each links. The result is shown in Fig. 8, which shows that the packets transmitted on these un-safe links in QS-Dijkstra are much less than in Dijkstra.
<figure><img src="image_4.png" /><figcaption>**Fig. 9.** The Average Response Time of Routers. In order to evaluate the network performance in the two networks, the average response times are recorded every 15 seconds.</figcaption></figure>

From the results shown in Figure 9, the conclusion could be proved that the network performance in QS-Dijkstra does not lost much except for a few short intervals, and the maximum responds time in these intervals is still could be acceptable.

**5. Conclusion**

In this paper, we consider the varying delay status of the communication network along with other network security parameters. Our approach capitalizes on the SDN framework and technology. The implement and experiment show that QS-Dijkstra algorithm is able to minimize traffic routing through vulnerable links while satisfying the QoS constraints of the network.

In the future work, the algorithm could consider more security and performance features of links and routing nodes, to make a more effective routing protocol.

**References**

1. B. Nunes, M. Mendonca, Xuan-Nam Nguyen, K. Obraczka and T. Turletti, "A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks", IEEE Communications Surveys & Tutorials, 16, 1617-1634. DOI: 10.1109/SURV.2014.012214.00180. pdf

2. Software-defined networking. http://en.wikipedia.org/wiki/Software-defined_networking

3. Open Networking Foundation 2012 "Software-defined networking: The new norm for networks," ONF White Paper

4. Y. Xiao, K. Thulasiraman, G. Xue and A. Juttner 2005 "The constrained shortest path problem: algorithmic approaches and an algebraic study with generalization," AKCE International Journal of Graphs and Combinatorics 2 63–86

5. F. Kuipers, P. Van Mieghem, T. Korkmaz, and M. Krunz 2002 "An overview of constraint-based path selection algorithms for QOS routing," IEEE Communications Magazine 40 50–55

6. A. Juttner, B. Szviatovski, I. M'ecs, and Z. Rajk'o 2001 "Lagrange relaxation based method for the QOS routing problem," Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies 2 859–868