compactrouting.m

best routing protocol

function  [routing_dist, routing_load, storage_load, dht_packets, cluster, dv_packets, dv_entries] = ...
    compactrouting(neighbor_dist,pre_landmarks, ...
		   test_pairs, failure_nodes, reactive,coord, study_dht)
%Refer to "Compact routing schemes" by Thorup & Zwick for the
%algorithm 
%neighbor_dist: distances are arbitrary ones, not necessarily
%hops. inf indicates non-connectivity.
% 
% pre_landmarks: pre-set landmark sets. 
% if not given, used the proposed randomized algorithm in the paper
% if length(pre_landmarks)==1, it's used as the number of landmarks
% note that in study_cr(), landmarks are always pre-specified.

% test_pairs: the src-dest pairs selected for routing performance evaluation
% failure_nodes: the nodes that may fail in routing test, but not
% in routing table establishment stage.

% reactive: 0: local flooding; 1: reactive; 2: Distance Vector

% coord: the physical coordinate for debug visualization only
% return values:
% routing_dist(): the routing distance for each test pair. Inf
% means unrechable
% routing_load: the load on every node
% storage_load: the storage load on every beacon
% dht_packet: how many packets does it take to setup the DHT
% cluster: the info about the cluster (routing table) size

debug = 1;
debug_route = 0; %this will generate a lot of debug information
if ~issparse(neighbor_dist)
  neighbor_dist = dist_full2sparse(neighbor_dist);
end
if nargin<5
  reactive = 0; %default CR is proactive, i.e. reactive = 0;
end
if nargin<7
  study_dht = 0;
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

if nargin<4
  failure_nodes = [];
end
tmp = failure_nodes;
failure_nodes = zeros(n,1);
failure_nodes(tmp) = ones(length(tmp),1);

fprintf(['*CR: running mode:%d (0:scoped flooding; 1:' ...
	 ' reactive; 2: scoped DV)\n'], reactive);

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));
%s = sqrt(n);%!!!!
while length(W)>0
  if length(pre_landmarks)>=1%!!!!
    A = pre_landmarks;
  elseif length(pre_landmarks)==1
    % pre_landmarks is defined as the # of random landmarks
    tmp = randperm(n);
    A = tmp(1:pre_landmarks);
  else
    A = union(A, sample(W,s));
  end
  A = sort(A);
  ordinary_nodes = setdiff(1:n, A);
  isbeacon = zeros(n,1);
  isbeacon(A) = 1:length(A);
  %every landmark floods the network
  lm_broadcast_snd = length(A)*n;
  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 get treeLabel of each node
  fprintf('CR: calculating tree labels...\n');
  tlabel = cell(n,1);
  for i=ordinary_nodes
    bcn = cent(i);
    if bcn<=0
      error('check here');
    end
    
    if deltaA(i)==Inf
      tlabel{i}(1) = -1;
    else
      curr = i;
      for count = deltaA(i)-1:-1:1
        curr = nexthop2bcn(curr, bcn);
        tlabel{i}(count) = curr;
      end
    end
  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);
  if reactive==1
    fprintf('reactive mode=1, do NOT do local broadcasting\n')
  elseif reactive==0
    fprintf('simulating local broadcasting...\n');
    % every ordinary node i floods the network in the radix of deltaA(i) to let others find itself in their clusters
    od_broadcast_snd = 0;
    od_broadcast_rcv = 0;
    
    count = 0; total_c = length(ordinary_nodes); old_c = 0;
    start_t = clock;old_t = clock;
    
    for i=ordinary_nodes
      new_t = clock;
      if etime(new_t, old_t)>10
	fprintf('progress %.1f%%. ETA %.1f secs\n', count*100/total_c, ...
		etime(new_t,old_t)/(count-old_c)*(total_c-count));
	old_t = new_t;
	old_c = count;
      end
      
      [b_snd, b_rcv, rt_i,label(i),rt_dist ] = BFS(i,deltaA(i), neighbor_dist, ...
					   1, A(cent(i)) );
      routing_table(:,i) = rt_i';
      tmp = find(neighbor_dist(:,i));
      routing_table(tmp,i)=repmat(i,length(tmp),1);
      direct_dist(:,i) = rt_dist';
      direct_dist(tmp,i) = neighbor_dist(tmp,i);
      routing_table(n,n) = 0;
      od_broadcast_snd = od_broadcast_snd + b_snd;
      od_broadcast_rcv = od_broadcast_rcv + b_rcv;
      count = count+1;
    end
  
    if debug
      fprintf('# broadcast packets sent due to local clustering: %d\n', od_broadcast_snd);
      fprintf('# broadcast packets received due to local clustering: %d\n', od_broadcast_rcv);
    end
  elseif reactive==2
    %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);
    dd = full(direct_dist);
    for i=1:n
      dests = find(dv{i}(:,1)>0);
      dd(i,dests) = dv{i}(dests,2)';
    end
    direct_dist = sparse(dd);
    clear dd;
    clear dv;
  end
      
  %%%%
  if length(pre_landmarks)>0
    W = [];
  else
    W = find( sum(C,2) > 4*n/s);
  end
  
end
if debug
  fprintf('%d selected landmarks.\n',length(A));
  if n<100
    A
  end
end
%% end of selecting landmarks.
%% other useful variables: cent(dest), C(src,dest)


%%%%use DHT to store node coordinates, see the overhead
%storage overhead per beacon, + packets sent
fprintf('CR: putting vectors to beacons as a DHT\n');
beacons = A;
ordinary_nodes = setdiff(1:n, beacons);
storage_load = zeros(length(beacons),1);
dht_packets = 0;

if study_dht
  stats = struct('fail_total', 0, ...
		 'fail_due2ttl', 0, ...
		 'fail_due2prev',0, ...
		 'fail_before_beacon',0, ... %failed before reach the closest beacon
		 'fail_after_beacon', 0);
  for i=ordinary_nodes
    b_k = consistent_hash(i,beacons, n); %b_k \in 1.. length(beacons)
    storage_load(b_k) = storage_load(b_k)+1;
    tmp_dist = 0;
    [f_path, f_dist, routing_table, direct_dist, tmp_load, stats] = cr_routing(i, ...
						  A(b_k), cent, A, debug_route, beacon_vectors, neighbor_dist, ...
						  routing_table, nexthop2bcn, isbeacon, [],reactive, ...
						  deltaA, direct_dist, ...
						  zeros(n,1), ...
						  zeros(n,1), stats);
  
    [b_path, b_dist, routing_table, direct_dist, tmp_load, stats] = cr_routing(A(b_k), ...
						  i, cent, A, debug_route, beacon_vectors, neighbor_dist, ...
						  routing_table, nexthop2bcn, isbeacon, tlabel{i},reactive, ...
						  deltaA, direct_dist, ...
						  zeros(n,1), ...
						  zeros(n,1), stats);
    dht_packets = dht_packets + f_dist + b_dist;
  end
  if length(beacons)<10
    storage_load
  end
end
fprintf('CR: dht_packets:%d; mean storage load:%.2f, max:%.2f\n', ...
	 dht_packets, mean(storage_load), max(storage_load));
%%%%


%% routing algorithm
if 0 %old.
  routing_nexthop = optimal_nexthop(:, A(cent)); %route to the
						 %nearest landmarks
						 routing_nexthop(:, A) = optimal_nexthop(:, A); % routes to
												% landmarks are optimal
  for src = 1:n
    routing_nexthop(src, src) = src; %route to itself
    dest = src;
    routing_nexthop(A(cent(dest)),dest) = optimal_nexthop(A(cent(dest)),dest);
  end
  optimal_mask = C | (neighbor_dist>0); %routing within the cluster
                                        %and routing within
                                        %neighborhood is optimal
  routing_nexthop = optimal_nexthop.*optimal_mask + ...
      routing_nexthop.*(1-optimal_mask); % if C(src,dest)==1, next hop is the optimal one
end
routing_load = zeros(n,1);
routing_dist = zeros(length(test_pairs), 1);

%routing_table
stats = struct('fail_total', 0, ...
	       'fail_due2ttl', 0, ...
	       'fail_due2prev',0, ...
	       'fail_before_beacon',0, ... %failed before reach the closest beacon
	       'fail_after_beacon', 0);
for count = 1:length(test_pairs)
  src = test_pairs(count,1);
  dest = test_pairs(count,2); 
  [routing_path, routing_dist(count), routing_table, direct_dist, routing_load, stats] = cr_routing(src, ...
	dest, cent, A, debug_route, beacon_vectors, neighbor_dist, ...
        routing_table, nexthop2bcn, isbeacon, tlabel{dest},reactive, ...
						  deltaA,direct_dist, ...
						  failure_nodes, ...
						  routing_load, stats);
  %routing_load(routing_path)=  routing_load(routing_path)+1;
  if 0 & routing_dist(count)==Inf & length(routing_path)>1 %for  %debugging only
    plot_route(coord, routing_path,'b');
    plot_route(coord, [src A(cent(dest)) dest],'r');
    error('stop here')
  end
end

% check out the overhead
cluster = full(sum(routing_table>0,2));
if debug
  fprintf('mean and max cluster size:%.1f, %.1f\n', mean(cluster), ...
	  max(cluster));
  %[tmp idx] = max(cluster);
  %deltaA(idx)
  %beacon_vectors(idx,:)
  if n<100
    fprintf('cluster size for each node:');
    cluster'
    fprintf('total cluster size:%d\n',sum(cluster));
  end
  stats
end


function [routing_path, routing_dist, routing_table, direct_dist, routing_load, ...
	 stats ] =cr_routing(src, ...
	dest, cent, A, debug_route, beacon_vectors, neighbor_dist, ...
	  routing_table, nexthop2bcn, isbeacon, label, reactive, ...
	  deltaA, direct_dist, failure_nodes, routing_load, stats)
MAX_ROUTE_HOPS = 1000;
routing_path = [src];
routing_dist = 0;
hops =1;
failed_hops = 0; %# of hops that need failure handling
max_consecutive_fail = 0;
found_loop = 0;
if src==dest
  routing_dist = 0;
  return
end
if nargin<17
  stats = struct('fail_total', ...
		 'fail_due2ttl', 0, ...
		 'fail_due2prev',0, ...
		 'fail_before_beacon',0, ... %failed before reach the closest beacon
		 'fail_after_beacon', 0);
end
n = length(neighbor_dist);
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');
  stats.fail_total = stats.fail_total;
  return
end
if failure_nodes(src) | failure_nodes(dest)
  routing_dist = Inf;
  routing_path = [];
  if debug_route
    fprintf('\n');
  end
  fprintf('source or dest failure\n');
  return
end