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)

libraryGraph_graphTransformation.m
% libraryWA_graphTransformation 

% Usage: [ingressTransfId egressTransfId transfNodeTable transfLinkTable transfTWCTable] = ...
%     libraryWA_graphTransformation (sequenceOfLinkIDs , sequenceOfNodeIDs, phys, netState)
%
% Abstract: This function computes a auxiliary graph (a transformed graph),
% that will be used to assign a wavelength to a given path by minimizing
% the number of used Tunable Wavelength Converters (TWCs). 
%
% Arguments:
% o	In: 
%    sequenceOfLinkIDs: Row vector with the sorted sequence of link IDs of
%     the path to which we want to assign the wavelengths. The links IDs
%     are sorted from the ingress node to the egress node of the path.
%
%   . sequenceOfNodeIDs: Row vector with the sorted sequence of node IDs
%     of the path to which we want to assign the wavelengths. The nodes IDs
%     are sorted from the ingress node to the egress node of the path.
%
%   . netState: NetState Structure. More information about netState in
%     section "Structure of netState variable" from Help. 
%
%   . phys: Phys Structure. More information about netState in section 
%     "Structure of phys variable" from Help.
%
% o	Out:
%    ingressTransfId: Integer scalar. ID of the ingress node of the path
%     in the transformed graph.
%
%    egressTransfId: Integer scalar. ID of the egress node of the path in
%     the transformed graph. 
%
%    transfNodeTable(N,3): N-by-3 matrix, where N is the number of nodes
%     of the transformed graph. This table express the correspondences
%     between the nodes of the original graph and the nodes of the transformed
%     graph. Each row is a node in the transformed graph, where the first
%     column is the ID of the node in the transformed graph, the second
%     column is the ID of the equivalent node in the original graph and the
%     third column is a column vector of -1's.
%
%    transfLinkTable(T,4): Matrix of T transformed links by 4. Each row is a
%     transformed link 't' of the auxiliary (or transformed graph), where
%     the first columns is the the nodeID in the transformed graph of the
%     origin node of the link 't', the second column is the the nodeID in
%     the transformed graph of the destination node of the link 't', the
%     third column is the link weight of the link 't', and the fourth
%     column is the ID of the wavelength corresponding to the transformed link,
%     except when the transformed link is a internal link to a node.
%     the 
%
%    transfTWCTable(N,2): Ntwc-by-2 matrix, where Ntwc is the number of nodes
%     which represent the TWCs in the transformed graph. This table express the
%     correspondences between the nodes of the original graph with TWCs and
%     the nodes of the transformed graph which model the TWCs. Each row is
%     a node which model a TWC in the transformed graph, where the first
%     column is the ID of the node-TWC in the transformed graph and the second
%     column is the ID of the equivalent node in the original graph.
%

function [ingressTransfId egressTransfId transfNodeTable transfLinkTable transfTWCTable] = ...
    libraryGraph_graphTransformation (sequenceOfLinkIDs , sequenceOfNodeIDs, phys, netState)

    ingressTransfId = 1;
    egressTransfId = -1;
    transfNodeTable = zeros (0,3);
    transfTWCTable = zeros (0,2);
    transfLinkTable = zeros (0,4);


    [numberOfOccupiedTWCsInNodeSequence] = netState.numberOfOccupiedTWCs(sequenceOfNodeIDs);
    
    %First node data
    numberOfLastNodeTransfCreated = 1;
    firstLinkId = sequenceOfLinkIDs (1);
    firstNodeId = sequenceOfNodeIDs (1);
    transfNodeTable = [transfNodeTable ; 1 firstNodeId -1];

    %Add the wavelengths which connect the next node
    previousNodeId = firstNodeId;
    nodeIdTransfPreviousNodeTWC = -1;
    
    [availableWavelengthsInLink] = calculateAvailableWavelengths (firstNodeId , sequenceOfNodeIDs(2) , firstLinkId , phys, netState);
    
    listOfPreviousNodeTransfId = [ones(length(availableWavelengthsInLink),1) (firstNodeId*ones(length(availableWavelengthsInLink),1)) (availableWavelengthsInLink')];
    
    for contIntermediateAndEgressNodes = 2:length (sequenceOfNodeIDs)
        currentNodeId = sequenceOfNodeIDs (contIntermediateAndEgressNodes);
        linkId = sequenceOfLinkIDs (contIntermediateAndEgressNodes - 1);

        [availableWavelengthsInLink] = calculateAvailableWavelengths (previousNodeId , currentNodeId , linkId , phys,netState);

        
        % listOfCreatedTransfNodes (nodoIdTransf , nodoId , lambda)
        % listOfCreatedTransfLinks (nodoIdTransfOrig , nodoIdTransfDest ,
        % weight)
        % if nodeIdTransfNodeTWC is the tranformed ID TWC. When the node
        % does not have converters, this variable is '-1'.
        thisNodeHasTWC = (numberOfOccupiedTWCsInNodeSequence(contIntermediateAndEgressNodes) > 0);
        thisIsTheEgressNode = (contIntermediateAndEgressNodes == length (sequenceOfNodeIDs));
      
        [listOfCreatedTransfNodes , listOfCreatedTransfLinks , nodeIdTransfNodeTWC , numberOfLastNodeTransfCreated] = intermediateOrEgressNodeIteration (previousNodeId , ...
                                                                currentNodeId , numberOfLastNodeTransfCreated , availableWavelengthsInLink , listOfPreviousNodeTransfId , nodeIdTransfPreviousNodeTWC , thisNodeHasTWC , thisIsTheEgressNode);

        transfLinkTable = [transfLinkTable ; listOfCreatedTransfLinks];
        transfNodeTable = [transfNodeTable ; listOfCreatedTransfNodes];
        if nodeIdTransfNodeTWC ~= -1
            transfTWCTable = [transfTWCTable ; nodeIdTransfNodeTWC currentNodeId];       
        end

        nodeIdTransfPreviousNodeTWC = nodeIdTransfNodeTWC;
        previousNodeId = currentNodeId;
        listOfPreviousNodeTransfId = listOfCreatedTransfNodes;
        
        if thisIsTheEgressNode == 1
            egressTransfId = listOfCreatedTransfNodes (1,1);
        end
    end
end



% 1- create as nodes as wavelengths between this node and the previous
% node.
% 2- If this node has converter, create a node for the converter. 
% 3- Create links from tranformed nodes (belonging this node) to
% tranformed nodes (belonging the previous node).
% 4- If the previous node has converter, create links from 
% tranformed nodes (belonging this node) to the TWC previous node.
% 5- If this node has converter, create links from 
% tranformed nodes (belonging this node) to the TWC node (belonging this
% node).
function [listOfCreatedTransfNodes , listOfCreatedTransfLinks , nodeIdTransfNodeTWC , numberOfLastNodeTransfCreated] = intermediateOrEgressNodeIteration (previousNodeId , ...
                                                                currentNodeId , numberOfLastNodeTransfCreated , availableWavelengthsInLink , listOfPreviousNodeTransfId , nodeIdTransfPreviousNodeTWC , thisNodeHasTWC , thisIsTheEgressNode)    
                                                            
    listOfCreatedTransfNodes  = zeros (0,3);
    listOfCreatedTransfLinks = zeros (0,4);
    % If this node is the egress node, we must take it into account.
    if (thisIsTheEgressNode)
        % Create a tranformed node for this node
        numberOfLastNodeTransfCreated = numberOfLastNodeTransfCreated + 1;
        listOfCreatedTransfNodes = [listOfCreatedTransfNodes ; numberOfLastNodeTransfCreated currentNodeId -1];
        % Create links from the egress node to the transformed nodes
        % (belonging the previous node).
        
        for contPreviousTransfNode = 1:size (listOfPreviousNodeTransfId,1)
            row = listOfPreviousNodeTransfId (contPreviousTransfNode , :);
            previousTransfNode = row (1);
            wavelengthToPreviousNode = row (3);
            
            if (isempty (intersect (wavelengthToPreviousNode , availableWavelengthsInLink)) == 0)
                listOfCreatedTransfLinks = [listOfCreatedTransfLinks ; previousTransfNode numberOfLastNodeTransfCreated 1 wavelengthToPreviousNode];
            end
            
        end
        for wavelength=availableWavelengthsInLink
            if nodeIdTransfPreviousNodeTWC ~= -1
                listOfCreatedTransfLinks = [listOfCreatedTransfLinks ; nodeIdTransfPreviousNodeTWC numberOfLastNodeTransfCreated 1 wavelength];%no veo clara la lambda q debemos asignar
            end
        end
        nodeIdTransfNodeTWC = -1;
        return;
    end
       
    
    % If this node has converter, create a transformed node for it.
    if (thisNodeHasTWC == 1)
        numberOfLastNodeTransfCreated = numberOfLastNodeTransfCreated + 1;
        nodeIdTransfNodeTWC = numberOfLastNodeTransfCreated;
    else
        nodeIdTransfNodeTWC = -1;
    end
        
    for contWav = 1:length (availableWavelengthsInLink)
        wavelengthThisTransfLink = availableWavelengthsInLink(contWav);
        
        % Create a tranformed node for this node
        numberOfLastNodeTransfCreated = numberOfLastNodeTransfCreated + 1;
        listOfCreatedTransfNodes = [listOfCreatedTransfNodes ; numberOfLastNodeTransfCreated currentNodeId wavelengthThisTransfLink];
        % Create links from this node to the transformed nodes
        % (belonging the previous node).
        
        % If this node has converter, create links from
        % tranformed nodes (belonging this node) to the TWC
        % previous node.
        if (nodeIdTransfNodeTWC ~= -1)
            listOfCreatedTransfLinks = [listOfCreatedTransfLinks ; numberOfLastNodeTransfCreated nodeIdTransfNodeTWC  1 -1];            
        end
        
        % Create links from tranformed nodes (belonging this node) to
        % tranformed nodes (belonging the previous node).
        for contPreviousTransfNode = 1:size (listOfPreviousNodeTransfId,1)
            row = listOfPreviousNodeTransfId (contPreviousTransfNode , :);
            previousTransfNode = row (1);
            wavelengthToPreviousNode = row (3);
            
            if (wavelengthThisTransfLink == wavelengthToPreviousNode)
                listOfCreatedTransfLinks = [listOfCreatedTransfLinks ; previousTransfNode numberOfLastNodeTransfCreated 1 wavelengthToPreviousNode];
            end
        end

        % If the previous node has converter, create links from 
        % tranformed nodes (belonging this node) to the TWC previous node.
        if nodeIdTransfPreviousNodeTWC ~= -1
            listOfCreatedTransfLinks = [listOfCreatedTransfLinks ; nodeIdTransfPreviousNodeTWC numberOfLastNodeTransfCreated 1 wavelengthThisTransfLink];
        end

    end

end


function [availableWavelengthsInLink] = calculateAvailableWavelengths (sourceNodeId , endNodeId , linkId , phys, netState)

    if (size (netState.lightpathRoutingMatrix,1) == 0)
        availableWavelengthsInLink = [1:phys.numberWavelengthPerFiber(linkId)];
        return
    end

    [lpIdsInLink] = find (netState.lightpathRoutingMatrix (:,linkId) ~= 0);
    
    usedWavelengthsInLink = netState.lightpathRoutingMatrix (lpIdsInLink , linkId);
    availableWavelengthsInLink = setdiff ([1:phys.numberWavelengthPerFiber(linkId)] ,  usedWavelengthsInLink);

end



Contact us