6D-4 Incentive Compatible Pricing Strategies For QoS Routing

5m ago
35 Views
0 Downloads
1.27 MB
9 Pages
Transcription

l[ncentive Compatible Pricing Strategies for QoSRoutingYannis A. KorilisBell LaboratoriesLucent TechnologiesHolmdel, NJ 07733, [email protected] comAriel Orda”Dept. of Electrical EngineeringTechnionHaifa 32000, [email protected] ee.technion.ac.ilments and have each node advertise its residual rate [8], [24],Absf?act- QoS routing mechanisms allow users identify paths that canaccommodate their performance requirements and reserve the necessary[30]. The Guaranteed Service Class proposed for the Internetresources. An important problem is how to conduct such resource idloca[28] is based on such rate-based principles. Based on the proption efficiently, not only from the single-connection, but atso from the rreterties of such schedulers, several recent studies [10], [11], [18],work pointof view. We propose the use of pricing mechanisms as a meansto regulate the users’ decisions in a networkwide efficient mamre Focns[22], [26] have analyzed algorithms for computing paths thating on Q& architectures that employ rate-bwed schedulers, we formulatesatisfy end-to-end delay bounds. In particular, it has been showna congestion-based pricing scheme. We establish the structure of the correSpOnd% user-optim response, i a pafi selection gorithm that satisfiesthe user’s requirements at minimal cost. We show that the underlying noncooperative game among users has a unique equilibrium, for any particularchoice of ptice fonctious. Then, we establish the existence of incentive compatible price functions, which drive the network into on equilibrium pointthat ccincides with the optimmu of a social function. Specifically, theseprice fiumctions arc the derivatives of the social function. We then eztendour resntts to the case in which users can identify only sub-optimal paths,as is often the case with mrdtiobjective path band integrated services networks are expected to support multiple and diverse applications, with various quality ofservice (QoS) requirements. Accordingly, a key issue in the design clfbroadband architectures is how to provide resources inorder to meet the requirements of each connection, and, moreover, how to meet that goal in a networkwide efficient manner.The establishment of efficient QoS routing schemes is one ofthe major building blocks in such architectures. QoS routinghas been the subject of several studies and proposaJs (see, e.g.,[11, u], [91, [181, [221, [261, [291and references therein).On of the major problems in the establishment of a connection with QoS guarantees arises from the need to map end-toend re uirements, such as delay and/or jitter, onto locat (nodal)requirements, which would indicate how to reserve resourcesalong the route. The ability to derive such a mapping dependsto a large extent on the scheduling policy and service disciplineemployed at the nodes. Such disciplines are characterized bybounclson the maximal delay that any node can incur, and hencea corresponding bound on the end-to-end delay can be derived.This way, the routing problem can be formulated as identifyingthe path that has the best performance according to that boundand with respect to the QoS requirement. Recent studies haveproposed schedulers that map delay guarantees into rate require“Pari of tlus work was done while visiting Bell Laboratories.in [10] that for a given connection with an end-to-end delay constraint, the existence and identity of a feasible path can be obtained through up to M’ executions of a standard shortest pathalgorithm, where M is the number of network links. In [18],[26] it was shown that, through this scheme, one can accommodate additional connection requirements such as jitter.An important problem that has not been sufficiently addressedin the literature on QoS routing is that of efficient allocationof resources, namely “rates” or “bandwidth”, not only fkom thesingle-connection, but also from the network point of view. Inparticular, while each connection can choose the path betweensource and destination along with the corresponding bandwidthreservations, the network provider/manager typically aims at anallocation of resources that is deemed efficient with respect tothe overall network performance, The underlying assumption inprevious studies on QoS routing is that efficient usage of network resources can be enforced through appropriate choice ofpricing strategies. What constitutes “efficient” resource utilization and how it can be achieved through pricing mechanisms arestill open problems. Both these open problems are addressed inthe present study.Pricing as an allocation mechanism that makes decentralizeddecisions compatible with overall efficiency has been studied inthe context of queueing systems; see, e.g., [20]. In computernetworks, pricing has been receiving increasing attention fromboth the research and the corporate world, mostly due to the explosive growth of the Internet, which is evolving from a heavilysubsidized network to a commercial enterprise [5], [13], [14],[161,[171, [191, [231, [271. The research community has takena normative approach, proposing usage-based pricing mechanisms that will motivate the users to adopt a social behavior,e.g., by regulating their traffic, or by requesting lower grade ofservice. Network providers, on the other hand, will benefit fromusing network-efficient pricing schemes, but at the same timeare interested in mechanisms that first generate profit and sec1The terms “connection” and “user” rrreused intercharrgeably.0-7803-5420-6/99/ 10.00 (c) 1999 IEEE

ond are more appealing to the end users than the mechanisms oftheir competitors.The interface between the performance- and the marketoriented approach to pricing, is one of the main factors that willdefine the future evolution of public networks – networks whereaccess is not restricted to members of an enterprise – such asthe Internet. In an attempt to delineate this interface, various debates have arisen within both communities. There seems to bea consensus, though, that some type of usage-constraining pricing is necessm-ymainly due to congestion considerations. In thepresent study we do not attempt to enter these debates. Rather,within the framework of the normative approach, we demonstrate how pricing strategies can be used to drive the network toan operating point that is deemed efficient with respect to theoveral1network performance,More specifically, we consider a general network with nodalschedulers that belong to the rate-based class as described in thespecification of the Guaranteed Service for 1P.Each connectionis characterized by its source-destination nodes, maximal packetsize, maximal burst, and an upper bound on the end-to-end delay. The properties of rate-based schedulers allow the derivationof an upper bound on the end-to-end delay of a connection whenit is routed over a given path at a given reserved rate.There is a cost associated with reserving a unit of rate overa link, which is the price of the link. Focusing on congestionpricing, we assume that the price of a link is a function of theaggregate rate reserved at the link. Each connection is established so as to minimize the total usage cost while satisfyingits end-to-end delay constraint. The interaction among the various connections that decide independent y on their individualrouting strategies can be modelled as a game [6], [21]. Any operating point of the network is a Nash equilibrium of that game,that is, a collection of routing strategies horn which no user hasan incentive to deviate unilaterally.Link price functions are determined by the networkprovider/manager. The goal of the manager is to drive the usersto a Nash equilibrium that is efficient from the network’s pointof view. More specifically, we assume that efficiency is definedas minimizing a global (social) cost function that quantifies theoveral1network performance and is the sum of link cost functions. The manager seeks a pricing strategy that enforces aunique Nash equilibrium that minimizes this sociaf cost function. Any such pricing strategy is called incentive compatible.We investigate the structure of the QoS-routing game andshow that, for any given set of link price functions (conformingto a s t of general assumptions), it has a unique Nash equilibrium. Moreover, we establish a set of necessary and sufficientconditions for a feasible (link) flow vector to be the equilibriumof the game. Having established these results, we turn our attention to the problem of incentive compatible pricing strategies. We show that if the network manager imposes link pricefunctions that are equal to the derivatives of the link cost functions, the unique equilibrium of the QoS-routing game coincideswith the network optimum. We note that this type of price functions have been known to enforce the network optimum whenthe users implement a much simpler class of optimat routingstrategies, such as in transportation networks [4].In Ifie sequel, we turn our attention to connections that con-duct multiobjective, constraint path optimization. A typical setting is to identify a path that minimizes some target function,e.g., administrative costs, while observing one or more constraints, such as end-to-end delay and jitter, For this setting weshow that the previous results about the routing game and theincentive compatible prices still apply. These results are basedon the assumption that the users are able to determine optimalroutes that provide both delay and jitter guarantees. However,such multiobjective path optimization problems are, in general,NP-complete [7], therefore optimal routing solutions are prohibitively complex. On the other hand, there are efficient approximation schemes which provide t-optimal solutions withinpolynomial time complexity (see, e.g., [12]). This means thatusers can be expected to make not self-optimizing but only suboptimd decisions. This situation presents a harder challenge fornetwork management, as the response of users to managementschemes becomes unpredictable, An important question is, then,whether there is still a pricing scheme that drives the network toan efficient operating point. We indicate that the answer is affirmative, Moreover, we show that the required prices are exactlythose that correspond to the standard scenario of self-optimizingusers.The rest of the paper is structured as follows. In Section IIwe present the QoS-routing model and formulate the problemof incentive compatible pricing. Focusing on end-to-end delay constraints, in Section III we investigate the structure of theQoS-routing game and study the problem of incentive compatible pricing, The multiobjective path optimization case is considered in Section IV. Conclusions are presented in Section V.Due to space limits, proofs are omitted from this version, andcan be found in [15].II. MODEL AND PROBLEM FORMULATIONWe consider a network (p, Z), where V is the set of nodesand C VxVistheset of links, andlet N IVIandibl’ I,Cl.We denote by H the maximal possible number of hops (links) ina path. For any link 1 (u, v) c Z, define S(l) u and 7’(1) v. Considering a node u V, let In(v) {1 : T(l) u}denote the set of its ingoing links, and Out(v) {1 : S(l) u}the set of its outgoing links. Each link t E L is characterized bythe following parameters:. A maximal rate (capacity) Rz, which the link can offer to anew connection. When a new connection with a rate r R1 isestablished through link 1,the value of Rl becomes R1 – r.2 A comtam delay dl, related to the link’s speed, propagationdelay and maximal transfer unit. Without loss of generality, weassume that dl takesinteger vatues.Connections belong to a set Z {1, 2,.,1} of “types.” Aconnection (of type) i E Z is characterized by the followingparameters: a source node .si and a destination node ti, a bias cri, related to the connection’s maximal burst,. a maximal packet size Ci, an end-to-end delay QoS requirement Di, which, without lossof generality, is assumed to take integer values, a bandwidth QoS requirement bi.2If the maximat available rate is a nodat property, then we associate it with allits outgoing links.0-7803-5420-6/99/ 10.00 (c) 1999 IEEE

A connection should be routed through some path p betweenthe corresponding source and destination nodes. We shall denote by n(p) the number of hops of a path p, and by r(p) itsmaximal available rate, that is, r(p) minzcP R1. We assumethat the scheduling policy in the network belongs to the ratebased class [8], [24], [30], as in the specification of the Guaranteed Service for 1P [28]. Accordingly, when a connection i isroutecl over a path p with a reserved rate r r(p), its end-toend delay is upper bounded by:D(p,r) rJi n(p)c r dh(1)KpLet Di (p) Di(p, r-(p)) denote the minimal possible valueof Di (p, r), which shall be referred to as the guaranteed delay of p. A path p between Si and - is said to be ea ibJe forconnection i if Di (p) Di and r(p) bi. Paths that cannotaccommodate the bandwidth requirement of the connection canbe eliminated, thus the bandwidth constrained can be treated asabsent. Therefore, denoting by ai (p) fl d,the minimal rate that satisfies the delay constraint of connection i onpath p, the feasibility of a path can be defined as follows.Dejhition ZZJ: A path p between .si and ti is said to befeasible for a connection (of type) i, if D; zeP dl andr(p) ai (p). Let Pi denote the set of all feasible paths forthat connection.The arrivat process of type i connections with source node uand destination node j is some ergodic process with rate (j).We assume that there is an infinite number of type i connections,each with infinitesimally small rate. There is a usage cost wz associated with reserving a unit of bandwidth on link 1 c C thatwill be referred to as the price of the link. The total cost for reserving bandwidth r over path p is, then, r lGP W1.Each userm