29 Jan 2007
08 May 2009)
Educational network planning tool for the RWA problem in WDM networks (MILP and heuristic based)
% Usage: [exitFlag linkTable] = libraryTA_trivialAssignment(traff_trafficMatrix, linkCapacity, maximumAllowedUtilization)
% Abstract: This algorithm computes the topology consisted of the
% sufficient number links to carry any traffic demand between any pair of
% nodes in a single-hop. Therefore, the obtained topology does not need
% traffic grooming to carry all the traffic offered.
% 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.
% linkCapacity: Capacity in Gbps of the link. This is the maximum
% traffic that the link can carry.
% maximumAllowedUtilization: Maximal fraction of the link
% capacity that is allowed to carry in the link.
% o Out:
% . exitFlag:
% 0, if it is possible to obtain a minimal topology which carries
% all the offered traffic.
% 1, if it is not possible to find a feasible solution. (This is
% not possible)
% . linkTable(M,2): M-by-2 integer matrix. Each row is a link in the
% topology obtained. First column is the origin node (1...N), second
% one, the destination node (1...N)
function [exitFlag linkTable] = libraryTA_trivialAssignment (traff_trafficMatrix, linkCapacity, maximumAllowedUtilization)
exitFlag = 0;
NUMBERNODES = size (traff_trafficMatrix,1);
%1) Topology Selection Subproblem: Select the node pairs candidate to
%establish the links among them:
%%% All the node pairs connected by the sufficient links to route all the
%%% traffic demand in an single hop.
linkTable = zeros (0,2);
capacitiesMatrix = zeros (NUMBERNODES,NUMBERNODES);
linkSurplusCapacityVector = zeros (0,0);
offeredTraffic = traff_trafficMatrix(ingressNode,egressNode);
pendingOfferedTraffic = offeredTraffic;
linkTable = [linkTable ; ingressNode egressNode];
carriedTrafficInThisLink = min (pendingOfferedTraffic,linkCapacity*maximumAllowedUtilization);
linkSurplusCapacityVector = [linkSurplusCapacityVector ; (linkCapacity*maximumAllowedUtilization-carriedTrafficInThisLink)];
pendingOfferedTraffic = pendingOfferedTraffic - carriedTrafficInThisLink;
capacitiesMatrix (ingressNode , egressNode) = capacitiesMatrix (ingressNode , egressNode) + linkCapacity*maximumAllowedUtilization;