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)

HPSR2001_minTransceivers_MH.m
% Algorithm for traffic grooming in optical networks to minimize the number of transceivers
% published in:
%
% [1]: Konda, V.R., Chow, T.Y.: Algorithm for Traffic Grooming
%      in Optical Networks to Minimize the Number of Transceivers.
%      IEEE Workshop on High Performance Switching and Routing, (2001),
%      pp. 218-221 
%
% Usage: [exitMsg exitFlag newNetState] = HPSR2001_minTransceivers_MH(traff_trafficMatrix, phys, oldNetState, parameters)
%
% Abstract: This function solves the virtual topology desing problem by
% means of the algorithm proposed in the reference [1], but focused on
% using this function in Multi-Hour Analysis, where the function is called
% 24 times for 24 different traffic matrices at 24 different hours in a
% day, obtaining 24 different virtual designs. The function signature
% includes the 'oldNetstate' as extra input parameter, as some Multi-Hour
% Designs take account the virtual topology ('oldNetState')designed at the
% previous hour. In this case, the 'oldNetState' parameter is not used for the
% function, because the function does not design a virtual topology from a
% former virtual topology. 
%
% This function solves 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
%
% The algorithm proposed by Konda in [1] solves the subproblem 1: it
% selects the node pairs candidate to establish the lightpaths by
% minimizing the number of used transceivers. The subproblem 1 does not
% consider the lightpath routing between the previous node pairs
% (subproblem 2) neither the wavelength assignment (subproblem 3). The
% subproblem 2 and 3 are also jointly called RWA (Routing and Wavelength
% Assignmen) problem. The RWA is implemented by the function
% 'libraryRWA_kShortestRWA', which search the k shortest routes valid to
% establish a lightpath between a pair of node. (For more information see
% this function). Finally the subproblem 4) is solved by usinf the function
% 'libraryFR_optimalFlowAssignment', which implements a LP formulation to
% address the Optimal Flow Assignment Problem.
%
% 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.
%
%  . oldNetState: NetState Structure that represents the former virtual
%    topology designed at a previous hour for a previous traffic demand.
%    See below to know the fields of a NetState Structure.
%
%  . parameters: algorithm parameters. For this algorithm, it is the number
%    of 'k' shortest paths computed as candidate routes for a each
%    lightpath.
%   
% o	Out:
%  . exitMsg: Exit Message. If the virtual topology design was successful
%    and all the traffic flows were routed, exitMsg='VIRTUAL TOPOLOGY
%    DESIGN AND FLOW ROUTING SUCCESSFUL!!!'; otherwise, exitMsg indicates
%    the cause of the fail.
%
%  . exitFlag: 
%           0, if it is possible to design the virtual topology and route
%              all the traffic flows over the virtual topology.
%           1, if it is not possible to find a feasible solution
%           2, if the some flow was not able to be routed by the flow
%              routing algorithm or the flow routing is not optimal
%
%  . newNetState: NetState Structure that represents the  virtual topology
%    designed for the current hour. More information about netState in
%    section "Structure of netState variable" from Help. 
%


function [exitMsg exitFlag mh_netState] = HPSR2001_minTransceivers_MH(mh_trafficMatrixes, phys, parameters)

numberTrafficMatrixes = size (mh_trafficMatrixes , 3);
mh_netState = cell (numberTrafficMatrixes,1);
lastLpSerialNumberUsed = 0;
lastFlowSerialNumberUsed = 0;

for orderTrafficMatrix=1:numberTrafficMatrixes
    trafficMatrix (:,:) = mh_trafficMatrixes(:,:,orderTrafficMatrix);
    [exitMsg exitFlag netState]  = HPSR2001_minTransceivers(trafficMatrix, phys, parameters);
    if (exitFlag == 1)
        mh_netState = [];
        break;
    end
    netState.flowTable (:,1) = (lastFlowSerialNumberUsed+1):(lastFlowSerialNumberUsed+size(netState.flowTable,1));
    netState.lightpathTable (:,1) = (lastLpSerialNumberUsed+1):(lastLpSerialNumberUsed+size(netState.lightpathTable,1));    
    lastLpSerialNumberUsed = lastLpSerialNumberUsed + size(netState.lightpathTable,1);
    lastFlowSerialNumberUsed = lastFlowSerialNumberUsed + size(netState.flowTable,1);
    mh_netState {orderTrafficMatrix} = netState;
end

Contact us