libraryTA_KondaHPSR2001 (traff_trafficMatrix, linkCapacity, maximumAllowedUtilization)

% libraryTA_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] = libraryTA_KondaHPSR2001(traff_trafficMatrix, linkCapacity, maximumAllowedUtilization)
%
% Abstract: This algorithm computes the minimal topology (set of links)
% enough to carry all the offered traffic between all the node pairs. 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.
%           1, if it is not possible to find a feasible solution. (This is
%           not possible)
%
%  . 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)
%
% 

function [exitFlag linkTable] = libraryTA_KondaHPSR2001 (traff_trafficMatrix, linkCapacity, maximumAllowedUtilization)

exitFlag = 0;

NUMBERNODES = size (traff_trafficMatrix,1);

%1) Topology Selection Subproblem: Select the node pairs candidate to
%establish the links among them.

%%% 1.a) Create the initial structure of links according to [1]: All the
%%% node pairs connected by the sufficient links to route all the
%%% traffic demand.
linkTable = zeros (0,2);
capacitiesMatrix = zeros (NUMBERNODES,NUMBERNODES);
linkSurplusCapacityVector = zeros (0,0);

for ingressNode=1:NUMBERNODES
    for egressNode=1:NUMBERNODES
        offeredTraffic = traff_trafficMatrix(ingressNode,egressNode);        
        pendingOfferedTraffic = offeredTraffic;
        for numberLinks=1:ceil(offeredTraffic/(linkCapacity*maximumAllowedUtilization))
            linkTable = [linkTable ; ingressNode egressNode];
            carriedTrafficInThisLink = min (pendingOfferedTraffic,linkCapacity*maximumAllowedUtilization);
            linkSurplusCapacityVector = [linkSurplusCapacityVector ; (linkCapacity*maximumAllowedUtilization-carriedTrafficInThisLink)];
            pendingOfferedTraffic = pendingOfferedTraffic - carriedTrafficInThisLink;
            capacitiesMatrix (ingressNode , egressNode) = capacitiesMatrix (ingressNode , egressNode) + linkCapacity*maximumAllowedUtilization;
        end
    end
end

weMustStop = 0;
%%% 1.b) We tear down a link per iteration and we try to route the
%%% traffic carried by the removed LP throug the remaining virtual
%%% topology according to [1].
while (weMustStop ~= 1) & (sum(linkSurplusCapacityVector) >=  linkCapacity*maximumAllowedUtilization)
    
    minimumSurplusCapacityConsumedTotal = inf;
    linkIdWithMinimumLoadTotal = [];
    
    for ingressNode=1:NUMBERNODES
        for egressNode=1:NUMBERNODES 
            if (ingressNode==egressNode), continue, end
            % Obtain the set of links between these node pairs
            setOfLinksBetweenThisNodePair_1 = find (linkTable(:,1) == ingressNode);
            setOfLinksBetweenThisNodePair_2 = find (linkTable(:,2) == egressNode);
            setOfLinksBetweenThisNodePair = intersect (setOfLinksBetweenThisNodePair_1,setOfLinksBetweenThisNodePair_2);
            if(isempty(setOfLinksBetweenThisNodePair))
                continue
            end
            % Obtain the link between the node pair least loaded
            [maximumSurplusCapacityThisIteration,linkPositionInSet] = max (linkSurplusCapacityVector (setOfLinksBetweenThisNodePair));
            minimumCarriedTrafficThisIteration = linkCapacity*maximumAllowedUtilization - maximumSurplusCapacityThisIteration;
            linkIdWithMinimumLoadThisIteration = setOfLinksBetweenThisNodePair (linkPositionInSet);
            % Try to route the capacity of the link candidate in the surplus
            % topology
            linkCostVector = ones (size (linkTable,1),1);
            linkSurplusCapacityVector (linkIdWithMinimumLoadThisIteration) = 0;
             
            [exitFlag_MCF, flowRoutingVectorThisIteration , minimumSurplusCapacityConsumedThisIteration] = libraryGraph_minCostFlow (ingressNode , egressNode , minimumCarriedTrafficThisIteration , linkTable , linkCostVector , linkSurplusCapacityVector);
            linkSurplusCapacityVector (linkIdWithMinimumLoadThisIteration) = linkCapacity*maximumAllowedUtilization -minimumCarriedTrafficThisIteration;%%%%%Restore the linkSurplusCapacityVector(linkIdWithMinimumLoadThisIteration) with the real value (not zero)
            
            if (exitFlag_MCF == 0) & (minimumSurplusCapacityConsumedThisIteration < minimumSurplusCapacityConsumedTotal)
                flowRoutingVectorTotal = flowRoutingVectorThisIteration;
                linkIdWithMinimumLoadTotal = linkIdWithMinimumLoadThisIteration;
                minimumSurplusCapacityConsumedTotal = minimumSurplusCapacityConsumedThisIteration;
            end                  
        end
    end

    if (isempty (linkIdWithMinimumLoadTotal))
        weMustStop = 1;
    else
        linkTable (linkIdWithMinimumLoadTotal,:) = [];
        linkSurplusCapacityVector(:) = linkSurplusCapacityVector - flowRoutingVectorTotal';
        linkSurplusCapacityVector (linkIdWithMinimumLoadTotal) = [];
    end
end