% 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