COMPUTER NETWORKS RESEARCH LAB

TSP Lab

Department of Electrical and Computer Engineering, McGill University

  NAVIGATION

Home
People
Photos
 

  RESEARCH

Projects
Publications
 

  LINKS

AAPN
MITACS
McGill TSP
McGill ECE
 

  LOCAL ACCESS
Local Info
 
 

Project Descriptions Return to Service Overlay Networks Projects

Capacity Allocation in Service Overlay Networks
- Maximum Profit vs Minimum Cost Formulations
 

Researchers: Ngok Lam, Ph.D. Student & Prof. Lorne Mason

Description:

It is quite common that in formulating network design problems, one may be confronted with the choice of choosing whether to minimize the investment or to maximize the profit from the network. While this choice of the criterion of optimization could have profound influence on the final solution obtained, we note that in the literature the choices are usually made in a somewhat undisclosed manner without giving the detailed background rationale to the readers. A natural question is: Since the Maximum Profit (MP) and the Minimum Cost (MC) formulations optimize different objectives, how do their solutions compare? Or to be specific, for a given set of parameters, which formulation should be picked and how do their solutions compare.

Though these questions can be answered by the sensitivity analysis theory, but it is not trivial under the SON environment. Unlike the traditional Internet where inter-domain routing are usually determined by some idiosyncratic business objectives of the independent autonomous systems, the operators of SON enjoy great degree of freedom in deploying their own inter-domain routing schemes as the network is solely under their administrations. Owning to this flexibility, different network administrators are likely to employ different routing schemes that fit their own business objectives. The conclusion regarding SON design for a particular routing scheme may not be valid for another.

This paper addresses this objective function choice problem faced by the operators for a class of Service Overlay Network (SON) capacity allocation problems. The result does not depend on a specific routing scheme as long as certain conditions are met. We identify the region such that MP and MC formulations offer the same solution. We also identify the region such that MP gives different solutions than the MC formulation. It is shown that the set of Lagrange multipliers from the MC formulation plays an important role in separating the aforesaid regions. When the service charges are lower than the set of multipliers, the MC and MP formulations will give the same solution. When the service charges are higher than the multipliers, the solutions will be different. The same set of Lagrange multipliers also acts as thresholds for the service charges so that the SON operator would provide adequate service levels under the MP formulation. This additional pricing information is almost free of charge for the network operators. First, it is because that the Lagrange multipliers are frequently the "side-products" of various numerical methods for solving an optimization problem. Second, even if the values of the multipliers are not explicitly obtained, they could be computed relatively easy by solving a set of linear equations at the optimality (given that the regularity condition holds).

The maximum profit formulation of this problem is given by the expression in (1). Where l_ij is the poissonian connection arrival rate for the node pair ij (i.e. source node is i, destination node is j), w_ij is the expected reward generated by an admitted ij connection, both l_ij and w_ij are assumed to be given parameters. The variable Bij is the blocking probability for traffic pairs ij, which is a value returned by the routing layer. The GoS constraint for each OD pair ij is given by L_ij which specifies the maximum allowed connection blocking probability, it is assumed that the Erlang B equation is employed to quantify the blocking probabilities. The capacity of a link s is denoted by Ns and it is a decision variable of this problem. The function Cs(.) is the cost function that quantifies the cost rate of allocating N_s units of capacities on link s and it is assumed to be a linear function of the variable N_s. The variables u_ij and z_s are the Lagrange multipliers with respect to the constraints. The minimum cost formulation of the same problem is given by (2).


Publications:

N. Lam, Z. Dziong and L.G. Mason, Maximum Profit VS Minimum Cost in Service Overlay Network Design, in Proc. IADIS International Conference in Telecommunications, Networks and Systems,Algarve, Portugal, June 2009.
[Paper (pdf format)]