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)

libraryVTD_TILDA.m
% TILDA (Traffic Independent Logical Design Algorithm)
%
% Usage: [exitFlag lightpathTable lightpathRoutingMatrix numberOfOccupiedTWCs numberOfOccupiedTxs numberOfOccupiedRxs] = libraryVTD_TILDA(traff_trafficMatrix, phys)
%
% Abstract: TILDA designs logical topology regardless of the traffic. It
% first places lighrpaths between all one-hop neighbors in the physical
% topology, then between all two-hop neighbors (provided that there are no
% lighrpaths between them already), then between all three-hop nighbors
% (provided that there are no lighrpaths between them already), etc.,
% provided the degree constraints are not violated. Since lightpaths that
% use as few physical topology edges as possible will tend to keep the
% number of wavelengths required, and may be an appropriate choice if the
% traffic is unknown or known to be uniform.
%
% 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.
%
%  . 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_TILDA(traff_trafficMatrix, phys)

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

exitFlag=0;

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

lightpathTable=[];
lightpathRoutingMatrix=[];
numberOfOccupiedTxs = zeros (numberOfNodes,1);
numberOfOccupiedRxs = zeros (numberOfNodes,1);
numberOfOccupiedTWCs = zeros (numberOfNodes,1); % 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

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

numberOfLightpaths=0;

 %This loop calculates all the shortest paths between any pair of nodes
 k=0;
 cellOfSequences=cell(numberOfNodes^2-numberOfNodes, 3);
 for i=1:numberOfNodes,
     for j=1:numberOfNodes,
         if i~=j,
             k=k+1;
             linkTable=[phys.linkTable ones(numberOfLinks,1)];
             [cellOfSequences{k,1} ,cellOfSequences{k,2} , cellOfSequences{k,3}]=...
                  libraryGraph_shortestPath (linkTable, i, j);
         end
     end
 end

 physicalHops=cell2mat(cellOfSequences(:,3));
 maxNrOfHops=max(physicalHops);
 
%Main loop. It works along such iterations as maximum number of hops
%between neighboors are required
for hops=1:maxNrOfHops,
    nodePairIDs=find(physicalHops==hops);
    %All node pairs are ordered randomly
    randomOrder=randperm(length(nodePairIDs));
    nodePairIDs=nodePairIDs(randomOrder,:);
    for m=1:length(nodePairIDs),
        sequenceOfSPFLinkIds=cell2mat(cellOfSequences(nodePairIDs(m),1));
        sequenceOfSPFNodeIds=cell2mat(cellOfSequences(nodePairIDs(m),2));
     
        %FIRST CONDITION: A TRANSMITER IN SOURCE NODE AND A RECEIVER IN DESTINATION NODE
        if(numberOfOccupiedRxs(sequenceOfSPFNodeIds(end))<phys.numberRxPerNode(sequenceOfSPFNodeIds(end)) &&...
        numberOfOccupiedTxs(sequenceOfSPFNodeIds(1))<phys.numberTxPerNode(sequenceOfSPFNodeIds(1))), 

            %SECOND 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 one 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(sequenceOfSPFNodeIds(1))=numberOfOccupiedTxs(sequenceOfSPFNodeIds(1))+1;
                    numberOfOccupiedRxs(sequenceOfSPFNodeIds(end))=numberOfOccupiedRxs(sequenceOfSPFNodeIds(end))+1;

                    %freeWavelengths is updated when the used wavelength which is occupied (0)
                    freeWavelengths(sequenceOfSPFLinkIds,usedWavelength)=0;

                    %virtualTopology is updated with the new lightpath
                    serialNumberOfLightpath=size(lightpathTable,1)+1;
                    lightpathTable=[lightpathTable; [serialNumberOfLightpath sequenceOfSPFNodeIds(1) sequenceOfSPFNodeIds(end)]];

                    currentLightpathRouting=zeros(1,numberOfLinks);
                    currentLightpathRouting(sequenceOfSPFLinkIds)=usedWavelength;
                    lightpathRoutingMatrix=[lightpathRoutingMatrix; currentLightpathRouting];
                    numberOfLightpaths=numberOfLightpaths+1;

                    break%we don't continue checking wavelengths when a successful one has been found    
                end
            end
        end          
    end
end%End of the main loop

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

Contact us