Capacity acquisition and task allocation with tax-band pricing intelecom networks

Telekom ağlarında kademeli fiyatlandırmayla kapasite kiralanması ve iş dağılımı

Abstract

Usage of data networks encompasses not only thetraditional data applications but also newer applica- tions such as real-time audio/video streaming, voiceover TCP/IP, real-time transactions, asynchronousmessaging and other batch transactions over digitalnetworks. Each application has different capacityand quality of service (QoS) requirements. Each isaffected differently by network reliability and speed.Major network providers have already started ef- forts to accommodate the QoS demand generated bythese applications. Providers charge differently for the capacity theysell. For example, Internet service providers (ISPs)offer a combination of fixed price for a fixed maxi- mum bandwidth (all-you-can-send) or pay per hour(or minute) for again a maximum bandwidth. Wire- less phone companies charge for text messagingbased on bytes sent. Certain calling plans offer dif- ferent per minute charges for phone conversationsdepending on when the call is placed.A firm uses data networks to perform and supportbusiness operations, which we will call tasks. Forexample, a videoconference is a type of task, so is aremote web site update. The obvious commonality isthat both tasks require network resources. A networkresource is characterized by its capacity (bandwidthand duration) and QoS. We assume that the contractsigned between the firm and the provider specifiesthe amount of bandwidth and quality guaranteed ata given time. Duration specifies the period duringwhich the resource is available. There are two types of costs associated with usingdata networks. The first one is the resource (i.e.,bandwidth, capacity) acquisition cost. The second isthe opportunity cost incurred due to insufficientquality realized in performing certain tasks such asvideo conferencing. Given a heterogeneous set oftasks and resources that differ in bandwidth andquality requirements, it might be in the firm's bestinterest to use either multiple providers or sign mul- tiple contracts with different bandwidth and qualityrequirements. For example, while resources withlower quality can be used for data applications,more expensive resources might be utilized for real- time applications with high QoS requirements.Therefore, the problem that the firm has to solve is acost minimization problem that reflects a trade offbetween the cost of acquiring resources and the op- portunity cost of degradation in realized quality oftasks performed. The quality of service of the resource affects the cus- tomer in two ways. First, size-fixed tasks might bedelayed beyond acceptable deadlines. Second, therealized quality of a time-fixed task such as a vide- oconference might be unacceptable creating an op- portunity cost for the customer. In general, oppor- tunity cost reflects the importance of a task. Themore important the task is, the higher the penalty fornot achieving desired targets (such as audio or visu- al quality). The decision maker will minimize thetotal cost by considering the trade-off among thesecosts when assigning tasks to resources.In our study we formulate a cost minimization prob- lem subject to QoS and capacity constraints. Weconsider the tax-band pricing scheme suggested byCourcoubetis et al. (2000a) in which each supplierhas a convex piecewise-linear cost function for eachresource offered. Courcoubetis et al. (2000a) claimthat tax-band pricing reduces bursty traffic sincecustomers are likely to reduce such demand to avoidpaying more. Suppliers in general would prefer hav- ing more customers with less capacity demand ra- ther than fewer customers with high capacity de- mand.Given this pricing structure the customer has to de- cide how much capacity to acquire and how to allo- cate tasks. For tractability we relax the due dateconstraints and assume that all tasks and resourcesare available at time zero. We also assume that real- time applications have desired transmission ratesand any deviation from that creates an opportunitycost for the customer. In spirit, this is the same ob- jective function used in Kasap et al. (2007) thattrades the quality cost with the capacity cost but thecost structure for capacity is quite different in thisproblem.In this study, firstly, we present tax-band pricing.Secondly, a formulation and a solution procedurebased on GBD are described.

Özet

Bu çalışmada bir şirketin, birden fazla tedarikçiden ağ kapasitesi kiralarken karşılaşılacağı eniyi- leme problemi incelenmiştir. Problem ele alınırken, bir firmanın veri ağları üzerinde gerçekleştire- bileceği işler sabit zamanlı ve sabit boyutlu işler olmak üzere başlıca iki kategoriye ayrılmıştır. Buiki kategorideki işlerin ihtiyaç duydukları zaman ve bant genişlikleri ile kalite gereksinimleri olduk- ça farklıdır. Bu nedenle çalışmada; farklı fiyat, kalite ve görev dağılımlarının firmaların optimaldavranışını nasıl etkilediği analiz edilmiştir. Problemin karmaşıklığını biraz olsun azaltmak ama- cıyla, kaynak ve talep hazır olduğu sürece, kapasite için bir üst limit bulunmadığı ve kapasiteninlimitsiz olduğu varsayılmıştır. Firmaların bu maliyet en küçültme problemi modellenirken, Courco- ubetis ve diğerlerinin (2000a) önerdiği her bir tedarikçinin doğru parçalarından oluşan dışbükeydoğrusal amaç fonksiyonuna sahip olduğu kademeli (tax-band) fiyatlandırma politikası dikkatealınmış ve amaç fonksiyonu iki tür maliyeti yansıtacak şekilde oluşturulmuştur. Bu maliyetlerdenilki, tedarikçilerin farklı fiyat seviyelerini yansıtan satın alma maliyetidir. İkinci maliyet ise, son tes- lim tarihlerinin kaçırılması veya vadelerin geçirilmesi, kalitenin düşmesinden kaynaklanan maliyet- ler ve karar merci bilinçli olarak hizmet niteliği düzeyini düşürdüğünde veya başka bir tedarikçiyeyöneldiğinde meydana gelen hizmet niteliği değişim maliyeti gibi olası fırsat maliyetleridir. Ayrıca,gevşetilmiş problemin çözümünde daha iyi bir alt sınır elde etmek için Genelleştirilmiş Bender Ay- rıştırma (Generalized Bender’s Decompomposition – GBD) algoritması uygulanmıştır.