Qos

1

CHAPTER 1 INTRODUCTION

1.1

GENERAL Today’s Internet can only provide ‘best-effort’ service which

means it tries to forward user traffic but can provide no guarantee regarding delay, delay variance, hop-count, loss rate and bandwidth. QoS routing differs from conventional best-effort routing mainly in that, the path selected for forwarding traffic needs to satisfy multiple constraints simultaneously (Subharthi Paul et al 2010). In traditional data networks, routing is primarily concerned with connectivity. Routing proposals usually characterize the network with a single metric such as delay or hop-count and use shortest-path algorithms for path computation. In order to support a wide range of QoS requirements, routing protocols need to have a more complex model where the network is characterized with multiple metrics. The basic problem of QoS routing is to find a path that satisfies multiple constraints. As current routing protocols are reaching the limit of feasible complexity, it is important that the complexity introduced by the QoS support should not impair the performance of routing protocols. The role of a QoS routing strategy is to compute paths that are suitable for the different types of traffics generated by various applications, while maximizing the utilization of network resources (Pablo Belzarena and Laura Aspirot 2010).

2

The Quality-of-Service can be estimated and specified in terms of metric that are of prime importance to the application under consideration. The metrics can be delay, bandwidth and variation in delay experienced by the receiver, packet loss that can be tolerated and/or number of hops etc (Singh et al 2004). Quality-of-Service has many definitions. According to the QoS forum Quality-of-Service is the ability of a network element to have some level of assurance that its traffic and service requirements can be satisfied (Johnson 1999). QoS based routing is defined as ‘A routing mechanism under which paths for flows are determined based on some knowledge of resources availability in the network as the QoS requirements of the flows’ (Crawley et al 1998). QoS routing is the most significant and complex functional element in the network to provide quality assurances and involves two concepts, namely, Routing information i.e. information about the topology and the link states of the network and Routing algorithm i.e. the algorithm used to find a feasible path for a new connection between source and destination based on the routing information. Routing becomes more difficult when these additional requirements of QoS have to be met. As a result, QoS routing has been the topic of many researchers for quite some time now and there is a considerable effort going on currently to provide QoS. Collection and measurement of network state information and computation of routes based on the information collected are the two important issues. Metric selection is very important since the metric must represent the basic network properties of interest (Crawley et al 1998). Computation complexity must be considered, which means path computation based on a metric or a combination of metrics must not be too complex. One important issue is how often routing information is exchanged between the routers. QoS based routing needs to exchange more information than best-

3

effort routing. A related problem is how to maintain the information collected. QoS based routing is expected to be scalable with the number of nodes and links in the network increasing the complexity of path computation and the information exchanged need to be maintained very effectively. QoS metrics are broadly divided into three different categories namely additive, multiplicative and concave metrics. Additive metric is the summation of all links constituting the path e.g. delay, hop-count, delay variance, cost (Abdelhamid Mellout et al 2009, Yu Wang et al 2008, Wills 2005, Shuchitfa Upadhyaya and Gayathri Dhingra 2010, Liu et al 2005, Therence Houngbadji and Samuel Pierre 2010, Leela et al 2010). Multiplicative metric is the product of all links constituting the path. Reliability (1-loss rate) is an example of multiplicative metric. If an edge weight represents the reliability of the edge, the corresponding path weight is the product of the weight associated with the edges on the path. Since the logarithm of the product of N positive numbers is the sum of the logarithm of the N positive numbers. Hence, QoS metric such as reliability is known as additive metric i.e. multiplicative metric can be converted into additive metric (Sobrinho 2002, Sameer Qazi and Tim Moors 2010). Another kind of QoS metric is known as concave (bottleneck) metric where the corresponding weight of a path is the smallest of the weight of the edges on the path e.g. bandwidth i.e. consider sub graphs with only those edges whose weights are greater than or equal to a particular chosen value (Mingozzi et al 2009, Yu Wang et al 2008). The concave metric of a path is the maximum or the minimum of the metric over all the links in the path. This metric is usually dealt with a preprocessing step called topology filtering, wherein all the links that do not satisfy the constraint are pruned and not considered further in the path selection process. The metrics considered should be orthogonal to each other so that there is no redundant information among the metrics (Zheng Wang and Crowcroft 1996, Li 2006).

4

The QoS routing problem with a single metric can be solved in polynomial time such as the widest path or least delay path, or least cost path problem etc. However, multi-constrained QoS routing problems where more than one additive parameter is involved, such as least delay and cost are intractable (Kwei-Jay Lin et al 2010, Eiji Oki and Ayako Iwaki 2010, Hua Wang et al 2009, Kuipers and Mieghem 2005, Ghosh et al 2001, Ronghui Hou et al 2009, Korkmaz et al 2004). QoS Architecture consists of two major components namely QoS Routing protocols and QoS Algorithms. Routing Protocols need to capture the network state information and disseminate it throughout the network, while routing algorithms use this information to compute appropriate paths. QoS based routing needs to take into account both the application requirements and the availability of network resources. QoS Routing has many challenging issues compared with best-effort routing. Scalable dissemination of dynamic information and computation of constrained paths are challenging issues. In case of an additive measure it is equal to the sum of the corresponding weights of the links along that path. For a concave measure, the QoS value of a path is minimum (or maximum) link weight along that path. In general, concave measures can be easily dealt with by requested QoS constraints and only additive measures cause more difficulties. Hence, without loss of generality, only additive measures are considered in this dissertation. 1.2

MOTIVATION The main purpose of this research work is to find feasible paths

between a source and destination with additive multiple constraints. A difficulty in Multi Constrained Path (MCP) problem is that it is intractable which means that the time required to solve, cannot be upper bounded by polynomial function (Liu et al 2005, Xiao et al 2006, Sen et al 2003, De Neve and Van Mieghem 2000).

5

Due to its increasing importance, this problem has been studied by many researchers. Solutions for MCP problems can be classified into two broad classes namely approximation schemes and heuristic algorithms. An approximation scheme guarantees that the computed path is a specified predefined factor of optimal solution. Heuristic algorithms are normally simple without providing a priori theoretical guarantees of the computed path. Several approaches have been carried out to address the Multi Constrained Path (MCP) problem (Xue et al 2007, Mieghem and Kuipers 2004, Wang Ping et al 2008). Major limitations of these approaches are their inability to find the solution in linear time (Impagliazzo et al 2001) and several works attempted only two or less constraints which are relatively simple. Several Quality-of-Service routing algorithms are proposed (Yuan 2002, Xue et al 2007, Xue Guoliang and Weiyi Zhang 2007, Xue Guoliang 2000, Lorenz and Raz 2001). Yuan (2002) algorithm does not guarantee to return the path if every path weight is not more than (1- ) W, where

is

approximation factor. K-approximation algorithm has high execution time and fails to return the path especially if the constraints are tight (Xue et al 2007). Xue Guoliang and Weiyi Zhang (2007) proposed Greedy algorithm uses absolute path length while searching for feasible path. Because of this, possibility of finding more number of better feasible paths has become very much limited and thereby it affects the performance guarantee in terms of path length and execution time (Xue Guoliang 2000). Greedy algorithms fail to produce the optimal solution because they usually do not operate exhaustively on all the data and may even produce the unique worst possible solution. They can make commitment to certain choices too early that prevent them from finding the best overall solution (Jorgen et al 2004).

6

This motivates to alleviate the shortcoming in the above method, two different categories of algorithms were developed i.e. in the first category a protocol called Optimized Multi Constrained Routing (OMCR) and in the second category two different algorithms to address Multi Constraint Path problem in various application requirements namely Multi Constrained Path algorithm version 3 (MCPv3) and Delay Coerced Multi Constrained Routing (DCMCR) were developed. Here a range of upper and lower bound values used are in contrary to absolute path weight so that more number of feasible paths is found. Better performance guarantee has been achieved by selecting appropriate testing techniques and approximation factor. It is also found that feasible paths retrieved in linear time irrespective of the size of the network. MCPv3 uses all constraints equally to find the feasible path between the given source and destination. In DCMCR, one constraint is coerced and the remaining constraints are approximated. This algorithm is useful where one constraint has to be strictly followed i.e. in strict tightconstraint applications. Again DCMCR is compared with MCPv3 and it is found that DCMCR is useful where one constraint bound is to be strictly implemented. QoS architecture consists of two major components namely QoS protocol and QoS algorithms. Routing protocols need to capture the network state information and disseminate it throughout the network, while routing algorithm uses this information to compute appropriate paths. Both are equally important to implement successful QoS routing. Routing dynamics is considered to be a difficult issue to resolve i.e. QoS routing protocol consists of all the action that inform individual nodes with a consistent and updated view of the network. In this dissertation, convergence time, message overhead in terms of ‘Number of Messages’ and ‘Number of Operations’ for link and node failures are discussed.

7

The algorithms have high overhead in terms of number of packets (Zhenjiang Li 2007, Li 2006). The total ‘number of message’ exchanged is quite high and that in turn increases ‘Convergence time’. This motivated to propose an algorithm Optimized Multi Constrained Routing (OMCR), which addresses these issues effectively. Convergence time is reduced by addressing ‘count-to-infinity’ effectively i.e. the update messages are to be sent definite number of times so that formation of loops can be avoided and addressing optimal sub structure property. Moreover, OMCR maintains shortest feasible path for each destination and hence the multi constrained path problem is efficiently dealt with. Success Rate of OMCR is found to be better by comparing with distributed algorithms (Zhenjiang Li 2007, Li 2006, Kevin 2007) and centralized schemes proposed by Jaffe (1996) and Korkmaz et al (2003). Other parameters such as link failure, node failure, packet overhead and convergence time were compared and found to be outperforming. Hence, the need of this research is substantiated to achieve the following: To find a path between source and destination node pair that satisfies two or more additive QoS constraints. To propose hop-by-hop connectionless QoS routing algorithms for Internet Protocol (IP). To find multi constrained path solutions with performance guarantee, less running time, high success ratio, better path length and improved scalability. This thesis emphasizes the importance of finding feasible paths between a source and destination and proposes solutions to achieve the following:

8

Better quality paths Improved success ratio Better convergence time in case of network failure Better running time in computing feasible paths Reduced overhead by concentrating on number of messages exchanged Improved scalability This research concentrates only on additive constrained QoS issues such as delay, variance of delay and hops count and does not concentrate on multiplicative and concave metrics.

Multiplicative metrics e.g. packet loss can be converted to additive metrics and could be treated same as that of additive metric. In concave metric bottleneck weight of a path is the smallest weight of the edges on the path. e.g. bandwidth and throughput. This is usually dealt with a preprocessing step called topology filtering wherein all the links that do not satisfy the constraint are pruned. Network throughput is not considered as it belongs to concave metric.

To assess the performance of a protocol convergence time, volume of overhead message and success ratio play an important role. Convergence time deals with how quickly the network brings back to normal operating condition in case of a failure. It is an important parameter to be considered in measuring the performance of the protocol. Convergence time is important whenever the topology changes. i.e. when a node or link failure occurs the network should recover as quickly as possible. The link and node information have to

9

propagate the entire network and each node has to reflect the dynamics of the topology.

Volume of overhead messages should be less so that the control packets will not consume large bandwidth. This enables the network to send the data packets more effectively. Frequent exchange of overhead message may not be too good for any network and this volume should be less. The message overhead should be as low as possible in case of node/link failures. So, many packets may occupy more bandwidth and hence it may affect the performance. Hence, message overhead is considered. Success ratio normally deals with how effectively the feasible paths between the source and destination are calculated. High success ratio indicates the efficiency of the protocol in finding the feasible paths. It has been found from literature survey of earlier works done in this area, the above stated metrics are playing an important role in judging the performance. Hence these parameters are selected. 1.3

CONTRIBUTIONS A summary of contributions from the above perspective is as

follows. In this dissertation, three different algorithms are proposed to compute feasible path(s) subject to multi constraints. The proposed protocol OMCR performs connectionless, hop-by-hop Internet Protocol (IP) routing and need not remember the global state of the network. By using the vector transform method the volume of update message is reduced significantly and using effective count-to-infinity, formation of loops is reduced. Nodes are making decision independently and able to manage the dynamic nature of the network swiftly.

10

Multi Constrained Path version 3 (MCPv3) is the second algorithm proposed to deal with multi constrained path problem. MCPv3 computes paths by approximating all constraints. MCPv3 finds a (1+ ) approximation to the optimal solution by choosing a suitable approximation factor . Various experiments are conducted to analyze the performance of the proposed algorithm. Delay Coerced Multi Constrained Routing (DCMCR) is a (1+ ) (K-1) approximate algorithm with K 2 additive constraints and may be treated as a variant of MCPv3 and used where one constraint is to be strictly implemented. Experimental validation of DCMCR reveals that the proposed algorithm performs better to achieve relatively less running time and delivers good results in tight constraint scenario. 1.4

THESIS OUTLINE The remaining of the thesis contains the following chapters.

Chapter 2 formally discusses the background and related work. A concise description of various QoS routing methodologies is provided. The limitation of existing routing schemes is mentioned. Various QoS routing algorithms proposed in the literature suffer from high running time, lack of better quality paths, poor success ratio and scalability. So there is always a necessity to address these issues to improve the overall performance. To address the above mentioned issues, a distributed protocol OMCR is proposed in chapter 3. This protocol returns feasible solution under multiple constraints. Experimental evaluation is carried out to analyze the performance of the proposed scheme. In chapter 4, a multi constraint QoS routing algorithm MCPv3 is proposed. This algorithm is compared with its peers and experimental

11

evaluations demonstrate that the proposed algorithm outperforms in terms of running time, path quality and scalability. Another algorithm DCMCR which is a modification of MCPv3 is proposed in chapter 5 where one constraint is coerced and remaining constraints are approximated. If the number of constraints is reduced to two, this algorithm behaves like delay constrained least cost schemes. Simulations are carried out on different scenario to analyze the performance. Finally, conclusions of the entire research work and a few directions for future research are presented in chapter 6.