/* Copyright (c) 1997, 1998 Carnegie Mellon University. All Rights Reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 3. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. The WCETT code developed by the CMU/MONARCH group was optimized and tuned by Samir Das and Mahesh Marina, University of Cincinnati. The work was partially done in Sun Microsystems. Modified for gratuitous replies by Anant Utgikar, 09/16/02. */ //#include #include #include #include #include //#include #define max(a,b) ( (a) > (b) ? (a) : (b) ) #define CURRENT_TIME Scheduler::instance().clock() //#define DEBUG //#define ERROR #ifdef DEBUG static int extra_route_reply = 0; static int limit_route_request = 0; static int route_request = 0; #endif /* TCL Hooks */ int hdr_wcett::offset_; static class WCETTHeaderClass : public PacketHeaderClass { public: WCETTHeaderClass() : PacketHeaderClass("PacketHeader/WCETT", sizeof(hdr_all_wcett)) { bind_offset(&hdr_wcett::offset_); } } class_rtProtoWCETT_hdr; static class WCETTclass : public TclClass { public: WCETTclass() : TclClass("Agent/WCETT") {} TclObject* create(int argc, const char*const* argv) { assert(argc == 5); //return (new WCETT((nsaddr_t) atoi(argv[4]))); return (new WCETT((nsaddr_t) Address::instance().str2addr(argv[4]))); } } class_rtProtoWCETT; int WCETT::command(int argc, const char*const* argv) { if(argc == 2) { Tcl& tcl = Tcl::instance(); if(strncasecmp(argv[1], "id", 2) == 0) { tcl.resultf("%d", index); return TCL_OK; } if(strncasecmp(argv[1], "start", 2) == 0) { btimer.handle((Event*) 0); #ifndef WCETT_LINK_LAYER_DETECTION htimer.handle((Event*) 0); ntimer.handle((Event*) 0); #endif // LINK LAYER DETECTION rtimer.handle((Event*) 0); return TCL_OK; } } else if(argc == 3) { if(strcmp(argv[1], "index") == 0) { index = atoi(argv[2]); return TCL_OK; } else if(strcmp(argv[1], "log-target") == 0 || strcmp(argv[1], "tracetarget") == 0) { logtarget = (Trace*) TclObject::lookup(argv[2]); if(logtarget == 0) return TCL_ERROR; return TCL_OK; } else if(strcmp(argv[1], "drop-target") == 0) { int stat = rqueue.command(argc,argv); if (stat != TCL_OK) return stat; return Agent::command(argc, argv); } //[Ramon] else if(strcmp(argv[1], "if-queue") == 0) { ifqueue = (PriQueue*) TclObject::lookup(argv[2]); ifqueuelist[nIfaces]= ifqueue; if (ifqueuelist[nIfaces]) return TCL_OK; return TCL_ERROR; } else if (strcmp(argv[1], "port-dmux") == 0) { dmux_ = (PortClassifier *)TclObject::lookup(argv[2]); if (dmux_ == 0) { fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__, argv[1], argv[2]); return TCL_ERROR; } return TCL_OK; } else if(strcmp(argv[1], "node") == 0) { node_= (MobileNode*) TclObject::lookup(argv[2]); if (node_) { return TCL_OK; } return TCL_ERROR; } } else if (argc == 4){ //[Ramon] if(strcmp(argv[1], "if-queue") == 0) { ifqueue = (PriQueue*) TclObject::lookup(argv[3]); int temp_=atoi(argv[2]); if (temp_==nIfaces){ nIfaces++; } ifqueuelist[temp_]= ifqueue; if (ifqueuelist[temp_]) return TCL_OK; return TCL_ERROR; } if (strcmp(argv[1],"target")==0 ){ int temp=atoi(argv[2]); if (temp == nIfaces){ nIfaces++; } targetlist[temp]=(NsObject *) TclObject::lookup(argv[3]); if(targetlist[temp]) { return TCL_OK; } return TCL_ERROR; } } return Agent::command(argc, argv); } /* Constructor */ WCETT::WCETT(nsaddr_t id) : Agent(PT_WCETT), btimer(this), htimer(this), ntimer(this), rtimer(this), lrtimer(this), rqueue(),nIfaces(0),ChannelAssignTimer_(this),hctimer(this),hellocounter(0){ index = id; seqno = 2; bid = 1; LIST_INIT(&nbhead); LIST_INIT(&bihead); logtarget = 0; ifqueue = 0; //carmen for (int i=0;iid_purge(); Scheduler::instance().schedule(this, &intr, BCAST_ID_SAVE); } WCETTHelloTimer:: WCETTHelloTimer(WCETT* a) : agent(a){ } void WCETTHelloTimer::handle(Event*) { agent->sendHello(); //change the hello to broadcast at one second interval double interval=HELLO_INTERVAL; assert(interval >= 0); Scheduler::instance().schedule(this, &intr, interval); } void WCETTNeighborTimer::handle(Event*) { agent->nb_purge(); Scheduler::instance().schedule(this, &intr, HELLO_INTERVAL); } void WCETTRouteCacheTimer::handle(Event*) { //agent->rt_purge(); #define FREQUENCY 0.5 // sec //Scheduler::instance().schedule(this, &intr, FREQUENCY); } void WCETTLocalRepairTimer::handle(Event* p) { // SRD: 5/4/99 wcett_rt_entry *rt; struct hdr_ip *ih = HDR_IP( (Packet *)p); /* you get here after the timeout in a local repair attempt */ /* fprintf(stderr, "%s\n", __FUNCTION__); */ rt = agent->rtable.rt_lookup(ih->daddr()); if (rt && rt->rt_flags != RTF_UP) { // route is yet to be repaired // I will be conservative and bring down the route // and send route errors upstream. /* The following assert fails, not sure why */ /* assert (rt->rt_flags == RTF_IN_REPAIR); */ //rt->rt_seqno++; agent->rt_down(rt); // send RERR #ifdef DEBUG fprintf(stderr,"Node %d: Dst - %d, failed local repair\n",index, rt->rt_dst); #endif } Packet::free((Packet *)p); } /* Channel Assignment Timer operation. */ void WCETTChannelAssignTimer::expire(Event *) { a_->ChannelAssign(); resched(0.1); } void WCETTHelloCounterTimer::expire(Event *) { resched(20); } /* Broadcast ID Management Functions */ void WCETT::id_insert(nsaddr_t id, u_int32_t bid) { BroadcastID *b = new BroadcastID(id, bid); assert(b); b->expire = CURRENT_TIME + BCAST_ID_SAVE; LIST_INSERT_HEAD(&bihead, b, link); } /* SRD */ bool WCETT::id_lookup(nsaddr_t id, u_int32_t bid) { BroadcastID *b = bihead.lh_first; // Search the list for a match of source and bid for( ; b; b = b->link.le_next) { if ((b->src == id) && (b->id == bid)) return true; } return false; } void WCETT::id_purge() { BroadcastID *b = bihead.lh_first; BroadcastID *bn; double now = CURRENT_TIME; for(; b; b = bn) { bn = b->link.le_next; if(b->expire <= now) { LIST_REMOVE(b,link); delete b; } } } /* Helper Functions */ double WCETT::PerHopTime(wcett_rt_entry *rt) { int num_non_zero = 0, i; double total_latency = 0.0; if (!rt) return ((double) NODE_TRAVERSAL_TIME ); for (i=0; i < MAX_HISTORY; i++) { if (rt->rt_disc_latency[i] > 0.0) { num_non_zero++; total_latency += rt->rt_disc_latency[i]; } } if (num_non_zero > 0) return(total_latency / (double) num_non_zero); else return((double) NODE_TRAVERSAL_TIME); } /* Link Failure Management Functions */ static void wcett_rt_failed_callback(Packet *p, void *arg) { ((WCETT*) arg)->rt_ll_failed(p); } /* * This routine is invoked when the link-layer reports a route failed. */ void WCETT::rt_ll_failed(Packet *p) { struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); wcett_rt_entry *rt; nsaddr_t broken_nbr = ch->next_hop_; #ifndef WCETT_LINK_LAYER_DETECTION drop(p, DROP_RTR_MAC_CALLBACK); #else /* * Non-data packets and Broadcast Packets can be dropped. */ if(! DATA_PACKET(ch->ptype()) || (u_int32_t) ih->daddr() == IP_BROADCAST) { drop(p, DROP_RTR_MAC_CALLBACK); return; } log_link_broke(p); if((rt = rtable.rt_lookup(ih->daddr())) == 0) { drop(p, DROP_RTR_MAC_CALLBACK); return; } log_link_del(ch->next_hop_); #ifdef WCETT_LOCAL_REPAIR /* if the broken link is closer to the dest than source, attempt a local repair. Otherwise, bring down the route. */ if (ch->num_forwards() > rt->rt_hops) { local_rt_repair(rt, p); // local repair // retrieve all the packets in the ifq using this link, // queue the packets for which local repair is done, return; } else #endif // LOCAL REPAIR { drop(p, DROP_RTR_MAC_CALLBACK); // Do the same thing for other packets in the interface queue using the // broken link -Mahesh while((p = ifqueue->filter(broken_nbr))) { drop(p, DROP_RTR_MAC_CALLBACK); } nb_delete(broken_nbr); } #endif // LINK LAYER DETECTION } void WCETT::handle_link_failure(nsaddr_t id) { wcett_rt_entry *rt, *rtn; Packet *rerr = Packet::alloc(); struct hdr_wcett_error *re = HDR_WCETT_ERROR(rerr); re->DestCount = 0; for(rt = rtable.head(); rt; rt = rtn) { // for each rt entry rtn = rt->rt_link.le_next; if ((rt->rt_hops != INFINITY2) && (rt->rt_nexthop == id) ) { assert (rt->rt_flags == RTF_UP); assert((rt->rt_seqno%2) == 0); rt->rt_seqno++; re->unreachable_dst[re->DestCount] = rt->rt_dst; re->unreachable_dst_seqno[re->DestCount] = rt->rt_seqno; #ifdef DEBUG fprintf(stderr, "%s(%f): %d\t(%d\t%u\t%d)\n", __FUNCTION__, CURRENT_TIME, index, re->unreachable_dst[re->DestCount], re->unreachable_dst_seqno[re->DestCount], rt->rt_nexthop); #endif // DEBUG re->DestCount += 1; rt_down(rt); } // remove the lost neighbor from all the precursor lists rt->pc_delete(id); } if (re->DestCount > 0) { #ifdef DEBUG fprintf(stderr, "%s(%f): %d\tsending RERR...\n", __FUNCTION__, CURRENT_TIME, index); #endif // DEBUG sendError(rerr, false); } else { Packet::free(rerr); } } void WCETT::local_rt_repair(wcett_rt_entry *rt, Packet *p) { #ifdef DEBUG fprintf(stderr,"%s: Dst - %d\n", __FUNCTION__, rt->rt_dst); #endif // Buffer the packet rqueue.enque(p); // mark the route as under repair rt->rt_flags = RTF_IN_REPAIR; sendRequest(rt->rt_dst); // set up a timer interrupt Scheduler::instance().schedule(&lrtimer, p->copy(), rt->rt_req_timeout); } void WCETT::rt_update(wcett_rt_entry *rt, u_int32_t seqnum, u_int16_t metric, nsaddr_t nexthop, double expire_time) { rt->rt_seqno = seqnum; rt->rt_hops = metric; rt->rt_flags = RTF_UP; rt->rt_nexthop = nexthop; rt->rt_expire = expire_time; } void WCETT::rt_down(wcett_rt_entry *rt) { /* * Make sure that you don't "down" a route more than once. */ if(rt->rt_flags == RTF_DOWN) { return; } // assert (rt->rt_seqno%2); // is the seqno odd? rt->rt_last_hop_count = rt->rt_hops; rt->rt_hops = INFINITY2; rt->rt_flags = RTF_DOWN; rt->rt_nexthop = 0; rt->rt_expire = 0; } /* rt_down function */ /* Route Handling Functions */ void WCETT::rt_resolve(Packet *p) { struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); wcett_rt_entry *rt,*rt0; int bestroute=0; double bestmetric=0; double delay = 0.0; /* * Set the transmit failure callback. That * won't change. */ ch->xmit_failure_ = wcett_rt_failed_callback; ch->xmit_failure_data_ = (void*) this; rt = rtable.rt_lookup(ih->daddr()*10); if(rt == 0) { rt = rtable.rt_add(ih->daddr()*10); node_->PacketPr_.RtEntryIndex_.add_rt_entry(ih->daddr()); } //to find out the best route carmen for(int i=0;i<10;i++) { rt = rtable.rt_lookup((int)ih->daddr()*10+i); if(rt) { double rtmetric=ChannelETTCal(rt); if (bestmetricdaddr()*10+bestroute); if(rt0) { if(rt0->rt_flags == RTF_UP) { for(int i=0;i<20;i++) { ch->rtdecision_[i].nodeid=rt0->rt_linkstate[i].node1; ch->rtdecision_[i].channel=rt0->rt_linkstate[i].currentchannel; }//for //first handle the bufferpacket Packet *buf_pkt; while((buf_pkt = rqueue.deque(rt0->rt_dst))) { assert (rt0->rt_flags == RTF_UP); // Delay them a little to help ARP. Otherwise ARP // may drop packets. -SRD 5/23/99 for(int i=0;i<20;i++) { struct hdr_cmn *chtmp= HDR_CMN(buf_pkt); chtmp->rtdecision_[i].nodeid=rt0->rt_linkstate[i].node1; chtmp->rtdecision_[i].channel=rt0->rt_linkstate[i].currentchannel; } handleforward(rt0, buf_pkt, delay); delay += ARP_DELAY; } //then //handle the current packet handleforward(rt0,p,NO_DELAY); } //if rt_flag==up /* * if I am the source of the packet, then do a Route Request. */ else if (ih->saddr() == index) { rqueue.enque(p); sendRequest(rt0->rt_dst); } /* * A local repair is in progress. Buffer the packet. */ else if (rt0->rt_flags == RTF_IN_REPAIR) { rqueue.enque(p); } /* * I am trying to forward a packet for someone else to which * I don't have a route. */ else { Packet *rerr = Packet::alloc(); struct hdr_wcett_error *re = HDR_WCETT_ERROR(rerr); /* * For now, drop the packet and send error upstream. * Now the route errors are broadcast to upstream * neighbors - Mahesh 09/11/99 */ assert (rt0->rt_flags == RTF_DOWN); re->DestCount = 0; re->unreachable_dst[re->DestCount] = rt0->rt_dst; re->unreachable_dst_seqno[re->DestCount] = rt0->rt_seqno; re->DestCount += 1; #ifdef DEBUG fprintf(stderr, "%s: sending RERR...\n", __FUNCTION__); #endif sendError(rerr, false); drop(p, DROP_RTR_NO_ROUTE); } } // if (rt0) } void WCETT::rt_purge() { wcett_rt_entry *rt, *rtn; double now = CURRENT_TIME; double delay = 0.0; Packet *p; for(rt = rtable.head(); rt; rt = rtn) { // for each rt entry rtn = rt->rt_link.le_next; if ((rt->rt_flags == RTF_UP) && (rt->rt_expire < now)) { // if a valid route has expired, purge all packets from // send buffer and invalidate the route. assert(rt->rt_hops != INFINITY2); while((p = rqueue.deque(rt->rt_dst))) { #ifdef DEBUG fprintf(stderr, "%s: calling drop()\n", __FUNCTION__); #endif // DEBUG drop(p, DROP_RTR_NO_ROUTE); } rt->rt_seqno++; assert (rt->rt_seqno%2); rt_down(rt); } else if (rt->rt_flags == RTF_UP) { // If the route is not expired, // and there are packets in the sendbuffer waiting, // forward them. This should not be needed, but this extra // check does no harm. assert(rt->rt_hops != INFINITY2); while((p = rqueue.deque(rt->rt_dst))) { forward (rt, p, delay); delay += ARP_DELAY; } } else if (rqueue.find(rt->rt_dst)) // If the route is down and // if there is a packet for this destination waiting in // the sendbuffer, then send out route request. sendRequest // will check whether it is time to really send out request // or not. // This may not be crucial to do it here, as each generated // packet will do a sendRequest anyway. sendRequest(rt->rt_dst); } } /* Packet Reception Routines */ void WCETT::recv(Packet *p, Handler*) { struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); assert(initialized()); //assert(p->incoming == 0); // XXXXX NOTE: use of incoming flag has been depracated; In order to track direction of pkt flow, direction_ in hdr_cmn is used instead. see packet.h for details. if(ch->ptype() == PT_WCETT) { ih->ttl_ -= 1; recvWCETT(p); return; } /* * Must be a packet I'm originating... */ if((ih->saddr() == index) && (ch->num_forwards() == 0)) { /* * Add the IP Header */ ch->size() += IP_HDR_LEN; // Added by Parag Dadhania && John Novatnack to handle broadcasting if ( (u_int32_t)ih->daddr() != IP_BROADCAST) ih->ttl_ = NETWORK_DIAMETER; } /* * I received a packet that I sent. Probably * a routing loop. */ else if(ih->saddr() == index) { drop(p, DROP_RTR_ROUTE_LOOP); return; } /* * Packet I'm forwarding... */ else { /* * Check the TTL. If it is zero, then discard. */ if(--ih->ttl_ == 0) { drop(p, DROP_RTR_TTL); return; } } // Added by Parag Dadhania && John Novatnack to handle broadcasting if ( (u_int32_t)ih->daddr() != IP_BROADCAST) { rt_resolve(p); } else { forward((wcett_rt_entry*) 0, p, NO_DELAY); } } void WCETT::recvWCETT(Packet *p) { struct hdr_wcett *ah = HDR_WCETT(p); assert(HDR_IP (p)->sport() == RT_PORT); assert(HDR_IP (p)->dport() == RT_PORT); /* * Incoming Packets. */ switch(ah->ah_type) { case WCETTTYPE_RREQ: recvRequest(p); break; case WCETTTYPE_RREP: recvReply(p); break; case WCETTTYPE_RERR: recvError(p); break; case WCETTTYPE_HELLO: recvHello(p); break; case WCETTTYPE_HELLO_ACK: recvACK(p); break; default: fprintf(stderr, "Invalid WCETT type (%x)\n", ah->ah_type); exit(1); } } void WCETT::recvRequest(Packet *p) { struct hdr_ip *ih = HDR_IP(p); struct hdr_cmn *ch = HDR_CMN(p); struct hdr_wcett_request *rq = HDR_WCETT_REQUEST(p); wcett_rt_entry *rt; /* * Drop if: * - I'm the source * - I recently heard this request. */ if(rq->rq_src == index) { #ifdef DEBUG fprintf(stderr, "%s: got my own REQUEST\n", __FUNCTION__); #endif // DEBUG Packet::free(p); return; } if (id_lookup(rq->rq_src, rq->rq_bcast_id)) { #ifdef DEBUG fprintf(stderr, "%s: discarding request\n", __FUNCTION__); #endif // DEBUG Packet::free(p); return; } /* * Cache the broadcast ID */ id_insert(rq->rq_src, rq->rq_bcast_id); /* * We are either going to forward the REQUEST or generate a * REPLY. Before we do anything, we make sure that the REVERSE * route is in the route table. */ wcett_rt_entry *rt0; // rt0 is the reverse route //carmen //look up multiple entry from the route table. //rt0 = rtable.rt_lookup(rq->rq_src); bool jumpoutloop=false; for(int i=0;i<10;i++) { rt0=rtable.rt_lookup(rq->rq_src*10+i); //if at least one route entry is found then jump out of the loop if(rt0!=0){ jumpoutloop=true; } if(jumpoutloop==true) break; } if(rt0 == 0) { /* if not in the route table */ // create an entry for the reverse route. rt0 = rtable.rt_add(rq->rq_src*10); //increase the route index in route table rt0->rt_expire = max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE)); rt0->rt_flags == RTF_UP; //add the route info in the request for the pevious hop rq->RouteRecord[rq->rq_hop_count].nodeid=index; int iface=0; if(nIfaces){ iface=HDR_CMN(p)->localif(); rq->RouteRecord[rq->rq_hop_count-1].channel=iface; rq->RouteRecord[rq->rq_hop_count-1].ETT=ChannelETT[ih->saddr()][iface]; rt0->rt_if=iface; } else { rq->RouteRecord[rq->rq_hop_count-1].channel=0; rq->RouteRecord[rq->rq_hop_count-1].ETT=ChannelETT[ih->saddr()][0]; rt0->rt_if=0; } for (int i=rq->rq_hop_count-1;i>=0;i--) { rt0->rt_linkstate[i].node1=rq->RouteRecord[i].nodeid; rt0->rt_linkstate[i].linkETT=rq->RouteRecord[i].ETT; rt0->rt_linkstate[i].currentchannel=rq->RouteRecord[i].channel; } //also add my self into the route; rt0->rt_linkstate[rq->rq_hop_count].node1=index; if(nIfaces){ iface=HDR_CMN(p)->localif(); rt0->rt_linkstate[rq->rq_hop_count].currentchannel=iface; rt0->rt_linkstate[rq->rq_hop_count].linkETT=ChannelETT[ih->saddr()][iface]; }else { rt0->rt_linkstate[rq->rq_hop_count].currentchannel=0; rt0->rt_linkstate[rq->rq_hop_count].linkETT=ChannelETT[ih->saddr()][0]; } node_->PacketPr_.RtEntryIndex_.add_rt_entry(rq->rq_src); //if this is the new route entry added into route table... if (rt0->rt_hops==INFINITY2) { // If we have a fresher seq no. or lesser #hops for the // same seq no., update the rt entry. Else don't bother. rt_update(rt0, rq->rq_src_seqno, rq->rq_hop_count, ih->saddr(), max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE)) ); if (rt0->rt_req_timeout > 0.0) { // Reset the soft state and // Set expiry time to CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT // This is because route is used in the forward direction, // but only sources get benefited by this change rt0->rt_req_cnt = 0; rt0->rt_req_timeout = 0.0; rt0->rt_req_last_ttl = rq->rq_hop_count; rt0->rt_expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT; } } /* Find out whether any buffered packet can benefit from the * reverse route. * May need some change in the following code - Mahesh 09/11/99 */ assert (rt0->rt_flags == RTF_UP); Packet *buffered_pkt; while ((buffered_pkt = rqueue.deque(rt0->rt_dst))) { if (rt0 && (rt0->rt_flags == RTF_UP)) { assert(rt0->rt_hops != INFINITY2); forward(rt0, buffered_pkt, NO_DELAY); } } } else { //rt!=0 //carmen //add another new entry //rt_index is not correct //look up the rt_index for this dst int rt_index_= node_->PacketPr_.RtEntryIndex_.look_rt_index(rq->rq_src); if(rt_index_==-1) { //rt_index_=-1 must be something wrong Packet::free(p); return; } rt0 = rtable.rt_add(rq->rq_src*10+rt_index_+1); //add one more entry record for the same dst node_->PacketPr_.RtEntryIndex_.add_rt_entry(rq->rq_src); rt0->rt_expire = max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE)); rt_update(rt0, rq->rq_src_seqno, rq->rq_hop_count, ih->saddr(),max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE)) ); if (rt0->rt_req_timeout > 0.0) { // Reset the soft state and // Set expiry time to CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT // This is because route is used in the forward direction, // but only sources get benefited by this change rt0->rt_req_cnt = 0; rt0->rt_req_timeout = 0.0; rt0->rt_req_last_ttl = rq->rq_hop_count; rt0->rt_expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT; } //add link state for the new route rt0->rt_flags == RTF_UP; //add the route info in the request for the pevious hop rq->RouteRecord[rq->rq_hop_count].nodeid=index; if(nIfaces) { int iface=HDR_CMN(p)->localif(); rq->RouteRecord[rq->rq_hop_count-1].channel=iface; rq->RouteRecord[rq->rq_hop_count-1].ETT=ChannelETT[ih->saddr()][iface]; } else { rq->RouteRecord[rq->rq_hop_count-1].channel=0; rq->RouteRecord[rq->rq_hop_count-1].ETT=ChannelETT[ih->saddr()][0]; } //add the route into the linkstate table //reverse route for (int i=rq->rq_hop_count-1;i>=0;i--) { rt0->rt_linkstate[i].node1=rq->RouteRecord[i].nodeid; rt0->rt_linkstate[i].linkETT=rq->RouteRecord[i].ETT; rt0->rt_linkstate[i].currentchannel=rq->RouteRecord[i].channel; } //also add my selfinto the route rt0->rt_linkstate[rq->rq_hop_count].node1=index; rt0->rt_linkstate[rq->rq_hop_count].node2=0; if(nIfaces){ int iface=HDR_CMN(p)->localif(); rt0->rt_linkstate[rq->rq_hop_count].currentchannel=iface; rt0->rt_linkstate[rq->rq_hop_count].linkETT=ChannelETT[ih->saddr()][iface]; } else { rt0->rt_linkstate[rq->rq_hop_count].currentchannel=0; rt0->rt_linkstate[rq->rq_hop_count].linkETT=ChannelETT[ih->saddr()][0]; } /* Find out whether any buffered packet can benefit from the * reverse route. * May need some change in the following code - Mahesh 09/11/99 */ assert (rt0->rt_flags == RTF_UP); Packet *buffered_pkt; while ((buffered_pkt = rqueue.deque(rt0->rt_dst))) { if (rt0 && (rt0->rt_flags == RTF_UP)) { assert(rt0->rt_hops != INFINITY2); forward(rt0, buffered_pkt, NO_DELAY); } } } //rt==0 /* * We have taken care of the reverse route stuff. * Now see whether we can send a route reply. */ //carmen //send reply over several routes!!!!!!!!! rt = rtable.rt_lookup(rq->rq_dst); // First check if I am the destination .. if(rq->rq_dst == index) { #ifdef DEBUG fprintf(stderr, "%d - %s: destination sending reply\n", index, __FUNCTION__); #endif // DEBUG //I'm the destination, I will try to find some routes to reply the source //try to find some route //not find some routes to rq->rq_dst,casue I am the dst this packet //intended for. int rt_index_= node_->PacketPr_.RtEntryIndex_.look_rt_index(rq->rq_src); if(rt_index_!=-1){ int rtentrytableindex; for(rtentrytableindex=0;rtentrytableindex<=rt_index_;rtentrytableindex++){ rt=rtable.rt_lookup(rq->rq_src*10+rtentrytableindex); //for every possible route, may not exist if(rt){ // Just to be safe, I use the max. Somebody may have // incremented the dst seqno. seqno = max(seqno, rq->rq_dst_seqno)+1; if (seqno%2) seqno++; //carmen //copy the route info from the route table // struct hdr_wcett_reply *rp = HDR_WCETT_REPLY(p); for(int i=0;irq_hop_count;i++) { rt->rt_linkstate[i].node1=rq->RouteRecord[i].nodeid; rt->rt_linkstate[i].node2=0; rt->rt_linkstate[i].currentchannel=rq->RouteRecord[i].channel; rt->rt_linkstate[i].linkETT=rq->RouteRecord[i].ETT; } //add dst info in the route table(myself) rt->rt_linkstate[rq->rq_hop_count].node1=index; rt->rt_linkstate[rq->rq_hop_count].node2=0; if(nIfaces){ int iface=HDR_CMN(p)->localif(); rt->rt_linkstate[rq->rq_hop_count].currentchannel=iface; rt->rt_linkstate[rq->rq_hop_count].linkETT=ChannelETT[ih->saddr()][iface]; } else { rt->rt_linkstate[rq->rq_hop_count].currentchannel=0; rt->rt_linkstate[rq->rq_hop_count].linkETT=ChannelETT[ih->saddr()][0]; } //set the route state. rt->rt_flags == RTF_UP; sendReply( rq->rq_src, // IP Destination 1, // Hop Count index, // Dest IP Address seqno, // Dest Sequence Num MY_ROUTE_TIMEOUT, // Lifetime rq->rq_timestamp, // timestamp rq->rq_hop_count, //routeindex //+1 counts the final hop // &rq->RouteRecord); //rt index rtentrytableindex); }//if rt!=0 }//for Packet::free(p); }// rt_index_==-1 else { Packet::free(p); } }// I am the destination // I am not the destination, but I may have a fresh enough route. /* else if (rt && (rt->rt_hops != INFINITY2) && (rt->rt_seqno >= rq->rq_dst_seqno) ) { //assert (rt->rt_flags == RTF_UP); assert(rq->rq_dst == rt->rt_dst); //assert ((rt->rt_seqno%2) == 0); // is the seqno even? sendReply(rq->rq_src, rt->rt_hops + 1, rq->rq_dst, rt->rt_seqno, (u_int32_t) (rt->rt_expire - CURRENT_TIME), // rt->rt_expire - CURRENT_TIME, rq->rq_timestamp); // Insert nexthops to RREQ source and RREQ destination in the // precursor lists of destination and source respectively rt->pc_insert(rt0->rt_nexthop); // nexthop to RREQ source rt0->pc_insert(rt->rt_nexthop); // nexthop to RREQ destination #ifdef RREQ_GRAT_RREP sendReply(rq->rq_dst, rq->rq_hop_count, rq->rq_src, rq->rq_src_seqno, (u_int32_t) (rt->rt_expire - CURRENT_TIME), // rt->rt_expire - CURRENT_TIME, rq->rq_timestamp); #endif // TODO: send grat RREP to dst if G flag set in RREQ using rq->rq_src_seqno, rq->rq_hop_counT // DONE: Included gratuitous replies to be sent as per IETF wcett draft specification. As of now, G flag has not been dynamically used and is always set or reset in wcett-packet.h --- Anant Utgikar, 09/16/02. Packet::free(p); } */ /* * Can't reply. So forward the Route Request */ else { ih->saddr() = index; ih->daddr() = IP_BROADCAST; //forward rq //add the route info in the request for the pevious hop rq->RouteRecord[rq->rq_hop_count].nodeid=index; if(nIfaces){ int iface=HDR_CMN(p)->localif(); rq->RouteRecord[rq->rq_hop_count-1].channel=iface; rq->RouteRecord[rq->rq_hop_count-1].ETT=ChannelETT[ih->saddr()][iface]; } else { rq->RouteRecord[rq->rq_hop_count-1].channel=0; rq->RouteRecord[rq->rq_hop_count-1].ETT=ChannelETT[ih->saddr()][0]; } rq->rq_hop_count += 1; // Maximum sequence number seen en route if (rt) rq->rq_dst_seqno = max(rt->rt_seqno, rq->rq_dst_seqno); forward((wcett_rt_entry*) 0, p, DELAY); } } void WCETT::recvReply(Packet *p) { struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); struct hdr_wcett_reply *rp = HDR_WCETT_REPLY(p); wcett_rt_entry *rt,*rt0; char suppress_reply = 0; double delay = 0.0; #ifdef DEBUG fprintf(stderr, "%d - %s: received a REPLY\n", index, __FUNCTION__); #endif // DEBUG /* * Got a reply. So reset the "soft state" maintained for * route requests in the request table. We don't really have * have a separate request table. It is just a part of the * routing table itself. */ // Note that rp_dst is the dest of the data packets, not the // the dest of the reply, which is the src of the data packets. //carmen //look up multiple entry from the route table. bool jumpoutloop=false; for(int i=0;i<10;i++) { rt=rtable.rt_lookup(rp->rp_dst*10+i); //if at least one route entry is found then jump out of the loop if(rt!=0){ jumpoutloop=true; } if(jumpoutloop==true) break; } /* * If I don't have a rt entry to this host... adding */ if(rt == 0) { rt = rtable.rt_add(rp->rp_dst*10); node_->PacketPr_.RtEntryIndex_.add_rt_entry(rp->rp_dst); if(nIfaces){ rt->rt_if=HDR_CMN(p)->localif(); } else { // use the default interface rt->rt_if=0; } rt->rt_flags = RTF_UP; //copy the route info into the node that recvreply int rt_to_dst=0; //can not use the below code ... // for(int i=0;irp_hop_count+1;i++){ // need to copy whole route onto the intermediate node for(int i=0;i<20;i++){ rt->rt_linkstate[i].node1=rp->RouteRecord[i].nodeid; rt->rt_linkstate[i].currentchannel=rp->RouteRecord[i].channel; rt->rt_linkstate[i].linkETT=rp->RouteRecord[i].ETT; } } //rt==0 if (ih->daddr() == index) { // If I am the original source // Update the route discovery latency statistics // rp->rp_timestamp is the time of request origination //to record the route info.. rt0 = rtable.rt_lookup(rt->rt_dst*10+src_recv_reply); if(rt0){ rt0->rt_flags = RTF_UP; for(int i=0;i<20;i++) { rt0->rt_linkstate[i].node1=rp->RouteRecord[i].nodeid; rt0->rt_linkstate[i].node2=0; rt0->rt_linkstate[i].currentchannel=rp->RouteRecord[i].channel; rt0->rt_linkstate[i].linkETT=rp->RouteRecord[i].ETT; } src_recv_reply++; /* * Send all packets queued in the sendbuffer destined for * this destination. * XXX - observe the "second" use of p. */ Packet *buf_pkt; while((buf_pkt = rqueue.deque(rt->rt_dst))) { assert (rt->rt_flags == RTF_UP); // Delay them a little to help ARP. Otherwise ARP // may drop packets. -SRD 5/23/99 //need to find the best route first. for(int i=0;i<20;i++) { struct hdr_cmn *chtmp= HDR_CMN(buf_pkt); chtmp->rtdecision_[i].nodeid=rt0->rt_linkstate[i].node1; chtmp->rtdecision_[i].channel=rt0->rt_linkstate[i].currentchannel; } handleforward(rt, buf_pkt, delay); delay += ARP_DELAY; //} } } //rt!=0 } /* * If reply is for me, discard it. */ if(ih->daddr() == index || suppress_reply) { Packet::free(p); } /* * Otherwise, forward the Route Reply. */ else { handlereplyforward(p,NO_DELAY); } } void WCETT::recvError(Packet *p) { struct hdr_ip *ih = HDR_IP(p); struct hdr_wcett_error *re = HDR_WCETT_ERROR(p); wcett_rt_entry *rt; u_int8_t i; Packet *rerr = Packet::alloc(); struct hdr_wcett_error *nre = HDR_WCETT_ERROR(rerr); nre->DestCount = 0; for (i=0; iDestCount; i++) { // For each unreachable destination rt = rtable.rt_lookup(re->unreachable_dst[i]); if ( rt && (rt->rt_hops != INFINITY2) && (rt->rt_nexthop == ih->saddr()) && (rt->rt_seqno <= re->unreachable_dst_seqno[i]) ) { assert(rt->rt_flags == RTF_UP); assert((rt->rt_seqno%2) == 0); // is the seqno even? #ifdef DEBUG fprintf(stderr, "%s(%f): %d\t(%d\t%u\t%d)\t(%d\t%u\t%d)\n", __FUNCTION__,CURRENT_TIME, index, rt->rt_dst, rt->rt_seqno, rt->rt_nexthop, re->unreachable_dst[i],re->unreachable_dst_seqno[i], ih->saddr()); #endif // DEBUG rt->rt_seqno = re->unreachable_dst_seqno[i]; rt_down(rt); // Not sure whether this is the right thing to do Packet *pkt; while((pkt = ifqueue->filter(ih->saddr()))) { drop(pkt, DROP_RTR_MAC_CALLBACK); } // if precursor list non-empty add to RERR and delete the precursor list if (!rt->pc_empty()) { nre->unreachable_dst[nre->DestCount] = rt->rt_dst; nre->unreachable_dst_seqno[nre->DestCount] = rt->rt_seqno; nre->DestCount += 1; rt->pc_delete(); } } } if (nre->DestCount > 0) { #ifdef DEBUG fprintf(stderr, "%s(%f): %d\t sending RERR...\n", __FUNCTION__, CURRENT_TIME, index); #endif // DEBUG sendError(rerr); } else { Packet::free(rerr); } Packet::free(p); } /* Packet Transmission Routines */ void WCETT::forward(wcett_rt_entry *rt, Packet *p, double delay) { struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); if(ih->ttl_ == 0) { #ifdef DEBUG fprintf(stderr, "%s: calling drop()\n", __PRETTY_FUNCTION__); #endif // DEBUG drop(p, DROP_RTR_TTL); return; } if (ch->ptype() != PT_WCETT && ch->direction() == hdr_cmn::UP && ((u_int32_t)ih->daddr() == IP_BROADCAST) || (ih->daddr() == here_.addr_)) { dmux_->recv(p,0); return; } int dstif=0; if (rt) { assert(rt->rt_flags == RTF_UP); rt->rt_expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT; ch->next_hop_ = rt->rt_nexthop; ch->addr_type() = NS_AF_INET; ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction } else { // if it is a broadcast packet // assert(ch->ptype() == PT_WCETT); // maybe a diff pkt type like gaf assert(ih->daddr() == (nsaddr_t) IP_BROADCAST); ch->addr_type() = NS_AF_NONE; ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction } if (ih->daddr() == (nsaddr_t) IP_BROADCAST) { // If it is a broadcast packet assert(rt == 0); /* * Jitter the sending of broadcast packets by 10ms */ //carmen if(nIfaces) { for(int i=0;icopy(); Scheduler::instance().schedule(targetlist[i], p_copy, 0.01 * Random::uniform()); } } else { Scheduler::instance().schedule(target_, p, 0.01 * Random::uniform()); } } else { // Not a broadcast packet if(delay > 0.0) { //carmen if(nIfaces) { Scheduler::instance().schedule(targetlist[rt->rt_if], p, delay); } else { Scheduler::instance().schedule(target_, p, delay); } } else { // Not a broadcast packet, no delay, send immediately if(nIfaces) { Scheduler::instance().schedule(targetlist[rt->rt_if], p, 0); } else { Scheduler::instance().schedule(target_, p, 0); } } } } /* Packet Transmission Routines */ void WCETT::handleforward(wcett_rt_entry *rt, Packet *p, double delay) { struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); //want to read the routetable in the packet. //delay=0.01; if(ih->ttl_ == 0) { #ifdef DEBUG fprintf(stderr, "%s: calling drop()\n", __PRETTY_FUNCTION__); #endif // DEBUG drop(p, DROP_RTR_TTL); return; } if (ch->ptype() != PT_WCETT && ch->direction() == hdr_cmn::UP && ((u_int32_t)ih->daddr() == IP_BROADCAST) || (ih->daddr() == here_.addr_)) { dmux_->recv(p,0); return; } int rtarrayindex; bool jumpoutloop=false; for(rtarrayindex=0;rtarrayindex<20;rtarrayindex++) { //find out current node's position in the route decision array. if(ch->rtdecision_[rtarrayindex].nodeid==index) { jumpoutloop=true; } if(jumpoutloop==true) break; } //check whether this is the end of the route //it is wrong to come to here if this is the end of the route if(rtarrayindex==20) { drop(p, 0); return; } //current node is the src and its nexthop in array is null //then this may be a backward loop if(ih->saddr()==index && (int)ch->rtdecision_[rtarrayindex+1].nodeid==255){ ch->backwardrt=1; } //carmen //initilize the start address for each node int dstif=0; if (rt) { assert(rt->rt_flags == RTF_UP); rt->rt_expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT; if(ch->backwardrt==0) { ch->next_hop_=ch->rtdecision_[rtarrayindex+1].nodeid; } else { ch->next_hop_=ch->rtdecision_[rtarrayindex-1].nodeid; } if(ch->backwardrt==0) { rt->rt_if=ch->rtdecision_[rtarrayindex+1].channel; } else { rt->rt_if=ch->rtdecision_[rtarrayindex-1].channel; } ch->addr_type() = NS_AF_INET; ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction } else { // if it is a broadcast packet // assert(ch->ptype() == PT_WCETT); // maybe a diff pkt type like gaf assert(ih->daddr() == (nsaddr_t) IP_BROADCAST); ch->addr_type() = NS_AF_NONE; ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction } if (ih->daddr() == (nsaddr_t) IP_BROADCAST) { // If it is a broadcast packet assert(rt == 0); /* * Jitter the sending of broadcast packets by 10ms */ //carmen if(nIfaces) { for(int i=0;icopy(); Scheduler::instance().schedule(targetlist[i], p_copy, 0.01 * Random::uniform()); } } else { Scheduler::instance().schedule(target_, p, 0.01 * Random::uniform()); } } else { // Not a broadcast packet if(delay > 0.0) { //carmen if(nIfaces) { Scheduler::instance().schedule(targetlist[rt->rt_if], p, delay); } else { Scheduler::instance().schedule(target_, p, delay); } } else { // Not a broadcast packet, no delay, send immediately if(nIfaces) { Scheduler::instance().schedule(targetlist[rt->rt_if], p, 0); } else { Scheduler::instance().schedule(target_, p, 0); } } } } void WCETT::sendRequest(nsaddr_t dst) { // Allocate a RREQ packet Packet *p = Packet::alloc(); struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); struct hdr_wcett_request *rq = HDR_WCETT_REQUEST(p); //wcett_rt_entry *rt = rtable.rt_lookup(dst); wcett_rt_entry *rt = rtable.rt_lookup(dst*10); assert(rt); if(rt){ /* * Rate limit sending of Route Requests. We are very conservative * about sending out route requests. */ //record itself in the routing table. rq->RouteRecord[0].nodeid=index; if (rt->rt_flags == RTF_UP) { assert(rt->rt_hops != INFINITY2); // assert(rt_sum_ett != INFINITY2); Packet::free((Packet *)p); return; } if (rt->rt_req_timeout > CURRENT_TIME) { Packet::free((Packet *)p); return; } // rt_req_cnt is the no. of times we did network-wide broadcast // RREQ_RETRIES is the maximum number we will allow before // going to a long timeout. if (rt->rt_req_cnt > RREQ_RETRIES) { rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT; rt->rt_req_cnt = 0; Packet *buf_pkt; while ((buf_pkt = rqueue.deque(rt->rt_dst))) { drop(buf_pkt, DROP_RTR_NO_ROUTE); } Packet::free((Packet *)p); return; } #ifdef DEBUG fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d\n", ++route_request, index, rt->rt_dst); #endif // DEBUG // Determine the TTL to be used this time. // Dynamic TTL evaluation - SRD rt->rt_req_last_ttl = max(rt->rt_req_last_ttl,rt->rt_last_hop_count); if (0 == rt->rt_req_last_ttl) { // first time query broadcast ih->ttl_ = TTL_START; } else { // Expanding ring search. if (rt->rt_req_last_ttl < TTL_THRESHOLD) ih->ttl_ = rt->rt_req_last_ttl + TTL_INCREMENT; else { // network-wide broadcast ih->ttl_ = NETWORK_DIAMETER; rt->rt_req_cnt += 1; } } // remember the TTL used for the next time rt->rt_req_last_ttl = ih->ttl_; // PerHopTime is the roundtrip time per hop for route requests. // The factor 2.0 is just to be safe .. SRD 5/22/99 // Also note that we are making timeouts to be larger if we have // done network wide broadcast before. rt->rt_req_timeout = 2.0 * (double) ih->ttl_ * PerHopTime(rt); if (rt->rt_req_cnt > 0) rt->rt_req_timeout *= rt->rt_req_cnt; rt->rt_req_timeout += CURRENT_TIME; // Don't let the timeout to be too large, however .. SRD 6/8/99 if (rt->rt_req_timeout > CURRENT_TIME + MAX_RREQ_TIMEOUT) rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT; rt->rt_expire = 0; #ifdef DEBUG fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d, tout %f ms\n", ++route_request, index, rt->rt_dst, rt->rt_req_timeout - CURRENT_TIME); #endif // DEBUG // Fill out the RREQ packet // ch->uid() = 0; ch->ptype() = PT_WCETT; ch->size() = IP_HDR_LEN + rq->size(); //carmen ch->iface() = -2; ch->error() = 0; ch->addr_type() = NS_AF_NONE; ch->prev_hop_ = index; // WCETT hack ih->saddr() = index; ih->daddr() = IP_BROADCAST; ih->sport() = RT_PORT; ih->dport() = RT_PORT; // Fill up some more fields. rq->rq_type = WCETTTYPE_RREQ; rq->rq_hop_count = 1; rq->rq_bcast_id = bid++; rq->rq_dst = dst; rq->rq_dst_seqno = (rt ? rt->rt_seqno : 0); rq->rq_src = index; seqno += 2; assert ((seqno%2) == 0); rq->rq_src_seqno = seqno; rq->rq_timestamp = CURRENT_TIME; if(nIfaces) { for(int i=0;icopy(); Scheduler::instance().schedule(targetlist[i], p_copy, 0.); } } else { Scheduler::instance().schedule(target_, p, 0.); } } } void WCETT:: sendReply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst, u_int32_t rpseq, u_int32_t lifetime, double timestamp, int routeindex, int rtentryindex){ //ETTInfo& routerecord) { Packet *p = Packet::alloc(); struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); struct hdr_wcett_reply *rp = HDR_WCETT_REPLY(p); //wcett_rt_entry *rt = rtable.rt_lookup(ipdst); wcett_rt_entry *rt = rtable.rt_lookup(ipdst*10+rtentryindex); #ifdef DEBUG fprintf(stderr, "sending Reply from %d at %.2f\n", index, Scheduler::instance().clock()); #endif // DEBUG assert(rt); rp->rp_type = WCETTTYPE_RREP; //rp->rp_flags = 0x00; rp->rp_hop_count = hop_count; rp->rp_dst = rpdst; rp->rp_dst_seqno = rpseq; rp->rp_src = index; rp->rp_lifetime = lifetime; rp->rp_timestamp = timestamp; // ch->uid() = 0; ch->ptype() = PT_WCETT; ch->size() = IP_HDR_LEN + rp->size(); ch->error() = 0; ch->addr_type() = NS_AF_INET; ch->next_hop_ = rt->rt_nexthop; ch->prev_hop_ = index; // WCETT hack ch->direction() = hdr_cmn::DOWN; ih->saddr() = index; ih->daddr() = ipdst; ih->sport() = RT_PORT; ih->dport() = RT_PORT; ih->ttl_ = NETWORK_DIAMETER; for(int i=0;iRouteRecord[i].nodeid=rt->rt_linkstate[i].node1; rp->RouteRecord[i].channel=rt->rt_linkstate[i].currentchannel; rp->RouteRecord[i].ETT=rt->rt_linkstate[i].linkETT; } //change the nexthop... and channel interface //-2 instead of -1...??? no should be -1 ch->next_hop_ = rp->RouteRecord[routeindex-1].nodeid; rt->rt_if=rp->RouteRecord[routeindex-1].channel; if(nIfaces && (nIfaces>1)){ Scheduler::instance().schedule(targetlist[rt->rt_if], p, 0.); } else { Scheduler::instance().schedule(target_, p, 0.); } } void WCETT::sendError(Packet *p, bool jitter) { struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); struct hdr_wcett_error *re = HDR_WCETT_ERROR(p); #ifdef ERROR fprintf(stderr, "sending Error from %d at %.2f\n", index, Scheduler::instance().clock()); #endif // DEBUG re->re_type = WCETTTYPE_RERR; //re->reserved[0] = 0x00; re->reserved[1] = 0x00; // DestCount and list of unreachable destinations are already filled // ch->uid() = 0; ch->ptype() = PT_WCETT; ch->size() = IP_HDR_LEN + re->size(); //carmen broadcast packet ch->iface() = -2; ch->error() = 0; ch->addr_type() = NS_AF_NONE; ch->next_hop_ = 0; ch->prev_hop_ = index; // WCETT hack ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction ih->saddr() = index; ih->daddr() = IP_BROADCAST; ih->sport() = RT_PORT; ih->dport() = RT_PORT; ih->ttl_ = 1; // Do we need any jitter? Yes if (jitter) { if(nIfaces) { //carmen for(int i=0;icopy(); Scheduler::instance().schedule(targetlist[i], p_copy, 0.01*Random::uniform()); } } else { Scheduler::instance().schedule(target_, p, 0.01*Random::uniform()); } } else { if(nIfaces) { //carmen for(int i=0;icopy(); Scheduler::instance().schedule(targetlist[i], p_copy, 0.0); } } else { Scheduler::instance().schedule(target_, p, 0.0); } } } /* Neighbor Management Functions */ void WCETT::sendHello() { Packet *p = Packet::alloc(); struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); struct hdr_wcett_reply *rh = HDR_WCETT_REPLY(p); #ifdef DEBUG fprintf(stderr, "sending Hello from %d at %.2f\n", index, Scheduler::instance().clock()); #endif // DEBUG rh->rp_type = WCETTTYPE_HELLO; //rh->rp_flags = 0x00; rh->rp_hop_count = 1; rh->rp_dst = index; rh->rp_dst_seqno = seqno; rh->rp_lifetime = (1 + ALLOWED_HELLO_LOSS) * HELLO_INTERVAL; // ch->uid() = 0; ch->ptype() = PT_WCETT; ch->size() = IP_HDR_LEN + rh->size(); //carmen broadcast packet ch->iface() = -2; ch->error() = 0; ch->addr_type() = NS_AF_NONE; ch->prev_hop_ = index; // WCETT hack ih->saddr() = index; ih->daddr() = IP_BROADCAST; ih->sport() = RT_PORT; ih->dport() = RT_PORT; ih->ttl_ = 1; if(nIfaces) { //carmen for(int i=0;icopy(); Scheduler::instance().schedule(targetlist[i], p_copy, 0.0); } } else { Scheduler::instance().schedule(target_, p, 0.0); } } void WCETT::recvHello(Packet *p) { //struct hdr_ip *ih = HDR_IP(p); struct hdr_wcett_reply *rp = HDR_WCETT_REPLY(p); WCETT_Neighbor *nb; struct hdr_cmn *chtemp = HDR_CMN(p); //use reply ack to build hello ack Packet *pack = Packet::alloc(); struct hdr_cmn *ch = HDR_CMN(pack); struct hdr_ip *ih = HDR_IP(pack); struct hdr_wcett_rrep_ack *rpack=HDR_WCETT_RREP_ACK(pack); nb = nb_lookup(rp->rp_dst); if(nb == 0) { nb_insert(rp->rp_dst); } else { nb->nb_expire = CURRENT_TIME + (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL); } //record the hellocounter for each neighbor on each channel if(nIfaces){ int iface=HDR_CMN(p)->localif(); ++ChannelETT[rp->rp_dst][iface]; } //carmen //build hello ack rpack->rpack_type=WCETTTYPE_HELLO_ACK; rpack->RxPr=p->txinfo_.RxPr; //store the RxPr ch->ptype() = PT_WCETT; ch->size() = IP_HDR_LEN + rpack->size(); ch->iface() = -2; ch->error() = 0; ch->addr_type() = NS_AF_NONE; ch->next_hop_ = rp->rp_dst; ch->prev_hop_ = index; // WCETT hack ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction ih->saddr() = index; ih->daddr() = rp->rp_dst; ih->sport() = RT_PORT; ih->dport() = RT_PORT; ih->ttl_ = 1; if(nIfaces) { int ifacetemp=HDR_CMN(p)->localif(); Scheduler::instance().schedule(targetlist[ifacetemp], pack, 0.); } else { Packet::free(pack); } Packet::free(p); ++hellocounter; } void WCETT::nb_insert(nsaddr_t id) { WCETT_Neighbor *nb = new WCETT_Neighbor(id); assert(nb); nb->nb_expire = CURRENT_TIME + (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL); LIST_INSERT_HEAD(&nbhead, nb, nb_link); seqno += 2; // set of neighbors changed assert ((seqno%2) == 0); } WCETT_Neighbor* WCETT::nb_lookup(nsaddr_t id) { WCETT_Neighbor *nb = nbhead.lh_first; for(; nb; nb = nb->nb_link.le_next) { if(nb->nb_addr == id) break; } return nb; } /* * Called when we receive *explicit* notification that a Neighbor * is no longer reachable. */ void WCETT::nb_delete(nsaddr_t id) { WCETT_Neighbor *nb = nbhead.lh_first; log_link_del(id); seqno += 2; // Set of neighbors changed assert ((seqno%2) == 0); for(; nb; nb = nb->nb_link.le_next) { if(nb->nb_addr == id) { LIST_REMOVE(nb,nb_link); delete nb; break; } } handle_link_failure(id); } /* * Purges all timed-out Neighbor Entries - runs every * HELLO_INTERVAL * 1.5 seconds. */ void WCETT::nb_purge() { WCETT_Neighbor *nb = nbhead.lh_first; WCETT_Neighbor *nbn; double now = CURRENT_TIME; for(; nb; nb = nbn) { nbn = nb->nb_link.le_next; if(nb->nb_expire <= now) { nb_delete(nb->nb_addr); } } } //Change the next hop interface for void WCETT::UpdateIf(wcett_rt_entry *rt,int newif){ rt->rt_if=newif; } //Channel Assignment Function void WCETT::ChannelAssign(){ } //ChannelETTCal is used to calculate the new routing metric //WCETT double WCETT::ChannelETTCal(wcett_rt_entry *rt) { // add BETA later into calculation!!!!!!!!!!!!!!!!!!!!!!!!!! // right now only consider ETX not ETT ETT=ETX*S/B //normalfreq reflects the normal transmission probability. //here use the freq instead of probability for easy computation //int normalfreq=ETTRESCHED; //Hello is sent once per sec, and is calculated once per 20s. //ChannelETT[20][12] //ETTSum is the ETT Sum on the route, //ChannelETTSum is the Sum on channel j int ETTSum=0, ChannelETTSum[12]; for(int i=0; i< rt->linkstateindex; i++) { ETTSum=ETTSum+rt->rt_linkstate[i].linkETT; //Find out the ETT sum on each channel switch (rt->rt_linkstate[i].currentchannel) { case 0: ChannelETTSum[0]=ChannelETTSum[0]+rt->rt_linkstate[i].linkETT; break; case 1: ChannelETTSum[1]=ChannelETTSum[1]+rt->rt_linkstate[i].linkETT; break; case 2: ChannelETTSum[2]=ChannelETTSum[2]+rt->rt_linkstate[i].linkETT; break; case 3: ChannelETTSum[3]=ChannelETTSum[3]+rt->rt_linkstate[i].linkETT; break; case 4: ChannelETTSum[4]=ChannelETTSum[4]+rt->rt_linkstate[i].linkETT; break; case 5: ChannelETTSum[5]=ChannelETTSum[5]+rt->rt_linkstate[i].linkETT; break; case 6: ChannelETTSum[6]=ChannelETTSum[6]+rt->rt_linkstate[i].linkETT; break; case 7: ChannelETTSum[7]=ChannelETTSum[7]+rt->rt_linkstate[i].linkETT; break; case 8: ChannelETTSum[8]=ChannelETTSum[8]+rt->rt_linkstate[i].linkETT; break; case 9: ChannelETTSum[9]=ChannelETTSum[9]+rt->rt_linkstate[i].linkETT; break; case 10: ChannelETTSum[10]=ChannelETTSum[10]+rt->rt_linkstate[i].linkETT; break; case 11: ChannelETTSum[11]=ChannelETTSum[11]+rt->rt_linkstate[i].linkETT; break; default: ; //default do nothing } //switch } //for int maxChannelETTSum=0; //Find out the max ChannelETTSum on channel j for(int i=0; i<12;i++) { if(ChannelETTSum[i]>maxChannelETTSum) { maxChannelETTSum=ChannelETTSum[i]; } } return ((1-wcettbeta)*ETTSum+wcettbeta*maxChannelETTSum); } void WCETT::sendAck(void) { } //carmen void WCETT::recvACK(Packet *p){ //receive ack for hello from neighbor //update channel status for this neighbor. WCETT_Neighbor *nb; struct hdr_ip *ih = HDR_IP(p); struct hdr_cmn *ch = HDR_CMN(p); struct hdr_wcett_rrep_ack *rpack=HDR_WCETT_RREP_ACK(p); //look up whether the ack for hello is from one of neighbors nb = nb_lookup(ih->saddr()); if(nb) { if(nIfaces){ int iface=HDR_CMN(p)->localif(); nbchannelRxPr[ih->daddr()][iface]= rpack->RxPr; } } //free the ACK packet Packet::free(p); } /* Find the best route a given source and dst. */ void WCETT::find_best_rt(Packet *p,int& index){ struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); wcett_rt_entry *rt; int bestroute=0; double bestmetric=0; } void WCETT::handlereplyforward(Packet *p, double delay) { struct hdr_cmn *ch = HDR_CMN(p); struct hdr_ip *ih = HDR_IP(p); struct hdr_wcett_reply *rp = HDR_WCETT_REPLY(p); //find out which node I belongs to in the route array. // Find the rt entry int iface=0; bool hasroute=false; for(int i=19;i>=0;i--){ if(index==rp->RouteRecord[i].nodeid) { ch->next_hop_=rp->RouteRecord[i-1].nodeid; iface=rp->RouteRecord[i-1].channel; hasroute=true; } if(hasroute==true) break; // hasroute=false; } if(!hasroute){ //no route to reply currentnode drop(p, DROP_RTR_NO_ROUTE); } if(ih->ttl_ == 0) { #ifdef DEBUG fprintf(stderr, "%s: calling drop()\n", __PRETTY_FUNCTION__); #endif // DEBUG drop(p, DROP_RTR_TTL); return; } if (ch->ptype() != PT_WCETT && ch->direction() == hdr_cmn::UP && ((u_int32_t)ih->daddr() == IP_BROADCAST) || (ih->daddr() == here_.addr_)) { dmux_->recv(p,0); return; } // ch->next_hop_ = rt->rt_nexthop; ch->addr_type() = NS_AF_INET; ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction // Not a broadcast packet if(delay > 0.0) { if(nIfaces) { Scheduler::instance().schedule(targetlist[iface], p, delay); } else { Scheduler::instance().schedule(target_, p, delay); } } else { // Not a broadcast packet, no delay, send immediately if(nIfaces) { Scheduler::instance().schedule(targetlist[iface], p, 0); } else { Scheduler::instance().schedule(target_, p, 0); } } }