Hyperbolic Routing Complete
diff --git a/nlsr-sync-0.0/nlsr_lsdb.c b/nlsr-sync-0.0/nlsr_lsdb.c
index 68a6451..e36a922 100755
--- a/nlsr-sync-0.0/nlsr_lsdb.c
+++ b/nlsr-sync-0.0/nlsr_lsdb.c
@@ -2415,7 +2415,7 @@
char *key=(char *)malloc(cor_lsa->header->orig_router->length+2+2);
- memset(key,0,cor_lsa->header->orig_router->length+2);
+ memset(key,0,cor_lsa->header->orig_router->length+2+2);
make_cor_lsa_key(key,cor_lsa);
struct ccn_charbuf *lsa_data=ccn_charbuf_create();
@@ -2443,3 +2443,77 @@
ccn_charbuf_destroy(&lsa_data);
}
+void
+make_cor_lsa_key_by_router_name(char *key,char *router_name)
+{
+ memcpy(key+strlen(key),router_name,strlen(router_name));
+ memcpy(key+strlen(key),"/",1);
+ char ls_type[2];
+ sprintf(ls_type,"%d",LS_TYPE_COR);
+ memcpy(key+strlen(key),ls_type,strlen(ls_type));
+ key[strlen(key)]='\0';
+}
+
+
+double
+get_hyperbolic_r(char *router)
+{
+ double ret=-1.0;
+ char *cor_lsa_key=(char *)calloc(strlen(router)+4,sizeof(char));
+ make_cor_lsa_key_by_router_name(cor_lsa_key,router);
+
+
+ struct clsa *cor_lsa;
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+ int res;
+
+ hashtb_start(nlsr->lsdb->cor_lsdb, e);
+ res = hashtb_seek(e, cor_lsa_key, strlen(cor_lsa_key), 0);
+
+ if ( res == HT_OLD_ENTRY)
+ {
+ cor_lsa=e->data;
+ ret=cor_lsa->cor_r;
+ }
+ else if(res == HT_NEW_ENTRY)
+ {
+ hashtb_delete(e);
+ }
+
+ hashtb_end(e);
+
+ free(cor_lsa_key);
+ return ret;
+}
+
+double
+get_hyperbolic_theta(char *router)
+{
+ double ret=-1.0;
+ char *cor_lsa_key=(char *)calloc(strlen(router)+4,sizeof(char));
+ make_cor_lsa_key_by_router_name(cor_lsa_key,router);
+
+ struct clsa *cor_lsa;
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+ int res;
+
+ hashtb_start(nlsr->lsdb->cor_lsdb, e);
+ res = hashtb_seek(e, cor_lsa_key, strlen(cor_lsa_key), 0);
+
+ if ( res == HT_OLD_ENTRY)
+ {
+ cor_lsa=e->data;
+ ret=cor_lsa->cor_theta;
+ }
+ else if(res == HT_NEW_ENTRY)
+ {
+ hashtb_delete(e);
+ }
+
+ hashtb_end(e);
+
+ free(cor_lsa_key);
+ return ret;
+}
diff --git a/nlsr-sync-0.0/nlsr_lsdb.h b/nlsr-sync-0.0/nlsr_lsdb.h
index 420e178..c67348e 100755
--- a/nlsr-sync-0.0/nlsr_lsdb.h
+++ b/nlsr-sync-0.0/nlsr_lsdb.h
@@ -99,5 +99,7 @@
void write_cor_lsa_to_repo(struct clsa *cor_lsa);
void build_and_install_others_cor_lsa(char *orig_router,int ls_type,char *orig_time, double cor_r, double cor_theta);
+double get_hyperbolic_r(char *router);
+double get_hyperbolic_theta(char *router);
#endif
diff --git a/nlsr-sync-0.0/nlsr_npt.c b/nlsr-sync-0.0/nlsr_npt.c
index c661930..64373fe 100755
--- a/nlsr-sync-0.0/nlsr_npt.c
+++ b/nlsr-sync-0.0/nlsr_npt.c
@@ -478,7 +478,7 @@
{
fle=ef->data;
if ( nlsr->debugging )
- printf(" Face: %d Route_Cost: %d \n",fle->next_hop_face,fle->route_cost);
+ printf(" Face: %d Route_Cost: %f \n",fle->next_hop_face,fle->route_cost);
if ( nlsr->detailed_logging )
writeLogg(__FILE__,__FUNCTION__,__LINE__," Face: %d Route_Cost: %d \n",fle->next_hop_face,fle->route_cost);
hashtb_next(ef);
diff --git a/nlsr-sync-0.0/nlsr_route.c b/nlsr-sync-0.0/nlsr_route.c
index 36a9957..08a574e 100755
--- a/nlsr-sync-0.0/nlsr_route.c
+++ b/nlsr-sync-0.0/nlsr_route.c
@@ -1,6 +1,7 @@
-#include<stdio.h>
-#include<string.h>
-#include<stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+#include <stdlib.h>
#include <unistd.h>
#include <getopt.h>
#include <sys/time.h>
@@ -75,38 +76,104 @@
print_adj_matrix(adj_matrix,map_element);
long int source=get_mapping_no(nlsr->router_name);
- long int *parent=(long int *)malloc(map_element * sizeof(long int));
- long int *dist=(long int *)malloc(map_element * sizeof(long int));
-
int num_link=get_no_link_from_adj_matrix(adj_matrix, map_element ,source);
-
- if ( (num_link == 0) || (nlsr->multi_path_face_num == 1 ) )
- {
- calculate_path(adj_matrix,parent,dist, map_element, source);
- print_all_path_from_source(parent,source);
- print_all_next_hop(parent,source);
- update_routing_table_with_new_route(parent, dist,source);
- //print_routing_table();
- }
- else if ( (num_link != 0) && (nlsr->multi_path_face_num > 1 ) )
+
+ if ( nlsr->is_hyperbolic_calc == 1)
{
long int *links=(long int *)malloc(num_link*sizeof(long int));
long int *link_costs=(long int *)malloc(num_link*sizeof(long int));
get_links_from_adj_matrix(adj_matrix, map_element , links, link_costs, source);
- for ( i=0 ; i < num_link; i++)
+
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+ for (hashtb_start(nlsr->rev_map, e); e->key != NULL; hashtb_next(e))
{
- adjust_adj_matrix(adj_matrix, map_element,source,links[i],link_costs[i]);
+ struct map_entry *me=e->data;
+ if ( me->mapping != source )
+ {
+ long int *faces=(long int *)calloc(num_link,sizeof(long int));
+ double *nbr_dist=(double *)calloc(num_link,sizeof(double));
+ double *nbr_to_dest=(double *)calloc(num_link,sizeof(double));
+ for ( i=0 ; i < num_link; i++)
+ {
+ int face=get_next_hop_face_from_adl(get_router_from_rev_map(links[i]));
+ double dist_to_nbr=get_hyperbolic_distance(source,links[i]);
+ double dist_to_dest_from_nbr=get_hyperbolic_distance(links[i],me->mapping);
+ faces[i]=face;
+ nbr_dist[i]=dist_to_nbr;
+ nbr_to_dest[i]= dist_to_dest_from_nbr;
+
+
+ }
+ sort_hyperbolic_route(nbr_to_dest,nbr_dist, faces,0,num_link);
+ if (nlsr->multi_path_face_num <= 1 )
+ {
+ update_routing_table_with_new_hyperbolic_route(me->mapping,faces[0],nbr_to_dest[0]);
+ }
+ else
+ {
+ if ( num_link <= nlsr->multi_path_face_num )
+ {
+ for ( i=0 ; i < num_link; i++)
+ {
+ update_routing_table_with_new_hyperbolic_route(me->mapping,faces[i],nbr_to_dest[i]);
+ }
+ }
+ else if (num_link > nlsr->multi_path_face_num)
+ {
+ for ( i=0 ; i < nlsr->multi_path_face_num; i++)
+ {
+ update_routing_table_with_new_hyperbolic_route(me->mapping,faces[i],nbr_to_dest[i]);
+ }
+ }
+
+ }
+ free(faces);
+ free(nbr_dist);
+ free(nbr_to_dest);
+ }
+ }
+ hashtb_end(e);
+
+
+ free(links);
+ free(link_costs);
+ }
+ else if (nlsr->is_hyperbolic_calc == 0 )
+ {
+
+ long int *parent=(long int *)malloc(map_element * sizeof(long int));
+ long int *dist=(long int *)malloc(map_element * sizeof(long int));
+
+
+ if ( (num_link == 0) || (nlsr->multi_path_face_num == 1 ) )
+ {
calculate_path(adj_matrix,parent,dist, map_element, source);
print_all_path_from_source(parent,source);
print_all_next_hop(parent,source);
update_routing_table_with_new_route(parent, dist,source);
- //print_routing_table();
}
+ else if ( (num_link != 0) && (nlsr->multi_path_face_num > 1 ) )
+ {
+ long int *links=(long int *)malloc(num_link*sizeof(long int));
+ long int *link_costs=(long int *)malloc(num_link*sizeof(long int));
+ get_links_from_adj_matrix(adj_matrix, map_element , links, link_costs, source);
+ for ( i=0 ; i < num_link; i++)
+ {
+ adjust_adj_matrix(adj_matrix, map_element,source,links[i],link_costs[i]);
+ calculate_path(adj_matrix,parent,dist, map_element, source);
+ print_all_path_from_source(parent,source);
+ print_all_next_hop(parent,source);
+ update_routing_table_with_new_route(parent, dist,source);
+ }
- free(links);
- free(link_costs);
+ free(links);
+ free(link_costs);
+ }
+ free(parent);
+ free(dist);
}
-
+
print_routing_table();
print_npt();
@@ -120,8 +187,7 @@
{
free(adj_matrix[i]);
}
- free(parent);
- free(dist);
+
free(adj_matrix);
hashtb_destroy(&nlsr->map);
hashtb_destroy(&nlsr->rev_map);
@@ -142,7 +208,7 @@
//long int *dist=(long int *)malloc(V * sizeof(long int));
long int *Q=(long int *)malloc(V * sizeof(long int));
long int head=0;
- /* Initial the Parent */
+ /* Initiate the Parent */
for (i = 0 ; i < V; i++)
{
parent[i]=EMPTY_PARENT;
@@ -324,6 +390,50 @@
}
+void
+sort_hyperbolic_route(double *dist_dest,double *dist_nbr, long int *faces,long int start,long int element)
+{
+ long int i,j;
+ double temp_dist;
+ long int temp_face;
+
+ for ( i=start ; i < element ; i ++)
+ {
+ for( j=i+1; j<element; j ++)
+ {
+ if (dist_dest[i] < dist_dest[j])
+ {
+ temp_dist=dist_dest[j];
+ dist_dest[j]=dist_dest[i];
+ dist_dest[i]=temp_dist;
+
+ temp_dist=dist_nbr[j];
+ dist_nbr[j]=dist_nbr[i];
+ dist_nbr[i]=temp_dist;
+
+ temp_face=faces[j];
+ faces[j]=faces[i];
+ faces[i]=temp_face;
+ }
+ if ( (dist_dest[i] == dist_dest[j]) && (dist_nbr[i] < dist_nbr[j]) )
+ {
+ temp_dist=dist_dest[j];
+ dist_dest[j]=dist_dest[i];
+ dist_dest[i]=temp_dist;
+
+ temp_dist=dist_nbr[j];
+ dist_nbr[j]=dist_nbr[i];
+ dist_nbr[i]=temp_dist;
+
+ temp_face=faces[j];
+ faces[j]=faces[i];
+ faces[i]=temp_face;
+ }
+ }
+ }
+
+}
+
void
print_map(void)
{
@@ -983,7 +1093,7 @@
{
fle=ef->data;
if ( nlsr->debugging )
- printf(" Face: %d Route_Cost: %d \n",fle->next_hop_face,fle->route_cost);
+ printf(" Face: %d Route_Cost: %f \n",fle->next_hop_face,fle->route_cost);
if ( nlsr->detailed_logging )
writeLogg(__FILE__,__FUNCTION__,__LINE__," Face: %d Route_Cost: %d \n",fle->next_hop_face,fle->route_cost);
hashtb_next(ef);
@@ -1114,6 +1224,28 @@
hashtb_end(e);
}
+void
+update_routing_table_with_new_hyperbolic_route(long int dest_router_rev_map_index, long int face, double nbr_to_dest_dist)
+{
+ if ( nlsr->debugging )
+ printf("update_routing_table_with_new_hyperbolic_route called\n");
+ if ( nlsr->detailed_logging )
+ writeLogg(__FILE__,__FUNCTION__,__LINE__,"update_routing_table_with_new_hyperbolic_route called\n");
+
+ char *orig_router=get_router_from_rev_map(dest_router_rev_map_index);
+
+ if (face != NO_NEXT_HOP && face != NO_FACE )
+ {
+ update_routing_table(orig_router,face,nbr_to_dest_dist);
+ if ( nlsr->debugging )
+ printf ("Orig_router: %s Next Hop Face: %ld \n",orig_router,face);
+ if ( nlsr->detailed_logging )
+ writeLogg(__FILE__,__FUNCTION__,__LINE__,"Orig_router: %s Next Hop Face: %ld \n",orig_router,face);
+
+ }
+
+
+}
void
@@ -1178,8 +1310,6 @@
printf("Dest Router: %s and Face id: %d \n",dest_router, face_id);
}
- //print_routing_table();
-
int ret=0;
int res;
@@ -1194,22 +1324,6 @@
if( res == HT_OLD_ENTRY )
{
rte=e->data;
- /*
- struct hashtb_enumerator eef;
- struct hashtb_enumerator *ef = &eef;
-
- hashtb_start(rte->face_list, ef);
- res1 = hashtb_seek(ef, &face_id, sizeof(face_id), 0);
- if( res1 == HT_OLD_ENTRY)
- {
- ret=1;
- }
- else
- {
- hashtb_delete(ef);
- }
- hashtb_end(ef);
- */
unsigned *v;
v = hashtb_lookup(rte->face_list, &face_id, sizeof(face_id));
if (v != NULL)
@@ -1222,7 +1336,29 @@
hashtb_end(e);
- //print_routing_table();
-
return ret;
}
+
+double
+get_hyperbolic_distance(long int source, long int dest)
+{
+ double distance;
+ char *src_router=get_router_from_rev_map(source);
+ char *dest_router=get_router_from_rev_map(dest);
+
+ double src_r=get_hyperbolic_r(src_router);
+ double src_theta=get_hyperbolic_r(src_router);
+
+ double dest_r=get_hyperbolic_r(dest_router);
+ double dest_theta=get_hyperbolic_r(dest_router);
+ if ( src_r != -1 && dest_r != -1 )
+ {
+ distance=acosh(cosh(src_r)*cosh(dest_r)-sinh(src_r)*sinh(dest_r)*cos(src_theta-dest_theta));
+ }
+ else
+ {
+ distance= -1.0;
+ }
+
+ return distance;
+}
diff --git a/nlsr-sync-0.0/nlsr_route.h b/nlsr-sync-0.0/nlsr_route.h
index b0eef14..b6dff03 100755
--- a/nlsr-sync-0.0/nlsr_route.h
+++ b/nlsr-sync-0.0/nlsr_route.h
@@ -24,7 +24,7 @@
struct face_list_entry
{
int next_hop_face;
- int route_cost;
+ double route_cost;
};
int route_calculate(struct ccn_schedule *sched, void *clienth, struct ccn_scheduled_event *ev, int flags);
@@ -64,4 +64,8 @@
void print_all_next_hop(long int *parent,long int source);
int does_face_exist_for_router(char *dest_router, int face_id);
+double get_hyperbolic_distance(long int source, long int dest);
+void sort_hyperbolic_route(double *dist_dest,double *dist_nbr, long int *faces,long int start,long int element);
+void update_routing_table_with_new_hyperbolic_route(long int dest_router_rev_map_index, long int face, double nbr_to_dest_dist);
+
#endif