[INET'99] [ Up ][Prev][Next]

Schemes for Adaptive QoS Routing

Eleni STROULIA <stroulia@cs.ualberta.ca>
Ioanis NIKOLAIDIS <yannis@cs.ualberta.ca>
University of Alberta
Canada

Abstract

The majority of proposed quality-of-service (QoS) routing schemes operate by augmenting an underlying link-state protocol through the calculation of alternative paths or paths with particular resource-related properties and through control of the frequency of link-state updates. The objective is the maximization of the connections that can be successfully accepted. However, link-state routing suffers from an inherent drawback, namely, the need for each node to collect information about the complete network topology. In this paper we explore an alternative QoS routing and call admission scheme by using significantly reduced information at each node. The reduction is achieved by the construction of a hierarchy through a learning algorithm which uses the original (complete) topology and the particular call traffic profile in the network. Once the size of the stored routing state information is reduced, (a) the conveyed link-state information necessary to maintain it is similarly reduced and (b) the processing time necessary to determine optimal paths in the case of dynamic routing is reduced as well. The effectiveness of the scheme depends on the particular topology and connection traffic that is accommodated. We present preliminary results that demonstrate the effect of the topology on the connection blocking/rejection ratio. We note that for Internet-like topologies there is no drastic increase in the connection rejection/blocking ratio despite the severe reduction in routing information.

Contents

Introduction

The recent interest in the area of Quality of Service (QoS) routing in computer networks, and in the Internet in particular, has sparked intense research [1,2,3,4] for routing algorithms that exhibit desirable scalability, responsiveness, and efficiency objectives. In summary, the QoS routing is based on the assumption that in order for each traffic connection in the network to be set up successfully, a certain level of resources need to be allocated. Failure to reserve the resources results in rejection of the connection request. The resources that need to be allocated are predominantly bandwidth at the links and buffer space at the routers. We consider that the buffer space is a secondary issue that relates to the particular burstiness characteristics of the traffic and that can be regulated (shaped) at the entry point of the network. In this sense, the issue of buffer allocation, although nontrivial, can be considered to be orthogonal to that of bandwidth allocation. The rest of this paper focuses on bandwidth allocation alone.

If the bandwidth for a connection is not available, the connection is rejected. The rejection of a connection does not necessarily mean that a connection will not be set up. Rather, it can be set up without any resource commitments. Thus, a rejected connection may still be supported at the best-effort service class, which provides no service guarantees of any kind (in the same way that the Internet does not provide any service guarantee). Furthermore, we will not give attention to the underlying mechanisms used to convey the allocation information (e.g., ReSerVation Protocol [RSVP] [5]) or to the schedulers used to implement the bandwidth allocation at the routers (e.g., some implementation of Fair Queuing scheduling [6]). The criterion of the effectiveness of a QoS routing scheme will be assumed to be the fraction of rejected connections.

Existing QoS routing schemes are based on modifications of link-state routing protocols, and as a result, they inherit the space, message, and computational complexities of link-state routing, especially when the networks are large and highly dynamic. In this paper, we take the approach of reducing the necessary information stored by a link-state protocol and conveyed in link-state messages. To accomplish this, we build a routing hierarchy that depends on the particular topological information and the traffic load (connection requests) on the network. In the process, we are introducing a potential increase of the connection rejection ratio with the objective of reducing the space, computational, and message exchange demands. The argument is that for topologies that resemble the Internet topology, the increase in the rejection ratio is small and certainly well worth the spectacular reduction of the link-state overheads.

In summary, the proposed scheme is a hierarchical routing scheme. Its novelty lies in how the multilevel hierarchy is established. The hierarchical routing that is used in the current Internet is a result of the two-level hierarchical partition of the address space. Instead, in this paper, the proposed hierarchy is based purely on load and topology considerations and can result in a multilevel hierarchy. Moreover, it does not contradict the existing Internet address hierarchy, but rather, it builds the routing on top of it.

Topology- and load-dependent hierarchies

Routing schemes that are based on link-state information, such as Open Shortest Path First (OSPF) [7], present the most flexible basis for QoS routing because they allow the topology of the network to be known at each node; thus, alternative paths can be calculated (once per connection request or, typically, less frequently) while the link-state information can be used to reflect the link load, allowing the adaptive routing. Adaptive routing is not new; it has been explored in telephone networks in the past. A key difference between the telephone network and the Internet is found in their topologies. The telephone network topology is over-engineered, that is, it resembles (at least at the logical level) an almost completely connected graph. The Internet topology comes closer to a set of interconnected trees [8], partly because of its historical evolution from the gradual interconnection of separate local area networks on campus-wide backbone networks, and from there, through what was typically single-link, to a wide area network backbone. As a result, one can expect many more alternative paths to exist in the telephone network than on the Internet. On the other hand, the Internet provides a routing framework that is more flexible than the telephone network. Indirect paths in the telephone network are frequently limited to a certain maximum number of hops, whereas on the Internet, they are virtually unlimited.

The question that naturally arises at this point is whether all the topological information stored by link-state protocols is valuable in terms of providing bandwidth allocation in QoS routing for incoming connection requests. We suggest that the answer is no. In particular, the rest of the paper is based on the following intuitive claim: from the perspective of a specific node, the necessary link-state information is only the information for the links that are more likely to be used in setting up connections that pass through this specific node. For example, in an extreme case, we can eliminate the need for storing the information for alternative links that connect to a destination to which no connection (or very few connections) have historically been established. Inversely, we can preserve the links that are most frequently used. In addition, entire connected components of the graph can be viewed as a "neighborhood" (hereafter called a "locality") and represented as a single point. Subsequently, call admission can be performed on the link(s) that connect us to the neighborhood when the destination is a node in the neighborhood. The further refinement of the path within the neighborhood is left between the nodes of the neighborhood of the destination itself. The risk taken is that in this process of "abstraction" of the original topology, we lose sight of some possible paths, that is, we pick worse paths because our search space is limited.

The algorithm that determines the hierarchy needs to be repeated occasionally to compensate for the changing traffic conditions. Because of the need to observe the connection history and to know the entire topology initially, the simplest way to accomplish a dynamic version of the algorithm is to reset the link-state information occasionally to use the complete topology, and to use the recent history of the connection requests to determine the new effective hierarchy. After the hierarchy is determined, the extraneous link-state information is discarded, and likewise, the scope to which link-state information is propagated is limited. The process is repeated whenever a drastic new change in the traffic conditions is observed, and it can be performed on a seasonal, daily, and hourly basis. We will not discuss further how the particular scheme is implemented, because our primary concern in this paper is whether there is any valid performance reason to pursue it.

The learning algorithm

The purpose of the learning algorithm is to determine how the topology can be partitioned in localities based on the original topological information and the connection load profile. When a node belongs to a locality, it possesses the entire topological information of this locality. In addition, it possesses the abstracted (lumped) representation of the rest of the network outside the locality.

When the learning algorithm is run, the entire topology is initialized as one single locality, i.e., all nodes belong to a single universal "neighborhood." During the learning process, we identify connections, for which a path was produced within a single existing locality, but the path had a length greater than a given threshold length (the threshold path length is a parameter to the learning algorithm). The detection of such a path triggers a decomposition of the locality into two sub-localities. The locality decomposition operation involves two steps:

Figure 1 provides an example of a decomposition whereby a single locality is abstracted through the decomposition to two smaller localities. The decomposition is triggered by the excessive length (cost) of the path for a connection from A to B. In this particular example, the top, abstracted locality includes five nodes (in red) and the sub-localities include four nodes each (green and blue).


Figure 1

Hierarchical path construction

Given a new connection, if the two endpoints belong within a single locality, then planning is the same as before. If, however, the two endpoints do not belong in a single locality, then a third locality is found such that it is the closest common ancestor of the localities of both endpoints. Then, the problem becomes that of planning a path from the originating node to a node in the common ancestor locality, and a path from a node in the common ancestor locality to the destination node, and then connecting these two paths with one that is local to this high-level locality. Evidently, paths that are local at the high-level locality are not necessarily the optimal ones because the possible paths are limited at the localities higher in the hierarchy tree. It is precisely this point that generates the possible implication of the increased call rejection ratio.

Figure 2 illustrates this recursive planning process, for the path of a connection from node A to node Z. Node A belongs in the blue locality La, where node Z belongs in green locality Lz. Locality L (in red) is closest common ancestor of the two. L is a parent of both La and Lz. The problem then of planning a path from A to Z becomes the problem of planning a path from A to N1, which is a common intersection between La and L, and from N2, which is a common intersection between L and Lz, to Z. The individual paths planned locally in La, L and Lz are shown with strong arrows within each locality. The overall path is the composition of the three.


Figure 2

Experimental results

Each of the experiments consisted of three phases: simulation before learning, learning, and simulation after learning. First we simulated the behavior of the network in its original state with the complete traffic trace of 2,000 and 5,000 connection requests. Then we ran the learning algorithm with the first 200 connections of the traffic. At the end of the learning phase, a new simulation phase occurred, that is, the whole traffic was presented to the network, and the behavior of the network was observed. In this new phase, the network topology was always the same, but the process of planning the path of a connection was different. Planning was now hierarchical, that is, based on the learned locality hierarchy. In our experiments, we considered nodes of 100 nodes. We varied the following parameters:

In all experiments, the duration of each connection was produced from an exponential distribution with mean 10 time units. The connection requests were arriving according to Poisson process with a rate of one connection per unit of time. The bandwidth requested was produced from an exponential distribution with mean 1. The link capacities were all set to 3 in order to create congestion artificially. The threshold for the decomposition algorithm was 4 for the case of static routing and 8 for the case of dynamic routing. All connections have symmetric bandwidth demands in both directions.

Table 1 shows that the data collected through the experiments capture

Table 1: Experimental results
Hierarchy Routing Info Paths with Increased Hops (Average Increase) Rejected Connections (before/after)
Static
routing

2,000
runs
RAND
UNIF
51 2,309 1,051
(+3.99)
189/478
RAND
BIAS
39 2,680 972
(+4.04)
196/484
TS
UNIF
21 1,564 123
(+1.00)
403/412
TS
BIAS
23 1,372 0
(+0.00)
402/433
Static
routing

5,000
runs
RAND
UNIF
45 2,599 2,741
(+4.41)
430/1,048
RAND
BIAS
39 2,680 2,536
(+4.14)
460/1,177
TS
UNIF
21 1,564 1,443
(+1.23)
956/1,103
TS
BIAS
25 1,385 702
(+1.31)
963/1,111
Dynamic
routing

2,000
runs
RAND
UNIF
21 2,976 1,110
(+3.04)
129/245
RAND
BIAS
23 2,384 1,092
(+4.40)
151/452
TS
UNIF
31 1,516 45
(+0.2)
363/370
TS
BIAS
27 1,435 24
(+0.08)
369/368
Dynamic
routing

5,000
runs
RAND
UNIF
37 2,437 2,745
(+4.19)
290/1,036
RAND
BIAS
19 2,278 2,820
(+4.42)
336/1,039
TS
UNIF
29 1,591 399
(+ 0.49)
851/850
TS
BIAS
29 1,574 74
(+0.19)
869/868

Note that the routing table sizes presented in Table 1 are the sum of all the routing table entries over all the nodes, which has to be compared with the roughly 28,000 of the original system to account for the 280 edges/links used in the topological examples replicated on all 100 nodes. The difference is clearly huge. From the results, we can also see that the Internet-like topologies, simulated using TS models, result in no noticeable increase in terms of rejection ratio, partly because the TS structure agrees with the abstracted hierarchies produced from the presented scheme. The opposite happens when the topology is a flat random graph and the number of rejected connections exceeds two or three times the original (before learning). Moreover, an interesting result is the relatively minor role of the precise traffic model. That is, the uniformly random and biased cases generate similar results. Because we can never be sure about the exact traffic pattern we will encounter in a network, the insensitivity of the rejection ratio to the traffic model is encouraging news.

Summary and conclusions

It is too early to produce a conclusive argument in the presented research; however, our initial experiments provide some evidence that QoS routing can be accomplished by using drastically restricted topological information. In this paper, we presented a learning process that imposes on a network a hierarchical organization of local neighborhoods by taking into account the actual traffic demands and the network topology. This hierarchy transforms the route planning process into a composition of locally optimal paths, thus incurring a penalty on the quality of the complete end-to-end paths. At the same time, it drastically decreases the total amount of routing table information, and consequently it should also simplify the process of communicating and updating this information. In the networks and traffic patterns we examined, we found the resulting increase in the cost of the routes to be small, but nevertheless accompanied by a drastic reduction of the routing table information. However, further experiments are needed to precisely qualify the efficiency tradeoff under different topologies and traffic patterns.

Acknowledgments

This work was supported by NSERC RGPIN203221-98 and NSERC OGP 0194424.

References

  1. G. Apostolopoulos, R. Guerin, S. Kamat, S.K. Tripathi, Quality of Service Based Routing: A Performance Perspective, ACM SIGCOMM, October 1998.
  2. Q. Ma, P. Steenkiste, Quality of Service Routing for Traffic with Performance Guarantees, IFIP Workshop on Quality of Service (iwQoS), May 1997.
  3. Z. Zhang, C. Sanchez, B. Salkewicz, E. Crawley. Quality of Service Extensions to OSPF or Quality Of Service Path First Routing (QOSPF), Internet Draft draft-zhang-qos-ospf-01.txt, June 1996.
  4. G. Apostolopoulos, R. Guerin, S. Kamat, A. Orda, T. Przygienda, D. Williams, QoS Routing Mechanisms and OSPF Extensions, Internet Draft draft-guerin-qos-routing-ospf-04.txt, December 1998.
  5. L. Zhang, S. Deering, D. Estrin, S. Shenker, D. Zappala. RSVP: A New Resource ReSerVation Protocol, IEEE Network, Vol. 7, No. 5, September 1993.
  6. A. Varma, D. Stiliadis, Hardware Implementation of Fair Queueing Algorithms for ATM Networks, IEEE Communications Magazine, Vol. 35, No. 12, December 1997.
  7. J. Moy, OSPF Version 2, RFC 1583, March 1994.
  8. E.W. Zegura, K.L. Calvert, S. Bhattacharjee, How to Model an Internetwork, Proc. IEEE INFOCOM '96.

[INET'99] [ Up ][Prev][Next]