diff -urN ./aodv-uu-0.6/Makefile ./maodv-umd/Makefile --- ./aodv-uu-0.6/Makefile Thu Oct 31 22:05:20 2002 +++ ./maodv-umd/Makefile Fri Feb 21 18:03:58 2003 @@ -3,7 +3,10 @@ SRC = main.c debug.c timer_queue.c aodv_socket.c aodv_hello.c \ aodv_neighbor.c aodv_timeout.c routing_table.c seek_list.c \ k_route.c aodv_rreq.c aodv_rrep.c aodv_rerr.c packet_input.c \ - packet_queue.c libipq.c icmp.c + packet_queue.c libipq.c icmp.c maodv_grph.c maodv_mact.c \ + multicast_routing_table.c igmp.c \ + maodv_rreq.c maodv_rrep.c k_mroute.c multicast_packet_cache.c \ + maodv_neighbor.c SRC_NS = debug.c timer_queue.c aodv_socket.c aodv_hello.c \ aodv_neighbor.c aodv_timeout.c routing_table.c seek_list.c \ @@ -32,7 +35,8 @@ # Comment out to disable debug operation... DEBUG=-g -DDEBUG -DEFS=#-DUSE_IW_SPY +DEFS= -DMAODV #-DUSE_IW_SPY + CFLAGS=$(OPTS) $(DEBUG) $(DEFS) ifneq (,$(findstring USE_IW_SPY,$(DEFS))) @@ -67,7 +71,8 @@ KCFLAGS=-Wall -O2 $(KDEFS) $(KINC) KCFLAGS_ARM =-Wall -O2 -D__KERNEL__ -DMODULE $(KINC) -.PHONY: default clean install uninstall depend tags aodvd-arm docs +# .PHONY used to have a docs target in it, I removed it, we got no docs... +.PHONY: default clean install uninstall depend tags aodvd-arm default: aodvd kaodv.o @@ -96,7 +101,7 @@ aodvd: $(OBJS) Makefile $(CC) $(CFLAGS) -o $@ $(OBJS) -aodvd-arm: $(OBJS_ARM) Makefile$(name).pdf +aodvd-arm: $(OBJS_ARM) $(ARM_CC) $(CFLAGS) -DARM -o $(@:%-arm=%) $(OBJS_ARM) aodv-uu.o: $(OBJS_NS_CPP) $(OBJS_NS) @@ -130,49 +135,66 @@ rm -f /usr/sbin/aodvd rm -rf /lib/modules/$(KERNEL)/aodv -docs: - cd docs && $(MAKE) all +# Commented out, we don't have any documentation... yet. +# docs: +# cd docs && $(MAKE) all + clean: rm -f aodvd *~ *.o core *.log libaodv-uu.a endian endian.h - cd docs && $(MAKE) clean +# cd docs && $(MAKE) clean # DO NOT DELETE -main.o: defs.h timer_queue.h debug.h params.h aodv_socket.h aodv_rerr.h -main.o: routing_table.h aodv_timeout.h k_route.h aodv_hello.h aodv_rrep.h -main.o: packet_input.h packet_queue.h link_qual.h -debug.o: aodv_rreq.h defs.h timer_queue.h seek_list.h routing_table.h -debug.o: aodv_rrep.h aodv_rerr.h debug.h params.h -timer_queue.o: timer_queue.h defs.h debug.h -aodv_socket.o: aodv_socket.h defs.h timer_queue.h aodv_rerr.h routing_table.h -aodv_socket.o: aodv_rreq.h seek_list.h aodv_rrep.h params.h aodv_hello.h -aodv_socket.o: aodv_neighbor.h debug.h link_qual.h -aodv_hello.o: aodv_hello.h defs.h timer_queue.h aodv_rrep.h routing_table.h -aodv_hello.o: aodv_timeout.h aodv_rreq.h seek_list.h params.h aodv_socket.h -aodv_hello.o: aodv_rerr.h debug.h -aodv_neighbor.o: aodv_neighbor.h defs.h timer_queue.h aodv_hello.h -aodv_neighbor.o: aodv_rrep.h routing_table.h aodv_timeout.h aodv_rreq.h -aodv_neighbor.o: seek_list.h params.h aodv_socket.h aodv_rerr.h debug.h -aodv_timeout.o: defs.h timer_queue.h aodv_timeout.h aodv_socket.h aodv_rerr.h -aodv_timeout.o: routing_table.h aodv_rreq.h seek_list.h aodv_hello.h -aodv_timeout.o: aodv_rrep.h debug.h params.h packet_queue.h k_route.h icmp.h -routing_table.o: routing_table.h defs.h timer_queue.h aodv_timeout.h -routing_table.o: packet_queue.h aodv_rerr.h aodv_hello.h aodv_rrep.h -routing_table.o: aodv_socket.h k_route.h debug.h params.h seek_list.h -seek_list.o: seek_list.h defs.h timer_queue.h aodv_timeout.h params.h debug.h -k_route.o: defs.h timer_queue.h debug.h k_route.h -aodv_rreq.o: aodv_rreq.h defs.h timer_queue.h seek_list.h routing_table.h -aodv_rreq.o: aodv_rrep.h aodv_timeout.h k_route.h aodv_socket.h aodv_rerr.h -aodv_rreq.o: params.h debug.h -aodv_rrep.o: aodv_rrep.h defs.h timer_queue.h routing_table.h aodv_timeout.h -aodv_rrep.o: aodv_socket.h aodv_rerr.h debug.h params.h -aodv_rerr.o: aodv_rerr.h defs.h timer_queue.h routing_table.h aodv_socket.h -aodv_rerr.o: aodv_timeout.h debug.h params.h -packet_input.o: defs.h timer_queue.h debug.h routing_table.h aodv_rreq.h -packet_input.o: seek_list.h aodv_rerr.h libipq.h params.h aodv_timeout.h -packet_input.o: aodv_socket.h packet_queue.h packet_input.h -packet_queue.o: packet_queue.h defs.h timer_queue.h debug.h routing_table.h -packet_queue.o: libipq.h params.h -libipq.o: libipq.h -icmp.o: defs.h timer_queue.h debug.h -link_qual.o: defs.h timer_queue.h debug.h +aodv_hello.o: aodv_hello.c aodv_hello.h defs.h timer_queue.h aodv_rrep.h \ + routing_table.h aodv_timeout.h aodv_rreq.h seek_list.h params.h \ + aodv_socket.h aodv_rerr.h debug.h +aodv_neighbor.o: aodv_neighbor.c aodv_neighbor.h defs.h timer_queue.h \ + routing_table.h aodv_rerr.h aodv_hello.h aodv_rrep.h aodv_socket.h \ + params.h debug.h +aodv_rerr.o: aodv_rerr.c aodv_rerr.h defs.h timer_queue.h routing_table.h \ + aodv_socket.h aodv_timeout.h debug.h params.h +aodv_rrep.o: aodv_rrep.c aodv_rrep.h defs.h timer_queue.h routing_table.h \ + aodv_neighbor.h aodv_hello.h aodv_timeout.h aodv_socket.h aodv_rerr.h \ + debug.h params.h +aodv_rreq.o: aodv_rreq.c aodv_rreq.h defs.h timer_queue.h seek_list.h \ + routing_table.h aodv_rrep.h aodv_timeout.h k_route.h aodv_socket.h \ + aodv_rerr.h params.h debug.h +aodv_socket.o: aodv_socket.c aodv_socket.h defs.h timer_queue.h \ + aodv_rerr.h routing_table.h aodv_rreq.h seek_list.h aodv_rrep.h \ + params.h aodv_hello.h aodv_neighbor.h debug.h +aodv_timeout.o: aodv_timeout.c defs.h timer_queue.h aodv_timeout.h \ + aodv_socket.h aodv_rerr.h routing_table.h aodv_neighbor.h aodv_rreq.h \ + seek_list.h aodv_hello.h aodv_rrep.h debug.h params.h packet_queue.h \ + k_route.h icmp.h +debug.o: debug.c aodv_rreq.h defs.h timer_queue.h seek_list.h \ + routing_table.h aodv_rrep.h aodv_rerr.h debug.h params.h +endian.o: endian.c +icmp.o: icmp.c defs.h timer_queue.h debug.h +igmp.o: igmp.c +kaodv.o: kaodv.c +k_mroute.o: k_mroute.c +k_route.o: k_route.c defs.h timer_queue.h debug.h k_route.h +libipq.o: libipq.c libipq.h +link_qual.o: link_qual.c defs.h timer_queue.h debug.h +main.o: main.c defs.h timer_queue.h debug.h params.h aodv_socket.h \ + aodv_rerr.h routing_table.h aodv_timeout.h k_route.h aodv_hello.h \ + aodv_rrep.h packet_input.h packet_queue.h +maodv_grph.o: maodv_grph.c +maodv_mact.o: maodv_mact.c +maodv_neighbor.o: maodv_neighbor.c +maodv_rrep.o: maodv_rrep.c +maodv_rreq.o: maodv_rreq.c +multicast_packet_cache.o: multicast_packet_cache.c +multicast_routing_table.o: multicast_routing_table.c +packet_input.o: packet_input.c defs.h timer_queue.h debug.h \ + routing_table.h aodv_hello.h aodv_rrep.h aodv_rreq.h seek_list.h \ + aodv_rerr.h libipq.h params.h aodv_timeout.h aodv_socket.h \ + packet_queue.h packet_input.h +packet_queue.o: packet_queue.c packet_queue.h defs.h timer_queue.h \ + debug.h routing_table.h libipq.h params.h aodv_timeout.h +routing_table.o: routing_table.c routing_table.h defs.h timer_queue.h \ + aodv_timeout.h packet_queue.h aodv_rerr.h aodv_hello.h aodv_rrep.h \ + aodv_socket.h k_route.h debug.h params.h seek_list.h +seek_list.o: seek_list.c seek_list.h defs.h timer_queue.h aodv_timeout.h \ + params.h debug.h +timer_queue.o: timer_queue.c timer_queue.h defs.h debug.h diff -urN ./aodv-uu-0.6/aodv_hello.c ./maodv-umd/aodv_hello.c --- ./aodv-uu-0.6/aodv_hello.c Tue Nov 5 16:13:29 2002 +++ ./maodv-umd/aodv_hello.c Fri Jan 24 12:13:34 2003 @@ -117,7 +117,8 @@ rrep = rrep_create(flags, 0, 0, DEV_NR(i).ipaddr, this_host.seqno, DEV_NR(i).ipaddr, - ALLOWED_HELLO_LOSS * HELLO_INTERVAL); + ALLOWED_HELLO_LOSS * HELLO_INTERVAL, + 0 ); /* Assemble a RREP extension which contain our neighbor set... */ if (unidir_hack) { diff -urN ./aodv-uu-0.6/aodv_neighbor.c ./maodv-umd/aodv_neighbor.c --- ./aodv-uu-0.6/aodv_neighbor.c Wed Nov 6 10:43:35 2002 +++ ./maodv-umd/aodv_neighbor.c Sat Feb 8 14:19:30 2003 @@ -41,6 +41,7 @@ rt_table_t *rt = NULL; u_int32_t seqno = 0; int flags = 0; + struct timeval now; /* According to the draft, the seqno should always be set to * invalid when adding neighbors... */ @@ -68,6 +69,10 @@ VALID, flags); } + gettimeofday(&now, NULL); + hello_update_timeout(rt, ALLOWED_HELLO_LOSS * HELLO_INTERVAL); + rt->last_hello_time = now; + #ifndef AODVUU_LL_FEEDBACK hello_update_timeout(rt, ALLOWED_HELLO_LOSS * HELLO_INTERVAL); #endif diff -urN ./aodv-uu-0.6/aodv_rrep.c ./maodv-umd/aodv_rrep.c --- ./aodv-uu-0.6/aodv_rrep.c Wed Nov 6 08:48:46 2002 +++ ./maodv-umd/aodv_rrep.c Fri Feb 14 13:07:58 2003 @@ -36,6 +36,13 @@ #include "debug.h" #include "params.h" +#ifdef MAODV +#include "maodv_rrep.h" +#include "maodv_ext.h" +#include "maodv_mact.h" +#include "seek_list.h" +#endif + #endif extern int unidir_hack, optimized_hellos; @@ -46,9 +53,14 @@ u_int32_t dest_addr, u_int32_t dest_seqno, u_int32_t orig_addr, - u_int32_t life) + u_int32_t life, + u_int32_t grp_addr ) { RREP *rrep; +#ifdef MAODV + int size = RREP_SIZE; + GRP_MERGE_EXT * gme; +#endif rrep = (RREP *) aodv_socket_new_msg(); rrep->type = AODV_RREP; @@ -66,6 +78,19 @@ if (flags & RREP_ACK) rrep->a = 1; +#ifdef MAODV + if ( rrep->r ) { + /* add group merge extension */ + gme = (GRP_MERGE_EXT *) ((char *)rrep + size); + gme->type = GME_TYPE; + gme->length = GME_LENGTH; + gme->res = 0; + gme->grp_addr = htonl(grp_addr); + + size += GME_LENGTH + 2; /* length + "header" */ + } +#endif /* MAODV */ + /* Don't print information about hello messages... */ #ifdef DEBUG_OUTPUT if (dest_addr != orig_addr) { @@ -107,13 +132,15 @@ timer_remove(&rt->ack_timer); } -void NS_CLASS rrep_send(rt_table_t * rev_rt, rt_table_t * fwd_rt) +void NS_CLASS rrep_send(rt_table_t * rev_rt, rt_table_t * fwd_rt, + u_int16_t flags, u_int32_t grp_addr ) { RREP *rrep; - u_int8_t rrep_flags = 0; + u_int8_t rrep_flags = flags; u_int32_t seqno, dest, lifetime; int hcnt; struct timeval now; + int size = RREP_SIZE; if (!rev_rt) { DEBUG(LOG_WARNING, 0, "Can't send RREP, rev_rt = NULL!"); @@ -165,9 +192,16 @@ ip_to_str(dest)); rrep = rrep_create(rrep_flags, 0, hcnt, dest, seqno, rev_rt->dest_addr, - lifetime); + lifetime, grp_addr ); + +#ifdef MAODV + if ( rrep_flags & RREP_REPAIR ) { + DEBUG( LOG_DEBUG, 0, "RREP_GRP_MERGE_EXT set." ); + size += GRP_MERGE_EXT_SIZE; + } +#endif /* MAODV */ - aodv_socket_send((AODV_msg *) rrep, rev_rt->next_hop, RREP_SIZE, MAXTTL, + aodv_socket_send((AODV_msg *) rrep, rev_rt->next_hop, size, MAXTTL, &DEV_IFINDEX(rev_rt->ifindex)); /* Update precursor lists */ @@ -182,7 +216,7 @@ } void NS_CLASS rrep_forward(RREP * rrep, rt_table_t * rev_rt, - rt_table_t * fwd_rt, int ttl) + rt_table_t * fwd_rt, int ttl, int size ) { /* Sanity checks... */ if (!fwd_rt || !rev_rt) { @@ -221,10 +255,10 @@ } } - rrep = (RREP *) aodv_socket_queue_msg((AODV_msg *) rrep, RREP_SIZE); + rrep = (RREP *) aodv_socket_queue_msg((AODV_msg *) rrep, size); rrep->hcnt = fwd_rt->hcnt; /* Update the hopcount */ - aodv_socket_send((AODV_msg *) rrep, rev_rt->next_hop, RREP_SIZE, ttl, + aodv_socket_send((AODV_msg *) rrep, rev_rt->next_hop, size, ttl, &DEV_IFINDEX(rev_rt->ifindex)); precursor_add(fwd_rt, rev_rt->next_hop); @@ -240,6 +274,16 @@ u_int32_t rrep_dest, rrep_orig, rrep_lifetime, rrep_seqno, rrep_new_hcnt; u_int8_t pre_repair_hcnt = 0; rt_table_t *fwd_rt, *rev_rt; + int size = rreplen; + + AODV_ext * ext; + +#ifdef MAODV + GRP_MERGE_EXT * gmg_ext = NULL; + u_int32_t grp_addr; + + grp_addr = 0; +#endif /* Convert to correct byte order on affeected fields: */ rrep_dest = ntohl(rrep->dest_addr); @@ -265,7 +309,48 @@ #ifdef DEBUG_OUTPUT log_pkt_fields((AODV_msg *) rrep); #endif - + + ext = (AODV_ext *) ((char *) rrep + RREP_SIZE); + + while( rreplen > (int) RREP_SIZE ) { + switch(ext->type) { +#ifdef MAODV + case RREP_GRP_MERGE_EXT: + DEBUG(LOG_INFO, 0, "RREP includes group merge extension." ); + gmg_ext = (GRP_MERGE_EXT *) ext; + if ( gmg_ext->length != GME_LENGTH ) { + DEBUG(LOG_DEBUG, 0, "Wrong length[%d] for gmg_ext.", + gmg_ext->length ); + gmg_ext = NULL; + } else { + grp_addr = ntohl(gmg_ext->grp_addr); + } + break; +#endif + default: + log(LOG_WARNING, 0, __FUNCTION__, "Unknown extension type %d", + ext->type); + break; + } + rreplen -= AODV_EXT_SIZE(ext); + ext = AODV_EXT_NEXT(ext); + } + +#ifdef MAODV + if ( IN_MULTICAST( rrep_dest ) ) { + DEBUG(LOG_DEBUG, 0, "MAODV rrep process." ); + maodv_rrep_process( rrep, rreplen, ip_src, ip_dst, ip_ttl, + ifindex, size); + +#ifndef AODVUU_LL_FEEDBACK + if (optimized_hellos) + hello_start(); +#endif + + return; + } +#endif + /* ---------- CHECK IF WE SHOULD MAKE A FORWARD ROUTE ------------ */ fwd_rt = rt_table_find(rrep_dest); @@ -288,7 +373,12 @@ DEBUG(LOG_DEBUG, 0, "Dropping RREP, fwd_rt->hcnt=%d fwd_rt->seqno=%ld", fwd_rt->hcnt, fwd_rt->dest_seqno); } - return; + + if ( rrep->r ) { + DEBUG(LOG_DEBUG, 0, "Special RREP for group merge. Accepting despite an existing route." ); + } else { + return; + } } @@ -325,11 +415,102 @@ RERR_CALC_SIZE(rerr), 1, &DEV_IFINDEX(fwd_rt->ifindex)); } - } + } else { +#ifdef MAODV + mrt_table_t *mrt; + + if ( (gmg_ext != NULL) && + (mrt = mrt_table_find(grp_addr)) && + rrep->r ) { + mrt_nexthop_t *upstream; + + DEBUG(LOG_DEBUG, 0, "in gmg_ext processing section"); + DEBUG(LOG_DEBUG, 0, "grp_addr: %s", ip_to_str(grp_addr)); + + /* make ip_src upstream */ + upstream=mrt_table_get_activated_upstream(mrt); + if(upstream!=NULL){ + mrt_nexthop_deactivate(mrt, upstream->addr); + } + + upstream=mrt_nexthop_find(mrt, ip_src); + if(upstream==NULL){ + upstream=mrt_nexthop_add(mrt, ip_src, MRT_UPSTREAM, 0); + } + + if(upstream->activated){ + mrt_nexthop_deactivate(mrt, upstream->addr); + } + upstream->direction=MRT_UPSTREAM; + + mrt_nexthop_activate(mrt, upstream->addr); + + /* send mact */ + mact_send(MACT_JOIN, 1, grp_addr, ip_src, 1); + + /* route is repaired */ + mrt->in_repair=0; + + /* stop being leader */ + mrt->am_leader = 0; + + DEBUG( LOG_DEBUG, 0, "Giving up leadership to other leader." ); + DEBUG( LOG_DEBUG, 0, "grp_addr: %s", ip_to_str(grp_addr) ); + + seek_list_remove_mcast(rrep_dest, grp_addr); + } +#endif /* MAODV */ + } } else { /* --- Here we FORWARD the RREP on the REVERSE route --- */ if (rev_rt && rev_rt->state == VALID) { - rrep_forward(rrep, rev_rt, fwd_rt, --ip_ttl); +#ifdef MAODV + if ( rrep->r ) { + /* make old activated upstream a downstream? or let mact? */ + mrt_table_t *mrt; + + DEBUG(LOG_DEBUG, 0, "grp_addr: %s", ip_to_str(grp_addr)); + + if ( (gmg_ext != NULL) && + (mrt = mrt_table_find(grp_addr)) && + rrep->r ) { + mrt_nexthop_t *upstream; + + DEBUG(LOG_DEBUG, 0, "in gmg_ext processing section"); + DEBUG(LOG_DEBUG, 0, "grp_addr: %s", ip_to_str(grp_addr)); + + /* make ip_src upstream */ + upstream=mrt_table_get_activated_upstream(mrt); + if(upstream!=NULL){ + mrt_nexthop_deactivate(mrt, upstream->addr); + } + + upstream=mrt_nexthop_find(mrt, ip_src); + if(upstream==NULL){ + upstream=mrt_nexthop_add(mrt, ip_src, + MRT_UPSTREAM, 0); + } + + if(upstream->activated){ + mrt_nexthop_deactivate(mrt, upstream->addr); + } + upstream->direction=MRT_UPSTREAM; + + mrt_nexthop_activate(mrt, upstream->addr); + + mrt->is_router=1; + + /* send mact */ + mact_send(MACT_JOIN, 1, grp_addr, ip_src, 1); + + /* update GL information */ + /* GRPH->u */ + } + } + rrep_forward(rrep, rev_rt, fwd_rt, --ip_ttl, size); +#else /* MAODV */ + rrep_forward(rrep, rev_rt, fwd_rt, --ip_ttl, size); +#endif /* MAODV */ } else { DEBUG(LOG_DEBUG, 0, "Could not forward RREP - NO ROUTE!!!"); } diff -urN ./aodv-uu-0.6/aodv_rrep.h ./maodv-umd/aodv_rrep.h --- ./aodv-uu-0.6/aodv_rrep.h Thu Oct 31 19:09:55 2002 +++ ./maodv-umd/aodv_rrep.h Fri Jan 24 12:13:34 2003 @@ -72,12 +72,14 @@ u_int8_t prefix, u_int8_t hcnt, u_int32_t dest_addr, - u_int32_t dest_seqno, u_int32_t orig_addr, u_int32_t life); + u_int32_t dest_seqno, u_int32_t orig_addr, u_int32_t life, + u_int32_t grp_addr ); RREP_ack *rrep_ack_create(); -void rrep_send(rt_table_t * rev_rt, rt_table_t * fwd_rt); +void rrep_send(rt_table_t * rev_rt, rt_table_t * fwd_rt, u_int16_t flags, + u_int32_t grp_addr ); void rrep_forward(RREP * rrep, rt_table_t * rev_rt, rt_table_t * fwd_rt, - int ttl); + int ttl, int size ); void rrep_process(RREP * rrep, int rreplen, u_int32_t ip_src, u_int32_t ip_dst, int ip_ttl, unsigned int ifindex); void rrep_ack_process(RREP_ack * rrep_ack, int rreplen, u_int32_t ip_src, diff -urN ./aodv-uu-0.6/aodv_rreq.c ./maodv-umd/aodv_rreq.c --- ./aodv-uu-0.6/aodv_rreq.c Thu Oct 31 22:01:26 2002 +++ ./maodv-umd/aodv_rreq.c Sat Feb 15 16:18:58 2003 @@ -36,6 +36,14 @@ #include "seek_list.h" #include "defs.h" #include "debug.h" + + +#ifdef MAODV +#include "multicast_routing_table.h" +#include "maodv_rreq.h" +#include "maodv_ext.h" +#endif + #endif #define DEBUG_OUTPUT @@ -55,9 +63,15 @@ #endif RREQ *NS_CLASS rreq_create(u_int8_t flags, u_int32_t dest_addr, - u_int32_t dest_seqno, u_int32_t orig_addr) + u_int32_t dest_seqno, u_int32_t orig_addr, + u_int16_t grp_hcnt, u_int32_t grp_addr ) { RREQ *rreq; +#ifdef MAODV + int size = RREQ_SIZE; + GRP_REBUILD_EXT * gre; + GRP_MERGE_EXT * gme; +#endif rreq = (RREQ *) aodv_socket_new_msg(); rreq->type = AODV_RREQ; @@ -84,6 +98,30 @@ if (flags & RREQ_UNKNOWN_SEQNO) rreq->u = 1; +#ifdef MAODV + + if (flags & RREQ_GRP_REBUILD ) { + gre = (GRP_REBUILD_EXT *) ((char *) rreq + size); + gre->type = GRE_TYPE; + gre->length = GRE_LENGTH; + gre->grp_hcnt = htons(grp_hcnt); + + size += GRP_REBUILD_EXT_SIZE; + } + + if ( rreq->r && rreq->j ) { + /* add merge extension */ + gme = (GRP_MERGE_EXT *) ((char *) rreq + size); + gme->type = GME_TYPE; + gme->length = GME_LENGTH; + gme->res = 0; + gme->grp_addr = htonl(grp_addr); + + size += GRP_MERGE_EXT_SIZE; + } + +#endif /* MAODV */ + DEBUG(LOG_DEBUG, 0, "Assembled RREQ %s", ip_to_str(dest_addr)); #ifdef DEBUG_OUTPUT log_pkt_fields((AODV_msg *) rreq); @@ -92,6 +130,44 @@ return rreq; } +void NS_CLASS rreq_send_ext(u_int32_t dest_addr, u_int32_t dest_seqno, + int ttl, u_int8_t flags, u_int16_t grp_hcnt, + u_int32_t grp_addr ) +{ + RREQ *rreq; + int i; + int size = RREQ_SIZE; + + /* Check if we should force the gratuitous flag... (-g option). */ + if (rreq_gratuitous) + flags |= RREQ_GRATUITOUS; + +#ifdef MAODV + + if ( flags & RREQ_GRP_REBUILD ) { + DEBUG( LOG_DEBUG, 0, "RREQ_GRP_REBUILD_EXT set." ); + size += GRP_REBUILD_EXT_SIZE; + } + + if ( (flags & RREQ_JOIN) && (flags & RREQ_REPAIR) ) { + DEBUG( LOG_DEBUG, 0, "RREQ_GRP_MERGE_EXT set, group %s", ip_to_str(grp_addr) ); + size += GRP_MERGE_EXT_SIZE; + } + +#endif /* MAODV */ + + /* Broadcast on all interfaces */ + for (i = 0; i < MAX_NR_INTERFACES; i++) { + if (!DEV_NR(i).enabled) + continue; + rreq = rreq_create(flags, dest_addr, dest_seqno, DEV_NR(i).ipaddr, + grp_hcnt, grp_addr ); + + aodv_socket_send((AODV_msg *) rreq, AODV_BROADCAST, size, + ttl, &DEV_NR(i) ); + } +} + void NS_CLASS rreq_send(u_int32_t dest_addr, u_int32_t dest_seqno, int ttl, u_int8_t flags) { @@ -106,13 +182,14 @@ for (i = 0; i < MAX_NR_INTERFACES; i++) { if (!DEV_NR(i).enabled) continue; - rreq = rreq_create(flags, dest_addr, dest_seqno, DEV_NR(i).ipaddr); + rreq = rreq_create(flags, dest_addr, dest_seqno, DEV_NR(i).ipaddr, + 0, 0 ); aodv_socket_send((AODV_msg *) rreq, AODV_BROADCAST, RREQ_SIZE, ttl, &DEV_NR(i)); } } -void NS_CLASS rreq_forward(RREQ * rreq, int ttl) +void NS_CLASS rreq_forward(RREQ * rreq, int ttl, int size ) { int i; /* FORWARD the RREQ if the TTL allows it. */ @@ -120,7 +197,7 @@ ip_to_str(ntohl(rreq->orig_addr)), ntohl(rreq->rreq_id)); /* Queue the received message in the send buffer */ - rreq = (RREQ *) aodv_socket_queue_msg((AODV_msg *) rreq, RREQ_SIZE); + rreq = (RREQ *) aodv_socket_queue_msg((AODV_msg *) rreq, size ); rreq->hcnt++; /* Increase hopcount to account for * intermediate route */ @@ -129,10 +206,35 @@ for (i = 0; i < MAX_NR_INTERFACES; i++) { if (!DEV_NR(i).enabled) continue; - aodv_socket_send((AODV_msg *) rreq, AODV_BROADCAST, RREQ_SIZE, ttl, + aodv_socket_send((AODV_msg *) rreq, AODV_BROADCAST, size, ttl, + &DEV_NR(i)); + } +} + +#ifdef MAODV +void NS_CLASS rreq_forward_uni(RREQ * rreq, u_int32_t dest, int ttl, + int size ) +{ + int i; + /* FORWARD the RREQ if the TTL allows it. */ + DEBUG(LOG_INFO, 0, "forwarding RREQ src=%s, rreq_id=%lu", + ip_to_str(ntohl(rreq->orig_addr)), ntohl(rreq->rreq_id)); + + /* Queue the received message in the send buffer */ + rreq = (RREQ *) aodv_socket_queue_msg((AODV_msg *) rreq, size ); + + rreq->hcnt++; /* Increase hopcount to account for + * intermediate route */ + + /* Send out on all interfaces */ + for (i = 0; i < MAX_NR_INTERFACES; i++) { + if (!DEV_NR(i).enabled) + continue; + aodv_socket_send((AODV_msg *) rreq, AODV_BROADCAST, size, ttl, &DEV_NR(i)); } } +#endif /* MAODV */ void NS_CLASS rreq_process(RREQ * rreq, int rreqlen, u_int32_t ip_src, u_int32_t ip_dst, int ip_ttl, unsigned int ifindex) @@ -142,6 +244,14 @@ rt_table_t *rev_rt, *fwd_rt = NULL; u_int32_t rreq_orig, rreq_dest, rreq_orig_seqno, rreq_dest_seqno; u_int32_t rreq_id, rreq_new_hcnt, life; + int size; +#ifdef MAODV + GRP_REBUILD_EXT *grb_ext=NULL; + GRP_MERGE_EXT *gmg_ext=NULL; + u_int32_t grp_addr; + + grp_addr = 0; +#endif rreq_id = ntohl(rreq->rreq_id); rreq_dest = ntohl(rreq->dest_addr); @@ -150,6 +260,7 @@ rreq_orig_seqno = ntohl(rreq->orig_seqno); rreq_new_hcnt = rreq->hcnt + 1; + size = rreqlen; DEBUG(LOG_DEBUG, 0, "ip_src=%s rreq_orig=%s rreq_dest=%s", ip_to_str(ip_src), ip_to_str(rreq_orig), ip_to_str(rreq_dest)); @@ -191,14 +302,36 @@ DEBUG(LOG_INFO, 0, "RREQ include EXTENSION"); /* Do something here */ break; +#ifdef MAODV + case RREQ_GRP_REBUILD_EXT: + DEBUG(LOG_INFO, 0, "RREQ includes group rebuild extension"); + grb_ext=(GRP_REBUILD_EXT*)ext; + if(grb_ext->length!=GRE_LENGTH) { + grb_ext=NULL; + } + break; + case RREQ_GRP_MERGE_EXT: + DEBUG(LOG_INFO, 0, "RREQ includes group merge extension" ); + gmg_ext = (GRP_MERGE_EXT *) ext; + if ( gmg_ext->length != GME_LENGTH ) { + gmg_ext = NULL; + } else { + grp_addr = ntohl(gmg_ext->grp_addr); + } + break; +#endif default: - log(LOG_WARNING, 0, __FUNCTION__, "Unknown extension type %d", - ext->type); + log(LOG_WARNING, 0, __FUNCTION__, "Unknown extension type." ); break; } rreqlen -= AODV_EXT_SIZE(ext); ext = AODV_EXT_NEXT(ext); } + +#ifdef MAODV + DEBUG(LOG_DEBUG, 0, "grp_addr: %s", ip_to_str(grp_addr)); +#endif /* MAODV */ + #ifdef DEBUG_OUTPUT log_pkt_fields((AODV_msg *) rreq); #endif @@ -242,9 +375,21 @@ this_host.gateway_mode && (rreq_dest & DEV_IFINDEX(ifindex).netmask) != (DEV_IFINDEX(ifindex).ipaddr & DEV_IFINDEX(ifindex).netmask)) { - rrep_send(rev_rt, NULL); + rrep_send(rev_rt, NULL, 0, 0); return; } + +#ifdef MAODV + if ( IN_MULTICAST(rreq_dest) ) { + DEBUG(LOG_DEBUG, 0, "MAODV RREQ process."); + /* TODO: Added multicast rreq support. */ + maodv_rreq_process( rreq, rreqlen, ip_src, ip_dst, + ip_ttl, ifindex, grb_ext, size ); + + return; + } +#endif + /* Are we the destination of the RREQ?, if so we should immediately send a RREP.. */ if (rreq_dest == DEV_IFINDEX(ifindex).ipaddr) { @@ -252,10 +397,26 @@ /* WE are the RREQ DESTINATION. Update the node's own sequence number to the maximum of the current seqno and the one in the RREQ. */ - if (!rreq->u && this_host.seqno < rreq_dest_seqno) - this_host.seqno = rreq_dest_seqno; + if (!rreq->u && this_host.seqno == rreq_dest_seqno) + this_host.seqno++; - rrep_send(rev_rt, NULL); +#ifdef MAODV + if ((rreq->j) && (rreq->r) && (gmg_ext != NULL)) { + mrt_table_t *mrt; + mrt=mrt_table_find(grp_addr); + if(mrt->am_leader && !mrt->in_repair){ + /* recieved a rreq because i'm leader */ + DEBUG(LOG_DEBUG, 0, "Received a RREQ[j] for me. Should send RREP for group."); + /* make GRPH flag update */ + mrt->grph_update_cnt=2; + rrep_send(rev_rt, NULL, RREP_REPAIR, grp_addr ); + } + } else { + rrep_send(rev_rt, NULL, 0, 0); + } +#else /* MAODV */ + rrep_send(rev_rt, NULL, 0, 0); +#endif /* MAODV */ } else { /* We are an INTERMEDIATE node. - check if we have an active @@ -271,12 +432,12 @@ enough (our destination sequence number for that route is larger than the one in the RREQ). */ - rrep_send(rev_rt, fwd_rt); + rrep_send(rev_rt, fwd_rt, 0, 0); /* If the GRATUITOUS flag is set, we must also unicast a gratuitous RREP to the destination. */ if (rreq->g) { - rrep_send(fwd_rt, rev_rt); + rrep_send(fwd_rt, rev_rt, 0, 0); DEBUG(LOG_INFO, 0, "Sending G-RREP to %s with rte to %s", ip_to_str(rreq_dest), ip_to_str(rreq_orig)); @@ -290,7 +451,38 @@ rreq->u = 0; } - rreq_forward(rreq, --ip_ttl); +#ifdef MAODV + if (( rreq->j ) && ( rreq->r ) && (gmg_ext != NULL)) { + mrt_table_t * mrt; + mrt_nexthop_t * upstream; + + /* if I am part of group, unicast up. */ + /* else regular rreq */ + DEBUG( LOG_DEBUG, 0, "Recieved a RREQ[jr], forwarding." ); + + mrt = mrt_table_find( grp_addr ); + if (( mrt != NULL ) && + ( mrt->grp_leader_addr == rreq_dest ) && + ( mrt->is_router ) ) { + /* one of the members of the >ip tree */ + + /* find activated upstream */ + upstream = mrt_table_get_activated_upstream( mrt ); + if ( ! upstream ) { + DEBUG( LOG_DEBUG, 0, "Odd State: no activated upstream, but not leader..." ); + } else { + rreq_forward_uni(rreq, upstream->addr, --ip_ttl, size ); + } + } else { + /* not part of > ip tree, just forward along */ + rreq_forward(rreq, --ip_ttl, size ); + } + } else { + rreq_forward(rreq, --ip_ttl, size ); + } +#else /* MAODV */ + rreq_forward(rreq, --ip_ttl, size ); +#endif /* MAODV */ } else { DEBUG(LOG_DEBUG, 0, "RREQ not forwarded - ttl=0"); @@ -301,33 +493,58 @@ /* Perform route discovery for a unicast destination */ void NS_CLASS rreq_route_discovery(u_int32_t dest_addr, u_int8_t flags, - struct ip_data *ipd) + struct ip_data *ipd, u_int32_t grp_addr) { struct timeval now; rt_table_t *rt; seek_list_t *seek_entry; u_int32_t dest_seqno; int ttl; + u_int16_t grp_hcnt; + +#ifdef MAODV + mrt_table_t *mrt; +#endif /* MAODV */ gettimeofday(&now, NULL); +#ifdef MAODV + /* for non-merge RREQs, grp_addr should always be zero, so + seek_list_find_mcast will act like seek_list_find. */ + if (seek_list_find_mcast(dest_addr, grp_addr)) + return; +#else if (seek_list_find(dest_addr)) return; +#endif /* If we already have a route entry, we use information from it. */ rt = rt_table_find(dest_addr); + grp_hcnt = 0; + +#ifdef MAODV + mrt = NULL; + if ( IN_MULTICAST( dest_addr ) ) { + mrt = mrt_table_find( dest_addr ); + } +#endif + ttl = NET_DIAMETER; /* This is the TTL if we don't use expanding ring search */ - if (rt == NULL) { +#ifdef MAODV + if (( rt == NULL ) && ( mrt == NULL )) { +#else + if ( rt == NULL ) { +#endif /* MAODV */ flags |= RREQ_UNKNOWN_SEQNO; dest_seqno = 0; if (expanding_ring_search) ttl = TTL_START; - } else { + } else if ( rt != NULL ) { if (rt->flags & RT_INV_SEQNO) { flags |= RREQ_UNKNOWN_SEQNO; @@ -343,12 +560,44 @@ if (timeval_diff(&rt->rt_timer.timeout, &now) < (2 * NET_TRAVERSAL_TIME)) rt_table_update_timeout(rt, 2 * NET_TRAVERSAL_TIME); + +#ifndef MAODV + } +#else + } else { + + if ( mrt->grp_seqno == 0 ) { + flags |= RREQ_UNKNOWN_SEQNO; + dest_seqno = 0; + } else + dest_seqno = mrt->grp_seqno; + + if (expanding_ring_search) { + if ( mrt->leader_hcnt == 0xff ) { + ttl = TTL_START; + } else { + ttl = mrt->leader_hcnt + TTL_INCREMENT; + } + } + + grp_hcnt = mrt->leader_hcnt; + + /* A routing table entry waiting for a RREP should not be expunged + before 2 * NET_TRAVERSAL_TIME... */ + /* CHECK: timeouts not happening yet. */ + /* + if (timeval_diff(&mrt->mrt_timer.timeout, &now) < + (2 * NET_TRAVERSAL_TIME)) + mrt_table_update_timeout(mrt, 2 * NET_TRAVERSAL_TIME); + */ } +#endif /* MAODV */ - rreq_send(dest_addr, dest_seqno, ttl, flags); + rreq_send_ext(dest_addr, dest_seqno, ttl, flags, grp_hcnt, grp_addr); /* Remember that we are seeking this destination */ - seek_entry = seek_list_insert(dest_addr, dest_seqno, ttl, flags, ipd); + seek_entry = seek_list_insert(dest_addr, dest_seqno, ttl, flags, ipd, + grp_hcnt, grp_addr); /* Set a timer for this RREQ */ if (expanding_ring_search) @@ -414,7 +663,7 @@ /* Remember that we are seeking this destination and setup the timers */ seek_entry = seek_list_insert(rt->dest_addr, rt->dest_seqno, - ttl, flags, ipd); + ttl, flags, ipd, 0, 0); if (expanding_ring_search) timer_set_timeout(&seek_entry->seek_timer, diff -urN ./aodv-uu-0.6/aodv_rreq.h ./maodv-umd/aodv_rreq.h --- ./aodv-uu-0.6/aodv_rreq.h Thu Oct 31 19:09:56 2002 +++ ./maodv-umd/aodv_rreq.h Sat Feb 15 16:18:58 2003 @@ -36,6 +36,7 @@ #define RREQ_GRATUITOUS 0x4 #define RREQ_DEST_ONLY 0x8 #define RREQ_UNKNOWN_SEQNO 0x10 +#define RREQ_GRP_REBUILD 0x20 typedef struct { u_int8_t type; @@ -56,7 +57,6 @@ # else # error "Adjust your defines" # endif - u_int8_t flags; u_int8_t res2; u_int8_t hcnt; u_int32_t rreq_id; @@ -85,20 +85,27 @@ #ifndef NS_NO_DECLARATIONS RREQ *rreq_create(u_int8_t flags, u_int32_t dest_addr, - u_int32_t dest_seqno, u_int32_t orig_addr); + u_int32_t dest_seqno, u_int32_t orig_addr, + u_int16_t grp_hcnt, u_int32_t grp_addr ); +void rreq_send_ext(u_int32_t dest_addr, u_int32_t dest_seqno, int ttl, + u_int8_t flags, u_int16_t grp_hcnt, u_int32_t grp_addr ); void rreq_send(u_int32_t dest_addr, u_int32_t dest_seqno, int ttl, u_int8_t flags); -void rreq_forward(RREQ * rreq, int ttl); +void rreq_forward(RREQ * rreq, int ttl, int size); void rreq_process(RREQ * rreq, int rreqlen, u_int32_t ip_src, u_int32_t ip_dst, int ip_ttl, unsigned int ifindex); void rreq_route_discovery(u_int32_t dest_addr, u_int8_t flags, - struct ip_data *ipd); + struct ip_data *ipd, u_int32_t grp_addr ); int rreq_record_remove(u_int32_t orig_addr, u_int32_t rreq_id); struct blacklist *rreq_blacklist_insert(u_int32_t dest_addr); int rreq_blacklist_remove(u_int32_t dest_addr); void rreq_local_repair(rt_table_t * rt, u_int32_t src_addr, struct ip_data *ipd); +#ifdef MAODV +void NS_CLASS rreq_forward_uni(RREQ * rreq, u_int32_t dest, int ttl, int size); +#endif /* MAODV */ + #ifdef NS_PORT struct rreq_record *rreq_record_insert(u_int32_t orig_addr, u_int32_t rreq_id); struct rreq_record *rreq_record_find(u_int32_t orig_addr, u_int32_t rreq_id); diff -urN ./aodv-uu-0.6/aodv_socket.c ./maodv-umd/aodv_socket.c --- ./aodv-uu-0.6/aodv_socket.c Mon Nov 4 11:03:28 2002 +++ ./maodv-umd/aodv_socket.c Thu Jan 16 14:41:58 2003 @@ -49,6 +49,12 @@ #ifdef USE_IW_SPY #include "link_qual.h" #endif + +#ifdef MAODV +#include "maodv_mact.h" +#include "maodv_grph.h" +#endif + #endif /* NS_PORT */ #ifndef NS_PORT @@ -228,6 +234,16 @@ DEBUG(LOG_DEBUG, 0, "Received RREP_ACK"); rrep_ack_process((RREP_ack *) aodv_msg, len, src, dst); break; +#ifdef MAODV + case MAODV_MACT: + DEBUG(LOG_DEBUG, 0, "Received MACT"); + mact_process((MACT *) aodv_msg); + break; + case MAODV_GRPH: + DEBUG(LOG_DEBUG, 0, "Received GRPH"); + grph_process((GRPH *) aodv_msg, src, ttl); + break; +#endif default: log(LOG_WARNING, 0, __FUNCTION__, "Unknown msg type %u rcvd from %s to %s", aodv_msg->type, diff -urN ./aodv-uu-0.6/aodv_timeout.c ./maodv-umd/aodv_timeout.c --- ./aodv-uu-0.6/aodv_timeout.c Sun Nov 3 19:22:47 2002 +++ ./maodv-umd/aodv_timeout.c Sat Feb 15 16:18:58 2003 @@ -41,6 +41,13 @@ #include "k_route.h" #include "seek_list.h" #include "icmp.h" + +#ifdef MAODV +#include "multicast_routing_table.h" +#include "maodv_mact.h" +#include "maodv_neighbor.h" +#endif /* MAODV */ + #endif /* These are timeout functions which are called when timers expire... */ @@ -55,6 +62,9 @@ struct timeval now; seek_list_t *seek_entry; rt_table_t *rt, *repair_rt; +#ifdef MAODV + u_int32_t dest_addr; +#endif seek_entry = (seek_list_t *) arg; @@ -96,11 +106,77 @@ (2 * NET_TRAVERSAL_TIME)) rt_table_update_timeout(rt, 2 * NET_TRAVERSAL_TIME); - rreq_send(seek_entry->dest_addr, seek_entry->dest_seqno, - seek_entry->ttl, seek_entry->flags); - + rreq_send_ext(seek_entry->dest_addr, seek_entry->dest_seqno, + seek_entry->ttl, seek_entry->flags, seek_entry->grp_hcnt, + seek_entry->grp_addr ); } else { +#ifdef MAODV + if(seek_entry->flags & RREQ_JOIN && !(seek_entry->flags & RREQ_REPAIR)){ + mrt_table_t *group_rec; + mrt_nexthop_t *upstream; + + DEBUG(LOG_DEBUG, 0, "In special MCAST timeout segment"); + + /* try to join the group */ + group_rec=mrt_table_find(seek_entry->dest_addr); + upstream=mact_activate_best_upstream(group_rec); + + if(upstream){ + if(!group_rec->is_broken){ + /* we were able to select an upstream */ + group_rec->is_member=1; + DEBUG(LOG_DEBUG, 0, "Joined Group"); + }else{ + /* we were repairing route */ + group_rec->is_broken=0; + } + }else{ + /* have to become leader ourselves */ + if(group_rec->is_broken && !group_rec->is_member){ + /* we are a router who lost his upstream */ + group_rec->is_broken=0; + mact_make_downstream_leader(group_rec); + DEBUG(LOG_DEBUG, 0, "Link broke, made downstream leader."); + }else{ + if ( group_rec->is_broken ) { + group_rec->is_broken = 0; + DEBUG(LOG_DEBUG, 0, "Was broken, now fixed."); + } + + mrt_table_become_leader(group_rec); + DEBUG(LOG_DEBUG, 0, "Became group leader"); + } + } + + dest_addr = seek_entry->dest_addr; + if ( seek_list_remove(seek_entry->dest_addr) ) { + if ( mcast_packet_queue_send(dest_addr) < 0 ) { + DEBUG(LOG_DEBUG, 0, "Error dequeueing packets."); + } + } else { + DEBUG(LOG_DEBUG, 0, "No longer in seek list."); + } + + return; + } else if ( (seek_entry->flags & RREQ_JOIN) && + (seek_entry->flags & RREQ_REPAIR) ) { + mrt_table_t * mrt; + mrt=mrt_table_find(seek_entry->grp_addr); + + if ( mrt ) { + /* Done merging, might have worked. */ + DEBUG(LOG_DEBUG, 0, "Route discovery for merge timed out. Clearing in_repair."); + + mrt->in_repair = 0; + } else { + DEBUG(LOG_DEBUG, 0, "Bad dest_addr:%d in seek_list.", + ip_to_str(seek_entry->grp_addr) ); + } + } +#endif /* MAODV */ + /* have to drop if no route */ packet_queue_drop(seek_entry->dest_addr); + DEBUG(LOG_DEBUG, 0, "NO ROUTE FOUND!"); @@ -172,6 +248,31 @@ precursor_list_destroy(rt); } +#ifdef MAODV +void NS_CLASS multicast_route_expire_timeout( void * arg ) +{ + mrt_table_t *mrt; + + mrt = (mrt_table_t *) arg; + + if ( !mrt ) { + log( LOG_WARNING, 0, __FUNCTION__, "arg was NULL, ignoring timeout!" ); + return; + } + + DEBUG( LOG_DEBUG, 0, "Multicast Route %s DOWN, seqno = %d", + ip_to_str( mrt->grp_addr ), mrt->grp_seqno ); + +/* + CHECK: Remove after creating valid flag. + + mrt_table_invalidate( mrt ); + mrt_nexthop_remove_all( mrt ); +*/ + + return; +} +#endif void NS_CLASS route_expire_timeout(void *arg) { @@ -241,6 +342,9 @@ #endif } neighbor_link_break(rt); +#ifdef MAODV + mcast_neighbor_link_break(rt); +#endif } } diff -urN ./aodv-uu-0.6/aodv_timeout.h ./maodv-umd/aodv_timeout.h --- ./aodv-uu-0.6/aodv_timeout.h Sun Nov 3 19:22:47 2002 +++ ./maodv-umd/aodv_timeout.h Mon Nov 11 14:56:49 2002 @@ -31,6 +31,7 @@ void route_delete_timeout(void *arg); void local_repair_timeout(void *arg); void route_discovery_timeout(void *arg); +void multicast_route_expire_timeout(void *arg); void route_expire_timeout(void *arg); void hello_timeout(void *arg); void rreq_record_timeout(void *arg); diff -urN ./aodv-uu-0.6/defs.h ./maodv-umd/defs.h --- ./aodv-uu-0.6/defs.h Tue Nov 5 16:13:29 2002 +++ ./maodv-umd/defs.h Sat Feb 15 16:18:58 2003 @@ -27,13 +27,16 @@ #include #include #include +#include #ifndef NS_PORT #include + #include #include #include #include + #endif #include @@ -138,7 +141,6 @@ } #endif - /* Two macros to simplify retriving of a dev_info struct. Either using an ifindex or a device number (index into devs array). */ #define DEV_IFINDEX(ifindex) (this_host.devs[ifindex2devindex(ifindex)]) @@ -156,6 +158,12 @@ #define AODV_RERR 3 #define AODV_RREP_ACK 4 +#ifdef MAODV +/* multicast types */ +#define MAODV_MACT 5 +#define MAODV_GRPH 6 +#endif /* MAODV */ + /* A generic AODV packet header struct... */ #ifdef NS_PORT struct AODV_msg { @@ -189,6 +197,13 @@ #define RREP_HELLO_INTERVAL_EXT 2 #define RREP_HELLO_NEIGHBOR_SET_EXT 3 +#ifdef MAODV +/* MAODV Extension types */ +#define RREQ_GRP_REBUILD_EXT 4 +#define RREQ_GRP_MERGE_EXT 9 +#define RREP_GRP_MERGE_EXT 9 +#endif /* MAODV */ + /* An generic AODV extensions header */ typedef struct { u_int8_t type; diff -urN ./aodv-uu-0.6/draft-ietf-manet-maodv-00.txt ./maodv-umd/draft-ietf-manet-maodv-00.txt --- ./aodv-uu-0.6/draft-ietf-manet-maodv-00.txt Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/draft-ietf-manet-maodv-00.txt Thu Nov 14 17:38:44 2002 @@ -0,0 +1,1425 @@ + +Mobile Ad Hoc Networking Working Group Elizabeth M. Royer +INTERNET DRAFT University of California, Santa Barbara +15 July 2000 Charles E. Perkins + Nokia Research Center + + Multicast Ad hoc On-Demand Distance Vector (MAODV) Routing + draft-ietf-manet-maodv-00.txt + + +Status of This Memo + + This document is a submission by the Mobile Ad Hoc Networking Working + Group of the Internet Engineering Task Force (IETF). Comments should + be submitted to the manet@itd.nrl.navy.mil mailing list. + + Distribution of this memo is unlimited. + + This document is an Internet-Draft and is in full conformance with + all provisions of Section 10 of RFC2026. Internet-Drafts are working + documents of the Internet Engineering Task Force (IETF), its areas, + and its working groups. Note that other groups may also distribute + working documents as Internet-Drafts. + + Internet-Drafts are draft documents valid for a maximum of six months + and may be updated, replaced, or obsoleted by other documents at + any time. It is inappropriate to use Internet-Drafts as reference + material or to cite them other than as "work in progress." + + The list of current Internet-Drafts can be accessed at: + http://www.ietf.org/ietf/1id-abstracts.txt + The list of Internet-Draft Shadow Directories can be accessed at: + http://www.ietf.org/shadow.html. + + +Abstract + + The multicast operation of the Ad hoc On-Demand Distance Vector + (AODV) routing protocol (MAODV) is intended for use by mobile nodes + in an ad hoc network. It offers quick adaptation to dynamic link + conditions, low processing and memory overhead, and low network + utilization. It creates bi-directional shared multicast trees + connecting multicast sources and receivers. These multicast trees + are maintained as long as group members exist within the connected + portion of the network. Each multicast group has a group leader + whose responsibility is maintaining the group sequence number, which + is used to ensure freshness of routing information. + + + + + + + + + +Royer, Perkins Expires 15 December 2000 [Page i] + +Internet Draft Multicast AODV 15 July 2000 + + + + + Contents + + +Status of This Memo i + +Abstract i + + 1. Introduction 2 + + 2. Overview 2 + + 3. Route Tables 3 + + 4. MAODV Terminology 5 + + 5. Route Request (RREQ) Message Format 6 + + 6. Route Reply (RREP) Message Format 6 + + 7. Multicast Activation (MACT) Message Format 7 + + 8. Group Hello (GRPH) Message Format 8 + + 9. Protocol Operation 9 + 9.1. Maintaining Multicast Tree Utilization Records . . . . . 9 + 9.2. Generating Route Requests . . . . . . . . . . . . . . . . 9 + 9.2.1. Controlling Route Request broadcasts . . . . . . 10 + 9.3. Receiving Route Requests . . . . . . . . . . . . . . . . 10 + 9.4. Generating Route Replies . . . . . . . . . . . . . . . . 11 + 9.5. Forwarding Route Replies . . . . . . . . . . . . . . . . 12 + 9.6. Route Activation . . . . . . . . . . . . . . . . . . . . 12 + 9.7. Multicast Tree Pruning . . . . . . . . . . . . . . . . . 13 + 9.8. Repairing a Broken Link . . . . . . . . . . . . . . . . . 14 + 9.9. Tree Partitions . . . . . . . . . . . . . . . . . . . . . 16 + 9.10. Reconnecting Two Trees . . . . . . . . . . . . . . . . . 17 + 9.11. Maintaining Local Connectivity . . . . . . . . . . . . . 17 + 9.12. Group Hello Messages . . . . . . . . . . . . . . . . . . 18 + 9.13. Actions After Reboot . . . . . . . . . . . . . . . . . . 19 + 9.14. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 20 + +10. Extensions 20 + 10.1. Multicast Group Leader Extension Format . . . . . . . . . 20 + 10.2. Multicast Group Rebuild Extension Format . . . . . . . . 21 + 10.3. Multicast Group Information Extension Format . . . . . . 21 + +11. Configuration Parameters 22 + + + + +Royer, Perkins Expires 15 December 2000 [Page 1] + +Internet Draft Multicast AODV 15 July 2000 + + +12. Security Considerations 23 + + +1. Introduction + + The Multicast Ad hoc On-Demand Distance Vector (MAODV) protocol + enables dynamic, self-starting, multihop routing between + participating mobile nodes wishing to join or participate in a + multicast group within an ad hoc network. The membership of these + multicast groups is free to change during the lifetime of the + network. MAODV enables mobile nodes to establish a tree connecting + multicast group members. Mobile nodes are able to respond quickly + to link breaks in multicast trees by repairing these breaks in a + timely manner. In the event of a network partition, multicast trees + are established independently in each partition, and trees for the + same multicast group are quickly connected if the network components + merge. + + One distinguishing feature of MAODV is its use of sequence numbers + for multicast groups. Each multicast group has its own sequence + number, which is initialized by the multicast group leader and + incremented periodically. Using these sequence numbers ensures that + routes found to multicast groups are always the most current ones + available. Given the choice between two routes to a multicast tree, + a requesting node always selects the one with the greatest sequence + number. + + MAODV is the multicast protocol associated with the Ad hoc On-Demand + Distance Vector (AODV) routing protocol, and as such it shares many + similarities and packet formats with AODV. The Route Request and + Route Reply packet types are based on those used by AODV, as is the + unicast Route Table. Similarly, many of the configuration parameters + used by MAODV are defined by AODV. The reader is referred to the AODV + Internet draft [2] for the suggested values of those parameters, as + well as for details on the unicast operation of AODV. + + +2. Overview + + Route Requests (RREQs), Route Replies (RREPs), Multicast Activations + (MACTs), and Group Hellos (GRPHs) are the message types utilized + by the multicast operation AODV. RREQs and RREPs are handled as + specified in [2], except for certain procedures controlled by new + flags (see section 5, 6). These message types are handled by UDP, + and normal IP header processing applies. So, for instance, the + requesting node is expected to use its IP address as the source IP + address for the messages. The range of dissemination of broadcast + RREQs can be indicated by the TTL in the IP header. Fragmentation is + typically not required. + + + +Royer, Perkins Expires 15 December 2000 [Page 2] + +Internet Draft Multicast AODV 15 July 2000 + + + As long as the multicast group members remain connected (within + a ``multicast tree''), MAODV does not play any role. When a + node either wishes to join a multicast group or find a route to a + multicast group, the node uses a broadcast RREQ to discover a route + to the multicast tree associated with that group. For join requests, + a route is determined when the RREQ reaches a node that is already a + member of the multicast tree, and the node's record of the multicast + group sequence number is at least as great as that contained in the + RREQ. For non-join requests, any node with a current route to the + multicast tree may respond to the RREQ. A current route is defined as + an unexpired multicast route table entry whose associated sequence + number for the multicast group is at least as great as that contained + in the RREQ. The route to the multicast tree is made available by + unicasting a RREP back to the source of the RREQ. Since each node + receiving the request caches a route back to the source of the + request, the RREP can be unicast back to the source from any node + able to satisfy the request. Once the source node has waited the + discovery period to receive RREPs, it selects the best route to the + multicast tree and unicasts the next hop along that route a MACT + message. This message activates the route. + + Nodes monitor the link status of next hops on the multicast tree. + When a link break on the multicast tree is detected, the tree branch + should be immediately repaired through the use of the RREQ/RREP/MACT + messages. + + A multicast group leader is associated with each multicast group. + The primary responsibility of this node is the initialization and + maintenance of the group sequence number. A Group Hello message is + periodically broadcast across the network by the multicast group + leader. This message carries a multicast group and group sequence + number and corresponding group leader IP address. This information + is used for disseminating updated group sequence numbers throughout + the multicast group and for repairing multicast trees after a + previously disconnected portion of the network containing part of the + multicast tree becomes reachable once again. + + +3. Route Tables + + MAODV is a routing protocol, and it deals with route table + management. Route table information must be kept even for ephemeral + routes, such as are created to temporarily store reverse paths + towards nodes originating RREQs. MAODV uses the following fields + with each route table entry, which are based on the route table + defined in the AODV Internet Draft [2]: + + - Destination IP Address + + + + +Royer, Perkins Expires 15 December 2000 [Page 3] + +Internet Draft Multicast AODV 15 July 2000 + + + - Destination Sequence Number + + - Hop Count (number of hops needed to reach destination) + - Last Hop Count (described in subsection 9.2.1) + + - Next Hop + - Next Hop Interface + + - List of Precursors + - Lifetime (expiration or deletion time of the route) + + - Routing Flags + + The following information is stored in each entry of the multicast + route table for multicast tree routes: + + - Multicast Group IP Address + - Multicast Group Leader IP Address + + - Multicast Group Sequence Number + - Next Hops + + - Hop Count to next Multicast Group Member + + - Hop Count to Multicast Group Leader + + The Next Hops field is a linked list of structures, each of which + contains the following fields: + + - Next Hop IP Address + - Next Hop Interface + + - Link Direction + - Activated Flag + + The direction of the link is relative to the location of the group + leader, i.e. UPSTREAM is a next hop towards the group leader, and + DOWNSTREAM is a next hop away from the group leader. A node on the + multicast tree must necessarily have only one UPSTREAM link. The IP + Address of a Next Hop MUST NOT be used to forward multicast messages + until after a MACT message has activated the route (see Section 9.6). + The Next Hop Interface fields in the Route Table and Next Hop field + of the Multicast Route Table are used for recording the outgoing + interface on which the next hop can be reached (see Section 9.14). + + Nodes MAY also maintain a Group Leader Table, which is an association + between multicast groups and their corresponding group leaders. The + fields of the group leader table are the following: + + + + +Royer, Perkins Expires 15 December 2000 [Page 4] + +Internet Draft Multicast AODV 15 July 2000 + + + - Multicast Group IP Address + + - Group Leader IP Address + + This table can be used when discovering routes to multicast groups, + as described in Section 9.2. + + +4. MAODV Terminology + + This protocol specification uses conventional meanings [1] for + capitalized words such as MUST, SHOULD, etc., to indicate requirement + levels for various protocol features. This section defines other + terminology used with MAODV that is not already defined in [3]. + + group leader + + A node which is a member of the given multicast group + and which is typically the first such group member in the + connected portion of the network. This node is responsible for + initializing and maintaining the multicast group destination + sequence number. + + group leader table + + The table where ad hoc nodes keep information concerning each + multicast group and its corresponding group leader. There is + one entry in the table for each multicast group for which the + node has received a Group Hello (see Section 9.2). + + multicast tree + + The tree containing all nodes which are members of the + multicast group and all nodes which are needed to connect the + multicast group members. + + multicast route table + + The table where ad hoc nodes keep routing (including next hops) + information for various multicast groups. + + reverse route + + A route set up to forward a reply (RREP) packet back to the + source from the destination or from an intermediate node having + a route to the destination. + + + + + + +Royer, Perkins Expires 15 December 2000 [Page 5] + +Internet Draft Multicast AODV 15 July 2000 + + +5. Route Request (RREQ) Message Format + + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Type |J|R|G| Reserved | Hop Count | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Other fields as specified for AODV....... + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + The format of the Route Request message remains as specified in [2], + except that the following flags have been added: + + J Join flag; set when source node wants to join a + multicast group. + + R Repair flag; set when a node wants to initiate + a repair to connect two previously disconnected + portions of the multicast tree. + + When a node wishes to repair a multicast tree, it appends the + Multicast Group Rebuild extension (see Section 10.2). When a node + wishes to unicast the RREQ for a multicast group to the group leader, + it includes the Multicast Group Leader extension (see Section 10.1). + + +6. Route Reply (RREP) Message Format + + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Type |R| Reserved |Prefix Sz| Hop Count | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Other fields as specified for AODV....... + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + The format of the Route Reply message remains as specified in [2], + except that the following flag has been added: + + R Repair flag; set when a node is responding + to a repair request to connect two previously + disconnected portions of the multicast tree. + + When the RREP is sent for a multicast destination, the Multicast + Group Information extension is appended (see Section 10.3). + + + + + + + +Royer, Perkins Expires 15 December 2000 [Page 6] + +Internet Draft Multicast AODV 15 July 2000 + + +7. Multicast Activation (MACT) Message Format + + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Type |J|P|G|U|R| Reserved | Hop Count | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Multicast Group IP address | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Source IP address | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Source Sequence Number | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + + The format of the Multicast Activation message is illustrated above, + and contains the following fields: + + Type 4 + + J Join flag; set when a node is joining the multicast + group, as opposed to finding a route to the group for + the transmission of data messages. + + P Prune flag; set when a node wishes to prune itself + from the tree, unset when the node is activating a + tree link. + + G Group Leader flag; set by a multicast tree member that + fails to repair a multicast tree link breakage, and + indicates to the group member receiving the message + that it should become the new multicast group leader. + + U Update flag; set when a multicast tree member has + repaired a broken tree link and is now a new distance + from the group leader. + + R Reboot flag; set when a node has just rebooted (see + Section 9.13). + + Reserved Sent as 0; ignored on reception. + + Hop Count The distance of the sending node from the multicast + group leader. Used only when the 'U' flag is set; + otherwise sent as 0. + + Multicast Group IP Address + The IP address of the Multicast Group for which a + route is supplied. + + + +Royer, Perkins Expires 15 December 2000 [Page 7] + +Internet Draft Multicast AODV 15 July 2000 + + + Source IP Address + The IP address of the sending node. + + Source Sequence Number + The current sequence number for route information + generated by the source of the route request. + + To prune itself from the tree (i.e., inactivate its last link to the + multicast tree), a multicast tree member sends a MACT with the 'P' + flag = 1 to its next hop on the multicast tree. A multicast tree + member that has more than one next hop to the multicast tree SHOULD + NOT prune itself from the multicast tree. + + +8. Group Hello (GRPH) Message Format + + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Type |U|O| Reserved | Hop Count | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Group Leader IP address | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Multicast Group IP address | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Multicast Group Sequence Number | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + + The format of the Group Hello message is illustrated above, and + contains the following fields: + + Type 5 + + U Update flag; set when there has been a change in group + leader information. + + O Off_Mtree flag; set by a node receiving the group + hello that is not on the multicast tree. + + Reserved Sent as 0; ignored on reception. + + Hop Count The number of hops the packet has traveled. Used by + multicast tree nodes to update their distance from the + group leader when the M flag is not set. + + Group Leader IP Address + The IP address of the group leader. + + + + +Royer, Perkins Expires 15 December 2000 [Page 8] + +Internet Draft Multicast AODV 15 July 2000 + + + Multicast Group IP Address + The IP address of the Multicast Group for which the + sequence number is supplied. + + Multicast Group Sequence Number + The current sequence number of the multicast group. + + +9. Protocol Operation + + This section describes the scenarios under which nodes generate + control messages for multicast communication, and how the fields in + the messages are handled. + + +9.1. Maintaining Multicast Tree Utilization Records + + For each multicast tree to which a node belongs, either because + it is a member of the group or because it is a router for the + multicast tree, the node maintains a list of next hops -- i.e., those + 1-hop neighbors that are likewise a part of the multicast tree. + This list of next hops is used for forwarding messages received + for the multicast group. A node forwards a multicast message to + every such next hop, except that neighbor from which the message + arrived. If there are multiple next hops, the forwarding operation + MAY be performed by broadcasting the multicast packet to the node's + neighbors; only the neighbors that belong to the multicast tree + and have not already received the packet continue to forward the + multicast packet. + + +9.2. Generating Route Requests + + A node sends a RREQ either when it determines that it should be a + part of a multicast group, and it is not already a member of that + group, or when it has a message to send to the multicast group but + does not have a route to that group. If the node wishes to join the + multicast group, it sets the `J' flag in the RREQ; otherwise, it + leaves the flag unset. The destination address of the RREQ is always + set to the multicast group address. If the node knows the group + leader and has a route to it, the node MAY place the group leader's + address in the Multicast Group Leader extension (Section 10.1), and + unicast the RREQ to the corresponding next hop for that destination. + Otherwise, if the node does not have a route to the group leader, or + if it does not know who the multicast group leader is, it broadcasts + the RREQ and does not include the extension field. + + After transmitting the RREQ, the node waits for the reception of a + RREP. The node may resend the RREQ up to RREQ_RETRIES additional + + + +Royer, Perkins Expires 15 December 2000 [Page 9] + +Internet Draft Multicast AODV 15 July 2000 + + + times if a RREP is not received. If a RREQ was unicast to a group + leader and a RREP is not received within RREP_WAIT_TIME milliseconds, + the node broadcasts subsequent RREQs for that multicast group across + the network. If a RREP is not received after RREQ_RETRIES additional + requests, the node may assume that there are no other members of that + particular group within the connected portion of the network. If it + wanted to join the multicast group, it then becomes the multicast + group leader for that multicast group and initializes the sequence + number of the multicast group. Otherwise, if it only wanted to send + packets to that group without actually joining the group, it drops + the packets it had for that group and aborts the session. + + When the node wishes to join or send a message to a multicast group, + it first consults its Group Leader Table. Based on the existence + of an entry for the multicast group in this table, the node then + formulates and sends the RREQ as described at the beginning of this + section. + + +9.2.1. Controlling Route Request broadcasts + + To prevent unnecessary network-wide broadcasts of RREQs, the source + node SHOULD use an expanding ring search technique as specified + in [2]. When a RREP is received, the Hop Count to the group leader + used in the RREP packet is remembered as Last Hop Count for that node + in the routing table. When a new route to the same multicast group + is required at a later time (e.g., upon a link break in the multicast + tree), the TTL in the RREQ IP header is initially set to this Last + Hop Count plus TTL_INCREMENT. Thereafter, following each timeout the + TTL is incremented by TTL_INCREMENT until TTL = TTL_THRESHOLD is + reached, as in [2]. + + +9.3. Receiving Route Requests + + When a node receives a RREQ, the node checks whether the 'J' flag of + the RREQ is set. If the 'J' flag is set, the node can only respond + if it is a member of the multicast tree for the indicated multicast + group, and if its record of the multicast group sequence number is + at least as great as that contained in the RREQ. If the 'J' flag is + not set, then the node can respond if it has an unexpired route to + the multicast group and the above multicast group sequence number + criteria is met. + + If the node does not meet either of these conditions, it rebroadcasts + the RREQ from its interface(s) but using its own IP address in the IP + header of the outgoing RREQ. The Destination Sequence Number in the + RREQ is updated to the maximum of the existing Destination Sequence + Number in the RREQ and the multicast group sequence number in the + + + +Royer, Perkins Expires 15 December 2000 [Page 10] + +Internet Draft Multicast AODV 15 July 2000 + + + multicast route table (if an entry exists) of the current node. The + TTL or hop limit field in the outgoing IP header is decreased by one. + The Hop Count field in the broadcast RREQ message is incremented by + one, to account for the new hop through the intermediate node. + + The node always creates or updates a reverse route as specified + in [2]. This reverse route would be needed in case the node + receives an eventual RREP back to the node which originated the RREQ + (identified by the Source IP Address). + + In addition to creating or updating the route table entry for the + source node, the node receiving the RREQ also creates a next hop + entry for the multicast group in its multicast route table. If no + entry exists for the multicast group, it creates one, and then places + the node from which it received the RREQ as next hop for that group. + It leaves the Activated flag associated with this next hop unset. + The direction for this next hop entry is DOWNSTREAM. + + +9.4. Generating Route Replies + + If a node receives a join RREQ for a multicast group, and it is + already a member of the multicast tree for that group, the node + updates its multicast route table and then generates a RREP message. + The Source and Destination IP Addresses in RREQ message are copied + to corresponding fields in the RREP message. The RREP contains the + current sequence number for the multicast group and the IP address + of the group leader. Furthermore, the node initializes the Hop + Count field of the RREP to zero. Additional information about the + multicast group is entered into the Multicast Group Information + extension (see Section 10.3). It unicasts the RREP back to the node + indicated by the Source IP Address field of the received RREQ. + + A node can respond to a join RREQ only if it is a member of the + multicast tree. If a node receives a multicast route request that + is not a join message, it can reply if it has a current route to the + multicast tree. Otherwise it continues forwarding the request. If a + node receives a join RREQ for a multicast group and it is not already + a member of the multicast tree for that group, it rebroadcasts the + RREQ to its neighbors. + + When a node receives a RREQ for a multicast group which has its own + IP address in the Destination IP address of the IP header, that + means that the source node expects this destination node to be the + multicast group leader. In this case, if the node is in fact not the + group leader, it can simply ignore the RREQ. The source node will + time out after RREP_WAIT_TIME milliseconds and will broadcast a new + RREQ without the group leader address specified. + + + + +Royer, Perkins Expires 15 December 2000 [Page 11] + +Internet Draft Multicast AODV 15 July 2000 + + + Regardless of whether the multicast group leader or a multicast tree + member generates the RREP, the RREP fields are set as follows: + + Hop Count 0 + + Destination IP Address + The IP address of the multicast group. + + Destination Sequence Number + The current multicast group sequence number. + + Lifetime The time for which nodes receiving the RREP consider + the route to be valid (only used it the RREQ is not a + join request). + + The Multicast Group Information extension described in Section 10.3 + is also included for join requests. If the node generating the RREP + is not on the multicast tree (because the RREQ was not a join RREQ), + it places its distance from the multicast tree in the Hop Count + field, instead of 0. + + +9.5. Forwarding Route Replies + + If an intermediate node receives a RREP in response to a RREQ that it + has transmitted (or retransmitted on behalf of some other node), it + creates a multicast group next hop entry for the node from which it + received the RREP. The direction of this next hop is UPSTREAM, and + the Activated flag is left unset. Additionally, the node updates + the Lifetime field in the route table entry associated with the node + from which it received the RREP. It then increments the Hop Count and + Multicast Group Hop Count fields or the RREP and forwards this packet + along the path to the source of the RREQ. + + When the node receives more than one RREP for the same RREQ, it saves + the route information with the greatest sequence number, and beyond + that the lowest hop count; it discards all other RREPs. This node + forwards the first RREP towards the source of the RREQ, and then + forwards later RREPs only if they have a greater sequence number or + smaller metric. + + +9.6. Route Activation + + When a node broadcasts a RREQ message, it is likely to receive more + than one reply since any node in the multicast tree can respond. The + RREP message sets up route pointers as it travels back to the source + node. If the request is a join request, these route pointers may + eventually graft a branch onto the multicast tree. Also, because + + + +Royer, Perkins Expires 15 December 2000 [Page 12] + +Internet Draft Multicast AODV 15 July 2000 + + + multicast data packets may be transmitted as broadcast traffic, the + route to the multicast tree must be explicitly selected. Otherwise, + each node with a route to the tree which receives a multicast data + packet will rebroadcast the packet, resulting in an inefficient use + of network bandwidth. Hence, it is necessary to activate only one + of the routes created by the RREP messages. The RREP containing + the largest destination sequence number is chosen to be the branch + added to the multicast tree (or the path to the multicast tree, if + the request was a non-join). In the event that a node receives more + than one RREP with the same (largest) sequence number, it selects the + first one with the smallest hop count, i.e., the shortest distance to + a member of the multicast tree. + + After waiting RREP_WAIT_TIME milliseconds, the node must select the + route it wishes to use as its link to the multicast tree. This is + accomplished by sending a Multicast Activation (MACT) message. The + Destination IP Address field of the MACT packet is set to the IP + address of the multicast group. If the node is joining the multicast + group, it sets the join flag of this message. The node unicasts this + message to the selected next hop, effectively activating the route. + It then sets the Activated flag in the next hop Multicast Route Table + entry associated with that node. After receiving this message, the + node to which the MACT was sent activates the route entry for the + link in its multicast route table, thereby finalizing the creation of + the tree branch. All neighbors not receiving this message time out + and delete that node as a next hop for the multicast group in their + route tables, having never activated the route entry for that next + hop. + + Two scenarios exist for a neighboring node receiving the MACT + message. If this node was previously a member of the multicast + tree, it does not propagate the MACT message any further. However, + if the next hop selected by the source node's MACT message was not + previously a multicast tree member, it will have propagated the + original RREQ further up the network in search of nodes which are + tree members. Thus it is possible that this node also received more + than one RREP, as noted in Section 9.5. + + When the node receives a MACT selecting it as the next hop, it + unicasts its own MACT to the node it has chosen as its next hop, + and so on up the tree, until a node which was already a part of the + multicast tree is reached. + + +9.7. Multicast Tree Pruning + + A multicast group member can revoke its member status at any time. + However, it can only actually leave the multicast tree if it is not a + tree router for any other nodes in the multicast group (i.e., if it + + + +Royer, Perkins Expires 15 December 2000 [Page 13] + +Internet Draft Multicast AODV 15 July 2000 + + + is a leaf node). If a node wishing to leave the multicast group is + a leaf node, it unicasts to its next hop on the tree a MACT message + with the 'P' flag set and with the Destination IP Address set to the + IP address of the multicast group. It then deletes the multicast + group information for that group from its multicast route table. + When its next hop receives this message, it deletes the sending + node's information from its list of next hops for the multicast tree. + If the removal of the sending node causes this node to become a leaf + node, and if this node is also not a member of the multicast group, + it may in turn prune itself by sending its own MACT message up the + tree. + + When the multicast group leader wishes to leave the multicast group, + it proceeds in a manner similar to the one just described. If it + is a leaf node, it may leave the group and unicast a prune message + to its next hop. The next hop acts in the manner described in + Section 9.10, since the prune message is coming from its upstream + neighbor. Otherwise, if the group leader is not a leaf node, it may + not prune itself from the tree. It takes the actions described in + Section 9.9, where it selects one of its next hops and unicasts to it + the MACT with set 'G' flag. + + +9.8. Repairing a Broken Link + + Branches of the multicast tree become invalid if a broken link + results in an infinite metric being associated with the next hop + route table entry. When a broken link is detected between two nodes + on the multicast tree, the two nodes should delete the link from + their list of next hops for the multicast group. The node downstream + of the break (i.e., the node which is further from the multicast + group leader) is responsible for initiating the repair of the broken + link. In order to repair the tree, the downstream node broadcasts + a RREQ with destination IP address set to the IP address of the + multicast group and with the 'J' flag set. The destination sequence + number of the RREQ is the last known sequence number of the multicast + group. The node also includes the Multicast Group Leader Extension. + The Multicast Group Hop Count field of this extension is set to the + distance of the source node from the multicast group leader. A node + MUST have a hop count to the multicast group leader less than or + equal to the indicated value in order to respond. This hop count + requirement prevents nodes on the same side of the break as the node + initiating the repair from replying to the RREQ. + + The RREQ is broadcast using an expanding rings search, as described + in Section 9.2.1. Because of the high probability that other + nearby nodes can be used to rebuild the route, the original + RREQ is broadcast with a TTL (time to live) field value equal to + TTL_INCREMENT plus the Multicast Group Hop Count. In this way, + + + +Royer, Perkins Expires 15 December 2000 [Page 14] + +Internet Draft Multicast AODV 15 July 2000 + + + the effects of the link breakage may be localized. If no reply + is received within RREP_WAIT_TIME milliseconds, the node SHOULD + increment the TTL of each successive RREQ by TTL_INCREMENT, until + either a route is determined, or TTL_THRESHOLD is reached. After + this point, if a route is still not discovered, each additional RREQ + is broadcast with TTL = NET_DIAMETER. Up to RREQ_RETRIES additional + broadcasts may be attempted after TTL = NET_DIAMETER is reached. + + A node receiving this RREQ can respond if it meets the following + conditions: + + - It is a member of the multicast tree. + + - Its record of the multicast group sequence number is at least as + great as that contained in the RREQ. + + - Its hop count to the multicast group leader is less than or equal + to the contained in the Multicast Group Hop Count extension + field. + + If the originating node receives more than one RREP, route activation + occurs as described in the previous section. + + At the end of the discovery period, the node selects its next hop + and unicasts a MACT message to that node to activate the link, as + described in Section 9.6. Since the node was repairing a tree break, + it is likely that it is now a different distance from the group + leader than it was before the break. If this is the case, it must + inform its DOWNSTREAM next hops of their new distance from the group + leader. It does this by broadcasting a MACT message with the 'U' + flag set, and the Hop Count field set to the node's new distance + from the group leader. This 'U' flag indicates that multicast tree + nodes should update their distance from the group leader. When a + node on the multicast tree receives the MACT message with the 'U' + flag set, it determines whether this packet arrived from its UPSTREAM + neighbor. If it did not, the node discards the packet. Otherwise, + it increments the Hop Count value contained in the MACT packet and + updates it distance to the group leader to be this node value. If + this node has one or more downstream next hops, it in turn must send + a MACT message with a set 'U' flag to its next hops, and so on. + + When a link break occurs, it is possible that the tree will be + repaired through different intermediate nodes. If the node UPSTREAM + of the break is not a group member, and if the loss of that link + causes it to become a leaf node, it sets a prune timer to wait + for the link to be repaired. This PRUNE_TIMEOUT should be larger + than RREP_WAIT_TIMEOUT to give the link time to be repaired. If, + when this timer expires, the node has not received a MACT message + selecting it to be a part of the repaired tree branch, it prunes + + + +Royer, Perkins Expires 15 December 2000 [Page 15] + +Internet Draft Multicast AODV 15 July 2000 + + + itself from the tree by sending a MACT with set 'P' flag to its next + hop, as previously described. + + +9.9. Tree Partitions + + It is possible that after a link breaks, the tree cannot be repaired + due to a network partition. If the node attempting to repair a tree + link break does not receive a response after RREQ_RETRIES attempts, + it can be assumed that the network has become partitioned and the + multicast tree cannot be repaired at this time. In this situation, + if the node which initiated the route rebuilding is a multicast group + member, it becomes the new multicast group leader for its part of the + multicast tree partition. It increments the group sequence number + and then broadcasts a Group Hello (GRPH) for this multicast group. + The 'U' flag in the GRPH is set, indicating that there has been a + change in the group leader information. All nodes receiving this + message update their group leader table to indicate the new group + leader information. Nodes which are a part of the multicast tree + also update the group leader and sequence number information for that + group in their multicast route table. + + On the other hand, if the node which had initiated the repair is not + a multicast group member, there are two possibilities. If it only + has one next hop for the multicast tree, it prunes itself from the + tree by unicasting a MACT message, with the 'P' flag set, to its + next hop. The node receiving this message notes that the message + came from its upstream link, i.e., from a node that is closer to + the group leader than it is. If the node receiving this message + is a multicast group member, it becomes the new group leader and + broadcasts a GRPH message as indicated above. Otherwise, if it is + not a multicast group member and it only has one other next hop link, + it similarly prunes itself from the tree. This process continues + until a multicast group member is reached. + + The other possibility is that the node which initiated the rebuilding + is not a group member and has more than one next hop for the tree. + In this case, it cannot prune itself, since doing so would partition + the tree. It instead selects one of its next hops and unicasts a + MACT with the 'G' flag set to that node. This flag indicates that + the next group member to receive this message should become the new + group leader. It then changes the direction of that link to be + UPSTREAM. If the node receiving the MACT is a group member, then this + node becomes the new group leader. Otherwise, the node unicasts its + own MACT message with the 'G' flag set to one of its next hops, and + changes the direction of that link. Once a group member is reached, + the new group leader is determined. + + + + + +Royer, Perkins Expires 15 December 2000 [Page 16] + +Internet Draft Multicast AODV 15 July 2000 + + +9.10. Reconnecting Two Trees + + In the event that a link break cannot be repaired, the multicast + tree remains partitioned until the two parts of the network become + connected once again. A node from one partition of the network knows + that it has come into contact with a node from the other partition of + the network by noting the difference in the GRPH message multicast + group leader information. The multicast group leader with the lower + IP address initiates the tree repair. For the purposes of this + explanation, call this node GL1. GL1 unicasts a RREQ with both + the 'J' and 'R' flags set to the group leader of the other network + partition (GL2), using the node from which it received the GRPH + as the next hop. This RREQ contains the current value of GL1's + multicast group sequence number. If any node that receives the RREQ + is a member of GL2's multicast tree, it MUST forward the RREQ along + its upstream link, i.e. towards GL2. This prevents any loops from + being formed after the repair. Upon receiving the RREQ, GL2 takes + the larger of its and the received multicast group sequence number, + increments this value by one, and responds with a RREP. This is the + group leader which becomes the leader of the reconnected multicast + tree. The 'R' flag of the RREP is set, indicating that this RREP is + in response to a repair request. + + As the RREP is propagated back to GL1, nodes add the incoming and + outgoing links to the multicast route table next hop entries if + these entries do not already exist. The nodes also activate these + entries, thereby adding the branch on to the multicast tree. If a + node that was previously a member of GL1's tree receives the RREP, it + MUST forward the packet along its link to its previous group leader + (GL1). It then updates its group leader information to reflect GL2 + as the new group leader, changes the direction of the next hop link + associated with GL1 to DOWNSTREAM, and sets the direction of the + link on which it received the RREP to UPSTREAM. When GL1 receives + the RREP, it updates its group leader information and sets the + link from which it received the RREP as its upstream link. The + tree is now reconnected. The next time GL2 broadcasts a GRPH, it + sets the `U' flag to indicate that there is a change in the group + leader information and group members should update the corresponding + information. All network nodes update their group leader table to + reflect the new group leader information. + + +9.11. Maintaining Local Connectivity + + Each node on the multicast tree MUST keep track of its neighbors + which are next hops on the multicast tree. This is done as specified + in [2]. If a link to the next hop cannot be detected by any of the + methods specified therein, the forwarding node MUST assume that the + + + + +Royer, Perkins Expires 15 December 2000 [Page 17] + +Internet Draft Multicast AODV 15 July 2000 + + + link is broken, and take corrective action by following the methods + specified in Section 9.8. + + Whenever the multicast tree is used for the transmission of data + packets, a node on the tree must hear from each of its next hop + neighbors every RETRANSMIT_TIME. The node can hear from its neighbors + through one of the methods previously described, or through the + reception of a rebroadcast of a data packet from these next hops, + if the data packets are being transmitted by broadcast. If a + node does not hear from one of its multicast tree next hops within + RETRANSMIT_TIME, and if the multicast tree is actively being used + to transmit data packets, then the node MUST assume the link to + its next hop is broken, and proceed as described in Section 9.8. + Decreasing the amount of time between when a node must hear from its + next hops from ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds to + RETRANSMIT_TIME allows for the quickest detection of broken links and + fewer data packet losses. + + +9.12. Group Hello Messages + + If a node sends a RREQ to join a multicast group (`J' flag set) + and after RREQ_RETRIES attempts does not receives a response, it + then becomes the multicast group leader. The node initializes the + multicast group sequence number and then broadcasts a GRPH message + to inform network nodes that it is now the group leader for the + multicast group. To ensure nodes maintain consistent and up-to-date + information about who the multicast group leaders are, any node which + is a group leader for a multicast group broadcasts such a GRPH across + the network every GROUP_HELLO_INTERVAL milliseconds. The contents of + the GRPH fields are set as follows: + + U Flag 0 + + M Flag 0 + + Hop Count 0 + + Group Leader IP Address + The IP Address of the group leader. + + Multicast Group IP Address + The IP Address of the Multicast Group for which the + node is the group leader. + + Multicast Group Sequence Number + One plus the last known sequence number of the + multicast group. + + + + +Royer, Perkins Expires 15 December 2000 [Page 18] + +Internet Draft Multicast AODV 15 July 2000 + + + Nodes receiving the GRPH increment the Hop Count field by one before + forwarding the message. When a node not on the multicast tree + receives the GRPH message, it sets the 'M' flag. This indicates that + this incarnation of the message has traveled off the multicast tree, + and hence cannot be used by group members to verify their distance + from the group leader. The 'U' flag is set by the group leader + whenever there has been a change in group leader information. It + informs nodes that they should update the group leader information + associated with the indicated multicast group. + + A node receiving the GRPH message first verifies that is has + not already received the GRPH message with the same group IP + address/group sequence number pair in the last BCAST_ID_SAVE + milliseconds. If it has, it silently discards the message. + Otherwise, the node updates its group leader table to reflect + the current multicast group IP address/group leader IP address + combination, and increments the Hop Count value in the message. If + the node receiving the GRPH message is a member of the multicast + tree, it also updates this information in its multicast route table. + If the 'M' flag is unset, then this node can also use the Hop Count + value to verify its current distance from the group leader. + + After processing the GRPH message, the node buffers the group + IP address/ group sequence number combination to avoid multiple + processings of the same GRPH message. It then rebroadcasts the + message to its neighbors. + + +9.13. Actions After Reboot + + A node participating in the multicast tree that reboots (or + restarts the routing daemon) loses all of its multicast tree + information. Upon reboot, the rebooted node does not know whether + it was previously a member of the multicast tree. Hence, it should + unconditionally broadcast a MACT message with set Reboot ('R') flag + to inform neighboring nodes that it has lost its multicast group + information. When a node on the multicast tree receives the reboot + MACT message, it checks whether this message came from one of its + next hops on the multicast tree. If so, one of two situations + exists. + + If the reboot MACT came from a downstream link, the node deletes that + link from its list of next hops and sets a prune timer according to + the guidelines in Section 9.8. Otherwise, if the reboot MACT came + from a node's upstream link, it must rebuild the tree branch as is + also indicated in Section 9.8. + + + + + + +Royer, Perkins Expires 15 December 2000 [Page 19] + +Internet Draft Multicast AODV 15 July 2000 + + +9.14. Interfaces + + Because MAODV should operate smoothly over wired, as well as + wireless, networks, and because it is likely that MAODV will also be + used with multi-homed radios, the interface over which packets arrive + must be known to MAODV whenever a packet is received. This includes + the reception of RREQ, RREP, MACT, and GRPH messages. Whenever a + packet is received from a new neighbor, the interface on which that + packet was received is recorded into the route table entry for that + neighbor, along with all the other appropriate routing information. + Similarly, whenever a route to a new destination is learned, the + interface through which the destination can be reached is also + recorded into the destination's route table entry. + + When multiple interfaces are available, a node receiving and + rebroadcasting a RREQ or GRPH message rebroadcasts that message on + all interfaces except the one on which it was received. If a node is + participating on the multicast tree, and if multicast data packets + are being sent as broadcast traffic, a multicast tree node should + only rebroadcast a packet on those interfaces which have multicast + tree next hops. + + +10. Extensions + + This section specifies for multicast extensions for RREQ and RREP + messages, conforming to the format defined in [2]. + + +10.1. Multicast Group Leader Extension Format + + This extension is appended to a RREQ by a node wishing to repair a + multicast tree. + + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Type | Length | Multicast Group Leader IP ... | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | ... Address (continued) | Previous Hop IP Address ... | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | ... (continued) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Type 3 + + Length 8 + + + + + +Royer, Perkins Expires 15 December 2000 [Page 20] + +Internet Draft Multicast AODV 15 July 2000 + + + Multicast Group Leader IP Address + The IP Address of the Multicast Group Leader. + + Previous Hop IP Address + The IP Address of the node which previously received the + RREQ. This field is used when the RREQ is unicast to + the group leader when a node wishes to join a multicast + group. + + This extension is used when unicasting the RREQ to the group leader. + Each node receiving the RREQ updates the Previous Hop IP Address + field to reflect its address. + + +10.2. Multicast Group Rebuild Extension Format + + This extension is appended to a RREQ by a node wishing to repair a + multicast tree. + + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Type | Length | Multicast Group Hop Count | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Type 4 + + Length 2 + + Multicast Group Hop Count + The distance in hops of the node sending the RREQ from + the Multicast Group Leader. + + This extension is used for rebuilding a multicast tree branch. It is + used to ensure that only nodes as least as close to the group leader + as indicated by the Multicast Group Hop Count field respond to the + request. + + +10.3. Multicast Group Information Extension Format + + The following extension is used to carry additional information for + the RREP message (see Section 6) when sent to establish a route to a + multicast destination. + + + + + + + + +Royer, Perkins Expires 15 December 2000 [Page 21] + +Internet Draft Multicast AODV 15 July 2000 + + + + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Type | Length | Multicast Group Hop Count | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Multicast Group Leader IP Address | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + + Type 5 + + Length 6 + + Multicast Group Hop Count + The distance of the node from the Multicast Group Leader. + + Multicast Group Leader IP Address + The IP Address of the current Multicast Group Leader. + + This extension is included when responding to a RREQ to join a + multicast group. The node responding to the RREQ places its distance + from the group leader in the Multicast Group Hop Count field. + + +11. Configuration Parameters + + This section gives default values for some important values + associated with MAODV protocol operations. A particular mobile node + may wish to change certain of the parameters, in particular the + NET_DIAMETER, MY_ROUTE_TIMEOUT, ALLOWED_HELLO_LOSS, RREQ_RETRIES, + and possibly the HELLO_INTERVAL. In the latter case, the node should + advertise the HELLO_INTERVAL in its Hello messages, by appending + a Hello Interval Extension to the RREP message. Choice of these + parameters may affect the performance of the protocol. + + + + + + + + + + + + + + + + + +Royer, Perkins Expires 15 December 2000 [Page 22] + +Internet Draft Multicast AODV 15 July 2000 + + + + Multicast Parameters Value + ---------------------- ----- + GROUP_HELLO_INTERVAL 5,000 Milliseconds + MTREE_BUILD 2 * REV_ROUTE_LIFE + PRUNE_TIMEOUT ACTIVE_ROUTE_TIMEOUT + RETRANSMIT_TIME 750 Milliseconds + + + Additional AODV Parameters + -------------------------- + ACTIVE_ROUTE_TIMEOUT + ALLOWED_HELLO_LOSS + BCAST_ID_SAVE + DELETE_PERIOD + HELLO_INTERVAL + NET_DIAMETER + NEXT_HOP_WAIT + NODE_TRAVERSAL_TIME + REV_ROUTE_LIFE + RREP_WAIT_TIME + RREQ_RETRIES + TTL_START + TTL_INCREMENT + TTL_THRESHOLD + + + + Please see [2] for a discussion of and the appropriate values for the + Additional AODV Parameters. + + +12. Security Considerations + + Currently, MAODV does not specify any special security measures. + Route protocols, however, are prime targets for impersonation + attacks, and must be protected by use of authentication techniques + involving generation of unforgeable and cryptographically strong + message digests or digital signatures. It is expected that, in + environments where security is an issue, that IPSec authentication + headers will be deployed along with the necessary key management to + distribute keys to the members of the ad hoc network using MAODV. + + + + + + + + + + +Royer, Perkins Expires 15 December 2000 [Page 23] + +Internet Draft Multicast AODV 15 July 2000 + + +References + + [1] S. Bradner. Key words for use in RFCs to Indicate Requirement + Levels. Request for Comments (Best Current Practice) 2119, + Internet Engineering Task Force, Mar. 1997. + + [2] C. Perkins, E. Royer, and S. Das. Ad hoc on demand distance + vector (AODV) routing (work in progress). Internet Draft, + Internet Engineering Task Force, Mar. 2000. + + [3] C. E. Perkins. Terminology for Ad-Hoc Networking (work in + progress). draft-ietf-manet-terms-00.txt, Nov. 1997. + + +Author's Addresses + + Questions about this memo can be directed to: + + Elizabeth M. Royer + Dept. of Electrical and Computer Engineering + University of California, Santa Barbara + Santa Barbara, CA 93106 + +1 805 893 7788 + +1 805 893 3262 (fax) + eroyer@alpha.ece.ucsb.edu + + + Charles E. Perkins + Communications Systems Laboratory + Nokia Research Center + 313 Fairchild Drive + Mountain View, CA 94303 + USA + +1 650 625 2986 + +1 650 691 2170 (fax) + charliep@iprg.nokia.com + + + + + + + + + + + + + + + + +Royer, Perkins Expires 15 December 2000 [Page 24] diff -urN ./aodv-uu-0.6/igmp.c ./maodv-umd/igmp.c --- ./aodv-uu-0.6/igmp.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/igmp.c Mon Feb 24 12:38:51 2003 @@ -0,0 +1,134 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifdef NS_PORT +#include "aodv-uu.h" +#else +#include +#include "aodv_socket.h" +#include "params.h" +#include "seek_list.h" +#include "defs.h" +#include "debug.h" +#include "multicast_routing_table.h" +#include "igmp.h" +#include "aodv_rreq.h" +#include "maodv_mact.h" +#include "packet_queue.h" +#endif + +static void maodv_join(u_int32_t grp_addr){ + mrt_table_t *group_rec; + + group_rec=mrt_table_find(grp_addr); + + if(group_rec==NULL){ + group_rec=mrt_table_insert(grp_addr, 0, 0, 0, 255, 0); + } + + if(!group_rec->is_router){ + /* no route to group, so let's find one. */ + rreq_route_discovery(grp_addr, RREQ_JOIN, NULL, 0); + }else if(!group_rec->is_member){ + /* I'm routing, so I just need to reactivate my membership */ + group_rec->is_member=1; + } +} + +static void maodv_leave(u_int32_t grp_addr){ + mrt_table_t *group_rec; + + group_rec=mrt_table_find(grp_addr); + + /* don't leave if not in the group */ + if(group_rec==NULL || !group_rec->is_router) + return; + + /* leave group */ + group_rec->is_member=0; + + if(group_rec->am_leader){ + if(group_rec->activated_downstream_cnt>0){ + /* do have downstreams, so make one new leader */ + mact_make_downstream_leader(group_rec); + } + group_rec->am_leader=0; + mrt_table_stop_routing(group_rec); + }else if(group_rec->activated_downstream_cnt==0){ + /* no downs, prune self and invalidate route */ + mrt_nexthop_t *upstream; + + upstream=mrt_table_get_activated_upstream(group_rec); + if(upstream != NULL){ + mact_send(MACT_PRUNE, 1, grp_addr, upstream->addr,1); + mrt_nexthop_deactivate(group_rec, upstream->addr); + } + mrt_table_stop_routing(group_rec); + + /* remove any pending RREQs (or other packets) for this group */ + seek_list_remove(grp_addr); + packet_queue_drop(grp_addr); + + /* flush all nexthops */ + mrt_nexthop_remove_all(group_rec); + } + /* otherwise I must keep route valid so I keep routing */ +} + +void igmp_process( IGMP *pkt ) +{ + u_int32_t grp_addr; + DEBUG(LOG_DEBUG, 0, "IGMP packet out. Dropped."); + + grp_addr=ntohl(pkt->igmp_group.s_addr); + + switch( pkt->igmp_type ) { + case IGMP_V1_MEMBERSHIP_REPORT: + case IGMP_V2_MEMBERSHIP_REPORT: + DEBUG(LOG_DEBUG, 0, "IGMP_REPORT"); + + /* may not do anything if we already have a valid route. */ + maodv_join( grp_addr ); + + break; + case IGMP_V2_LEAVE_GROUP: + DEBUG(LOG_DEBUG, 0, "IGMP_LEAVE"); + + /* it may not actually prune, but at least un-member me. */ + maodv_leave( grp_addr ); + + break; + case IGMP_MEMBERSHIP_QUERY: + DEBUG(LOG_DEBUG, 0, "IGMP_QUERY"); + break; + default: + DEBUG(LOG_DEBUG, 0, "IGMP_UNKNOWN [0x%x]", pkt->igmp_type ); + break; + } +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/igmp.h ./maodv-umd/igmp.h --- ./aodv-uu-0.6/igmp.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/igmp.h Mon Feb 24 12:38:51 2003 @@ -0,0 +1,44 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef IGMP_H +#define IGMP_H + +#ifndef NS_NO_GLOBALS + +#include "defs.h" +#include + +#define IGMP struct igmp + +#endif /* NS_NO_GLOBALS */ + +#ifndef NS_NO_DECLARATIONS + +void igmp_process( IGMP * buff ); + +#endif /* NS_NO_DECLARATIONS */ + +#endif /* IGMP_H */ diff -urN ./aodv-uu-0.6/k_mroute.c ./maodv-umd/k_mroute.c --- ./aodv-uu-0.6/k_mroute.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/k_mroute.c Mon Feb 24 12:38:51 2003 @@ -0,0 +1,222 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#include "k_mroute.h" +#include /* perror */ +#include +#include +#include +#include + +/* Yanked from debug.h during a battle with the includes. */ +#include +void log(int, int, const char *, char *, ...); + +int multicast_socket; + +/* much of this code was taken from Dinesh's kernel MAODV + implementation and cleaned up for user space. + + also, smc_route v.0.92 provided a good user space reference. */ + +/* + * kernel_mrt_init( ) + * Create and initialize the multicast socket for communication with the kernel. + */ +int kernel_mrt_init( void ) +{ + int error; + int enable = 1; + + multicast_socket = socket( AF_INET, SOCK_RAW, IPPROTO_IGMP ); + + /* error creating socket? */ + if ( multicast_socket < 0 ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Failed to create socket."); + return -1; + } + + error = setsockopt( multicast_socket, IPPROTO_IP, MRT_INIT, + (int *) &enable, sizeof( enable ) ); + if ( error < 0 ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Error starting kernel multicast routing."); + return -1; + } + + log(LOG_DEBUG, 0, __FUNCTION__, + "Got the multicast kernel route socket!"); + + return 0; +} + +/* + * kernel_mrt_clean_up( ) + * Close the socket and clean up the virtual interfaces. + */ +int kernel_mrt_clean_up( void ) +{ + int error = setsockopt( multicast_socket, IPPROTO_IP, MRT_DONE, + (char *) NULL, 0 ); + if ( error < 0 ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Error finishing (MRT_DONE) kernel multicast routing."); + return -1; + } + + close( multicast_socket ); + + log(LOG_DEBUG, 0, __FUNCTION__, + "Killed multicast socket!"); + + return 0; +} + +/* + * kernel_mrt_vif_add( addr, index ) + * Adds a virtual interface from ip "addr" as index "index". + */ +int kernel_mrt_vif_add( u_int32_t this_ip, int index ) +{ + struct vifctl vc; + int error; + + /* taken from smcroute-0.92 */ + vc.vifc_vifi = index; + vc.vifc_flags = 0; + vc.vifc_threshold = 1; + vc.vifc_rate_limit = 0; + + vc.vifc_lcl_addr.s_addr = htonl(this_ip); + vc.vifc_rmt_addr.s_addr = INADDR_ANY; + + error = setsockopt( multicast_socket, IPPROTO_IP, MRT_ADD_VIF, + (char *)&vc, sizeof(vc) ); + if ( error < 0 ) { + perror("ERROR! " ); + log(LOG_WARNING, 0, __FUNCTION__, + "Error creating virtual interface for kernel multicast routing[%d]." , error ); + return -1; + } + + log(LOG_DEBUG, 0, __FUNCTION__, + "Added virtual interface."); + + return 0; +} + +/* + * kernel_mrt_vif_del( addr, index ) + * Deletes a virtual interface at from ip "addr" as index "index". + */ +int kernel_mrt_vif_del( u_int32_t this_ip, int index ) +{ + struct vifctl vc; + int error; + + vc.vifc_vifi = (vifi_t) index; + vc.vifc_flags = 0; + // Is the threshold value 0 or 1??? - Dinesh + vc.vifc_threshold = 0; + vc.vifc_rate_limit = 0; + + vc.vifc_lcl_addr.s_addr = htonl(this_ip); + vc.vifc_rmt_addr.s_addr = INADDR_ANY; + + error = setsockopt( multicast_socket, IPPROTO_IP, MRT_DEL_VIF, + (char *)&vc, sizeof(vc) ); + if ( error < 0 ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Error deleting virtual interface for kernel multicast routing."); + return -1; + } + + return 0; +} + +/* + * kernel_mrt_add_route( source, grp, vif ) + * Add a multicast route to the kernel routing cache. + */ +int kernel_mrt_add_route( u_int32_t src, u_int32_t grp, int index ) +{ + struct mfcctl mc; + int error; + + mc.mfcc_origin.s_addr = htonl(src); + mc.mfcc_mcastgrp.s_addr = htonl(grp); + mc.mfcc_parent = (vifi_t) index; + mc.mfcc_ttls[index] = 2; /* CHECK: this seems odd... */ + + error = setsockopt( multicast_socket, IPPROTO_IP, MRT_ADD_MFC, + (char *) ( &mc ), sizeof( mc ) ); + + if ( error < 0 ) { + perror( "ERROR " ); + log(LOG_WARNING, 0, __FUNCTION__, + "Error adding route for kernel multicast routing."); + return -1; + } + + log(LOG_DEBUG, 0, __FUNCTION__, + "Added multicast route cache entry."); + + return 0; +} + +/* + * kernel_mrt_del_route( source, grp, vif ) + * Delete a multicast route from the kernel routing cache. + */ +int kernel_mrt_del_route( u_int32_t src, u_int32_t grp, int index ) +{ + struct mfcctl mc; + int error; + + /* CHECK: ttls are diff in Dinesh's code... intentional? */ + mc.mfcc_origin.s_addr = htonl(src); + mc.mfcc_mcastgrp.s_addr = htonl(grp); + mc.mfcc_parent = (vifi_t) index; + mc.mfcc_ttls[index] = 1; + + error = setsockopt( multicast_socket, IPPROTO_IP, MRT_DEL_MFC, + (char *) ( &mc ), sizeof( struct mfcctl ) ); + + if ( error < 0 ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Error deleting route for kernel multicast routing."); + return -1; + } + + log(LOG_DEBUG, 0, __FUNCTION__, + "Removed multicast route cache entry."); + + return 0; +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/k_mroute.h ./maodv-umd/k_mroute.h --- ./aodv-uu-0.6/k_mroute.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/k_mroute.h Mon Feb 24 12:38:52 2003 @@ -0,0 +1,38 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef K_MROUTE_H +#define K_MROUTE_H + +#include + +int kernel_mrt_init( void ); +int kernel_mrt_clean_up( void ); +int kernel_mrt_vif_add( u_int32_t this_ip, int index ); +int kernel_mrt_vif_del( u_int32_t this_ip, int index ); +int kernel_mrt_add_route( u_int32_t src, u_int32_t grp, int index ); +int kernel_mrt_del_route( u_int32_t src, u_int32_t grp, int index ); + +#endif /* K_MROUTE_H */ diff -urN ./aodv-uu-0.6/macs ./maodv-umd/macs --- ./aodv-uu-0.6/macs Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/macs Thu Jan 16 13:10:32 2003 @@ -0,0 +1,4 @@ +PEANUT="00:02:2D:75:F8:CC" +PINKEYE="00:02:2D:4F:73:68" +MAGGIE="00:02:2D:76:08:8A" +HUMMUS="00:02:2D:57:AD:FC" diff -urN ./aodv-uu-0.6/main.c ./maodv-umd/main.c --- ./aodv-uu-0.6/main.c Wed Nov 6 08:48:46 2002 +++ ./maodv-umd/main.c Fri Feb 21 17:43:58 2003 @@ -42,6 +42,11 @@ #include "aodv_hello.h" #include "packet_input.h" #include "packet_queue.h" +#ifdef MAODV +#include "multicast_routing_table.h" +#include "multicast_packet_cache.h" +#include "k_mroute.h" +#endif #ifdef USE_IW_SPY #include "link_qual.h" @@ -58,7 +63,7 @@ int receive_n_hellos = 0; int hello_jittering = 1; int optimized_hellos = 0; -int ratelimit = 1; /* Option for rate limiting RREQs and RERRs. */ +int ratelimit = 0; /* Option for rate limiting RREQs and RERRs. */ char *progname; int wait_on_reboot = 1; int hello_qual_threshold = 12; @@ -411,6 +416,12 @@ DEV_IFINDEX(ifreq.ifr_ifindex).ipaddr = ntohl(ina->sin_addr.s_addr); + #ifdef MAODV + /* CHECK */ + kernel_mrt_vif_add( DEV_IFINDEX(ifreq.ifr_ifindex).ipaddr, 0 ); + + #endif + /* Get netmask of interface... */ ina = get_if_info(iface, SIOCGIFNETMASK); if (ina == NULL) @@ -593,12 +604,21 @@ /* Initialize data structures and services... */ log_init(); +#ifdef MAODV + kernel_mrt_init( ); +#endif + host_init(ifname); timer_queue_init(); rt_table_init(); +#ifdef MAODV + mrt_table_init(); + init_packet_cache(); +#endif packet_queue_init(); packet_input_init(); aodv_socket_init(); + #ifdef USE_IW_SPY if (spy_addrs) link_qual_init(spy_addrs); @@ -671,6 +691,13 @@ system("/sbin/route del default"); remove_modules(); rt_table_destroy(); +#ifdef MAODV + mrt_table_destroy(); + + /* CHECK: What interface? should we cycle through and fins a nice interface? */ + kernel_mrt_vif_del( DEV_IFINDEX(0).ipaddr, 0 ); + kernel_mrt_clean_up(); +#endif packet_input_cleanup(); aodv_socket_cleanup(); #ifdef USE_IW_SPY diff -urN ./aodv-uu-0.6/maodv_ext.h ./maodv-umd/maodv_ext.h --- ./aodv-uu-0.6/maodv_ext.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_ext.h Mon Feb 24 12:38:52 2003 @@ -0,0 +1,98 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef MAODV_EXT_H +#define MAODV_EXT_H + +#ifndef NS_NO_GLOBALS +#include + +#include "defs.h" + +typedef struct _grp_leader_ext_t { + u_int8_t type; + u_int8_t length; + u_int32_t grp_leader_addr; + u_int32_t prev_hop_addr; +} grp_leader_ext; + +typedef struct _grp_rebuild_ext_t { + u_int8_t type; + u_int8_t length; + u_int16_t grp_hcnt; +} grp_rebuild_ext; + +typedef struct _grp_info_ext_t { + u_int8_t type; + u_int8_t length; + u_int32_t grp_hcnt; + u_int32_t grp_leader_addr; +} grp_info_ext; + +/* See note below. */ +typedef struct _grp_merge_ext_t { + u_int8_t type; + u_int8_t length; + u_int16_t res; + u_int32_t grp_addr; + u_int32_t grp_seqno; +} grp_merge_ext; + +#define GRP_LEADER_EXT (grp_leader_ext) +#define GRP_LEADER_EXT_SIZE ( sizeof(GRP_LEADER_EXT) ) +#define GLE_TYPE ( 3 ) + /* 2 = size of header */ +#define GLE_LENGTH (GRP_LEADER_EXT_SIZE - 2) + +#define GRP_REBUILD_EXT grp_rebuild_ext +#define GRP_REBUILD_EXT_SIZE ( sizeof(GRP_REBUILD_EXT) ) +#define GRE_TYPE ( 4 ) + /* 2 = size of header */ +#define GRE_LENGTH (GRP_REBUILD_EXT_SIZE - 2) + +#define GRP_INFO_EXT (grp_info_ext) +#define GRP_INFO_EXT_SIZE ( sizeof(GRP_INFO_EXT) ) +#define GIE_TYPE ( 5 ) + /* 2 = size of header */ +#define GIE_LENGTH (GRP_INFO_EXT_SIZE - 2) + +/* NOTE: This is a non-standard extension. The draft is + unclear about the tree merge process. We have created + a new extension for our tree merge. The type number + was chosen in an attempt to avoid collisions with any + future extensions. */ +#define GRP_MERGE_EXT grp_merge_ext +#define GRP_MERGE_EXT_SIZE ( sizeof(GRP_MERGE_EXT) ) +#define GME_TYPE ( 9 ) + /* 2 = size of header */ +#define GME_LENGTH (GRP_MERGE_EXT_SIZE - 2) + +#endif /* NS_NO_GLOBALS */ + +#ifndef NS_NO_DECLARATIONS + +#endif /* NS_NO_DECLARATIONS */ + +#endif /* MAODV_MACT_H */ diff -urN ./aodv-uu-0.6/maodv_grph.c ./maodv-umd/maodv_grph.c --- ./aodv-uu-0.6/maodv_grph.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_grph.c Mon Feb 24 12:38:52 2003 @@ -0,0 +1,218 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifdef NS_PORT +#include "aodv-uu.h" +#else +#include +#include "maodv_grph.h" +#include "aodv_socket.h" +#include "params.h" +#include "seek_list.h" +#include "defs.h" +#include "debug.h" +#include "multicast_routing_table.h" +#include "aodv_rreq.h" +#endif + +GRPH *grph_create(u_int8_t flags, u_int8_t hcnt, u_int32_t grp_leader_addr, u_int32_t grp_addr, u_int32_t grp_seqno) +{ + GRPH *grph; + + grph=(GRPH *)aodv_socket_new_msg(); + + grph->type=MAODV_GRPH; + grph->res1=0; + grph->res2=0; + grph->hcnt=hcnt; + grph->grp_leader_addr=htonl(grp_leader_addr); + grph->grp_addr=htonl(grp_addr); + grph->grp_seqno=htonl(grp_seqno); + + if(flags & GRPH_UPDATE) + grph->u=1; + if(flags & GRPH_OFFMTREE) + grph->o=1; + + DEBUG(LOG_DEBUG, 0, "Assembled GRPH %s", ip_to_str(grp_addr)); + if(grph->u){ + DEBUG(LOG_DEBUG, 0, "GRPH->u set"); + } + + return grph; +} + +void grph_send(u_int8_t flags, u_int8_t hcnt, u_int32_t grp_addr, u_int32_t grp_seqno) +{ + GRPH *grph; + int i; + /* ttl is one, packets get rebroadcast at each step */ + int ttl = NET_DIAMETER; + + for(i=0; igrp_addr))); + + grph->hcnt++; + for(i=0; igrp_addr))); + + upstream=mrt_table_get_activated_upstream(mrt); + if(upstream != NULL){ + rt=rt_table_find(upstream->addr); + grph->hcnt++; + grph = (GRPH *) aodv_socket_queue_msg((AODV_msg *) grph, GRPH_SIZE); + aodv_socket_send((AODV_msg *)grph, upstream->addr, GRPH_SIZE, ttl, &DEV_IFINDEX(rt->ifindex)); + } +} + +void grph_process(GRPH *grph, u_int32_t src_addr, int ttl) +{ + mrt_table_t *mrt; + u_int32_t grp_addr; + u_int32_t grp_leader_addr; + u_int32_t grp_seqno; + int do_forward=0, do_forward_ucast=0; + u_int8_t new_hcnt; + + grp_addr=ntohl(grph->grp_addr); + grp_leader_addr=ntohl(grph->grp_leader_addr); + grp_seqno=ntohl(grph->grp_seqno); + new_hcnt=grph->hcnt+1; + + mrt=mrt_table_find(grp_addr); + if(mrt==NULL){ + mrt=mrt_table_insert(grp_addr, grp_leader_addr, grp_seqno, 0, new_hcnt, 0); + do_forward=1; + } + + if(mrt->is_router){ + mrt_nexthop_t *upstream; + upstream=mrt_table_get_activated_upstream(mrt); + + /* group leader doens't need to process grph */ + /* nor do I care about offmtree packets if I'm on the tree */ + if(mrt->am_leader){ + if(mrt->grp_leader_addr != grp_leader_addr){ + /* initiate tree merge */ + /* Check IP's */ + if ( ( mrt->grp_leader_addr < grp_leader_addr ) && + ( !mrt->in_repair ) ){ + /* my IP is less than his ;( */ + /* initiate route discovery with all the flags */ + DEBUG(LOG_DEBUG, 0, "Initiating tree merge for %s.", ip_to_str(grp_addr)); + + mrt->in_repair = 1; + rreq_route_discovery( grp_leader_addr, + RREQ_JOIN | RREQ_REPAIR | RREQ_DEST_ONLY, + NULL, mrt->grp_addr ); + } + } + }else if(!grph->o){ + if(upstream != NULL && src_addr==upstream->addr){ + mrt->leader_hcnt=new_hcnt; + mrt->grp_seqno=grp_seqno; + + if(grph->u || mrt->grp_leader_addr!=grp_leader_addr){ + mrt_table_set_leader(mrt, grp_leader_addr, new_hcnt); + } + do_forward=1; + } + } + + if(!mrt->am_leader && grp_leader_addr != mrt->grp_leader_addr){ + /* if you get a grph for a different leader.... */ + /* unicast it to your upstream */ + do_forward_ucast=1; + } + }else{ + /* if not on the tree, you can be less discriminating about + your information */ + grph->o=1; + /* potential method for forwarding grph */ + if(grp_seqno>mrt->grp_seqno || + (grp_seqno==mrt->grp_seqno && new_hcntleader_hcnt)){ + do_forward=1; + } + if(mrt->grp_leader_addr!=grp_leader_addr || + (mrt->grp_leader_addr==grp_leader_addr && new_hcntleader_hcnt)){ + mrt_table_set_leader(mrt, grp_leader_addr, new_hcnt); + do_forward=1; + } + /* and finally update our sequence number */ + mrt->grp_seqno=grp_seqno; + + } + + if(do_forward && ttl>1){ + grph_forward(grph, --ttl); + } + + if(do_forward_ucast && ttl>1){ + grph_forward_ucast(mrt, grph, --ttl); + } +} + +void grph_send_callback(mrt_table_t *mrt){ + int flags=0; + if(mrt->grph_update_cnt>0){ + flags=GRPH_UPDATE; + mrt->grph_update_cnt--; + } + if(mrt->am_leader){ + grph_send(flags, 0, mrt->grp_addr, ++mrt->grp_seqno); + + timer_set_timeout(&(mrt->grph_timer), GROUP_HELLO_INTERVAL); + } +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/maodv_grph.h ./maodv-umd/maodv_grph.h --- ./aodv-uu-0.6/maodv_grph.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_grph.h Mon Feb 24 12:38:52 2003 @@ -0,0 +1,84 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef MAODV_GRPH_H +#define MAODV_GRPH_H + +#ifndef NS_NO_GLOBALS +#include + +#include "defs.h" +#include "multicast_routing_table.h" + +/* GRPH Flags: */ +#define GRPH_UPDATE 0x2 +#define GRPH_OFFMTREE 0x1 + +typedef struct _grph_t { + u_int8_t type; +# if __BYTE_ORDER == __LITTLE_ENDIAN + u_int8_t res1:6; + u_int8_t o:1; + u_int8_t u:1; +# elif __BYTE_ORDER == __BIG_ENDIAN + u_int8_t u:1; + u_int8_t o:1; + u_int8_t res1:6; +# else +# error "Adjust your defines" +# endif + u_int8_t res2; + u_int8_t hcnt; + u_int32_t grp_leader_addr; + u_int32_t grp_addr; + u_int32_t grp_seqno; +} grph_t; + +#define GRPH grph_t +#define GRPH_SIZE sizeof(grph_t) + +#endif /* NS_NO_GLOBALS */ + +#ifndef NS_NO_DECLARATIONS +GRPH *grph_create(u_int8_t flags, + u_int8_t hcnt, + u_int32_t grp_leader_addr, + u_int32_t grp_addr, + u_int32_t grp_seqno); + +void grph_send(u_int8_t flags, + u_int8_t hcnt, + u_int32_t grp_addr, + u_int32_t grp_seqno); + +void grph_forward(GRPH * GRPH, int ttl); + +void grph_process(GRPH * GRPH, u_int32_t src, int ttl); + +void grph_send_callback(mrt_table_t *mrt); + +#endif /* NS_NO_DECLARATIONS */ + +#endif /* MAODV_GRPH_H */ diff -urN ./aodv-uu-0.6/maodv_mact.c ./maodv-umd/maodv_mact.c --- ./aodv-uu-0.6/maodv_mact.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_mact.c Mon Feb 24 12:38:52 2003 @@ -0,0 +1,293 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifdef NS_PORT +#include "aodv-uu.h" +#else +#include +#include "maodv_mact.h" +#include "maodv_grph.h" +#include "aodv_socket.h" +#include "params.h" +#include "seek_list.h" +#include "defs.h" +#include "debug.h" +#include "multicast_routing_table.h" +#include "packet_queue.h" +#endif + +MACT *mact_create(u_int8_t flags, u_int8_t hcnt, u_int32_t src_addr, + u_int32_t grp_addr) +{ + MACT *mact; + + mact=(MACT *)aodv_socket_new_msg(); + + mact->type=MAODV_MACT; + mact->res1=0; + mact->res2=0; + mact->hcnt=hcnt; + mact->grp_addr=htonl(grp_addr); + mact->src_addr=htonl(src_addr); + mact->src_seqno=htonl(++this_host.seqno); + + /* handle flags */ + if(flags & MACT_JOIN) + mact->j=1; + if(flags & MACT_PRUNE) + mact->p=1; + if(flags & MACT_GRPL) + mact->g=1; + if(flags & MACT_UPDATE) + mact->u=1; + if(flags & MACT_REBOOT) + mact->r=1; + + DEBUG(LOG_DEBUG, 0, "Assembled MACT %s", ip_to_str(grp_addr)); + + return mact; +} + +void mact_send(u_int8_t flags, u_int8_t hcnt, u_int32_t grp_addr, u_int32_t dst_addr, int ttl) +{ + MACT *mact; + rt_table_t *route; + int i; + + route=rt_table_find(dst_addr); + i=route->ifindex; + mact=mact_create(flags, hcnt, DEV_IFINDEX(i).ipaddr, grp_addr); + + aodv_socket_send((AODV_msg *)mact, dst_addr, MACT_SIZE, ttl, &DEV_IFINDEX(i)); +} + +void mact_mcast(u_int8_t flags, u_int8_t hcnt, u_int32_t grp_addr, int ttl) +{ + MACT *mact; + mrt_table_t *group_rec; + mrt_nexthop_t *nexthop; + rt_table_t *route; + /* prevent sending packet twice on an iface */ + static char ifmask[MAX_NR_INTERFACES]; + int i; + + bzero(ifmask, sizeof(ifmask)*sizeof(char)); + + group_rec=mrt_table_find(grp_addr); + nexthop=group_rec->nexthops; + + /* an attempt to send multicast packets right. + * destination is group address + * only send one per interface you are currently multicasting to group on + */ + while(nexthop!=NULL) { + route=rt_table_find(nexthop->addr); + i=route->ifindex; + if (!DEV_IFINDEX(i).enabled) + continue; + if (!ifmask[i]) { + mact=mact_create(flags, hcnt, DEV_IFINDEX(i).ipaddr, grp_addr); + aodv_socket_send((AODV_msg *)mact, grp_addr, MACT_SIZE, ttl, &DEV_IFINDEX(i)); + ifmask[i]=1; + } + nexthop=nexthop->next; + } +} + +void mact_process(MACT *mact) +{ + u_int32_t src_addr, grp_addr, src_seqno; + u_int8_t hcnt; + mrt_table_t *group_rec; + + src_addr=ntohl(mact->src_addr); + grp_addr=ntohl(mact->grp_addr); + src_seqno=ntohl(mact->src_seqno); + hcnt=mact->hcnt; + + group_rec=mrt_table_find(grp_addr); + + if(group_rec == NULL) { + /* shouldn't happen */ + return; + } + + if(mact->j) { + /* JOIN */ + /* sender wants to join specified group with us as next hop. + * if we are already in group, then fine, else need to + * pseudo-join ourselves. + */ + mrt_nexthop_t *nh; + + nh=mrt_nexthop_find(group_rec, src_addr); + if(nh==NULL){ + nh=mrt_nexthop_add(group_rec, src_addr, MRT_DOWNSTREAM, src_seqno); + } + if(nh->activated){ + mrt_nexthop_deactivate(group_rec, nh->addr); + } + if ( nh->direction==MRT_UPSTREAM) { + nh->direction=MRT_DOWNSTREAM; + } + mrt_nexthop_activate(group_rec, src_addr); + DEBUG(LOG_DEBUG, 0, "activated downstream %s", ip_to_str(src_addr)); + + /* check if we are not leader and yet have no upstream*/ + if(!group_rec->am_leader && group_rec->activated_upstream_cnt==0) { + /* not leader and no upstream, so activate one */ + mact_activate_best_upstream(group_rec); + } + + + }else if(mact->p) { + /* PRUNE */ + mrt_nexthop_t *nexthop; + + DEBUG(LOG_DEBUG, 0, "Entered mact->p handler"); + + nexthop=mrt_table_get_activated_upstream(group_rec); + if(nexthop!=NULL && nexthop->addr==src_addr){ + DEBUG(LOG_DEBUG, 0, "\tUpstream sent prune"); + /* deactivate said upstream in our records */ + mrt_nexthop_deactivate(group_rec, nexthop->addr); + /* upstream sent us prune */ + /* if member, become leader, else leave and make a downstream */ + if(group_rec->is_member){ + mrt_table_become_leader(group_rec); + }else{ + mact_make_downstream_leader(group_rec); + } + } + + /* if no other downstreams and not listening ourselves, prune self */ + else if(!(group_rec->is_member) && group_rec->activated_downstream_cnt==1) { + mrt_nexthop_t *upstream; + upstream=mrt_table_get_activated_upstream(group_rec); + DEBUG(LOG_DEBUG, 0, "\tDownstream sent prune, prune self"); + if(upstream != NULL){ + mact_send(MACT_PRUNE, 1, grp_addr, upstream->addr,1); + mrt_nexthop_deactivate(group_rec, upstream->addr); + } + mrt_table_stop_routing(group_rec); + }else{ + DEBUG(LOG_DEBUG, 0, "\tDownstream sent prune, stay on tree"); + } + + /* remove them */ + mrt_nexthop_deactivate(group_rec, src_addr); + } else if(mact->g) { + /* GR/OUP LEADER + * + * my upstream may send it to me. + * either I become leader or I promote a child + */ + + /* node who sent it has me marked as its upstream now */ + mrt_nexthop_t *node; + node=mrt_table_get_activated_upstream(group_rec); + if(node!=NULL){ + node->direction=MRT_DOWNSTREAM; + group_rec->activated_upstream_cnt--; + group_rec->activated_downstream_cnt++; + } + + if(group_rec->is_member) { + /* declare myself leader */ + /* TODO: might need to set U flag on first one */ + + mrt_table_become_leader(group_rec); + } else { + /* send a notice to a downstream making it leader */ + mact_make_downstream_leader(group_rec); + } + } else if(mact->u) { + /* UPDATE */ + } else if(mact->r) { + /* REBOOT */ + } +} + +mrt_nexthop_t *mact_activate_best_upstream(mrt_table_t *mrt){ + mrt_nexthop_t *besthop=NULL; + + besthop=mrt_table_get_best_upstream(mrt); + + /* and activate it */ + if(besthop!=NULL){ + mrt_nexthop_activate(mrt, besthop->addr); + mact_send(MACT_JOIN, 1, mrt->grp_addr, besthop->addr, 1); + DEBUG(LOG_DEBUG, 0, "activated upstream %s", ip_to_str(besthop->addr)); + mrt->is_router=1; + + if ( seek_list_remove( mrt->grp_addr ) ) { + mcast_packet_queue_send( mrt->grp_addr ); + } + } + + return besthop; +} + +void mact_make_downstream_leader(mrt_table_t *group_rec){ + mrt_nexthop_t *downstream; + DEBUG(LOG_DEBUG, 0, "Entered mact_make_downstream_leader"); + + if(group_rec->activated_downstream_cnt==0){ + DEBUG(LOG_DEBUG, 0, "No downstreams to make leader! Clearing flags"); + mrt_table_stop_routing(group_rec); + return; + } + + downstream=group_rec->nexthops; + while(downstream->direction!=MRT_DOWNSTREAM || !downstream->activated){ + downstream=downstream->next; + } + + if(group_rec->activated_downstream_cnt==1){ + /* one child, make him leader */ + DEBUG(LOG_DEBUG, 0, "\tEntered one child version"); + mact_send(MACT_PRUNE, 0, group_rec->grp_addr, downstream->addr,1); + mrt_nexthop_deactivate(group_rec, downstream->addr); + mrt_table_stop_routing(group_rec); + + /* remove any pending RREQs (or other packets) for this group */ + seek_list_remove(group_rec->grp_addr); + packet_queue_drop(group_rec->grp_addr); + + /* flush all nexthops */ + mrt_nexthop_remove_all(group_rec); + }else{ + /* send a 'G' mact to an arbitrary child, then make it upstream */ + DEBUG(LOG_DEBUG, 0, "\tEntered many child version (where you stay as router)"); + mact_send(MACT_GRPL, 0, group_rec->grp_addr, downstream->addr,1); + downstream->direction=MRT_UPSTREAM; + group_rec->activated_downstream_cnt--; + group_rec->activated_upstream_cnt++; + } +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/maodv_mact.h ./maodv-umd/maodv_mact.h --- ./aodv-uu-0.6/maodv_mact.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_mact.h Mon Feb 24 12:38:52 2003 @@ -0,0 +1,98 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef MAODV_MACT_H +#define MAODV_MACT_H + +#ifndef NS_NO_GLOBALS +#include + +#include "defs.h" +#include "multicast_routing_table.h" + +/* MACT Flags: */ +#define MACT_JOIN 0x10 +#define MACT_PRUNE 0x08 +#define MACT_GRPL 0x04 +#define MACT_UPDATE 0x02 +#define MACT_REBOOT 0x01 + +typedef struct _mact_t { + u_int8_t type; +# if __BYTE_ORDER == __LITTLE_ENDIAN + u_int8_t res1:3; + u_int8_t r:1; + u_int8_t u:1; + u_int8_t g:1; + u_int8_t p:1; + u_int8_t j:1; +# elif __BYTE_ORDER == __BIG_ENDIAN + u_int8_t j:1; + u_int8_t p:1; + u_int8_t g:1; + u_int8_t u:1; + u_int8_t r:1; + u_int8_t res1:3; +# else +# error "Adjust your defines" +# endif + u_int8_t res2; + u_int8_t hcnt; + u_int32_t grp_addr; + u_int32_t src_addr; + u_int32_t src_seqno; +} mact_t; + +#define MACT mact_t +#define MACT_SIZE sizeof(MACT) + +#endif /* NS_NO_GLOBALS */ + +#ifndef NS_NO_DECLARATIONS +MACT *mact_create(u_int8_t flags, + u_int8_t hcnt, + u_int32_t src_addr, + u_int32_t grp_addr); + +void mact_send(u_int8_t flags, + u_int8_t hcnt, + u_int32_t grp_addr, + u_int32_t dst_addr, + int ttl); + +void mact_mcast(u_int8_t flags, + u_int8_t hcnt, + u_int32_t grp_addr, + int ttl); + +void mact_process(MACT *mact); + +mrt_nexthop_t *mact_activate_best_upstream(mrt_table_t *mrt); +void mact_make_downstream_leader(mrt_table_t *mrt); + + +#endif /* NS_NO_DECLARATIONS */ + +#endif /* MAODV_MACT_H */ diff -urN ./aodv-uu-0.6/maodv_neighbor.c ./maodv-umd/maodv_neighbor.c --- ./aodv-uu-0.6/maodv_neighbor.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_neighbor.c Mon Feb 24 13:27:16 2003 @@ -0,0 +1,104 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#include "maodv_neighbor.h" +#include "routing_table.h" +#include "multicast_routing_table.h" +#include "aodv_rreq.h" +#include "maodv_mact.h" +#include "debug.h" +#include "params.h" + +void mcast_neighbor_link_break(rt_table_t *rt){ + mrt_table_t *mrt; + mrt_nexthop_t *nexthop; + int i; + + /* determine which, if any, groups the broken node is in */ + for(i=0; idest_addr); + + /* only care about activated routes */ + if(nexthop!=NULL && nexthop->activated){ + int nh_dir=nexthop->direction; + + mrt_nexthop_remove(mrt, nexthop->addr); + if(nh_dir==MRT_UPSTREAM){ + mrt->is_broken = 1; + + /* we lost our upstream, find a new one */ + rreq_route_discovery(mrt->grp_addr, + RREQ_JOIN|RREQ_GRP_REBUILD, NULL, 0); + }else{ + /* we lost our downstream, wait to see if he returns */ + mrt_nexthop_remove(mrt, nexthop->addr); + + if(!mrt->is_member && mrt->activated_downstream_cnt==0){ + DEBUG(LOG_DEBUG, 0, "setting prune dangle timer"); + + /* set timeout to prune self if downstream doesn't + * reconnect */ + mrt->prune_timer.handler = (timeout_func_t) &mcast_prune_dangle; + mrt->prune_timer.data = &mrt; + + /* 20 seconds of rebuild time. */ + timer_set_timeout( &mrt->prune_timer, PRUNE_TIMEOUT ); + } + } + } + + mrt=mrt->next; + } + } +} + +/* mcast_prune_dangle + * if you become a router only with no downstream nodes, (dangling) then + * prune self after a timeout */ +void mcast_prune_dangle( mrt_table_t *mrt ) { + mrt_nexthop_t * upstream; + + DEBUG(LOG_DEBUG, 0, "in prune dangle timer"); + if ( mrt->activated_downstream_cnt == 0 && !mrt->is_member ) { + /* prune me */ + + upstream = mrt_table_get_activated_upstream( mrt ); + DEBUG( LOG_DEBUG, 0, "Pruning myself after a reasonable timeout." ); + + if(upstream != NULL){ + mact_send( MACT_PRUNE, 1, mrt->grp_addr, upstream->addr, 1 ); + mrt_nexthop_deactivate( mrt, upstream->addr ); + } + + mrt_table_stop_routing(mrt); + } +} + +#endif diff -urN ./aodv-uu-0.6/maodv_neighbor.h ./maodv-umd/maodv_neighbor.h --- ./aodv-uu-0.6/maodv_neighbor.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_neighbor.h Mon Feb 24 13:27:16 2003 @@ -0,0 +1,38 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef MAODV_NEIGHBOR_H +#define MAODV_NEIGHBOR_H + +#include "routing_table.h" +#include "multicast_routing_table.h" + +void mcast_neighbor_link_break(rt_table_t *rt); +/* mcast_prune_dangle + * if you become a router only with no downstream nodes, (dangling) then + * prune self after a timeout */ +void mcast_prune_dangle( mrt_table_t *mrt ); + +#endif diff -urN ./aodv-uu-0.6/maodv_rrep.c ./maodv-umd/maodv_rrep.c --- ./aodv-uu-0.6/maodv_rrep.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_rrep.c Mon Feb 24 13:27:16 2003 @@ -0,0 +1,191 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#include "defs.h" +#include "debug.h" +#include "maodv_rrep.h" +#include "routing_table.h" +#include "multicast_routing_table.h" +#include "aodv_socket.h" +#include "aodv_rreq.h" +#include "aodv_rrep.h" +#include "packet_queue.h" + +/* + * maodv_rrep_process( lots of stuff ) + * Processes an rrep that has already been sanity checked and is + * responding to a multicast group. + */ +void maodv_rrep_process( RREP *rrep, int rreplen, u_int32_t ip_src, + u_int32_t ip_dst, int ip_ttl, unsigned int ifindex, int size ) +{ + mrt_nexthop_t * upstream; + mrt_table_t * mrt; + rt_table_t * rev_rt; + u_int32_t rrep_orig, rrep_dest, rrep_seqno, rrep_lifetime; + mrt_orig_t *orig; + + DEBUG( LOG_DEBUG, 0, "Inside RREP process." ); + + rrep_dest = ntohl(rrep->dest_addr); + rrep_seqno = ntohl(rrep->dest_seqno); + rrep_orig = ntohl(rrep->orig_addr); + rrep_lifetime = ntohl(rrep->lifetime); + + rev_rt = rt_table_find( rrep_orig ); + mrt = mrt_table_find( rrep_dest ); + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "No multicast route to group %s found in RREP.", + ip_to_str( rrep_dest ) ); + return; + } + + upstream = mrt_nexthop_find(mrt, ip_src); + if(upstream == NULL){ + DEBUG( LOG_DEBUG, 0, "Created nexthop." ); + upstream = mrt_nexthop_add( mrt, ip_src, MRT_UPSTREAM, rrep_seqno ); + } else { + /* update seqno */ + DEBUG( LOG_DEBUG, 0, "Had nexthop, updated seqno." ); + upstream->grp_seqno = rrep_seqno; + } + + /* add the originator to the originator list if not there already */ + orig=mrt_origlist_find(mrt, rrep_orig); + if(orig==NULL){ + DEBUG(LOG_DEBUG, 0, "originator not in list, adding"); + orig=mrt_origlist_add(mrt, rrep_orig); + } + + DEBUG(LOG_DEBUG, 0, "originator seqno: %d hcnt: %d", orig->grp_seqno, + orig->grp_hcnt); + + /* rrep is propagated if the prior rreq had a lower + sequence number or the sequence numbers are equal and the + incoming rrep has a smaller hopcount */ + if ( ( ( orig->grp_seqno < rrep_seqno ) || + ( ( orig->grp_seqno == rrep_seqno ) && + ( orig->grp_hcnt > rrep->hcnt ) ) ) ){ + + DEBUG( LOG_DEBUG, 0, "Forwardable/acceptable rrep." ); + + mrt->grp_seqno = rrep_seqno; + orig->grp_seqno=rrep_seqno; + orig->grp_hcnt = rrep->hcnt; + + if ( !upstream->activated ) { + upstream->direction = MRT_UPSTREAM; + upstream->grp_hcnt = rrep->hcnt; + } + + if ( rrep_orig != DEV_IFINDEX(ifindex).ipaddr ) + maodv_rrep_forward( rrep, rev_rt, mrt, --ip_ttl, size ); + } else { + DEBUG( LOG_DEBUG, 0,"mrt->grp_seqno: %d\trrep_seqno: %d", + mrt->grp_seqno, rrep_seqno ); + } +} + +void maodv_rrep_forward( RREP * rrep, rt_table_t * rev_rt, + mrt_table_t * fwd_rt, int ttl, int size ) +{ + mrt_nexthop_t * upstream; + + if (!fwd_rt || !rev_rt) { + DEBUG(LOG_WARNING, 0, "Could not forward RERR because of NULL route!"); + return; + } + + if (!rrep) { + DEBUG(LOG_WARNING, 0, "No RREP to forward!"); + return; + } + + DEBUG(LOG_DEBUG, 0, "Forwarding RREP to %s", ip_to_str(rev_rt->next_hop)); + + rrep = (RREP *) aodv_socket_queue_msg((AODV_msg *) rrep, size); + upstream = mrt_table_get_best_upstream( fwd_rt ); + + /* Update the hopcount */ + if(!fwd_rt->is_router){ + rrep->hcnt++; + } + + aodv_socket_send((AODV_msg *) rrep, rev_rt->next_hop, size, ttl, + &DEV_IFINDEX(rev_rt->ifindex)); + + /* TODO: timing code... */ +/* rt_table_update_timeout(rev_rt, ACTIVE_ROUTE_TIMEOUT); */ +} + +void maodv_rrep_send( rt_table_t * rev_rt, mrt_table_t * fwd_rt ) +{ + RREP *rrep; + u_int8_t rrep_flags = 0; + u_int32_t dest, lifetime; + int hcnt; + + /* CHECK: we do not use this... */ + lifetime = 0x0ffffffff; + + if (!rev_rt) { + DEBUG(LOG_WARNING, 0, "Can't send RREP, rev_rt = NULL!"); + return; + } + + if (!fwd_rt) { + DEBUG(LOG_WARNING, 0, "Can't send RREP, fwd_rt = NULL!"); + return; + } + + DEBUG(LOG_DEBUG, 0, "[maodv] sending rrep."); + + dest = fwd_rt->grp_addr; + + hcnt = 0; + + /* TODO: timeout code... */ + /* + gettimeofday(&now, NULL); + lifetime = timeval_diff(&fwd_rt->rt_timer.timeout, &now); + */ + + DEBUG(LOG_DEBUG, 0, "[maodv] Sending RREP to %s about %s->%s", + ip_to_str(rev_rt->next_hop), ip_to_str(rev_rt->dest_addr), + ip_to_str(dest)); + + rrep = rrep_create(rrep_flags, 0, hcnt, dest, fwd_rt->grp_seqno, + rev_rt->dest_addr, lifetime, 0 ); + + aodv_socket_send((AODV_msg *) rrep, rev_rt->next_hop, RREP_SIZE, MAXTTL, + &DEV_IFINDEX(rev_rt->ifindex)); + +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/maodv_rrep.h ./maodv-umd/maodv_rrep.h --- ./aodv-uu-0.6/maodv_rrep.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_rrep.h Mon Feb 24 12:38:52 2003 @@ -0,0 +1,41 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef MAODV_RREP_H +#define MAODV_RREP_H + +#include "routing_table.h" +#include "multicast_routing_table.h" +#include "aodv_rrep.h" + +void maodv_rrep_process( RREP *rrep, int rreplen, u_int32_t ip_src, + u_int32_t ip_dst, int ip_ttl, unsigned int ifindex, int size ); + +void maodv_rrep_forward( RREP * rrep, rt_table_t * rev_rt, + mrt_table_t * fwd_rt, int ttl, int size ); + +void maodv_rrep_send( rt_table_t * rev_rt, mrt_table_t * fwd_rt ); + +#endif diff -urN ./aodv-uu-0.6/maodv_rreq.c ./maodv-umd/maodv_rreq.c --- ./aodv-uu-0.6/maodv_rreq.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_rreq.c Mon Feb 24 13:27:16 2003 @@ -0,0 +1,175 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#include "defs.h" +#include "debug.h" +#include "maodv_rreq.h" +#include "maodv_rrep.h" +#include "multicast_routing_table.h" +#include "aodv_socket.h" +#include "aodv_rreq.h" +#include "aodv_rrep.h" +#include "maodv_ext.h" + +/* + * maodv_rreq_process( lots of stuff ) + * Processes an rreq that has already been sanity checked and is + * headed for a multicast group. + */ +void maodv_rreq_process( RREQ *rreq, int rreqlen, u_int32_t ip_src, + u_int32_t ip_dst, int ip_ttl, unsigned int ifindex, + GRP_REBUILD_EXT *grb_ext, int size ) +{ + mrt_table_t * mrt; + rt_table_t * rev_rt; + u_int32_t rreq_orig, rreq_dest, rreq_orig_seqno, rreq_dest_seqno; + u_int32_t rreq_id, rreq_new_hcnt; + mrt_nexthop_t * nh; + mrt_orig_t *orig; + + DEBUG( LOG_DEBUG, 0, "Inside RREP process." ); + + rreq_id = ntohl(rreq->rreq_id); + rreq_dest = ntohl(rreq->dest_addr); + rreq_dest_seqno = ntohl(rreq->dest_seqno); + rreq_orig = ntohl(rreq->orig_addr); + rreq_orig_seqno = ntohl(rreq->orig_seqno); + rreq_new_hcnt = rreq->hcnt + 1; + + mrt = mrt_table_find( rreq_dest ); + if ( mrt==NULL ) { + /* no route found */ + DEBUG(LOG_DEBUG, 0, "MRREQ: No mrt found." ); + mrt = mrt_table_insert( rreq_dest, 0, rreq_dest_seqno, + ifindex, 255, 0 ); + } + + /* add nexthop downstream */ + nh = mrt_nexthop_find( mrt, rreq_orig ); + if ( nh == NULL ) { + mrt_nexthop_add( mrt, ip_src, MRT_DOWNSTREAM, rreq_dest_seqno ); + } + + /* add the originator to the originator list if not there already */ + orig=mrt_origlist_find(mrt, rreq_orig); + if(orig==NULL){ + DEBUG(LOG_DEBUG, 0, "originator not in list, adding"); + orig=mrt_origlist_add(mrt, rreq_orig); + } + DEBUG(LOG_DEBUG, 0, "originator seqno: %d hcnt: %d", orig->grp_seqno, orig->grp_hcnt); + + if ( rreq->j ) { + /* a Join request */ + DEBUG(LOG_DEBUG, 0, "MRREQ: [j] Join." ); + + if ( !mrt->is_router) { + DEBUG(LOG_DEBUG, 0, "MRREQ: [j] Found a mrt, but not on the tree."); + } else if ( mrt->grp_seqno < rreq_dest_seqno ) { + DEBUG(LOG_DEBUG, 0, "MRREQ: [j] Found a mrt, but it is old. %d < %d", mrt->grp_seqno, rreq_dest_seqno ); + mrt->grp_seqno = rreq_dest_seqno; + } else { + if(grb_ext==NULL || mrt->leader_hcnt<=grb_ext->grp_hcnt){ + DEBUG(LOG_DEBUG, 0, "MRREQ: [j] Should send RREP!" ); + + /* send rrep */ + rev_rt = rt_table_find( rreq_orig ); + orig->grp_seqno=mrt->grp_seqno; + orig->grp_hcnt=0; + maodv_rrep_send( rev_rt, mrt ); + + /* done! get out */ + return; + }else{ + DEBUG(LOG_DEBUG, 0, "had repair extension, bad hopcount, do nothing"); + } + } + } else { + /* non-Join request */ + DEBUG(LOG_DEBUG, 0, "MRREQ: [] non-Join." ); + + if ( mrt->grp_seqno < rreq_dest_seqno ) { + DEBUG(LOG_DEBUG, 0, "MRREQ: [] Found a mrt, but it is old." ); + /* update sequence number in our table */ + mrt->grp_seqno = rreq_dest_seqno; + } else if ( mrt->is_router ) { + DEBUG(LOG_DEBUG, 0, "MRREQ: [] Should send RREP!" ); + + /* send rrep */ + rev_rt = rt_table_find( rreq_orig ); + orig->grp_seqno=mrt->grp_seqno; + orig->grp_hcnt=0; + maodv_rrep_send( rev_rt, mrt ); + + /* we're done! */ + return; + } + } + + /* if we get this far, no RREP has been sent. */ + + /* now, forward RREQ */ + /* if rreq has unknown seqno and our table has a known one + (not zero), then update packet seqno field. or if ours + is just bigger. + CHECK: this may not be the way to do this */ + if ( ( mrt->grp_seqno > rreq_dest_seqno ) || + ( rreq->u && mrt->grp_seqno ) ) { + rreq->u = 0; + rreq->dest_seqno = htonl( mrt->grp_seqno ); + } + + /* send it back out */ + maodv_rreq_forward( rreq, --ip_ttl, size ); +} + +/* + * maodv_rreq_forward( RREQ * rreq, int ttl, int size ) + * Forwards a route request. + */ +void maodv_rreq_forward( RREQ * rreq, int ttl, int size ) +{ + int i; + /* FORWARD the RREQ if the TTL allows it. */ + DEBUG(LOG_DEBUG, 0, "[maodv] forwarding RREQ src=%s, rreq_id=%lu", + ip_to_str(ntohl(rreq->orig_addr)), ntohl(rreq->rreq_id)); + + /* Queue the received message in the send buffer */ + rreq = (RREQ *) aodv_socket_queue_msg((AODV_msg *) rreq, size); + + rreq->hcnt++; /* Increase hopcount to account for + * intermediate route */ + + /* Send out on all interfaces */ + for (i = 0; i < MAX_NR_INTERFACES; i++) { + if (!DEV_NR(i).enabled) + continue; + aodv_socket_send((AODV_msg *) rreq, AODV_BROADCAST, size, ttl, + &DEV_NR(i)); + } +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/maodv_rreq.h ./maodv-umd/maodv_rreq.h --- ./aodv-uu-0.6/maodv_rreq.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/maodv_rreq.h Mon Feb 24 12:38:52 2003 @@ -0,0 +1,39 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef MAODV_RREQ_H +#define MAODV_RREQ_H + +#include "defs.h" +#include "aodv_rreq.h" +#include "maodv_ext.h" + +void maodv_rreq_process( RREQ *rreq, int rreqlen, u_int32_t ip_src, + u_int32_t ip_dst, int ip_ttl, unsigned int ifindex, + GRP_REBUILD_EXT *grb_ext, int size ); + +void maodv_rreq_forward( RREQ * rreq, int ttl, int size ); + +#endif /* MAODV_RREQ_H */ diff -urN ./aodv-uu-0.6/multicast_packet_cache.c ./maodv-umd/multicast_packet_cache.c --- ./aodv-uu-0.6/multicast_packet_cache.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/multicast_packet_cache.c Mon Feb 24 12:38:52 2003 @@ -0,0 +1,77 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Matthew Impett + * + * + *****************************************************************************/ + +#include "multicast_packet_cache.h" + +void init_packet_cache(void) +{ + int i; + int j; + for(i=0; i< HASHBUCKETS; i++) + { + packet_cache[i].packet_cache_write_index = 0; + for(j=0; j < MAX_PACKET_CACHE; j++) + { + packet_cache[i].ip_src[j] = 0; + packet_cache[i].ip_id[j] = 0; + } + } +} + +/* This function returns 1 if a duplicate packet has not been + found and returns 0 if a duplicate packet has not been found and adds + that packet to the packet cache. */ +int check_duplicate(u_int32_t src, u_int16_t id) +{ + u_int8_t hash_value; + int i; + int j = 0; + hash_value = packet_hashfunction(src); + + for(i=0; i< MAX_PACKET_CACHE; i++) + { + if( (packet_cache[hash_value].ip_src[i] == src) && + (packet_cache[hash_value].ip_id[i] == id) ) + { + /* Found a duplicate packet.... Drop it */ + return 0; + } + } + + /* Not found the packet in the cache... Add it to the packet cache */ + + j = packet_cache[hash_value].packet_cache_write_index ; + packet_cache[hash_value].ip_src[j] = src; + packet_cache[hash_value].ip_id[j] = id; + packet_cache[hash_value].packet_cache_write_index = (j+1)%(MAX_PACKET_CACHE); + return 1; +} + +u_int8_t packet_hashfunction(u_int32_t addr) +{ + return ((addr >> 24) % HASHBUCKETS); +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/multicast_packet_cache.h ./maodv-umd/multicast_packet_cache.h --- ./aodv-uu-0.6/multicast_packet_cache.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/multicast_packet_cache.h Mon Feb 24 12:38:52 2003 @@ -0,0 +1,52 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Matthew Impett + * + * + *****************************************************************************/ + +/********************************************************************** + The following packet cache has been obtained from Matthew Impett's + TORA implementation code..... + **********************************************************************/ + +#ifndef MULTICAST_PACKET_CACHE_H +#define MULTICAST_PACKET_CACHE_H + +#include "defs.h" + +#define HASHBUCKETS 10 /* number of buckets for entries */ +#define MAX_PACKET_CACHE 10 /* # of packets for each hash bucket */ + +/* This structure is used to hold a little cache of recently forwarded + packets which we can use to detect duplicate packets. */ +struct pack_cache +{ + u_int32_t ip_src[MAX_PACKET_CACHE]; + u_int16_t ip_id[MAX_PACKET_CACHE]; + int packet_cache_write_index; +}; + +struct pack_cache packet_cache[HASHBUCKETS]; +void init_packet_cache(void); +u_int8_t packet_hashfunction(u_int32_t addr); +int check_duplicate(u_int32_t source, u_int16_t id); + +#endif /* MULTICAST_PACKET_CACHE_H */ + diff -urN ./aodv-uu-0.6/multicast_routing_table.c ./maodv-umd/multicast_routing_table.c --- ./aodv-uu-0.6/multicast_routing_table.c Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/multicast_routing_table.c Mon Feb 24 12:38:52 2003 @@ -0,0 +1,966 @@ +#ifdef MAODV + +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#include +#include +#include + +#include "multicast_routing_table.h" + +#include "aodv_timeout.h" +#include "packet_queue.h" +#include "aodv_rerr.h" +#include "aodv_hello.h" +#include "aodv_socket.h" +#include "k_route.h" +#include "k_mroute.h" +#include "timer_queue.h" +#include "defs.h" +#include "debug.h" +#include "params.h" +#include "seek_list.h" +#include "maodv_mact.h" +#include "maodv_grph.h" + +static struct timer mrt_debug_timer; + +inline static unsigned int hashing(u_int32_t addr); + +/* + Local static functions +*/ + +/* + hashing( addr ) + A VERY simple "hash" function. Taskes the multicast address as + a key and hacks off the most significant bits. (how many bits it + masks off depends on the size of the hash table. look at the + MRT_TABLEMASK define) This becomes an index into the hash table. + +*/ +inline static unsigned int hashing(u_int32_t addr) +{ + return( addr & MRT_TABLEMASK ); +} + +/* + * Public functions + */ + +/* + * mrt_table_init( ) + * Create an empty table with 0 entries. + */ +void mrt_table_init() +{ + int index; + int fd; + + mrt_tbl.num_entries = 0; + + /* init buckets with null pointers. */ + for( index = 0; index < MRT_TABLESIZE; index++ ) { + mrt_tbl.tbl[index] = NULL; + } + + /* CHECK: add in with other log code? not yet... */ + + /* every 10 seconds? */ + mrt_debug_timer.handler = (timeout_func_t) &mrt_table_dump; + mrt_debug_timer.data = NULL; + + fd = open( "nh_log", O_RDWR | O_CREAT | O_TRUNC, S_IROTH | + S_IWUSR | S_IRUSR | S_IRGRP ); + + close ( fd ); + + fd = open( "mrt_log", O_RDWR | O_CREAT | O_TRUNC, S_IROTH | + S_IWUSR | S_IRUSR | S_IRGRP ); + + close ( fd ); + + mrt_table_dump(); +} + +/* + * mrt_table_destroy( ) + * Destroy table and each entry. + */ +void mrt_table_destroy() +{ + int index; + mrt_table_t *curr; + mrt_table_t *dead; + + for( index = 0; index < MRT_TABLESIZE; index++ ) { + curr = mrt_tbl.tbl[index]; + + while( curr ) { + dead = curr; + curr = curr->next; + + /* TODO: Timeout multicast routes. + timer_remove( &dead->mrt_timer ); */ + + mrt_nexthop_remove_all( dead ); + + mrt_sources_remove_all( dead ); + free( dead ); + } + + /* safety */ + mrt_tbl.tbl[index] = NULL; + } + + mrt_tbl.num_entries = 0; +} + +/* + * mrt_table_insert( route info ) + * This creates a route with NO next hop info. Any next hop info must be + * added with other function calls. + */ +mrt_table_t *mrt_table_insert(u_int32_t grp_addr, u_int32_t grp_leader_addr, + u_int32_t grp_seqno, + unsigned int ifindex, + u_int8_t leader_hcnt, + u_int8_t is_member) +{ + mrt_table_t *new_entry; + int index; + + /* if it's already in the table, we can't add it */ + if ( mrt_table_find( grp_addr ) ) { + return NULL; + } + + index = hashing( grp_addr ); + + new_entry = (mrt_table_t *) malloc( sizeof( mrt_table_t ) ); + if ( !new_entry ) { + /* go down if theres no memory? probably best idea */ + fprintf( stderr, "multicast_routing_table.c: Cannot allocate memory for route.\n" ); + exit( -1 ); + } + + new_entry->grp_addr = grp_addr; + new_entry->grp_leader_addr = grp_leader_addr; + new_entry->grp_seqno = grp_seqno; + new_entry->am_leader = 0; /* false... i am not leader! */ + + new_entry->ifindex = ifindex; + new_entry->leader_hcnt = leader_hcnt; + new_entry->is_member = is_member; + new_entry->is_router = 0; /* false */ + new_entry->is_broken = 0; /* false */ + new_entry->in_repair = 0; /* false */ + + /* initialize timers */ + + /* TODO: Timeout routes. + new_entry->mrt_timer.handler = &multicast_route_expire_timeout; + new_entry->mrt_timer.data = new_entry; */ + + /* empty next hop list */ + new_entry->nexthops = NULL; + new_entry->activated_upstream_cnt = 0; + new_entry->activated_downstream_cnt = 0; + + new_entry->sources = NULL; + new_entry->origlist = NULL; + + /* make me first, so next will be whoever is currently top of bucket */ + new_entry->next = mrt_tbl.tbl[index]; + mrt_tbl.tbl[index] = new_entry; + mrt_tbl.num_entries++; + /* CHECK: add kernel route entry */ + + /* grph timer */ + new_entry->grph_timer.handler=(timeout_func_t) &grph_send_callback; + new_entry->grph_timer.data=new_entry; + + /* start new timer */ + + /* TODO: Timeout routes. + DEBUG(LOG_INFO, 0, "New timer for %s, life=%d", + ip_to_str(new_entry->grp_addr), ACTIVE_ROUTE_TIMEOUT ); + + timer_set_timeout( &new_entry->mrt_timer, ACTIVE_ROUTE_TIMEOUT ); + */ + + return new_entry; +} + +/* + * mrt_table_update_timeout( route, lifetime ) + * Resets the route timeout. Renews the lease in the route table. + */ +NS_INLINE mrt_table_t *mrt_table_update_timeout(mrt_table_t * mrt, + u_int32_t lifetime) +{ + struct timeval new_timeout; + + /* make sure route tp update is somewhat legal. */ + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to update NULL route."); + + return NULL; + } + + gettimeofday( &new_timeout, NULL ); + timeval_add_msec( &new_timeout, lifetime ); + + /* TODO: Timeout routes. + if ( timeval_diff( &mrt->mrt_timer.timeout, &new_timeout ) < 0 ) { + timer_set_timeout( &mrt->mrt_timer, lifetime ); + } + */ + + return mrt; +} + +/* + * mrt_table_find( group address ) + * This looks up an entry in the routing table. If none is found, + * NULL is returned. Otherwise a pointer to the entry is returned. + */ +mrt_table_t *mrt_table_find(u_int32_t grp_addr) +{ + mrt_table_t *curr; + int index; + + index = hashing( grp_addr ); + curr = mrt_tbl.tbl[index]; + + /* If nothing is in the bucket the group address hashes to, + return NULL. It's definitely not here. */ + if ( !curr ) { + return NULL; + } + + while( curr ) { + if ( curr->grp_addr == grp_addr ) { + break; + } + + curr = curr->next; + } + + return curr; +} + +/* + * mrt_table_delete( group addr ) + * Delete a route from the routing table. + */ +void mrt_table_delete(u_int32_t grp_addr) +{ + int index; + mrt_table_t * curr, * prev; + + index = hashing( grp_addr ); + + curr = mrt_tbl.tbl[index]; + prev = NULL; + + if ( !curr ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to delete an unknown route."); + return; + } + + while( curr ) { + if ( curr->grp_addr == grp_addr ) { + break; + } + + prev = curr; + curr = curr->next; + } + + if ( !curr ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to delete an unknown route."); + return; + } + + /* CHECK: Remove entry from kernel routing table. */ + /* TODO: Timeout routes. + timer_remove( &curr->mrt_timer ); */ + + mrt_nexthop_remove_all( curr ); + + if ( !prev ) { + /* Deleting the head */ + mrt_tbl.tbl[index] = NULL; + } else { + prev->next = curr->next; + } + + mrt_tbl.num_entries--; + + free( curr ); +} + +/* + * mrt_nexthop_add( multi route, nh addr, direction ) + * Adds a nexthop entry into a routes information. Starts out unactivated. + */ +mrt_nexthop_t * mrt_nexthop_add(mrt_table_t * mrt, u_int32_t addr, + u_int8_t direction, u_int32_t grp_seqno) +{ + mrt_nexthop_t *newhop; + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to add a next hop to an unknown route."); + return NULL; + } + + newhop = mrt_nexthop_find( mrt, addr ); + if ( newhop ) { /* if it's already there, update it? */ + return newhop; + } + + newhop = (mrt_nexthop_t *) malloc( sizeof( mrt_nexthop_t ) ); + if ( !newhop ) { + fprintf( stderr, "multicast_routing_table.c: Error allocating nexthop entry.\n" ); + exit( -1 ); + } + + newhop->addr = addr; + newhop->direction = direction; + newhop->activated = 0; /* 0 == FALSE */ + newhop->grp_hcnt = 0xff; /* start with infinite hcnt */ + newhop->grp_seqno=grp_seqno; + + newhop->next = mrt->nexthops; + mrt->nexthops = newhop; + + return newhop; +} + +/* + * mrt_nexthop_remove( route, addr ) + * Remove a nexthop entry from a kernel route info. + */ +void mrt_nexthop_remove(mrt_table_t * mrt, u_int32_t addr ) +{ + mrt_nexthop_t * curr, * prev; + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to remove a next hop from an unknown route."); + return; + } + + curr = mrt->nexthops; + prev = NULL; + + if ( !curr ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to remove a next hop [%s] that doesn't exist.", + ip_to_str( addr ) ); + return; + } + + while( curr ) { + if ( curr->addr == addr ) { + break; + } + + prev = curr; + curr = curr->next; + } + + if ( !curr ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to remove a next hop that doesn't exist."); + return; + } + + if ( !prev ) { + mrt->nexthops = curr->next; + } else { + prev->next = curr->next; + } + + if ( curr->activated ) { + if ( curr->direction == MRT_UPSTREAM ) { + mrt->activated_upstream_cnt--; + } else if ( curr->direction == MRT_DOWNSTREAM ) { + mrt->activated_downstream_cnt--; + } + } + + free( curr ); +} + +/* + * mrt_nexthop_activated( route, addr, on/off ) + * Sets a certain nexthop flag indicating if this route is active or not. + */ +void mrt_nexthop_activate(mrt_table_t * mrt, u_int32_t addr) +{ + FILE *nh_log; + mrt_nexthop_t *curr; + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to activate a next hop for a NULL route."); + return; + } + + curr = mrt->nexthops; + + while( curr ) { + if ( curr->addr == addr ) { + break; + } + + curr = curr->next; + } + + if ( !curr ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to activate a next hop that doesn't exist."); + return; + } + + curr->activated = 1; + + if ( curr->direction == MRT_UPSTREAM ) { + mrt->activated_upstream_cnt++; + } else if ( curr->direction == MRT_DOWNSTREAM ) { + mrt->activated_downstream_cnt++; + } + + nh_log=fopen("nh_log", "a"); + fprintf(nh_log, "ACTIVATE: %x %x\n", mrt->grp_addr, addr); + fclose(nh_log); +} + +/* + * mrt_nexthop_deactivate( route, addr ) + * Sets a certain nexthop flag indicating if this route is active or not. + */ +void mrt_nexthop_deactivate(mrt_table_t * mrt, u_int32_t addr) +{ + FILE *nh_log; + mrt_nexthop_t *curr; + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to activate a next hop for a NULL route."); + return; + } + + curr = mrt->nexthops; + + while( curr ) { + if ( curr->addr == addr ) { + break; + } + + curr = curr->next; + } + + if ( !curr ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to deactivate a next hop that doesn't exist."); + return; + } + + if(curr->activated == 1){ + if ( curr->direction == MRT_UPSTREAM ) { + mrt->activated_upstream_cnt--; + } else if ( curr->direction == MRT_DOWNSTREAM ) { + mrt->activated_downstream_cnt--; + } + + curr->activated=0; + + nh_log=fopen("nh_log", "a"); + fprintf(nh_log, "DEACTIVATE: %x %x\n", mrt->grp_addr, addr); + fclose(nh_log); + } +} + +/* + * mrt_nexthop_get_upstream( table entry ) + * Returns pointer to activated upstream next hop. + */ +mrt_nexthop_t *mrt_table_get_activated_upstream(mrt_table_t * mrt) +{ + mrt_nexthop_t *curr; + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to get an upstream for a NULL route."); + return NULL; + } + + curr = mrt->nexthops; + + while( curr ) { + if ( ( curr->activated ) && ( curr->direction == MRT_UPSTREAM ) ) { + break; + } + + curr = curr->next; + } + + return curr; +} + +/* + * mrt_nexthop_remove_all( table entry ) + * Destroys every entry in next_hop list for a multicast route. + */ +void mrt_nexthop_remove_all(mrt_table_t * mrt) +{ + mrt_nexthop_t *curr, *dead; + + curr = mrt->nexthops; + + while( curr ) { + dead = curr; + curr = curr->next; + + free( dead ); + } + + /* easier to debug if it's NULL instead of garbage */ + mrt->nexthops = NULL; + mrt->activated_upstream_cnt = 0; + mrt->activated_downstream_cnt = 0; +} + +/* + * mrt_sources_find( table entry, source ) + * Finds an entry in source list for a multicast route. + */ +mrt_src_t *mrt_sources_find(mrt_table_t * mrt, u_int32_t src) +{ + mrt_src_t *curr; + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to find a source to an unknown route."); + return NULL; + } + + curr = mrt->sources; + + while( curr ) { + if ( curr->src_addr == src ) { + break; + } + + curr = curr->next; + } + + return curr; +} + +/* + * mrt_sources_add( table entry, source ) + * Adds an entry in source list for a multicast route. + */ +void mrt_sources_add(u_int32_t src, u_int32_t dest) +{ + mrt_table_t *mrt; + mrt_src_t *newsrc; + + mrt = mrt_table_find( dest ); + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to add a source to an unknown route."); + return; + } + + newsrc = mrt_sources_find( mrt, src ); + if ( newsrc ) { /* if it's already there, update it? */ + return; + } + + newsrc = (mrt_src_t *) malloc( sizeof( mrt_src_t ) ); + if ( !newsrc ) { + /* if no memory... quit */ + fprintf( stderr, "multicast_routing_table.c: Error allocating source entry.\n" ); + exit( -1 ); + } + + kernel_mrt_add_route( src, dest, 0 ); + + newsrc->src_addr = src; + newsrc->next = mrt->sources; + mrt->sources = newsrc; +} + +/* + * mrt_sources_remove_all( table entry ) + * Destroys every entry in source list for a multicast route. + */ +void mrt_sources_remove_all(mrt_table_t * mrt) +{ + mrt_src_t *curr, *dead; + + curr = mrt->sources; + + while( curr ) { + dead = curr; + curr = curr->next; + + kernel_mrt_del_route( dead->src_addr, mrt->grp_addr, 0 ); + + free( dead ); + } + + /* easier to debug if it's NULL instead of garbage */ + mrt->sources = NULL; +} + +/* + * mrt_origlist_find( table entry, orig ) + * Finds an entry in originator list for a multicast route. + */ +mrt_orig_t *mrt_origlist_find(mrt_table_t * mrt, u_int32_t orig) +{ + mrt_orig_t *curr; + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to find a source to an unknown route."); + return NULL; + } + + curr = mrt->origlist; + + while( curr ) { + if ( curr->orig_addr == orig ) { + break; + } + + curr = curr->next; + } + + return curr; +} + +/* + * mrt_origlist_add( table entry, orig, seqno, hcnt ) + * Adds an entry in originator list for a multicast route. + */ +mrt_orig_t * mrt_origlist_add(mrt_table_t *mrt, u_int32_t orig ) +{ + mrt_orig_t *neworig; + + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to add a source to an unknown route."); + return NULL; + } + + neworig = mrt_origlist_find( mrt, orig ); + if ( neworig ) { /* if it's already there, update it? */ + return neworig; + } + + neworig = (mrt_orig_t *) malloc( sizeof( mrt_orig_t ) ); + if ( !neworig ) { + fprintf( stderr, "multicast_routing_table.c: Error allocating orig entry.\n" ); + exit( -1 ); + } + + neworig->orig_addr = orig; + neworig->grp_seqno = 0; + neworig->grp_hcnt = 0xff; + neworig->next = mrt->origlist; + neworig->up = mrt; + mrt->origlist = neworig; + + /* do timeout stuff */ + neworig->cleanup_timer.handler = (timeout_func_t) &mrt_origlist_remove; + neworig->cleanup_timer.data = neworig; + timer_set_timeout( &( neworig->cleanup_timer ), RREP_WAIT_TIME ); + + return neworig; +} + +/* + * mrt_origlist_remove( orig entry ) + * For the timeout callback. Removes a single entry in the list. + */ +void mrt_origlist_remove(mrt_orig_t *entry) +{ + mrt_orig_t * curr = NULL, * prev = NULL; + + DEBUG( LOG_DEBUG, 0, "In origlist timeout." ); + + if ( !entry ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to remove a orig entry that didn't exist."); + return; + } + + timer_remove( &( entry->cleanup_timer ) ); + + if ( !( entry->up ) ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to remove a orig entry that didn't have a mrt."); + return; + } + + prev = NULL; + curr = entry->up->origlist; + + while( (curr) && (curr != entry) ) { + prev = curr; + curr = curr->next; + } + + if ( prev == NULL ) { + if ( curr == NULL ) { + /* empty list */ + DEBUG( LOG_DEBUG, 0, "Tried to remove from empty list." ); + return; + } else { + /* first element remove */ + DEBUG( LOG_DEBUG, 0, "Removed first element" ); + entry->up->origlist = NULL; + free( entry ); + } + } else { + if ( curr == NULL ) { + /* empty list */ + DEBUG( LOG_DEBUG, 0, "Tried to remove an unknown entry." ); + return; + } else { + /* somewhere in the middle or last element */ + DEBUG( LOG_DEBUG, 0, "Removed middle or last element."); + prev->next = curr->next; + free( entry ); + } + } +} + +/* + * mrt_table_set_leader( route, leader addr, leader hops ) + * Sets the leader and hopcount of a particular route entry (a multicast group). + */ +void mrt_table_set_leader(mrt_table_t * mrt, u_int32_t grp_leader_addr, u_int8_t leader_hcnt) +{ + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to set the leader of a route that doesn't exist."); + return; + } + + mrt->grp_leader_addr = grp_leader_addr; + mrt->leader_hcnt = leader_hcnt; +} + +/* + * mrt_table_set_leader_hcnt( route, leader hops ) + * Sets only the hopcount to the leader. Leader remains the same. + */ +void mrt_table_set_leader_hopcount(mrt_table_t * mrt, u_int8_t leader_hcnt) +{ + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to set the hop count of a route that doesn't exist."); + return; + } + + mrt->leader_hcnt = leader_hcnt; +} + +/* + * mrt_table_set_membership( route, boolean (memeber or not) ) + * Sets our flag true if we're a member of the group to which this is a route. + */ +void mrt_table_set_membership(mrt_table_t * mrt, u_int8_t ismember) +{ + if ( !mrt ) { + log(LOG_WARNING, 0, __FUNCTION__, + "Attempting to set membership of a route that doesn't exist."); + return; + } + + mrt->is_member = ismember; +} + +/* + * mrt_table_dump( ) + * Prints the routing table + */ +void mrt_table_dump(void) +{ + int index; + mrt_table_t * curr; + mrt_nexthop_t * hops; + mrt_orig_t * origs; + FILE *log; + struct timeval now; + struct tm *time; + + log=fopen("mrt_log", "a"); + if(log==NULL){ + perror("mrt_table_dump"); + } + + /* reset timer */ + timer_set_timeout( &( mrt_debug_timer ), 5000 ); + + gettimeofday(&now, NULL); + time = localtime(&now.tv_sec); + + fprintf( log, "\n# Entries: %d Time: %02d:%02d:%02d.%03ld\n", mrt_tbl.num_entries, + time->tm_hour, time->tm_min, time->tm_sec, now.tv_usec / 1000 ); + for ( index = 0; index < MRT_TABLESIZE; index++ ) + { + curr = mrt_tbl.tbl[index]; + while ( curr ) { + fprintf( log, "\t* * * * * * * * * * * * * * *\n" ); + fprintf( log, "\tGroup Addr[%s]\tLeader Addr[%s]\n", + ip_to_str( curr->grp_addr ), + ip_to_str( curr->grp_leader_addr ) ); + fprintf( log, "\tSeq #[%d]\tLeader Hop Count[%d]\n", + curr->grp_seqno, curr->leader_hcnt ); + fprintf( log, "\tMembership[%d]", curr->is_member ); + fprintf( log, "\tRouter[%d]\tLeader[%d]\n", curr->is_router, + curr->am_leader ); + fprintf( log, "\tBroken[%d]\tRepairing[%d]\n", curr->is_broken, + curr->in_repair ); + fprintf( log, "\tAct. Up. Count[%d]\tAct. Down. Count[%d]\n", + curr->activated_upstream_cnt, + curr->activated_downstream_cnt ); + fprintf( log, "\tNext Hops\n" ); + hops = curr->nexthops; + while( hops ) { + fprintf( log, "\t\t* * * * * * * *\n\t\tAddr[%s]\n", + ip_to_str( hops->addr ) ); + fprintf( log, "\t\tActivated[%d]\tDirection[%c]\n", + hops->activated, + ( ( hops->direction == MRT_UPSTREAM ) ? ( 'U' ) : ( 'D' ) ) ); + fprintf( log, "\t\tGroup Hopcount[%d]\tGroup Seq#[%d]\n", + hops->grp_hcnt, hops->grp_seqno ); + hops = hops->next; + } + fprintf( log, "\tOriginator List\n" ); + origs = curr->origlist; + while( origs ){ + fprintf( log, "\t\t* * * * * * * *\n\t\tAddr[%s]\n", + ip_to_str( origs->orig_addr ) ); + fprintf( log, "\t\tOrig Hopcount[%d]\tOrig Seq#[%d]\n", + origs->grp_hcnt, origs->grp_seqno ); + origs = origs->next; + } + curr = curr->next; + } + } + + fclose( log ); +} + +void mrt_table_become_leader(mrt_table_t *mrt){ + int i=0; + FILE *nh_log; + /* CHECK: better way to select interface */ + /* set first enabled interface's ip as the group leader ip */ + for(i=0; igrp_leader_addr=this_host.devs[i].ipaddr; + } + } + mrt->is_member=1; + mrt->is_router=1; + mrt->am_leader = 1; /* wahoo i'm now the REAL leader */ + mrt->grp_seqno=0; + mrt->leader_hcnt=0; + mrt->grph_update_cnt=1; + + /* send a hello */ + grph_send_callback(mrt); + + nh_log=fopen("nh_log", "a"); + fprintf(nh_log, "JOIN: %x\n", mrt->grp_addr); + fclose(nh_log); +} + +mrt_nexthop_t *mrt_table_get_best_upstream(mrt_table_t *mrt){ + mrt_nexthop_t *nexthop, *besthop=NULL; + + nexthop=mrt->nexthops; + + while(nexthop!=NULL) { + /* Before qualifying to be a upstream best hop, the next + hop must first, in fact be upstream. + - if that is true, then the current nexthop will take the + besthop position if either: + - there is not current besthop + - sequence number is greater than curr besthop + - seq no are equal, but we have a lesser hop count + */ + if(nexthop->direction == MRT_UPSTREAM && + (besthop == NULL || + (nexthop->grp_seqno > besthop->grp_seqno || + (nexthop->grp_seqno == besthop->grp_seqno && + nexthop->grp_hcnt < besthop->grp_hcnt) ) ) ) { + besthop=nexthop; + } + nexthop=nexthop->next; + } + + return besthop; +} + +mrt_nexthop_t *mrt_nexthop_find(mrt_table_t *mrt, uint32_t addr){ + mrt_nexthop_t *nexthop; + + nexthop=mrt->nexthops; + + while(nexthop!=NULL && nexthop->addr!=addr) { + nexthop=nexthop->next; + } + + return nexthop; +} + +void mrt_table_stop_routing(mrt_table_t *mrt){ + FILE *nh_log; + + mrt->is_router=0; + + nh_log=fopen("nh_log", "a"); + fprintf(nh_log, "LEAVE: %x\n", mrt->grp_addr); + fclose(nh_log); +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/multicast_routing_table.h ./maodv-umd/multicast_routing_table.h --- ./aodv-uu-0.6/multicast_routing_table.h Wed Dec 31 19:00:00 1969 +++ ./maodv-umd/multicast_routing_table.h Mon Feb 24 12:38:52 2003 @@ -0,0 +1,150 @@ +/***************************************************************************** + * + * Copyright (C) 2003 CSHCN, University of Maryland. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Authors: Dionysus Blazakis + * Jonathan Polley + * Dan Rusk + * Manish Karir + * + *****************************************************************************/ + +#ifndef MULTICAST_ROUTING_TABLE_H +#define MULTICAST_ROUTING_TABLE_H + +#ifndef NS_NO_GLOBALS +#include "defs.h" + +typedef struct mrt_table mrt_table_t; + +#define MRT_UPSTREAM 1 +#define MRT_DOWNSTREAM 2 + +/* struct for next hops */ +typedef struct _mrt_nexthop_t { + u_int32_t addr; + u_int8_t activated; + u_int8_t direction; + u_int8_t grp_hcnt; /* only for use with upstream hops */ + u_int32_t grp_seqno; /* only for use with upstream hops */ + struct _mrt_nexthop_t *next; +} mrt_nexthop_t; + +typedef struct _mrt_src_t { + u_int32_t src_addr; + struct _mrt_src_t *next; +} mrt_src_t; + +typedef struct _mrt_orig_t { + u_int32_t orig_addr; + u_int32_t grp_seqno; + u_int8_t grp_hcnt; + struct timer cleanup_timer; + + mrt_table_t * up; + struct _mrt_orig_t * next; +} mrt_orig_t; + +/* Route table entries */ +struct mrt_table { + u_int32_t grp_addr; + u_int32_t grp_leader_addr; + u_int32_t grp_seqno; + u_int8_t am_leader; /* are we the group leader? */ + + unsigned int ifindex; + u_int8_t leader_hcnt; + u_int8_t is_member; + u_int8_t is_router; + u_int8_t is_broken; + u_int8_t in_repair; + + struct timer mrt_timer; + struct timer grph_timer; + struct timer mact_timer; /* send mact to our upstream */ + struct timer prune_timer; + + mrt_nexthop_t *nexthops; + u_int8_t activated_upstream_cnt; + u_int16_t activated_downstream_cnt; + + mrt_src_t * sources; + mrt_orig_t * origlist; + + char grph_update_cnt; /* for if the next grph is to be an update */ + + struct mrt_table *next; +}; + + +#define MRT_TABLESIZE 64 /* Must be a power of 2 */ +#define MRT_TABLEMASK (MRT_TABLESIZE - 1) + +struct multicast_routing_table { + unsigned int num_entries; + mrt_table_t *tbl[MRT_TABLESIZE]; +}; + +#endif /* NS_NO_GLOBALS */ + +#ifndef NS_NO_DECLARATIONS + +struct multicast_routing_table mrt_tbl; + +void mrt_table_init(); +void mrt_table_destroy(); +mrt_table_t *mrt_table_insert(u_int32_t grp_addr, u_int32_t grp_leader_addr, + u_int32_t grp_seqno, + unsigned int ifindex, + u_int8_t leader_hcnt, + u_int8_t is_member); + +NS_INLINE mrt_table_t *mrt_table_update_timeout(mrt_table_t * mrt, + u_int32_t lifetime); +mrt_table_t *mrt_table_find(u_int32_t grp_addr); +void mrt_table_delete(u_int32_t grp_addr); +mrt_nexthop_t *mrt_table_get_activated_upstream(mrt_table_t * mrt); +mrt_nexthop_t *mrt_table_get_best_upstream(mrt_table_t *mrt); + +mrt_nexthop_t *mrt_nexthop_add(mrt_table_t * mrt, u_int32_t addr, + u_int8_t direction, u_int32_t grp_seqno); +void mrt_nexthop_remove(mrt_table_t * mrt, u_int32_t addr ); +void mrt_nexthop_activate(mrt_table_t * mrt, u_int32_t addr); +void mrt_nexthop_deactivate(mrt_table_t * mrt, u_int32_t addr); +void mrt_nexthop_remove_all(mrt_table_t * mrt); +mrt_nexthop_t *mrt_nexthop_find(mrt_table_t *mrt, uint32_t addr); + +mrt_src_t *mrt_sources_find(mrt_table_t * mrt, u_int32_t src); +void mrt_sources_add(u_int32_t src, u_int32_t dest); +void mrt_sources_remove_all(mrt_table_t * mrt); + +mrt_orig_t * mrt_origlist_find(mrt_table_t *mrt, u_int32_t orig); +mrt_orig_t * mrt_origlist_add(mrt_table_t *mrt, u_int32_t orig); +void mrt_origlist_remove(mrt_orig_t *entry); + +void mrt_table_set_leader(mrt_table_t * mrt, u_int32_t grp_leader_addr, u_int8_t leader_hcnt); +void mrt_table_set_leader_hopcount(mrt_table_t * mrt, u_int8_t leader_hcnt); +void mrt_table_become_leader(mrt_table_t *mrt); + +void mrt_table_set_membership(mrt_table_t * mrt, u_int8_t ismember); +void mrt_table_stop_routing(mrt_table_t *mrt); + +void mrt_table_dump(void); + +#endif /* NS_NO_DECLARATIONS */ + +#endif /* MULTICAST_ROUTING_TABLE_H */ diff -urN ./aodv-uu-0.6/ns-2.1b9a-aodv-uu-0.6.patch ./maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch --- ./aodv-uu-0.6/ns-2.1b9a-aodv-uu-0.6.patch Wed Nov 6 10:49:24 2002 +++ ./maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch Fri Nov 8 16:53:27 2002 @@ -5,8 +5,8 @@ # WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF # MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. # --# @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/Makefile.in,v 1.245 2002/03/15 19:01:01 ddutta Exp $ (LBL) -+# @(#) $Header: /mnt/core/ape/cvsroot/ape-sources/src/aodv-uu/ns-2.1b9a/Makefile.in,v 1.2 2002/10/05 19:29:15 bjwi7937 Exp $ (LBL) +-# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ (LBL) ++# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ (LBL) # # Various configurable paths (remember to edit Makefile.in, not Makefile) @@ -93,8 +93,8 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * -- * @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/common/packet.h,v 1.89 2002/05/30 17:44:03 haldar Exp $ (LBL) -+ * @(#) $Header: /mnt/core/ape/cvsroot/ape-sources/src/aodv-uu/ns-2.1b9a/common/packet.h,v 1.1 2002/08/28 12:33:37 bjwi7937 Exp $ (LBL) +- * @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ (LBL) ++ * @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ (LBL) */ #ifndef ns_packet_h @@ -129,8 +129,8 @@ priqueue.cc A simple priority queue with a remove packet function -- $Id: priqueue.cc,v 1.3 2002/03/14 01:18:09 haldar Exp $ -+ $Id: priqueue.cc,v 1.1 2002/08/28 12:33:38 bjwi7937 Exp $ +- $Id: ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ ++ $Id: ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ */ #include @@ -166,8 +166,8 @@ # OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF # SUCH DAMAGE. # --# @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcl/lib/ns-agent.tcl,v 1.24 2001/08/17 19:00:42 kfall Exp $ -+# @(#) $Header: /mnt/core/ape/cvsroot/ape-sources/src/aodv-uu/ns-2.1b9a/tcl/lib/ns-agent.tcl,v 1.1 2002/08/28 12:33:44 bjwi7937 Exp $ +-# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ ++# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ # # @@ -189,8 +189,8 @@ # OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF # SUCH DAMAGE. # --# @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcl/lib/ns-default.tcl,v 1.288 2002/05/31 23:11:30 haldar Exp $ -+# @(#) $Header: /mnt/core/ape/cvsroot/ape-sources/src/aodv-uu/ns-2.1b9a/tcl/lib/ns-default.tcl,v 1.5 2002/11/06 13:48:46 erno3431 Exp $ +-# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ ++# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ # @@ -218,8 +218,8 @@ # SUCH DAMAGE. # --# @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcl/lib/ns-lib.tcl,v 1.248 2002/06/06 00:28:08 haldar Exp $ -+# @(#) $Header: /mnt/core/ape/cvsroot/ape-sources/src/aodv-uu/ns-2.1b9a/tcl/lib/ns-lib.tcl,v 1.1 2002/08/28 12:33:44 bjwi7937 Exp $ +-# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ ++# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ # @@ -259,8 +259,8 @@ # OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF # SUCH DAMAGE. # --# @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcl/lib/ns-packet.tcl,v 1.46 2002/01/14 20:05:43 xuanc Exp $ -+# @(#) $Header: /mnt/core/ape/cvsroot/ape-sources/src/aodv-uu/ns-2.1b9a/tcl/lib/ns-packet.tcl,v 1.1 2002/08/28 12:33:44 bjwi7937 Exp $ +-# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ ++# @(#) $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ # # set up the packet format for the simulation # (initial version) @@ -279,8 +279,8 @@ * Ported from CMU/Monarch's code, appropriate copyright applies. * nov'98 -Padma. * -- * $Header: /nfs/jade/vint/CVSROOT/ns-2/trace/cmu-trace.cc,v 1.66 2002/04/01 23:07:28 buchheim Exp $ -+ * $Header: /mnt/core/ape/cvsroot/ape-sources/src/aodv-uu/ns-2.1b9a/trace/cmu-trace.cc,v 1.1 2002/08/28 12:33:46 bjwi7937 Exp $ +- * $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ ++ * $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ */ #include @@ -494,8 +494,8 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * -- * $Header: /nfs/jade/vint/CVSROOT/ns-2/trace/cmu-trace.h,v 1.13 2002/03/14 01:18:09 haldar Exp $ -+ * $Header: /mnt/core/ape/cvsroot/ape-sources/src/aodv-uu/ns-2.1b9a/trace/cmu-trace.h,v 1.1 2002/08/28 12:33:46 bjwi7937 Exp $ +- * $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ ++ * $Header: /dept/isr/labs/hnl/project/manet/maodv-umd/src/maodv-umd/ns-2.1b9a-aodv-uu-0.6.patch,v 1.1.1.1 2002/11/08 21:53:27 dblaze Exp $ */ /* Ported from CMU/Monarch's code, nov'98 -Padma.*/ diff -urN ./aodv-uu-0.6/packet_input.c ./maodv-umd/packet_input.c --- ./aodv-uu-0.6/packet_input.c Tue Nov 5 16:13:30 2002 +++ ./maodv-umd/packet_input.c Sat Feb 15 16:34:42 2003 @@ -44,6 +44,12 @@ #include "packet_queue.h" #include "packet_input.h" +#ifdef MAODV +#include "igmp.h" +#include "multicast_routing_table.h" +#include "multicast_packet_cache.h" +#endif + #define BUFSIZE 2048 extern int internet_gw_mode, wait_on_reboot, optimized_hellos; @@ -58,6 +64,24 @@ /* Set this if you want lots of debug printouts: */ /* #define DEBUG_PACKET */ +/* from + "Internetworking with TCP/IP: Volume II" + Second Edition + Douglas E. Comer, David L. Stevens */ +static u_int16_t my_ip_csum( unsigned short *buf, int nshorts ) +{ + u_int32_t sum; + + for( sum = 0; nshorts > 0; nshorts-- ) { + sum += *buf++; + } + + sum = ( sum >> 16 ) + ( sum & 0xffff ); + sum += (sum >> 16 ); + + return ~sum; +} + #ifndef NS_PORT static void die(struct ipq_handle *h) { @@ -106,11 +130,26 @@ static void packet_input(int fd) #endif { - rt_table_t *fwd_rt, *rev_rt, *next_hop_rt, *expired_rt = NULL; + rt_table_t *fwd_rt = NULL, *rev_rt, *next_hop_rt, *expired_rt = NULL; u_int32_t dest_addr, src_addr; u_int8_t rreq_flags = 0; unsigned int ifindex; struct ip_data *ipd = NULL; +#ifdef MAODV + /* This is to "hack" around the Linux UDP ip->id field which + remains zero unless you fragment a IP packet. Not likely. + + We just change the ip->id for each packet leaving + destined for a multicast address. There is really no + other way to work this in Linux. The source code states + that Linux was never intened to have a router + host for + multicast IP. + + The ip-id is needed to cache multicast packets to avoid + flooding a multicast packet around the network for ttl + hops. */ + static u_int16_t staticid = 0; +#endif #ifdef NS_PORT ifindex = NS_IFINDEX; // Always use ns interface @@ -168,8 +207,9 @@ dev_name = pkt->indev_name; else if (pkt->hook == 3) dev_name = pkt->outdev_name; - else + else { dev_name = NULL; + } /* We know from kaodv.c that this is an IP packet */ ip = (struct iphdr *) pkt->payload; @@ -200,8 +240,20 @@ DEBUG(LOG_INFO, 0, "setting G flag for RREQ to %s", ip_to_str(dest_addr)); #endif - - break; + break; +#ifdef MAODV + case IPPROTO_IGMP: + if(pkt->hook==3){ + igmp_process( (IGMP *) ((char *) ip + (ip->ihl << 2)) ); + + /* drop the packet after processing. */ + status = ipq_set_verdict(h, pkt->packet_id, NF_DROP, 0, NULL); + if (status < 0) + die(h); + return; + } + break; +#endif } #ifdef DEBUG_PACKET @@ -226,6 +278,74 @@ goto accept; #endif } + +#ifdef MAODV + if(IN_MULTICAST(dest_addr)){ + u_int8_t *pay; + u_int32_t size; + mrt_table_t *mrt=mrt_table_find(dest_addr); + + if(mrt==NULL || (!mrt->is_router && DEV_IFINDEX(ifindex).ipaddr!=src_addr)){ + /* we got a packet for which we have no entry */ + status = ipq_set_verdict(h, pkt->packet_id, NF_DROP, 0, NULL); + if (status < 0) + die(h); + return; + } + /* note: this is like an else... note the return */ + + if ( pkt->mark == 4 ) { + /* from our LOCAL_OUT hook. let's change the ip->id field */ + ip->id = htons(++staticid); + + /* now recalculate the chksum... wahoo! */ + /* CHECK: this could be more intelligent... */ + ip->check = 0; + ip->check = my_ip_csum( (unsigned short *) ip, ip->ihl * 2 ); + + } + + if(!mrt->is_router || mrt->is_broken ){ + /* we have an invalid route, do discovery. */ + size = pkt->data_len; + pay = (u_int8_t *) malloc( pkt->data_len ); + if ( pay == NULL ) { + perror( "in packet_input for multicast local out buffer." ); + exit( -1 ); + } + memcpy( pay, pkt->payload, size ); + + rreq_flags = rreq_flags | RREQ_JOIN; + mcast_packet_queue_add(pkt->packet_id, dest_addr, size, pay); + + check_duplicate( src_addr, ip->id ); + + goto mcast_route_discovery; + + }else{ + /* route is valid, packet wants out, send the packet along its way */ + if ( !check_duplicate( src_addr, ip->id ) ) { + status = ipq_set_verdict(h, pkt->packet_id, NF_DROP, 0, NULL); + if (status < 0) + die(h); + return; + } else { + mrt_sources_add( src_addr, dest_addr ); + mrt_table_update_timeout(mrt, ACTIVE_ROUTE_TIMEOUT); + + status = ipq_set_verdict( h, pkt->packet_id, NF_ACCEPT, + pkt->data_len, pkt->payload ); + if (status < 0) + die(h); + + /* we did our own accept! */ + /* goto accept; */ + return; + } + /***** never gets here... look above ****/ + } + } +#endif /* Find the entry of the neighboring node and the destination (if any). */ rev_rt = rt_table_find(src_addr); @@ -345,6 +465,10 @@ #else packet_queue_add(pkt->packet_id, dest_addr); +#ifdef MAODV + mcast_route_discovery: +#endif /* MAODV */ + /* Already seeking the destination? Then do not allocate any memory or generate a RREQ. */ if (seek_list_find(dest_addr)) @@ -355,7 +479,7 @@ Host Unreachable in case we don't find a route... */ if (src_addr == DEV_IFINDEX(ifindex).ipaddr) { ipd = (struct ip_data *) malloc(sizeof(struct ip_data)); - if (ipd < 0) { + if (ipd == NULL) { perror("Malloc for IP data failed!"); exit(-1); } @@ -368,7 +492,7 @@ if (fwd_rt && (fwd_rt->flags & RT_REPAIR)) rreq_local_repair(expired_rt, src_addr, ipd); else - rreq_route_discovery(dest_addr, rreq_flags, ipd); + rreq_route_discovery(dest_addr, rreq_flags, ipd, 0); return; diff -urN ./aodv-uu-0.6/packet_queue.c ./maodv-umd/packet_queue.c --- ./aodv-uu-0.6/packet_queue.c Tue Nov 5 16:13:30 2002 +++ ./maodv-umd/packet_queue.c Fri Feb 14 13:07:59 2003 @@ -34,6 +34,10 @@ #include "timer_queue.h" #include "aodv_timeout.h" +#ifdef MAODV +#include "multicast_routing_table.h" +#endif + extern struct ipq_handle *h; #endif @@ -72,6 +76,10 @@ #else ipq_set_verdict(h, tmp->id, NF_DROP, 0, NULL); #endif /* NS_PORT */ + if ( tmp->payload != NULL ) { + free( tmp->payload ); + } + free(tmp); count++; } @@ -112,6 +120,11 @@ tmp = curr; curr = curr->next; + + if ( tmp->payload ) { + free( tmp->payload ); + } + free(tmp); count++; PQ.len--; @@ -127,6 +140,7 @@ return count; } + /* Buffer a packet in a FIFO queue. Implemented as a linked list, where we add elements at the end and remove at the beginning.... */ @@ -170,6 +184,10 @@ qp->id = id; #endif qp->dest_addr = dest_addr; + + qp->payload = NULL; + qp->size = 0; + qp->next = NULL; gettimeofday(&qp->q_time, NULL); @@ -193,6 +211,53 @@ #endif } +void mcast_packet_queue_add(unsigned long id, u_int32_t dest_addr, + u_int32_t s, u_int8_t *pay) +{ + struct q_pkt *qp; + + if (PQ.len >= MAX_QUEUE_LENGTH) { + if (PQ.head) { + qp = PQ.head; + PQ.head = PQ.head->next; + + ipq_set_verdict(h, qp->id, NF_DROP, 0, NULL); + PQ.len--; + if ( qp->payload ) { + free( qp->payload ); + } + free(qp); + } + } + + if ((qp = (struct q_pkt *) malloc(sizeof(struct q_pkt))) == NULL) { + fprintf(stderr, "Malloc failed!\n"); + exit(-1); + } + + qp->id = id; + qp->dest_addr = dest_addr; + + qp->payload = pay; + qp->size = s; + + qp->next = NULL; + + gettimeofday(&qp->q_time, NULL); + + if (PQ.head == NULL) + PQ.head = qp; + + if (PQ.tail != NULL) + PQ.tail->next = qp; + + PQ.tail = qp; + + PQ.len++; + +} + + int NS_CLASS packet_queue_drop(u_int32_t dest_addr) { int count = 0; @@ -220,6 +285,9 @@ tmp = curr; curr = curr->next; + if ( tmp->payload ) { + free( tmp->payload ); + } free(tmp); count++; PQ.len--; @@ -278,6 +346,9 @@ tmp = curr; curr = curr->next; + if ( tmp->payload ) { + DEBUG(LOG_DEBUG, 0, "Sent a multicast queued packet from wrong function." ); + } free(tmp); count++; PQ.len--; @@ -303,3 +374,74 @@ return count; } + +#ifdef MAODV + +int NS_CLASS mcast_packet_queue_send(u_int32_t dest_addr) +{ + int count = 0; + struct q_pkt *curr, *tmp, *prev; + mrt_table_t *mrt; +#ifdef NS_PORT + double delay = 0; +#define ARP_DELAY 0.005 +#endif + + mrt = mrt_table_find(dest_addr); + + if (!mrt || !mrt->is_router ) + return -1; + + curr = PQ.head; + prev = NULL; + + while (curr != NULL) { + if (curr->dest_addr == dest_addr) { + ipq_set_verdict(h, curr->id, NF_ACCEPT, curr->size, + curr->payload); + + if (prev == NULL) + PQ.head = curr->next; + else + prev->next = curr->next; + + /* If we remove the last element in the queue we must update the + tail pointer */ + if (curr->next == NULL) + PQ.tail = prev; + + tmp = curr; + curr = curr->next; + if ( tmp->payload ) { + free( tmp->payload ); + } + free(tmp); + count++; + PQ.len--; + continue; + } + prev = curr; + curr = curr->next; + } + + /* Update rt timeouts */ + if (dest_addr != DEV_IFINDEX(mrt->ifindex).ipaddr) { + /* TODO: CHECK: Update multicast route table timer. */ + /* rt_table_update_timeout(rt, ACTIVE_ROUTE_TIMEOUT); */ + + /* + next_hop_rt = rt_table_find(rt->next_hop); + + if (next_hop_rt && next_hop_rt->state == VALID && + next_hop_rt->dest_addr != rt->dest_addr) + rt_table_update_timeout(next_hop_rt, ACTIVE_ROUTE_TIMEOUT); + */ + } + + DEBUG(LOG_INFO, 0, "SENT %d packets to %s qlen=%u", + count, ip_to_str(dest_addr), PQ.len); + + return count; +} + +#endif /* MAODV */ diff -urN ./aodv-uu-0.6/packet_queue.h ./maodv-umd/packet_queue.h --- ./aodv-uu-0.6/packet_queue.h Sun Nov 3 19:22:48 2002 +++ ./maodv-umd/packet_queue.h Fri Jan 17 15:15:21 2003 @@ -38,6 +38,8 @@ #else unsigned long id; #endif + u_int8_t * payload; + u_int32_t size; struct q_pkt *next; }; @@ -58,6 +60,11 @@ #else void packet_queue_add(unsigned long id, u_int32_t dest_addr); #endif + +int mcast_packet_queue_send(u_int32_t dest_addr); +void mcast_packet_queue_add(unsigned long id, u_int32_t dest_addr, + u_int32_t s, u_int8_t *pay); + void packet_queue_init(); void packet_queue_destroy(); int packet_queue_drop(u_int32_t dest_addr); diff -urN ./aodv-uu-0.6/params.h ./maodv-umd/params.h --- ./aodv-uu-0.6/params.h Thu Oct 10 11:19:41 2002 +++ ./maodv-umd/params.h Fri Jan 24 12:29:12 2003 @@ -56,4 +56,9 @@ #define TTL_INCREMENT 2 #define TTL_THRESHOLD 7 +/* MAODV params */ +#define GROUP_HELLO_INTERVAL 5000 +#define RREP_WAIT_TIME 10000 +#define PRUNE_TIMEOUT 2 * RREP_WAIT_TIME + #endif diff -urN ./aodv-uu-0.6/routing_table.c ./maodv-umd/routing_table.c --- ./aodv-uu-0.6/routing_table.c Wed Nov 6 10:43:35 2002 +++ ./maodv-umd/routing_table.c Thu Nov 21 14:39:13 2002 @@ -39,6 +39,8 @@ #include "seek_list.h" #endif /* NS_PORT */ +#include + static unsigned int hashing(u_int32_t * addr, hash_value * hash); #ifndef NS_PORT @@ -109,6 +111,9 @@ rt_tbl.num_entries++; + /* trying to track weird route bug */ + assert(!(dest_addr == DEV_NR(0).ipaddr == next )); + DEBUG(LOG_INFO, 0, "Inserting %s (bucket %d) next hop %s", ip_to_str(dest_addr), index, ip_to_str(next)); diff -urN ./aodv-uu-0.6/seek_list.c ./maodv-umd/seek_list.c --- ./aodv-uu-0.6/seek_list.c Mon Oct 7 11:42:21 2002 +++ ./maodv-umd/seek_list.c Wed Feb 12 13:31:59 2003 @@ -46,7 +46,9 @@ seek_list_t *NS_CLASS seek_list_insert(u_int32_t dest_addr, u_int32_t dest_seqno, int ttl, u_int8_t flags, - struct ip_data *ipd) + struct ip_data *ipd, + u_int16_t grp_hcnt, + u_int32_t grp_addr ) { seek_list_t *entry; @@ -61,6 +63,8 @@ entry->reqs = 0; entry->ttl = ttl; entry->ipd = ipd; + entry->grp_hcnt = grp_hcnt; + entry->grp_addr = grp_addr; entry->seek_timer.handler = &NS_CLASS route_discovery_timeout; entry->seek_timer.data = entry; entry->next = seek_list_head; @@ -69,6 +73,38 @@ return entry; } +#ifdef MAODV +int NS_CLASS seek_list_remove_mcast(u_int32_t dest_addr, u_int32_t grp_addr) +{ + seek_list_t *curr, *prev; + + curr = seek_list_head; + prev = NULL; + + while (curr != NULL) { + if ((curr->dest_addr == dest_addr) && + (curr->grp_addr == grp_addr)) { + + if (prev == NULL) + seek_list_head = curr->next; + else + prev->next = curr->next; + + /* Make sure any timers are removed */ + timer_remove(&curr->seek_timer); + + if (curr->ipd) + free(curr->ipd); + free(curr); + return 1; + } + prev = curr; + curr = curr->next; + } + return 0; +} +#endif + int NS_CLASS seek_list_remove(u_int32_t dest_addr) { seek_list_t *curr, *prev; @@ -112,6 +148,28 @@ return NULL; } +#ifdef MAODV +/* note: This function call seems misleading at first because + most of the time a multicast RREQ should be destined for + a group, but tree merge is destined for the leader and contains + the group information in an extension. */ +seek_list_t *NS_CLASS seek_list_find_mcast(u_int32_t dest_addr, + u_int32_t grp_addr) +{ + seek_list_t *entry; + + entry = seek_list_head; + + while (entry != NULL) { + if ( (entry->dest_addr == dest_addr) && + (entry->grp_addr == grp_addr) ) + return entry; + entry = entry->next; + } + return NULL; +} +#endif + #ifdef SEEK_LIST_DEBUG void NS_CLASS seek_list_print() { diff -urN ./aodv-uu-0.6/seek_list.h ./maodv-umd/seek_list.h --- ./aodv-uu-0.6/seek_list.h Wed Jun 19 11:28:34 2002 +++ ./maodv-umd/seek_list.h Wed Feb 12 13:31:59 2003 @@ -42,6 +42,8 @@ u_int8_t flags; /* The flags we are using for resending the RREQ */ int reqs; int ttl; + u_int16_t grp_hcnt; + u_int32_t grp_addr; struct timer seek_timer; struct seek_list *next; } seek_list_t; @@ -49,10 +51,18 @@ #ifndef NS_NO_DECLARATIONS seek_list_t *seek_list_insert(u_int32_t dest_addr, u_int32_t dest_seqno, - int ttl, u_int8_t flags, struct ip_data *ipd); + int ttl, u_int8_t flags, struct ip_data *ipd, + u_int16_t grp_hcnt, u_int32_t grp_addr); int seek_list_remove(u_int32_t dest_addr); seek_list_t *seek_list_find(u_int32_t dest_addr); +#ifdef MAODV +seek_list_t *seek_list_find_mcast(u_int32_t dest_addr, + u_int32_t grp_addr); +int NS_CLASS seek_list_remove_mcast(u_int32_t dest_addr, + u_int32_t grp_addr); +#endif + #ifdef NS_PORT #ifdef SEEK_LIST_DEBUG void seek_list_print();