WIXLIB

Profit OptimizationUnit Utility at steady state : u( p) ( p ω)Y Our method of Providers’ ProfitOptimization:–Design Traffic-EngineeredNetwork to Guarantee QoS– Minimize congestion sensitivecost ( Y)– Select strategically appropriateprice by Game TheoryMaximize u(.)Network Architecture Constraints.t. Internet Traffic Pattern and Queue System ConstraintGame Strategy ConstraintMaximize u( p) Max ( p ω)YMax pY Max ( ωY )(Maximize pY Minimize ωY )Marginal CostTime (t)profitn Network Throughput (Y)ThroughputTime (t)dtProfit ( u(.))(.))Marginal Cost ( (.)) kMaximize u( p)( p s , t , k ω n , s , t , k ) d n , k yn , s , kp: call unit price: call marginal costd: call durationy: call bandwidthdtUnit-Profit-ProfitMarket Price to maximize revenue (pY)Price (p(.))Max ( p ω)Y21dtdt

AlgorithmSealed Bid Reverse AuctionProtocol(Signaling & Control Layer)Find bid price based on providersStrategy: P H(F(p))Perform Non-CooperativeGame of Oligopoly to developBelief Function: F(p) G( )Find bid price based on providersStrategy: pb H(F(p))Perform Minimize Marginal CostGame of Oligopoly to develop byPerformBelief Function: F(p) G( Optimum, , )Traffic RoutingApproximateDevelop CongestionDevelop OptimumDemandSensitive Cost: (M*)Mean Function:Number of (Y)Packets (M*) for Y(Based on Queuing Theory (e.g. M/M/1))Minimize Marginal CostbyBased onOptimum Traffic Routing MathematicalNon-Linear ProgrammingApproximate (GradientProjection Method andGolden Section Line Search)OptimumMean Number of Packets (M*) for Ymco.(Based on Queuing Theory (e.g. M/M/1))ACustomerDomainBearerLayeromcB.Traffic Engineering RuleBasedEnforceonNon-Linear Programming Based on(Gradient ProjectionQueuingMethod andTheory (e.g. M/G/1)Golden Section Line Search)QoS GuaranteeEnforce Traffic Engineering RuleBased on Queuing Theory (e.g. M/G/1)22

QoS Guarantee We develop TE Rules to guarantee mean delay less than 1 msec.– Homogeneous services Link Load (Green) 90%– Heterogeneous Services Link Load (Blue) 20% Link Load (Green) 30% Link Load (Red) 40%Based on M/G/1 SystemE[τ b ] E[ Lg ]E[ Lb ]E[ Lr ], E[τ g ] , E[τ r ] CCCE[ Lb ]E[τ ] 2.C2b2, E[τ ] 2.2gE[ Lg ]CλgλbλE[τ b ] E[τ g ] v E[τ r ]λλλλgλλE[τˆ 2 ] b E[τ b 2 ] E[τ g 2 ] v E[τ r 2 ]λλλE[ Ls ]λ E[τˆ 2 ] E[Ts ] 2(1 λ E[τˆ])CE[τˆ] 2M/G/1 System Delay1.61.4E[ Lr ], E[τ ] 2.C2r21.2System Delay: E[τ](msec) BlueGrenRedρb 20%ρg 30%ρr 5% -- 45%10.80.60.40.200.550.60.650.70.750.8Link Utilization (ρLINK)0.85230.90.95

Service Cost Function Assumption: Following four influences on the service cost:– Congestion in the network Degrades the service quality– causes the delay in packet transmission. The degradation of service is detrimental to the revenue Providers have to pay to the Enterprise for jitter (Expense An indicator of network congestion– Mean packet count (M) in the queue system– Protocol used to provide a service Service cost coefficient ( s)– Amount of service (commodity) Throughput (Y)– Providers’ fixed cost ( )Costn , s ,t (Yn ,t ) g (Yn ,t ) δ s Mˆ n ,tYn ,t θ nYn ,tf (Yn ,t ) M n ,t24

Minimize CostA Cost Function assumption Service cost is a functions of network congestion Mean packet count in network queue system is a congestion indicatorMinimize ωn ,t Minimize {δ s (Yn ,t Mˆ n ,t Yn ,t Mˆ n ,t ) θ n }Minimize Mˆ optimize network traffic routes applying nonlinear programMinimizeYn ,t Mˆ n ,t Yn ,troute optimization loadbalances and reduces change in Mˆ in low loadn ,t25

Minimize Marginal Cost Minimize Congestion Cost by Optimum Routing Method– Minimizing Mean Packet Count Mean Packet Count (M/M/1 Model):Mˆ j:l jE[ packets ] l Non-Linear Program:Minimize : Mˆ j :l jlSubject to :j :l JCl xjj :l jCl xjj:l jxjxjx j ρ TE C lj J ( w )x j rwxj 0We implement Gradient Projection and Golden Section line searchto satisfy Karush-Kuhn-Tucker conditionIn each game instance (each request for bid), this optimization is performed(See dissertation for details, we provide highlight in next three slides)

NonNon-linear Program: 1 x231 x241 x2431 x2341 r21 egion#3x12 x132 x142 x1342 x1432 r12 egion#1Region#1(Chicago)(Chicago)3002100x31 x321 x341 x3421 x3241 r31 0x14 x124 x134 x1324 x1234 r14 0E-LSR100NSP1NSP1x13 x123 x143 x1243 x1423 r13 0300100[H] lanta)(Atlanta)x41 x421 x431 x4231 x4321 r41 0x42 x412 x432 x4132 x4312 r42 0x24 x214 x234 x2314 x2134 r24 0x23 x213 x243 x2143 x2413 r23 0x32 x312 x342 x3412 x3142 r32 0x34 x314 x324 x3124 x3214 r34 0x12 x123 x124 x1243 x1234 x312 x3124 x3412 x4123 x412 x4312 ρTE C12 0 x43 x413 x423 x4213 x4123 r43 0x21 x321 x421 x3421 x4321 x213 x4213 x2143 x3214 x214 x2134 ρTE C21 0x13 x134 x213 x413 x132 x1342 x1324 x4132 x2134 x2413 x4213 ρTE C13 0x31 x431 x312 x314 x231 x2431 x4231 x2314 x4312 x3142 x3124 ρTE C31 0x14 x142 x214 x314 x143 x1432 x1423 x2314 x3214 x3142 x2143 ρTE C14 0G Inequality x41 x241 x412 x413 x341 x2341 x3241 x4132 x4123 x2413 x3412 ρTE C41 0x42 x142 x342 x421 x423 x1342 x1423 x3142 x3421 x4213 x4231 ρTE C42 0x24 x241 x243 x124 x324 x2431 x3241 x2413 x1243 x3124 x1324 ρTE C24 0x23 x231 x234 x123 x423 x1234 x1423 x2314 x2341 x4123 x4231 ρTE C23 0x32 x132 x432 x321 x324 x4321 x3241 x4132 x1432 x3214 x1324 ρTE C32 0x34 x134 x234 x341 x342 x1342 x1234 x2341 x2134 x3421 x3412 ρTE C34 0x43 x431 x432 x143 x243 x2431 x4321 x1432 x4312 x1243 x2143 ρTE C43 0xp: BW of an LSPEach O-D pair has Five LSPs.Total: 60 LSPs in each providernetworkCl: Capacity of each linkTE: TE loadG non neg . { x j 0, j J27

NonNon-Linear Program: Initial Feasible Point Gradient Projection Method requires an initial feasible vector (X0)Determine: New Session Route Vector (NV)– Minimum Hop Routing Step 1– Select the shortest path (one hop route) If fails Step 1, Step 2– Select either of the two hop route with equal probability If fails Step 2, Step 3– Select either of the three hop route with equal probability Anticipated Route Vector (Current Route Vector) NV Initial feasible vector (X0)Anticipated Route Vector28

NonNon-Linear Program: Gradient Projection SnapshotInequality Constraints:(12 60)G Inequaltiy(60 60) G Non negativeY (60 1)Equality Constraints:(12 1)ρTE C(60 1) 0Working Matrix: [ 72 1 0][ W] [ 12 60 H LSP ][ 60 1Y ] [ 12 1 R ] [ 12 1 0][ 12 1 H ] [ 12 1 0]G ActiveHThis working matrix is the foundation of the working surface (Aq)Direction of movement (d) is found as follows:P I AqT ( Aq AqT ) 1 Aqd P f (x)TFind Maximum distance (Max):ginactive (x) α Max ginactive (x)d bUse Golden Section Line search to find optimum point in each feasible segment:Minimizef ( xk α k d k )s.t.[ A] [ b ]Minimum is achieved at dk 0 and λ 0 such that the following FONC is satisfied f (xk ) λkT Aq 029

NonNon-Linear Program: Output Output of Non-linear program– Optimized Mean Packet CountM̂ *– Optimum Routes– Fair Load Distribution Inside the Network- Minimization of Cost30

Minimizing Change in CongestionMinimize Mˆ n ,t Yn ,troute optimization loadbalances and reduces change in Mˆ in low loadn ,tWith Optimization0.12Network Load (δn) 38%Network Load (δn) 38%0.1Change in Mean Number of PacketsChange in Mean Number of Packets0.10.080.060.040.020Without Optimization0.1200.511.5Simulation Time24x 100.080.060.040.02000.511.5Simulation Time24x 1031

Congestion Sensitive Optimized Marginal CostWe develop the Marginal Cost Functionfromthe Optimized Mean Packet Count (M*):ωns ,t ( Mˆ ) δ s (Yn,t*n ,t Mˆ n*,t 1Marginal Cost (ω) and Cost Coefficient (δ)140140120120100δb 1.0806080202000.40.5 0.6 0.7 0.8Network Load (ρNetw ork(Y))Ω r 70δg 0.1δr 0.01Provider MˆY Mˆ 1,* t ) 101.00(1,t1 Y1,t0.10(Y1,tProvider Mˆ *2,tY1.00( Mˆ *2,t ) 102,t2 Y2,t0.10(Y2,tMˆ n*,t 1 Mˆ n*,t(bOD bDO )Simulation0.5 0.6 0.7 0.8Network Load (ρNetw ork(Y))Green*1,t Yn ,t Mˆ *n,t ) θ nThree classes (Blue, Green, Red)Cost coefficient parameterdepends on security levels(High, Medium, Low) Cost coefficient parameterdistinguishes Service ClassMean Packet Count: M/M/16040BlueΩ g 1001004000.4 Yn ,t 1160Ω b 160Marginal Cost (ω(Y)Marginal Cost (ω(Y)160 Mˆ *n ,tRed Mˆ*1,t Y1,t Mˆ *2,t Y2,t Mˆ 1,* t ) 100.01(Y1,t Mˆ *2,t ) 100.01(Y2,t Mˆ 1,* t Y1,t Mˆ *2,t Y2,t Mˆ 1,* t ) 10 Mˆ *2,t ) 1032

Game Theory Model Our Model is Our models extends– Based on Bertrand Oligopoly Model– A Myopic Markovian-Bayesian Static Game of Incomplete Information– Bandyopadhyay et al. On-Line-Exchange ModelBandyopadhyay et al. On-LineExchange Model Our Model:– Based on Bertrand Model and “ Modelof Sale” example– Extension to Bandyopadhyay et al.model– Symmetric market– Asymmetric market All parameters are fixed Demand and cost are functions of thedynamic nature of Internet traffic– Commodity is not Internet bandwidth– Commodity is internet bandwidth– Two step static game of incompleteinformation– “ Myopic” Markovian static game ofincomplete information– Homogeneous service– Heterogeneous service– Uses Reinforcement Learning (RL) insimulation to determine best strategy– An analytical framework to determinethe best strategy in dynamic internettraffic33

Oligopoly Model Selection Oligopoly– A small number of providers collectively influence Market condition such as price, capacity– A single provider alone cannot completely control the marketTwo well-established fundamental models of Oligopoly– Bertrand Model Strategic Variable: Price Strategic Variable: Capacity (quantity)– Cournot Model34

Oligopoly Model In the Internet, providers strategically interact– Long term: Adds more capacity, i.e. “ bandwidth wars” Price adjustment in fixed capacity, i.e., “ price wars”– Short term: Our Model is based on Bertrand Oligopoly Model– Short term Session arrival and departure in a relatively short time period– Capacity does not change during the game– Providers adjust price to win over customers– Customers subscribe to the service from the lowest priced provider.35

Game Model Selection Game Theory– The mathematical theory pertaining to the strategic interaction of decision makers There are four fundamental classes of gameGame ClassEquilibriumStatic Game of Complete InformationDynamic Game of Complete InformationStatic Game of Incomplete InformationDynamic Game of Incomplete InformationNash EquilibriumSubgame-perfect Nash equilibriumBayesian Nash equilibriumPerfect Bayesian Equilibrium Complete Information: Providers’ payoff or strategies are common knowledge Incomplete Information: At least one player is unware of the payoffs or strategies of other providers Static Game Players simultaneously interacts (chooses actions) without the knowledge of past Dynamic Game Players repeatedly interacts based on the knowledge of game history (e.g., payoff)36

Game Model Our model is Myopic Markovian-Bayesian Game of Incomplete Information– Each provider is a rational player– Each provider’s payoff is private information.– All providers simultaneously select bid price without past knowledge of payoffs– “ Myopic Markovian” Each session is an instance of the gameGame uses one step nearsighted information Developed based on Bayes’ Conditional Probability Rule– The game is also known as Bayesian Static Game of Incomplete Information37

Game Parameters Our Game Parameters–––––––––Strategic Players : A few Internet Service ProvidersStrategic variable : Bid Price (pbid)Commodity: the bandwidth of services in the InternetServices: Homogeneous/Heterogeneous (Plat., Gold, Silv.) ServicesCapacity: Peer capacity in bw (Fixed)Demand: Sensitive to Internet traffic throughput (Variable)Marginal Cost: Sensitive to network congestion (Variable)Customer’s limited Budget: Reservation price (Fixed)Payoff: Profit38

Bayesian Static Game of Incomplete Information Static Bayesian Game of two Providers ( A.com, B.com)– In Static Bayesian game, a provider’s strategy is to maximize its’ expected Profit– G {ActionA, ActionB; TypeA, TypeB; BeliefA(), BeliefB(); PayoffA(), PayoffB()} Action Bid price (pbid)Type Provider’s marginal cost ( )Payoff Expected Profit (E(u(.))BeliefA(.) ProbA(TypeB TypeA)– A.com’s belief or uncertainty of B’s Type given that A.com knows own type– It is a conditional probability function– It is also referred to as the Mixed Strategy Profile– A.com develops a set of feasible strategies from the belief function:strategy h Aj : Action A h Aj (., Belief A (.))39

Game Model: Belief functions and Strategies The Belief function is the main entity of this GameBelief Function: FA(p):–is the Rejection probability of A.com for A’s bid price p. A.com’s belief of B.com’s winning probability for A.com’s bid price pAFA ( p Abid ) Prob( pB p bidA ) Strategy space h is the set of functions over F(p)– Strategy is identified by the rejection probability A Strategy, hAj “ 95% probability of having the bid rejected”pnbid,s,t : Fn,s,t ( pnbid,s,t ) prob( p pnbid,s,t ) 0.9540

Belief Function (F(p)) Belief function– It is a cumulative distribution function F(p) FA(p)–A.com’s belief of B.com’s winning probability for A.com’s bid price pAbidFA ( p bid) Prob(p pABA )– A.com’s probability of having its pA bid rejected The Rejection probability of A.com A.com’s rejection probability 90%bidFA ( p bid) Prob(p pABA ) 0.90 A.com believes that B.com will select bid-prices at most pA with 90%probability A.com’s winning probability 10%41

Strategy Strategy space h is the set of functions over F(p)––The strategy space is constructed from the Type and Action spaceA.com’s set of strategies hAj is the set of all possible functions with domain (input) TypeA and range(output) ActionA.strategy h Aj : Action A h Aj ( Belief A (., Type A )) A Strategy, hAj “ 95% probability of having the bid rejected”pnbid, s ,t : Fn , s ,t ( pnbid, s ,t ) prob( p pnbid, s ,t ) 0.95 Strategy is identified by the rejection probabilityF ( pmy bid ) Prob(pothersbid pmy bid ) γ42

Game Model: Belief Parameters F(p) Game(N, , (Y) ,s,(M*))– N: Number of providers in the market– : Market Capacity– (Y): Market Demand (function of throughput)–s: Customer Reservation Price, function of service type (s)– (M*)): Marginal Cost (function of mean packet count, M)NΓ K n ρ TE ρ TEn 1Nn 1Knρ TE ( N 1) K ε N Yn , t ρ TE K , ε 0 (Y n , t ) N Yn , t ρ TE K N Yn , t M axω n , s , t ( Mˆ ) δ s (Yn , t*n ,t Mˆ*n , t Yn , t Mˆn*, t 1 Yn , t 1 Mˆ*n , t Yn , tC1(C Yn , t ) 212Mˆn*, t 1 Mˆn*, t ( bO D b DO ) Mˆ*n , t ) θ nAnalysisS im ulation43

Y)30030010011100100100100NSP1100NSP1NSP1A.com 1003B.com NEngineered access bandwidth capacities of allproviders in a market100100Γ 300300E-LSR(Y)Market Capacity ( ): Aggregate egion#3(Dallas)(Dallas)300410033002100Nn a)(Atlanta)K n ρTE ρTENn 1KnN 2TEKMarket Demand ( ):Max(Y) NY(Y) (N-1)(N-1)TEK ρTE ( N 1) K ε NYn,t ρTE K , ε 0 (Yn ,t ) NYn ,t ρTE K NYn ,t MaxTEK(N-1)TEKMaxNTEKY44

Market Demand Max Market Demand (Max)– Aggregate Bandwidth in active session by all the customers from all theproviders at a certain instant of game (t)– An NSP cannot meet the demand ( ) of the whole market TEK Max – Maximum Market Demand is less than Market Capacity – Market Demand is greater than N-1 providers’ aggregate capacity TE(N-1)K MaxProposed Market Demand is a function of traffic served (Networkoutput/production)– Network is loss-less (no packet drop occurs in the network)ρTE ( N 1) K ε NYn,t ρTE K , ε 0 (Yn ,t ) NYn ,t ρTE K NYn ,t MaxYt : Sum of output (production) traffic bandwidth in all the egress ports of an45NSP at a certain Instant of the game (t)

Reservation Price of the Institution Reservation price ( ) is the price that a customer is willing to pay in theReverse Auction– It can be considered as customer’s budget. We do not study the method of determining .We assume– Enterprises (customers) are rational Reservation price is selected during the business agreementEnterprises do not violate the agreement– Do not change the reservation price during the game– for Homogeneous services,– For Heterogeneous services, is a same fixed value for all providerss depends on the type of serviceEnterprises may adopt their own strategies to determine.– This will require another larger research For example, Enterprise selects reservation price by considering monopoly market(assume

Introduced new area in Internet pricing research - Our research is the first in Internet Oligopoly pricing research for disjoint providers - Existing research are for monopoly market Introduced pricing research in a complex network model - Bi-directional links, multiple paths, Origin-Destination and Destination-Origin Call Legs.