function varargout=compute_blocking_birman(varargin)
%COMPUTE_BLOCKING_BIRMAN Compute blocking propability in a circuit switched
%network using a generalized reduced load approximation.
% [BLOCKING]=COMPUTE_BLOCKING_BIRMAN(NAME,NUMBER,EPSILON,METHOD,D,C) is a
% function which computes blocking probability using generalized reduced
% load approximation method first introduced by Kelly [4], extended by
% Chung et al. and implemented for WDM network by Birman [1] (full and no
% wavelength conversion) and Tripathi [2] (sparse wavelength conversion).
% BLOCKING is given in %.
%
% NAME is a string containing name of analized network saved in
% MATLABROOT/networks directory, NUMBER is the number of dimension in
% TRAFFIC structure. This means, that for analisys TRAFFIC{:,:,NUMBER}
% will be choosed.
%
% METHOD is the type of conversion and D is the degree of sparse
% conversion (for details see help P_M).
%
% EPSILON is some treshold value given by user. For details see [1], [2].
% C is the channel number which we want to use to evaluate blocking.
%
% See also COMPUTE_BLOCKING_KOVACEVIC, P_M, CREATE_NETWORK,
% CREATE_LOAD_MANUAL, LINK_SIM_CONV.
%
% References:
% [1] Alexander Birman, "Computing Approximate Blocking Probabilities
% for a Class of All-Optical Network", IEEE Journal on
% Selected Areas in Communications, vol. 14, June 1996
% [2] Tushar Tripathi, Kumar N. Sivarajan, "Computing Approximate
% Blocking Probabilities in Wavelength Routed All_optical Networks
% with Limited-Range Wavelength Conversion", IEEE Journal on
% Selected Areas in Communications, vol. 18, October 2000
% [3] S. Chung, A. Kashper, K.W. Ross, "Computing Approximate
% Blocking Propabilities for large loss networks", IEEE/ACM
% Transactions on Networking, vol. 1, 1993
% [4] F.P. Kelly, "Routing and capcity allocation in networks with
% trunk reservation", Matematics of Operation Research, vol. 15, no.
% 4, 1990
% Copyright 2003-2004 Przemyslaw Pawelczak
% E-mail: przemyslaw_pawelczak@idg.com.pl
% Wroclaw University of Technology, Poland
% $Revision: 1.0 $ $Date: 2004/05/10 18:01:32 $
%Exeption handling
message=nargchk(6,6,nargin);
if ~isempty(message)
error('MATLAB:COMPUTE_BLOCKING_BIRMAN:NumberOfInputArguments',...
message);
end
testing_int=[varargin{2},varargin{3},varargin{4},varargin{5},varargin{6}];
if find(isnan(testing_int))
error('MATLAB:COMPUTE_BLOCKING_BIRMAN:ArgumentType',...
'Argument must be numbers.');
end
%Check if VARARGIN are positive integers
if sum([testing_int<0,...
fix([testing_int(1),testing_int(3:5)])~=...
[testing_int(1),testing_int(3:5)]])~=0
error('MATLAB:COMPUTE_BLOCKING_BIRMAN:ArgumentType',...
'Wrong type of argument.');
end
if ~isstr(varargin{1})
error('MATLAB:COMPUTE_BLOCKING_BIRMAN:ArgumentType',...
'Argument must be string.');
end
%Change string into number (for all number arguments)
for k=2:5
if isstr(varargin{k})==1
varargin{2}=str2num(varargin{2});
end
end
%List all '*.mat' files in current working directory
%Change directory to MATLABROOT\networks - catalog must exist
cd([matlabroot,['\work\networks']]);
directory=what;
directory=struct2cell(directory);
directory=cellstr(directory{3});
%Check if specified '*.mat' file already exist
if find(strcmp(directory,[varargin{1},'.mat'])==1)
%Load *.MAT file
load(varargin{1});
fields_vector=[exist('description'),exist('structure'),exist('traffic')];
if length(find(fields_vector))~=3
error('MATLAB:COMPUTE_BLOCKING_KOVACEVIC:BadFieldNames',...
'Bad field names.');
end
%Check if BLOCKING definition already exists in this file
%Initialize flag
blocking_exists=0;
varias=who;
varias_dimension=cellfun('ndims',varias);
varias_dimension=length(varias_dimension');
%Check
for k=1:varias_dimension
if isequal(cell2mat(varias(k)),'blocking')
blocking_exists=1;
end
end
%If definition does exist - add another
if blocking_exists==1
%Check how many BLOCKING definitions are there
blocking_dimension=cellfun('ndims',blocking);
blocking_dimension=length(blocking_dimension)+1;
%Load BLOCKING procedure
blocking=birman(traffic,varargin{2},varargin{3},varargin{4},...
varargin{5},varargin{6},blocking,blocking_dimension);
varargout{1}=save_network(description,structure,traffic,blocking,...
varargin{1});
%If definition does not exist - make first one
elseif blocking_exists==0;
blocking{1,1}=[];
blocking_dimension=1;
%Load MAKE_LOAD procedure
blocking=birman(traffic,varargin{2},varargin{3},varargin{4},...
varargin{5},varargin{6},blocking,blocking_dimension);
varargout{1}=save_network(description,structure,traffic,blocking,...
varargin{1});
end
else
error('MATLAB:COMPUTE_BLOCKING_BIRMAN:BadFiledName',...
'Bad file name.');
end
function [blocking]=birman(traffic,number,epsilon,method,d,C,blocking,blocking_dimension);
%Check how many routes does TRAFFIC{:,:,NUMBER} have
%Check how many nodes are in the TRAFFIC{:,:,NUMBER}
traffic_dim=cellfun('ndims',traffic);
traffic_length=length(traffic_dim(:,1,1));
route_number=0;
for k=1:traffic_length
if ~isempty(traffic{k,1,number})
route_number=route_number+1;
max_node_number(k)=[max(traffic{k,1,number})];
end
end
node_number=max(max_node_number);
%Name links in the network with numbers
nodes_matrix=zeros(node_number,node_number);
node_names(1:(node_number*(node_number-1)/2))=1:(node_number*(node_number-1)/2);
for k=1:(node_number-1)
places=(1+(k-1)*node_number+(k-1)+1):(node_number*k);
nodes_matrix(places)=node_names(1:(node_number-k));
node_names(1:(node_number-k))=[];
end
nodes_matrix=nodes_matrix+nodes_matrix';
%Check which links exist in TRAFFIC definition and change routes from edge
%adjacency to link adjacency
%Memory initialization
link_routes{1}=[];
for k=1:route_number
route=traffic{k,1,number};
%Initialization (vector where links of the route will be stored)
link_route=[];
for w=1:(length(route)-1)
%Find name of the link in NODES_MATRIX
link_route=[link_route,nodes_matrix(route(w),route(w+1))];
%One link can traverse path for only one time
link_route=unique(link_route);
%Check how long current route is
route_length(k)=length(link_route);
end
link_routes{k}=link_route;
end
%Find which path is the longest (if >1 longest paths - choose one randomly)
%PATH_LENGTH_POSITION will be lately used in main loop
[path_length,path_length_position]=min(route_length);
%Check which routes use specified links
%Memory initialization
for k=1:(node_number*(node_number-1)/2)
which_routes_use_link{k}=[];
end
for k=1:route_number
path=link_routes{k};
for w=1:length(path)
which_routes_use_link{path(w)}=[which_routes_use_link{path(w)},k];
end
end
%Initialize ALFA_j(m)
for k=1:(node_number*(node_number-1)/2)
which_paths=which_routes_use_link{k};
alfa{k}=[];
if ~isempty(which_paths)
sum_alfa_paths=[];
for w=1:length(which_paths)
sum_alfa_paths=[sum_alfa_paths,traffic{which_paths(w),2,number}];
end
%Numbering of alfa starts form 0 not from 1
temp_vector_alfa(1)=0;
temp_vector_alfa(2:C+1)=sum(sum_alfa_paths);
alfa{k}=temp_vector_alfa;
end
end
%Lr and Lr_prim initialization
Lr(1:route_number)=0;
Lr_prim(1:route_number)=Inf;
%Main loop
while abs(Lr(path_length_position)-Lr_prim(path_length_position))>epsilon
%Assign L_prim to Lr
Lr_prim=Lr;
%Compute Q
for c=1:C
C_vector(c)=C-c+1;
end
for k=1:(node_number*(node_number-1)/2)
%Memory initialization
q{k}=[];
alfa_vector=alfa{k};
if ~isempty(alfa_vector)
q0_sum_elements=[];
for w=1:C
q0_sum_elements=[q0_sum_elements,prod(C_vector(1:w))/prod(alfa_vector(2:(w+1)))];
end
q0=1/(1+sum(q0_sum_elements));
qm(1)=q0;
for w=1:C
qm(w+1)=prod(C_vector(1:w))/prod(alfa_vector(2:(w+1)))*q0;
end
q{k}=qm;
end
end
%Compute ALFA_j(m)
for k=1:(node_number*(node_number-1)/2)
%For every link present in the network
if ~isempty(alfa{k})
%Make vector of arrivals for routes traversing link
%Empty Ar_VECTOR in every iteration
ar_vector=0;
for g=1:length(which_routes_use_link{k})
ar_vector(g)=traffic{which_routes_use_link{k}(g),2,number};
end
%Make computations for every m
for w=2:C+1
%For every path which traverses link K
%Empty Pr_Xr_Xj in every iteration
pr_Xr_Xj_vector=0;
for g=1:length(which_routes_use_link{k})
%Take first path which traverses link k
path=link_routes{which_routes_use_link{k}(g)};
%Remove the link we are considering (link K)
path(find(path==k))=[];
%Check how long it is
path_length=length(path);
%Two choices
if path_length==0
%Probability as stated in equation (9) in [1]
pr_Xr_Xj_vector(g)=1;
else
%Make coordinates
coord_matrix=coordinates(1,C,path_length);
coord_length=size(coord_matrix,1);
%Compute pr_Xr_Xj - equation (9), (10) in [10]
q_vector_sum=[];
for x=1:coord_length
%Add for later multiplication 1-p_0(l,m,n,...)
%Sort X in increasing order because x1>=x2>=...>=xn
x_sorted=sort([coord_matrix(x,:),w-1]);
x_sorted=x_sorted(length(x_sorted):-1:1);
q_vector=(1-p_m(0,x_sorted,C,d,method));
for y=1:path_length
q_vector=[q_vector,q{path(y)}(coord_matrix(x,y)+1)];
end
q_vector_sum=[q_vector_sum,prod(q_vector)];
end
pr_Xr_Xj_vector(g)=sum(q_vector_sum);
end
end
alfa{k}(w)=sum(pr_Xr_Xj_vector.*ar_vector);
end
end
end
%Compute Lr
for k=1:route_number
path_length=length(link_routes{k});
q_vector_sum=[];
if path_length==1
Lr(k)=q{link_routes{k}(1)}(1);
else
%Make coordinates
coord_matrix=coordinates(0,C,path_length);
coord_length=size(coord_matrix,1);
for x=1:coord_length
%Add for later multiplication p_0(l,m,n,...)
%Sort X in increasing order because x1>=x2>=...>=xn
x_sorted=sort(coord_matrix(x,:));
x_sorted=x_sorted(length(x_sorted):-1:1);
q_vector=(p_m(0,x_sorted,C,d,method));
for y=1:path_length
q_vector=[q_vector,q{link_routes{k}(y)}(coord_matrix(x,y)+1)];
end
q_vector_sum=[q_vector_sum,prod(q_vector)];
end
Lr(k)=sum(q_vector_sum);
end
end
end
%Blocking in %
Lr=Lr*100;
%Assign blocking to VARARGOUT of function
blocking{1,blocking_dimension}=Lr;
%Make coordinates for summations in (9), (10) and (11); Because varoius
%paths are different in length we must compute pr_Xr_Xj in one loop. That's
%why we have to make coordinates for summation signs and assign them to
%specified Qs
function [coord_matrix]=coordinates(down,up,path_length)
coord_matrix(1:path_length)=down;
for w=path_length:-1:1
coord_matrix_temp=coord_matrix;
for k=down:up-1
coord_matrix_temp(:,w)=coord_matrix_temp(:,w)+1;
coord_matrix=[coord_matrix;coord_matrix_temp];
end
end
%Saving to structure
function [net_out]=save_network(description,structure,traffic,blocking,name);
save(name,'description','structure','traffic','blocking');
%Cannot make structure with cells of different dimension (sic!) - it needs
%checking
net_out=struct('blocking',blocking);
