libraryVTD_MLDA.m

% MLDA (Minimum-Delay Logical Topology Design Algorithm)
%
% Usage: [exitFlag lightpathTable lightpathRoutingMatrix numberOfOccupiedTWCs numberOfOccupiedTxs numberOfOccupiedRxs] =
% libraryVTD_MLDA(traff_trafficMatrix, phys)
%
% Abstract: The minimum-delay logical topology design algorithm (MLDA)
% heuristic ensures that a shortest (propagation delay) path exists for
% every pair of nodes. First the MLDA copies the physical topology as
% virtual topology.Then it uses HLDA to create addtional lightpaths between
% node pairs till there are no more available network resources.
%
% This method solves the first three of the four classic subproblems into
% which the Virtual Topology Design Problem is possible to decompose:
%
% 1) Virtual Topology Subproblem
% 2) Lightpath Routing Subproblem
% 3) Wavelength Assignment Subproblem
% 4) Traffic Routing (over the Virtual Topology) Subproblem
%
% NOTE: This algorithm does not solve the traffic flow routing over the
% virtual topology. For this purpose, it is necessary to apply some flow
% routing method over the virtual topology obtained with this function.
%
% 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.
%
%  . phys: Phys Structure. More information about netState in section 
%    "Structure of phys variable" from Help.
%  
% o	Out:
%  . exitFlag: 
%           0, if it is possible to design the virtual topology
%           1, if the virtual topology design is NOT FEASIBLE as there is
%              no sufficient resources to establish any lightpath.
%           2,  if the virtual topology design is NOT FEASIBLE as there
%              is no sufficient transceivers to include the physical
%              topology into the virtual topology.
%
%  . lightpathTable(L,3): L-by-3 integer matrix. Each row is a
%    lightpath 'l', where the first column is the serial number of the 
%    lightpath, the second and third columns of each row are
%    theorigin node 'i' and destination node 'j' of this lightpath 'l'
%    respectively and L is the number of lightpaths of the virtual
%    topology. 
%
% .  lightpathRoutingMatrix (L,M): L-by-M integer matrix where L
%    is the number of lightpaths and M is the number of physical fibre
%    links. Each row is a lightpath 'l' and each column is a physical link
%    'm'. If a lightpath 'l' uses a physical link 'm' with a certain
%    wavelength 'w', the entry (l,m) is  equal to 'w'. If no physical link
%    is used by the lightpath 'l', the entry is equal to '0'.
%
%  . numberOfOccupiedTxs (Nx1): N integer vector where N is the 
%    number of nodes. Each position 'i' is the number of occupied (used)
%    transmitters that the node with ID 'i' has.
%
%  . numberOfOccupiedRxs (Nx1): N integer vector where N is the 
%    number of nodes. Each position 'i' is the number of occupied (used)
%    receivers that the node with ID 'i' has.
%
%  . numberOfOccupiedTWCs (Nx1): N integer vector where N is the 
%    number of nodes. Each position 'i' is the number of occupied (used)
%    converters that the node with ID 'i' has.
%
%
function [exitFlag lightpathTable lightpathRoutingMatrix numberOfOccupiedTWCs numberOfOccupiedTxs numberOfOccupiedRxs] = libraryVTD_MLDA(traff_trafficMatrix, phys)

%MAIN VARIABLES*********************************************************

exitFlag=0;

numberOfNodes = phys.N;
numberOfLinks = phys.M;

lightpathTable=[];
lightpathRoutingMatrix=[];
numberOfOccupiedTxs = zeros (1,numberOfNodes);
numberOfOccupiedRxs = zeros (1,numberOfNodes);
numberOfOccupiedTWCs = zeros (1,numberOfNodes); % does not change as this is a non-wavelength-converting heuristic

%"freeWavelengths" is a matrix, where rows are each link
%((1,1)(2,1)(3,1)(4,1)(1,2)(2,2)...) and columns are a specifical
%wavelength: w0, w1, w2... Each value is 0 or 1 if that is free 
freeWavelengths=zeros(numberOfLinks,max(phys.numberWavelengthPerFiber));
for i=1:numberOfLinks,
    freeWavelengths(i,1:phys.numberWavelengthPerFiber(i))=1;
end

%total number of node pairs whose traffic must be considered
numberOfNodePairsToBeConsidered = length(traff_trafficMatrix)^2-...
    sum(sum(traff_trafficMatrix==zeros(length(traff_trafficMatrix),length(traff_trafficMatrix))));

iteration=1;

%ALGORITHM DEVELOPMENT*********************************************

%1)MLDA COPY THE PHYSICAL TOPOLOGY ONTO THE VIRTUAL TOPOLOGY
numberOfLightpaths=size(lightpathTable,1);

lightpathTable=[(1:size(phys.linkTable,1))' phys.linkTable];

lightpathRoutingMatrix=eye(numberOfLinks);
numberOfLightpaths=numberOfLinks;

%update of the free transmitters and free receivers
for i=1:numberOfNodes,    
    numberOfOccupiedTxs(i) = numberOfOccupiedTxs(i) + length(find(lightpathTable(:,2)==i));
    numberOfOccupiedRxs(i) = numberOfOccupiedRxs(i) + length(find(lightpathTable(:,3)==i));
end

%If the number of available tx and rx is not enough to include the physical topology
%in the virtual topology, the algorithm is aborted

if (~isempty(find(numberOfOccupiedTxs>phys.numberTxPerNode,1)) || ~isempty(find(numberOfOccupiedRxs>phys.numberRxPerNode,1))),
    exitFlag = 2;
    return
end
%Update of the free wavelengths in each edge:
%The first wavelength is occupied in all physical edges.

freeWavelengths(:,1)=0;

%2)HLDA ALGORITHM

consideredNodePairs=[];

%Main loop. It works along such iterations as possible traffics to route
while size(consideredNodePairs,1) < numberOfNodePairsToBeConsidered,

    %First maximum traffic value
    %at first, we find the maximum traffic value. It is avoid two equal
    %maximums, we take the first one.
    maximumTraffic=max(max(traff_trafficMatrix));
    [aux1,aux2]=find(traff_trafficMatrix==max(max(traff_trafficMatrix)));
    source(iteration)=aux1(1);
    destination(iteration)=aux2(1);

    if(isempty(intersect(consideredNodePairs,[source(iteration) destination(iteration)],'rows')))
        consideredNodePairs=[consideredNodePairs;[source(iteration) destination(iteration)]];
    end   

    %FIRST CONDITION: A TRANSMITER IN SOURCE NODE AND A RECEIVER IN DESTINATION NODE
    if(numberOfOccupiedRxs(destination(iteration))<phys.numberRxPerNode(destination(iteration)) &&...
        numberOfOccupiedTxs(source(iteration))<phys.numberTxPerNode(source(iteration))), 

        %SECOND CONDITION: FIND A physical ROUTE BETWEEN SOURCE AND DESTINATION
        linkTable=[phys.linkTable ones(numberOfLinks,1)];
        [sequenceOfSPFLinkIds, sequenceOfSPFNodeIds, totalCost] = ...
            libraryGraph_shortestPath (linkTable, source(iteration), destination(iteration));

        %THIRD CONDITION: IT'S NECESSARY THE SAME WAVELENGTH IN ALL physical ROUTE
        %A matrix such "freeWavelengths" is built. It only contains the links of
        %the physical route. Now we can check which of them are availables to be used.
        freeWavelengthsOnRoute = freeWavelengths(sequenceOfSPFLinkIds,:);
        usedWavelength=0;

        for i=1:size(freeWavelengthsOnRoute,2)%we check all wavelengths 
            %The column with all-ones is the used as wavelength
            if(freeWavelengthsOnRoute(:,i)==ones(size(freeWavelengthsOnRoute,1),1)),
                usedWavelength=i;%the wavelength is established

                %trasmitters and receivers are updated in source and destination nodes
                numberOfOccupiedTxs(source(iteration))=numberOfOccupiedTxs(source(iteration))+1;
                numberOfOccupiedRxs(destination(iteration))=numberOfOccupiedRxs(destination(iteration))+1;

                %freeWavelengths is updated when the used wavelength which is occupied (0)
                freeWavelengths(sequenceOfSPFLinkIds,usedWavelength)=0;
                
                %virtualTopology is updated with the new lightpath
                serialNumberOfLightpaths=size(lightpathTable,1)+1;
                lightpathTable=[lightpathTable; [serialNumberOfLightpaths source(iteration) destination(iteration)]];
                
                currentLightpathRouting=zeros(1,numberOfLinks);
                currentLightpathRouting(sequenceOfSPFLinkIds)=usedWavelength;
                lightpathRoutingMatrix=[lightpathRoutingMatrix; currentLightpathRouting];
                numberOfLightpaths=numberOfLightpaths+1;
              
                %traff_trafficMatrix is updated         
                %we are going to search the second maximum value at traffic
                %matrix
                traff_trafficMatrix(source(iteration),destination(iteration))=0;
                [aux1,aux2]=find(traff_trafficMatrix==max(max(traff_trafficMatrix)));
                sourceOfSecond=aux1(1);
                destinationOfSecond=aux2(1);
                traff_trafficMatrix(source(iteration),destination(iteration))=maximumTraffic;%we complete the original matrix again
     
                if traff_trafficMatrix(source(iteration),destination(iteration))>0,
                    traff_trafficMatrix(source(iteration),destination(iteration))=...
                        traff_trafficMatrix(source(iteration),destination(iteration))-traff_trafficMatrix(sourceOfSecond,destinationOfSecond);
                end
                
                break%we don't continue checking wavelengths when a successful one has been found    
            end
        end

        %Condition of used wavelength
        if usedWavelength==0 %There is not avalaible wavelength for the selected physical route;
            %traff_trafficMatrix updating
            traff_trafficMatrix(source(iteration),destination(iteration))=0;
        end

    else %There is not available transmitters or receivers at node pair
        %traff_trafficMatrix updating
         traff_trafficMatrix(source(iteration),destination(iteration))=0;
    end

    iteration=iteration+1;   
end%End of the main loop

if isempty(lightpathTable) || isempty(lightpathRoutingMatrix), exitFlag = 1; end % there is no sufficient resources to establish any lightpath.