% 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