29 Jan 2007
08 May 2009)
Educational network planning tool for the RWA problem in WDM networks (MILP and heuristic based)
% Usage: [exitFlag , flowRoutingVector , cost] = libraryGraph_minCostFlow
% (ingressNode , egressNode , flowRate , linkTable , costVector , capacityVector)
% Abstract: This function solves the Minimum Cost Flow Problem. This
% problem consist of finding the traffic flow routing between two nodes
% (ingress node and egress node) with the minimum cost. It is allowed
% bifurcations. To solve the Min Cost Flow, we use the function
% 'libraryFR_optimalFlowAssignment', that model the problem of assign
% optimally flows using a Linear Programming (LP) formulation. The problem
% is solved with the linprog solver from MATLAB.
% The function provides the solution which minimizes a given cost function.
% The cost function employed is the sum of the costs in each link.
% The cost in each link is give by the product of the Gbps
% carried and cost per Gbps in the link.
% o In:
% ingressNode: Origin Node of the flow.
% . egressNode: Destination Node of the flow.
% flowRate: Traffic flow offered between the ingress node and egress
% . linkTable(M,2): M-by-2 integer matrix. Each row is a link in the graph.
% first column is the ingress node (1...N), second the egress node
% ( 1...N)
% . capacityVector(M,1): Capacity in Gbps of each link. This is the
% maximum traffic that the link can carry.
% . costVector(M,1): Cost of carrying 1 Gbps in each link. If the
% vector is constant, the average number of hops is minimized. If the
% vector contains a measure of link distance, the average distance
% traversed by the carried traffic is minimized
% o Out:
% . exitFlag:
% 0, if the solution to the Minimun Cost Flow is feasible.
% 1, if the solution to the Minimun Cost Flow is not feasible.
% . flowRoutingVector (1,L): 1-by-L integer matrix where L is the number
% of links. An element (l) means the Gbps belonging to flow that
% traverse link l
% cost: value of the cost function at optimum
function [exitFlag , flowRoutingVector , cost] = libraryGraph_minCostFlow (ingressNode , egressNode , flowRate , linkTable , costVector , capacityVector)
NUMBERNODES = max(linkTable(:,1:2));
NUMBERNODES = max ([NUMBERNODES ingressNode egressNode]);
traff_trafficMatrix = zeros (NUMBERNODES,NUMBERNODES);
traff_trafficMatrix (ingressNode , egressNode) = flowRate;
[exitFlagFA flowTable flowRoutingVector cost] = libraryFR_optimalFlowAssignment(traff_trafficMatrix, linkTable , capacityVector , costVector);
if (size (flowTable,1) ~= 1)
exitFlag = 1;
if (exitFlagFA ~= 0)
exitFlag = 1;
exitFlag = 0;