A Framework for QoS-Based Routing

This page is based on RFC2386

Glossary

Background

Best-Effort and QoS based Routing

Routing deployed in todays internet is typically known as 'best-effort' datagram delivery. The current routing protocols such as OSPF, RIP use 'shortest path routing', ie routing that is optimised for a single arbitrary metrc, administrative weight or hop count. These routing algorithms are opportunistic.

QoS routing must extend the current routing paradigm in three ways,

QoS Based Routing and Resource Reservation

There is a difference between QoS-based routing and resource reservation. The latter involve protocols such as RSVP provide a method for requestin and reserving network resources, they do not provide a mechanism for the requested QoS. Conversely, QoS-based routingallows the determination of a that that has a good chance of acomodating the requested QoS, but it does not include a mechanism to reserve the required resources.

As such, boath are usually used together. In the case of OSPF, a different shortest-path tree can be computed for each of the 8 ToS values in the IP Header. Such mechanisms can be used to select specially provisioned paths but do not ocmpletely assure that resources are not overbooked along a path. As long as strict resource management and control are not needed, mechanisms such as ToS based routing are useful for separaring whole classes of traffic over multiple routes.

Combining Qos routing and resource reservation protocol allow fine control over hte route and resources at the cost of additional state and setup time. For example, a protocol such as RSVP may be used to trigger QoS based routign calculations to meet the needs of a specific flow.

Objectives of QoS-Based Routing

Under QoS based routing, paths for flows would be determined based on some knowledge of resource availability in the network as well as the QoS requirements of flows. As such, the main objective are,

QoS based routing on the internet raises many issues

- How do routers determine the QoS capability of each outgoing link and reserve link resources? Note that some of these links may be virtual, over ATM networks and others may be broadcast multi-access links.

- What is the granularity of routing decision (i.e., destination-based, source and destination-based, or flow-based)?

- What routing metrics are used and how are QoS-accommodating paths computed for unicast flows?

- How are QoS-accommodating paths computed for multicast flows with different reservation styles and receiver heterogeneity?

- What are the performance objectives while computing QoS-based paths?

- What are the administrative control issues?

- What factors affect the routing overheads?, and

- How is scalability achieved?

QoS Determinationand Resource Reservation

To determine whether the QoS requirements of a flow can be accomodated on a link, a router must be able to determine the QoS availabel on the link. It is still an open issue as to how the QoS availability is determined for broadcast multicple access links and the reservation of resources of such links.

Similiarly, problems arise when a router is connected to a large non-broadcast multiple access network, such as ATM. The router may have multiple egress choices. Furthermore, the QoS availablity on the ATM paths to each egree point my be different. Issues then are,

- how does a router determine all the egress choices across the ATM network?
- how does it determine what QoS is available over the path to each egress point?, and
- what QoS value does the router advertise for the ATM link.

Typically, IP over ATM allows the selection of a single egress point in the ATM network, and the proceedure does not incorporate any knowledge of the QoS required over the path.

Another problem wiht resource reservation is how to determine what resources have already been allocated to a multicast flow. The availability of this information during path computation improves the chances of finding a path to add a new receiver to a multicast flow. QOSPF handles this problem by letting routers broadcast reserved resource information to toher routers in the area.

Granularity of Routing Decision

If routing based only on destination address is considered, the all routers between different sources and an given distination will route all flows along the same path. This has implications should there be multipel flows to a destination that exceeds the capcacity of the link.

A version of QOSPF determines QoS routes based on source and destination addresses. This implies that all traffic between a given source and destination will travel down the same route. The amount of routing state also increases since the routing tables must include source/destination pairs instead of just the destination.

The best granularity is found when routing is based on individual flows. This, however, incurs a tremendous cost in terms of routing state. Each QoS flow can be routed separately between any source and destination. PQC and alternative path routing are examles of this.

Both source/destination and flow-based routing may be susceptible to packet looping under hop-by-hop forwarding. This could happen should a node along a source/destination path loses the state information for the flow. If the flow-based route is dfferent from the regular route, the potential for a routing loop tof orm exists.

Metrics and Path Computation

Metric Selection and Representation

Certain considerations arise in defining suitable link and node metrics. Metrics must be represent the basic network properties of interest - such as residual bandideth, delay and jitter. Since the flow QoS requirements have to be mapped onto these metrics, the metrics define the types of QoS guarantees the network can support.

Path computation based on a metric or a combination of metrics must not be too complex as to render them impractical. A common strategy to allow flexible combinations of metrics while reducingthe path computation complexity is to utilise a 'sequential filtering'. this means that a combination fo metrics is ordered in some fashion, reflecting the importance of different metrics. Paths based on the primary metric are computed first and a subset of them are elimiated based on the secondary metric and so forth. This should leaves a single path.

With these sets of suitable link and node metrics, a uniform respresentation of them is required across independent domains. Encoding of the min, max, range and granularity of the metrics are needed. Definitions of the comparisions and accumulation operators are required - also, suitable triggers must be defined for indicating a significant change from a minor change.

Metric Hierarchy

A hierarchy can be defined amongth various classes of service based on the degree to which traffic from one class can potentially degrade service of traffic from low classes that traverse the saem link. IN this hierarchy, guarantee constant bit rate traffic is at the top and 'best effort' datagram traffic at the bottom. A datagram slow should not affect a real-time service.

Datagram flows

A delay sensitive metric is probably the most obvious metric for this type of flow. A recursive filtering technique based on a simple and efficient weighted averageing algorithm could be used. This filter is used to stabilise the metric to reduce storage and bandwidth requirments. Another stabilising tool is a minimum time between updates that can help filter out high frequency oscillations.

Real-Time Flows

In real-time QoS, delay variables is generallly more critical than delay as lon gas the delay is not too high. Routing is real-time flow reduces to an exercise in allocating the required network resources while minising fragmentation of bandwidth. The resulting situation is a bandwidth limited minimum hop path from the source to destination. ie the router performs an ordered search through paths of increaseing hop count until it finds the one that meets all the bandwidth needs of the flow. The router could select a path randomly from a 'window' of paths which meet the needs of the flow and satify one of three additional criteria: best-fit, first-fit, or worst-fit.

Path Properties

Path computation is merely a search technique. The usefulness of paths computed depend to a large extent on the metrics used in evaluating the cost of a path with respect to a flow. Each link considered must be evaluated against he requirements of the flow. This requires a unifrom method of combining features such as delay, bandwidth, priority and other service features. The costs must reflect the lost opportunity of using each link after routing the flow.

Performance Objectives

One common objective is to improve the total network throughtput. By merely routing a flow on any path that accomodates its QoS requirement is therefore no a good strategy. This may adversely impact performance at higher traffic loads. To determine whether or not the flow should be routed on the path, it is therefore necessary to consider the total resources, to determine whether or not the flow should be routed on th epath. This is referred to as 'higher level admission control', its goal to ensure that the cost incurred by the network in routing a flow with a given QoS is never more than the revenue gained. The routing cost can be the considered as the lost revenue in potentially blocking other flows that contend for the same resources. The formulation of the higher level admission control strategy (with administative hooks and fairness) is an issue.

Administrative Control

Administrative control of routing behaviour may be necessary within an AS. The control of interdomain routing is also of importance. Also, other areas include handling flow priority with preemption and resource allocation for multiple service classes.

Flow Priorities and Preemption

A mechanism must be implemented to recognise flow priorities. In order to priortise flows there must be a policy to decide how different users are allowed to set priorities for flows they originate. The network must be able to verify that a given flow is allowed to claim a priority level signaled for it. Second, the routing scheme must ensure that a path with the requested QoS will be found for a flow with a probability that increases with priority of the flow. Routing procedures for flow prioritisation can be complex.

Resource Control

If there are multiple service classes, it is necessary to engineer a network to carry the forecast traffic demands of each class. To do this, router and link resources may be logically partitioned among various service classes. It is desireable to use dynamic partitioning whereby unused resources in various partitions are dynamically shifted to other partitions on demand. This must be done in a controled fashion to prevent traffic under some service class from taking up more resources than given.

QoS-Based Routing for Muticast Flows

QoS based Multicast routing is an important problem, especially if the notion of higher level admission control is considered. With distributed heiristic algorithms for multicast path computation, the difficulty is one of scalability. To accomodate QoS, multicast path computation at the router must have knowledge of not only the id of subnets where group members are present, but also the identiy of branches in the existing tree. In other words, routers must keep flow-specific state information. Also, computing optimal shared trees based on the shared reservation style may require new algorithms.

Routing Overheads

There are 3 types of overhead to be considered - computational, storage and communciation. Consider link-state information, the choice of update propagation mechanism is important since network state is dynamic and changes frequenty. A flooding mechanism would result in many unessary message transmission and processing. Tree based forwarding then have to be considered. This leads to a quantisation of state information to prevent frequent updating of dynamic state. While coarse quantisation reduces updating oerheads, it may affect the performance of the routing scheme. QoS based routing incurs certain overheads during flow establishment, eg computing a source route, and techniques for the minisation of routing relativing overheads during flow establishement must be investigated.

interdomain etc.

Wed, 23 July, 2003 13:07