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)

dynamicAlgorithm.m
%>>>dynamicAlgorithm 
%
%This function decides the actions to do according to the event and the net
%state. It decides whether a new flow can be carried or not, and the ordered
%sequence of planning decisions to take in order to accommodate the flow. 
%Each action can be a lightpath setup, termination or reroute, and a flow
%setup, termination or reroute.This function is also responsible for 
%making the planning decisions to be taken when a termination flow event 
%arrives, returned as a set of actions similarly as with a new flow event
%arrives.

%>>>The inputs are:
%
% 1) eventType: type of event belonging to the next pending event. If Its an 
%    arrived event, eventType is '0'. If Its an end event, eventType is
%    '1'.
%
% 2) netState: NetState Structure. More information about netState in
%    section "Structure of netState variable" from Help. 
%
% 3) phys: Phys Structure. More information about netState in section 
%    "Structure of phys variable" from Help.
%
% 4) simTime: current moment of simulation.  
%
% 5) algorithmParameters: parameters of the algorithm what are taken from 
%    the guide aplication.
%
% 6) flowProperties: is a struct with the properties of the flow to
%   process. It has the next fields:
%       -flowDuration: duration of the flow. This duration is expresed in seg.   
%       -flowAverageRate: average rate of the flow what has caused the event.
%       This bit rate is expresed in Gbps. 
%       -pairIngressEgress: vector with two positions and (Ingress Node Id,
%       Egress Node Id). 
%       -flowPriority: priority of the flow.
%       -flowSerialNumber: serial number of the flow.
%       -flowSetUpTime: arrival time of the flow.
%
%>>>The outputs are:
%
% 1) actions: is a cell with the structs of the actions to do. The possible
%   actions are:
%       -1(Add a new flow):
%           struct('Action',1, 'newFlowProperties', flowProperties ,
%           'newFlowRoutingEntry',newFlowRoutingEntry )
%       where newFlowProperties is a struct with the properties of the new
%       flow and newFlowRoutingEntry is the new row of flowRoutingMatrix
%       with the lightpath used.
%   
%       -2(Reroute an existing flow):
%           struct('Action',2, 'flowSerialNumber', flowSerialNumber ,
%           'newFlowRoutingEntry',newFlowRoutingEntry )
%       where flowSerialNumber is the serial number of the flow to
%       reallocate and newFlowRoutingEntry is the new row of flowRoutingMatrix
%       with the lightpath used.
%
%       -3(Delete an existing flow):
%           struct('Action',3, 'flowSerialNumberToDelete', flowSerialNumber)
%       where flowSerialNumberToDelete is the serial number of the flow to
%       delete from the net.
%
%       -4(Create a new lightpath):
%           struct('Action',4,'newLightpathRoutingEntry',newLightpathRoutingEntry,
%           'pairIngressEgress',[ingressNode egressNode],'occupiedTWCsPerNode',
%           occupiedTWCsPerNode)
%       where newLightpathRoutingEntry is the route of the new lightpath
%       with the physical links and wavelengths used, pairIngressEgress is
%       the pair source and destiation of the new lightpath, 
%       occupiedTWCsPerNode is a vector containing the number of converters
%       occupied per node.
%
%       -5(Reroute an existing lightpath):
%           struct('Action',5,'lightpathSerialNumberToReroute',
%           lightpathSerialNumberToReroute,'newLightpathRoutingEntry',
%           newLightpathRoutingEntry, 'occupiedTWCsPerNode', occupiedTWCsPerNode)
%       where lightpathSerialNumberToReroute is the serial number of the 
%       lightpath to reallocate, newLightpathRoutingEntry is the new route 
%       of the lightpath, occupiedTWCsPerNode is a vector containing the
%       number of converters occupied per node.
%
%       -6(Delete an existing lightpath):
%           struct('Action',6,'lightpathSerialNumberToDelete',
%           lightpathSerialNumberToDelete)
%       where lightpathSerialNumberToDelete is the serial number of the 
%       lightpath to delete from the net.

%
% 2) infoWhatHappenedWithTheFlow: is a flag. If its value is '0', the flow
%   has been processed. If its value is '1', the flow has been lost.
%
% 3) exitFlagParameter: If exitFlag = 0, the processing of the generator parameters
%   string was succesful. If exitFlag = -1, the processing of the generator
%   parameters string was failed.  
%
% 4) exitMsgParameter: Exit Message.

function [actions ,infoWhatHappenedWithTheFlow,exitFlagParameter,exitMsgParameter] =dynamicAlgorithm (eventType,netState,...
    phys,simTime, algorithmParameters,flowProperties)

%%%%%%%%%%%%         AUXILIARY VARIABLES INITIALIZATION  %%%%%%%%%%%%%%%%%%
infoWhatHappenedWithTheFlow=1;
numberOfNodes = phys.N;
numberOfLinks = phys.M;
maxNumberOfWavelengthsInAFiber = max (phys.numberWavelengthPerFiber);
auxWavelengthRoute=[]; 
auxTWCsRoute=zeros(1,numberOfNodes);
actions=[];
exitFlagParameter = 0;
exitMsgParameter = ''; 

occupiedTxsPerNode = netState.numberOfOccupiedTxs; 
occupiedRxsPerNode = netState.numberOfOccupiedRxs; 
occupiedTWCsPerNode = netState.numberOfOccupiedTWCs; 
%%%%%%%%%%%%%%%    PERSISTENT VARIABLES INITIALIZATION   %%%%%%%%%%%%%%%%%%
global k;
global first;

if isempty(first)
    first=1; 
    %%%%%%%%%%%%%%%%%%%%%%%%0. PARAMETERS PROCESSING %%%%%%%%%%%%%%%%%%%%%%%%%
    %We define the default parameter values 
    cellOfDefaultParameters = {['k'], ['1'], ['integer'], ['[1,inf)']};      
    %We process the string of the algorithm parameters      

    [exitFlagOfProcessParam exitMsgOfProcessParam structOfReadParameters] = ...
        processAlgorithmParameters (algorithmParameters, cellOfDefaultParameters);

    if (exitFlagOfProcessParam ~= 0)
        exitFlagParameter = -1;
        exitMsgParameter = 'Bad Algorithm Parameters'; 
        return
    end
    k=structOfReadParameters.k;
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%            ARRIVED EVENT          %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

if ( eventType==0 )
    successfullyRoutedFlow=0;
    pairIngressEgress=flowProperties.pairIngressEgress;
    ingressNode=pairIngressEgress(1);
    egressNode=pairIngressEgress(2);
    minimumCapacityInEachLink=flowProperties.flowAverageRate;
    

    if(flowProperties.flowAverageRate > phys.lightpathCapacity )
        successfullyRoutedFlow = 1;
    end

    %%%%%FIRST OPTION%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %Routing this flow with available lightpaths.
    if(isempty(netState.lightpathTable)==0&successfullyRoutedFlow==0)
 
        lightpathTableWithCapacity=[netState.lightpathTable(:,2:3) ones(size(netState.lightpathTable,1),1)];
        lightpathTableWithCapacity(:,end+1)=(phys.lightpathCapacity*ones(1,size(netState.flowRoutingMatrix,2))-sum(netState.flowRoutingMatrix,1))';
        [sequenceOfSPFLinkIds,sequenceOfSPFNodeIds , totalCost] = libraryGraph_capacityShortestPath (...
        lightpathTableWithCapacity ,ingressNode , egressNode , minimumCapacityInEachLink);

        if(isempty(sequenceOfSPFLinkIds)==0)%It's possible to route with available lightpath.
            
            infoWhatHappenedWithTheFlow=0;
            successfullyRoutedFlow=1;  
            %Updating the net state variables.
            newFlowRoutingEntry=zeros(1,size(netState.flowRoutingMatrix,2));
            for i=sequenceOfSPFLinkIds
                newFlowRoutingEntry(i)=flowProperties.flowAverageRate;
            end
            actions=cell(1,1);
            actions{1}=struct('Action',1, 'newFlowProperties', flowProperties , 'newFlowRoutingEntry',newFlowRoutingEntry );        
        end
    end

    %%%%%SECOND OPTION%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %if it isn't possible to use an existent lp, we try to create a new
    %lightpath to accommodate the flow.
    
    if ( successfullyRoutedFlow == 0 ) 
 
        %At first, we check if there are available transmitter in ingress node 
        %and receiver in egress node.   
 
        if(occupiedTxsPerNode(ingressNode)<phys.numberTxPerNode(ingressNode) & occupiedRxsPerNode(egressNode)<phys.numberRxPerNode(egressNode)) 

            [exitFlag sequenceOfSPFLinkIds sequenceOfSPFNodeIds sequenceOfWavelengths occupiedTWCsPerNode newLightpathRoutingEntry] = libraryRWA_kShortestRWA(k, ingressNode,...
            egressNode, phys, netState);

            if(exitFlag==0)%SUCCESSFULLY
                actions=cell(2,1);
                actions{1}=struct('Action',4,'newLightpathRoutingEntry',newLightpathRoutingEntry,'pairIngressEgress',pairIngressEgress,'occupiedTWCsPerNode',occupiedTWCsPerNode);

                if( isempty( netState.flowRoutingMatrix ) )
                        newFlowRoutingEntry= flowProperties.flowAverageRate;
                else
                    newFlowRoutingEntry=[zeros(1,size(netState.flowRoutingMatrix,2)) flowProperties.flowAverageRate];
                end
                actions{2}=struct('Action',1,'newFlowProperties',flowProperties,'newFlowRoutingEntry',newFlowRoutingEntry);
                lightpathSerialNumberToReroute=1;
  
                infoWhatHappenedWithTheFlow=0;
                successfullyRoutedFlow=1;
            end
            
        else
            %disp('No hay tx o rx %disponible');
        end%There is not available transmitters or receivers at node pair
    end%it isn't possible to use an existent lp
    
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    %%%%%THIRD OPTION%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %We check if it's possible routing using an available lightpath and building 
    %a new lightpath with an intermediate node.
    if(successfullyRoutedFlow==0&isempty(netState.lightpathTable)==0)

        %At first, we check if it's possible to use an available lightpath
        %between ingress node and an intermediate node.
        lpOutIngressNode=find(netState.lightpathTable(:,2)==ingressNode);
        capacityOflpOutIngressNode = phys.lightpathCapacity-sum(netState.flowRoutingMatrix(:,lpOutIngressNode),1);
        minimumCapacityInlpOutIngressNode=find(capacityOflpOutIngressNode>=minimumCapacityInEachLink);
        ingressNeighbours = netState.lightpathTable(lpOutIngressNode(minimumCapacityInlpOutIngressNode),3);
        i=1;

        if(isempty(ingressNeighbours)==0 & occupiedRxsPerNode(egressNode)<phys.numberRxPerNode(egressNode))
            
            for neighbour = ingressNeighbours'
                
                firstlp=lpOutIngressNode(minimumCapacityInlpOutIngressNode(i));
                i=i+1;
                flowInLp = sum (netState.flowRoutingMatrix (:,firstlp));

                if (flowInLp + flowProperties.flowAverageRate > phys.lightpathCapacity)
                   continue;
                end

                if(occupiedTxsPerNode(ingressNode)<phys.numberTxPerNode(ingressNode)) 

                    [exitFlag sequenceOfSPFLinkIds sequenceOfSPFNodeIds sequenceOfWavelengths occupiedTWCsPerNode newLightpathRoutingEntry] = libraryRWA_kShortestRWA(k, neighbour,...
                    egressNode, phys, netState);

                    if(exitFlag==0)%SUCCESSFULLY

                        actions=cell(2,1);
                        actions{1}=struct('Action',4,'newLightpathRoutingEntry',newLightpathRoutingEntry,'pairIngressEgress',[neighbour pairIngressEgress(2)],'occupiedTWCsPerNode',occupiedTWCsPerNode);

                        newFlowRoutingEntry=zeros(1,size(netState.flowRoutingMatrix,2)+1);%Create a new column because it is a new lightpath.
                        newFlowRoutingEntry(end)=flowProperties.flowAverageRate;
                        newFlowRoutingEntry(firstlp)=flowProperties.flowAverageRate;
                        actions{2}=struct('Action',1,'newFlowProperties',flowProperties,'newFlowRoutingEntry',newFlowRoutingEntry);                          
                        infoWhatHappenedWithTheFlow=0;
                        successfullyRoutedFlow=1;

                        break;
                    end
                else
                    %disp('No hay tx o rx %disponible');
                end%There is not available transmitters or receivers at node pair
            end
        end
        
        if(successfullyRoutedFlow==0&isempty(netState.lightpathTable)==0)
            
            %If it hasn't been possible to use an available lightpath
            %between ingress node and an intermediate node, then we try to
            %use an available lightpath between an intermediate node and
            %egress node.
            
            lpInEgressNode=find(netState.lightpathTable(:,3)==egressNode);
            capacityOflpInEgressNode = phys.lightpathCapacity-sum(netState.flowRoutingMatrix(:,lpInEgressNode),1);
            minimumCapacityInlpInEgressNode=find(capacityOflpInEgressNode>=minimumCapacityInEachLink);
            egressNeighbours = netState.lightpathTable(lpInEgressNode(minimumCapacityInlpInEgressNode),2);
            i=1;

            if(isempty(egressNeighbours)==0 & occupiedTxsPerNode(ingressNode)<phys.numberTxPerNode(ingressNode))
                for neighbour = egressNeighbours'
                    
                    firstlp=lpInEgressNode(minimumCapacityInlpInEgressNode(i));
                    i=i+1;
                    flowInLp = sum (netState.flowRoutingMatrix (:,firstlp));

                    if (flowInLp + flowProperties.flowAverageRate > phys.lightpathCapacity)
                        continue;
                    end
                    
                        if(occupiedRxsPerNode(egressNode)<phys.numberRxPerNode(egressNode)) 

                            [exitFlag sequenceOfSPFLinkIds sequenceOfSPFNodeIds sequenceOfWavelengths occupiedTWCsPerNode newLightpathRoutingEntry] = libraryRWA_kShortestRWA(k, ingressNode,...
                            neighbour, phys, netState);
                            
                            if(exitFlag==0)%SUCCESSFULLY

                                actions=cell(2,1);
                                actions{1}=struct('Action',4,'newLightpathRoutingEntry',newLightpathRoutingEntry,'pairIngressEgress',[pairIngressEgress(1) neighbour],'occupiedTWCsPerNode',occupiedTWCsPerNode);

                                newFlowRoutingEntry=zeros(1,size(netState.flowRoutingMatrix,2)+1);%Create a new column because it is a new lightpath.
                                newFlowRoutingEntry(end)=flowProperties.flowAverageRate;
                                newFlowRoutingEntry(firstlp)=flowProperties.flowAverageRate;

                                actions{2}=struct('Action',1,'newFlowProperties',flowProperties,'newFlowRoutingEntry',newFlowRoutingEntry);
                                infoWhatHappenedWithTheFlow=0;
                                successfullyRoutedFlow=1;
                                break;
                            end

                        else
                            %disp('No hay tx o rx %disponible');
                        end%There is not available transmitters or receivers at node pair                     
                end
            end
        end
    end
    
    %FOURTH OPTION%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %We try to build two new lightpaths using an intermediate node.
    
   if(successfullyRoutedFlow==0) 
   
        intermediateNodes = 1:numberOfNodes;
        intermediateNodes(find(intermediateNodes==ingressNode))=[];
        intermediateNodes(find(intermediateNodes==egressNode))=[];
       
        if(occupiedTxsPerNode(ingressNode)<phys.numberTxPerNode(ingressNode) & occupiedRxsPerNode(egressNode)<phys.numberRxPerNode(egressNode))        
            for node = intermediateNodes
                if(occupiedTxsPerNode(node)<phys.numberTxPerNode(node) & occupiedRxsPerNode(node)<phys.numberRxPerNode(node)) 
           
                    [exitFlag firstSequenceOfSPFLinkIds firstSequenceOfSPFNodeIds firstSequenceOfWavelengths firstOccupiedTWCsPerNode firstLightpathRoutingEntry] = libraryRWA_kShortestRWA(k, ingressNode,...
                    node, phys, netState);

                    if(exitFlag==0)%SUCCESSFULLY)
 
                        auxNetState = netState;
                        auxNetState.lightpathTable(end+1,:)=[-1 ingressNode node];
                        auxNetState.lightpathRoutingMatrix(end+1,:)=firstLightpathRoutingEntry;
                        auxNetState.numberOfOccupiedTWCs = auxNetState.numberOfOccupiedTWCs + firstOccupiedTWCsPerNode;

                        [exitFlag secondSequenceOfSPFLinkIds secondSequenceOfSPFNodeIds secondSequenceOfWavelengths secondOccupiedTWCsPerNode secondLightpathRoutingEntry] = libraryRWA_kShortestRWA(k, node,...
                        egressNode, phys, auxNetState);

                        if(exitFlag==0)
                            successfullyRoutedFlow=1;
                            infoWhatHappenedWithTheFlow=0;
                            actions=cell(3,1);
                            actions{1}=struct('Action',4,'newLightpathRoutingEntry',firstLightpathRoutingEntry,'pairIngressEgress',[ingressNode node],'firstOccupiedTWCsPerNode',firstOccupiedTWCsPerNode);
                            actions{2}=struct('Action',4,'newLightpathRoutingEntry',secondLightpathRoutingEntry,'pairIngressEgress',[node egressNode],'secondOccupiedTWCsPerNode',secondOccupiedTWCsPerNode);
                            
                            newFlowRoutingEntry=[zeros(1,size(netState.flowRoutingMatrix,2)) flowProperties.flowAverageRate flowProperties.flowAverageRate];
                            actions{3}=struct('Action',1,'newFlowProperties',flowProperties,'newFlowRoutingEntry',newFlowRoutingEntry);

                            break;
                        end
                    end
                end
            end
        end
    end
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%              END EVENT            %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if(eventType==1)

    actions=cell(1);
    actions{1}=struct('Action',3,'flowSerialNumberToDelete',flowProperties.flowSerialNumber);
    infoWhatHappenedWithTheFlow=0;
    
    rowOfThisFlow=find(netState.flowTable(:,1)==flowProperties.flowSerialNumber);
    lpsTraversedByThisFlow=find(netState.flowRoutingMatrix(rowOfThisFlow,:)~=0);    

    for lpID=lpsTraversedByThisFlow
        trafficWithTheFlowToRemove = sum (netState.flowRoutingMatrix (:,lpID));
        trafficOfTheFlowToRemove = netState.flowRoutingMatrix (rowOfThisFlow,lpID);
        if (trafficWithTheFlowToRemove - trafficOfTheFlowToRemove == 0)
            actions{end+1,1}=struct('Action',6,'lightpathSerialNumberToDelete',netState.lightpathTable(lpID,1));
        end
    end    
end


        

Contact us