Shortest Path Calculation and Fib Manipulation
diff --git a/Makefile b/Makefile
index abfca2b..1225fed 100644
--- a/Makefile
+++ b/Makefile
@@ -7,8 +7,8 @@
all: $(PROGRAMS)
-nlsr: nlsr.c nlsr_ndn.c nlsr_npl.c nlsr_adl.c nlsr_lsdb.c utility.c
- $(CC) $(CFLAGS) nlsr.c nlsr_ndn.c nlsr_npl.c nlsr_adl.c nlsr_lsdb.c utility.c -o nlsr $(LIBS)
+nlsr: nlsr.c nlsr_ndn.c nlsr_npl.c nlsr_adl.c nlsr_lsdb.c nlsr_route.c utility.c
+ $(CC) $(CFLAGS) nlsr.c nlsr_ndn.c nlsr_npl.c nlsr_adl.c nlsr_lsdb.c nlsr_route.c utility.c -o nlsr $(LIBS)
clean:
rm -f *.o
diff --git a/macbook.conf b/macbook.conf
index 7dc397b..3ddbd23 100644
--- a/macbook.conf
+++ b/macbook.conf
@@ -1,6 +1,5 @@
router-name /ndn/memphis.edu/netlab/macbook
ccnneighbor /ndn/memphis.edu/netlab/pollux face2 10
-ccnneighbor /ndn/memphis.edu/netlab/castor face3 8
ccnneighbor /ndn/memphis.edu/netlab/maia face4 15
ccnname /ndn/memphis.edu/netlab/macbook/name1
ccnname /ndn/memphis.edu/netlab/macbook/test
diff --git a/nlsr.c b/nlsr.c
index 9b7a703..108f7d1 100644
--- a/nlsr.c
+++ b/nlsr.c
@@ -69,7 +69,7 @@
{
signal(sig, SIG_IGN);
nlsr_destroy();
-// exit(0);
+ //exit(0);
}
void
@@ -336,13 +336,14 @@
{
printf("Freeing Allocated Memory....\n");
-
/* Destroying every hash table attached to each neighbor in ADL before destorying ADL */
hashtb_destroy(&nlsr->npl);
hashtb_destroy(&nlsr->adl);
hashtb_destroy(&nlsr->lsdb->name_lsdb);
hashtb_destroy(&nlsr->lsdb->adj_lsdb);
+ hashtb_destroy(&nlsr->pit_alsa);
+
ccn_schedule_destroy(&nlsr->sched);
ccn_destroy(&nlsr->ccn);
@@ -352,7 +353,6 @@
free(nlsr->router_name);
free(nlsr);
-
printf("Finished freeing allocated memory\n");
}
@@ -377,14 +377,15 @@
exit(1);
}
-
nlsr=(struct nlsr *)malloc(sizeof(struct nlsr));
struct hashtb_param param_adl = {0};
nlsr->adl=hashtb_create(sizeof(struct ndn_neighbor), ¶m_adl);
struct hashtb_param param_npl = {0};
nlsr->npl = hashtb_create(sizeof(struct name_prefix), ¶m_npl);
-
+ struct hashtb_param param_pit_alsa = {0};
+ nlsr->pit_alsa = hashtb_create(sizeof(struct pneding_interest), ¶m_pit_alsa);
+
nlsr->in_interest.p = &incoming_interest;
nlsr->in_content.p = &incoming_content;
@@ -401,6 +402,8 @@
nlsr->lsdb->adj_lsdb = hashtb_create(sizeof(struct alsa), ¶m_adj_lsdb);
struct hashtb_param param_name_lsdb = {0};
nlsr->lsdb->name_lsdb = hashtb_create(sizeof(struct nlsa), ¶m_name_lsdb);
+
+
nlsr->is_synch_init=1;
@@ -408,7 +411,8 @@
nlsr->adj_build_flag=0;
nlsr->adj_build_count=0;
nlsr->is_build_adj_lsa_sheduled=0;
- nlsr->is_send_lsdb_interest_scheduled=0;
+ nlsr->is_send_lsdb_interest_scheduled=0;
+ nlsr->is_route_calculation_scheduled=0;
nlsr->lsdb_synch_interval = LSDB_SYNCH_INTERVAL;
nlsr->interest_retry = INTEREST_RETRY;
@@ -482,17 +486,23 @@
nlsr->event_send_info_interest = ccn_schedule_event(nlsr->sched, 1, &send_info_interest, NULL, 0);
while(1)
- {
- if (nlsr->sched)
+ {
+ if( nlsr->sched != NULL )
+ {
ccn_schedule_run(nlsr->sched);
- if (nlsr->ccn)
- res = ccn_run(nlsr->ccn, 500);
+ }
+ if(nlsr->ccn != NULL)
+ {
+ res = ccn_run(nlsr->ccn, 500);
+ }
if (!(nlsr->sched && nlsr->ccn))
- break;
+ {
+ break;
+ }
+
}
- //nlsr_destroy();
return 0;
}
diff --git a/nlsr.h b/nlsr.h
index 27b4adc..41df3c5 100644
--- a/nlsr.h
+++ b/nlsr.h
@@ -19,6 +19,12 @@
char *lsdb_version;
};
+struct pneding_interest
+{
+ char *int_name;
+ int timed_out;
+};
+
struct nlsr
{
@@ -30,9 +36,12 @@
struct ccn_scheduled_event *event_send_info_interest;
struct ccn_scheduled_event *event_build_name_lsa;
struct ccn_scheduled_event *event_build_adj_lsa;
+ struct ccn_scheduled_event *event_calculate_route;
struct hashtb *adl;
struct hashtb *npl;
+ struct hashtb *pit_alsa;
+ struct hashtb *map;
struct linkStateDatabase *lsdb;
@@ -47,6 +56,7 @@
long int adj_build_count;
int is_build_adj_lsa_sheduled;
int is_send_lsdb_interest_scheduled;
+ int is_route_calculation_scheduled;
long int lsdb_synch_interval;
int interest_retry;
diff --git a/nlsr_fib.c b/nlsr_fib.c
new file mode 100644
index 0000000..e89e80d
--- /dev/null
+++ b/nlsr_fib.c
@@ -0,0 +1,224 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <netinet/in.h>
+#include <netdb.h>
+#include <sys/time.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <stdarg.h>
+#include <string.h>
+
+#include <ccn/ccn.h>
+#include <ccn/uri.h>
+#include <ccn/face_mgmt.h>
+#include <ccn/reg_mgmt.h>
+#include <ccn/charbuf.h>
+
+#include "nlsr_fib.h"
+
+
+static void
+ccn_fib_warn(int lineno, const char *format, ...)
+{
+ struct timeval t;
+ va_list ap;
+ va_start(ap, format);
+ gettimeofday(&t, NULL);
+ fprintf(stderr, "%d.%06d ccn_fib[%d]:%d: ", (int)t.tv_sec, (unsigned)t.tv_usec, (int)getpid(), lineno);
+ vfprintf(stderr, format, ap);
+ va_end(ap);
+}
+
+#define ON_ERROR_CLEANUP(resval) \
+{ \
+ if ((resval) < 0) { \
+ ccn_fib_warn (__LINE__, "OnError cleanup\n"); \
+ goto cleanup; \
+ } \
+}
+
+#define ON_NULL_CLEANUP(resval) \
+{ \
+ if ((resval) == NULL) { \
+ ccn_fib_warn(__LINE__, "OnNull cleanup\n"); \
+ goto cleanup; \
+ } \
+}
+
+
+
+static int
+register_unregister_prefix(struct ccn *h, struct ccn_charbuf *local_scope_template,
+ struct ccn_charbuf *no_name, struct ccn_charbuf *name_prefix,const unsigned char *ccndid, size_t ccnd_id_size, int faceid, int operation)
+{
+ struct ccn_charbuf *temp = NULL;
+ struct ccn_charbuf *resultbuf = NULL;
+ struct ccn_charbuf *signed_info = NULL;
+ struct ccn_charbuf *name = NULL;
+ struct ccn_charbuf *prefixreg = NULL;
+ struct ccn_parsed_ContentObject pcobuf = {0};
+ struct ccn_forwarding_entry forwarding_entry_storage = {0};
+ struct ccn_forwarding_entry *forwarding_entry = &forwarding_entry_storage;
+ struct ccn_forwarding_entry *new_forwarding_entry;
+ const unsigned char *ptr = NULL;
+ size_t length = 0;
+ int res;
+
+ /* Register or unregister the prefix */
+ forwarding_entry->action = (operation == OP_REG) ? "prefixreg" : "unreg";
+ forwarding_entry->name_prefix = name_prefix;
+ forwarding_entry->ccnd_id = ccndid;
+ forwarding_entry->ccnd_id_size =ccnd_id_size;
+ forwarding_entry->faceid = faceid;
+ forwarding_entry->flags = -1;
+ forwarding_entry->lifetime = (~0U) >> 1;
+
+ prefixreg = ccn_charbuf_create();
+ ccnb_append_forwarding_entry(prefixreg, forwarding_entry);
+ temp = ccn_charbuf_create();
+ res = ccn_sign_content(h, temp, no_name, NULL, prefixreg->buf, prefixreg->length);
+ resultbuf = ccn_charbuf_create();
+
+ /* construct Interest containing prefixreg request */
+ name = ccn_charbuf_create();
+ ccn_name_init(name);
+ ccn_name_append_str(name, "ccnx");
+ ccn_name_append(name, ccndid, ccnd_id_size);
+ ccn_name_append_str(name, (operation == OP_REG) ? "prefixreg" : "unreg");
+ ccn_name_append(name, temp->buf, temp->length);
+
+ /* send Interest, get Data */
+ res = ccn_get(h, name, local_scope_template, 1000, resultbuf, &pcobuf, NULL, 0);
+ ON_ERROR_CLEANUP(res);
+
+ res = ccn_content_get_value(resultbuf->buf, resultbuf->length, &pcobuf, &ptr, &length);
+ ON_ERROR_CLEANUP(res);
+
+ /* extract new forwarding entry from Data */
+ new_forwarding_entry = ccn_forwarding_entry_parse(ptr, length);
+ ON_NULL_CLEANUP(new_forwarding_entry);
+
+ res = new_forwarding_entry->faceid;
+
+ ccn_forwarding_entry_destroy(&new_forwarding_entry);
+ ccn_charbuf_destroy(&signed_info);
+ ccn_charbuf_destroy(&temp);
+ ccn_charbuf_destroy(&resultbuf);
+ ccn_charbuf_destroy(&name);
+ ccn_charbuf_destroy(&prefixreg);
+
+ return res;
+
+ cleanup:
+ ccn_forwarding_entry_destroy(&new_forwarding_entry);
+ ccn_charbuf_destroy(&signed_info);
+ ccn_charbuf_destroy(&temp);
+ ccn_charbuf_destroy(&resultbuf);
+ ccn_charbuf_destroy(&name);
+ ccn_charbuf_destroy(&prefixreg);
+
+ return -1;
+}
+
+
+static int
+get_ccndid(struct ccn *h, struct ccn_charbuf *local_scope_template,
+ unsigned char *ccndid)
+{
+ struct ccn_charbuf *name = NULL;
+ struct ccn_charbuf *resultbuf = NULL;
+ struct ccn_parsed_ContentObject pcobuf = {0};
+ char ccndid_uri[] = "ccnx:/%C1.M.S.localhost/%C1.M.SRV/ccnd/KEY";
+ const unsigned char *ccndid_result;
+ static size_t ccndid_result_size;
+ int res;
+
+ name = ccn_charbuf_create();
+ resultbuf = ccn_charbuf_create();
+
+ res = ccn_name_from_uri(name, ccndid_uri);
+ ON_ERROR_CLEANUP(res);
+
+ /* get Data */
+ res = ccn_get(h, name, local_scope_template, 4500, resultbuf, &pcobuf, NULL, 0);
+ ON_ERROR_CLEANUP(res);
+
+ /* extract from Data */
+ res = ccn_ref_tagged_BLOB(CCN_DTAG_PublisherPublicKeyDigest,
+ resultbuf->buf,
+ pcobuf.offset[CCN_PCO_B_PublisherPublicKeyDigest],
+ pcobuf.offset[CCN_PCO_E_PublisherPublicKeyDigest],
+ &ccndid_result, &ccndid_result_size);
+ ON_ERROR_CLEANUP(res);
+
+ memcpy((void *)ccndid, ccndid_result, ccndid_result_size);
+
+ ccn_charbuf_destroy(&name);
+ ccn_charbuf_destroy(&resultbuf);
+
+ return (ccndid_result_size);
+
+ cleanup:
+ ccn_charbuf_destroy(&name);
+ ccn_charbuf_destroy(&resultbuf);
+
+ return -1;
+}
+
+static void
+init_data(struct ccn_charbuf *local_scope_template,
+ struct ccn_charbuf *no_name)
+{
+ ccn_charbuf_append_tt(local_scope_template, CCN_DTAG_Interest, CCN_DTAG);
+ ccn_charbuf_append_tt(local_scope_template, CCN_DTAG_Name, CCN_DTAG);
+ ccn_charbuf_append_closer(local_scope_template); /* </Name> */
+ ccnb_tagged_putf(local_scope_template, CCN_DTAG_Scope, "1");
+ ccn_charbuf_append_closer(local_scope_template); /* </Interest> */
+
+ ccn_name_init(no_name);
+}
+
+int
+add_delete_ccn_face_by_face_id(struct ccn *h, const char *uri, int operation, int faceid)
+{
+ struct ccn_charbuf *prefix;
+ struct ccn_charbuf *local_scope_template = ccn_charbuf_create();
+ struct ccn_charbuf *no_name = ccn_charbuf_create();
+ unsigned char ccndid_storage[32] = {0};
+ unsigned char *ccndid = ccndid_storage;
+ size_t ccndid_size = 0;
+ int res;
+
+ prefix = ccn_charbuf_create();
+ res = ccn_name_from_uri(prefix, uri);
+ ON_ERROR_CLEANUP(res);
+
+
+ init_data(local_scope_template, no_name);
+
+ ccndid_size = get_ccndid(h, local_scope_template, ccndid);
+ if (ccndid_size != sizeof(ccndid_storage))
+ {
+ fprintf(stderr, "Incorrect size for ccnd id in response\n");
+ ON_ERROR_CLEANUP(-1);
+ }
+
+ res = register_unregister_prefix(h, local_scope_template, no_name, prefix,ccndid, ccndid_size,faceid, operation);
+
+ ON_ERROR_CLEANUP(res);
+
+ ccn_charbuf_destroy(&local_scope_template);
+ ccn_charbuf_destroy(&no_name);
+ ccn_charbuf_destroy(&prefix);
+
+ return 0;
+
+ cleanup:
+ ccn_charbuf_destroy(&prefix);
+ ccn_charbuf_destroy(&local_scope_template);
+ ccn_charbuf_destroy(&no_name);
+
+ return -1;
+}
+
+
diff --git a/nlsr_fib.h b/nlsr_fib.h
new file mode 100644
index 0000000..ce5e6d1
--- /dev/null
+++ b/nlsr_fib.h
@@ -0,0 +1,11 @@
+#ifndef _NLSR_FIB_H_
+#define _NLSR_FIB_H_
+
+#define CCN_FIB_LIFETIME ((~0U) >> 1)
+#define CCN_FIB_MCASTTTL (-1)
+#define OP_REG 0
+#define OP_UNREG 1
+
+int add_delete_ccn_face_by_face_id(struct ccn *h, const char *uri, int operation, int faceid);
+
+#endif
diff --git a/nlsr_lsdb.c b/nlsr_lsdb.c
index 29c7440..4df0840 100644
--- a/nlsr_lsdb.c
+++ b/nlsr_lsdb.c
@@ -23,6 +23,7 @@
#include "utility.h"
#include "nlsr_npl.h"
#include "nlsr_adl.h"
+#include "nlsr_route.h"
void
set_new_lsdb_version(void)
@@ -511,9 +512,13 @@
}
}
-
hashtb_end(e);
+ if ( !nlsr->is_route_calculation_scheduled )
+ {
+ nlsr->event_calculate_route = ccn_schedule_event(nlsr->sched, 1000000, &route_calculate, NULL, 0);
+ nlsr->is_route_calculation_scheduled=1;
+ }
free(key);
}
diff --git a/nlsr_ndn.c b/nlsr_ndn.c
index f05a90d..bd59459 100644
--- a/nlsr_ndn.c
+++ b/nlsr_ndn.c
@@ -390,7 +390,7 @@
//printf("Content Data to be sent: %s \n",raw_data);
- if( nlsr->adj_build_count == 0 || nlsr->is_build_adj_lsa_sheduled == 1 || strlen((char *)raw_data) == 0 )
+ if( nlsr->is_build_adj_lsa_sheduled == 1 || strlen((char *)raw_data) == 0 )
{
res= ccn_sign_content(nlsr->ccn, data, name, &sp, "WAIT" , strlen("WAIT"));
}
@@ -754,6 +754,11 @@
ccn_content_get_value(info->content_ccnb, info->pco->offset[CCN_PCO_E_Content]-info->pco->offset[CCN_PCO_B_Content], info->pco, &ptr, &length);
//printf("Content data Received: %s\n",ptr);
+
+
+
+
+
printf("LSA Data\n");
if( strlen((char *) ptr ) > 0 )
@@ -828,6 +833,14 @@
{
process_incoming_timed_out_interest_info(selfp,info);
}
+ if(ccn_name_comp_strcmp(info->interest_ccnb,info->interest_comps,nlsr_position+1,"lsdb") == 0)
+ {
+ process_incoming_timed_out_interest_lsdb(selfp,info);
+ }
+ if(ccn_name_comp_strcmp(info->interest_ccnb,info->interest_comps,nlsr_position+1,"lsa") == 0)
+ {
+ process_incoming_timed_out_interest_lsa(selfp,info);
+ }
}
void
@@ -867,6 +880,19 @@
}
+void
+process_incoming_timed_out_interest_lsdb(struct ccn_closure* selfp, struct ccn_upcall_info* info)
+{
+ printf("process_incoming_timed_out_interest_lsdb called \n");
+}
+
+void
+process_incoming_timed_out_interest_lsa(struct ccn_closure* selfp, struct ccn_upcall_info* info)
+{
+ printf("process_incoming_timed_out_interest_lsa called \n");
+
+}
+
int
send_info_interest(struct ccn_schedule *sched, void *clienth, struct ccn_scheduled_event *ev, int flags)
{
@@ -961,7 +987,9 @@
printf("send_lsdb_interest called \n");
if(flags == CCN_SCHEDULE_CANCEL)
- return -1;
+ {
+ return -1;
+ }
int i, adl_element;
struct ndn_neighbor *nbr;
@@ -1158,8 +1186,8 @@
memset(&lsa_str,0,5);
sprintf(lsa_str,"lsa");
- char *int_name=(char *)malloc(nbr->length + strlen(ls_type)+strlen(orig_router)+strlen(nlsr_str)+strlen(lsa_str)+3);
- memset(int_name,0,nbr->length +strlen(ls_type)+ strlen(orig_router)+strlen(nlsr_str)+strlen(lsa_str)+3);
+ char *int_name=(char *)malloc(nbr->length + strlen(ls_type)+strlen(orig_router)+strlen(nlsr_str)+strlen(lsa_str)+3+strlen(ls_type)+1);
+ memset(int_name,0,nbr->length +strlen(ls_type)+ strlen(orig_router)+strlen(nlsr_str)+strlen(lsa_str)+3+strlen(ls_type)+1);
memcpy(int_name+strlen(int_name),nbr->name,nbr->length);
memcpy(int_name+strlen(int_name),"/",1);
@@ -1169,16 +1197,15 @@
memcpy(int_name+strlen(int_name),"/",1);
memcpy(int_name+strlen(int_name),ls_type,strlen(ls_type));
memcpy(int_name+strlen(int_name),orig_router,strlen(orig_router));
-
+ memcpy(int_name+strlen(int_name),"/",1);
+ memcpy(int_name+strlen(int_name),ls_type,strlen(ls_type));
struct ccn_charbuf *name;
name=ccn_charbuf_create();
ccn_name_from_uri(name,int_name);
- ccn_name_append_str(name,ls_type);
-
/* adding InterestLifeTime and InterestScope filter */
struct ccn_charbuf *templ;
@@ -1196,16 +1223,16 @@
ccn_charbuf_append_closer(templ); /* </Interest> */
/* Adding InterestLifeTime and InterestScope filter done */
- printf("Sending ADJ LSA interest on name prefix : %s/%s/%s%s/%s/\n",nbr->name,nlsr_str,lsa_str,orig_router,ls_type);
+ printf("Sending ADJ LSA interest on name prefix : %s\n",int_name);
res=ccn_express_interest(nlsr->ccn,name,&(nlsr->in_content),templ);
if ( res >= 0 )
+ {
printf("ADJ LSA interest sending Successfull .... \n");
+ }
ccn_charbuf_destroy(&templ);
ccn_charbuf_destroy(&name);
free(int_name);
}
-
-
diff --git a/nlsr_ndn.h b/nlsr_ndn.h
index 4932fb6..1feab1e 100644
--- a/nlsr_ndn.h
+++ b/nlsr_ndn.h
@@ -23,6 +23,8 @@
void process_incoming_timed_out_interest(struct ccn_closure* selfp, struct ccn_upcall_info* info);
void process_incoming_timed_out_interest_info(struct ccn_closure* selfp, struct ccn_upcall_info* info);
+void process_incoming_timed_out_interest_lsdb(struct ccn_closure* selfp, struct ccn_upcall_info* info);
+void process_incoming_timed_out_interest_lsa(struct ccn_closure* selfp, struct ccn_upcall_info* info);
int send_info_interest(struct ccn_schedule *sched, void *clienth, struct ccn_scheduled_event *ev, int flags);
void send_info_interest_to_neighbor(struct name_prefix *nbr);
diff --git a/nlsr_route.c b/nlsr_route.c
new file mode 100644
index 0000000..8d47f3e
--- /dev/null
+++ b/nlsr_route.c
@@ -0,0 +1,456 @@
+#include<stdio.h>
+#include<string.h>
+#include<stdlib.h>
+#include <unistd.h>
+#include <getopt.h>
+#include <sys/time.h>
+#include <assert.h>
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+#include <sys/types.h>
+
+
+#include <ccn/ccn.h>
+#include <ccn/uri.h>
+#include <ccn/keystore.h>
+#include <ccn/signing.h>
+#include <ccn/schedule.h>
+#include <ccn/hashtb.h>
+
+
+#include "nlsr.h"
+#include "nlsr_route.h"
+#include "nlsr_lsdb.h"
+
+int
+route_calculate(struct ccn_schedule *sched, void *clienth, struct ccn_scheduled_event *ev, int flags)
+{
+ printf("route_calculate called\n");
+
+ if( ! nlsr->is_build_adj_lsa_sheduled )
+ {
+ /* Calculate Route here */
+
+ struct hashtb_param param_me = {0};
+ nlsr->map = hashtb_create(sizeof(struct map_entry), ¶m_me);
+ make_map();
+ assign_mapping_number();
+ print_map();
+
+ int i;
+ int **adj_matrix;
+ int map_element=hashtb_n(nlsr->map);
+ adj_matrix=malloc(map_element * sizeof(int *));
+ for(i = 0; i < map_element; i++)
+ {
+ adj_matrix[i] = malloc(map_element * sizeof(int));
+ }
+ make_adj_matrix(adj_matrix,map_element);
+ 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));
+
+ calculate_path(adj_matrix,parent, map_element, source);
+
+ print_all_path_from_source(parent,source);
+
+
+
+ for(i = 0; i < map_element; i++)
+ {
+ free(adj_matrix[i]);
+ }
+ free(parent);
+ free(adj_matrix);
+ hashtb_destroy(&nlsr->map);
+
+ }
+ nlsr->is_route_calculation_scheduled=0;
+
+ return 0;
+}
+
+void
+calculate_path(int **adj_matrix, long int *parent, long int V, long int S)
+{
+ int i;
+ long int v,u;
+ 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 */
+ for (i = 0 ; i < V; i++)
+ {
+ parent[i]=EMPTY_PARENT;
+ dist[i]=INF_DISTANCE;
+ Q[i]=i;
+ }
+
+ dist[S]=0;
+ sort_queue_by_distance(Q,dist,head,V);
+
+ while (head < V )
+ {
+ u=Q[head];
+ if(dist[u] == INF_DISTANCE)
+ {
+ break;
+ }
+
+ for(v=0 ; v <V; v++)
+ {
+ if( adj_matrix[u][v] > 0 ) //
+ {
+ if ( is_not_explored(Q,v,head+1,V) )
+ {
+
+ if( dist[u] + adj_matrix[u][v] < dist[v])
+ {
+ dist[v]=dist[u] + adj_matrix[u][v] ;
+ parent[v]=u;
+ }
+
+ }
+
+ }
+
+ }
+
+ head++;
+ sort_queue_by_distance(Q,dist,head,V);
+ }
+
+ free(Q);
+ free(dist);
+}
+
+void
+print_all_path_from_source(long int *parent,long int source)
+{
+ int i, map_element;
+ struct map_entry *me;
+
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+
+ hashtb_start(nlsr->map, e);
+ map_element=hashtb_n(nlsr->map);
+
+ for(i=0;i<map_element;i++)
+ {
+ me=e->data;
+ if(me->mapping != source)
+ {
+ print_path(parent,(long int)me->mapping);
+ printf("\n");
+ }
+ hashtb_next(e);
+ }
+
+ hashtb_end(e);
+
+}
+
+void
+print_path(long int *parent, long int dest)
+{
+ if (parent[dest] != EMPTY_PARENT )
+ print_path(parent,parent[dest]);
+
+ printf(" %ld",dest);
+}
+
+int
+is_not_explored(long int *Q, long int u,long int start, long int element)
+{
+ int ret=0;
+ long int i;
+ for(i=start; i< element; i++)
+ {
+ if ( Q[i] == u )
+ {
+ ret=1;
+ break;
+ }
+ }
+ return ret;
+}
+
+void
+sort_queue_by_distance(long int *Q,long int *dist,long int start,long int element)
+{
+ long int i,j;
+ long int temp_u;
+
+ for ( i=start ; i < element ; i ++)
+ {
+ for( j=i+1; j<element; j ++)
+ {
+ if (dist[Q[j]] < dist[Q[i]])
+ {
+ temp_u=Q[j];
+ Q[j]=Q[i];
+ Q[i]=temp_u;
+ }
+ }
+ }
+
+}
+
+void
+print_map(void)
+{
+ int i, map_element;
+ struct map_entry *me;
+
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+
+ hashtb_start(nlsr->map, e);
+ map_element=hashtb_n(nlsr->map);
+
+ for(i=0;i<map_element;i++)
+ {
+ me=e->data;
+ printf("Router: %s Mapping Number: %d \n",me->router,me->mapping);
+ hashtb_next(e);
+ }
+
+ hashtb_end(e);
+}
+
+
+void
+assign_mapping_number(void)
+{
+ int i, map_element;
+ struct map_entry *me;
+
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+
+ hashtb_start(nlsr->map, e);
+ map_element=hashtb_n(nlsr->map);
+
+ for(i=0;i<map_element;i++)
+ {
+ me=e->data;
+ me->mapping=i;
+ hashtb_next(e);
+ }
+
+ hashtb_end(e);
+}
+
+void
+make_map(void)
+{
+
+
+ int i, adj_lsdb_element;
+ struct alsa *adj_lsa;
+
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+
+ hashtb_start(nlsr->lsdb->adj_lsdb, e);
+ adj_lsdb_element=hashtb_n(nlsr->lsdb->adj_lsdb);
+
+ for(i=0;i<adj_lsdb_element;i++)
+ {
+ adj_lsa=e->data;
+ add_adj_data_to_map(adj_lsa->header->orig_router->name,adj_lsa->body,adj_lsa->no_link);
+ hashtb_next(e);
+ }
+
+ hashtb_end(e);
+
+}
+
+void
+add_map_entry(char *router)
+{
+
+ struct map_entry *me=(struct map_entry*)malloc(sizeof(struct map_entry ));
+
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+ int res;
+
+ hashtb_start(nlsr->map, e);
+ res = hashtb_seek(e, router, strlen(router), 0);
+
+ if(res == HT_NEW_ENTRY)
+ {
+ me=e->data;
+ me->router=(char *)malloc(strlen(router)+1);
+ memset(me->router,0,strlen(router)+1);
+ memcpy(me->router,router,strlen(router));
+ me->mapping=0;
+ }
+
+ hashtb_end(e);
+
+}
+
+
+void
+add_adj_data_to_map(char *orig_router, char *body, int no_link)
+{
+ add_map_entry(orig_router);
+
+ int i=0;
+ char *lsa_data=(char *)malloc(strlen(body)+1);
+ memset( lsa_data,0,strlen(body)+1);
+ memcpy(lsa_data,body,strlen(body)+1);
+ char *sep="|";
+ char *rem;
+ char *rtr_id;
+ char *length;
+ char *face;
+ char *metric;
+
+ if(no_link >0 )
+ {
+ rtr_id=strtok_r(lsa_data,sep,&rem);
+ length=strtok_r(NULL,sep,&rem);
+ face=strtok_r(NULL,sep,&rem);
+ metric=strtok_r(NULL,sep,&rem);
+
+ add_map_entry(rtr_id);
+
+ for(i=1;i<no_link;i++)
+ {
+ rtr_id=strtok_r(NULL,sep,&rem);
+ length=strtok_r(NULL,sep,&rem);
+ face=strtok_r(NULL,sep,&rem);
+ metric=strtok_r(NULL,sep,&rem);
+
+ add_map_entry(rtr_id);
+
+ }
+ }
+
+ free(lsa_data);
+}
+
+int
+get_mapping_no(char *router)
+{
+ struct map_entry *me;
+
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+ int res,ret;
+
+ hashtb_start(nlsr->map, e);
+ res = hashtb_seek(e, router, strlen(router), 0);
+
+ if( res == HT_OLD_ENTRY )
+ {
+ me=e->data;
+ ret=me->mapping;
+ }
+ else if(res == HT_NEW_ENTRY)
+ {
+ hashtb_delete(e);
+ }
+
+ hashtb_end(e);
+
+ return ret;
+
+}
+
+void
+assign_adj_matrix_for_lsa(struct alsa *adj_lsa, int **adj_matrix)
+{
+ int mapping_orig_router=get_mapping_no(adj_lsa->header->orig_router->name);
+ int mapping_nbr_router;
+
+ int i;
+ char *lsa_data=(char *)malloc(strlen(adj_lsa->body)+1);
+ memset( lsa_data,0,strlen(adj_lsa->body)+1);
+ memcpy(lsa_data,adj_lsa->body,strlen(adj_lsa->body)+1);
+ char *sep="|";
+ char *rem;
+ char *rtr_id;
+ char *length;
+ char *face;
+ char *metric;
+
+ if(adj_lsa->no_link >0 )
+ {
+ rtr_id=strtok_r(lsa_data,sep,&rem);
+ length=strtok_r(NULL,sep,&rem);
+ face=strtok_r(NULL,sep,&rem);
+ metric=strtok_r(NULL,sep,&rem);
+
+ mapping_nbr_router=get_mapping_no(rtr_id);
+ adj_matrix[mapping_orig_router][mapping_nbr_router]=atoi(metric);
+
+ for(i=1;i<adj_lsa->no_link;i++)
+ {
+ rtr_id=strtok_r(NULL,sep,&rem);
+ length=strtok_r(NULL,sep,&rem);
+ face=strtok_r(NULL,sep,&rem);
+ metric=strtok_r(NULL,sep,&rem);
+
+ mapping_nbr_router=get_mapping_no(rtr_id);
+ adj_matrix[mapping_orig_router][mapping_nbr_router]=atoi(metric);
+
+ }
+ }
+
+ free(lsa_data);
+}
+
+void
+make_adj_matrix(int **adj_matrix,int map_element)
+{
+
+ init_adj_matrix(adj_matrix,map_element);
+
+ int i, adj_lsdb_element;
+ struct alsa *adj_lsa;
+
+ struct hashtb_enumerator ee;
+ struct hashtb_enumerator *e = ⅇ
+
+ hashtb_start(nlsr->lsdb->adj_lsdb, e);
+ adj_lsdb_element=hashtb_n(nlsr->lsdb->adj_lsdb);
+
+ for(i=0;i<adj_lsdb_element;i++)
+ {
+ adj_lsa=e->data;
+ assign_adj_matrix_for_lsa(adj_lsa,adj_matrix);
+ hashtb_next(e);
+ }
+
+ hashtb_end(e);
+
+}
+
+void
+init_adj_matrix(int **adj_matrix,int map_element)
+{
+ int i, j;
+ for(i=0;i<map_element;i++)
+ for(j=0;j<map_element;j++)
+ adj_matrix[i][j]=0;
+}
+
+void print_adj_matrix(int **adj_matrix, int map_element)
+{
+ int i, j;
+ for(i=0;i<map_element;i++)
+ {
+ for(j=0;j<map_element;j++)
+ printf("%d ",adj_matrix[i][j]);
+ printf("\n");
+ }
+}
+
+
diff --git a/nlsr_route.h b/nlsr_route.h
new file mode 100644
index 0000000..0e7884b
--- /dev/null
+++ b/nlsr_route.h
@@ -0,0 +1,29 @@
+#ifndef _NLSR_ROUTE_H_
+#define _NLSR_ROUTE_H_
+
+#define EMPTY_PARENT -12345
+#define INF_DISTANCE 2147483647
+
+struct map_entry
+{
+ char *router;
+ int mapping;
+};
+
+int route_calculate(struct ccn_schedule *sched, void *clienth, struct ccn_scheduled_event *ev, int flags);
+void make_map(void);
+void add_map_entry(char *router);
+void add_adj_data_to_map(char *orig_router, char *body, int no_link);
+void print_map(void);
+void assign_mapping_number(void);
+void make_adj_matrix(int **adj_matrix,int map_element);
+void init_adj_matrix(int **adj_matrix,int map_element);
+void print_adj_matrix(int **adj_matrix, int map_element);
+int get_mapping_no(char *router);
+void calculate_path(int **adj_matrix, long int *parent, long int V, long int S);
+void sort_queue_by_distance(long int *Q,long int *dist,long int start,long int element);
+int is_not_explored(long int *Q, long int u,long int start, long int element);
+void print_path(long int *parent, long int dest);
+void print_all_path_from_source(long int *parent,long int source);
+
+#endif