simulation_dv.m

best routing protocol

function  res = simulation_dv(fn, n_beacons, n_failure_percent,failure_include_beacon)

verify_correctness = 0;
S = load(fn);
neighbor_dist = S.D;
tmp = randperm(S.n_nodes);
pre_landmarks = tmp(1:n_beacons);

tmp = randperm(S.n_nodes);
pre_landmarks = tmp(1:n_beacons);

if ~failure_include_beacon
  tmp = randperm(S.n_nodes);
end
n_failure_nodes = ceil(S.n_nodes* n_failure_percent);
failure_nodes = tmp(S.n_nodes-n_failure_nodes+1: S.n_nodes);
n = length(neighbor_dist);
failure_vector = zeros(n,1);
failure_vector(failure_nodes) = ones(length(failure_nodes),1);

debug = 1;

deltaA = zeros(1,n); % deltaA(v) == \delta(A,v)

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
  
  
fprintf('simulating scoped distance vector initial state..\n');
[dv, dv_packets, dv_entries_1] = distance_vector(neighbor_dist, deltaA);
if verify_correctness
  verify_DV(neighbor_dist, dv, deltaA)
end
fprintf('................................\n');

D_after_fail = neighbor_dist;
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

[dv2, dv_packets2, dv_entries_2] = distance_vector(D_after_fail, ...
						deltaA,failure_vector, ...
						dv, deltaA_f);
[dv3, dv_packets, dv_entries_3] = distance_vector(D_after_fail, ...
						deltaA);

if verify_correctness
  res = verify_DV(D_after_fail, dv2, deltaA_f, failure_vector)
end

res = struct(...
    'broadcast_1', lm_broadcast_snd,...
    'dv_entries_1',dv_entries_1,...
    'dv_entries_2',dv_entries_2,...
    'dv_entries_3',dv_entries_3,...
    'broadcast_2', broadcast_overhead(D_after_fail, A));

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