No BSD License  

Highlights from
MatPlanWDM v0.5

image thumbnail

MatPlanWDM v0.5

by

 

29 Jan 2007 (Updated )

Educational network planning tool for the RWA problem in WDM networks (MILP and heuristic based)

trans_pijmw2LPRoutingMatrix.m
% trans_pijmw2LPRoutingMatrix
% 
%>> Usage: [lightpathTable lightpathRoutingMatrix] = ...
%                                trans_pijmw2LPRoutingMatrix(pijmw, phys)
%
%>> Abstract: This function converts the "lightpath wavelength link
%   indicator" (variable 'pijmw') into a "lightpath routing matrix". We
%   translate the information about the lightpath routing over the physical
%   topology from the format used in the MILP fomulation ("lightpath
%   wavelength link indicator", pijmw) into the "netState structure" format
%   of "lightpath routing matrix" used in the rest of the program.
%
%>> Arguments:
% o  In: 
%  . pijmw(NxNxM_W): Matrix of N nodes by N nodes by M_W wavelengths
%    channels. An entry (i,j,mw) is a binary value which indicates if there
%    is a lightpath from node 'i' to node 'j' using the wavelength channel
%    'mw'. The index 'mw' corresponds to the wavelength 'w' on the physical
%    link 'm'. Otherwise, the value is '0'
%
%  . phys: Phys Structure. More information about netState in section 
%    "Structure of phys variable" from Help.
%
%
% o Out:
%   lightpathTable(L,2): L-by-2 integer matrix. Each row is a lightpath
%    'l', where the first and second columns of each row are the origin
%    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'.
%
%
function [lightpathTable lightpathRoutingMatrix] = trans_pijmw2LPRoutingMatrix(pijmw, phys)

    initializationMILPVariablesScript;

    lightpathWavelengthLinkIndicator=vect2array(pijmw,[N N NUMBERLINKWAVELENGTHS]);% We transform the vector captured from "x" into an array.

    [N,N,M_W]=size(lightpathWavelengthLinkIndicator);
    %Lightpath-Wavelenght-Link Indicator is converted from the format A(N,N,M_W) to the format B(N,N,M,W)
    lightpathWavelenLinkIndAUX=zeros(N,N,M,WMAX);
    for m=1:M,
        for w=1:WMAX,
            if (MWPOSITION(m,w) ~= -1), %only in this situation there is wavelength channel in the fiber.
                lightpathWavelenLinkIndAUX(:,:,m,w)=lightpathWavelengthLinkIndicator(:,:,MWPOSITION(m,w));
            end
        end
    end
    
    lightpathTable = zeros(0,2);
    lightpathRoutingMatrix =zeros(0, M);

    for i=1:N,
        for j=1:N,
            [nrLPsFromOriginToEnd] = calculate_nrLPsFromOriginToEnd (i, j , lightpathWavelenLinkIndAUX , phys.outgoingLinksFromNode , phys.incomingLinksToNode ,phys);
            if (nrLPsFromOriginToEnd == 0)
                continue;
            end
            %%% First, I create lps with wavelength continuity
            for w=1:WMAX
                while (1)            
                    [linkTableOfLightpathInThisW , originalLinkIdsOfSubgraph] = createWavelengthSubgraph (i , j , w , lightpathWavelenLinkIndAUX , phys);
                    [sequenceOfSPFLinkIds,sequenceOfSPFNodeIds , totalCost] = libraryGraph_shortestPath (linkTableOfLightpathInThisW , i , j);

                    lightpathWavelenLinkIndAUXVector = squeeze (lightpathWavelenLinkIndAUX (i,j,:,w));
                    
                    if (isempty (sequenceOfSPFLinkIds))
                        break;
                    end
                    
                    sequenceOfOriginalLinkIdsOfPath = originalLinkIdsOfSubgraph(sequenceOfSPFLinkIds);
                    
                    % add t lpTable, lpRouting, and remove from lpWLIndicator
                    newLightpathRoutingMatrixEntry = zeros(1,M);
                    newLightpathRoutingMatrixEntry(sequenceOfOriginalLinkIdsOfPath) = w;
                    lightpathRoutingMatrix = [lightpathRoutingMatrix; newLightpathRoutingMatrixEntry]  ;
                    lightpathWavelenLinkIndAUX(i,j,sequenceOfOriginalLinkIdsOfPath,w)=0;
                    lightpathTable = [lightpathTable; i j];                    
                end
            end
            
            %% Second, I create lps which require wavelength conversion
            [nrLPsFromOriginToEnd] = calculate_nrLPsFromOriginToEnd (i, j , lightpathWavelenLinkIndAUX , phys.outgoingLinksFromNode , phys.incomingLinksToNode ,phys);
            while (1)
                [linkTableOfLightpath , originalLinkIdsOfSubgraph] = createLinkSubgraph (i , j , lightpathWavelenLinkIndAUX , phys);
                [sequenceOfSPFLinkIds,sequenceOfSPFNodeIds , totalCost] = libraryGraph_shortestPath (linkTableOfLightpath , i , j);
                if (isempty (sequenceOfSPFLinkIds))
                    break;
                end

                sequenceOfOriginalLinkIdsOfPath = originalLinkIdsOfSubgraph(sequenceOfSPFLinkIds);
                
                % add to lpTable, lpRouting, and remove from lpWLIndicator
                newLightpathRoutingMatrixEntry = zeros(1,M);
                for traversedLink=makeRowVector(sequenceOfOriginalLinkIdsOfPath);
                    listOfAvaialableWavelengths = find (lightpathWavelenLinkIndAUX(i,j,traversedLink,:) == 1);
                    newLightpathRoutingMatrixEntry(traversedLink) = listOfAvaialableWavelengths(1);
                    lightpathWavelenLinkIndAUX(i,j,traversedLink,listOfAvaialableWavelengths(1))=0;    
                end
                lightpathRoutingMatrix = [lightpathRoutingMatrix; newLightpathRoutingMatrixEntry]; 
                lightpathTable = [lightpathTable; i j] ;
            end
        end
    end
                
end


function [linkTable originalLinkIdsOfSubgraph] = createWavelengthSubgraph (i , j , w , lightpathWavelenLinkIndAUX , phys)
    linkTable = zeros (0,3);
    originalLinkIdsOfSubgraph = zeros (0);
    M=size(phys.linkTable,1);
    for m=1:M
        if (lightpathWavelenLinkIndAUX (i,j,m,w)>0)
            linkTable = [linkTable ; phys.linkTable(m,1) phys.linkTable(m,2) 1];
            originalLinkIdsOfSubgraph = [originalLinkIdsOfSubgraph m];
        end
    end
end

function [linkTable originalLinkIdsOfSubgraph] = createLinkSubgraph (i , j , lightpathWavelenLinkIndAUX , phys)
    linkTable = zeros (0,3);
    originalLinkIdsOfSubgraph = zeros (0);
    M=size(phys.linkTable,1);
    for m=1:M
        if (sum(lightpathWavelenLinkIndAUX (i,j,m,:)>0))
            linkTable = [linkTable ; phys.linkTable(m,1) phys.linkTable(m,2) 1];
            originalLinkIdsOfSubgraph = [originalLinkIdsOfSubgraph m];            
        end
    end
end

function [nrLPsFromOriginToEnd] = calculate_nrLPsFromOriginToEnd (originNode , endNode , lightpathWavelenLinkIndAUX , outgoingLinksFromNode , incomingLinksToNode , phys)    
    nrLPsFromOriginToEnd_1 =length(find(lightpathWavelenLinkIndAUX(originNode,endNode, outgoingLinksFromNode{originNode},:)>0));
    nrLPsFromOriginToEnd_2 =length(find(lightpathWavelenLinkIndAUX(originNode,endNode, incomingLinksToNode{endNode},:)>0));

    if (nrLPsFromOriginToEnd_1 ~= nrLPsFromOriginToEnd_2)
          error('Error using calculate_nrLPsFromOriginToEnd => "nrLPsFromOriginToEnd_1" must match "nrLPsFromOriginToEnd_2"')
    end
    nrLPsFromOriginToEnd = nrLPsFromOriginToEnd_2;    
end

Contact us