欢迎来到留学生英语论文网

当前位置:首页 > 论文范文 > Computer Science

N Nodes and E Edges Network with QoS Constraints

发布时间:2017-04-09
该论文是我们的学员投稿,并非我们专家级的写作水平!如果你有论文作业写作指导需求请联系我们的客服人员

The task of QoS routing is to find a route in the network that satisfy the constraints using suffcient resources . In multi constrained Quality of Service (QoS) the routing deals with finding the routes that satisfy multiple independent constraints of Quality of Service. This problem is NP hard. The paper investigate two heuristics which are limited granularity heuristic and the limited path heuristic. These heuristics use extend the BellmanFord shortest path algorithm to solve general k-constrained QoS routing problems. The major results of this paper includethat the paper proves an optimal limited granularity heuristic idea and it shows that in polynomial time, the limited path heuristic has very high possibility of finding a path that satisfies the QoS constraints. The paper focused on an N nodes and E edges network with k QoS constraints, the limited granularity heuristic maintain a table of size O(|N|k–1) at each node to which has time complexity of O(|N|k|E|) and the limited path heuristic can achieve very high performance by maintaining O(|N|2lg(|N|)) entries in each node.

The multi-constrained routing problem is complicated and complex because different constraints conflict with each other. The multi-constrained path problem (MCP) like delay-costconstrained routing to find a route between two nodes in the network with constraints of end-to-end delay and end-to-end cost and it is NP-complete. The constraints is defined for QoS requirement of a pointtopoint connection can be a link constraints or path constraints. A link constraint is the limitation on the use of links like the bandwidth constraint in which each link has to support certain bandwidth. A path constraint is the an endtoend QoS requirement for the entire path. QoS routing identifies paths that meet the QoS requirement and finds one path that use resource efficiently. The kconstrained QoS routing problems are solved by applying two time heuristics, the limited granularity heuristic and the limited path heuristic on extended BellmanFord algorithm. For N nodes and E edges network with k independent path constraints, the limited granularity heuristic maintain a table of size O(|N|k–1) in each node and it achieve high probability of finding a path that satisfies the QoS k-constraints. The results in the paper showed that the limited granularity heuristic is ineffective when k>3 because the time and space requirement of the limited granularity heuristic increases with an increase in k but the limited path heuristic work more effective when k>3 . The three main contributions of the paper are first, the paper summarizes two types of heuristics which are applied on the extended Bellman-Ford algorithm solve kconstrained

QoS path routing problems. Second, the paper proves that the proposed algorithm provides guarantee in optimal worst case of finding paths that satisfy the QoS constraints. Third, the paper proposes the both the heuristic can efficiently find paths that satisfy the QoS constraints with very high probability when such paths exist. The paper consist of the following section. Section 2 describes the multi-constrained QoS routing problem and the bellman–ford algorithm.The section 3 discusses in detail the extension in bellman –ford algorithm which solvek–constrained problems. Section 3 discusses the heuristic for k–constrained problems. Section 4 presents the experimentation .Section 5 concludes the paper

In multi-constrained path problem (MCP) directed graph G (V, E) is given with a source vertex s, a destination vertex t, two weight functions w1:E → R+ 0 and w2:E → R+ 0 two constants c1 R+ 0 and c2 R+ 0 the problem is denoted MCP(G,s,t,w1,w2,c1,c2). It will find a path p from s to t such that constraint w2(p)≤ c1 and w2(p)≤ c2 are followed. If a path that satisfies the w2(p)≤ c1 and w2(p)≤ c2 isthe solution of MCP(G,s,t,w1,w2,c1,c2) The network is modeled as a directed graph G(N,E), with set of nodes N representing routers and set of edges E which represent the connection between the routers.Weight is associated with each edge e=u→v had associated weight with each edge which are independent to k–constraints w1(e),w2(e),w3(e).....wk(e) the wk2(e) is a positive real number wkR+ and wk> 0.

In Figure 1 there are three path from source S to destination D path p1 = S→ A →D (w(p1) = (40,2)) and path p2 = S →

B → D (w( p2) = (2,40)) are optimal QoS paths from node S to node D and path p3 = S → D the weight of this path is w(p3) = (50,4), p3 is not an optimal QoS path because w(p3) = (50,4)> w(p1).When k = 1 than only one shortest path is optimal QoS path . When k >1, however, there can be multiple optimal QoS paths between two nodes. QoS routing algorithm can guarantee of nding a path that satises the QoS constraints if such a path exists which satises the QoS constraints then algorithm considers all optimal QoS paths. The number of optimal QoS paths are increased exponentially with according to the size of network .

The bellman–Ford algorithm is use to solves the single source shortest path problems with negative and positive weight edges. The algorithm returns a boolean value indicating whether or not there is a negative weigh tcycle that is reachable from the source. It detects negative cycles and return true in case of negative weight cycle otherwise it returns the shortest path–tree Bellman–Ford returns the set of shortest paths from source s to all other vertices in the graph reachable from s. In the Initialization all the nodes expect source node are initialized with infinity(∞). The source node is initialized with 0. Then all the edges are labeled randomly. Then in each pass the shortest path on each edge is calculated. If G= (V, E)contains no negative weight cycles, then after the Bellman-Ford algorithm executes, d[v] = δ(s, v)for all v∈ V. Theorem : If G= (V, E)contains no negative weight cycles, then after the Bellman–Ford algorithm executes, d[v] = (s, v)for all v∈ V. Proof. Let v∈V be any vertex, and consider a shortest path p from s to v with the minimum number of edges According to figure 3 p is a shortest path, we have (s, vi) = δ(s, vi–1) + w(vk–1, vii) Initially, d[v0] = 0 = (s, v0), and d[v0]is unchanged by subsequent relaxations. After 1 pass through E, we have d[v1] = δ(s, v1). After 2 passes through E, we have d[v2] =δ(s, v2). . . . After k passes through E, we have d[vk] = δ(s, vk).

Since G contains no negative-weight cycles, p is simple. Longest simple path has ≤|V|–1edges. The Bellman-Ford algorithm runs in time O(VE), the initialization takes (V) time, each of the |V|–1 passes over the edges takes O(E) time and calculating the distance takes O(E) times.So total running time will be (|V|–1)—E— + —E— = O(VE)

The algorithm used in the paper to solve k–constraint problem is variation of the Bellman–Ford algorithm, the version of extended Bellman–Ford algorithm is described in this section. Figure 2 shows the algorithm, which is a variation of the Constrained Bellman–Ford algorithm. The algorithm checks whether there is an optimal path which satises the QoS constraints. The algorithm can easily be customized and modified to find the exact path. It is named as extended Bellman–Ford algorithm (EBFA). The Lines (1) to (3) in BELLMAN FORD are initialization of variables. Lines (4) to (6) perform the RELAX(u,v,w) operations on PATH(u) and PATH(v). After the relax operations all optimal QoS paths from node source src to node destination are stored in the set PATH(dst). Lines (7) and (8) check whether there exists an optimal path return by RELAX operation satises the QoS constraints. Inline(4)of the RELAX routine checks whether the old path q from src to v that is better than the new path p + (u → v) then the new path p + (u→ v) is not an optimal QoS path. Line (6) checks whether

the new path p + (u→v) is better than the old path q from src to v, if such path exist then the old path q is not an optimal QoS path and is removed from the set PATH(v). Line (8) adds the newly found optimal QoS path which satisfy the constraints to PATH(v). EBFA guarantees to find a path that satises the QoS constraints if such path exists it record all optimal QoS paths in each node. The number of the optimal QoS paths from source to u or v can increase exponentially with respect to the size of vertices V and edges E, the time and the space requirement of EBFA grow exponentially. The complexity of EBFA is O(V 2E). The heuristic limited granularity heuristic and the limited path heuristic are applied on EBFA to reduce the time and space requirement of EBFA while maintaining its effectiveness in finding paths that satisfy the QoS constraints. The idea of limited granularity heuristic is to limit the number of paths maintained in each node and limited path heuristic limit the size of the set PATH to bound the time and space requirement to execute the RELAX operation.

By limiting the size of PATH, each node cannot record all optimal QoS paths from the source and it only record the path which are approximate solutions. The challenge of the heuristics is how to limit the size of PATH in each node while maintaining the effectiveness in nding paths that satisfy QoS constraints, find the approximate and optimal solution. In this sections, we will discuss two heuristic to limit the size of PATH and study their performance when solving general k–constrained QoS routing problems.

Limited granularity heuristic is to use bound finite ranges of the path to approximate QoS metrics, it reduces the original NP–hard problem to a simpler problem which is solvable in polynomial time. It limit the number of path maintained by each node X. To solve the k–constrained problem the limited granularity heuristic approximates k–1 metrics with k–1 bounded finite ranges. Each node u maintains a table du[1 : X2,1 :X3,....,1 : Xk]. Each entry du[i1,i2,...,ik] in the table records the path that has the smallest w1 weight among all paths p from the source to node u. In the RELAX(u,v,w) operation, to compute dv[i1,i2,...,ik], only du[j1,j2,...,jk] where jl is the largest jl such that rljl rl il wl(u,v), for 2≤l≤k,needs to be considered. The RELAX routine has a time complexity of O(X2X3...Xk). By limiting the granularity of the QoS metrics, the time complexity of limited granularity heuristic is O(X|N||E|). The most complicated problem of limited granularity heuristic is to determine the relationship between the size of the table and the effectiveness of the heuristic in nding paths that satisfy the k QoS constraints. Lemma 1 : The limited granularity heuristic has probability of nding any path of length L that satises the QoS constraints, the size of the table in each node must be at least Lk–1 which is, X = X2X3...Xk ge Lk–1. It shows that the order for the limited granularity heuristic to find effective path of length L that satisfy k independent path constraints each node should be at least Lk–1 number of entries. For path of length L the entries in each node should be at least L. A network of N node paths can potentially be of length N. The limited granularity heuristic should at least maintain a table of size O(|N|k–1) for each node. The limited granularity heuristic is susceptible to the number of constraints .

B. The limited path heuristic The limited path heuristic make sure the worst case polynomial time complexity by limiting the number of optimal QoS paths, let X optimal QoS paths, in each node.In the limited granularity heuristic X is the size of the table maintained by each node. When a path is inserted into PATH, the size of PATH is checked first if the PATH already contains X elements, then new path is not inserted. The value X must be chosen carefully so that the heuristic is ecient and effective. If X is large such that each node then that records all optimal QoS paths but then it require large time and space complexity. To derive the probability probi the following method is used in which a set S contains i optimal QoS paths. The path p is an optimal QoS path because w1(p) is the smallest among all the paths. The wj(p) are not optimal QoS paths because their weights are 2≤j≤k. The is set T include all such nonoptimal QoS paths and set S –T contains all paths q where there exists at least one j such that wj(q) > wj(p). A path in the set S–T can be potentially be an optimal QoS path. The process is then repeated on the set S–T. If S contains m optimal QoS paths then this process can be repeated m times. The Pi,j notion is used to represent the probability of the remaining set size equal to j when the process is applied to a set of i paths and the number of QoS metrics is k. It is assumed that 0 ≤ j≤ i–1, then the notion Pi,j k is used.

The limited path heuristic will have very high probability to record all optimal QoS paths if each node maintains O(|N|2lg(|N|)) . It will have very high probability to nd the QoS paths which fulfill Qos constraints. It is not as sensitive to the number of QoS constraints.

The experiments are performed to compare the performance of the heuristics for real world network topologies and to study the impact of constants in the asymptotic bounds derived.It compared the two heuristics with the EBFA, it guarantees in finding a path that satises the QoS constraints.The experiment results are described using are two concepts, the existence percentage and the competitive ratio. The existence percentage tell how difficult it is to find a paths that satisfy the QoS constraints and competitive ratio indicates how well a heuristic algorithm performs. The data is obtained by running the two heuristics and the exhaustive algorithm using QoS constraints on 8×8 meshes. When a there large number of entries are at each nod the limited granularity heuristics and the limited granularity heuristics can have close to 1 competitive ratio.To achieve high competitive ratio the limited granularity heuristic requires to maintain a very large number the of entries .The competitive ratio of the limited path heuristic decreases to some extent. Comparing Figure 5 and the results in Figure 6,for 3constrained problems the number of entries in each node for the increases significantly as compared to 2–constrained problems. The table of 3–constrained problem has size of 40000 (200×200) worse as compare to the table of 2-constrained problems When the number of constraints increases from 2 to 6 but the competitive ratio falls from 100% to 32% for low existence percentage paths and from 100% to 58% for high existence percentage paths. The limited path heuristic is more efficient than the limited granularity heuristic in solving general k–constrained problems when k >3.

The QoS routing has two objectives rst to find routes that satisfy the QoS constraints. Second to make the efficient use of the network resources. First MCP problem is formalized and proposed a heuristic algorithm with a polynomial time complexity. The algorithm first reduces the problem MCP(G,s,t,w1,w2,c1,c2) to a simpler one MCPG,s,t,w1,w2,c1,x), and then uses an extended Bellman-Ford algorithm to find a solution for the new problem in

polynomial time. The paper present two heuristics, the limited granularity heuristic and the limited path heuristic, which are applied to the extended Bellman Ford algorithm to reduce its time and space complexity and efficiently solve k constrained QoS path routing problems. Both the heuristics can solve k–constrained QoS routing problems with high probability in polynomial time. The limited granularity heuristic requires much more resources than the limited path heuristic. The k–constrained routing problem is NP hard in the worst case, it can be solved efficiently by using the heuristics discussed in the paper. The limited granularity heuristics maintain a table of size O(|N|k–1) which results in a time complexity of O(|k||E|) and the limited path heuristic maintain O(|N|2lg(|N|–1)) entries in each node.

上一篇:Building a Feedback Control Based Website Security to Prevent XML Injection Attacks 下一篇:Literature Review on Online Gaming