test_dv.m

best routing protocol

function  [res,dv,dv2] = test_dv(fn, n_beacons, failure_nodes)
verify_correctness = 0;
if isstr(fn)
  S = load(fn);
else
  topology_generator('tmp.mat',fn, 5.12, 0,0,0);
  S = load('tmp.mat');
end
%D = sparse([0 1 0 1;1 0 1 0; 0 1 0 1; 1 0 1 0]);%!!
%n_nodes = 4;%!!
neighbor_dist = S.D;
tmp = randperm(S.n_nodes);
pre_landmarks = tmp(1:n_beacons)
%pre_landmarks = [1 ]%!!
%pre_landmarks = [113   143    19]

if nargin<3
  failure_nodes = [1];
end
failure_nodes
tmp = failure_nodes;
n = length(neighbor_dist);
failure_vector = zeros(n,1);
failure_vector(tmp) = ones(length(tmp),1);
if n<=100
  %visualize(S.D, S.coord, pre_landmarks, failure_nodes, 1,1 );
end
debug = 1;
debug_route = 0; %this will generate a lot of debug information
if ~issparse(neighbor_dist)
  neighbor_dist = dist_full2sparse(neighbor_dist);
end

n = length(neighbor_dist);
%fprintf('calculating best path...');
%[delta optimal_nexthop] = floyd_warshall(neighbor_dist);
%[delta optimal_nexthop] = allpair_dijkstra(neighbor_dist);
%fprintf('done\n');

%%%select landmarks
W = 1:n;
if nargin<2
  pre_landmarks = []; 
end

if nargin<3
  tmp1 = repmat(1:n,n,1);
  tmp2 = tmp1';
  rest_pairs = [tmp1(:) tmp2(:)];
end


out_degree = full(sum(neighbor_dist>0,2));
%C = zeros(n,n); %C(w,v)==1 means v \in C(w)
%routing_table(w,v)=nexthop, if v \in C(w)
routing_table = sparse([]);
routing_table(n,n) = 0;
%direct_dist = routing_table; %should be sync with routing_table:
                             %direct_dist(w,v)=shortest_dist bwteen w&v
for i=1:n
  tmp = find(neighbor_dist(:,i));
  routing_table(tmp,i)=repmat(i,length(tmp),1);
end
%routing_table
direct_dist = neighbor_dist;
%nexthop2bcn(i,b) = nexthop(i,b) where b is the relative beacon id
deltaA = zeros(1,n); % deltaA(v) == \delta(A,v)
%cent(u), the closest landmark to each node, relative index to A

A = [];
s = sqrt(n*log(n)/log(2));
A = sort(pre_landmarks);
ordinary_nodes = setdiff(1:n, A);
isbeacon = zeros(n,1);
isbeacon(A) = 1:length(A);
%every landmark floods the network
lm_broadcast_snd = broadcast_overhead(neighbor_dist, A);
%lm_broadcast_rcv = length(A)*sum(out_degree);

if debug
  fprintf('# broadcast packets sent: %d\n', lm_broadcast_snd);
  %fprintf('# broadcast packets received: %d\n', lm_broadcast_rcv);
end

[beacon_vectors, nexthop2bcn] = allpair_dijkstra(neighbor_dist, A);
[deltaA, cent] = min(beacon_vectors,[],2);
%plot_cumu_matrix(deltaA);%!!!!
if debug
  fprintf('mean and max deltaA:%.1f, %.1f\n', mean(deltaA), ...
	  max(deltaA));
end
if debug & n<=50
  deltaA'
end
  
  
%now sort out the clusters for ordinary nodes
%%C = delta < repmat(deltaA,n,1);
%%C = delta <= repmat(deltaA,n,1); %!!!change from the algorithm
%%C(:,A) = zeros(n, length(A));
%%C(A,:) = zeros(length(A),n);

%ok. distance vector mode
fprintf('simulating scoped distance vector..\n');
[dv, dv_packets, dv_entries] = distance_vector(neighbor_dist, deltaA);
%update routing_table and direct_dist according to dv
%rt = full(routing_table);
%for i=1:n
%  dests = find(dv{i}(:,1)>0);
%  rt(i,dests) = dv{i}(dests,1)';
%  rt(i,i) = 0;
%end
%routing_table = sparse(rt);
%clear rt;
routing_table = dv2rt(dv, routing_table);


%print_dv(dv)
if verify_correctness
  verify_DV(neighbor_dist, dv, deltaA)
end
fprintf('................................\n');


D_after_fail = neighbor_dist;
failure_nodes
D_after_fail(failure_nodes,:) = zeros(length(failure_nodes), n);
D_after_fail(:, failure_nodes) = zeros(n, length(failure_nodes));

[beacon_vectors_f, nexthop2bcn_f] = allpair_dijkstra(D_after_fail, A);
[deltaA_f, cent_f] = min(beacon_vectors_f,[],2);
if debug
  fprintf('mean and max deltaA_f:%.1f, %.1f\n', mean(deltaA_f), ...
	  max(deltaA_f));
end
%deltaA-deltaA_f

[dv2, dv_packets, dv_entries] = distance_vector(D_after_fail, ...
						deltaA,failure_vector, ...
						dv, deltaA_f);
%[dv3, dv_packets, dv_entries] = distance_vector(D_after_fail, ...
%						deltaA);

%cell_equal(dv,dv2)
%cell_equal(dv,dv)
%cell_equal(dv3,dv2)
%print_dv(dv)
res = 1;
if verify_correctness
  res = verify_DV(D_after_fail, dv2, deltaA_f, failure_vector)
end
%print_dv(dv2)
%print_dv(dv,76)
%print_dv(dv2,76)
%res

function b = cell_equal(c1, c2)
b = 0;
if length(c1)~=length(c2)
  return
end
for i=1:length(c1)
  if c1{i}==c2{i}
    continue
  end
  return
end
b = 1;
return

function b = verify_DV(D, dv, deltaA, failure_vector)
% make sure that everything is contained in the routing table, 
MAX_DISTANCE=100;
n = length(D);
[delta optimal_nexthop] = allpair_dijkstra(D);
b = 1;
if nargin<4
  failure_vector = zeros(n,1);
end
for i=1:n
  if failure_vector(i)
    continue
  end
  if deltaA(i)>=MAX_DISTANCE %e.g. inf
    nodes_in_range = find(delta(i,:)<=MAX_DISTANCE); %!!classic is <
  else
    nodes_in_range = find(delta(i,:)<=deltaA(i)); %!!classic is <
  end
  for j=nodes_in_range
    nexthop = dv{j}(i,1);
    dist = dv{j}(i,2);
    range = dv{j}(i,3);
    if nexthop==0
      fprintf('missing DV in %d, dest %d\n',j,i);
      b = 0;
    elseif dist~=delta(i,j)
      fprintf('wrong DV in %d, dest %d, dist should be %d, but is %d\n',...
	      j,i,delta(i,j), dist);
      b = 0;
    elseif dist+range~=deltaA(i)
      fprintf('wrong DV in %d, dest %d, range should be %d, but is %d\n',...
	      j,i,deltaA(i)-dist, range);
      b = 0;
    %elseif dv{nexthop}(i,2)+D(j,nexthop)~=dist
    elseif delta(nexthop,i)+D(j,nexthop)~=delta(j,i)
      fprintf('invalid nexthop %d selection in %d, dest %d\n',nexthop, ...
	      j,i);
      b = 0;
    end
    
  end
    
end  
%make sure everything in DV is necessary
% and everything in the DV is correct
for i=1:length(dv)
  if failure_vector(i)
    continue
  end
  dests = find(dv{i}(:,1));
  for j=1:length(dests)
    k=dests(j);
    nexthop =dv{i}(k,1);
    dist = dv{i}(k,2);
    range = dv{i}(k,3);
    if dv{i}(k,2)>deltaA(k)
      fprintf('uneccssary dv in %d, dest=%d,dist=%d, deltaA=%d,nexthop=%d\n',i,k,...
	      dist, deltaA(k), nexthop);
    end  
    if dist~=delta(k,i) 
      if dist<MAX_DISTANCE | delta(k,i)<MAX_DISTANCE
	fprintf('in %d, dest=%d,** wrong dist should be %d, but is %d\n'...
		,i,k,delta(k, i),dist);
	b=0;
      end
    end
    if dist+range~=deltaA(k)
      
      fprintf('in %d,next %d dest=%d **wrong range: should be %d, but is %d\n',...
	      i,nexthop,k,deltaA(k)-delta(k,i), range);
      b=0;
    end
    if delta(nexthop,k)+D(i,nexthop)~=delta(k,i)
      fprintf('in %d, dest=%d ** invalid nexthop: %d\n', i,k,nexthop);
      b=0;
    end
      
  end
end