one that yields the highest profit, except that the
inverse of the previous transaction is barred.
The profit of a transaction is defined as the dif-
ference between a buying price and a selling
price. Each LSP and each link compute the price
at which it is willing to buy or sell bandwidth. A
search is then made over all aggregates to deter-
mine the profit from (i) buying, and (ii) selling
bandwidth on any of the existing LSPs, and (iii)
buying bandwidth on a new LSP. The sellers in
the latter case are the links along the current
least cost path which is computed from current
link prices by Floyd’s shortest path algorithm.
After each transaction the prices are re-evaluated
and the algorithm proceeds to the next iteration.
The transactions continue until no profit can be
made from buying/selling bandwidth and the
algorithm halts.
An overview of the operation of the XFG algo-
rithm is presented below, see [14, 15] for a com-
plete description.
1 Initialisation. Establish LSPs between all
nodes which are interconnected by direct links
and assign all bandwidth on the links to these
LSPs. Compute the prices they would charge
for selling one unit of bandwidth.
2 Compute shortest paths. Let the price of
bandwidth denote the cost of a link and com-
pute the least cost paths for all O-D pairs.
3 Find the most attractive allocation. Examine
all profits, i.e. buying prices less selling
prices, that would result if multi-link LSPs
bought more bandwidth from single link LSPs
or if new multi-link LSPs were created by
buying bandwidth from single link LSPs on
the least cost paths. Identify the transaction
that offers the maximum profit.
4 Find the most attractive de-allocation.
Examine all profits, i.e. selling price less buy-
ing price, that would result if multi-link LSPs
sold bandwidth to single link LSPs. Identify
the transaction that offers the maximum profit.
5 Convergence test. If the profits from the most
attractive allocation and de-allocation are both
negative or sufficiently close to zero, then stop.
6 Perform the most attractive transaction. If
the profit from the best allocation exceeds that
of the best de-allocation, then remove one unit
of bandwidth from the single link LSPs on the
path of the existing or new multi-link LSP and
add one unit of bandwidth to the existing or
new multi-link LSP. Update the bandwidth
prices of the affected LSPs.
If the profit from the best de-allocation
exceeds that of the best allocation, then add
one unit of bandwidth to the single link LSPs
on the path of the existing multi-link LSP and
remove one unit of bandwidth from the exist-
ing multi-link LSP. Update the bandwidth
prices of the affected LSPs.7 Loop Statement. Go to step 2.The XFG algorithm belongs to the class of so-
called greedy algorithms where the action taken
at each optimisation step is the one which imme-
diately gives the highest reward without consid-
ering long term impacts. However, the final
result is optimal if the bandwidth prices are con-
vex, and if the unit of bandwidth can be made
infinitely small. The former condition is fulfilled
by, e.g., using the Erlang-B formula for the ob-
jective function E(⋅,⋅) in equation (2), but the
latter restriction will in practice put a limit on
the optimality.It is noted that the number of iterations required
by the algorithm appears to depend on the num-
ber of bandwidth units in the network. This
seems to suggest a conflict between accuracy
(which requires small units) and speed (which
requires large units). This is however not the
case as a large unit can be used initially to
quickly compute an approximate solution after
which successively smaller units can be used
to refine the solution to within practical limits.4.3 An Application
Consider the network presented in Figure 2 con-
sisting of 55 nodes connected by 71 bi-direc-
tional links. The network contains 1,485 O-D
pairs and carries 6 service classes. Peak rate allo-
cation is presumed and the effective bandwidth
requirement of connections in aggregate a= 1,
..., 6 are 1, 3, 4, 6, 24 and 40 bandwidth units
respectively. Note that, although not used in this
example, Equation (1) also allows for variable
bit rate allocation where the effective bandwidth
of a connection depends upon the statistical gain Figure 2 A 55 node network