bv.m

用BV算法可以实现交换机的高吞吐量

function [schedultable,schedullen,bandsize,matrixnumb]=bv(T) %流量矩阵T的行或列元素之和>10的矩阵

N=4; %交换机端口数
T=[3,2,4,1;2,5,1,2;4,1,3,5;2,4,2,3];%流量矩阵T的行或列元素之和>10的矩阵
INF=100;

%%%%%%备份原流量矩阵T
backupT=T; 
T1=T;
T2=T;
constbackT=T;  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%     计算最小需求带宽minbandwith      %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
minbandwith=0;%%% 表示最小需求带宽
g=zeros(1,N);%%%创建（1*N）的全零数组
h=zeros(1,N);

%%%%%%%  对T的列向量进行冒泡排序,按降序排列 
for j=1:N     
    for k=1:N-1  
        for i=1:N-k
            if T1(i,j)<T1(i+1,j)
                temp=T1(i,j);
				T1(i,j)=T1(i+1,j);
				T1(i+1,j)=temp;
            end
        end
    end
end
T1
%%%%%%%%%%%%%%   计算流量矩阵 T 的最小需求带宽    %%%%%%%%%%%
    %找出每行的最大值存入g[i]中
    for i=1:N 
        for j=1:N
            if T1(i,j)>g(i)
                g(i)=T1(i,j);
            end
        end
    end
    g
    %对T的行向量进行冒泡排序,按降序排列
    for i=1:N  
        for k=1:N-1
            for j=1:N-k
                if T2(i,j)<T2(i,j+1)
                    temp=T2(i,j+1);
                    T2(i,j+1)=T2(i,j);
                    T2(i,j)=temp;
                end 
            end
        end
    end 
    T2
 %找出每列的最大值存入h[i]中
 for j=1:N  
     for i=1:N
         if T2(i,j)>h(j)
             h(j)=T2(i,j);
         end
     end
 end  
 h
   tempminbandwith=0;   
   for i=1:N
       tempminbandwith=tempminbandwith+g(i);
   end
   minbandwith=0;
   for i=1:N
       minbandwith=minbandwith+h(i);
   end
   if tempminbandwith>minbandwith
       minbandwith=tempminbandwith;
   end
   fprintf('最小需求带宽等于');minbandwith
    
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
 %%%%%%%%%%%%%%%%           构造双随机矩阵T          %%%%%%%%%%%%%%%  
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %初始化 
   sumr=zeros(1,N);	%sumr[i]为第i行的元素和;
   suml=zeros(1,N);%suml[i]为第i列的元素和;
   decr=zeros(1,N);%decr[i]为第i行元素和与minbandwith的差;
   decl=zeros(1,N);%decrl[i]为第i列元素和与最大值max的差;  
 %%%%%%%%%        计算每行、每列元素和        %%%%%%%%%%%%
   for i=1:N
	   for j=1:N
           sumr(i)=sumr(i)+T(i,j);
	       suml(i)=suml(i)+T(j,i);
       end
   end   
 %%%%%%%%%       计算每行、每列元素和与最小需求带的差     %%%%%%%%%%%%
   for i=1:N
        decr(i)=minbandwith-sumr(i);
        decl(i)=minbandwith-suml(i);
   end  
 maxsum=0;%%% 每个元素所在的行和与列和的最大值
   for i=1:N
	   for j=1:N
           maxsum=sumr(i);
           if suml(j)>maxsum 
               maxsum=suml(j);
           end
           e=minbandwith-maxsum; %%% e表示矩阵T中每个元素应该加的值
           T(i,j)=T(i,j)+e;
           sumr(i)=sumr(i)+e;
           suml(j)=suml(j)+e;
           if sumr(i)==minbandwith
               break;
           end
       end %for j
   end%for i   
   fprintf('转换后的双随机矩阵T如下');T 
   
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
  %%%%%%%%%%%%%%%             进行BV分解             %%%%%%%%%%%%%%%% 
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  BANDWITH=2; %预先分配得到的调度矩阵的个数为2，后面matlab可以根据实际数修改
  p=zeros(N,N,BANDWITH);   %预附三维排列矩阵p为全零矩阵
    
  %%%% 循环分解得到一组排列矩阵的集合，直到T为0为止  
  bandsize=0;       %存放实际得到的需求带宽 
  matrixnumb=0;  %%%分解得到的排列矩阵个数  
  notzerotag=1;   %表示T是否为全零的标记，＝0为全零矩阵   
  while notzerotag        
	  temp=1;       
      lieb=randseed();%产生的置换排列放于lieb[]中
      for i=1:N
          j=lieb(i);
          temp=temp*T(i,j);  %for循环产生了一组置换列向量 
      end
      if temp~=0 
          min=INF;
          for i=1:N     %%%%%%  计算置换矩阵的系数=矩阵中非零元素的最小值
              k=lieb(i);
              if T(i,k)<min
                  min=T(i,k);
              end
          end 
          matrixnumb=matrixnumb+1;
          minq(matrixnumb)=min; %%%%% 存放分解得到的矩阵系数
          for i=1:N
              temp=lieb(i);
              p(i,temp,matrixnumb)=1;
              T(i,temp)=T(i,temp)-minq(matrixnumb);
          end 
          %判断分解后剩下的矩阵R是否为全零矩阵    
          notzerotag=0;
          for i=1:N    
              for j=1:N
                  if T(i,j)~=0 
                      notzerotag=1;
                      break;
                  end                      
              end
              if notzerotag==1
                  break;
              end
          end
      end %if
    end %while  
    fprintf('BV分解共得到的排列矩阵个数：');matrixnumb
    fprintf('个矩阵的系数分别为');minq
   for i=1:matrixnumb
	   bandsize=bandsize+minq(i);   
   end
   fprintf('\n实际的带宽需求等于');bandsize  
   fprintf('\n得到的调度表如下 ');   p
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%下面对p[i][j][t]进行LJ调度 得到调度表schedul[N][t],每一列对应一个时隙的调度
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    t=matrixnumb;    
    V=minbandwith;%%%  交换机端口速率      
    for i=1:t      
        selecttag(i)=minq(i);   %对t个标记的被选择标记附初值＝0：被调度完，~=0：未被调度完
        minq(i)=minq(i)/V;    %minq表示t个排列矩阵的系数
        tagclass(i)=1/minq(i);%对t个排列矩阵预附标记初值
        select(i)=tagclass(i);        
        position(i)=i;        
    end       
    selecttag,select,position
    
    for k=1:bandsize 
        for i=1:t     %对t个标记进行冒泡排序,按升序排列在select数组中
            for j=1:t-1
                if select(j)>select(j+1) 
                    temp2=select(j+1);
                    select(j+1)=select(j);
                    select(j)=temp2;     
                    temp1=position(j+1);
                    position(j+1)=position(j);
                    position(j)=temp1;
                    temp1=selecttag(j+1);
                    selecttag(j+1)=selecttag(j);
                    selecttag(j)=temp1;
                end
            end
        end%一次排序完成  
        k,select,selecttag,position
        for i=1:t
            if selecttag(i)~=0
                mintag=position(i);
                temp1=i;
                break;
            end
        end	
        %下面对p[][][mintag]调度
        for i=1:N
            for j=1:N
                if p(i,j,mintag)==1
                    schedul(i,k)=j;
                end
            end
        end
        %%%%%%%%%%修改被调度的排列矩阵的标记
        select(temp1)=select(temp1)+tagclass(mintag);
        selecttag(temp1)=selecttag(temp1)-1;
        select,selecttag,position
    end
    fprintf('\n得到的调度矩阵如下');
    schedul 
    
  %%%修改得到的调度表,删除冗余调度使其等于原流量
      for i=1:N
         for j=1:bandsize 
             if schedul(i,j)~=0
                 temp=schedul(i,j); 
                 if backupT(i,temp)>=1	
                     backupT(i,temp)=backupT(i,temp)-1;
                 else
                     schedul(i,j)=0;
                 end
             end
         end
     end 
     fprintf('\n删除冗余调度后得到的调度矩阵如下');schedul 
     
  %%%%  删除全零调度向量
  delenumb=0;% 删除向量的个数  
  for j=1:bandsize
      zeronumb=0;%计数器，计0的个数，为4时即为一个零调度向量应删除
      for i=1:N
          if schedul(i,j)==0
              zeronumb=zeronumb+1;
          end
      end
      if zeronumb==4
          for k=j+1:bandsize-delenumb
              for t=1:N
                  schedul(t,k-1)=schedul(t,k);
              end
          end
          delenumb=delenumb+1;
          zeronumb=0;
      end
  end
  fprintf('\n先删除全零调度后的调度表为：');   schedul  
  delenumb   

     schedullen=bandsize-delenumb;
     schedultable=zeros(N,2);
     for i=1:N
         for j=1:schedullen
             schedultable(i,j)=schedul(i,j);
         end
     end     
     T=constbackT;T
     fprintf('最终得到的调度表如下');schedultable 
     fprintf('size is');schedullen