Auction based algorithm for Network Bandwidth Allocation Problem
BTP term1 report
Project Adviser Prof. Sumit Ganguly sganguly@cse.iitk.ac.in November 9, 2008
Anupam Ashish Y5101 anupash@cse.iitk.ac.in Naveen Kumar Kushwaha Y5274 naveenk@cse.iitk.ac.in
Abstract
Auction Algorithms have been used to solve the general assignment problem in [1].They have been used in more than one ways to solve resource allocation problems. They are pretty useful if the existing deterministic algorithm are NPhard
Auction based algorithm for NetworkBandwidth Allocation Problem
BTP term1 report
Project Adviser
Prof. Sumit Gangulysganguly@cse.iitk.ac.inNovember 9, 2008
Anupam Ashish Naveen Kumar KushwahaY5101 Y5274anupash@cse.iitk.ac.innaveenk@cse.iitk.ac.in
Abstract
Auction Algorithms have been used to solve the general assignment problem in [1].They have
been used in more than one ways to solve resource allocation problems. They are pretty useful if theexisting deterministic algorithm are NPhard as we can design heuristics based on auction mechanismto get a nearly optimal solution. Network bandwidth allocation problem can be transformed toassignment problem and solved using method given in[1]by converting it to ﬂow problem or we
can propose another auction based mechanism to solve a bandwidth allocation problem. Here weare trying to solve a bandwidth allocation problem where
K
sourcesink pair wish to communicatewith each other. We have been motivated by [1]and an another auction algorithm to solve this
problem.
Introduction
Auction based algorithm are being used extensively these days in problems where the deterministicalgorithm takes too much time. Bandwidth allocation for users in a network is one of such kindof problem.There are many variations to the Network bandwidth problem in which auction basedmechanism can be applied.
Model of a simple Auction
Suppose A service provider wants to sell the bandwidth at a single link in the network.There is a ﬁxedamount of for the available bandwidth.But many users want to get the bandwidth.So demand forthe Bandwidth would be more than the Available. So to allocate the Bandwidth Service providerwill start an auction. Auctioneer suggests a price and bidder bids for the amount of bandwidthwhich they want to get at this price.This is one simple notion of an auction.There are variety of techniques for Auctions. Some famous types of auctions are English vs Dutch, Single Dimensionalvs Multi Dimensional, Sealed bid vs Closed bid, Single sided vs Double sided, ﬁrst price vs secondprice(VCG). A brief introduction about auctions can be found in [3].
1
Motivation & Literature
Bertsekas’s Survey on Network Flow problems [1]
The prototypes being used here is auction algorithms for assignment problems. These auctionwork like real life auctions where persons/bidders compete for the objects by increasing their pricesthrough competitive bidding.
Naive Auctions
Two types of problem exists here one is the symmetric assignment and second is asymmetric assignment. In the ﬁrst problem n bidder matches for n object and assignment is oneone while later inlater problem a bidder may have more than one objects.To simulate an auction we will introduce a beneﬁt
a
[
ij
] for matching bidder i to object j. So hereour aim is to maximize the total beneﬁt
n
0
a
[
ij
] .We have given a set A of (i ,j) that can be matched .So we have
A
(
i
) =
{
j

(
i,j
)
∈
A
}
(1)
B
(
j
) =
{
i

(
i,j
)
∈
A
}
(2)Solution to this problem would be the a set S congaing pairs of (i,j) where S is such that
S
=
{
(
i,j
)

object
j
is assigned to some person
i
}
And this assignment would be feasible if set S has n elementsand each bidder ’i’ is assigned to a distinct object ’j’. The Algorithm tries to optimize this feasiblesolution by maximizing the total beneﬁt
n
0
a
[
ij
].Now we associate price with each object. So if anobject j has price P(j) then value for person i for that j object is
a
[
i,j
]
−
P
(
j
).Each person tries tomaximize his value.
a
[
i,j
k
]
−
P
(
j
k
) = max
{
a
[
i,j
]
−
P
(
j
)
}
is satisﬁed for all pairs in assignment. If all bidders areassigned then algorithm terminates.Otherwise notempty subset of unassigned persons is selectedand computation for the best is performed.Let I be that non empty subset. Each person i in I ﬁnds object j in A(i) for which its value ismaximal. bidding increment is
γ
i
=
v
i
−
w
i
where
v
i
is the value of best object for i and
w
i
is value of second best object for i .
w
i
is
−∞
if noother object is there.Note that
γ
i
can never be negative.Here is a situation where this algorithm fails to work .Suppose we have two equally qualiﬁed objectfor a person .In that case will be zero and hence algorithm inters in next iteration without raisingobjects prices. Hence algorithm gets into a cycle. To break such cycle there is a concept of
complementary slackness mechanism .In this mechanism each bid must increase the price of anobject by some minimum positive increment
.So here
γ
i
will be equal to
v
i
−
w
i
+
.
Network Bandwidth Allocation over paths [2]
This paper gave us deep insight into the problem of Network Bandwidth Allocation. We haveextended the problem solved by them and gave a solution for a modiﬁed problem. He explores theproblem using Dutch auctions. He solves the problem to a general topology network. Approach isto run auction simultaneously at each node for the bandwidth allocation. Although each auctionruns independently.They deﬁne a price reduction policy called price Freezing. Price Freezing policysays that when allocation of bandwidth takes place price at that link will freeze for some time of period. In Price reduction price at time
t
at a link
l
will be as
P
l
(
t
) =
P
l
(0)
−
r
∗
[
t
−
s.x
l
(
t
)] where
r
and
s
are constants.
x
l
(
t
) is the allocated bandwidth at link
l
.
P
l
(0) is the initial price set.For thesupport of their Mechanism they had given three simple propositions.
Proposition 1:
There exist a choice for initial prices for the various links such that at any time ,for every pair of links for none of which prize are frozen , link with lowest remaining capacity hasthe highest price.2
Proof:
Suppose at time t remaining capacity at link
i
is less then at
j
ie.
C
i
−
x
i
(
t
)
< C
j
−
x
j
(
t
).For having
P
i
(
t
)
> P
j
(
t
) condition
P
i
(0)
−
rt
+
rs.x
i
(
t
)
> P
j
(0)
−
rt
+
rs.x
j
(
t
) (3)
P
i
(0) +
rs.
[
x
i
(
t
) +
C
i
−
C
i
]
> P
j
(0) +
rs.
[
x
j
(
t
) +
C
j
−
C
j
] (4)
P
i
(0) +
rsC
i
]
rs
[
C
i
−
x
i
(
t
)]
> P
j
(0) +
rsC
j
]
rs
[
C
j
−
x
j
(
t
)] (5)as r.s
≥
0 this condition is true for
C
i
−
x
i
(
t
)
< C
j
−
x
j
(
t
)
Proposition 2:
The Maximal execution time for algorithm is proportional to the link’s initial priceand capacity.
Proof:
As auction will terminate at Price = 0 .So
P
i
(0)
−
r.t
0
i
+
r.s.x
i
(
t
0
i
)set
x
i
(
t
0
i
) =
C
i
we get
t
0
i
=
P
i
(0)
/r
+
s.C
i
Proposition 3:
Algorithm allocates bandwidth eﬃciently if optimal price of links are already known.
Proof:
Let optimal price at link i is
P
∗
i
and allocation with respect to it is
x
∗
i
(Computed by LagrangeMultipliers) we have
P
i
(0) =
P
∗
i
+
rt
−
rs.x
∗
i
Algorithm works in two stages 1. Users submit their bidwith their demand. 2.The auctioneer will decides on price vector when should auction will end.Thenhe can decide the optimal point of termination. Bidders are then allocated and charged accordingto VCG rule. The criteria of optimization may be either the Revenue Maximization or the SocialWelfare. They have not proven any optimality constraints.They showed that experimented resultsare better than other techniques.
Problem Statement
Given a network represented by graph
G
= (
V,E
) where
V
is a ﬁnite set of vertices/nodes and
E
is the set of edges/arcs. Each edge
e
ij
where
i,j
element of
V
has a capacity
c
ij
and a cost/price
p
i,j
. Let there be a set of pairs of source and sink
S
k
= (
s
k
,t
k
) each with a supply and demand.
S
k
,source and sink pair represent two modes who want to communicate with each other. The problemis to ﬁnd a minimum cost allocation of bandwidth across the network.It can be mathematically stated as :
min
i,j
k
f
(
e
kij
)
∗
p
ij
where
f
(
e
kij
) is the bandwidth corresponding to
S
k
in the edge
e
ij
j

(
i,j
)
∈
E
f
(
e
kij
)
−
j

(
j,i
)
∈
E
f
(
e
kji
) =
f
(
S
k
) if
i
=
s
k
−
f
(
S
k
) if
i
=
t
k
0 otherwise(6)
k
f
(
e
kij
)
<
=
c
ij
f
(
e
kij
)
>
= 0It can be seen that the number of variable here are equal to the number of arcs multiplied by thenumber of pairs
S
k
. Hence as the number of variables gets bigger and bigger the time to solve evengets bigger.This problem can directly model a network where there are nodes ready to communicate with eachother. And we have to ﬁnd the minimum cost allocation of bandwidth to such nodes so that theycan communicate. The problem can be varied with integral bandwidth or nonlinear cost function.3
Auction Algorithm
There can be various such approach such ﬁrst ﬁnding a feasible solution and iterating it to get asolution close to optimal. But our algorithm would ﬁrst ﬁnd an optimal solution for each
S
k
andthen combine them to get a feasible solution.
1.Basis
We run the mincost ﬂow algorithm individually for each
S
k
. Hence ﬁnd an individual optimalsolution which corresponds to and optimal path. Now we would look at the conﬂicts at the commonedges i.e for any edge
e
ij
there are more than
S
k
who are interested in taking that path. One suchpath is chosen and the algorithm start with it.
2.Auction/Bidding
ã
Begin:
Each of
S
k
who have a conﬂict at the corresponding edge
e
ij
and satisfy the conditionfor bidding would have to bid for the link/edge keeping in mind it’s usage and the cost of avoiding it. The bid value for each of
S
k
can be evaluated by solving a new mincost ﬂowwithout the current edge, then subtracting it with the current optimal value.Condition for bidding : If the some of the ﬂows/bandwidth allocated to all
S
k
at the edge doesnot exceed the capacity then there will be no bidding, otherwise we have to have bidding inorder to determine the winner.
ã
End:
The main program determines the winner of the bid. The edge/link is then assigned tothe winner of the bid. The losers have to change the maximal capacity in that arc to zero.Note that we have determined only one winner and all other are kicked out.
ã
Reopen Auctions:
Some of the
S
k
lost their bid and have to consider changing their routeand therefore they can reconsider their bids on previous auctions. In such cases the previousauction can be reopened and the capacity of the arc/edge be changed to the srcinal value.
3.Updating and Iteration
After all the capacities are updated then each of
S
k
solve their (adapted) mincost ﬂow. If therestill remains some arc/edge which has a conﬂict then return to step 2. Otherwise stop.
Proof and Termination
The algorithm will work only if the output is an optimal solution given feasible solution exists. Sowe have to take care of the feasibility and the optimality.
Termination
It is easy to see that the algorithm never terminates if the solution is not feasible. This happensbecause algorithm will keep on iterating till all the conﬂicts have been removed. We now look atthe number of conﬂicts. The number of conﬂicts is equal to the maximal number of conﬂicts perarc/edges multiplied with the number of arcs/edges. Moreover the maximal number of conﬂicts perarc/edge depends on the maximal number of auctions started by
S
k
(source,sink pair) multipliedwith the number of such pairs,
S
k
.
S
k
starts a new auction if it has lost an arc/edge and migratesto some other arc where it again faces conﬂict. So essentially the number of times
S
k
will reopenan auction is the number of edges/arcs. So the maximal number of auctions are

E

2
.

K

K
isthe number of pairs
S
k
and

E

is the number of arcs/edges. So unless there are inﬁnite number of arcs/edges or number of pairs
S
k
the termination time will be bounded.4