Citation
Auction-based mechanisms for pricing network services

Material Information

Title:
Auction-based mechanisms for pricing network services
Creator:
Nashnoush, Ranim Hassan
Publication Date:
Language:
English
Physical Description:
viii, 58 leaves : ; 28 cm

Subjects

Subjects / Keywords:
Computer networks -- Prices ( lcsh )
Internet auctions ( lcsh )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 57-58).
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Ranim Hassan Nashnoush.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
788432036 ( OCLC )
ocn788432036
Classification:
LD1193.E52 2011M N37 ( lcc )

Full Text
AUCTION-BASED MECHANISMS FOR PRICING NETWORK SERVICES
By
Ranim Hassan Nashnoush
B.S. Alfateh University/ Tripoli, 2001
A thesis submitted to the
University of Colorado Denver
In partial fulfillment
Of the requirements for the degree of
Master of Science
Computer Science


This thesis for the Master of Science
degree by
Ranim Hassan Nashnoush
has been approved
by
Gita Alaghband
l< !o7- /2oil
Date
Ilkyeun Ra


Nashnoush, Ranim H (M.S., Computer Science)
Auction-Based Mechanisms for Pricing Network Services.
Thesis directed by Associate Professor Bogdan S. Chlebus
ABSTRACT
We investigate the effect of pricing for the quality of service in networks
that offer different levels of quality of service. Dynamic pricing of network
services is to improve the use of network resources and maximize the service
providers benefits. We discuss the principles of quality of service, differentiated
service networks, and pricing approaches. We present in detail three specific
auction-based mechanisms that allocate network recourses and control
congestion. One of them is Smart Market for pricing traffic on the Internet.
Another is SPAC which is a game theoretic pricing mechanism to statistically
guarantee the quality of service in packet-switched networks. The third
mechanism is an optimal solution for a single-link network to allocate bandwidth.
We present a comparison between all the considered mechanisms. We propose


how to set the base price in SPAC. We also propose adding more parameters to
the revenue function to enhance pricing mechanisms.
This abstract accurately represents the content of candidates thesis. I recommend
its publication.
Bogdan Chlebus


TABLE OF CONTENTS
Figures......................................................... vii
Tables........................................................... viii
Chapter
1. Introduction................................................ 1
1.1 Quality of Service(QoS).................................... 2
1.2 Integrated Services (IntServ).............................. 3
1.3 Differentiated Services (DiffServ)......................... 4
1.4 Pricing Approaches......................................... 7
1.4.1 Flat-rate Pricing......................................... 7
1.4.1.1 Capacity-based Pricing.................................. 7
1.4.1.2 Usage-based Pricing..................................... 7
1.4.2 Auction-based Pricing................................... 8
2. Pricing Mechanisms for Resource Allocation and Congestion Control.. 9
2.1 The Smart Market Mechanism................................. 9
2.2 The Smart Market as Pricing Mechanism for DiffServ......... 11
2.3 The Smart Pay Access Control (SPAC) Mechanism.............. 13
2.3.1 The Difference between Smart Market and SPAC............. 15
2.3.2 SPAC Formal Definition................................... 15
2.4 SPAC as Pricing Mechanism for DiffServ..................... 19
v


2.4.1 Pricing the Traffic Profiles(TPs)............................. 20
2.4.2 Pricing the Out-profile Traffic................................ 20
3. Optimal Solution for a Single-Link Network....................... 24
3.1 Problem Formulation.............................................. 25
3.2 Optimal Solution for Single Class Case......................... 27
3.2.1 Example........................................................ 30
3.3 Optimal Solution for Multiple Classes Case...................... 34
4. Heuristic Algorithm for Multiple Links network................... 37
4.1 Problem Formulation............................................ 37
4.2 Intra-link and Inter-link Solution(IIS)......................... 38
4.2.1 Intra-link Adjustments......................................... 39
4.2.2 Inter-link Adjustments......................................... 41
4.3 Related Issue................................................... 45
5. Comparison and Proposed Modifications............................ 46
5.1 Comparison between Auction-Based Pricing mechanisms.............. 46
5.2 Proposed Modifications.......................................... 48
5.2.1 Proposal Regarding the SPAC Mechanism.......................... 48
5.2.2 Proposal Regarding the Optimal Solution and the IIS Algorithm. 51
6. Conclusion....................................................... 53
References........................................................... 57
VI


LIST OF FIGURES
Figure
2.1 Representation of DiffServ Architecture..................12
2.2 SPAC-Based Pricing for DiffServ..........................22
vii


LIST OF TABLES
Table
1.1 Shows the Assured Forwarding per-hop behavior codepoints...6
6.1 Shows the Features of The Auction-Based Pricing Mechanism.53
viii


1. Introduction
Over the years, the Internet has come to support many more applications
than it did previously. Today, applications such as real time audio and video can
be transmitted over the Internet. In order to ensure a certain level of quality of
service to these applications, certain minimum levels of requirements have to be
provided. As we know, resources in the network environment are limited, so they
need to be allocated in a fair manner and in a manner that will maximize the
service providers revenue as much as we can. The pricing approach is applied to
allocate these resources. Also, the pricing approach is applied to solve another
problem which the congestion in the network as the number of users is growing
fast.
Most of the service providers these days use the tradition pricing approach
which is flat-rate. This approach offers only one class of service which is the best
effort, where all users pay the same and get the same level of service. Also, this
approach encourages the waste usage of the Internet resources by making users
pay a certain amount of money and in turn get unlimited usage to the Internet.
We need several levels of quality of service to satisfy the requirements of
the new generation of applications. New pricing approaches have emerged to
meet this goal. Some of these pricing approaches are based on the idea of auction,
1


where the users submit bids and the bidder who wins the auction gets the service.
In this thesis, we present in detail three auction-based pricing mechanisms that are
applied to provide different levels of quality of services.
The thesis is divided as follows: the concepts of the Quality of Service,
Integrated Services, Differentiated Services, and pricing approaches will be
introduced first. In the next chapter, we will present two auction-based pricing
mechanisms that are used to allocate the resources and control the congestion.
These mechanisms are: the Smart Market for pricing traffic on the Internet, and
the Smart Pay Access Control (SPAC), which is a game theoretic pricing
mechanism to statistically guarantee the quality of service in packet-switched
networks. The third chapter presents a mechanism called an Optimal Solution a
mechanism that allocates bandwidth in case of a single-link network. The
heuristic algorithm for multi-links network will be discussed in chapter four.
Chapter five shows the comparison between the pricing mechanisms that are
discussed in the previous chapters. In the same chapter, we suggest some
modifications for future work that enhance the auction-based pricing mechanisms.
We conclude the thesis with a culminating chapter that summarizes all of the
material that we have discussed.
1.1 Quality of Service (QoS)
In computer networking, Quality of Service means that some
characteristics of traffic such as transmission rates, error rates, and bandwidth can
2


be measured, improved and guaranteed. It also provides different priorities to
guarantee a certain level of performance to applications and data flows. Quality
of Service is important for the new generation of applications such as Voice over
IP (VoIP), video conferencing, and online games. These applications require a
certain minimum level of bandwidth allocation and latency in order to work well.
The Internet Engineering Task Force (IETF) working groups have proposed two
approaches to provide quality of service in IP networks: Integrated Services and
Differentiated Services. These two approaches will be discussed next.
1.2 Integrated Services (IntServ)
The Internet Engineering Task Force (IETF) working groups have
proposed Integrated Services (IntServ) to provide more than one single best-effort
class of service. IntServ is based on the reservation paradigm where end users
request resource reservation for each flow. In other words, network resources
such as bandwidth must be reserved along the routing path [5]. Each router has to
ensure that the requests are accepted only if there are enough local resources
available by applying admission control to the requests. The Resource
Reservation protocol (RSVP) is a key component in the IntServ architecture,
which enables communication between the senders, receivers, and routers. RSVP
is used to reserve resources along the routing path designated by the underlying
routing protocol. The problems with the Integrated Services that lead to the
Differentiated Services are:
3


The Integrated Services architecture does not scale well in the core
network because each router must maintain state information and
the amount of state information increases with the number of
flows.
In order to obtain end-to-end quality of service, all routers must
implement many additional requirements like RSVP and admission
control, which is unrealistic in the current Internet.
1.3 Differentiated Services (DiffServ)
The Internet Engineering Task Force (IETF) working groups have
proposed Differentiated Services (DiffServ) as a mechanism to provide quality of
service in packet-based networks such as the Internet. DiffServ is based on a
generalized priority paradigm which guarantees that a packet of a higher priority
class gets through with a higher probability than that of a lower class. DiffServ
offers a finite number of different service classes. It stamps each packet with a
single codepoint. The DiffServ codepoint (DSCP) is stamped in the Type of
Service (TOS) field of the IPv4 packet header or in the Traffic Class field of IPv6
packet header. All packets with the same codepoint are treated similarly.
Users mark their traffic to one of the offered classes when they access the
network. The network forwards packets at each node according to per-hop
behaviors. The per-hop behavior based on DiffServ codepoint (DSCP) carried in
differentiated services (DS) field of the IPv4 header or IPv6 header determines the
4


forwarding treatment (policy and priority) for a packet when traversing a router.
DiffServ cannot target any particular quality of service for each codepoint without
additional mechanism such as pricing. What it can do is to ensure that some
codepoints will obtain different quality of service than others. This is normally
not sufficient because some applications require specific minimum quality of
service to perform well. For example, suppose there are two service classes: a
premium and best-effort, where the premium traffic always gets better treatment
than the best-effort traffic. When the congestion in the networks increases,
premium traffic will obtain a better quality of service than the best-effort traffic.
As a result, users who use a high-quality service (premium) will pay more than
the users who use the low-quality (best effort). An important feature of DiffServ
is good scalability obtained by aggregating flows into a finite number of classes
which eliminates the need to recognize and store information about each
individual flow in core routers. There are three per-hop behaviors that have been
defined:
1. Expedited Forwarding (EF) per-hop behavior is a high priority behavior
whose forwarding treatment supports low loss, low delay and low jitter. A
packet gets lost through the path if it has entered the network and it does not
get to its destination point. The delay is the amount of time taken for a packet
to arrive from its source to its destination. The jitter is the variation in delay
that is experienced by consecutive packets.
5


2. Assured Forwarding (AF) is a group of per-hop behaviors that offers various
levels of forwarding assurances. There are four assured forwarding classes
that have been defined. For each of them there are three possible drop
precedence values (low, medium, high) that packets of the class are marked
with one of them. In case of congestion, the drop precedence of a packet
determines its importance within the assured forwarding class. In other words,
the congested node discards packets with high drop precedence to protect
packets with low drop precedence. The combination of classes and drop
precedence values gives twelve different codepoints (DSCP).The following
table summarizes all the cases.
Tabel [1.1] Shows the assured forwarding per-hop behavior codepoints
Class 1 Class 2 Class 3 Class 4
Low Drop AF11(DSCP 10) AF21(DSCP 18) AF31(DSCP 26) AF41(DSCP 34)
Med Drop AF12(DSCP 12) AF22(DSCP 20) AF32(DSCP 28) AF42(DSCP 36)
High Drop AF13(DSCP 14) AF23(DSCP 22) AF33(DSCP 30) AF43(DSCP 38)
3. Best Effort (BE) Forwarding is the default per-hop behavior where any traffic
that does not meet the requirements of the other classes is placed in the best
effort. Best effort does not guarantee a packet delivery; it guarantees that
packets sent to this flow queue receive any share of bandwidth that is not used
by the other classes [5][8][2].
6


1.4 Pricing Approaches
Network resources such as bandwidth and buffer space are limited. Pricing
would help to allocate them in a fair and cost-effective way. We review some
pricing approaches that are discussed in [2].
1.4.1 Flat-rate Pricing Approach
Most Internet service companies use this approach where every client pays
a flat-rate price in order to receive the best effort service. When the network is
congested, this approach does not provide information to routers about some
packets. The other observation is that the flat-rate approach does not encourage
clients to pay more for better quality of service during the peak time. Possible
extensions to this approach are as follows:
1.4.1.1 Capacity-based Pricing
We assume that there is a perfect prior knowledge of demand. This allows
calculating the optimal prices off-line so that on-line algorithms adjust prices
based on the predicted functional form of demand. The shortcoming of this
pricing approach is that in the real network, it is hard to make predictions of
demand when the traffic of the network is changed rapidly which make it hard to
implement.
1.4.1.2 Usage-based Pricing
In this approach the charge and the usage are directly related in that the
price is based on the clients usage. The approach offers individual pricing plans
7


which are easy to use. However, this is a complicated approach to implement in
the real network environment.
1.4.2 Auction-based Pricing Approach
The pricing approach that is based on the auction needs minimal prior
information in order to calculate the price. This approach consists of two steps:
clients submit their bids and then an auction step allocates the resources to them.
This approach encourages the clients to participate because they will bid what
they are willing to pay in order to get the service. The auction-based-pricing
approach can generate more benefits for the service provider compared with the
flat-rate pricing approach by admitting the higher-priced traffic classes and
rejecting the lower-priced ones.
8


2. Pricing Mechanisms for Resource Allocation and Congestion Control
One network problem is the congestion that happens when there are too many
users competing for limited resources. Moreover, most service providers offer a
flat-rate pricing approach for network services which gives a client unlimited use
of the network; this encourages waste and lowers the quality of services. In this
chapter we will present two auction-based pricing approaches that allocate the
network resources in the congested network. The first one is called the Smart
Market and the other is called Smart Pay Access Control (SPAC).
2.1 The Smart Market Mechanism
Smart Market was proposed by Varian and Mackie-Mason in 1994 [7],
Consider one of the first attempts to solve the problem of pricing on the Internet,
it is an auction-based pricing mechanism for the resource allocation in a
congested network. This approach is based on the per-packet charge in case of
congested network and the charge is zero if the network is not congested which is
what we have in the flat-rate pricing approach. Smart Market views the network
as an auction market where the router is an auctioneer and the bidder is a packet
owner who wants to send this packet through this router. Smart Market introduces
a new packet header that contains a bid field where the user states the price which
he is willing to pay for the transmission though the router. Users set default bids
9


for different applications; for instance, a user may assign a high bid for real-time
video packets and a low bid for e-mail packets. In special cases, the default values
may be changed. For example, if the e-mail message is urgent then the user will
pay a high price in case of a congested network.
Each router has a threshold value that is dynamically changed according
to the network status such as capacity and congestion. Only packets that have bid
values higher than the predetermined threshold are admitted by the router. These
packets consider as auction winners and they are ordered at each router before
they pass through it based on their bid values. For each packet, the owner does not
pay his own bid; instead he pays the market-cleaning price which is the maximum
bid value of packets that are not admitted. In other words, the market-cleaning
price is the highest threshold value between all routers threshold values which
the packet passed through. This concept is called Second Price Auction or
Generalized Vickrey Auction (GVA) and has the advantage that the optimal
strategy for the user is to bid his true value of service.
However, Smart Market has been determined as an unsuitable option for
the real network for many reasons. First, it does not guarantee the service to the
users. It just gives the admitted packets priority to pass the router according to
their bid values. This priority may lead to packet re-ordering. Also, in the real
network, packets make many hops on routers in their trip from the source to the
destination which means the user must bid higher values to all routers that are
10


followed the congested ones in order to not lose their money that is already spent
in the congested router; this may increase the traffic overhead in the already
congested network. Another observation is that the large amount of auctions that
have to be done for each packet at each router makes the Smart Market hard to
implement in the real network. Lastly, Smart Market does not consider how fast
the users will react to the auction in the environment where the network status is
under no ones control. Considering these limitations, the Smart Market has
mostly been implemented as pricing scheme in a differentiated services network
as we will show next.
2.2 The Smart Market as Pricing Mechanism for DiffServ
Yuksel and Kalyanaraman in [6] have presented a strategy to implement
Smart Market pricing scheme on differentiated services (DiffServ). Their strategy
is based on the Smart Market limitations that we addressed in the previous
section. Also, they suggested some modifications in order to implement the
pricing scheme. Figure (2.1) shows that there are two types of routers in the
DiffServ architecture: The edge routers (ER), and the interior routers (IRs). The
edge router which is at the entry point for a traffic flow to pass through the
differentiated services domain is called ingress-ER. It is called egress-ER at the
exit point.
11


Figure 2.1: Representation of DiffServ Architecture
This strategy to implement Smart Market proposes that the customer sets
the bid value in the bid field in the packet header before sending it to the network.
The packet passes through the edge router (ER) first and then through many
interior routers (IRs). Each router has a threshold value and it arranges the packets
that have bid values greater than the threshold value in the priority queue.
Otherwise the packet is dropped.
Yuksel and Kalyanaraman suggest adding a new field to the packet header
which is the cleaning price field. This field contains the price that the user is
going to pay. The cleaning price field is initialized to 0 and then it is updated at
each interior router to the maximum value of threshold values, so when the packet
arrives to the edge router it contains the maximum threshold of all routers that it
passed through. The edge router sends the cleaning price that needs to be paid to
each corresponding sender. The sender requires being up to date with the network
status in order to adjust his bids and sending rate. Yuksel and Kalyanaraman met
12


this requirement by proposing a simple probing procedure. The probing procedure
happens at fixed-time interval and works as follows: The customer sends a probe
packet to get feedback about the network status. The probe packet passes through
the interior routers to find the current cleaning price. When the egress-ER
receives the probe packet, it sends a feedback packet to the customer which
contains the current cleaning price. In the latest interval the feedback packet
contains the customer bill which is the total of all cleaning prices to that customer.
2.3 The Smart Pay Access Control (SPAC) Mechanism
In [10][11] Shu and Varaiya proposed The Smart Pay Access Control
(SPAC), which is an auction-based pricing mechanism that is efficient allocates
the limited resources among the competing clients. The network resources usage
in a packet-switched network is reflected in the statistical guarantee the packets
receive. This mechanism guarantees that the higher the value a client puts on the
service (packet delivery) the better statistical guarantee of delivery that he
receives. The idea of SPAC is based on the idea of Smart Market mechanism and
the differentiated quality of service is formed by the different guarantees of
delivery.
The SPAC approach proposes that a service provider sells a service to clients
where there are a range of different qualities of this service. The quality of service
is defined as the statistical guarantee of service delivery which means that the
higher the probability, the better the quality. Clients first bid for the service by
13


announcing how much they are willing to pay for this service, and then they get
admission tickets with different colors to this service. Based on all users bids, the
SPAC mechanism decides the color of each client. These different colors
represent different quality of services, so every client is served with certain
quality based on the color of his admission ticket. For example, suppose that the
service has three different levels of quality of service: level 2, 1, and 0 where
level 2 the highest quality. Each level can admit a certain number of clients where
the clients are N, hence N2, Ni, and No respectively.
SPAC mechanism works as follows: The first step is sorting all bids (equal
bids are ordered randomly among themselves) and then assigning the number of
clients that each class can admit. The highest N2 bidders receive the service at the
highest quality level 2, the next highest Ni bidders get quality level 1, and the
remaining bidders get the lowest quality level 0. The important observation is that
although clients receive different quality of services, their bid values are the
values of service not the values of different qualities.
SPAC mechanism requires that the lowest quality level of services admits all
the remaining clients who are not accepted for any higher quality levels, even
clients who bid zero. This means that SPAC admits every client to the service,
which means the mechanism has a feature called universal coverage.
Regarding the payment, clients have to pay a price for receiving a quality of
service. This price is known as the congestion fee. For the lowest level of service,
14


the congestion fee is always zero which corresponds to the current fee best
effort service in the Internet. The price of other higher levels of quality of service
is calculated based on Generalized Vickrey Auction (GVA). Based on the SPAC
payment scheme, the service provider can divide the network resources to provide
levels of services which encourage the clients to choose the right categories.
2.3.1 The Difference between Smart Market and SPAC
Although the SPAC approach is based on the idea of the Smart Market
approach, there is a major difference between the mechanisms. The SPAC treats
the packets as aggregates to solve the major problem of Smart Market approach
which is the large amount of auctions of each packet at each router. Alternatively,
SPAC provides quality of service differentiation and congestion control as fast as
the sorting algorithm, which makes it feasible for real world usage. The
mathematical formulation for that price will be presented in the next section.
2.3.2 SPAC Formal Definition
Formally, SPAC is represented as a game that consists of players, outcomes,
players strategies, outcome function and players utility function. The SPAC
mechanism (Mspac) is defined as follows:
1- Players: There are n players called agents denoted by player i =1,..., n and,
one principal which is player i = 0.
2- Profile of values: a profile is a collection of values of some variable (e.g.
a), one value for each player, denoted by (a1,...,an). For any profile
15


a = (a1;an) and any player i£{l, .,n}, let a_; be the list of
elements of the profile a for all players except /, that is, a_t =
(<*1, > &i1< ai+i> ^n)
3- Service and Quality of Service: The principle who provides the service to
the agents statistically guarantees the service at different delivery rates, so
the quality of service is defined as the delivery rate of the service. There
are m different levels of quality of service that represented as k= 0, 1,
m-1 and dk represents the quality of service delivery rate at £-th level of
service. It can be expressed as d = (d0,d1( ...,drn_1), where 0 < do<
d/<...< dm.i job is to allocate C among m levels of quality of service where each level
can admit a limited number of clients which is Ak.
4- Agents Actions: All n agents must announce their values of the service.
The announced values, also called bids are represented as b = (bi, ..., bt,
..., b), where bi is the bid for agent i. The true values which are the
agents private information are denoted by Q = (01; ...,0; ,...,0), where
8i is the true value of agent i. Let b(i), b(2),b(n) be the order statistics
corresponding to bj, b2,, b. That is, b0) is the /th smallest value among
bi,b2, ,b.
5- Principals Action: The principle decides at what level of quality of
service each client will be admitted based on all agents bids. Formally,
16


the principle computes the vector x = (xj, ...,x,-,... ,x), where x, is the
service delivery rate that agent i receives, so Xj G X and X = {do, dj,...,
dm-]}
The function Qk(Xi) that indicate the level of quality of service agent i
receives is defined as:
Qk(xi) -
1, ifx,- = dk
0, otherwise
Subject to the constraint that for all i G {1, ...,}, each agent i receives
only one level of quality of service, 'ZkL=o Qk(xi) = 1-
The solution x*(b), a function of b, maximizing the total benefit to all
agents if x*(b) = arg maxxi ex Ef=i (2.1)
Subject to:
The capacity constraint that V/c = 1,..., m 1,
I=i<2k(*t)< Ak (2.2)
The universal service coverage Yk=o Ak >n (2.3)
6- Congestion Price: The principal calculates a congestion price that the
clients must pay for each level based on all agents bids. The prices are
represented by p = (p0, p10,..., pm-i), where the price for level 0 is zero
p0 = 0 (2.4)
and the price for level k can be computed by,
17


Pk(b) = Pft-i(fc) + (dfc dk-i)b^n_Ym-iAly
(2.5)
where b^n_^m-iA^ is the highest bid of agents who are not admitted from
the &th level of service or above.
7- Agents Utility: The agents utility function for all i G {1, ...,} is
Wf(Mt) = diXi Yk=oPkQk(Xi), (2.6)
where pkQk(.xi) is the amount that the agent pays for receiving
service at certain level.
After describing all SPAC formal definitions, we can see what strategy an
agent should adopt in order to maximize his utility. The agents strategy
determines how much he should bid to get service at a certain level. This strategy
is dependent on all agents actions. However, Shu and Varaiya in [10] have
claimed that the optimal strategy for every agent is to bid the true value where
bi= This strategy is dominant because it does not depend on other agents
strategies and it is the optimal solution that maximize agents utility for all
i E {1,..., n}. It has been shown that the SPAC mechanism is dominant incentive
compatible. The precise proof is given in [10].
Next, based on all agents bids, the principle decides which agents to
admit at each level of service by sorting all the bids in the descending order, then
admitting the highest Am_1 to the quality of service level dm_l5 the next higher
Am_2 to the level dm_2and so on, until all the bidders are admitted at some level.
The equations (2.4) and (2.5) are used to calculate the congestion fees for each
18


agent based on his level of service. In the next section we will present how
SPAC is applied as pricing mechanism for differentiated service networks.
2.4 SPAC as Pricing Mechanism for DiffServ
Shu and Varaiya have applied SPAC as pricing scheme for DiffServ network
architecture to manage the network service and control the congestion [10][11].
As we know from the first chapter that is in the DiffServ architecture, the traffic is
classified in the boundaries of the network and assigned to different aggregates.
Furthermore, in the packet header, each packet is identified with a certain
DiffServ codepoint (DSCP) where all packets in each aggregate have the same
DiffServ codepoint. Packets are forwarded from node to node in the core of the
network based on the per-hop behavior that is associated with the DiffServ
codepoint. The service differentiation is achieved by treating packets from
different aggregates differently. The scalability is achieved because of the three
major features of the DiffServ model: 1) the service differentiation is given to
packet aggregates not to an individual microflow; 2) the classification of the
traffic is pushed to the edge of the network; 3) the information of service
differentiation is stored in the packet headers rather than in the network nodes,
which means there is no need for the network to maintain the traffic status [1].
There are two steps to applying the pricing scheme for DiffServ: first is pricing
the traffic profiles and second is pricing the out-profile traffic streams. The SPAC
is only applied to price the out-profile traffic.
19


2.4.1 Pricing the Traffic Profiles (TPs)
A traffic profile is a description that determines the temporal properties of
a traffic stream such as rate R and burst size B. Also, it provides rules to specify if
a particular packet is in or out profiles. As an example of a traffic profile that is
based on a token bucket is (codepoint=X, token-bucket r, b), this profile
determines that all packets that are marked with DiffServ codepoint =X should be
measured with rate r and burst size b against the token bucket meter. A packet is
considered as in-profile if there are sufficient tokens available in the bucket.
Otherwise, it is considered as out- profile. Regarding pricing, a traffic profile is
sold at a flat fee for certain time period with unlimited usage. There is no extra fee
for in-profile traffic and SPAC is the pricing mechanism that is used for the out-
profile traffic as we will see in the next section.
2.4.2 Pricing the Out- Profile Traffic
The user pays a congestion fee for the out-profile traffic because it is the
reason behind the congestion and there is no restriction on how much a user may
generate an out-profile traffic. The SPAC as a pricing mechanism for DiffServ
network works as follows:
1. The service provider decides the service delivery rate vector, d =
(d0, d1#..., dm_1) which indicates how many different levels of quality of
service that the network provides.
20


2. The Resource Manager, which is dynamically configures, statistically
guarantees the different service delivery rates. Setting bandwidth on
routers and queue size for different classes of traffic is done in the interior
of the network. Each level of quality of service has its own DiffServ
codepoint that specifies a per-hop behavior for the aggregate.
3. An automatic agent (AA), that represents the user bids the true value of
service for the out-profile traffic.
4. Based on all users bids a bandwidth broker (BB) calculates p =
(p0, Pi, , Pm-i) ,which is the congestion fee for each level of QoS, as we
defined previously in SPAC. Note that the bandwidth broker
receives [Ak, k = 1, ...,m 1}, which is the cuurent capacity information
for different levels, from the resource manager.
5. According to the quality of service level assigned to the out-profile traffic,
a Marker marks the DiffServ codepoint of the out-profile traffic. Note that
the assignment of quality of service level is based on SPAC mechanism.
6. Finally, a billing system records the congestion fee and the out-profile
packet counts from the Marker.
21


The representation of SPAC as a pricing mechanism for DiffServ is shown in
figure (2.2).
-Users-
-Network Edge

in profile
Meter
outproMe
(w*i tch)
Cdrrtml Row
- Traffic Row
TQ -Traffic Generator
AA ~ Automatic Agent
TP -Ttaffle Pfoiie
DSCP DifServ CoctoPoirt
Q Queue (Buffers
BW Bandwidth
B6 Bandwidth Broker
SPA Smart Pay Aansaon Mechanism
JHffasurwwrt A Configuration
(SRAC) A QoS capacities / \ Resource
BB V J N| ! Manager
Figure 2.2 SPAC-Based Pricing for DiffServ [10]
The figure shows one traffic generating source (TG), one traffic profile (TP)
and four different levels of quality of service. The highest quality which provides
a high rate of delivery is marked as DiffServ codepoint DSCP=in and it is
reserved for in-profile packets. The other three quality of service levels are
marked as DSCP=med, DSCP=low, or DSCP=be for the medium, low, or best-
effort rates of delivery are reserved for out-profile packets. The best effort rate is
equivalent to the current quality of the Internet. Also, at all quality of service
22


levels above the best effort level, the congestion is controlled for the major
property of SPAC mechanism which is each level of service admits the correct
amount of traffic. The bandwidth broker, the meter, the marker, and the billing
system, which apply SPAC as pricing mechanism, all reside at the edge of the
network, so the interior of the network does not need to deal with the SPAC
mechanism.
23


3. Optimal Solution for a Single Bottleneck Link Network
Y.Guan, W.Yang, H.Owen and D.M. Blough in [2] have presented an
auction-based pricing mechanism for bandwidth allocation in a differentiated
service network. This mechanism gives an optimal solution under the assumption
that the network can be modeled as a single bottleneck link. The main idea of this
approach is that clients belong to different classes and each client bids for the base
price, the price sensitivity coefficient and the minimum amount of resource that
the client requires. The base price is the price for the required minimum amount
of resource. The price sensitivity coefficient is the marginal price that the client is
willing to pay for an extra unit of bandwidth besides the minimum amount
required. For example, a client wants to submit an application that requires
minimum 8M bandwidth. If there is available extra bandwidth, the client can use
it to achieve a better quality.
Periodically, the auctions operate on sealed bids, so based on all clients
bids, the service provider decides the admission price and the service threshold
offered for each class of clients. After that, clients who offered base prices that are
no smaller than the admission price and their minimum amount of required
resources no larger than the service threshold are admitted to the network in order
24


to meet the service provider goal which is maximizing the total revenue subject to
limited resources.
3.1 Problem Formulation
As we mentioned, that the service provider aims to maximize the revenue,
so this auction-based scheme assumes revenue function similar to the function
that is used in [9] which is a logarithmic function of extra assigned bandwidth.
Vij = + Wij log^ ,(3.1)
For client i in class j, ytj represents the revenue that is obtained from that
client, Uij represents the base price, vvi;- represents the price sensitivity
coefficient, xtj is the allocated bandwidth, and ly is the minimum amount of
bandwidth which is required by client i in class j. Since the class of client i is
predetermined before the auction starts, we can say that i G 0(J) where 0(J)
describes the set of predetermined clients in class j.
By applying the sealed auction, for each class the service provider will
decide unique base price, price sensitivity coefficient and minimum bandwidth. In
order to satisfy all admitted clients requirements, the base price, price sensitivity
coefficient has to be smaller and the minimum bandwidth has to be larger than
what each admitted client provided. Also, clients in the same class will receive the
same amount of bandwidth.
Besides the revenue function in (3.1), we need to define some parameters
and decision variables. The parameters are Q which is the total amount of
25


bandwidth and N which is the total number of classes. The decision Variables
are uf, if wf xf, and Zjj where uf is the base price for class j, if is the
minimum amount of bandwidth provided for class j, wf is the price sensitivity
coefficient for class j, xf is the amount of bandwidth that is received by a client in
class j which is the same for all clients in that class and Zjj = 1 if client i is
admitted in class j and 0 otherwise. Based on all parameters and the decision
variables, the mathematical formulation for the bandwidth allocation problem
(BA) is as follows:
max (p = ZjLi Etc ay) [uf + wf log ^ j ztJ, (3.2)
Subject to these constraints:
1. The resources are limited: £7=1 Ei e 00) xij Q (3-3)
2. The minimum amount of resources that are provided for each class j
should be no smaller than the minimum required resource provided by
each admitted client:
If ~ kjZij > 0 Vi e 0(y), j = 1, ...,N (3.4)
3. The final sensitive price for each class j should be no larger than the
sensitive price provided by each admitted client:
wf WijZij < 0 Vi G 0(/), j = 1, -,N (3.5)
4. The final base price should be no larger than the base price provided by
each admitted client:
26


uf UijZij < 0 Vi G 00), j =
(3.6)
5. For each class j, the minimum bandwidth requirement is satisfied for all
admitted clients in that class:
Xij lijZij > 0 Vi e 00), j = (3.7)
6. For each class j, all admitted clients get the same amount of bandwidth:
Xij xf < 0 Vi G 00), j = 1, -,N (3.8)
After we have defined the mathematical formulation for the problem and all
its parameters and decision variables, next we will see that there is an optimal
solution for the problem if there is just a single class of service.
3.2 Optimal Solution for Single Class Case
In this section, we will present a polynomial-time algorithm for a single
class case. The class j is used to denote the single class case just to keep the
notation consistent as we described the problem formulation. The optimal solution
includes if, wf and uf where If = max{ ltj: i G 00)}, wf = rnin{ wi;-: i G
00) } and uf = min{ utj : i G 00)}, where 00) represents the set of admitted
clients in class j. The detailed proof of the optimal solution property is in [2], The
optimal solution for a single class case can be obtained by applying the following
steps as presented in [2]:
27


1. Generate all combinations of (uf, wf, if). There are 0(n3) combinations
that is for each element in the combination there are n choices where n is
total number of clients.
2. For each combination^^, wf, if), check each client i G 0(J) to see if
client i is candidate or not. Client i is candidate if this client satisfies the
conditions ltj < if, > wf and utj > uf. The total number of
candidates is sk and the complexity of this step is 0(n4).
3. In the optimal solution, for each admitted client i in class j, i G 0(y) we
have xtj = xf = Q/rrij, where m;- is the total number of admitted clients
in class j. Then, we calculate (pk{r) = ruf + rwf log (Q/(r if)) for each
r= 1, ..., sk. After we calculate it for all candidates, we get cpk =
max{ combination (uf, wf, if).
4. Finally, select the optimal value

among all combinations. The complexity of this step is 0(n4).
As we can see, we met the goal which is maximizing the service provider
revenue by calculating the best thresholds and assigning bandwidth to all admitted
client, so we can say that the single class bandwidth allocation problem can be
solved in 0(n4) time. Next we will present the detailed algorithm as described in
[2]-
28


Algorithm 1. (Optimal Solution for Single Class Problem)
Initialize (p = 0.
for k = 1 to n3 do
let (uf, wf, if) represent a possible combination of (uf, wf, if).
initialize sk = 0.
for each i 6 0(j) do
if kj < if.Wij > wf and Uij > uf, then update sk = sk+ 1.
end if
end for
if uf > wf then
if Q/sk > if then end if
else
initialize cpk = 0 .
for r = 1, sk do
if Q/r > if then
calculate if (pk < (pk(r) then cpk = cpk(r)
end if
end if
end for
end if
if (p < cpk then

end for
29


3.2.1. Example
In this example, we will apply the single class case algorithm to see how we
can obtain the optimal solution of bandwidth allocation problem. Suppose we
have five clients and the total available bandwidth Q = 12M. Also, assume that all
clients bid with the same base price but with different minimum required
bandwidth and price sensitivity coefficient. The clients bidding are as follows:
Client 1 (Cl): u1;- = 20, Z1;- = 2M, w1;- = 10
Client 2 (C2): u2j = 20, l2j = 3M, w2j = 11
Client 3 (C3) : u3;- = 20, l3j = 2.5 M, w3j = 9
Client 4 (C4): u4;- = 20, l4]- = 10M, w4]- = 12
Client5 (C5) : usj = 20 lsj = 8M, w5j- = 6
Since all clients base price are the same, we have 52 = 25 combinations for
(uf,wf,lf) :
Olj.Wlj) (lij.w2j) {llj'W3]) (llj'W4j) {hj.wsj)
{hj.wxj) {hj>w2j) O2j,w3]) (hj.wtj) (hj.wsj)
(j-3j> Wlj^) (^3 j> w2 7) (hj>w3j) (^3;' (hj.WlJ) (l3j.W2j) (Uj,W3j) (Uj,W4j) (l4j,ws])
. (!sj>Wlj) Osj.w2J) Osj.w3j) Os(isj'Wsj)
Now, for each combination we want to check all clients to determine who is
candidate and then we calculate each candidates revenue.
30


1. k=l (2M, 10), Cl is the only client that satisfy the conditions <
Z1;- and wtj > w1;-, so s1=l and Q/s1 = = 12M > i1;- = 2M. The
12
maximum revenue from this combination is 2. k=2 (2M,11), There is no candidate for this combination that is all clients
do not satisfy the conditions < Z1;- and wi;- > w2j, so s2=0.
3. k=3 (2M,9), Cl candidate. s3=l, 4. k=4 (2M,12), s4=0.
5. k=5 (2M,6), Cl candidate. s5=l, 6. k=6 (3M,10), Cl, C2 candidates. s6=2, ^ = 6M > l2j = 3M,
7. k=7 (3M,11), C2 candidate. s7=l, 8. k=8 (3M,9), C1,C2,C3 candidates. s8=3, = 4M > l2] = 3M.
9. k=9 (3M,12), s9=0.
10. k=10 (3M,6), C1,C2,C3 candidates. s10=3, = 4M > l2j = 3M.
11. k=ll (2.5M,10), Cl candidate. sn=l, 12. k=12 (2.5M,11), sI2=0.
31


12
13. k=13(2.5M,9), C1,C3 candidates. s13=2, 2(2.5)
46.84.
14. k=14 (2.5M,12), s14=0.
15. k=15 (2.5M,6), C1,C3 candidates. s15=2, cp15 = 2(20) + 2(6) log=
2(.2.5j
44.56.
16. k=16 (10M,10), C1,C2,C4 candidates. s16=3. ^ = AM < l4j = 10M.
That means we cannot admit all candidates. We have to check r=l,..., s16.
a. r=l,= 12M > 10M. b. r=2, = 6M < 10M.
c. r=3, = 4M < 10M.
Then we can admit only one client and the revenue is (p16 20.79.
17. k=17(10M,ll), C2,C4 candidates. s]7=2. ^ = 6M < 10M.
a. i=l, ^ = 12M > 10W, b. r=2, = 6M < 10M. Then 18. k=18 (10M,9), C1,C2,C3,C4 candidates. s,8=4. = 3M <= 10M.
a. i=l, = 12M > 10M, b. r=2, = 6M < 10M. Then 19. k=19 (10M.12), C4 candidate, s19=l, 32


20. k=20 (10M,6), C1,C2,C3,C4 candidates. s20=4. = 3M < 10M.
4
a. r=l,^ = 12M > 10M, b. r=2, = 6M< 10M. Then (p20 = 20.47
21. k=21 (8M,10), C1,C2 candidates. s21=2. ^ = 6M < 8M.
a. i=l,= 12M > 8M, 1 8
b. r=2,^ = 6M < 8M. Then 22. k=22 (8M,11), Cl candidate. s22=l, (p22 = 20 + 11 log = 21.93.
23. k=23 (8M,9), C1,C2,C3 candidates. s23=3. ^ = 4M < 8M.
a. i=l, = 12M > 8M, b. r=2,^ = 6M < QM. Then 24. k=24 ,(8M,12). S24=0.
25. k=25 (8M,6), C1,C2,C3 candidates. s25=3. ^ = 4M < 8M.
a. r=l, = 12M > 8M, 1 8
b. r=2,^ = 6M < 8M. Then After we checked all candidates for each combination, we obtained that the
maximum revenue is 63.37 which is from the eighth combination (3M,9) and
there are three candidates for this combination and we can admit all of them, so
the threshold for this class is (20,3M,9) and the admitted clients bids are
33


C1(20,2M,10), C2(20,3M,11), C3(20,2.5M,9). All clients in this class will get the
same amount of bandwidth which is 12M/3 = 4M that guarantee the minimum
amount required bandwidth to all admitted clients.
3.3 Optimal Solution for Multiple Classes Case
In this section we will see that there is an optimal solution for single link
multiple class problem as presented in [2][3]. If we assumed that the assigned
bandwidth in class j is Qj and the total number of admitted clients in class j is
m.j, so all admitted clients will share of Qj/mj and all of them will generate the
same revenue. Alternative mathematical formulation for bandwidth allocation
problem (BA2) is used to solve the single link multiple class case when
Uj, wf, if and my is given:
As described in [2] [3], we can calculate Qj the assigned bandwidth for each class
proof is given in [2], Note that for a class j and Qj we can calculate the objective
value and the optimal solution by applying the single class case algorithm and all
constrains in single class case are applied in multi-class case. The outlines of the
polynomial-time algorithm to obtain the optimal objective value for the single
link multi-class case are as follows:
where Qj = Q .
(3.9)
j from this formula: Qj = (my wf Q)/(Hy=1mj wf) Y/ = 1, ...,1V. The detailed
34


1. For each class j and each combination (my, wf) within this class, calculate
Qj based on the formula Qj = (my wf Q)/{Y,f=1m.j wf) Vj = 1,..., N.
We have n2N possible combination, so the complexity for this step is
0(n2N).
2. For each Qj and the corresponding combination (my, wf),
a. Check all different combinations of (uf,lf). For each
combination, check each client i G 0(J) to determine which
clients are candidates. Client i is candidate if the conditions
lij < if, Wij > wf, utj > uf are satisfied. The total number of
candidates is sk.
b. If sk > mj and Qj/rtij > if, calculate the optimal value for
(my, uf, wf, If), cpk(j) = mj uf + mj wf log (Qy/(my if)).
3. Finally, select the optimal value

summation of the objective values for each class j. The complexity of this
step is 0(n3).
As a result of the previous steps, we can say that the single link multi-class
bandwidth allocation problem can be solve in 0(n2N+3) time with the goal that
maximizing the service provider revenue. Next we will present the detailed
algorithm as described in [2],
35


Algorithm 2. (Optimal Solution for Multi-Class Problem)
Initialize (p = 0.
for k = 1 to n2N do
Assume the corresponding combination is (mf, wf,).
for each class j there is n2 possible combinations of (uf, if).
for r = 1 to n2 do // assume the corresponding combination is (uf, If).
for j = 1 to N do
Let Qj = (mf wf Q)/(Y!j=1 mf wf ).
Initialize sk = 0.
for each i E 0(j) do
if lij < If, Wij > wf and utj > uf, then update sk = sk+ 1.
end if
end for
if sk > mf and Qj/mf > If then
(pr(j) = mfuf + mfwf log(Qj/(mf If))
else
(PrOl = 0.
end if
end for
if cp < (pr then (p = end for
end for
36


4. Heuristic Algorithm for Multiple Links Network
In the real problems, several links along a path in the network may be used
by one client, so if we apply the same approach that we used to solve the
bandwidth allocation problem for a single link network we may face the problem
that the assigned amount of bandwidth for two consecutive links along one path is
different. Y.Guan, W.Yang, H.Owen and D.M. Blough in [2][4] have presented a
heuristic approach for bandwidth allocation problem in a multiple link network.
This approach considers the bandwidth assignment consistency across links for
the same clients routing path. Also, this approach assumes that the routing paths,
the network topology knowledge and the clients bids are given where the clients
bid is valid for all links along the routing path. As a single link network, the
service provider wants to admit the most valuable clients in order to maximize his
total revenue.
4.1 Problem Formulation
The same revenue function is adopted as a single link case with some
other notations to describe the multiple link case precisely. The value on a link is
represented by y, Cy represents the bandwidth capacity of link y in the network, r
stands for the set of all links in the network and ry is the set of all requested links
by client i in class j. Also, there are additional parameters and decision variables
37


that are introduced besides what we have in the single link. The parameters ,
wjj and ujj represent the minimum required bandwidth, the sensitive coefficient
and the base price in link y for client i in class j respectively. x[j is a decision
variable that represents the bandwidth in link y for client i in class j. The
mathematical formulation for the bandwidth allocation problem (BAM) is as
follows: max

Subject to the same constrains that are applied in the single link case with
additional two constrains:
1. For each link, the total used bandwidth will not exceed its capacity.
T.j=iZie0U)xIj Cy <0 Vy e T (4.2)
2. The assigned bandwidth for each client must be the same along the routing
path in the network, xjj xtj = 0 Vy G Tj;-,Vi 6 0(j),j = 1,
4.2 Intra-link and Inter-link Solution (IIS)
Due to the complexity of multiple link case, heuristic algorithms are
developed in [2] [4] to find a near optimal solution. The solution consists of two
major steps. The first step is to find an assignment for each link which is called
Intra-link adjustments. The second step is Inter-link adjustments which integrates
the assignments for multi-link case. The details for those steps will be presented
in the next two sections.
38


4.2.1 Intra-link Adjustments
It would be helpful to apply the Optimal Solution mechanism steps that we
have presented in the single link case in order to assign a bandwidth for each
individual link. Unfortunately, we cannot do that because of the hug size of search
space especially when the number of involved clients is large. Instead, a simple
heuristic algorithm is proposed to approximate the optimal solution for each
individual link. The solution includes two steps. First, assigning bandwidth for
each class and then allocating the amount of bandwidth for each client in that
class. The outlines of the heuristic algorithm are:
1. We consider two classes that there are two types of per-hop behaviors,
which are the Expedited Forwarding and Assured Forwarding. The idea
can be used recursively to obtain bandwidth allocation for more than two
classes. Given Qj the total amount of bandwidth for each class.
2. For each class j and a given bandwidth Qj, find a good client assignment
for each link y £ r by applying these steps:
a. Build a list Si in the decreasing order of the ratio ujj/l\j for each
client i in class j where y E r^.
b. Starting from the first clients ratio in the list, check if we can
accept the client. The client i can be accepted if the condition
CY(J)/m > max{/[,..., l^nj) is satisfied, where Cy(j) is the total
bandwidth in class j in link y, m is the number of admitted clients
39


including client i and max^, is the maximum minimum
required bandwidth among all admitted clients. Repeat this step
until the list is empty. Denote the admitted clients list as Ai.
c. Calculate the total revenue ^from the admitted clients in Aj.
d. Build the list S2 in the decreasing order of uj, The list S2 is built
to solve the problem that the ratio ujj/1\- represents clients i base
price for the unit bandwidth, so the larger value of uJj/lJj
generates more revenue to the service provider. Then the larger
ujj/ljj value receives the higher priority, but it may happen that a
client requires a large amount of bandwidth and willing to pay a
high base price ujj. This client will receive a low priority because
his ujj/ljj is low, so the list S2 is built to detect the valuable
clients.
e. Apply the same procedure to S2 as in Si. Denote the admitted
clients list as A2 and calculate the corresponding total revenue f. Let (p = max{(p1,(p2} and A is the admitted clients list
corresponding to (p.
g. Another element that affects the revenue is wj^. When two clients
bid the same base price, the client with the higher wfj must have a
40


better chance to win the auction. For that reason, build a list S3 in
the decreasing order of w? for clients who are not in A.
h. Starting from the first client in S3, check if swapping client i with
each admitted client in A generates more revenue. If so, perform
the swap. Repeat until the half of S3 elements are left. It has less
impact on the admitted clients as w?j goes smaller.
i. Lastly, let xjj = CY(j) /m for all admitted clients to each link and
class.
After we get a bandwidth assignment for each link, Inter-link adjustments
step will use this initial solution to integrate a bandwidth assignment for all
required links for each client.
4.2.2 Inter-link Adjustments
The goal of the Inter-link adjustments step is to satisfy the constraint
that is the assignment bandwidth for each client has to be the same throughout all
links in the network. The outlines of the heuristic algorithm for Inter-link
adjustments that is proposed in [2][4] are as follows:
1. For each client i, set its assigned bandwidth to the lowest among all links
that is xtj = min{x^- : y G ri;}. After this is done to all clients, it may
happen that there is extra bandwidth left on some links. Next step is to
improve the solution quality.
2. Build a set f from all links that have extra bandwidth.
41


3. Start with the link y* that has minimum unused bandwidth, and build a set
r(j) from all links that are used by at least one admitted client in class j.
4. Find the maximum value x that satisfies myx + Cy < Cy, for each
y G rij, my is the number of admitted clients in class j on this link, x is
the additional amount of bandwidth that each client can obtain in class j
and Cy is the current used bandwidth in link y. It can be expressed as
x* maxjx: myx + Cy < Cy Vy G z(j) }.
5. Add x* to each client in class j.
6. Update the current usage for each related link and delete the link y* from
the set f.
7. Repeat The procedure to all links in the set f.
The detailed algorithm for IIS solution as described in [2] will be presented
next.
42


Algorithm 3. ( A heuristic approach for multi-link problem).
Given Q1 and Q2 the amount of bandwidth for both classes,
for j=l to 2 do
for each y G r do
Build a list Si of ujj/ijj for class j in link y where
uij/lij ^ " ^ u|0O')lj/fla)iy
Initialize m=1 and A] = 0.
for i=l to 100)1 do
Ai = Aj U {i} and m = m + 1.
if Cy(J)/m < max{/^: Vi G Ai} then
A] = A] \ {i} andm = m- 1.
end if
end for
Calculate the total revenue Build a list S2 of ujj for class j in link y where,
Perform the same procedure as Si and calculate (p2 corresponding
to A2
Let (p = max{^1( Build a list S3 for clients 00) \ A on link y where,
W1J > W\0(J)\A\jm
for i=l to [| 0O)\A| /2J do
Swap i with each element in A and confirm the swap if it
increases the total revenue.
43


end for
Set xjj = Cy(j)/m.
end for
end for // end for the Intra-link adjustments
for j=l to 2 do
for each i e 0(J) do
Let Xij = min{xj: y G ri;}.
end for
end for
Let Cy be the used capacity for each link y E r and f = [y E t Cy Cy>
0}-
while f 0 do
Let y* = min{Cy Cy y E f} and select a class j that uses link y* .
Let r (J) be the set of links y E t that are used by at least one admitted
client in class j.
let x* = max{x: mYx + Cy < Cy Vy G r(/)).
let Xij = Xij + x* for each i G 0(J) and update Cy, f.
end while // end of Inter-link adjustments.
44


4.3 Related Issue
By applying the Intra-link adjustments followed by Inter-link adjustments,
we guarantee that the amount of bandwidth for each client is the same among
all links in the routing path. This solution raised an issue in the multi-links
case. This issue is about what price the client will pay when he crosses more
than one link and gets the same bandwidth in all links because each link has
its own threshold. The approach that is presented in [4] proposes to set the
clients price to the highest price among all links thresholds. This approach
ensures that the client pays at most his own bid which is the benefit that we
get from applying auction as a pricing mechanism.
45


5. Comparison and Proposed Modifications
As we surveyed the literature about auction-based pricing mechanisms, we
could not find a paper that compares the auction-based pricing mechanisms
presented in this thesis. For that reason, we embark to present our own
comparison between the Smart Market, SPAC, and the Optimal Solution
mechanism for the single-link network. We propose some modifications and
directions for future work to enhance the discussed pricing mechanisms.
5.1 Comparison between Auction-Based Pricing Mechanisms
1. All the pricing mechanisms that we have presented so far are auction
based but they apply different kinds of auctions. The Optimal Solution
mechanism applies the sealed auction, where a client pays only the
threshold of the class of service that he is admitted to, while the Smart
Market and SPAC apply the second-price auction where the client
pays the second highest price, which is the highest price of the rejected
clients bids in that class.
2. Regarding the auction time interval, the SPAC does not consider the
case when a new client wants to join the auction after all users already
submitted their bids. Such a client has to wait until a new auction
interval starts. Whereas the Optimal Solution mechanism gives a
46


chance to a new client to be admitted by checking if his bid satisfies
the conditions of the current auction interval such as the threshold and
the bandwidth capacity. If so, the client is admitted. Otherwise, he has
to wait until a new auction interval starts.
3. The complexity time is a major factor. The SPAC is as fast as a sorting
algorithm. The Optimal Solution mechanism in the case of a single
link network takes time as 0(n2N+3) to allocate a bandwidth to all
admitted clients, where n is the number of clients, and N is the number
of classes of service that are offered by the service provider.
4. Although the SPAC mechanism is only applied for the out-profile
traffics and the in-profile traffics are charged for a flat fee, there is no
information about how to determine this base price. The Smart Market
also does not provide any information about that price. The base price
is part of the clients bid in the Optimal Solution mechanism.
5. The SPAC has a property which is a universal coverage. This property
means that all clients will be admitted even if they bid zero. If a client
bids zero, he will get the service with the lowest quality which is the
best-effort class. In the Optimal Solution mechanism, if a clients bid
is below the threshold, he will not get any bandwidth allocation neither
the minimum requirement nor the extra amount of bandwidth. In the
47


Smart Market, the packet is simply dropped if its bid is below the
threshold.
6. The Optimal Solution mechanism considers the service provider
revenue as the basic goal. The mechanism depends on how to
maximize this revenue by checking each users bid if it increases this
revenue or not. The SPAC considers the clients utility function as its
major goal beside the service provider revenue.
7. In the Optimal Solution mechanism, the class of service that a client
belongs to is predetermined, but it is based on all clients bids in the
SPAC mechanism. The number of admitted clients is predetermined in
the SPAC where the threshold determines how many clients can be
admitted in the optimal solution mechanism.
5.2 Proposed Modifications
Based on the comparison given above, we propose alternative approaches.
The goal is to enhance the pricing mechanisms.
5.2.1 Proposal Regarding the SPAC Mechanism
The SPAC mechanism does not provide information about how to set the
price for the in-profile traffic. The only information that we have about the
in-profile traffic is that it will be sold at a flat fee. The improvement that
we suggest in order to set price to the in-profile traffic is integration
48


between the flat-rate approach and the SPAC pricing mechanism. The
integration would work as follows:
o A user chooses the service level that the service provider offers,
such as the speed of the Internet connection, by entering an
agreement with a flat fee.
o During the peak time or if the user wants to submit an application
that needs more quality than he gains from the service provider, he
can participate with SPAC mechanism by setting his bid in order to
have a chance to get better quality. If the user got the quality of
service that he bids for, the in-profile traffic will be charged for the
flat fee as he has an agreement with the service provider. The
SPAC will be applied to price the out-profile traffic.
The advantages from this enhancement are:
1. The participation in SPAC becomes voluntary. A user has access to
unlimited usage of the Internet as the flat-rate approach offers. If the
user is not satisfied with the quality of service that he gained, he can
participate with SPAC to obtain better quality.
2. A shortcoming of SPAC that it does not specify how to price the in-
profile traffic is solved by applying the flat-rate approach to price it.
3. The user does not have to set an agreement with a high level service
and pays a high price each month. He can choose the service that
49


satisfies his minimum requirements and in case that he needs better
quality, he can apply the SPAC. For example, there is no need to
choose a service with 20 Mbps and pay $30 a month. Instead, he can
choose 12 Mbps for $20 a month and pay extra by participating in
SPAC as he needs.
4. The service provider revenue will be increased by getting the flat fee
plus the extra fees each time the user participates in the SPAC. Also,
the users will be satisfied all the time because they have a choice either
to pay extra fee or not.
Although the integration between the flat-rate approach and the
SPAC pricing scheme has many advantages, the challenge of applying this
integration is:
We need to implement the SPAC as a new component to the flat-
rate approach. Up to now, the SPAC mechanism is still at the theoretical
level. Shu and Varaiya claimed in [10] that SPAC needs a dynamic
configuration for the IP routers. Currently, a manual configuration is
applied to manage the IP networks. They developed software for a
network management that supports a dynamic configuration for IP
networks, but we still need software to integrate the requirements for both
flat-rate and SPAC mechanisms.
50


5.2.2 Proposal Regarding the Optimal Solution Mechanism and the IIS
Algorithm
The Optimal Solution mechanism for the single-link network and the IIS
algorithm for the multi-links network can be developed to include not only
a bandwidth allocation problem but also another quality of service
parameters such as packet delivery. This can be done by adding some
factors to the revenue function. Also, this idea can be applied to the SPAC
mechanism to support more quality of service parameters beside the
packet delivery rate such as the latency.
As we have mentioned that in the optimal solution a client is either
admitted in class j or rejected. We can enhance this disadvantage by
giving the rejected users two choices:
o The first choice is to submit same bids to a lower class which is
next to class j. The advantage of this choice is that the user will
have a chance to be admitted and get at least his minimum
requirement of bandwidth.
o The other choice is that to let them wait until a next auction
interval starts and submits a new bid with the same class j if they
really need to be served at that specific class. With this choice the
rejected users will have higher priority to join the new auction
interval than the new users.
51


Finally, all the pricing mechanisms that we presented consider only one
service provider. In other words, the pricing mechanism is only applied by one
service provider. The user either wins the auction and gets the service that he
needs or not. If the user can submit his bid value to more than one service
provider at the same time, he may be admitted by one service provider while
he is rejected from the other. In other words, if a client submits a bid to the
service provider and this bid is below the threshold, he can submit the same
bid to different service provider to have chance to win the auction and get that
service. This enhancement will increase the competition between service
providers which benefit the users.
52


6. Conclusion
The popularity and growing use of widely spread of applications such as
video conferencing makes the Internet move from providing one level of service
(best effort) to different classes of quality of service. This can be facilitated by
pricing and resource allocation strategies to improve the quality of service and the
service providers revenue. In this thesis we surveyed researches about pricing as
a solution to the resource allocation problem and control of congestion. All the
pricing mechanisms that we have presented are auction-based. The following
table shows the features of the pricing mechanisms that we have studied in this
thesis:
Table 6.1 The features of the auction-based pricing mechanisms
The mechanism The Description
Smart Market This mechanism applies the second-price auction to solve the resource allocation problem in the congested network. It views the network as an auction market. The router is an auctioneer and the clients who want to send their packets across this router are the bidders. A client submits the bid which is the price that he is willing to pay in the bid field in the packet header. Each router offers a threshold value. The router admits only clients whose bids are higher than the threshold.
53


Table 6.1 (Cont)
The admitted clients are ordered before they pass the router according to their bid values. The main shortcoming of this mechanism is that the priority that it is given to the admitted clients may lead to re-order the packets. The packet re-ordering and the large amount of auctions that have to be done for each packet to transmit the network make this mechanism considered as unsuitable for the real networks.
SPAC This mechanism applies the second-price auction to solve the resource allocation problem in the network. The basic idea of this pricing mechanism is to mark packets according to their value to the service. Packets will be served differently according to their marks which mean that packets with the same marks will be served at the same quality of service. The best strategy to the client is to bid the true value to the service. SPAC is applied as a pricing scheme for DiffServ where the packets are marked at the edge of the network. In the interior of the network, packets are treated differently according to the marking. SPAC considers as a congestion control mechanism where users pay the congestion fee that they are served at certain quality of service. Users who valued the service less will be served at the best effort quality and the congestion fee will be zero. This mechanism is called universal coverage.
The Optimal Solution mechanism for the single-link network This pricing mechanism gives an optimal solution for the bandwidth allocation in DiffServ under the assumption which is the network can be modeled as a single bottleneck link. The sealed auction is applied in this mechanism. The service provider offers different classes of service. The clients bid on the minimum required bandwidth, the price that they are willing to pay for their minimum requirements and the price for any extra unit of bandwidth.
54


Table 6.1 (Cont)
The service provider decides the admission price and the service threshold for each class based on all clients bid and the available resources.
IIS It is a heuristic algorithm to allocate the bandwidth in multi-links network in order to maximize the service provider revenue. The main feature of this approach is that it considers the bandwidth assignment consistency across all links for the same clients routing path. This approach works under the assumption that the clients bid and the routing path are given. The clients bid is assumed to be valid for all links across the routing path. This approach finds the near optimal solution to allocate the bandwidth in two steps. The first step which is called Intra-link adjustments is to allocate the bandwidth for each link. The second step which is called Inter-link adjustment is to integrate the bandwidth allocation across all links for each client.
Auction-based pricing strategies control the congestion and allocate
network resources in an efficient way. They are not applied in the existing
networks since they need some special requirements such as dynamic
configuration to the IP routers instead of manual configuration which is applied
now. In the previous chapter we suggest the integration between the flat rate
approach and the SPAC to provide information about how to set the base price.
We also present the advantages and challenges of this integration.
All the mechanisms that we have presented support only one parameter of
quality of service. As the SPAC support the packet delivery, the Optimal Solution
55


mechanism in both single-link and multi-links network supports the bandwidth
allocation. Our suggestion was adding new parameters to the revenue function to
support more quality of services parameters.
56


REFRENCES
1. Blake, S, Black, D, Carlson, M, Davies, E, & Weiss, W, (1998). An
architecture for differentiated services. Internet Engineering Task Force
(IETF) Reference RFC 2475.
2. Blough, D, Guan, Y, Owen, H &Yang, W (2008). A pricing approach for
bandwidth allocation in differentiated service networks. Computer &
Operation Research, 35(12), 3769-3786.
3. Blough, D, Owen, H, &Yang, W (2005). Determining differentiated services
network pricing through auctions. In Lorenz,P & Dini,P (Eds.), Networking-
ICN2005 (pp. 802-809).
4. Blough, D, Owen, H, &Yang, W (2004). A comparison of auction and flat
pricing for differentiated service networks. IEEE International Conference
on Communications, 4, 2086-2091.
5. Jin, N & Jordan, S (2008). On the feasibility of dynamic congestion-based
pricing in differentiated service networks. IEEE/ACM Transaction on
Networks, 16(5), 1001-1014.
6. Kalyanaraman, S &Yuksel, M (2002). A strategy for implementing smart
market pricing scheme on diff-serv. In Proceeding of the IEEE Conference
on Global Communications, 2, 1430 1434.
7. Mackie-Mason, J, & Varian, H. (1995). Pricing the Internet. In Kahin, B &
Keller, J (Eds.), Public Access to the Internet (pp. 269-314).
8. Marbach, P. (2001). Pricing differentiated services network: bursty traffic. In
In Proceedings of IEEE INFOCOM 01 (pp. 650-658).
9. Schulzrinne, H &Wang, X (2006). Pricing network resources for adaptive
application in a differentiated services network. IEEE/ACM Transaction on
Networks, 14(2), 506-519.
57


10. Shu, J & Varaiya, P(2006). Smart pay access control via incentive alignment.
IEEE Journal on Selected Areas in Communications, 24(5), 1051-1060.
11. Shu, J & Varaiya, P (2003). Pricing network services. In Proceeding of
INFOCOM, 2, 1221-1230.
58