Term 1 Final

 Documents

 21 views
of 5
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
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 NP-hard
Share
Tags
Transcript
  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 NP-hard 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 flow 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  source-sink 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 fixedamount 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, first 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 assign-ment. In the first problem n bidder matches for n object and assignment is one-one while later inlater problem a bidder may have more than one objects.To simulate an auction we will introduce a benefit a [ ij ] for matching bidder i to object j. So hereour aim is to maximize the total benefit  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 benefit  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 satisfied for all pairs in assignment. If all bidders areassigned then algorithm terminates.Otherwise not-empty subset of unassigned persons is selectedand computation for the best is performed.Let I be that non empty subset. Each person i in I finds 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 qualified 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 modified 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 define 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 efficiently 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 finite 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 find 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 find the minimum cost allocation of bandwidth to such nodes so that theycan communicate. The problem can be varied with integral bandwidth or non-linear cost function.3  Auction Algorithm There can be various such approach such first finding a feasible solution and iterating it to get asolution close to optimal. But our algorithm would first find an optimal solution for each S  k andthen combine them to get a feasible solution. 1.Basis We run the min-cost flow algorithm individually for each S  k . Hence find an individual optimalsolution which corresponds to and optimal path. Now we would look at the conflicts 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 conflict 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 min-cost flowwithout the current edge, then subtracting it with the current optimal value.Condition for bidding : If the some of the flows/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) min-cost flow. If therestill remains some arc/edge which has a conflict 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 conflicts have been removed. We now look atthe number of conflicts. The number of conflicts is equal to the maximal number of conflicts perarc/edges multiplied with the number of arcs/edges. Moreover the maximal number of conflicts 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 conflict. 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 infinite number of arcs/edges or number of pairs S  k the termination time will be bounded.4
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks