cr_bf_routing.m

best routing protocol

function [routing_path, routing_dist, direct_dist] =cr_bf_routing(src, ...
	dest, cent, A, debug_route, beacon_vectors, neighbor_dist, ...
	  p, coe1, coe2, rbf, rtb, reactive, ...
	  deltaA, direct_dist, failure_nodes)
routing_path = [src];
routing_dist = 0;
hops =1;
if src==dest
  routing_dist = 0;
  return
end
k=5;
header = zeros(k,3); %packet annotation: k1 node's info:
                     %format(id,range,dist) range+dist==deltaA(id)
cent_dest = A(cent(dest)); %the closest landmark to dest
if debug_route
  fprintf('%d->%d:', src, dest);
end
  
if beacon_vectors(dest, cent(dest))==Inf | beacon_vectors(src, ...
						  cent(dest))==Inf
  %not reachable
  routing_dist = Inf;
  fprintf('unreachable\n');
  return
end
curr = src;
prev = -1;
passed_beacon = 0;
est_dist = Inf; %estimated distance to the destination

while curr~=dest

%disp((rtb{curr})');
%fprintf(1,'  curr %d, dest %d',curr, dest);

  tmpid = [];
  redirected_by_bcn = 0;
  if reactive & length(label)>0
    tmpid = find(label==curr);
  end
%{
% for debugging
tmpidx = find(rtb{curr}(:,1)==dest);
if ~isempty(tmpidx)
  tmpnext = rtb{curr}(tmpidx(1),2);
  %fprintf(1,', next %d',tmpnext);
else
  tmpidx = find(rtb{curr}(:,1)==cent_dest);
  if ~isempty(tmpidx)
    tmpnext = rtb{curr}(tmpidx(1),2);
    %fprintf(1,', cent_dest %d, next %d',cent_dest,tmpnext);
  else
    %rtb{curr}'
  end
end
%fprintf(1,'\n');
%}  
  if neighbor_dist(curr, dest)>0;

%fprintf(1,'dest %d is a neighbor of curr %d\n',dest,curr);

    next = dest;
    est_dist = 1;
    if debug_route
      fprintf('->n%d[1]', next);
    end
%{
  elseif routing_table(curr,dest)>0
    next = routing_table(curr, dest);
    est_dist = direct_dist(curr, dest);
    if debug_route
      fprintf('->c%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);
    if debug_route
      fprintf('->L%d[%d]', next, deltaA(dest));
    end
  elseif reactive & length(tmpid)==1
    next = label(tmpid+1);
    est_dist = length(label)-tmpid+1;
    if debug_route
      fprintf('->LL%d[?]', next);
    end
  else
    next = nexthop2bcn(curr, cent(dest));
    est_dist = deltaA(dest)+beacon_vectors(curr,cent(dest));
    if debug_route
      fprintf('->b%d[[%d]]', next,deltaA(dest)+beacon_vectors(curr,cent(dest)));
    end
%}
  else	% look up the bloom filter at current node
    % try all neighbors to find the next hop in the bloom filter
    neighbors = find(neighbor_dist(curr,:)>0);
    bitlength = length(rbf{curr});
    %rbf{curr}'
    found = 0;
    for i=1:length(neighbors)
      ngb = neighbors(i);
      bitpos = mod(mod(coe1*dest + coe2*ngb,p),bitlength);
      %rbf{curr}(bitpos+1)'
      tmp = sum(rbf{curr}(bitpos+1));
      if tmp >= length(coe1)
        next = ngb;
        found = 1;
        break;
      end
    end
    if found == 0	% if no next hop to dest, go to cent_dest first
      for i=1:length(neighbors)
        ngb = neighbors(i);
        bitpos = mod(mod(coe1*cent_dest + coe2*ngb,p),bitlength);
        %rbf{curr}(bitpos+1)'
        tmp = sum(rbf{curr}(bitpos+1));
        if tmp >= length(coe1)
          next = ngb;
          found = 1;
          break;
        end
      end
    end
    if found == 0
      %not reachable
      routing_dist = Inf;
      error('not found next hop: cur %d, dst %d\n',curr,dest);
    end
  end

  % detect routing loop
  if ~isempty(find(routing_path==next))
    fprintf(1,'routing loop!\n');
    %routing_path
    %pause
    routing_dist = Inf;
    return;
  end

  hops = hops +1;
  routing_path(hops) = next;
  routing_dist = routing_dist+neighbor_dist(curr, next);
  
  if reactive 
    if redirected_by_bcn
      if header(k,2)>0
	error('something impossible happened');
      end
      %clear all headers anyway -- 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
    header(:,2) = header(:,2)-neighbor_dist(curr, next);
    header(:,3) = header(:,3)+neighbor_dist(curr, next);
    %expired_idx = find(header(:,2)<=0); 
    %expired_idx = find(header(:,2)<0); %!!!not compact routing
    %header(expired_idx,1) = zeros(length(expired_idx), 1);
    [tmp idx] = sort(header(:,2));
    header = header(idx,:);
  
  end

  prev = curr;
  curr = next;

%fprintf(1,'    curr updated\n');

  %the actual packet got transmitted here to the next hop
  
  if reactive%upon receiving the packet, update routing table
    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 debug_route
  fprintf('\n');
end