libraryTFA_KondaHPSR2001 (traff_trafficMatrix, linkCapacity, maximumAllowedUtilization)

% libraryTFA_KondaHPSR2001
%
% Algorithm for virtual topology assignment in optical networks to minimize 
% the number of transceivers published in:
%
% [1]: Konda, V.R., Chow, T.Y.: Algorithm for Traffic Grooming
%      in Optical Networks to Minimize the Number of Transceivers.
%      IEEE Workshop on High Performance Switching and Routing, (2001),
%      pp. 218-221 
%
% Usage: [exitFlag linkTable flowTable flowRoutingMatrix] = libraryTFA_KondaHPSR2001 (traff_trafficMatrix, linkCapacity, maximumAllowedUtilization)
%
% Abstract: This algorithm, firtsly, computes the minimal topology (set of
% links) enough to carry all the offered traffic between all the node pairs.
% Then, it is solved the multicommodity flow assignment over the topology computed in the previous step.
% It was published in the reference [1] where the algorithm was applied to
% solve the virtual topology assignment problem. That is, the algorithm
% selects the candidate node pairs to establish the lightpaths (virtual
% links) by minimizing the number of used transceivers. It is guaranteed
% that the virtual topology selected can carry all the offered traffic from
% the traffic matrix. 
%
% Arguments:
% o	In: 
%   traff_trafficMatrix(NxN): Average traffic flow offered between node
%    pairs. The Traffic Matrix is a two-dimensional matrix with N (N:
%    number of nodes) rows and N columns. An entry(s,d) means the average
%    traffic flow from node 's' to node 'd', expressed in Gbps. The main
%    diagonal is full of 0s.
%
%   linkCapacity: Capacity in Gbps of the link. This is the maximum
%    traffic that the link can carry.
%
%   maximumAllowedUtilization: Maximal fraction of the link
%    capacity that is allowed to carry in the link.
%
%   
% o	Out:
%  . exitFlag: 
%           0, if it is possible to obtain a minimal topology which carries
%           all the offered traffic and the optimal flow assignment over
%           it.
%           1, if it is not possible to find a feasible solution. (Because
%           the optimal flow assignment fails)
%
%  . linkTable(M,2): M-by-2 integer matrix. Each row is a link in the
%    topology obtained. First column is the origin node (1...N), second
%    one, the destination node (1...N)
% 
%  . flowTable(F,3): F-by-3 matrix. First column de ingress node, second
%    the egress node, third the traffic offered in Gbps.
%
%  . flowRoutingMatrix (F,L): F-by-L integer matrix where F is the number of 
%    flows and L is the number of lightpaths. Each row is a flow 'f' and each 
%    column is a lightpath 'l'. If a flow 'f' uses a lightpath 'l', the
%    entry (f,l) is equal to the value of the flow 'f' carried by the
%    lightpath 'f'. If no lightpath is used by the flow 'f', the entry is
%    equal to '0'. If a row is a row of zeros, the the traffic flows was
%    not routed
%
%

function [exitFlag linkTable flowTable flowRoutingMatrix] = libraryTFA_KondaHPSR2001 (traff_trafficMatrix, linkCapacity, maximumAllowedUtilization)

exitFlag = 0;

%1) Topology Selection Subproblem: Select the node pairs candidate to
%establish the links among them.
[exitFlag linkTable] = libraryTA_KondaHPSR2001 (traff_trafficMatrix, linkCapacity, maximumAllowedUtilization);

%2) Traffic Flow Routing over the calculated topology.
% We must calculate the flowRoutingMatrix on top of the virtual topology.
% We make it using the optimalFA. If everythign is OK, the capacities MUST
% be enough to carry the flows

[exitFlagFR flowTable flowRoutingMatrix cost] = libraryFR_optimalFlowAssignment_CPLEX(traff_trafficMatrix, ...
    linkTable ,  maximumAllowedUtilization*linkCapacity*ones(1,size(linkTable,1)) , ones(1,size(linkTable,1)) , '');

switch exitFlag_FR,
    case 0,
        exitFlag = 0;%Optimal Multicommodity Flow Assignment
    case 1,
        exitFlag = 2;%'Some traffic flow was not routed or no optimal flow routing found';
    case 2
        exitFlag = 1;%'No feasible solution found';
    otherwise
        exitFlag = 1;%'No feasible solution found';
end