distance_vector.m

best routing protocol

function [dv, dv_packets, dv_entries] = distance_vector(neighbor_dist, ...
						  deltaA, failure_vector, ...
						  old_dv, deltaA_f)
%deltaA: column vector of the bunch radius
%failure_vector: boolean column vector indicating failure or not
%dv_packets: how many distance vector packets are sent
%dv_entries: in those dv packets, how many rt entries are contained
MAX_DISTANCE=100;
debug = 0;
n = length(neighbor_dist);
dv_packets = 0;
dv_round = 0;
dv_entries = 0;
dv = cell(n,1); %dv{1} is node 1's t-by-3 distance vectors:
		%dv{1}(dest,:)=[ nexthop, dist, valid_range, seq] 
use_classic_cr = 0;
%use_classic_cr = 1;
if use_classic_cr
  min_dist = 1;
else
  min_dist = 0; %increase the range one more hop
end
max_entry_once = 0; %maximum broadcast payload overhead

%calculate the initial DV and who should start sending what
updating_idx = cell(n,1);
if nargin<3
  %ok. default case
  for i=1:n
    dv{i} = sparse([]);
    dv{i}(n,4)=0;
    dv{i}(i,:) = [i 0 deltaA(i) 1];
    updating_idx{i} = [i];
  end
  dv_updated = deltaA'>min_dist;
else
  %failure recovery case
  dv = old_dv;
  failure_nodes = find(failure_vector);
  dv_updated = zeros(1,n);
  for i=1:n
    if failure_vector(i)
      continue
    end
    if deltaA_f(i)~=deltaA(i) 
      %the distance to the closest beacon changed
      if 0
	fprintf('node %d,distance to the closest beacon changed%d->%d\n', ...
		i,deltaA(i),deltaA_f(i));
      end
      dv{i}(i,3) = deltaA_f(i);
      dv{i}(i,4) = dv{i}(i,4) +1; %inc seq
      updating_idx{i} = [i];
      dv_updated(1,i) = 1;
    end
    
    for f = failure_nodes'
      dests = find(dv{i}(:,1)==f);
      if length(dests)>0
	%i,dests
	updating_idx{i} = union(dests, updating_idx{i} );
	%size(updating_idx{i})
	%invalidate the nexthop entry
	dv{i}(dests,2) = repmat(MAX_DISTANCE, length(dests), 1); 
	dv{i}(dests,3) = repmat(0, length(dests), 1);
	%clear the nexthop, but not the entry
	dv{i}(dests,1) = zeros(length(dests), 1); 
	if dv{i}==0
	  'asdfasdjf;klasdjfk'
	end
	dv_updated(1,i) =1;
      end
    end
  end
end
while sum(dv_updated)>0 
  dv_round = dv_round +1;
  fprintf('round %d************\n', dv_round);
  %print_dv(dv);
  new_dv = dv; %new_dv: dv after this round
  new_updating_idx = cell(n,1);
  dv_updated_new = zeros(1,n); %flag for next round
  for i = find(dv_updated)
    %node i's dv is updated, let's broadcast it in the neighborhood
    dv_packets = dv_packets +1;
    neighbors = find(neighbor_dist(i,:));
    %node i prepares the packet to send
    if length(updating_idx{i})==0
      continue
    end
    send_i = dv{i}(updating_idx{i},:);
    %unnecessary_idx = find(send_i(:,3)<=min_dist);
    %send_i(unnecessary_idx',:) = zeros( length(unnecessary_idx),3);
    %dests = find(send_i(:,1));
    dests = updating_idx{i};
    dv_entries = dv_entries + length(dests);
    max_entry_once = max(length(dests), max_entry_once);
    if debug
      %fprintf('node %d is broadcasting entries', i);
      %dests
    end
    for j = neighbors
      %j received dv_i
      if debug|dv_round>20
	fprintf('%d received dv from %d\n',j,i);
      end
      dv_i = send_i;
      dv_i(:,2) = dv_i(:,2)+repmat(neighbor_dist(i,j), length(dests), 1);
      dv_i(:,3) = dv_i(:,3)-repmat(neighbor_dist(i,j), length(dests), 1);
      dv_i(:,1) = repmat(i, length(dests),1);
      for k = 1:length(dests)
	%if dests(k)==53 & ismember(j,[1, 76, 83,99,54,72,71,89,78])
	%if  dests(k)==25 & ismember(j,[1,51, 64])
	if 0
	  debug=1;
	else
	  debug=0;
	end

	dst = dests(k);from=i; curr = j;
	%some reminder of the entries
	curr_nexthop = new_dv{j}(dst,1);
	from_nexthop = dv_i(k,1);%no need to send??
	curr_dist = new_dv{j}(dst, 2);
	from_dist = dv_i(k, 2);
	curr_range = new_dv{j}(dst, 3);
	from_range = dv_i(k, 3);
	curr_seq = new_dv{j}(dst, 4);
	from_seq = dv_i(k, 4);

	if debug
	  fprintf('rcvd %d->%d->%d=%d(%d.seq%d), curr:%d->%d->%d=%d(%d.seq%d)\n'...
		  ,curr,from,dst,from_dist,from_range,curr_seq,...
		  curr,curr_nexthop,dst,curr_dist,curr_range,from_seq);
	end
	
	to_update = 0; incoming_dv_is_worse = 0;
	will_send = 0;
	if curr_nexthop==0 
	  % curr_nexthop ==0 received an entry that didn't have
	  %take it
	  to_update =1;
	else % received an entry that existed
	  if curr_seq > from_seq
	    %old seq update. do not update
	    if debug
	      fprintf('worse seq\n');
	    end
	    incoming_dv_is_worse = 1;
	  elseif curr_seq < from_seq
	    %new seq update
	    to_update = 1;
	  else %equal seq. majority case
	    if curr_dist>from_dist
	      to_update = 1;
	      %incoming dv is better
	    elseif from==curr_nexthop & curr_dist~=from_dist+neighbor_dist(from, curr)
	      to_update = 1;
	      will_send = 1;
	    elseif curr_dist < from_dist-2*neighbor_dist(from, curr)
	      %fprintf('%d, %d current dist to %d %d less than from %d\n', curr,from,dst,curr_dist, ...
	      %      from_dist);
		%fprintf('update due to nexthop info changed\n');
		if 0 & debug
		  fprintf('incoming %d->%d->%d=%d\n'...
			  ,curr,from,dst,from_dist);
		end
		incoming_dv_is_worse = 1;
	    end
	  end
	end
	
	evicted_entry = 0;
	if to_update
	  if from_range>=min_dist
	    new_dv{curr}(dst,1:4) = dv_i(k,1:4);

	  else%clear current entry
	    if curr_nexthop >0
	      if debug
		fprintf('evict an-out-of range entry:dst=%d,curr=%d,from=%d\n'...
			,dst, curr, from);
	      end
	      new_dv{curr}(dst,1)=0;
	      new_dv{curr}(dst,2)=MAX_DISTANCE;
	      %new_dv{curr}(dst,3)=from_range+from_dist- ...
	      %MAX_DISTANCE;
	      new_dv{curr}(dst,3)=0;
	      new_dv{curr}(dst,4)=from_seq;
	      evicted_entry = 1;
	    else
	      new_dv{curr}(dst,1)=0;
	    end
	  end
	end
	if will_send | (to_update & new_dv{curr}(dst,3)>min_dist)...
	      | incoming_dv_is_worse | evicted_entry
	  %incoming_dv_is_worse
	  will_send=1;
	  dv_updated_new(j)=1;
	  new_updating_idx{j} = union(new_updating_idx{j}, [dst]);
	end
	if debug
	  evicted_entry;
	  to_update;
	  incoming_dv_is_worse;
	  fprintf('after %d->%d->%d=%d(%d) willsend=%d\n'...
		  ,curr,new_dv{curr}(dst,1),...
		  dst,new_dv{curr}(dst,2),...
		  new_dv{curr}(dst,3), will_send);
	end
      end %end of for each DV entry in the packet
      
    end %end of for each DV packet receiver
  end
  dv_updated = dv_updated_new;
  dv = new_dv;
  %for idx = length(new_dv)
  %  if new_dv{idx} clean up the lefted non-zeros 
  %end
  updating_idx = new_updating_idx;
  if debug
    %print_dv(dv);
  end
end

fprintf('DV packets: %d, # of round: %d, dv_entries:%d, max_entry_once:%d\n', dv_packets, ...
	dv_round, dv_entries, max_entry_once);
return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%old junk%%%%%%%%%%

	if new_dv{j}(dests(k),4)>dv_i(k,4) & new_dv{j}(dests(k),1)>0
	  if debug
	    fprintf('old seq update, ignore\n');
	  end
	elseif (new_dv{j}(dests(k),4) < dv_i(k,4)...
	      & new_dv{j}(dests(k),1)>0)
	      
	  if debug
	    fprintf('greater seq\n');
	  end
	  new_dv{j}(dests(k),4) = dv_i(k,4);
	  if dv_i(k,2)==Inf
	    new_dv{j}(dests(k),1) = 0;
	    new_dv{j}(dests(k),2) = Inf;%invalidate it!
	    dv_updated_new(j)=1;
	    %new_updating_idx{j}(length(new_updating_idx{j})+1) = dests(k);
	    new_updating_idx{j} = union(new_updating_idx{j}, [dests(k)]);
	  else
	    new_dv{j}(dests(k),:) = dv_i(k,:);
	    %fprintf('dest:%d,me: %d,from:%d:dist:%d, range:%d\n',dests(k),j,i,dv_i(k,2),dv_i(k,3));
	    if dv_i(k,3)>min_dist
	      dv_updated_new(j)=1;
	      %new_updating_idx{j}(length(new_updating_idx{j})+1) = dests(k);
	      new_updating_idx{j} = union(new_updating_idx{j}, [dests(k)]);
	    else
	      new_updating_idx{j} = setdiff(new_updating_idx{j}, [dests(k)]);
	    end
	  end
	    
	elseif dv_i(k,2)==Inf & new_dv{j}(dests(k), 1)>0 %a negative DV for failure case
	  %node i has a dead neighbor as nexthop to dests(k), see if j can
          %help
	  if debug
	    fprintf('recv neg dv from %d, dest=%d\n', i,dests(k));
	  end
	  if new_dv{j}(dests(k),1)==i
	    %oh. no.. j's nexthop is i!!
	    if debug
	      fprintf('oh no.%d nexthop is %d\n',j,i);
	    end
	    new_dv{j}(dests(k),1) = 0;
	    new_dv{j}(dests(k),2) = Inf;%invalidate it!
	    dv_updated_new(j)=1;
	    %new_updating_idx{j}(length(new_updating_idx{j})+1) = dests(k);
	    new_updating_idx{j} = union(new_updating_idx{j}, [dests(k)]);
	  elseif new_dv{j}(dests(k),3)> min_dist
	    dv_updated_new(j)=1;
	    new_updating_idx{j} = union(new_updating_idx{j}, [dests(k)]);
	    if debug
	      fprintf('%d will send out dest%d\n',j,dests(k));
	    end
	  else 
	    if debug
	      fprintf('%d will NOT send out dest due to out of range%d\n',j,dests(k));
	    end
	    new_updating_idx{j} = setdiff(new_updating_idx{j}, [dests(k)]);
	  end
	elseif ( new_dv{j}(dests(k),1)==0 & dv_i(k,2)<Inf)| ...
	      new_dv{j}(dests(k),2)>dv_i(k,2)%closer
	  new_dv{j}(dests(k),:) = dv_i(k,:);
	  if debug
	    fprintf('took it:dest:%d,me: %d,from:%d:dist:%d, range:%d\n',dests(k),j,i,dv_i(k,2),dv_i(k,3));
	  
	  end
	  if dv_i(k,3)>min_dist
	    dv_updated_new(j)=1;
	    %new_updating_idx{j}(length(new_updating_idx{j})+1) = dests(k);
	    new_updating_idx{j} = union(new_updating_idx{j}, [dests(k)]);
	  else
	    new_updating_idx{j} = setdiff(new_updating_idx{j}, [dests(k)]);
	  end
	else
	  if debug
	    fprintf('NOTHING: dest:%d,me: %d,from:%d:dist:%d, range:%d\n',dests(k),j,i,dv_i(k,2),dv_i(k,3));
	  end
	end