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.

p_m.m
function varargout=p_m(varargin)
%P_M Compute propability of finding M free channels on a path with C
%channles with/without channel conversion.
%   P_M probability is computed according to [1], [2] - no conversion,
%   [3] - sparse conversion, [4] - full conversion.
%
%   [PROB]=P_M(N,X,C,D,METHOD) computes propability stated in [4] - case
%   for WDM network. X is the vector of free channles on all considered
%   links, N is the expected value of free channles with he same number on
%   all considered links, D is the conversion degree, C is the number of
%   channels on every link and METHOD is the type of conversion, where:
%       1 - no conversion,
%       2 - full conversion,
%       3 - sparse conversion.
%   
%   When METHOD is different than 3 than D can be empty (D will be ommited
%   during computation).
%
%   See also COMPUTE_BLOCKING_BIRMAN, COMPUTE_BLOCKING_KOVACEVIC, P_L.
%
%   References:
%       [1] Milan Kovacevi, Anthony Acampora, "Benefits of Wavelength
%       translation in All-Optical Clear Channel Networks", IEEE Journal on 
%       Selected Areas in Communications, vol. 14, June 1996 
%       [2] Alexander Birman, "Computing Approximate Blocking Probabilities
%       for a Class of All-Optical Network", IEEE Journal on
%       Selected Areas in Communications, vol. 14, June 1996 
%       [3] 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 
%       [4] S. Chung, A. Kashper, K.W. Ross, "Computing Approximate
%       Blocking Propabilities for large loss networks", IEEE/ACM
%       Transactions on Networking, vol. 1, 1993

%   Copyright 2003-2004 Przemyslaw Pawelczak
%   E-mail: przemyslaw_pawelczak@idg.com.pl
%   Wroclaw University of Technology, Poland
%   $Revision: 1.0 $  $Date: 2004/05/08 15:03:12 $

%If no D specified then it will be i.e. "1"
if nargin==4
    varargin{5}=varargin{4};
    varargin{4}=1;
end

%Exeption handling
message=nargchk(4,5,nargin);
testing_int=[varargin{1},varargin{2},varargin{3},varargin{4},varargin{5}];
if ~isempty(message)
    error('MATLAB:P_M:NumberOfInputArguments',...
        message);
end 
if find(isnan(testing_int))
    error('MATLAB:P_M:ArgumentType',...
        'Arguments must be numbers.');
end
%Check if VARARGIN are positive integers
if sum([testing_int<0,fix(testing_int)~=testing_int])~=0
    error('MATLAB:P_M:ArgumentType',...
        'Arguments must be positive integers.');
end

%Change string into number (for all number arguments)
for k=1:5
    if isstr(varargin{k})==1
        varargin{k}=str2num(varargin{k});
    end
end

%Give names to input arguments
N=varargin{1};
X=varargin{2};
C=varargin{3};
D=varargin{4};
Method=varargin{5};

%Type of method
switch Method
    %No conversion
    case 1
        %Basic case - two links
        if length(X)==2
            varargout{1}=beta_2(N,X(1),X(2),C);
            %If there are more than two links
        else
            %Recursion verctor of probabilities
            P_former=[];
            for k=N:X(2)
                P_former=[P_former,beta_2(k,X(1),X(2),C)];
            end
            %Compute according to (4) in [2]
            position=2;
            P=[];
            P_former_temp=[];
            while position~=length(X)
                for N_prim=N:X(position)
                    for k=N:X(position)
                        P=[P,beta_1(N_prim,k,X(position+1),C,D)...
                                *P_former(length(P)+1)];
                    end
                    P_former_temp=[P_former_temp,sum(P)];
                    P=[];
                end
                P_former=P_former_temp;
                position=position+1;
            end
            varargout{1}=P_former(1);
        end
        %Full conversion    
    case 2
        %If on all hops number of free channels will be >=N and if jus one
        %channel will have free N channels then probability will be 1
        if find(X==N)>=1 & length(find(X>=N))==length(X)
        %if find(X==0)>=1
            varargout{1}=1;
            %Else
        else
            varargout{1}=0;
        end
        %Sparse conversion
    case 3
        %Basic case - two links
        if length(X)==2
            varargout{1}=beta_1(N,X(1),X(2),C,D);
            %If there are more than two links
        else
            %Recursion verctor of probabilities
            P_former=[];
            for k=N:X(2)
                P_former=[P_former,beta_1(k,X(1),X(2),C,D)];
            end
            %Compute according to (10) in [3]
            position=2;
            P=[];
            P_former_temp=[];
            while position~=length(X)
                for N_prim=N:X(position)
                    for k=N:X(position)
                        P=[P,beta_1(N_prim,k,X(position+1),C,D)...
                                *P_former(length(P)+1)];
                    end
                    P_former_temp=[P_former_temp,sum(P)];
                    P=[];
                end
                P_former=P_former_temp;
                position=position+1;
            end
            varargout{1}=P_former(1);
        end
end

%Implementation of (3) form [3] - sparse conversion
function [p_m_sparse]=beta_1(N,X,Y,C,D);

%Memory reservarion for vector p_m_sparse
p_m_sparse=[];

%If Y>X then swap places, just like in [3]: "We can rearrange the links
%such that the links of the path have free wavelengths in increasing order
%and we can use (3) to compute p_m(x,y)"
if Y>X
    A=X;
    X=Y;
    Y=A;
end

%Compute lower side of sum in (3)
sum_down=min(C,X+2*D);
%Compute upper side of sum in (3)
sum_up=min(C,(2*D+1)*X);

%Compute right side of (3)
p_gamma=[];
for l=sum_down:sum_up
    %If it is possible to compute binomial 
    if (l-2*D)>=X
        %Compute according to (9)
        p_gamma=[p_gamma,nchoosek(C,1)*nchoosek(l-2*D,X)/nchoosek(C,X)];
        %If it is not possible to compute binomial 
    else
        p_gamma=[p_gamma,0];
    end
end
%Remove last element form p_g
if length(p_gamma)~=0
    p_gamma(length(p_gamma))=[];
end
%Compute according to (5)
%See the notes in [3]
p_gamma_left=[p_gamma,1];
p_gamma_right=[0,p_gamma];
p_gamma=p_gamma_left-p_gamma_right;

%Compute left side of (3)
for l=sum_down:sum_up
    %If it is possible to compute then - do it
    %Check exeptions, see notes in [3]
    if (C-l)>=(Y-N) & l>=N & Y>=N
        p_m_sparse=[p_m_sparse,nchoosek(l,N)*nchoosek(C-l,Y-N)/nchoosek(C,Y)];
        %If it is not possible to compute then assign zero
    else
        p_m_sparse=[p_m_sparse,0];
    end
end

%Multiply left side by right and assign to R
p_m_sparse=sum(p_m_sparse.*p_gamma);


%Implementation of (2) form [1] - no conversion
function [p_m_sparse]=beta_2(N,X,Y,C);
if max(0,X+Y-C)<=N & min(X,Y)>=N
    p_m_sparse=(nchoosek(X,N)*nchoosek(C-X,Y-N))/nchoosek(C,Y);
else
    p_m_sparse=0;
end

%Another implementation: equation (3) form [2] - no conversion
%if max(0,X+Y-C)<=N & min(X,Y)>=N
%    i=1:N;
%    left=prod((X-i+1)./(C-i+1));
%    i=1:(Y-N);
%    right=prod((C-X-i+1)./(C-N-i+1));
%    p_m_sparse=nchoosek(Y,N)*left*right;
%else
%    p_m_sparse=0;
%end

Contact us