Sage Journals: Discover world-class research

Abstract

This article addresses the problem related to the reliability of path after transmitting the given amount of data with the service-level agreement cooperation in the computer communication network. The links have associated with service performance factor parameter during the data transmission, and each node is associated with the requested service performance factor. In this article, first we have considered the single objective to minimize the transmission time of the quickest path problem. An algorithm for quickest path problem has been proposed for results, and furthermore, its time complexity has been shown. The problem has been extended with bi-objective optimization of the quickest path problem, which minimizes the transmission time and hybrid logarithmic reliability. An algorithm is proposed for getting the number of efficient solutions for the quickest path problem using label-correcting algorithm. The algorithms are implemented and tested on different standard benchmark network problems provided with the set of Pareto front of the results.

Keywords

Quickest path problem hybrid logarithmic reliability service performance factor service-level agreements bi-objective optimization

Introduction

In the computer communication network (CCN), while data transmission occurs across the two specific ends, it takes time to transmit the data, which is the function of the two parameters, that is, delay occurred along the path and the capacity of the path. The applicability of these types of problem has been addressed in a number of examples; therefore, these types of problem in the networks gained attention by researchers and have been termed as quickest path problem (QPP). The QPP was pioneered by Chen and Chin¹ with the objective of designing a path with minimum transmission time in the directed network. But before this, the QPP was modelled by Moore² for the convey-type traffic problems. Later, the QPP model used to extend the single-path problem into a k-paths problem. Furthermore, the QPP model had been used to extend the model into bi-objective path problem by Martins and Dos Santos³ and Pelegrın and Fernández.⁴

To understand the concept of QPP, let us assume that CCN can be modelled as directed loopless CCN $(G = (N, E))$ with $(N)$ set of nodes and $(E)$ set of links. Each set of nodes and link contains $(n)$ number of nodes and $(m)$ number of links, respectively. Let $(u)$ and $(v)$ are the two nodes and a link is represented by $(u, v)$ . Let data $(σ)$ be transmitted between two specific nodes: source node $(s)$ and destination node $(t)$ . There are a number of different network resources associated with each link $(u, v) \in E$ such as capacity and delay of link, $d (u, v)$ and $c (u, v)$ , respectively. The capacity of a link is the bottleneck function of a path which represents as the bandwidth associated with the link so that data can be transmitted over a link $(u, v)$ per unit time with constant flow. The link delay is the time occurred during the traversing of the link $(u, v)$ . Consider path $(P)$ is the path from node $(s = u_{1})$ to node $(t = u_{k})$ with the combination of number of nodes and links given as $P = (s = u_{1}, \dots, u_{k} = t)$ such that $u_{i} \in N, i = 1, 2, \dots, k$ and $(u_{i}, u_{i + 1}) \in E, i = 1, 2, \dots, k - 1$ .

Let us assume that a unit data $(σ)$ is sent as a constant data stream over the link $(u, v)$ with a continuous flow rate $ρ$ such that $ρ \leq c (u, v)$ experience the $[d (u, v) + (σ / ρ)]$ transmission time from the node $(u)$ to node $(v)$ along the link $(u, v)$ . This transmission time is occurred minimum at the value of $ρ = c (u, v)$ ; therefore, the aforementioned expression indicates the minimum transmission time to transmit the unit data $(σ)$ , that is, $[d (u, v) + (σ / c (u, v))]$ .

Using the application of circuit-switching mode, let us assume that data $(σ)$ is being transmitted with a constant rate from $(s)$ to $(t)$ nodes without any intermediate buffering. The minimum transmission time along an $s - t$ path $(P)$ is given by Chen and Chin¹

\begin{matrix} T_{σ} (P) = \sum_{i = 1}^{i = k - 1} d (u_{i}, u_{i + 1}) \\ + \frac{σ}{\min_{i = 1}^{k - 1} c (u_{i}, u_{i + 1})} \equiv d (P) + \frac{σ}{c (P)} \end{matrix}

(1)

The first part of equation (1) represents the delay occurred along the path $(P)$ and the denominator of the second part in the equation shows the bottleneck capacity of the path $(P)$ , which are given as

d (P) = \sum_{i = 1}^{k - 1} d (u_{i}, u_{i + 1})

(2)

c (P) = min_{i = 1, 2, \dots, k} c (u_{i}, u_{i + 1})

(3)

The above equations are self-sufficient to formulate the QPP

\begin{matrix} min T_{σ} (P) \\ Subject to P is an s - t path in network (G) \end{matrix}

(4)

In general, the optimality of a path has a great influence on data transmitted along a path which is the general characteristic. If data traffic is very small, then transmission time mainly depends on the delay parameter which can be a good solution. If data traffic is extremely high, then the time taken for transmission is controlled by maximum capacity, where the path has to follow the maximum capacity of the path. In addition, it is worth to mention that QPP does not follow the principle of optimality of path such that if a path $(P)$ is optimum, then it is not necessary that its sub-path will be optimum. The QPP got wide attention by the research communities and, therefore, several different polynomial algorithms have been proposed with the same time complexity of $O (r (m + nlog (n)))$ , where $(r)$ represents the number of different capacities associated with the networks in previous studies;^5–7 however, it is worth to mention that they do not have same space complexities. The algorithms proposed by Calvete et al.⁵ and Park et al.⁸ use the space complexity of $O (rm + rn)$ , whereas the algorithms proposed by Martins and Dos Santos,³ Pelegrın and Fernández,⁴ Rosen et al.⁶ and Sedeño-Noda and González-Barrera⁷ use the space complexity of $O (m + n)$ .

In a previous study, Hamacher and Tjandra⁹ proposed the evacuation model for the QPP with only a single path for evacuee. Several extensions of QPP have been made by researchers,^10–16 to get the solution to the problem such as finding the k quickest paths. The computation of QPP by considering reliability not lower than the given threshold value has been proposed by Calvete et al.⁵

In the CCN, the reliability got embedded with QPP and, therefore, proposes to model as a reliable QPP. In addition, due to the importance of reliability in the communication, the number of extensions has been made by the researchers Ruzika and Thiemann,¹⁷ and Lin and colleagues^18,19 proposed the QPP for the network. The proposal of Xue²⁰ has been extended by Calvete et al.⁵ by setting the thresholding scheme for the reliability. In correspondence with the increased demand, data transmission services require a network to be predictable, that is, quick and reliable.

While formulating QPP, no attention is paid to the uncertainties associated with the network such as man-made disasters, natural disasters and Tsunamis. It was thought that the data transmission occurs without any failures along the $s - t$ path. Maybe it was the case of a wired network, but practically, still these are associated, and in case of wireless networks, this scenario becomes worse. Therefore, the consideration of link reliabilities gives us the privilege to comment on the successful data transmission.

To counter the failures with QPP, the link reliability $r_{l} (u, v)$ plays a better role for failure-free data transmission. Using the theory of reliability,²¹ the path reliability is given by Xue²⁰

R_{l} (P) = Π_{i = 1}^{k - 1} r_{l} (u_{i}, u_{i + 1})

(5)

In present times, due to the huge integrity of applications, the scarcity of network resources leads to imposing the service-level agreements (SLAs) on the data transmission or service.^22–24 These SLAs are the prime factor for the consideration of data transmission along the $s - t$ path.²⁵ The link reliabilities are not the only failure of data transmission, but SLA failures are also associated with the uncertainties; therefore, to save the network resources, each link is requested to be an SLA cooperative before taking part in the communication or data transmission.^26,27 Let us consider an example that any service or data transmission requested between two ends over an $s - t$ path in x time, but these data are received at y time such that $x < y$ ; therefore, SLAs are not satisfied, and the resources associated with the transmission over an $s - t$ path are wasted. As discussed earlier, there is a vast literature of taking account of link reliabilities and transmission time in the data transmission; therefore, it is good to model the SLAs comparable to the link reliabilities and transmission time. Hence, a service performance factor (SPF) is proposed to model the transmission time, reliabilities and SLAs into a single factor. In this article, we introduce the service-level agreement cooperative quickest path problem (SLAQPP) model and an algorithm which aims to give the SLA cooperation to the reliable and quickest path for the transmission of unit data $(σ)$ along the $s - t$ path.

In addition, it is worth full to mention that the proposed model is the only extension of QPP in terms of constrained QPP with the same time complexity.

However, as an evaluation of system reliability is a non-deterministic polynomial-time (NP)-hard problem, the problem remains interesting to the researchers, and in literature, it has been seen that it is not self-sufficient to restrict only single-objective QPP.^28–30

For better understanding between existing algorithm and proposed algorithm, a qualitative comparison study has been presented in Table 1.

Table 1.

Comparison of different existed algorithms with the proposed algorithm.

References	Quickest	Reliable	SLA	Comment
Chen and Chin¹	✓	✗	✗	Quickest path problem
Xue²⁰	✓	✓	✗	Quickest or most reliable path problem
Lin³¹	✓	✓	✗	QPP to the system reliability evaluation
Ruzika and Thiemann¹⁷	✓	✓	✗	Reliable and restricted path problem
Calvete et al.⁵	✓	✓	✗	Reliable quickest path problem
El Khadiri and Yeh³²	✓	✓	✗	Quickest path flow network reliability problem
Sharma and Kumar¹³	✓	✓	✗	Pre-computated multi-constrained QPP
Proposed SLAQPP	✓	✓	✓	SLA cooperative QPP

SLA: service-level agreement; QPP: quickest path problem; SLAQPP: service-level agreement cooperative quickest path problem.

The aforementioned comparative study shows that the proposed algorithm outperforms with existing algorithms and considering all the performance parameters for the computation of path for data transmission.

Nowadays, the applications are good indicative and shows the necessity of two or more objective,^33–35 other than of single objective. Some of the examples of the bi-objective problem to find the efficient solutions are transportation problem,^36–38 supply chain problem,^39,40 assignment problem,^41,42 travelling and salesman problem,^43–45 cargo loading and unloading,^46–48 defence machineries⁴⁹ and healthcare.⁵⁰

Therefore, we have addressed the bi-objective SLAQPP, that is, (BSLAQPP) where transmission time and hybrid logarithmic reliability are minimized. An algorithm has been developed to find the efficient set of paths based on solving the bi-objective shortest path problems (SPPs).

A solution of the bi-objective problem can provide the non-dominated path with minimum delay and maximum capacity. We have considered the bi-objective shortest path (BSP) problem⁵¹ which is the extension of the single-objective SPP. This extension comes under the category of multiple-objective combinatorial optimizations (MOCOs).⁵² In BSP, the aim is to find the number of efficient solutions for the problem. Since BSP problem is an NP-hard problem⁵³ and intractable as the number of the efficient solution may get exponential variation with small change in the number of nodes but, for the practical application, it is acceptable to get a finite number of efficient solution. In this article, it has been considered that for mission-critical applications, such as, remote surgeries, E-healthcare, E-banking and E-shopping,²⁶ mainly two objectives as minimum transmission time and hybrid logarithmic reliability of service are required. Therefore, the problem is formulated as a BSLAQPP.

Contribution

The main contribution of the proposed work can be seen as follows:

The main contribution can be highlighted, as authors have proposed a single-objective optimization model for data transmission with minimum transmission time by considering the SLAs for critical services. The SLA consideration guarantees the successful data transmission within requested service time.

In the proposed work, the authors have also extended single objective to bi-objective to minimize the transmission time and hybrid logarithmic reliability using bi-objective optimization. Using bi-objective optimization, both objectives have been used to find the path for data transmission which is a favourable case for critical services.

So far, many researchers have studied the minimum transmission time problem, but the inclusion of SLA and proposed bi-objective optimization algorithm makes this approach unique.

The qualitative and quantitative comparative study shows that the proposed algorithm is outperforming with all other existing models with consideration of SLAs.

Another major contribution of the proposed model is that the mathematical model can be further extended for the different application with bi-objective optimization such as healthcare critical routing and goods carriers routing.

Organization

This article is structured into six sections – section ‘Proposed system model’ is used to explain the proposed system model for SLAQPP. Theoretical results have been discussed in section ‘Theoretical results’, and an algorithm has been proposed in section ‘SLAQPP algorithm and complexity’. An extension of SLAQPP in terms of BSLAQPP has been proposed in section ‘The BSLAQPP’. Section ‘Simulation results and discussion’ has been used to explain the simulation results and discussion. The conclusion has been presented in section ‘Conclusion and future work’.

Proposed system model

In the CCN, the performance of data transmission has a great influence on the quality of service (QoS).⁵⁴ The QoS of a network depends on several parameters, such as link capacity $(c (u, v))$ , link delay $(d (u, v))$ , link reliability $(r_{l} (u, v))$ , data $(σ)$ and requested SLA parameters. Therefore, it is necessary to consider all performance factors collectively into a single parameter to maximize the QoS. The QoS depends mainly on the connectivity of the links and completion of service in specific SLA service requested time.⁵⁵ Here, we have conceptualized the integrity of the link parameters into a single-link parameter termed as service performance factor. But before this, the mapping of SLAs should be known; therefore, before jumping directly on the SPF, mapping of SLAs has been given in the next sub-section.

Mapping of SLAs

As the service expectations are stringent in mission-critical applications,⁵⁶ the SLAs are drawn between service providers (SPs) and users in various terms depending on the services.⁵⁷ Here, the problem is considered for the data transmissions, so SLAs are drawn in terms of requested service time $(t_{s})$ and service $(MTT F_{s})$ . Requested service time is the time till which a service is requested, and the service $(MTT F_{s})$ is the mean time for which transmission service of data traffic is considered as failure-free transmission.

In the CCN, the allowed time for the completion of services is very minute, approximately seconds $(s)$ . Therefore, units for requested service time and service $MTT F_{s}$ are considered in seconds $(s)$ .

Each node is endowed with requested service performance factor (RSPF) denoted as $(r_{u})$ for the data transmission at node $(u)$ and calculated using given SLAs

r_{u} = e^{- \frac{t_{s}}{MTT F_{s}}}

(6)

SPF

In the CCN, the performance of data transmission is not affected only by the link reliability $r_{l} (u, v)$ but also with the QoS resources associated with the links, so it is required to integrate all performance parameters to enhance the performance. The integrity of all parameters made comparable to the reliability, as this article deals with reliability theory. The single parameter termed as the service performance factor is denoted as $(r_{s} (u, v))$ and is given as

r_{s} (u, v) = e^{- [\frac{d (u, v) + \frac{σ}{c (u, v)}}{MTT F_{s}}]}

(7)

The SPF for a path $(P)$ is calculated as given below using equations (1) and (7)

R_{s} (P) = e^{- [\frac{\sum_{i = 1}^{i = k - 1} d (u_{i}, u_{i + 1}) + \frac{σ}{\min_{i = 1}^{k - 1} [c (u_{i}, u_{i + 1})]}}{MTT F_{s}}]}

(8)

Using the properties of exponentials, equation (8) is modified as

\begin{matrix} R_{s} (P) = Π_{i = 1}^{k - 1} e^{- [\frac{\sum_{i = 1}^{i = k - 1} d (u_{i}, u_{i + 1})}{MTT F_{s}}]} \times e^{- [\frac{\frac{σ}{\min_{i = 1}^{k - 1} [c (u_{i}, u_{i + 1})]}}{MTT F_{s}}]} \\ R_{s} (P) = e^{- [\frac{d (P) + \frac{σ}{c (u, v)}}{MTT F_{s}}]} = e^{- [\frac{T_{σ} (P)}{MTT F_{s}}]} \end{matrix}

(9)

To design the SLAQPP system model, let us assume that for data $(σ)$ transmitted along a link $(u, v) \in E$ is associated with the SPF $(r_{s} (u, v) > 0)$ which measures the SLA cooperation and depends typically on the characteristics of link $(u, v)$ (i.e. delay, capacity and SLAs).

In this model, to satisfy SLA, the SPF has to be more than that of the RSPF and the remaining value is termed as the residual requested service performance factor (RRSPF) symbolized by $r_{u} (σ, P)$ . The RRSPF is defined as the remaining RSPF from the endowed SPF at the nodes after the data transmission along path $(P)$ . This term used to comment on that whether the node is taking part in the SLA cooperative data transmission or not. After commenting and using the definition of RRSPF, the condition is given as

e^{- [\frac{d (u, v) + \frac{σ}{c (u, v)}}{MTT F_{s}}]} \geq r_{u}, \forall (u, v) \in E

(10)

From equation (10), if link $(u, v)$ does not cooperate with this condition, then it cannot take part in the SLA cooperative data transmission and can be removed. In addition, unit data $(σ)$ is transmitted through the $s - t$ path $(P)$ having the path capacity $c (P)$ ; therefore, the SPF along with the $s - t$ path is

R_{s} (P) = e^{- [\frac{d (P) + \frac{σ}{c (u, v)}}{MTT F_{s}}]}

(11)

Remark

The capacity of path $(c (P))$ has been considered here other than the link capacity $(c (u, v))$ because we have assumed that the path is associated with constant data flow $(ρ)$ and, therefore, the capacity of path $(c (P))$ is the minimum capacity of the link taking part in the $s - t$ path $(P)$ .

A diagram is shown in Figure 1 to show the framework of the link model with the link reliability $(r_{l} (u, v))$ and the SPF $(r_{s} (u, v))$ .

Figure 1.

The total hybrid reliability of a link.

The total hybrid reliability of a link $(u, v)$ is elaborated as

r_{T} (u, v) = r_{l} (u, v) \times r_{s} (u, v)

(12)

The total path reliability $(R_{T} (P))$ is evaluated as shown in Figure 2

R_{T} (P) = R_{l} (P) \times R_{s} (P)

(13)

Figure 2.

Model of computation of total hybrid reliability of the path.

Furthermore, total hybrid path reliability $(R_{T} (P))$ is expanded as follows

Π_{i = 1}^{k - 1} r_{l} (u_{i}, u_{i + 1}) \times e^{- [\frac{\sum_{i = 1}^{i = k - 1} d (u_{i}, u_{i + 1})}{MTT F_{s}}]} \times e^{- [\frac{\frac{σ}{\min_{i = 1}^{k - 1} [c (u_{i}, u_{i + 1})]}}{MTT F_{s}}]}

(14)

The RRSPF that is, $r_{u} (σ, P)$ at node $(u)$ after transmitting $(σ)$ unit data along with the $s - t$ path $(P)$ is

r_{u} (σ, P) = {\begin{matrix} [e^{- \frac{d (u_{i}, u_{i + 1})}{MTT F_{s}}} \times e^{- \frac{\frac{σ}{c (P)}}{MTT F_{s}}}] - (r_{u_{i}}), \\ if u = u_{i}, i = 1, 2, 3, ., k - 1 \\ - (r_{u_{i}}) else \end{matrix}

(15)

In order to get the SLA cooperative $s - t$ feasible path $(P)$ , $r_{u} (σ, P) \geq 0, \forall u \in P$ . Equation (15) is the SLA constraint applied at node $(u)$ . Hence, SLAQPP is formulated to find the $s - t$ path $(P)$ as

\begin{matrix} min T_{σ} (P) \\ Subject to : r_{u} (σ, P) \geq 0, u \in N \\ P is an s - t path in the network (G) \end{matrix}

(16)

The SLA cooperation on the data transmission allows us to propose an algorithm based on the RSPF which helps us to develop an algorithm based on the SPP in sub-networks $(G_{j})$ of the original network $(G)$ .

Theoretical results

In general, let us assume that a network $(G)$ is having $(r)$ number of different capacities. The SLA cooperative minimum capacity level associated with the each link $(u, v) \in N$ is given as

c_{\min} (u, v) = min_{i = 1, \dots, r} {c_{i} : [e^{- \frac{d (u_{i}, u_{i + 1})}{MTT F_{s}}} \times e^{- \frac{\frac{σ}{c (P)}}{MTT F_{s}}}] - (r_{u_{i}}) \geq 0}

(17)

Equation (17) is associated with the label of minimum SLA cooperative capacity of the link $(u, v)$ for the data transmission over an $s - t$ path $(P)$ . Therefore, by satisfying the SLA cooperative capacity for the links $(u, v)$ , the path $(P)$ is also satisfied. Note that a link $(u, v)$ can take part in the $s - t$ path $(P)$ only and only if it satisfies the condition of the feasibility of a link, that is, $c (P) \geq c_{\min} (u, v)$ .

A CCN is divided into different sub-networks $(G_{j}; j = 1, 2, \dots, r)$ which is equal to the number of different capacities $(c_{j})$ . The SLA cooperative links are sorted in the sub-networks $(G_{j})$ given as

c_{\min} (u, v) \leq c_{j} \leq c (u, v); where j = 1, 2, 3, \dots, r

(18)

Lemma 1

A path $P = (s = u_{1}, u_{2}, u_{3} \dots, u_{k} = t)$ is a feasible path if it is an SLA cooperative $s - t$ path in the sub-network $(G_{j})$ .

Proof

If path $(P)$ is an SLA cooperative $s - t$ path in sub-network $(G_{j})$ , then capacity of path follows $c (P) \geq c_{j} \geq c_{\min} (u_{i}, u_{i + 1})$ , where $j = 1, 2, 3, \dots, r and i = 1, 2, 3, \dots, k - 1$ . Hence

\begin{matrix} r_{u_{i}} (σ, P) = e^{\frac{- [\sum_{i = 1}^{k - 1} d (u_{i}, u_{i + 1}) + \frac{σ}{c (P)}]}{MTT F_{s}}} \\ - Π_{i = 1}^{k} r_{u_{i}} \geq e^{\frac{- [\sum_{i = 1}^{k - 1} d (u_{i}, u_{i + 1}) + \frac{σ}{{c_{\min}}_{i = 1}^{k - 1} (u_{i}, u_{i + 1})}]}{MTT F_{s}}} - Π_{i = 1}^{k} r_{u_{i}} \geq 0 \end{matrix}

Lemma 2

Let path $P = (s = u_{1}, u_{2}, \dots, u_{k} = t)$ is a feasible path for the SLAQPP having the capacity of $c (P) = c_{j}$ , then path $(P)$ is an $s - t$ path in the sub-network $(G_{j})$ .

Proof

From the definition of Lemma 1, the path $(P)$ is feasible

\begin{matrix} e^{\frac{- [\sum_{i = 1}^{k - 1} d (u_{i}, u_{i + 1}) + \frac{σ}{c (P)}]}{MTT F_{s}}} - Π_{i = 1}^{k} r_{u_{i}} \geq 0, \\ where i = 1, 2, 3, \dots, k - 1 \end{matrix}

Therefore, if $c (P) = c_{j}$ and $c_{\min} (u_{i}, u_{i + 1}) \leq c (P) = c_{j} \leq c (u_{i}, u_{i + 1})$ such that $i = 1, 2, 3, \dots, k - 1$ and link $(u_{i}, u_{i + 1})$ in the network, then $(P)$ is an $s - t$ path in sub-network $(G_{j})$ .

Now, here it is essential to point out that for an $s - t$ feasible SLAQPP path $(P)$ , it is not necessary to follow the condition for the capacity of path $c (P) > c_{j}$ in the sub-network $(G_{j})$ .

Lemma 3

Let a path $(P)$ be an optimal solution for the $s - t$ path given by the $(SP P_{j})$ having the path capacity of $c (P) = c_{h} > c_{j}$ . Then, in that network $(G)$ , there is no any other optimal solution for the $s - t$ SLAQPP path having the capacity $(c_{j})$ .

Proof

Let path $(Q)$ be considered as a feasible SLAQPP path having the capacity $(c_{j})$ . Then, the path $(Q)$ is an $s - t$ path in sub-network $(G_{j})$ and

R_{T} (P) = R_{l} (P) . e^{\frac{- [d (P) + \frac{σ}{c_{h}}]}{MTT F_{s}}} < R_{l} (Q) . e^{\frac{- [d (Q) + \frac{σ}{c_{j}}]}{MTT F_{s}}} = R_{T} (Q)

Thus, the path $(Q)$ is not said as an optimal SLAQPP path solution.

Theorem 1

Let path $(\tilde{P})$ be considered an optimal SLAQPP solution, and path $(\tilde{P})$ has a capacity of $(c_{h})$ , then the path $(\tilde{P})$ is an optimal solution of $SP P_{h}$ , and any optimal solution of the $SP P_{h}$ is an optimal solution of SLA cooperative QPP of data transmission.

Proof

Since, the path $(\tilde{P})$ is an SLAQPP $s - t$ feasible path having the capacity $(c_{h})$ , then $(\tilde{P})$ is a path in sub-network $(G_{h})$ . Let path $(Q)$ be an $s - t$ path in sub-network $(G_{h})$ , then capacity $c (Q) \geq c_{h}$ . If $d (Q) < d (\tilde{P})$ , then

R_{T} (Q) = R_{l} (P) . e^{\frac{- [d (Q) + \frac{σ}{c (Q)}]}{MTT F_{s}}} < R_{l} (\tilde{P}) . e^{\frac{- [d (\tilde{P}) + \frac{σ}{c_{h}}]}{MTT F_{s}}} = R_{T} (\tilde{P})

SLAQPP algorithm and complexity

Algorithm for SLAQPP

Algorithm 1: SLAQPP Algorithm
Input: $G (N, E), σ, r_{l} (u, v), c (u, v), d (u, v), r_{u}, t_{s} and MTT F_{s}$ Output: SLA-Cooperative QPPBEGIN{
Initialization: $j \leftarrow 1,$ Procedure: STEP0: Variable Declaration $G \leftarrow Directed Network$ $N \leftarrow Set of nodes$ $E \leftarrow Set of links$ $r_{l} (u, v) \leftarrow Reliability of link (u, v)$ $c (u, v) \leftarrow Capacity of link (u, v)$ $d (u, v) \leftarrow Delay of link (u, v)$ $r_{u} \leftarrow Requested service performance factor at node u$ $σ \leftarrow Data$ $t_{s} \leftarrow Requested service time$ $MTT F_{s} \leftarrow Mean Time to Failure of service$ STEP1: Prune $r$ different capacities of links corresponds to continuous service & label of minimum capacity: (i) $c_{1} < c_{2} < c_{3} \dots < c_{r}$ (ii) $c_{\min} (u, v)$ STEP2: Solve $SP P_{j}$ w.r.t. delay time $d (u, v)$ in $G_{j}$ with capacities $c_{j}$ For $j \leftarrow 1 : r$ Set $j \leftarrow 1$ Solve $SP P_{j}$ If No $s - t$ path in $G_{j}$ with capacity with $c_{j}$ go to STEP3 else Let $P_{j}$ is an optimal solution for $SP P_{j}$ with capacity $c (P_{j}) = c_{j}$ end endSTEP3:If $j = r$ go to STEP4else set $j = j + 1$ and go to STEP2endSTEP4: Find the solutionFind index $h \in (1, 2, \dots r)$ of path array $P_{j}$ such that $T_{σ} (P_{h}) = min_{j = 1, \dots, r} T_{σ} (P_{j})$ $P_{h}$ is an optimal solution of the SLAQPP} END

Algorithm 1: SLAQPP Algorithm

Input:

G (N, E), σ, r_{l} (u, v), c (u, v), d (u, v), r_{u}, t_{s} and MTT F_{s}

Output: SLA-Cooperative QPPBEGIN{

Initialization:

j \leftarrow 1,

Procedure: STEP0: Variable Declaration

G \leftarrow Directed Network

N \leftarrow Set of nodes

E \leftarrow Set of links

r_{l} (u, v) \leftarrow Reliability of link (u, v)

c (u, v) \leftarrow Capacity of link (u, v)

d (u, v) \leftarrow Delay of link (u, v)

r_{u} \leftarrow Requested service performance factor at node u

σ \leftarrow Data

t_{s} \leftarrow Requested service time

MTT F_{s} \leftarrow Mean Time to Failure of service

STEP1: Prune

r

different capacities of links corresponds to continuous service & label of minimum capacity: (i)

c_{1} < c_{2} < c_{3} \dots < c_{r}

(ii)

c_{\min} (u, v)

STEP2: Solve

SP P_{j}

w.r.t. delay time

d (u, v)

G_{j}

with capacities

c_{j}

For

j \leftarrow 1 : r

Set

j \leftarrow 1

Solve

SP P_{j}

If No

s - t

path in

G_{j}

with capacity with

c_{j}

go to STEP3 else Let

P_{j}

is an optimal solution for

SP P_{j}

with capacity

c (P_{j}) = c_{j}

end endSTEP3:If

j = r

go to STEP4else set

j = j + 1

and go to STEP2endSTEP4: Find the solutionFind index

h \in (1, 2, \dots r)

of path array

P_{j}

such that

T_{σ} (P_{h}) = min_{j = 1, \dots, r} T_{σ} (P_{j})

P_{h}

is an optimal solution of the SLAQPP} END

Complexity analysis

The complexity of SLAQPP is given as in Theorem 2.

Theorem 2

By performing the time complexity analysis on SLAQPP, the proposed algorithm has the time complexity of $O (r (m + n (\log (n)))$ .

Proof

The flow in computation of SLAQPP algorithm has been explained as follows in different steps. In the first step of simulation, that is, STEP0, all the input variables are defined. After defining the input variables, all the sub-networks are taken out after satisfying SLA constraint in STEP1. All these sub-networks are taken out after the satisfaction of SLA constraint for different link capacities present in the network. In STEP2, SPP is used to compute path with minimum cost for different sub-networks with the help of Dijkastra’s algorithm. The SPP computes the minimum cost path with time complexity of $O (m + n (logn))$ .⁵¹ In STEP3, as there are ‘r’ different capacities present in the network, the SPP algorithm runs for ‘r’ times. Therefore, in STEP3, the time complexity now becomes as $O (r (m + n (\log (n))))$ . STEP4 is used to find the path having minimum transmission time for the data transmission.

The BSLAQPP

As the name suggests that, the objective of the problem is not only to minimize the transmission time but also come up with the objective of maximizing the hybrid reliability of the path. Therefore, the problem of finding the path for both objectives has been designed as the minimization problem. Here, we have used a negative logarithm to the hybrid reliability and this term is known as hybrid logarithmic reliability. From the discussion of SLAQPP model, every link in the network $(G)$ is associated with delay $d (u, v)$ , capacity $c (u, v)$ and link reliability $r_{l} (u, v)$ . In addition, from the section ‘Proposed system model’, it has been assumed that for the SLA cooperation, the SLAs are drawn and, therefore, each node $(u)$ is associated with RSPF. Therefore, using the notations from the sections ‘Introduction’ and ‘Proposed system model’, the BSLAQPP is used to find the feasible set of feasible $s - t$ paths and is given by

\begin{matrix} \min (T_{σ} (P), - \ln R_{T} (P)) \\ Subject to : r_{u} (σ, P) \geq 0, u \in N \\ P is an s - t path in the network (G) \end{matrix}

(19)

The MOCO problems are the NP-hard problem to get the single optimized values of each objective simultaneously and can be studied with different application perspectives. In this article, the main objective is to construct the Pareto front of the set of efficient solutions. Let us dictate some definitions to understand the basis for the BSLAQPP model.

Definitions

Definitions – 1

The set $χ$ (chi) is the feasible set of solutions or the set of alternative solutions for the decision-type problems. The $χ$ (chi) is the subset of solutions from the sample space is known as the decision space.

Let, if $F = (F_{1}, F_{2})$ is the cost function, in our case $F_{1}$ represents the transmission time and $F_{2}$ is the hybrid logarithmic reliability, then the functions are mapped $F_{i} : χ \to R$ (set of real numbers) are the objective functions.

The bi-objective optimization problem is given as

min_{x \in X} (F_{1} (x), F_{2} (x))

This image set is called criterion space. Criterion values are selected from criterion space.

Definitions – 2

Consider the bi-criterion optimization problem of the type

min_{x \in X} (F_{1} (x), F_{2} (x))

For the feasible solution set X, the solution image is mapped as $y = F (x)$ under the objective function mapping $(F)$ . A solution $x^{*} \in X$ is said to be a Pareto optimal solution, if it satisfies the following criteria:

$x^{*}$ is a feasible solution.

There is no other $x \in X$ s.t. $F (x) ⩽ F (x^{*})$ .

Furthermore, if $(x^{*})$ is an efficient solution then $(x^{*})$ is said to be a non-dominated solution point in the Pareto front.

If $x_{1}, x_{2} \in X$ and $F (x_{1}) ⩽ F (x_{2})$ , then $x_{1}$ is said to dominate $x_{2}$ and hence $F (x_{1})$ dominates $F (x_{2})$ .

The collection of all efficient solution as called an efficient set, denoted by $X_{E}$ . The collection of all non-dominated set of solutions, denoted by $(Y_{N})$ .

Definitions – 3

The solutions that cannot be improved in any of the objectives without de-regarding at least one of the other objectives is called as Pareto solution. Mathematically, a feasible solution $(x_{1} \in X)$ is Pareto solution, which dominates to another Pareto solution $(x_{2} \in X)$ by following the conditions as $f_{i} (x_{1}) \leq f_{i} (x_{2}) \forall i \in {1, 2, 3, \dots, k}$ and $f_{j} (x_{1}) \leq f_{j} (x_{2}) \forall j \in {1, 2, 3, \dots, k}$ .

Any solution $x^{*} \in X$ is said to be Pareto optimal solution of only and only if there is no any other solution which dominates another solution. The Pareto front has been formed using Pareto optimal outcomes.

Definitions – 4

A feasible set of solutions of the path $(P)$ is said to be efficient if and only if there is no other feasible solution of the path $(Q)$ such that the condition are given as $T_{σ} (Q) \leq T_{σ} (P)$ and $- \ln [R_{T} (Q)] \leq - \ln [R_{T} (P)]$ .

Where one condition to follow the one strict inequality.

Definitions – 5

The image ${T_{σ} (P), - \ln [R_{T} (P)]}$ of the path $(P)$ is said to be the non-dominated point.

We know that a complete set of efficient solution is a set of efficient solutions, given by $(X_{e})$ such that complement of every feasible solution in $(X_{e})$ is either dominated or at least there is one feasible solution in set $(X_{e})$ .

Definitions – 6

The two feasible solutions $(P)$ and $(Q)$ are called equivalent if and only if they have the same image.

If images of two feasible solutions along the path $(P)$ and $(Q)$ are same then $(P)$ and $(Q)$ are said to be equivalent.

In bi-objective QPP, the target is to obtain the efficient solutions. Such type of problems are NP-hard problems and also intractable. In this situation, the total number of efficient solutions may be very large; hence, it is a difficult task.

The constraints on the SPF of link reliability can be converted into additive form by making use of logarithmic function as follows

R_{s} (P) = \underset{(u, v) \in P}{Π} F (u, v) ⩾ \underset{u \in P}{Π} α_{u}

- \ln (R_{s} (P)) = \sum_{(u, v) \in P} - \ln (F (u, v)) ⩽ \underset{u \in P}{Π} - \ln (α_{u})

where $(α_{u})$ is the RSPF.

Now, we can define the parameter $(F^{*})$ for the link of $G (N, E)$ as follows

F^{*} (v^{c_{i}}, u^{c_{j}}) = - \ln (F (u, v)) \forall (v^{c_{i}}, u^{c_{j}}) \in E_{i}

As a consequence, a path $(\tilde{P})$ is reliable if and only if $\sum_{(x, y) \in \tilde{P}} F (x, y) ⩽ - \ln (α_{u})$ , where $(\tilde{P})$ is the path in network $(G)$ .

Theorem 3

Let $\tilde{P}$ be an $s - t$ efficient path for the BSLAQPP algorithm and $c (\tilde{P}) = c_{h}$ . Then the path $(\tilde{P})$ is an $s - t$ efficient path given as follows

\begin{matrix} BSP P_{h} : min_{\tilde{P}} (d (\tilde{P}), - \ln (R_{s} (\tilde{P}))) \\ s . t . \tilde{P} is a s - t path in the network (G) \end{matrix}

Proof

The path $(\tilde{P})$ is an $s - t$ path in the network $(G_{h})$ , by construction of this network. Let us assume that there is an $s - t$ path $(Q)$ in the network $(G_{h})$ which dominates the path $(\tilde{P})$ with respect to the bi-objective function $(d, - \ln (R_{s}))$ . Then, $c (Q) \geq c_{h}$ and $d (Q) \leq d (\tilde{P})$ and $- \ln (R_{s} (Q)) \leq - \ln (R_{s} (\tilde{P}))$ with at least with one strict inequality

T_{σ} (Q) = d (Q) + \frac{σ}{c (Q)} \leq d (Q) + \frac{σ}{c (\tilde{P})} < d (\tilde{P}) + \frac{σ}{c (\tilde{P})} = T_{σ} (\tilde{P})

and

\begin{matrix} - \ln (R_{T} (Q)) = - \ln (R_{s} (Q) . e^{- [\frac{d (Q) + \frac{σ}{c (Q)}}{MTT F_{s}}]}) \\ \leq - \ln (R_{s} (\tilde{P}) . e^{- [\frac{d (Q) + \frac{σ}{c (\tilde{P})}}{MTT F_{s}}]}) \leq - \ln (R_{s} (\tilde{P}) . e^{- [\frac{d (\tilde{P}) + \frac{σ}{c (\tilde{P})}}{MTT F_{s}}]}) \\ = - \ln (R_{T} (\tilde{P})) \end{matrix}

The aforementioned equations contradict the theorem statement that the path $(\tilde{P})$ is an $s - t$ efficient solution of the algorithm.

In the first part of our proposed BSLAQPP algorithm, we will apply a bi-objective label-correcting method.⁵¹ The bi-objective problem is the simple extension of the single-objective problem. The main difference in this bi-objective problem is that a label contains two labels where these labels do not dominate one another. The merging has been done for the testing of dominance process and this process somewhat more classy and expensive. To reduce this constrained bi-objective problem has been proposed here. Based on Theorem 3, a BSLAQPP algorithm is proposed as follows:

Algorithm 2: BSLAQPP Algorithm
Input: $G (N, E), σ, r_{l} (u, v), c (u, v), d (u, v), r_{u}, t_{s} and MTT F_{s}$ Output: Bi-objective SLA-Cooperative QPPBEGIN {
Initialization: $j \leftarrow 1, ε = ϕ$ Procedure: STEP0: Variable Declaration $G \leftarrow Directed network$ $N \leftarrow Set of nodes$ $E \leftarrow Set of links$ $r_{l} (u, v) \leftarrow Reliability of link (u, v)$ $c (u, v) \leftarrow Capacity of link (u, v)$ $d (u, v) \leftarrow Delay of link (u, v)$ $r_{u} \leftarrow Requested service performance factor at node u$ $σ \leftarrow Data$ $t_{s} \leftarrow Requested service time$ $MTT F_{s} \leftarrow Mean Time to Failure of service$ STEP1: Prune ‘ $r$ ’ different capacities of links corresponds to continuous service & label of minimum capacity: (i) $c_{1} < c_{2} < c_{3} \dots < c_{r}$ (ii) $c_{\min} (u, v)$
STEP2: Solve the $BSP P_{j}$ using label correcting method. Initialize: $D (s) = {(0, 0)}, D (t) = ϕ, t = N - {s};$ Labelled: $\| s \|$ Routine:while Labelled $\neq ϕ$ Choose i from Labelled Labelled $= {i}$ For $j \in out (i)$ $D_{M} (j) : = Merge (D (j), D (i) + len (i, j));$ If $D_{M} (j) \neq D (j)$ , then $D (j) = D_{M} (j)$ If j is not labelled then (Avoid repetitive Labelling) Labelled = $Labelled \cup (j)$ end if;end if;end while if there is no $s - t$ path in $G_{j}$ , go to STEP3. Otherwise, let $E_{j}$ be a complete set of efficient paths of the $BSP P_{j}$ For each $P \in E_{j}$ , compute $[T_{σ} (P), - \ln (R_{T} (P))]$ $E = Merge (E, E_{j})$ STEP3: if $j = r$ , STOP, $E$ solves the bi-objective problem.Otherwise, set $j = j + 1$ and go to STEP2.Where the operation Merge is defined as follows; $Merge (E, E_{j}) = P \in E \cup E_{j}$ s. t. there is no $Q \in E \cup E_{j}$ such that Q dominates P with respect to the bi-objective function $[T_{σ}, - \ln (R_{T})]$ .

Simulation results and discussion

Experimental setup

The experimental results are performed on a desktop having processor of Intel(R) Core^TM i5–7400, CPU@ 3.00 GHz, 8-GB RAM, and Windows 10 operating system in MATLAB 2013a. The SLAMRQ involves the Dijkstra’s algorithm which is solvable in polynomial time. To conduct the simulation experiment, values of the capacities in $(Mb / s)$ and delay in $(s)$ are generated from the uniform distribution in the range of [1, 100], respectively. The reliability of links is generated from the uniform distribution ranging [0, 1]. A service promising contract SLA is drawn between the user and SP in term of requested service time $(t_{s})$ in $(s)$ and service $MTT F_{s}$ in $(s)$ . The illustration of results is performed over two different topologies: five-node benchmark-directed network with eight links^1,58–60 and 14-node National Science Foundation Network (NSFNET)-directed network with 21 links,⁶¹ shown in the Figures 3 and 4, respectively. Data of $100 Mb$ have been transmitted from $(s)$ to $(t)$ with the SLAs of $t_{s} = 240 s$ and $MTT F_{s} = 1500 s$ .

Figure 3.

Benchmark topology.

Figure 4.

14-NSFNET topology.

The SLAQPP performance evaluation

The performance evaluation for the SLAQPP has been given by performing simulations on two different standard topologies as shown below in Figures 3 and 4:

The step-wise explanation for the proposed SLAQPP algorithm has been given as below:

For the STEP0, all input variables have been declared. In Table 2, the values of reliability, capacity and delay of each link associated with each link have been shown for the topology shown in Figure 3. Data of $100 Mb$ have been transmitted from $(s)$ to $(t)$ with the SLAs of $t_{s} = 240 s$ and $MTT F_{s} = 1500 s$ .

Table 2.

The 3-tuple values of $(r, d, c)$ associated with each link for the benchmark topology.

Link	$r (u, v)$	$d (u, v)$	$c (u, v)$	Link	$r (u, v)$	$d (u, v)$	$c (u, v)$
$a_{1}$	0.3795	76	20	$a_{5}$	0.5936	35	60
$a_{2}$	0.3046	62	27	$a_{6}$	0.4966	81	20
$a_{3}$	0.1897	79	60	$a_{7}$	0.6979	92	60
$a_{4}$	0.1509	94	20	$a_{8}$	0.8998	1	60

In STEP1, the number of different capacities present in the given topology is equal to three; therefore, the network is divided into three different sub-networks after satisfying the SLA constraint. The simulation results of SLAQPP for the topology shown in Figure 3 are dictated in Table 3.

Table 3.

Results of the SLAQPP for the benchmark topology.

Capacity	Selected path	$T_{σ} (P)$	Comment
20	$1 - 2 - 5$	111.5000	Minimum
27	$1 - 3 - 4 - 5$	155.3704	No
67	Undefined	$\infty$	Path does not exist

SLAQPP: service-level agreement cooperative quickest path problem.

Using STEP2, the SPP algorithm with delay time as a cost function found only two paths for first two sub-networks as $P_{1} = 1 - 2 - 5$ and $P_{1} = 1 - 3 - 4 - 5$ . For the third sub-network, there is no path available for the data transmission. In STEP3, algorithm jumps for STEP4 after last sub-network. In STEP4, a set of all paths have been listed and corresponding to that path, value of minimum transmission time objective has been calculated, that is, $T_{σ} (P) = min [111.5000, 155.3704, \infty]$ . Now, path having minimum transmission time, $T_{σ} (P)$ value is the path for SLAQPP. Hence, the path $1 - 2 - 5$ is the SLAQPP path which has a minimum transmission time having the path capacity of $c (P) = 20 Mb / s$ .

Furthermore, SLAQPP also simulated for 14-node NSFNET as shown in Figure 4 with 21 links, and their respected values of reliability, capacity and delay are shown in Table 4. The numbers of different capacities present in the network are equal to 11. The simulation results of SLAQPP for the 14-NSFNET are shown in Table 5.

Table 4.

The 3-tuple values of $(r, d, c)$ associated with each link for the 14-node NSFNET topology.

Link	$r (u, v)$	$d (u, v)$	$c (u, v)$	Link	$r (u, v)$	$d (u, v)$	$c (u, v)$
$a_{1}$	0.5527	18	87	$a_{12}$	0.4249	96	4
$a_{2}$	0.7313	27	99	$a_{13}$	0.3062	35	44
$a_{3}$	0.0534	6	46	$a_{14}$	0.4091	6	17
$a_{4}$	0.1939	20	17	$a_{15}$	0.3756	73	31
$a_{5}$	0.6552	38	46	$a_{16}$	0.9423	59	59
$a_{6}$	0.4442	63	46	$a_{17}$	0.5208	5	17
$a_{7}$	0.1146	59	99	$a_{18}$	0.5414	19	12
$a_{8}$	0.5973	84	59	$a_{19}$	0.3939	24	17
$a_{9}$	0.5134	88	87	$a_{20}$	0.7241	55	17
$a_{10}$	0.5711	37	59	$a_{21}$	0.5692	64	34
$a_{11}$	0.1133	43	84

NSFNET: National Science Foundation Network.

Table 5.

Results of the SLAQPP for the 14-node NSFNET topology.

Capacity	Selected path	$T_{σ} (P)$	Comment
4	$1 - 2 - 4 - 11 - 14$	149.0000	No
12	$1 - 2 - 4 - 11 - 14$	132.3333	No
17	$1 - 2 - 4 - 11 - 14$	129.8824	Minimum
31	$1 - 3 - 6 - 13 - 14$	213.2258	No
34	$1 - 3 - 6 - 13 - 14$	212.9412	No
44	Undefined	$\infty$	Path does not exist
46	Undefined	$\infty$	Path does not exist
59	Undefined	$\infty$	Path does not exist
84	Undefined	$\infty$	Path does not exist
87	Undefined	$\infty$	Path does not exist
99	Undefined	$\infty$	Path does not exist

SLAQPP: service-level agreement cooperative quickest path problem; NSFNET: National Science Foundation Network.

There are only five paths which are capable to perform SLAQPP, and the path $1 - 2 - 1 - 11 - 14$ is the SLAQPP path which has the minimum transmission time with the path capacity of $c (P) = 34 Mb / s$ .

The simulations of SLAQPP for both standard topologies show that as the different capacities in the network are increased, the possibilities of getting different sets of $s - t$ paths is also increased.

The BSLAQPP performance evaluation

The simulation results for the BSLAQPP have been shown on the two different standard topologies benchmark and 14-node NSFNET as shown in Figures 3 and 4, respectively.

The step-wise explanation for the proposed BSLAQPP algorithm has been given as follows:

In STEP0, all the input variables have been declared. The different values used for the simulation of BSLAQPP for the benchmark topology have been shown in Table 6. Data of $100 Mb$ have been transmitted from $(s)$ to $(t)$ with the SLAs of $t_{s} = 240 s$ and $MTT F_{s} = 1500 s$ .

Using STEP1, the number of different capacities are present in the given network are five; therefore, there are five different sub-networks sorted according to different capacities, 10, 20, 30, 40 and 50 Mbps for the BSLAQPP. The SLA cooperative links for the each sorted sub-network has been shown below in Figure 5(b)–(f).

In STEP2, the BSLAQPP simulations for the given topology using label-correcting method⁵¹ are shown in Table 7. Using STEP3, the bi-objective minimization for the path $P = 1 - 2 - 5$ is the best path which has minimum tranmission time and minimum hybrid logarithmic relaibility.

Table 6.

The 3-tuple values of $(r, d, c)$ associated with each link of benchmark network for the BSLAQPP.

Link	$r (u, v)$	$d (u, v)$	$c (u, v)$	Link	$r (u, v)$	$d (u, v)$	$c (u, v)$
$a_{1}$	0.80	10	50	$a_{5}$	0.90	20	40
$a_{2}$	0.80	10	10	$a_{6}$	0.60	20	50
$a_{3}$	0.85	15	30	$a_{7}$	0.55	10	20
$a_{4}$	0.90	15	30	$a_{8}$	0.80	5	50

BSLAQPP: bi-objective service-level agreement cooperative quickest path problem.

Figure 5.

(a) On the links $(c_{\min} (u, v), c (u, v))$ , (b) network $G_{1}$ , (c) network $G_{2}$ , (d) network $G_{3}$ , (e) network $G_{4}$ and (f) network $G_{5}$ .

Table 7.

Path selection for the benchmark topology using the BSLAQPP.

Capacity	Selected path	$T_{σ} (P)$ , $- \ln (R_{T} (P))$	Comment
10	$1 - 2 - 3 - 4 - 5$	(45, 1.7440)	No
20	$1 - 2 - 5$	(30, 0.5506)	No
30	$1 - 2 - 5$	(28, 0.3285)	Minimum
40	$1 - 2 - 4 - 5$	(37, 0.8371)	No
50	Undefined	( $\infty$ , $\infty$ )	Path does not exist

BSLAQPP: bi-objective service-level agreement cooperative quickest path problem.

The Pareto solution distribution has shown in Figure 6 for the BSLAQPP results shows that the path $P = 1 - 2 - 5$ is the feasible path for the data transmission.

Figure 6.

Pareto solution of the benchmark network for the simulations of BSLAQPP.

It is worth pointing out that it is not necessary that a feasible $s - t$ path $(P)$ with path capacity $c (P) > c_{j}$ is a feasible $s - t$ path $(P)$ in network $(G_{j})$ . In the aforementioned example, the capacity of path $(P) 1 - 2 - 5$ is equal to 30. However, this path is neither in $(G_{1})$ nor in $(G_{2})$ . It can be concluded that a network $(G_{j})$ with a path $(P)$ of $(G)$ is feasible for BSLAMRQ having path capacity is greater than or equal to $(c_{j})$ , for which

{r_{u}}_{i} (σ, P) = e^{\frac{- [d (u_{i}, u_{i + 1}) + \frac{σ}{c_{j}}]}{τ}} - r_{u_{i}} \geq 0, i = 1, 2, 3, \dots, k - 1

The network $(G_{j})$ contains all the $s - t$ feasible paths for the BSLAMRQ with path capacity $(c_{j})$ . Hence, if there is no $s - t$ path $(P)$ in the network $(G_{j})$ , then there will not be an optimal solution of the BSLAMRQ path with capacity $(G_{j})$ . The values associated with each link of the 14-node NSFNET topology has been taken from the Table 4 as shown above in the previous section.

The simulation results of the BSLAQPP for the standard topology 14-nodes NSFNET have been shown in Table 8.

Table 8.

Path Selection for the 14-node NSFNET topology using BSLAQPP.

Capacity	Selected path	$T_{σ} (P), - \ln (R_{T} (P))$	Comment
4	$1 - 8 - 10 - 14$ or $1 - 2 - 4 - 11 - 14$	(151, 4.8516)or(149, 2.6290)	No
12	$1 - 2 - 4 - 11 - 14$	(150, 2.7340)	No
17	$1 - 2 - 4 - 11 - 14$	(148, 2.8324)	Minimum
31	$1 - 3 - 6 - 13 - 14$	(213, 2.8339)	No
34	$1 - 3 - 6 - 13 - 14$	(213, 2.9818)	No
44	Undefined	( $\infty$ , $\infty$ )	Path does not exist
46	Undefined	( $\infty$ , $\infty$ )	Path does not exist
59	Undefined	( $\infty$ , $\infty$ )	Path does not exist
84	Undefined	( $\infty$ , $\infty$ )	Path does not exist
87	Undefined	( $\infty$ , $\infty$ )	Path does not exist
99	Undefined	( $\infty$ , $\infty$ )	Path does not exist

BSLAQPP: bi-objective service-level agreement cooperative quickest path problem; NSFNET: National Science Foundation Network.

There are 11 different capacities present and, therefore, network has been divided into 11 different sub-networks. The number of BSLAQPP paths are less than or equal to the number of different capacities. Here, only five capacities are capable of providing BSLAQPP an $s - t$ path, but there is also a special case of BSLAQPP simulation for the path having capacity of $c (P) = 4 Mb / s$ . Therefore, by using Definition 4, both can be feasible solutions for the data transmission from the complete set of efficient solutions. The Pareto solution for the simulations has been shown below to get the feasible solution for the BSLAQPP (Figure 7).

Figure 7.

Pareto solutions of the 14-node NSFNET for the simulations of BSLAQPP.

The path $P = 1 - 2 - 4 - 11 - 14$ is the feasible solution for the BSLAQPP with the capacity of path $c (P) = 17 Mb / s$ . The results shows that when same values have been applied to the same topology for the SLAQPP simulation, then the path $P = 1 - 3 - 6 - 13 - 14$ is the feasible solution for the SLAQPP with the capacity of path $c (P) = 34 Mb / s$ .

The Pareto solution helps us to find the optimal path with two parameters, as one can see a path $P = 1 - 2 - 4 - 11 - 14$ with minimum hybrid logarithmic reliability having the path capacity of $c (P) = 12 Mb / s$ . But when both parameters considered the $P = 1 - 2 - 4 - 11 - 14$ has been considered with path capacity of $c (P) = 17 Mb / s$ . We can perceive that the number of efficient solutions is small as required in the practical applications.

The proposed BSLAQPP algorithm has certain applications in different research areas listed as follows with constraints comparable to our proposed BSLAQPP model (Table 9).

Table 9.

List of different applications with objectives.

Sr. No.	Applications	Objective A	Objective B
1	Ambulance routing	The time between accident and hospital	Gridlocks probability
2	Goods carriers routing	Goods abide time probability	Time for transportation
3	School bus routing	Students tolerable time in the bus	Time between drop and pick
4	Critical healthcare	Reliability and availability of the data transmission	Service lag time

In ambulance routing, the first objective is minimum time between accident and hospital location and second objective is minimum gridlock probability. Failure to one of these objectives at any time can lead to the loss of patient. Both objectives are needed to be minimized at the same time; hence, the proposed bi-objective theoretical model can be adopted here with little modification in mathematical models.

For another application such as critical healthcare over a network, where reliability of path should be maximum and service lag time should be as minimum as possible. As we are considering critical healthcare application, both objectives need to be satisfied at the same time. Failure to any one of the objectives may lead to severe consequences in terms of life loss. In practical real-time applications, there are a number of applications with a tremendous need of such type of models to support these applications.

Comparative remarks

For the comparative study, we have adopted three existing algorithms Chen and Chin,¹ Calvete and colleagues,^5,16 and compared with proposed algorithm to transmit $100 Mb$ data from s to t.

In Chen and Chin,¹ the algorithm gives the path $1 - 2 - 4 - 11 - 14$ but unable to comment on reliability, energy and SLA satisfaction.

In case of Calvete et al.,⁵ the algorithm is again able to compute the path $1 - 2 - 4 - 11 - 14$ , but with the drawback of energy and SLA satisfaction.

In case of Calvete et al.,¹⁶ the algorithm is again able to compute the path $1 - 2 - 4 - 11 - 14$ , but unable to provide the reliability and SLA satisfaction.

In the proposed algorithm, the computed path is able to comment on SLA as well as reliability of the path (Table 10). The energy consideration has not been considered in this case and can be computed in future works.

Table 10.

Qualitative comparison of the existing algorithms with proposed SLAQPP algorithm.

Reference	Objective function	Path	Path capacity	Remark
Chen and Chin¹	$\begin{matrix} min_{P} T_{σ} (P) \\ s . t . P is an s - t path in the network G \end{matrix}$	$1 - 2 - 4 - 11 - 14$	$17 (Mb / s)$	Quickest path but no comments on SLA satisfaction
Calvete et al.⁵	$\begin{matrix} \begin{matrix} min_{P} T_{σ} (P) \\ s . t . R (P) \geq α \end{matrix} \\ P is an s - t path in the network G \end{matrix}$	$1 - 2 - 4 - 11 - 14$	$17 (Mb / s)$	Reliable and quickest path but no comments on SLA satisfaction
Calvete et al.¹⁶	$\begin{matrix} \begin{matrix} min_{P} T_{σ} (P) \\ s . t . P_{u} (σ, P) \geq 0, u \in P \end{matrix} \\ P is an s - t path in the network G \end{matrix}$	$1 - 2 - 4 - 11 - 14$	$17 (Mb / s)$	Energy aware and quickest path but no comments on SLA satisfaction
Proposed SLAQPP	$\begin{matrix} \begin{matrix} min_{P} T_{σ} (P) \\ s . t . r_{u} (σ, P) \geq 0, u \in P \end{matrix} \\ P is an s - t path in the network G \end{matrix}$	$1 - 2 - 4 - 11 - 14$	$17 (Mb / s)$	SLA aware quickest path problem (SLAQPP)

SLAQPP: service-level agreement cooperative quickest path problem; SLA: service-level agreement.

Conclusion and future work

In this article, a theoretical model of BSLAQPP has been introduced which is a variant of QPP with the constraints of SLAs. As QPP simulation has been carried out by taking the delay as a cost function, in this article, before using this property of QPP, SLA cooperation over the links has been made. The consideration of SLA is useful for the successful completion of data transmission which is useful for the critical services. A polynomial time algorithm proposed for the SLAQPP simulation with the same time complexity. Furthermore, simulations have been extended for the bi-objective QPP with the objective of minimization in transmission time and hybrid logarithmic reliability. The BSLAQPP presents the Pareto front to find the feasible solution from the complete set of efficient paths. The results show its usefulness where the necessity of equal consideration of both objects is required. These theoretical models can be further extended with practical applications where both these objectives are strictly required. In the future works, these results will be expanded for the large networks, standard road networks and with the certain applications such as ambulance routing, goods carriers routing, school bus routing and critical healthcare. In addition, this problem can be modelled for the multi-objective QPP with different constraints like risk, energy, vulnerability and sensitivity.

Footnotes

Acknowledgements

We would like to thank the University of Sharjah, Dubai Electronic Security Center (DESC) and OpenUAE Research and Development Group for funding this research study.

Handling Editor: Gianluigi Ferrari

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 in part from the research project titled, ‘Reliability Modeling and Optimized Planning of Risk-based Resilient Networks’ sponsored by the Indo-Polish Programme (grant no. DST/INT/POL/P-04/2014).

ORCID iD

Ashutosh Sharma

References

Chen

Chin

The quickest path problem. Comput Oper Res 1990; 17: 153–161.

Moore

MH.

On the fastest route for convoy-type traffic in flowrate-constrained networks. Transport Sci 1976; 10: 113–124.

Martins

EDQV

Dos Santos

JLE

. An algorithm for the quickest path problem. Oper Res Lett 1997; 20: 195–198.

Pelegrın

Fernández

On the sum-max bicriterion path problem. Comput Oper Res 1998; 25: 1043–1054.

Calvete

del-Pozo

Iranzo

JA.

Algorithms for the quickest path problem and the reliable quickest path problem. Comp Manag Sci 2012; 9: 255–272.

Rosen

Sunand

S-Z

Xue

G-L.

Algorithms for the quickest path problem and the enumeration of quickest paths. Comput Oper Res 1991; 18: 579–584.

Sedeño-Noda

González-Barrera

JD.

Fast and fine quickest path algorithm. Eur J Oper Res 2014; 238: 596–606.

Park

C-K

Lee

Park

A label-setting algorithm for finding a quickest path. Comput Oper Res 2004; 31: 2405–2418.

Hamacher

Tjandra

SA.

Mathematical modelling of evacuation problems: a state of art, 2001, https://kluedo.ub.uni-kl.de/frontdoor/deliver/index/docId/1477/file/bericht24.pdf

10.

Chen

Finding the k quickest simple paths in a network. Inform Process Lett 1994; 50: 89–92.

11.

Clímaco

Pascoal

Craveirinha

, et al. Internet packet routing: application of a K-quickest path algorithm. Eur J Oper Res 2007; 181: 1045–1054.

12.

Pascoal

Captivo

Clímaco

Computational experiments with a lazy version of a K quickest simple path ranking algorithm. TOP 2007; 15: 372–382.

13.

Sharma

Kumar

A framework for pre-computated multi-constrained quickest QoS path algorithm. J Telecommun Electron Comput Eng 2017; 9: 73–77.

14.

Gopal

Kumar

An algorithm for computing the best-performing path in a computer network. Int J Perform Eng 2007; 3: 203–212.

15.

Calvete

del-Pozo

Iranzo

JA.

Dealing with residual energy when transmitting data in energy-constrained capacitated networks. Eur J Oper Res 2018; 269: 602–620.

16.

Calvete

del-Pozo

Iranzo

JA.

The energy-constrained quickest path problem. Optim Lett 2017; 11: 1319–1339.

17.

Ruzika

Thiemann

Reliable and restricted quickest path problems. In: Pahl

Reiners

Voß

(eds) Network optimization. Berlin: Springer, 2011, pp.309–314.

18.

Lin

Y-K

Chang

P-C.

Evaluate the system reliability for a manufacturing network with reworking actions. Reliab Eng Syst Safe 2012; 106: 127–137.

19.

Lin

Y-K

Huang

C-F

Yeng

LC-L

, et al. Project reliability interval for a stochastic project network subject to time and budget constraints. IEEE T Reliab 2017; 66: 689–699.

20.

Xue

End-to-end data paths: quickest or most reliable?

IEEE Commun Lett 1998; 2: 156–158.

21.

Barlow

Proschan

Mathematical theory of reliability, vol. 17. Philadelphia, PA: SIAM, 1996.

22.

Cicconetti

Lenzini

Mingozzi

, et al. Quality of service support in IEEE 802.16 networks. IEEE Network 2006; 20: 50–55.

23.

Helvik

Følstad

EL.

The cost for meeting SLA dependability requirements: implications for customers and providers. Reliab Eng Syst Safe 2016; 145: 136–146.

24.

Odun-Ayo

Ajayi

Omoregbe

Cloud service level agreements – issues and development. In 2017 international conference on next generation computing and information systems (ICNGCIS), Jammu, India, 11–12 December 2017, pp.1–6. New York: IEEE.

25.

Marilly

Martinot

Papini

, et al. Service level agreements: a main challenge for next generation networks. In: 2nd European conference on universal multiservice networks. ECUMN’2001, Colmar, 8–10 April 2002, pp.297–304. New York: IEEE.

26.

Xie

Zeng

Chen

, et al. Minimizing redundancy to satisfy reliability requirement for a parallel application on heterogeneous service-oriented systems. IEEE T Serv Comput 2017; 10: 1–16.

27.

Yang

Zhang

, et al. Experimental demonstration of multi-dimensional resources integration for service provisioning in cloud radio over fiber network. Sci Rep 2016; 6: 30678.

28.

Linand

Y-K

Nguyen

T-P.

Reliability evaluation of a multistate flight network under time and stopover constraints. Comput Ind Eng 2018; 115: 620–630.

29.

Chen

Yang

, et al. Capacity reliability of a road network: an assessment methodology and numerical results. Transport Res B-Meth 2002; 36: 225–252.

30.

Zhu

Guo

Lombardi

, et al. Approximate reliability of multi-state two-terminal networks by stochastic analysis. IET Networks 2017; 6: 116–124.

31.

Lin

Y-K.

Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Comput Oper Res 2003; 30: 567–575.

32.

El Khadiri

Yeh

W-C

. An efficient alternative to the exact evaluation of the quickest path flow network reliability problem. Comput Oper Res 2016; 76: 22–32.

33.

Deb

Multi-objective optimization. In: Burke

Kendall

(eds) Search methodologies. New York: Springer, 2014, pp.403–449.

34.

Kim

de Weck

OL.

Adaptive weighted-sum method for bi-objective optimization: Pareto front generation. Struct Multidiscip O 2005; 29: 149–158.

35.

Yang

Zhang

Zhao

, et al. CSO: cross stratum optimization for optical as a service. IEEE Commun Mag 2015; 53: 130–139.

36.

Issabakhsh

Hosseini-Motlagh

S-M

Pishvaee

M-S

, et al. A vehicle routing problem for modeling home healthcare: a case study. Int J Transp Eng 2018; 5: 211–228.

37.

Khaled

Minoux

Mousseau

, et al. A compact optimization model for the tail assignment problem. Eur J Oper Res 2018; 264: 548–557.

38.

Evans

Optimization algorithms for networks and graphs. Abingdon: Routledge, 2017.

39.

Tosarkani

Amin

SH.

A possibilistic solution to configure a battery closed-loop supply chain: multi-objective approach. Expert Syst Appl 2018; 92: 12–26.

40.

Khalilpourazari

Khamseh

AA.

Bi-objective emergency blood supply chain network design in earthquake considering earthquake magnitude: a comprehensive study with real world application. Ann Oper Res. Epub ahead of print 28 July 2017. DOI: 10.1007/s10479-017-2588-y.

41.

Hao

, et al. Fuzzy optimal allocation model for task-resource assignment problem in a collaborative logistics network. IEEE T Fuzzy Syst 2019; 27: 1112–1125.

42.

Wen

Pacino

Kontovas

, et al. A multiple ship routing and speed optimization problem under time, cost and environmental objectives. Transport Res D-Tr E 2017; 52: 303–321.

43.

Mahi

Baykan

ÖK

Kodaz

A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem. Appl Soft Comput 2015; 30: 484–490.

44.

Osaba

Yang

X-S

Diaz

, et al. An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng Appl Artif Intel 2016; 48: 59–71.

45.

Agatz

Bouman

Schmidt

Optimization approaches for the traveling salesman problem with drone. Transport Sci 2018; 52: 965–981.

46.

Wen

Ropke

Petersen

, et al. Full-shipload tramp ship routing and scheduling with variable speeds. Comput Oper Res 2016; 70: 1–8.

47.

Zachariadis

Tarantilis

Kiranoudis

CT.

The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints. Eur J Oper Res 2016; 251: 369–386.

48.

Linand

D-Y

Chang

Y-T.

Ship routing and freight assignment problem for liner shipping: application to the Northern Sea Route planning problem. Transport Res E-Log 2018; 110: 47–70.

49.

McCarter

Barker

Johansson

, et al. A bi-objective formulation for robust defense strategies in multi-commodity networks. Reliab Eng Syst Safe 2018; 176: 154–161.

50.

Sharma

Kumar

An optimal routing scheme for critical healthcare HTH services – an IOT perspective. In 2017 fourth international conference on image information processing (ICIIP), Shimla, India, 21–23 December 2017, pp.1–5. New York: IEEE.

51.

Raith

Ehrgott

A comparison of solution strategies for biobjective shortest path problems. Comput Oper Res 2009; 36: 1299–1331.

52.

Deb

. Multi-objective optimization using evolutionary algorithms, vol. 16 . Hoboken, NJ: John Wiley & Sons.

53.

Sedeno-Noda

Raith

A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem. Comput Oper Res 2015; 57: 83–94.

54.

Van Mieghem

Kuipers

. Concepts of exact QoS routing algorithms. IEEE Acm T Network 2004; 12: 851–864.

55.

Duan

Zhangand

Z-L

Hou

YT.

Service overlay networks: SLAs, QoS, and bandwidth provisioning. IEEE Acm T Network 2003; 11: 870–883.

56.

Kumar

Cholda

A framework for continuity of mission-critical network services. In 2015 IEEE international conference on Advanced networks and telecommuncations systems (ANTS), Kolkata, India, 15–18 December 2015, pp.1–3. New York: IEEE.

57.

Keller

Ludwig

The WSLA framework: specifying and monitoring service level agreements for web services. J Netw Syst Manag 2003; 11: 57–81.

58.

Gen-Huey

Yung-Chen

Algorithms for the constrained quickest path problem and the enumeration of quickest paths. Comput Oper Res 1994; 21: 113–118.

59.

G-H Chen Hung

Y-C

. On the quickest path problem. Inform Process Lett 1993; 46: 125–128.

60.

Lin

Y-K.

Optimal pair of minimal paths under both time and budget constraints. IEEE T Syst Man Cy A 2009; 39: 619–625.

61.

Bolot

J-C.

End-to-end packet delay and loss behavior in the Internet. Acm Sigcomm Comp Com 1993; 23: 289–298.

Network modelling and computation of quickest path for service-level agreements using bi-objective optimization

Abstract

Keywords

Introduction

Contribution

Organization

Proposed system model

Mapping of SLAs

SPF

Remark

Theoretical results

Lemma 1

Proof

Lemma 2

Proof

Lemma 3

Proof

Theorem 1

Proof

SLAQPP algorithm and complexity

Algorithm for SLAQPP

Complexity analysis

Theorem 2

Proof

The BSLAQPP

Definitions

Definitions – 1

Definitions – 2

Definitions – 3

Definitions – 4

Definitions – 5

Definitions – 6

Theorem 3

Proof

Simulation results and discussion

Experimental setup

The SLAQPP performance evaluation

The BSLAQPP performance evaluation

Comparative remarks

Conclusion and future work

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References