4.1 Introduction

The setting up of LANs and WANs paved the way for Intranets. The Internet emerged as the largest WAN. Intranets were used for the client–server type of applications where data was sent from the client to the server over the network. The server processed the data and sent back the results to the client on the network. With the Internet came applications such as email (SMTP), file transfer (FTP), remote login (telnet), and web access (HTTP), which supported the web‐based applications in which the client terminal was able to use the standard web browser to view or request applications. The initial applications planned for the networks were not bandwidth hungry.

The emergence of huge data crunching and analysis applications such as data mining, simulations, modeling, analysis, and visualization required tremendous processing capabilities supported by grid computing and supercomputing. Although these processor‐hungry applications required a huge amount of data to be transmitted from the client to the servers for their processing, once the data was transmitted from the client to the grid or the cluster, the processor became busy processing it and then sent back the results to the clients. All these applications had different types of data transmission pattern over the network. The pattern varied from a small amount of data transmission occasionally over the network to a huge amount of bursty traffic over the network. Still, none of these was affected much by delay in data transmission. They were all dependent on accuracy of the data transmission without any significant consideration of the delay in transmission. These early‐day applications were affected if there was a bit error or a packet loss that was to be detected and retransmitted. Moreover, these applications were not affected if the packet reached the destination with a considerable amount of delay or if the packet did not reach the destination in the same sequence in which it was sent because the packet was reassembled back as per the sequence number at the destination. Characteristics such as these also led to categorization of this traffic type as ‘elastic traffic’ [1].

The emergence of real‐time applications changed the requirement scenarios. Some of the real‐time applications are Voiceover IP (VoIP), live webcasting, video conferencing, tele conferencing, and Internet telephony. The real‐time applications were critical to the delay in data transmission and the sequence of arrival of the packets at the destination. However, they were tolerant to bit errors, packet losses, and unordered delivery of packets. Low bandwidth or fluctuating bandwidth affects real‐time applications. Still, there are applications such as interactive computing and computer games that are delay sensitive as well as error sensitive. Although real‐time applications may require transmission of a huge amount of data across the network, the transmission cannot be done in a bursty mode but has to be done at a constant rate over a period of time. Reduction below the minimum required bandwidth of the real‐time application leads to call drop, freezing, jitter, and hangs. These requirements led to categorization of this traffic type as ‘inelastic traffic’. As real‐time applications are transmitted over the TCP/IP network, they are dependent on the underlying capabilities of the IP network for assured minimum bandwidth.

Quality of service (QoS) [2, 3] is a parameter for standardizing the performance of a network in terms of the assurance and level of the services it offers. The QoS is a parameter of significance in multimedia streaming applications. It guarantees a certain level of performance of the data flow over the network by using specific data transmission techniques and protocols that enable the network to deliver satisfactory prioritization, bandwidth, and performance. A network can be divided into certain paths that provide QoS as well as satisfying QoS criteria. Thus, in order to satisfy QoS constraints, it is essential for the underlying protocol to determine the path that satisfies the QoS parameters. QoS requires prioritization of the network traffic into various categories based on its priority. The network packets have to be prioritized according to the urgency of their delivery to the destination. Generally, all packets belonging to a certain application are given the same priority. QoS is of importance in those networks where the network bandwidth is not sufficient to cater for all applications simultaneously. If sufficient bandwidth was available with the network, each application would have received its share of bandwidth on an ‘as per requirement’ basis without affecting the performance of other applications using the bandwidth at the same time. But generally bandwidth is a constrained resource that is not sufficient to meet the performance parameters of all the applications together and has to be shared among applications. QoS prioritizes the usage of this bandwidth among various applications.

A network is said to support QoS if it has the capability of treating different packets differently. QoS technology has enabled service providers to support different levels of service for different customers, thereby capacitating them with the option to provide better levels of paid services to some customers than to others. For example, some groups of customers may be concerned with a service that guarantees packet delivery, even if that means paying a higher price for these services, while others may just as well be satisfied with relatively less reliable data transfer by paying less for their subscribed services. Networks that transport multimedia traffic, i.e. voice, data, and video, need differential treatments to different packets; while voice traffic is highly sensitive to time delay and the order of delivery of packets, data traffic is relatively less sensitive to these, and video conferencing traffic requires a dedicated connection for a fixed amount of time for the real‐time, orderly delivery of packets [4].

Typical QoS‐routing‐based performance metrics [5] are bandwidth, delay, and throughput. While some applications require bandwidth guarantees, some others mandate the satisfiability of strict end‐to‐end delays, and others still require a high throughput, or a combination of both of these criteria.

Routing protocols in the pre‐QoS era did not consider QoS requirements of connections (e.g. delay, bandwidth, and throughput). Furthermore, optimization of resource utilization was not a primary goal. As a result, while there were flow requests that were rejected because of non‐availability of sufficient underlying resources, there were some other resources that remained available. To address such deficiencies with conventional routing protocols, QoS routing algorithms were devised that could locate network paths that satisfied QoS requirements, and that made better use of the network [2, 5]. Routing of QoS traffic requires stringent performance guarantees of the QoS metrics, i.e. delay, bandwidth, and throughput over the paths selected by the routing algorithms. Accordingly, whereas the traditional shortest path algorithms, e.g. Dijkstra’s algorithm or the Bellman–Ford algorithm [6], indeed have the potential for selecting a feasible path for routing, QoS routing algorithms must consider multiple QoS and resource utilization constraints, typically making the problem intractable. Thus, QoS routing is different from the routing in traditional circuit‐switched and packet‐switched networks.

In ATM networks, for example, a connection is accepted or not by the connection admission control (CAC), depending on whether or not sufficient resources (e.g. bandwidth) are available. The CAC operates by taking into account factors such as the incoming QoS requests and the available resources in the network. The CAC operates the QoS routing algorithms, which identify whether the different possible candidate paths satisfy the QoS requirements or not. The network architects and the engineers want to choose a routing algorithm that will help the service providers to maximize the network resources (e.g. the amount of bandwidth to be routed) while satisfying the requirements from the customers. Therefore, the design of any good QoS routing algorithm takes into account factors such as satisfying the QoS requirements, optimizing the consumption of the network resources (e.g. buffer space, link bandwidth), and balancing the traffic load across different paths [7]. In addition to these, a good QoS routing algorithm should characterize itself by its ability to adapt to the periodic dynamic behavior of the network [4].

QoS routing can be divided into two entities – QoS routing protocol and QoS routing algorithm. The QoS routing protocol determines the condition of the network in terms of links, nodes, bandwidth, congestion, and delay. The dynamic routing protocols regularly analyze the underlying network to capture the condition of the network on a regular basis to help determine the behaviour of the network. The routing protocol distributes this collected information across the network to various routing nodes. The routing algorithm uses this information provided by the routing protocol to calculate the path by which it should forward the packet in order to satisfy certain parameter criteria to deliver the packet with assured constraints [8].

The QoS criteria may be based on a number of constraints such as bandwidth assurance, buffer usage, priority queuing, CPU usage, loss ratio, and jitter, in addition to the hop count or delay, which are the common criteria for operation of a shortest path routing algorithm. QoS routing is unavoidable for certain applications that are delay sensitive; for example, the packets of a network management system should be given priority over other data packets in a congested network in order to enable the NMS to display the congestion in the network. If the NMS packet is not given priority in the congested network, it will remain queued up in one of the nodes of the congested link, and this will lead to the NMS believing that the link has failed, even though it is operational, or the congestion information will reach the NMS after it has been resolved and this will bring down the reliability of the NMS owing to its non‐real‐time behaviour.

The prime objective of QoS routing is to find a path that has sufficient resources to satisfy the service level constraints imposed on the network by the QoS. The minimum amount of resources should be assured even in the case of some other applications using the network and its resources. Even if another application uses the path already selected by the QoS application, the residual resources should be able to serve the QoS service criteria of the application.

The QoS constraints can be broken down into two categories: (1) link constraints and (2) path constraints [9]. The link constraint refers to the quality of a particular link and its ability to route the traffic so as to satisfy the minimum service criteria. The link constraint is of more importance in a packet switching network where a link is selected for each individual packet by the routing algorithm. Thus, the QoS parameter of the link has to be assured before a packet is placed on it. The link constraint must ensure a minimum level of service assurance across its endpoints, e.g. transmission with an assured maximum delay or assured minimum available bandwidth across it. The path constraint requires minimum service guarantee across the entire path from source to destination. It is of greater significance in the case of point‐to‐point circuit switching networks than the packet switching network. The path has to be carefully selected with the assured QoS, as the same path will be used throughout the transmission and its performance should not degrade beyond the assured level of service during the entire period of connection. In the case of QoS in multicasting, the tree constraint also gains significance. The tree constraint can be assumed to be a modified form of the path constraint. In the case of a tree constraint, the data has to traverse the tree with a minimum assured level of service, e.g. the packet should traverse the entire tree within a specified period so as to enable the source node to broadcast the message within the permissible delay to all the members of the multicast group.

As the QoS is a user‐oriented parameter, it has to be implemented end‐to‐end across a network. Thus, all the intermediate network components between the two endpoints, i.e. end nodes, switches, routers, and gateways, should have the capability of QoS implementation over them and should be capable of guaranteeing the QoS over the packet being processed or passing across it. The intermediate nodes should be capable of segregating the QoS packet from the normal packet before processing it. As the QoS packets may get priority of the network, QoS attacks are also possible by a network flow to get priority over the other packets. To prevent any QoS attack, ‘traffic policing’ [10] is one of the components of the QoS framework. The policing is done at the edge of the network to ensure that only the legitimate traffic is requesting QoS from the network. The packets violating the traffic policy are dropped at the edge. Alternatively, instead of dropping the packet, the packet that is not conforming to the traffic policy may be accepted by the processing node and stored in its buffer for processing with a lesser priority than the QoS packet, and then when processed the undesirable characteristics of the packet are removed before it is sent back to the network. This, referred to as ‘traffic shaping’, can smooth out bursty traffic. Leaky bucket and token bucket are common traffic‐shaping mechanisms. The QoS traffic should be managed by the intermediate nodes to provide fair competition among the flows with equal priority but with minimum assured level of service.

4.2 QoS Measures

QoS is a user‐oriented parameter. While the connectivity and the level of services between the service providers is measured in terms of network performance (NP), QoS measures the level of satisfaction of the user with the performance of all the services provided to her by the network. NP depends on the interconnect network between the service providers and its associated devices and does not rely on the performance of the end terminals and user input/output. The QoS, however, is the delivery of the services at the assured level of satisfaction as offered to the customer or demanded by the customer [11, 12]. In order to measure the level of performance over the assured level of service, the QoS should be quantifiable. The user should be able to define the quality of service in some measurable parameters and not as linguistic adjectives such as excellent, very good, assured, high bandwidth, low delay, or jitter‐free service. The QoS thus converts the quality into measurable parameters, and the parameters are such that they can be understood and measured by the user as well as by the service provider as they are related to user satisfaction.

Although QoS metrics quantify the measurable parameters, it is difficult to list a common set of QoS parameters for all types of application and network. The QoS metrics and their permissible values vary across applications. Thus, most of the QoS measures are defined on an application and network basis and not in general terms. In order to illustrate this, we present different sets of QoS parameters used by various organizations or mentioned in different literature sources. The European Telecommunications Standards Institute (ETSI) defines nine performance parameters to quantify the QoS. These parameters as mentioned by the ETSI are:

• access speed,
• access accuracy,
• access dependability,
• disengagement accuracy,
• disengagement dependability,
• disengagement speed,
• information transfer accuracy,
• information transfer dependability, and
• information transfer speed.

Dependability has been defined as the probability of successful completion of the activity irrespective of any assurance of speed or accuracy.

The critical factors [13] to measure the satisfaction of the user for a multimedia transmission over the Internet can be as follows:

• video rate,
• video smoothness,
• picture detail,
• picture color quality,
• audio quality, and
• audio/video synchronization.

The key indicators [14] of the QoS metrics from a user’s perspective in respect of a mobile network can be as follows:

• Coverage. This indicates the geographical area over which the network can provide its services.
• Accessibility. This describes the ease with which two remote sites connected through the network can communicate with each other by accessing the network. It also indicates the capability of the network to establish communication between the interconnected mobile terminal and the fixed‐line terminal.
• Audio quality. This indicates the ability of the network to maintain voice clarity over a certain period of time on the network with call disruption.

Thus, as the application changes, there is a change in the criteria for the measurement of its satisfiability. However, from a user point of view, a standard metric that can encompass some of the specific metrics across all applications can be defined as a guiding parameter for QoS measurement. A few common QoS measures are as follows:

• bit rate,
• delay,
• packet loss,
• jitters,
• response time,
• cross‐talk and echo levels,
• signal‐to‐noise ratio, and
• grade of service (ratio of lost traffic to offered traffic).

The QoS requirements can be categorized into levels [13] based on user requirements: criticality, cost, security, and reliability. Criticality of the QoS depends on the application being considered, and the measurement parameter varies with application. However, as the criticality of the application varies with the users, so do the metrics for measuring the criticality of the QoS. In a video conferencing environment, a particular user may give more importance to the voice quality, while for another user the video resolution may be more important. Cost is considered as another criterion for measuring the QoS, as the user expects assured level of service in return for the service charges paid. When the service provider charges money for the service to the user, it also assures a minimum level of service. The user should be able to measure whether she is being provided the minimum assured level of service. There can be different charging criteria, such as per usage cost, per unit cost, or per unit of time cost. The QoS should also deal with ensuring the security of the data being delivered. The QoS should not be delivered at the cost of security. The minimum assured security parameters should be in place at all levels when a packet with QoS assurance moves across the network. However, to ensure faster delivery, the security encapsulation of the packet should not be reduced or removed. The delay should not be reduced by decreasing the packet size and processing requirement by stripping the security parameters.

The reliability of a system is the amount of time a system is expected to be operational before it fails. It is different from availability, which is the amount of time a system is operational out of the total specified time. A system going down very frequently for a fraction of a second every hour may be highly available but has very low reliability. Depending on the application, a system may require high availability or high reliability or both, e.g. an airline ticket reservation network requires high availability, while the autopilot of an aircraft requires high reliability. A network controlling a nuclear reactor requires high availability as well as high reliability. Some other reliability‐based parameters that can be used to measure the QoS can be mean time to failure, mean time between failures, or mean time to repair.

The latest network‐related technologies, applications, and products being launched in the market are coming with an assured QoS equivalent to or better than the legacy systems. Service providers have various levels of cost for the same product or service, based on the assured resource availability. It is challenging to make a new technology meet the customer service expectations in terms of quality, availability, and reliability and at the same time enable the network quickly to adapt to the new technology. QoS allows measurement of the changing dynamics of the network and prioritization of traffic flow through it. Thus, QoS is becoming a key factor in the interconnected networks across a large number of service providers to deliver interactive multimedia communication support.

4.3 Differentiated and Integrated Services

Previously, various mechanisms in place to incorporate QoS in a network were not point‐to‐point across the network, as this involved consensus among all intermediate service providers and the devices. Such collaboration could be achieved only with standardization of QoS over an IP network because an IP network does not directly support QoS, rather it offers a best‐effort service. Moreover, QoS‐aware routing protocols were also being designed. An application that requires QoS over the network can attempt to achieve the same in two different ways; it should be able to state its QoS requirements either before initiation of the traffic or on the fly during movement of the data packets in the network. In a similar approach, the International Engineering Task Force (IETF) has defined two models for implementation of QoS – differentiated services and integrated services.

Differentiated services. Differentiated service architecture [15] divides the data flow in the network on the basis of committed performance and provides a separate QoS to each group of the flow. Differentiated service is implementable in IPv4 as well as IPv6 networks, and it uses an 8 bit differentiated service field in the header to assign a priority to the packet and group it in one of the QoS classes in the network. The differentiated service header uses the same eight bits of an IPv4 packet header that were previously kept for type of service (ToS) in bit positions 8 to 15 of the header but were not used. From the eight bits assigned for the differentiated service header, two bits are presently unused. The remaining six bits form the differentiated service code point. Thus, when a packet with a differentiated service header reaches a router, the entries of unused bits are ignored and only the differentiated service code point entries are read to ascertain the level of service assured to the packet. The differentiated service code point occupies bit positions 8 to 13 in the IPv4 header.

The assignment of the QoS priority value in the header is based on the service level agreement (SLA) between the customer and the service provider before generation of QoS‐assured traffic. The customer can be an individual, an organization, or another service provider that has its own differentiated service zone and would be exchanging traffic with this service provider. This enables the network of the service provider to be aware of the level of QoS assured to a particular customer before it starts receiving the data from the customer on its network. Once the service provider enters into an SLA with the customer, the customer marks its packets with its agreed priority value encoded in the form of a bit sequence in the differentiated service header. The header value may change for various traffic flows from the same customer, as the SLA might be different for different types of application from the same customer. As the priority level is decided on the basis of the value in the eight bits of the differentiated header, a number of customers or their specific applications may be assigned the same priority level. All the data packets that are assigned the same priority level are ‘aggregated’ together, even though they may belong to different customers or applications.

The differentiated service has to be implemented on each of the intermediate nodes in the network by configuring suitable ingress, egress, processing, and buffering policies, as each of them has to conform to the assured level of service. This also helps in distributing QoS assurance across the network, and each packet can be dealt with separately by the intermediate node with the assured level of service. However, as all the intermediate nodes in a huge network may not be under one administrative control, the differentiated services are generally restricted within a portion of the network that is under one administrative control or within even bigger portions of the network that may be under various ISPs each forming its own differentiated service domain, and the ISPs agree on providing QoS among the differentiated service domains of each other. The individual differentiated service domain of a single service provider or a combination of a number of differentiated service domains with mutual agreement among the service providers should be continuous in nature because, if the traffic has to go out of the domain, even if to a single routing node that is not configured for the differentiated services or does not recognize or accept the differentiated services of the service provider, it may hold or delay the packet beyond the service level agreed by the service provider and thus reduce the end‐to‐end QoS of the entire flow below acceptable limits.

An SLA may define the service parameters in qualitative terms or quantitative terms [15]. In the case of quantitatively defining the parameters, it is easy to measure the parameter and compare its compliance with the assured level. Some of the parameters defined in quantitative terms can be 2 Mbps bandwidth, 120 ms latency, 5% packet drop, <6 hops, or 99.8% availability. The parameters may be expressed qualitatively using linguistic expressions such as high bandwidth utilization, low jitter, and higher reliability. Although it is difficult to ensure the compliance of such an SLA because it is difficult to measure the service level, in such cases the service level of normal traffic, i.e. without any QoS based on SLAs but with a best‐effort service, is taken as the base reference to quantify high or low. An SLA can also have a mix of qualitative and quantitative representation of the different service levels.

There are two categories of routers in a service provider network – the interior routers and the boundary routers, as depicted in Figure 4.1.

Interior routers are connected only to those routers in the network that belong to the same service provider. When a service provider enters into an SLA with one or more customers, it has to configure all the routers in its network to make them aware of the QoS. In the case of an internal router, applying the QoS is simple as it receives packets that have come from some other router of the same service provider and thus have the assured level of service prior to reaching the entry point of this router. Also, once the router forwards the packet to another router within the same service provider network, that router too will ensure delivery of the assured level of service. Thus, this intermediate router just has to follow the differentiated service specifications across its input and output and treat the packet in accordance with its differentiated header value. This information available with the router on the type of treatment to be given to the data packet is also known as ‘per hop behavior’ (PHB). The internal router should process QoS packets with a priority over normal packets. This can be done by allowing them assured service along with empty or shorter queues. A shorter queue will reduce the latency, delay, jitter, and packet loss. This will ensure the assured level of service across the network of the service provider for the data packet.

Boundary routers are connected to at least one router that is not a part of the service provider network. These routers are responsible for regulating the traffic entering the differentiated service zone of the service provider. Traffic regulation consists of five processes [15]: classification, metering, marking, shaping, and dropping. During classification, the packet is distinguished into various classes based on the differentiated service header. However, the classifier may also take into consideration the payload and any other parameter from the packet header for classifying the traffic. Metering is the process of measuring at least those packet parameters that have an assured level of service guarantee so as to ensure compliance of SLA. Marking is the process of marking or changing the value of the differentiated service header. This is required when the performance parameter of a packet falls below the assured level or when a packet enters the differentiated service zone of one service provider from the differentiated service zone of another service provider. If the performance parameter of a packet falls below the assured level, the priority of the packet may be raised further to compensate for the loss or it may be changed to lowest‐priority best‐effort forwarding so as not to affect the performance of the other packets maintaining the performance parameter in their present flow. Shaping is done to make the packet conform to the traffic rate assured to the packet. It smooths out bursty traffic to a constant flow rate of traffic. Boundary routers may also drop those packets that do not meet the differentiated service specifications or are not of assured priority during congestion in link or buffer saturation.

Advantages of differentiated services are as follows:

• The routers can perform their primary job of routing without being affected by differentiated services, as the major processing related to differentiated services takes place at the boundary of the differentiated service zone.
• End‐to‐end connection negotiation for an assured level of service is not required.
• They are much easier to implement, and they work in a distributed manner.
• The QoS configurations are made in the router and are hence static. Thus, an application does not require any special configuration per flow to be sought for assured QoS.

Disadvantages of the differentiated services are as follows:

• As each router deals with the packet separately, it becomes difficult to predict the level of service that will be offered by the router.
• An initiator may tag a packet with high priority to get preference, even though it does not qualify for the same.

Integrated services. Integrated services provide end‐to‐end signaling to give a solution that meets most of the QoS requirements. They use Resource Reservation Protocol (RSVP) to reserve the resources to deliver the assured QoS to each ‘flow’ [15]. Flow is a unidirectional data stream from an application to one or more recipients. A flow is uniquely identified by five tuples: source IP address, source port number, destination IP address, destination port number, and transport protocol. A flow comprises a number of data packets generated from the same application, and all the packets in a flow have the same QoS requirement.

In a legacy IP network, routers attempt to provide the best‐effort service based on the routing algorithm running in it and the buffer capacity of the router. The routing algorithm attempts to find the least‐cost path from source to destination. A dynamic routing algorithm also finds alternative paths for forwarding data traffic in the case of congestion. However, no preferential treatment is given to a packet in the case of congestion. The router also drops any packet arriving at its interface if the buffer of the router is full. However, these attributes of IP routing do not suit implementation of QoS in the network. Integrated services manage routing and congestion control in a different manner to ensure assured level of service to the network flow. In an integrated service, all the routers collectively assure the availability of resources to process the packets in the flow within the assured level of service, and only thereafter is the flow accepted by the network. The routing algorithms consider QoS parameters in addition to the minimum cost to determine the next exit link to forward the packet. The buffering and packet drop policy of the routers are modified, as otherwise the FIFO buffering and processing policy will lead to treating all the packets with the same priority. Therefore, priority queues are created and assigned to QoS traffic, and a policy of dropping an existing non‐QoS data packet from the buffer is used in order to admit a packet with an assured QoS in the buffer even when the buffer is full.

In a router, the flows are categorized into various classes [15] to decide on their forwarding mechanism. There can be a single flow categorized into a particular class, or there can be a number of flows from one or more applications or customers categorized into a particular class. The class of the flow is selected on the basis of the five tuples in the IP header. All the flows and its packets belonging to a particular class are given similar resource allocation and preferential queue allocation across the network. A packet scheduler in the router is assigned the activity of managing the queues. The router may have one or more queues. The packet scheduler, based on the class of the data packet, decides on the ordering of the data packets in the queue and their processing and forwarding. It is also responsible for deciding about dropping packets from the buffer, if required, to accommodate packets with assured level of service. When a new flow is to be accepted for transmission, the RSVP invokes the router to check whether sufficient resources are available to process the flow as per the assured QoS. The router has to assure availability of resources at the assured QoS to this new flow after taking into consideration the existing flows with the router as well as the other normal traffic being processed by the router. As RSVP gets similar assurance from all routers and end systems along the path of the flow, it reserves these assured resources for the flow.

There are two categories of integrated services that can be requested through RSVP: guaranteed service and controlled load service. There can be various levels of services within these two categories, and the specific amount of service requested within a category by a flow is based on certain parameter values that are known as ‘traffic specifications’. Guaranteed service provides assurances such as a strict upper bound on the end‐to‐end delay, assured bandwidth for the traffic that conforms to the reserved specification, and assured queuing of packets in intermediate routers leading to zero packet loss due to buffer overflow. Thus, a guaranteed service is the requirement for a network supporting a hard real‐time system as it has a strict deadline. The controlled load service is better than the best‐effort service when the network is not under heavy load. The controlled load service does not provide an upper bound on the queuing delays or queuing loss. However, the service attempts to provide a high QoS by trying to minimize the packet drops and waiting time at buffers [1, 15]. It is better than a best‐effort service because, during congestion, a best‐effort service may fail to deliver the packet, but in the case of a controlled load service the network keeps aside a certain minimum amount of resources to process the flow even in the case of congestion. A controlled load type of service is generally used in the case of video‐streaming‐type applications, which are adaptive in nature and can tolerate a few packet drops and small delays.

4.4 QoS Routing Algorithms

Several QoS‐based path selection algorithms [16], such as the shortest widest path (SWP) [17], widest shortest path [2], and utilization‐based algorithms, have been proposed in the literature, and comparisons of their performance have also been made [5]. An overview of some of these algorithms is presented here.

SWP Algorithm

In distance vector routing [3], each node in the network is aware of the link costs of its immediate neighbors. When this information is exchanged by each of the nodes with its immediate neighbors, all the nodes are made aware of the distances to the rest of the nodes. When the algorithm stabilizes, upon updating the routing tables of each of the nodes, each node knows the costs and the next‐hop nodes for the rest of the nodes in the network.

In the case of linkstate routing [3], each node is made aware of the link state information (i.e. whether the links to its neighbors are active or dead and how much the cost of each link is) by a procedure called flooding, so that each of the nodes can find the shortest paths to all the remaining nodes in the network. Upon stabilization of the algorithm, after flooding has disseminated all the link state information to all the nodes in the network, each node is capable of calculating the shortest path to the remaining nodes in the network. The algorithm maintains two lists for a node, called the tentative and the confirmed lists, each of which contains entries that store information about the destination node, the cost to reach the neighbor of the node and the next hop of that node. The entries labeled tentative are those that are being processed but are not yet confirmed to belong to the shortest path routes.

In simplified terms, the link‐state‐based SWP algorithm can be stated in the following manner:

1. Firstly, from the list of tentatively labeled nodes, find the nodes with the maximum width.
2. If there are several such nodes satisfying step 1, select the node with the minimum length path, and label it as confirmed.
3. Finally, update the maximum width (or the link residual capacity) and the length for the shortest widest path for the nodes labeled as confirmed.

The SWP algorithm [17] has the following properties:

1. The time complexity of the SWP algorithm is proportional to that of the corresponding shortest path algorithm.
2. The SWP algorithm can be considered as a general case of the shortest path algorithm when all links are considered to have different link capacities. In other words, if all link capacities are considered to be the same, the shortest path algorithm can be viewed as a particular case of the SWP algorithm.
3. A path’s width is decided by the bottleneck link, i.e. the link in a path with the minimum residual bandwidth.
4. The paths computed using SWP algorithms do not form a loop. This property of SWP is analytically appealing and proven.

WSP Algorithm

The WSP algorithm was proposed by Guerin et al. [2]. Unlike the SWP algorithm, WSP first attempts to compute the shortest path. If there exists more than one alternative, the algorithm chooses the one with the largest residual bandwidth in the bottleneck link (i.e. the widest path) [4]. If there is still a tie with one or more such path(s), one of the prospective paths is randomly chosen [5].

This process can be described in four principal steps [2, 5, 16, 18] stated below:

1. Step 1. For a route request with b units of bandwidth, scan and discard all links, e, whose residual bandwidth r_j(e) < b.
2. Step 2. Apply a suitable shortest path algorithm (e.g. Dijkstra’s), and compute the shortest path. If all paths have the same edge lengths (costs), then select the path with the least number of hops.
3. Step 3. If step 2 results in more than one choice, select the widest path with the largest residual bandwidth.
4. Step 4. If it turns out that there is more than one path with the same widest path, randomly select one path from among the available alternatives.

The major limitation of WSP lies principally in the fact that the algorithm is essentially a shortest path greedy algorithm. The notion of widest paths arises only when there are multiple shortest paths. On the other hand, as the SWP algorithm first selects the path that has the largest residual bandwidth, it can select very long paths to satisfy its requirement. The choice of the algorithm should depend on the network environment and requirements. In a meshed networking with intricately connected equal‐length paths, WSP could be a better alternative than SWP. On the other hand, if (i) there is a general non‐meshed (or even small) network, where propagation delays are small, or (ii) network resources are inexpensive, SWP could be a better alternative.

The difference between WSP and SWP clearly lies in the fact that, whereas WSP attributes higher priority to minimize the distance or the hop count, SWP places more emphasis on balancing network loads.

SELA Routing Algorithm

The stochastic estimator learning automata (SELA) routing scheme is a QoS‐based scheme that was proposed by Vasilakos et al. [7] for use in CAC problems in ATM networks. It uses the reinforcement learning scheme called SELA for optimizing the network revenue while ensuring that the QoS requirements (e.g. cell loss ratio, maximum cell transfer delay, and cell delay variation) for the different connections are satisfied in the ATM networks.

In SELA routing, an automaton operates at each source node. The purpose of the automaton is to choose one of the different possible paths, represented as the different actions of the learning automata (LA) operating at the source node, for routing requests between pairs of source and destination nodes. The SELA algorithm maintains a table containing the current link utilizations for the entire network. This table helps to compute the feedback of SELA to the different possible actions. The algorithm reserves trunks for network conditions where uncontrolled alternative path routing can lead to unacceptably increased rejections of connection setup requests [7, 19]. As a result, the algorithm tries to improve its QoS performance by discouraging the loading of the congested links, unless the link happens to be in the shortest path (in terms of the number of hops) between the source and the destination nodes.

The algorithm [7] defines a parameter ρ_TRT that represents a predefined route utilization threshold that any route can have. The SELA algorithm routes a request through an overutilized path only if the maximum expected utilization that the links comprising a particular route can assume () exceeds ρ_TRT, but that overutilized path happens to be a shortest distance path. If the path is not a shortest distance path, the algorithm looks for an alternative path.

The SELA algorithm utilizes a feedback function b(t) for any link in a set of links comprising a route as follows [7]:

where

is the expected utilization of the ith of the n available link segments comprising any route, and MAX_NO_HOPS is the maximum number of hops that is possible between any pair of source–destination nodes.

The structure of the function b(t) demonstrates that increasing congestion would reduce its value. Similarly, the value of b(t) increases with increasing number of hops in a route, thereby signifying that the algorithm favors minimum‐hop routes [16].

4.5 QoS Unicast Routing Protocols

In a QoS unicast routing [9, 20], the data has to be sent from the source to only one destination through the feasible path that satisfies the QoS constraints. The feasible path is one that minimizes the routing cost across the network. The least cost can be based on any of the normal routing metrics such as hop count, delay, or bandwidth. The QoS constraints can be mapped in terms of link constraints and path constraints. Optimization of link constraints depends on availability of resources in the network, i.e. bandwidth, and availability of resources in the intermediate routing nodes, i.e. size of buffer, queue length, and availability of priority queue. The parameters of concern for the path metrics can be additive in nature along the path, e.g. delay, or can be multiplicative in nature along the path, e.g. packet loss or reliability.

The prime objective of QoS routing is to meet the service level parameter constraints across the network. This is achieved by trying to manage these constraints in each individual link and routing node along the path from source to destination to adhere effectively to the overall transmission constraint. QoS unicast routing may use source‐based routing, distributed routing or hierarchical routing strategy. In source‐based routing the sender computes, before transmitting the packet, the complete or outline path by which the packet should travel. In distributed routing, each intermediate node in the network between source and destination decides on the next link on which the packet should be forwarded. In a hierarchical network, the network is divided into a hierarchical structure forming groups, and the routing decision is made by the group leader or parent node of the tree recursively. A few [21] unicast source routing algorithms are the Wang–Crowcroft algorithm [22], the Ma–Steenkiste algorithm [23], the Chen–Nahrstedt algorithm [24], the Awerbuch et al. algorithm [25], and the Guerin–Orda algorithm [26], and a few unicast distributed routing algorithms are the Wang–Crowcroft algorithm [22], the Salama et al. algorithm [27], the Cidon et al. algorithm [28], and the Shin–Chou algorithm [29]. The commonly used hierarchical routing algorithm is the private network–network interface (PNNI). In all three cases the decision of the routing node is based on the QoS constraints as well as path optimization. When the routing decision is made, a single feasible path may be selected or multiple feasible paths satisfying the QoS constraints may be obtained, of which one is selected based on certain criteria as per the requirements. QoS unicast routing can also be categorized as distance vector routing, where the nodes have information only about their neighbors, or link state routing, where the routing node is aware of the complete network topology.

A QoS unicast routing protocol is broadly classified on the basis of the routing metrics into two categories: link‐constrained routing and link optimization routing. A link optimization routing finds a path from source to destination in which the constraint metrics are satisfied, i.e. the path metrics of the QoS parameter are above the required values if the assured level of service has to be more than the constrained parameter, e.g. bandwidth, and the path metrics of the QoS parameter are below the required value if the assured level of service has to be less than the constrained parameter, e.g. delay. A link optimization routing finds the path that maximizes or minimizes the path constraint from the source to all possible destinations in the network. An example of path optimization routing is Delay‐Constrained Least‐Cost Routing Protocol, and an example of link‐constrained routing is Delay‐Constrained Unicast Routing Protocol.

Delay‐Constrained Unicast Routing (DCUR) Protocol. DCUR is a distributed protocol where each routing node decides only the next‐hop node. The protocol is initiated by the sender, and the path of packet traversal is decided node‐wise as it moves from the source to the destination, i.e. it is a forward propagating protocol [27]. The protocol minimizes the delay as well as the cost of the routing path. If the least‐cost path does not satisfy the delay constraint, the protocol selects the least‐delay path instead of the least‐cost path. This helps to satisfy the QoS constraint by not forwarding the data packet on a path that will exceed the committed parameter constraint and violate the service agreement. In this protocol, each routing node uses cost as well as the delay vector table to decide on the next‐hop path. The routing node first calculates the least‐cost path and uses the same if it satisfies the delay constraint. If the delay constraint is not satisfied by the least‐cost path, the routing node selects the least‐delay path and forwards the packet to the next node by the least‐delay path. An intermediate node can decide only between the following two choices of path – least‐cost path or least‐delay path. The routing node is not capable of selecting an optimum path by minimizing the cost as well as the delay. This has been done to retain the simplicity of the protocol and reduce the computational complexity. The protocol is helpful in communication between nodes in a distributed real‐time application.

A special implementation of the protocol where all the nodes select the least‐cost path satisfying the delay constraint will make this protocol similar to distance vector protocol. However, generally, all the paths may not be selected on the basis only of the least cost or only of the least delay. With either least cost or least delay, looping would not be present as in the case of distance vector routing. But as some of the paths are calculated on the basis of the least‐cost vector and the remainder are calculated on the basis of the least‐delay vector, looping may occur in the protocol. A loop is detected by a node if it receives back a packet that it has already forwarded for the source–destination pair. In such a case it informs the node from which it has immediately received the packet by sending it a ‘remove loop’ message. The ‘remove loop’ message propagates backward till the path recovers from the loop by following a least‐cost path.

As DCUR cannot optimize delay and cost, it fails to select a link that may have a better overall delay as well as cost performance. Hence, the protocol may become very costly owing to the selection of the least‐delay paths only in the case of a strong delay constraint. As the protocol depends on the cost as well as the delay vector routing tables, the accuracy of both tables should be maintained. It also increases the memory and computational requirements. Moreover, it has to keep a record of the packets forwarded along with its source–destination pair so as to initiate or participate in the loop avoidance process.

Delay‐Constrained Least Cost (DCLC) Routing Protocol. DCLC routing protocol [30] is a source‐based routing and overcomes the drawbacks of DCUR routing by optimizing the delay as well as the cost constraint during path selection. The two parameters are negotiated to reduce the overall delay. The protocol works on the assumption that there is a positive delay and a positive cost associated with each link in the network. The QoS puts a constraint on the maximum amount of delay (d) that can be tolerated in the network for a particular source–destination pair. The protocol finds a path with minimum cost, subject to satisfying the delay constraint of less than d between the source–destination pair. Each node keeps a cost and a delay vector for the best next‐hop node for any destination in the network. The source node sends a control message for construction of a delay‐constrained path. Any node can select either the least‐cost path or the least‐delay path. However, the least‐cost path has priority over the least‐delay path as long as the delay constraint is not violated. Thus, the protocol acts as a multiconstraint path problem that is bounded by delay constraint, and the path cost has to be optimized.

4.6 QoS Multicast Routing Protocols

QoS multicast routing protocols are required to provide a path from a source to many destinations under constrained parameters as defined in the SLA. Multicast QoS routing is required for applications that require group communication with an assured level of service in terms of certain QoS parameters. A few examples of such services are applying software upgrades in a time‐bound manner to critical application, multiparty tele conferencing with assured maximum permissible delay in transmission, multilocation video conferencing with assured minimum bandwidth, jitter‐free online diagnostics, and hard real‐time image and video transmission for tele medicine and tele surgery. The nodes of the multicasting group can be confined within the LAN or can be spread across the WAN. In QoS multicast routing, the source node has to find the best feasible path from itself to all the nodes in the multicast group that satisfies the QoS constraints. The multicast path is in the form of a tree connecting the source to all the other multicast group nodes. In multicast QoS routing, the entire tree has to be optimized, unlike unicast QoS routing in which a single optimized path is calculated. Thus, the multicast routing protocol has to build a minimum cost distribution tree without violating the QoS constraints through which the data packets will be sent to the multicast group nodes.

The essential features [31] of a robust and scalable multicast routing protocol are as follows:

• The protocol should optimize between routing overhead and routing performance.
• Traffic should not be forwarded through the congested network areas.
• The protocol should attempt to minimize the state information required to be stored at each node.
• The routing protocol should not only adapt to the changing network load but also converge quickly in the case of changing load or topology.
• The protocol should support high scalability of the network.
• Decentralize the computation over several nodes for faster decision‐making and prevent a single point of failure.
• It should enhance the probability of successfully locating a path from source to destination.
• The protocol should minimize the cost of the selected path as well as minimize the delay over the selected path.

Based on various properties, multicast groups have been differentiated [32] into the following:

• dense groups versus sparse groups, based on the number of multicast group members per link;
• open groups versus closed groups, based on the permission available to a sender to transmit a message to a multicast group even if it is not a member of the group or only if it is a member of the group;
• permanent versus transient groups, based on the duration of existence of the multicast group;
• static groups versus dynamic groups, based on the nature of membership of the nodes in the multicast group and their permission to join or leave a group and the adaptability of the group to accept them on joining and delete them on leaving the group.

A multicast routing protocol can be static or dynamic. In a static multicast routing protocol, all the members of the multicast group must be known to the protocol, and thereafter the multicast tree is constructed. Dynamic multicast routing protocol allows the nodes to join the multicast group while the tree is being formed. The tree is not entirely reconstructed for every node joining the multicast group, but an attempt is made to connect the newly joined member to an existing node of the multicast group. The choice of the routing protocol to be used is also dependent on the type of application using the multicast routing protocol, e.g. a dynamic protocol is preferred for an application such as online live radio, video streaming, and webcasting, where users keep joining and leaving the multicast group.

The following stepwise process [32] is followed for setting up a multicast group:

1. Creation of a multicast group. A unique address is provided to each group to avoid any clash of data between groups. An address assigned permanently is known as a static address, whereas an address assigned temporarily to the group is considered to be dynamic. Generally, static addresses are assigned to permanent multicast groups and dynamic addresses are assigned to transient multicast groups. This kind of matching of type of multicast group and type of address avoids insecure or unnecessary communication.
2. Creation of a multicast QoS tree. The next phase in multicast routing is the creation of a tree from the source covering all the receivers and reserving resources on the tree. The tree structure has been adopted as it allows parallel transmission down to the various nodes. The formulated tree should also satisfy the QoS requirements. A tree that satisfies the QoS requirements best is selected.
3. Data transmission. After creation of the multicast group and creation of the multicast QoS tree, the following tasks [32] are performed during data transmission:
   • Group dynamics. The network should be able to detect each member joining or leaving the multicast group during the session’s lifetime. Once the members have been detected, wasteful transmission of data can be stopped to members who have left the group and the data can be forwarded to newly joined group members.
   • Network dynamics. The network should be able to detect node and link failures and restore the tree, bypassing faulty nodes with assured QoS.
   • Transmission problems. Faulty packet transmissions are identified. Some control activities are necessary to overcome these transmission problems.
   • Competition among senders. Resource contention occurs when a number of senders have to send their data along the same tree. A session control mechanism is required to prevent the service falling below QoS in such cases owing to unavailability of sufficient resources that can be reserved. Such a session control arbitrates transmission among senders.

Multicast routing protocols can be categorized into three main approaches: source‐based protocols, center‐based protocols, and hybrid protocols [32, 33]. The source‐based approach creates a shortest path tree routed at the source, and each branch of the tree represents the shortest path from the source to each receiver. Owing to QoS constraints, the shortest path is the shortest delay path. However, source‐based trees become too complex as the size of the network scales because a tree has to be created from each individual source spanning all the receivers. A few examples of source‐based multicasting routing protocols are Distance Vector Multicast Routing Protocol (DVMRP), Protocol‐Independent Multicasting Dense Mode (PIM‐dense), Multicast Open Shortest Path First (MOSPF), and Explicitly Requested Single‐Source Multicast (EXPRESS). The center‐based protocol is also known as the shared‐tree protocol, and it constructs a multicast tree spanning all the members and is rooted at a center node. The center‐based protocol is highly scalable. When a node wants to send some data to all other nodes in the multicast group through the center‐based protocol, it sends the data packets to the center. The data packet traversing from the source node to the center node passes through the other multicast group receiver nodes in the path from the source to the receiver. Once the data packet reaches the receiver, it is sent to those nodes along the tree that have not received the data packet earlier. Core‐Based Tree (CBT) and PIM Sparse Mode (PIM‐SM) are core‐based multicast tree protocols. A hybrid protocol gives the receiver flexibility to switch between the center‐based protocol and source‐based protocols, and an example of this is Multicast Internet Protocol (MIP). The overall working of a source‐based protocol and a center‐based protocol is described to give an understanding of the procedure.

DVMRP. The protocol uses a reverse path multicast (RPM) algorithm [33] to build its source‐based tree. In an RPM algorithm, when an intermediate routing node receives a packet, it forwards the packet to the other nodes connected to it only if it has received the packet from a link that is in the shortest path. This way the datagram is forwarded across the entire network from the source. A leaf node is one that does not have any multicast group nodes attached to it. When a leaf node receives the message, it sends a ‘prune’ message back along the path from which the packet was received. The ‘prune’ message traverses up to the source node and helps in constructing the forwarding table in all the intermediate routing nodes. As the ‘prune’ message times out after a certain periodicity, the packet is again forwarded throughout the network and the ‘prune’ message is received back from the leaf nodes. When a node joins a multicast group, the node to which it joins sends a ‘graft’ message upstream in the network to enable all the routing tables to update the forwarding table.

Core‐based tree. The core‐based tree [33] has a single shared tree spanning across all the nodes of the multicast group and is centered at the core. When a new node joins a multicast group, the routing node to which it joins sends a ‘join’ message to the router above it in the shortest path towards the core and enters a transient join state for this new node in its forwarding entries. As the ‘join’ message reaches the core, it sends a ‘join_ack’ message back to the new node by the same path. When an intermediate routing node gets a ‘join_ack’ message for the new node, it forwards the same on the shortest path towards the router that initiated the ‘join’ message. The intermediate node also converts the transient entry for the new node into a permanent one, making the new node a part of the multicast spanning tree.

The way a new member is connected to the tree is used to classify the routing protocol into Single‐Path Routing Protocols (SPRs) and Multiple‐Path Routing Protocols (MPRs). SPR provides a single path for joining a new member to the tree, whereas MPR provides multiple candidate paths. Some of the recently proposed protocols [31, 32] based on MPR are as follows.

Spanning joins. A new member broadcasts ‘join request’ messages to all its neighbors, based on which a reply message is sent back to this new member by the on‐tree nodes. The path of reply is treated as a candidate path. As the new member may receive multiple reply messages corresponding to multiple candidate paths, it selects the best path based on the QoS properties of the path received in the reply.

Quality‐of Service‐Multicasting (QoSMIC) Protocol. Two parallel procedures are followed for selecting the candidate paths – local search and tree search. A local search is the same as a spanning join and is used to search a small neighborhood. When an on‐tree node is not found by the local search, a tree search is initiated. In the tree search, the new node contacts a designated core node which informs a few of the on‐tree nodes to establish a path from them to the member. The new member then selects the best path out of these candidate paths.

Spanning joins and QoSMIC protocols are QoS‐unaware protocols because QoS requirements are not considered for selection of the candidate path and the on‐tree node is selected on the basis of minimum hop connectivity.

Quality‐of‐Service Multicast Routing Protocol (QMRP). QMRP is a QoS‐aware protocol. QMRP consists of two searching modes for construction of the search tree single‐path mode and multipath mode. The protocol uses single‐path mode until it reaches a node that does not have sufficient resources for the assured QoS. At this stage, the protocol initiates the multipath mode for building the search tree further until it reaches the multicast tree. A QMRP tree is constructed from a new node that wants to join, and the construction of the tree moves towards the multicast tree. As QMRP considers only bandwidth constraints, the paths being built in the search tree satisfy the bandwidth requirement. A feasible path for connecting the new node is discovered when the growing search tree touches the pre‐existing multicast tree.

These protocols either do not satisfy QoS constraints or satisfy them to a very little extent. A protocol that satisfies the properties of a good multicast routing protocol is RIMQoS.

Receiver‐Initiated QoS Multicast Protocol (RIMQoS). This protocol constructs a multicast tree in a distributed fashion [34] and has the following characteristics:

• For a new node to join, no prior information about the existing nodes is required.
• Minimum resource reservation is needed.
• The existing tree is adjusted minimally.
• The ‘join request’ causes minimum overhead.
• The overall cost of the tree is to be minimized.
• RIMQoS works on top of any existing QoS unicast routing protocols that compute the QoS paths.

RIMQoS protocol is a single‐source multicast application that satisfies QoS requirements. A router keeps forwarding information about incoming interface and outgoing interface set to all nodes in the network. When a new member wants to join, it sends a ‘join request’ to the source node. Additionally, in a forwarding entry, each outgoing interface is labeled as ‘live’ or ‘on hold’. Multicast traffic is only forwarded to outgoing interface marked as live. Two types of notification are required: live notification and deny notification. When a new node wants to join in and the request is accepted, a live notification is sent to the new receiver. If the request is denied, a deny notification is sent to the receiver. The resources required for the assured QoS are reserved if the notification received is live.

4.7 QoS Best‐Effort Routing

Best‐effort routing attempts to provide the best feasible path from source to destination without guarantee of any assured level of service. Although a best‐effort routing does not fulfill QoS requirements, it can be modified to satisfy minimum constraints to cater effectively for the assured level of service. On the Internet, which follows best‐effort routing, a single best path towards the destination is computed by each intermediate routing node [35]. The selected path changes with change in the network topology or congestion in any part of the network. As the path is selected and the packets are delivered on a hop‐by‐hop basis, the packets may reach out of order of delivery and may even get dropped in any of the intermediate routers owing to load condition and unavailability of buffer space. Unlike the single‐best‐path selection strategy used on the Internet, best‐effort QoS in a network requires multiple paths to a destination to support various levels of performance. The routing requires a path selection algorithm that efficiently computes a set of best‐effort paths, and forwards the traffic over multiple paths to the destination. However, routing over multiple paths faces the challenge of loop detection and avoidance. Moreover, the best set of paths have to be recomputed if there are changes in topology, including node or link failures.

Load‐sharing routing (LSR) [36] is one of the algorithms proposed for best‐effort QoS routing. This algorithm tries to improve the QoS only in those regions of the network where it has deteriorated owing to congestion. The overhead of the routing algorithm is reduced by making only the neighboring nodes of a congested node implement the LSR algorithm. In this routing algorithm, each routing node maintains an active routing table and a passive routing table. The active routing table is created from the node’s awareness of the network topology and gives the shortest path based on Dijkstra’s algorithm from the node to any other node in the network. These paths are referred to as OSPF paths in this protocol. The passive routing table keeps the shortest distance to all other nodes from each of its neighboring nodes as the source node. This is also calculated using Dikstra’a algorithm by keeping the neighbor as the source node. The entry in the routing table comprises the destination node, the next‐hop node, the total cost, the hop count, the OSPF next hop, and the LSR flag. When the LSR flag is false, the node forwards the packet as per the OSPF algorithm and the next‐hop node and the OSPF next‐hop node are the same. When the LSR flag is true, the next‐hop node is calculated on the basis of the LSR algorithm. The algorithm uses a number of different messages to calculate the path. The working of the algorithm can be well understood by referring to these messages.

When a node detects congestion beyond a threshold on any one of its links, it sends congestion notification about the node to all its neighbors. The neighbors that receive a congestion notification send a reroute request message to any one of the neighboring nodes to inform it that the router will reroute the packets meant for the node on the congested link to this router to which it is sending the reroute message. Once the congestion is cleared, a ‘congestion over’ message is sent to indicate normal behavior of the link. On receipt of the ‘congestion over’ message, the intermediate router sends a ‘reroute over’ message to its neighbor to which it had been rerouting the packet. When a router receives a reroute notification, it sets the LSR flag to true for the congested destination and starts rerouting the packets by the alternative path.

An alternative path routing algorithm [37, 38] that supports loop‐free routing is LSR. An LSR coefficient, which is based on operating parameters, has to be decided for the LSR protocol, which then decides the number of multiple paths for a particular destination. The LSR parameter can be global across the network or local to a routing node. The aim of the approach is to maximize the number of alternative paths to enable at least one alternative path for each node. However, search for the LSR coefficient is exhaustive and time consuming.

A protocol that reduces the search for the LSR coefficient to only potential areas is E‐LSR (efficient LSR) [39]. The cost of the links and the topology of the network are the parameters for deciding the alternative path. The algorithm uses the OSPF model to make the routing table. The entries in the routing table are ospfcost, ospfhopcount, and nexthop for a particular destination. Ospfcost is the cost of the ospf path to the destination. Ospfhopcount is the number of hops along the selected path. The nexthop is set to ospf nexthop to forward packets along the ospf path. There are two control messages used by the E‐LSR algorithm. A ‘congestion notification’ message is sent by a node to all its neighbors (except the one connected to it over the congested link) when it detects congestion on that outgoing link. When a link that was congested earlier is no longer congested, a ‘congestion over’ message is sent out to all the neighbors. The working of the protocol is similar to that of the LSR algorithm.

References

1. 1 L. Parziale. TCP/IP Tutorial and Technical Overview. IBM Redbooks. International Technical Support Organization, 8th edition, 2006.
2. 2 R. Guerin, A. Orda, and D. Williams. QoS routing mechanisms and OSPF extensions. 2nd Global Internet Miniconference, Phoenix, November 1997.
3. 3 L. Peterson and B. Davie. Computer Networks: A Systems Approach. Morgan Kaufman Publishers, 2nd edition, 2000.
4. 4 S. Misra. Quality‐of‐service routing, Chapter 509, pp. 3186–3190, in M. Khosrow‐Pour (ed.). Encyclopedia of Information Science & Technology, IGI‐Global, 2nd edition, 2008.
5. 5 Q. Ma. Quality‐of‐Service Routing in Integrated Services Networks. PhD thesis, School of Computer Science, Carnegie Mellon University, January 1998.
6. 6 R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87–90, 1958.
7. 7 A. Vasilakos, M.P. Saltouros, A.F. Atlassis, and W. Pedrycz. Optimizing QoS routing in hierarchical ATM networks using computational intelligence techniques. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 33(3):297–312, 2003.
8. 8 P. V. Mieghem (ed.), F.A. Kuipers, T. Korkmaz, M. Krunz, M. Curado, E. Monteiro, X. M. Bruin, J. S. Pareta, and J. D. Pascal. Quality of service routing. Quality of Future Internet Services. Springer, 2003.
9. 9 S. Chen and K. Nahrstedt. An overview of quality of service routing for next‐generation high‐speed networks: problems and solutions. IEEE Network, 12(6):64–79, 1998.
10. 10 A. V. Kumar and S. G. Thorenoor. Analysis of IP network for different quality of service. International Symposium on Computing, Communication, and Control (ISCCC 2009), CSIT, Singapore, 2009.
11. 11 J. Saliba, A. Beresford, M. Ivanovich, and P. Fitzpatrick. User‐perceived quality of service in wireless data networks. Personal and Ubiquitous Computing, 9(6):413–422, 2005.
12. 12 A. Jamalipour. The Wireless Mobile Internet: Architectures, Protocols and Services. John Wiley & Sons, Inc., 2003.
13. 13 J. D. Chalmers and M. Sloman. A survey of quality of service in mobile computing environments. IEEE Communications Surveys, 2(2):2–10, 1999.
14. 14 Quality of service indicators. GSM mobile networks – quality of service survey, Portugal: Autoridade Nacional de Comunicações, October 2002.
15. 15 W. Stallings. Data and Computer Communications. Prentice Hall, 8th edition, 2007.
16. 16 S. Misra, Network applications of learning automata. PhD dissertation, School of CS, Carleton University, Ottawa, Canada, 2005.
17. 17 Z. Wang and J. Crowcroft. QoS routing for supporting resource reservation. IEEE Journal on Selected Areas in Communications, 14(7):1228–1234, 1996.
18. 18 S. W. H. Wong. The online and offline properties of routing algorithms in MPLS. Master’s thesis, Department of Computer Science, University of British Columbia, 2002.
19. 19 F. Atlasis, M. P. Saltouros, and A. V. Vasilakos. On the use of a stochastic estimator learning algorithm to the ATM routing problem: a methodology. IEEE GLOBECOM, December 1998.
20. 20 C. Segui, A. Zaballos, X. Cadenas, and J. M. Selga. Evolution of unicast routing protocols in data networks. IEEE INFOCOM, Barcelona, Spain, 2006.
21. 21 S. Chen and K. Nahrstedt. Distributed quality‐of‐service routing in ad hoc networks. IEEE Journal on Selected Areas in Communications, 17(8):1488–1505, 2006.
22. 22 Z. Wang and J. Crowcroft. QoS routing for supporting resource reservation. IEEE Journal on Selected Areas in Communications, 14(7):1228–1234, 1996.
23. 23 Q. Ma and P. Steenkiste. QoS routing for traffic with performance guarantees. IFIP International Workshop on Quality of Service, pp. 115–126, Springer, 1997.
24. 24 S. Chen and K. Nahrstedt. On finding multi‐constrained paths. IEEE International Conference on Communications ICC 98, Volume 2, pp. 874—879, 1998.
25. 25 B. Awerbuch, Y. Azar, S. Plotkin, and O. Waarts. Throughput‐competitive online routing. 34th Annual Symposium on Foundations of Computer Science, pp. 32–40, Palo Alto, CA, 1993.
26. 26 R. Guerin and A. Orda. QoS‐based routing in networks with inaccurate information: theory and algorithms. IEEE INFOCOM ’97. 16th Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, Volume 1, pp. 75–83, Japan, 1997.
27. 27 H. F. Salama, D. S. Reeves, and Y. Viniotis. A distributed algorithm for delay‐constrained unicast routing. IEEE INFOCOM ’97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, Volume 1, pp. 84–91, Japan, 1997.
28. 28 I. Cidon, R. Rom, and Y. Shavitt. Multi‐path routing combined with resource reservation. IEEE INFOCOM ’97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, Volume 1, pp. 92–100, Japan, 1997.
29. 29 K. G. Shin and C. C. Chou. A distributed route‐selection scheme for establishing real‐time channel. 6th IFIP International Conference on High Performance Networking (HPN’95), pp. 319–329, 1995.
30. 30 S. Selvan and P. S. Prakash. Optimized delay constrained QoS routing. Advances in Modeling – Computer Science and Statistics, Volume 14, 2009.
31. 31 S. Chen and Y. Shavitt. SoMR: A scalable distributed QoS multicast routing protocol. Journal of Parallel Distributed Computing, 68(2):137–149, 2008.
32. 32 A. Striegel and G. Manimaran. A survey of QoS multicasting issues. IEEE Communications Magazine, 40(6):82–87, 2002.
33. 33 B. Wang and J. C. Hou. Multicast routing and its QoS extension: problems, algorithms, and protocols. IEEE Network, 14(1):22–36, 2000.
34. 34 A. Fei and M. Gerla. Receiver‐initiated multicasting with multiple QoS constraints. IEEE INFOCOM 2000. 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Volume 1, pp. 62–70, 2000.
35. 35 B. R. Smith and J. J. Garcia‐Luna‐Aceves. Best effort quality‐of‐service. 17th International Conference on Computer Communications and Networks, ICCCN ’08, Volume 1, pp. 3–7, 2008.
36. 36 A. Sahoo. A load‐sensitive QoS routing algorithm in best‐effort environment. IEEE MILCOM, Volume 2, pp. 1206–1210, 2002.
37. 37 A. Sahoo. An OSPF based load sensitive QoS routing algorithm using alternate paths. Computer Communications and Networks, pp. 236–241, 2002.
38. 38 A. Tiwari and A. Sahoo, A local coefficient based load sensitive routing protocol for providing QoS. 12th International Conference on Parallel and Distributed Systems (ICPADS ’06), Volume 1, p. 8, Washington, DC, 2006.
39. 39 A. Tiwari and A. Sahoo. Providing QoS support in OSPF based best effort network. 13th IEEE International Conference on Networks. Jointly held with the IEEE 7th Malaysia International Conference on Communication, Malaysia, 2005.

Abbreviations/Terminologies

ATM

Asynchronous Transfer Mode

CAC

Connection Admission Control

CBT

Core‐Based Tree

DCLC

Delay‐Constrained Least Cost (Routing Protocol)

DCUR

Delay‐Constrained Unicast Routing (Protocol)

DVMRP

Distance Vector Multicast Routing Protocol

E‐LSR

Efficient Load‐Sharing Routing

ETSI

European Telecommunications Standards Institute

EXPRESS

Explicitly Requested Single‐Source Multicast

FIFO

First In First Out

FTP

File Transfer Protocol

HTTP

Hypertext Transfer Protocol

IETF

Internet Engineering Task Force

IPv4

Internet Protocol Version 4

ISP

Internet Service Provider

LA

Learning Automata

LAN

Local Area Network

LSR

Load‐Sharing Routing

MIP

Multicast Internet Protocol

MOSPF

Multicast Open Shortest Path First

MPR

Multiple‐Path Routing

NMS

Network Management System

NP

Network Performance

OSPF

Open Shortest Path First

PHB

Per Hop Behavior

PIM

Protocol‐Independent Multicasting

PIM‐dense

Protocol‐Independent Multicasting Dense Mode

PIM SM

Protocol‐Independent Multicasting Sparse Mode

PNNI

Private Network–Network Interface

QMRP

Quality‐of‐Service Multicast Routing Protocol

QoS

Quality of Service

QoSMIC

Quality‐of‐Service Multicasting

RIMQoS

Receiver‐Initiated QoS Multicast Protocol

RPM

Reverse Path Multicast (algorithm)

RSVP

Resource Reservation Protocol

SELA

Stochastic Estimator Learning Automata (Routing)

SLA

Service Level Agreement

SMTP

Simple Mail Transfer Protocol

SPR

Single‐Path Routing

SWP

Shortest Widest Path

TCP/IP

Transmission Control Protocol/Internet Protocol

ToS

Type of Service

UDP

User Datagram Protocol

VoIP

Voiceover Internet Protocol

WAN

Wide Area Network

WSP

Widest Shortest Path (Algorithm)

Questions

1. Why is QoS required and what are the advantages of QoS?
2. Mention various QoS parameters defined for various criteria and applications.
3. Describe the packet header used in differentiated services.
4. As defined by IETF, what are the two models for implementing QoS?
5. Explain the following five processes of traffic regulation – classification, metering, marking, shaping, and dropping.
6. Mention the advantages and disadvantages of differentiated services and integrated services.
7. What are the properties of the SELA routing algorithm?
8. Name a few unicast source routing algorithms.
9. What are the essential features of a robust and scalable multicast routing protocol?
10. Explain the process of creation of a multicast group.
11. Explain best‐effort routing. Also, describe any best‐effort routing protocol.
12. Differentiate between source‐based and center‐based multicast routing protocol, along with one example of each protocol.
13. Explain the following:
    1. tree constraint for QoS in multicasting,
    2. traffic shaping,
    3. service level agreement,
    4. per hop behaviour,
    5. Resource Reservation Protocol (RSVP),
    6. properties of the shortest widest path (SWP) algorithm,
    7. widest shortest path (WSP) algorithm,
    8. SELA routing algorithm,
    9. Delay‐Constrained Unicast Routing Protocol,
    10. Delay‐Constrained Least‐Cost Routing Protocol.
14. Differentiate between the following:
    1. elastic traffic vs inelastic traffic,
    2. link constraint vs path constraint,
    3. interior router vs boundary router,
    4. differentiated services vs integrated services,
    5. guaranteed service vs controlled load service in an integrated service,
    6. tentative vs confirmed list of nodes in the SWP algorithm,
    7. link optimisation routing vs link‐constrained routing in QoS unicast routing,
    8. single‐path vs multipath mode of construction of a search tree in QMRP.
15. State whether the following statements are true or false and give reasons for the answer:
    1. The number of routing hops in a network can be one of the QoS metrics.
    2. The QoS routing algorithm uses information provided by QoS routing protocol to calculate the path by which the packet should be forwarded for delivery with assured quality.
    3. Some of the QoS parameters can be defined as excellent connectivity, low delay, assured bandwidth, and jitter‐free service.
    4. The differentiated service code point uses eight bits that were previously used for type of service in the IPv4 packet header.
    5. ‘Flow’ in an integrated service is the bidirectional data stream between two applications.
    6. The receiver can tear down the reservation of resources in the router of the path by sending a ‘path teardown’ message.
    7. Shortest widest path and widest shortest path are QoS‐based path selection algorithms.
    8. Once a loop is detected by a node in Delay‐Constrained Unicast Routing Protocol, a ‘remove loop’ message is used to recover from a loop.
    9. QoS best‐effort routing guarantees an assured level of service.
    10. Multicast routing protocols can be source based or destination based.