libraryTA_trivialAssignment.m

% libraryTA_trivialAssignment
%
% 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.
%
% 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.
%
%   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);

for ingressNode=1:NUMBERNODES
    for egressNode=1:NUMBERNODES
        offeredTraffic = traff_trafficMatrix(ingressNode,egressNode);        
        pendingOfferedTraffic = offeredTraffic;
        for numberLinks=1:ceil(offeredTraffic/(linkCapacity*maximumAllowedUtilization))
            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;
        end
    end
end