No BSD License  

Highlights from
WDM Network Blocking Computation Toolbox

image thumbnail

WDM Network Blocking Computation Toolbox

by

 

21 Apr 2004 (Updated )

Blocking computation in WDM Networks for three different types of constraints.

varargout=compute_blocking_birman(varargin)
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);

Contact us