compactrouting.m

best routing protocol

curr = src;
weirdo = 0; %debug routing failure
%routing_load(curr) = routing_load(curr) +1; 
prev = -1;
passed_beacon = 0;
est_dist = Inf; %estimated distance to the destination
best_est_dist = Inf;
ttl = (deltaA(dest)+beacon_vectors(curr,cent(dest)))+10;
best_total_dist = (deltaA(dest)+beacon_vectors(curr,cent(dest)));

while curr~=dest
  
  %now the packet arrives at node curr
  tmpid = [];
  redirected_by_bcn = 0;
  if reactive==1 & length(label)>0
    tmpid = find(label==curr);
  end
  
%  if neighbor_dist(curr, dest)>0;
%    next = dest;
%    est_dist = 1;
%    if debug_route
%      fprintf('->n%d[1]', next);
%    end
  if routing_table(curr,dest)>0
    next = routing_table(curr, dest);
    est_dist = direct_dist(curr, dest);
    passed_beacon = 1;
    if debug_route
      fprintf('->r%d[%d]', next,direct_dist(curr,dest));
      if direct_dist(curr,dest)<=0
	fprintf('??????');
      end
    end
  elseif isbeacon(dest)
    next = nexthop2bcn(curr,isbeacon(dest));
    est_dist = beacon_vectors(curr,isbeacon(dest));
    if debug_route
      fprintf('->B%d[%d]', next, beacon_vectors(curr,isbeacon(dest)));
    end
  elseif curr ==cent_dest
    next = label(1);
    redirected_by_bcn = 1;
    passed_beacon = 1;
    est_dist = deltaA(dest);
    fprintf('routing via label\n');%%shouldn't happen when the
                                   %range is not typical CR
    if debug_route
      fprintf('->L%d[%d]', next, deltaA(dest));
    end
  elseif reactive==1 & length(tmpid)==1
    next = label(tmpid+1);
    est_dist = length(label)-tmpid+1;
    if debug_route
      fprintf('->LL%d[?]', next);
    end
  else%routing towards the beacon
    next = nexthop2bcn(curr, cent(dest));
    est_dist = deltaA(dest)+beacon_vectors(curr,cent(dest));
    if passed_beacon==1 & ~weirdo
      fprintf('weird. we should not have passed the beacon\n');
      weirdo = 1;
    end
    
    if debug_route
      fprintf('->b%d[[%d]]', next,deltaA(dest)+beacon_vectors(curr,cent(dest)));
    end
  end
  best_est_dist = min(best_est_dist, est_dist);
  best_total_dist = min(best_total_dist, est_dist+hops-1);
  
  if 0 & (est_dist+hops-1-best_total_dist>=3) & failure_nodes(next)
    fprintf('wasted hops:%d\n',est_dist+hops-1-best_total_dist);
    next = -1; %this one doesn't work well
    routing_dist = Inf;
    break;
  end
  % we got a potential next hop, but haven't sent the packet yet.
  if failure_nodes(next) | (next==prev)
    failed_hops = failed_hops + 1;
    max_consecutive_fail = max(max_consecutive_fail,failed_hops);
    if debug_route
      fprintf('->DEAD(%d)',next);
      fprintf('{%d}',max_consecutive_fail);
    end
    failover_nexts = find(neighbor_dist(curr,:)>0 & ~ ...
			  failure_nodes');
    failover_nexts = setdiff(failover_nexts, [prev]);
    l = length(failover_nexts);
    
    next_distance = repmat(Inf,l,1);
    dead_node = next; %will be transmitted to neighbors for reference
    next = prev;
    if l==0
      if debug_route
	fprintf('ALLDEAD')
      end
    else
      %imagine curr node is broadcasting the local recovery request
      routing_load(curr) = routing_load(curr) + 1;
      routing_dist = routing_dist + 1;
    end
    
    for i=1:l
      next = failover_nexts(i);
      next2 = -1;
      tmpid = [];
      redirected_by_bcn = 0;
      if reactive==1 & length(label)>0
	tmpid = find(label==next);
      end
      if routing_table(next,dest)>0
	next_distance(i) = direct_dist(next, dest);
	next2 = routing_table(next,dest);
      elseif isbeacon(dest)
	next_distance(i) = beacon_vectors(next, isbeacon(dest));
	next2 = nexthop2bcn(next, isbeacon(dest));
      elseif next==cent_dest
	next_distance(i) = deltaA(dest);
	next2 = label(1);
      elseif reactive==1 & length(tmpid)==1
	next_distance(i) = length(label)-tmpid+1;
	next2 = label(tmpid+1);
      else % route via beacon
	next_distance(i) = deltaA(dest)+beacon_vectors(next, ...
						       cent(dest));
	next2 = nexthop2bcn(next, cent(dest));
      end
      if failure_nodes(next2)
	%next_distance(i) = MAX_ROUTE_HOPS; %don't route it
	next_distance(i) = next_distance(i) + 0.5;
      end
      if next2==curr
	next_distance(i) = MAX_ROUTE_HOPS;
      end
      
    end %for each live neighbor
    if l>0
      
      %the neighbors will respond to the sender in the order of
      %next_distance. if it's the same, break it by a random number
      next_distance_weight = next_distance + rand(l,1)*0.1;
      ack_to_send = zeros(n,1);
      ack_to_send(failover_nexts) = ones(l,1);
      next = -1;
      while length(find(ack_to_send)>0)
	[tmp_dist min_idx] = min(next_distance_weight);
	next_distance_weight(min_idx) = Inf;
	tmp_dist = next_distance(min_idx);
	%if est_dist - tmp_dist<-0.6%!!!!
	%  break
	%end
	
	ack_node = failover_nexts(min_idx);
	if next<0 %no one has acked yet
	  if tmp_dist >= MAX_ROUTE_HOPS
	    %all nodes can't reach the dest
	    %nobody does broadcast
	    if debug_route
	      fprintf('->DEADEND');
	    end
	    break;
	  end
	  next = ack_node;
	  if debug_route
	    fprintf('->try(%d:%.1f)',next,est_dist-tmp_dist);
	  end
	end
	if tmp_dist>=MAX_ROUTE_HOPS %ok, the rest of the nodes will not reply
	  break
	end
	if ~ack_to_send(ack_node)
	  %fprintf('saved one bd\n');
	  continue %don't send broadcast
	end
	routing_load(ack_node) = routing_load(ack_node) + 1;
	routing_dist = routing_dist + 1;
	%hops = hops +1;
	%routing_path(hops) = ack_node;
	%other nodes that receive this ack should not ack again
	nodes_recv_ack = find(neighbor_dist(ack_node,:));
	ack_to_send(nodes_recv_ack) = zeros(length(nodes_recv_ack), ...
					    1);
	ack_to_send(ack_node) = 0;
      end
    else %no neighbor except prev available, how sad
      stats.fail_due2prev = stats.fail_due2prev + 1;
      if next~=prev
	error('absurd.');
      end
      if debug_route
	fprintf('->back2prev');
      end
      next = -1;
    end
  else %not failed nexthop
    %max_consecutive_fail = max(max_consecutive_fail,failed_hops);
    failed_hops = 0; %clear it
  end % end of if failure
  
  ttl = ttl -1;
  if ttl<0 | next<0
    routing_dist = Inf;
    if ttl<0
      stats.fail_due2ttl = stats.fail_due2ttl + 1;
    end
    if debug_route & ttl<0
      fprintf('TTLexp');
    end
    break;
  end
  
  if reactive==1 
    if redirected_by_bcn
      if header(k,2)>0
	error('something impossible happened');
      end
      %clear all headers anyway because path may not be optimal
      header(:,1) = zeros(k,1);
    end
    %update the header
    if deltaA(curr)>neighbor_dist(curr, next)
      header(1,:) = [curr deltaA(curr) 0]; 
    end
  end
  
  if ismember(next, routing_path) & ~found_loop
    found_loop =1;
    %fprintf('found loop and exit as failing\n');
    next = -1;
    routing_dist = Inf;
    break;
  end
    
  prev = curr;
  curr = next;
  %the actual packet got transmitted here to the next hop

  hops = hops +1;
  routing_path(hops) = next;
  routing_load(prev) = routing_load(prev) +1;
  routing_dist = routing_dist+neighbor_dist(prev, curr);
    
  if reactive==1%upon receiving the packet, update routing table
    %update the distances in the header, and sort it
    header(:,2) = header(:,2)-neighbor_dist(prev, curr);
    header(:,3) = header(:,3)+neighbor_dist(prev, curr);
    [tmp idx] = sort(header(:,2));
    header = header(idx,:);
    
    in_cluster_id = find(header(:,2)>=0 & header(:,1)>0); %!!>= is
                                                          %not
                                                          %exactly CR
    %in_cluster_id = find(header(:,2)>0 & header(:,1)>0);
    l = length(in_cluster_id);
    if l>0
    %if 0 %!!!!!!!!!!!!!!!
      routing_table(curr, header(in_cluster_id,1)) = ...
 	  repmat(prev, 1, l);
      direct_dist(curr, header(in_cluster_id,1)) = header(in_cluster_id,3)';
%      if debug_route
      if 0
	fprintf('updating routing table of %d: nexthop:%d,dests:',curr, ...
		routing_path(hops-1));
	header(in_cluster_id,1)
      end
      
    end
  end  
end

if routing_dist ==Inf
  if passed_beacon 
    stats.fail_after_beacon = stats.fail_after_beacon + 1;
  else
    stats.fail_before_beacon = stats.fail_before_beacon + 1;
  end
  stats.fail_total = stats.fail_total + 1;
  if 0 & ttl<0 
    max_consecutive_fail, hops
  end
  if weirdo
    fprintf('failed, and weirdo==1\n');
  end
  if found_loop
    %fprintf('failed, and found_loop==1\n');
  end
  %est_dist - best_est_dist
end
if 0 & max_consecutive_fail > 2
  fprintf('max_consecutive_fail=%d, failed=%d\n',max_consecutive_fail, ...
	  routing_dist == Inf);
end
if debug_route
  fprintf('\n');
end


function S = sample(W, s)
%return a random subset of W by selecting each element,
%independently with probability s/|W|

n = length(W);
if n<=s
  S = W;
  return
end
idx = find(rand(1,n) < s/n);
S = W(idx);
return

function [b_snd, b_rcv, nexthop,label,d_dist] = BFS(start_node, range, neighbor_dist, ...
			       min_dist, cent)
% use breadth first search to simulate broadcasting a packet from a
% node within certain range
% BFS is more realistic than DFS because the nature of broadcasting
% min_dist: the minimal distance that two nodes could possibly be,
% 1 if it's hop count, must be >=0
% b_snd: how many broadcast packets are sent
% b_rcv: how many broadcast packets are received
% nexthop(i): to start_node
% cent: closest beacon to start_node
% label: =nexthop(cent,start_node)
% d_dist(i): distance between i and start_node if i is in routing_table
label = 0;
queue = [[start_node, range, 0]];
b_snd = 0;
b_rcv = 0;
nexthop = sparse([]);
n = length(neighbor_dist);
nexthop(n) = 0;
d_dist = nexthop;
if range<=min_dist
  return
end


shortest_dist = repmat(Inf, 1, n); % the initial shortest distance to node
shortest_dist(start_node) = 0; %except to itself
%fprintf('start brdcst(cent%d):',cent);
while length(queue)>0
  %dequeue
  current = queue(1,:);
  node = current(1); range = current(2); dist = current(3);
  [l,tmp] = size(queue);
  queue = queue(2:l,:);

  %fprintf('->%d',node);
  
  %broadcast on current node
  neighbors = find(neighbor_dist(node,:));
  b_snd = b_snd + 1;
  b_rcv = b_rcv + length(neighbors); % all neighbors will hear it
  for i=1:length(neighbors)
    dst = neighbors(i);
    if dst==node
      continue
    elseif dst==cent
      label = node;
    end
    if range-neighbor_dist(node, dst)<min_dist
      continue
    end
    if dist+neighbor_dist(node,dst)<shortest_dist(dst)
      shortest_dist(dst) = dist+neighbor_dist(node,dst);
%      fprintf('%d->%d---->%d\n',dst, node, start_node);
      nexthop(dst) = node;
      [l,tmp] = size(queue);
      queue(l+1,:) = [dst, range-neighbor_dist(node, dst),dist+ ...
		      neighbor_dist(node,dst)];
    end
  end
end
idx = find(shortest_dist<Inf);
d_dist(idx) = shortest_dist(idx);
%fprintf('\n');