LinkStateRouter.cc

Go to the documentation of this file.
00001 /*
00002  *    Copyright 2004-2006 Intel Corporation
00003  * 
00004  *    Licensed under the Apache License, Version 2.0 (the "License");
00005  *    you may not use this file except in compliance with the License.
00006  *    You may obtain a copy of the License at
00007  * 
00008  *        http://www.apache.org/licenses/LICENSE-2.0
00009  * 
00010  *    Unless required by applicable law or agreed to in writing, software
00011  *    distributed under the License is distributed on an "AS IS" BASIS,
00012  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  *    See the License for the specific language governing permissions and
00014  *    limitations under the License.
00015  */
00016 
00017 
00018 #include "BundleRouter.h"
00019 #include "RouteTable.h"
00020 #include "bundling/Bundle.h"
00021 #include "bundling/BundleActions.h"
00022 #include "bundling/BundleDaemon.h"
00023 #include "bundling/BundleList.h"
00024 #include "contacts/Contact.h"
00025 #include "contacts/ContactManager.h"
00026 
00027 #include "reg/Registration.h"
00028 #include "reg/RegistrationTable.h"
00029 #include <stdlib.h>
00030 
00031 #include "LinkStateRouter.h"
00032 #include "LinkStateGraph.h"
00033 
00034 namespace dtn {
00035 
00036 #define ROUTER_BCAST_EID "str://linkstate.router"
00037 
00038 LinkStateRouter::LinkStateRouter()
00039     : BundleRouter("LinkStateRouter", "linkstate")
00040 {
00041 }
00042 
00043 void 
00044 LinkStateRouter::initialize() 
00045 {
00046     reg_=new LSRegistration(this);
00047     BundleDaemon::instance()->post(new RegistrationAddedEvent(reg_, EVENTSRC_ADMIN));
00048 }
00049 
00050 void
00051 LinkStateRouter::handle_contact_up(ContactUpEvent* event)
00052 {
00053     BundleRouter::handle_contact_up(event);
00054     LinkStateGraph::Vertex *peer, *local;
00055 
00056     log_info("Contact Up. Adding edges %s <-> %s",
00057              BundleDaemon::instance()->local_eid().c_str(),
00058              event->contact_->link()->nexthop());
00059 
00060     // XXX/demmer this is bogus too... fix this whole implementation
00061     
00062     local=graph_.getVertex(BundleDaemon::instance()->local_eid().c_str());
00063     peer=graph_.getVertex(event->contact_->link()->nexthop());
00064 
00065     /* 
00066      *  Contact Up means we are able to transmit to the node at the other side. 
00067      *  Although we _could_ make an assumption of symmetric links, we don't really
00068      *  need to, the peer node will send an update about the other direction.
00069      */
00070     LinkStateGraph::Edge *e=graph_.addEdge(local, peer, 1);
00071     if(e) flood_announcement(e, true);
00072 
00073     /*
00074      *  Now record this event in the Log for this edge.
00075      */
00076     e=graph_.getEdge(local,peer);
00077     //  e->contact_.start = currentmillis()?
00078     //  e->contact_.duration = 0;
00079 
00080     /*
00081      *  Finally, transmit the entire link state database over to the newly discovered peer.
00082      *  An optimized implementation would send multiple updates in a single bundle, and 
00083      *  possibly use bloom filters to minimize the amount of state we need to send.
00084      *
00085      *  For now, we'll just send a lot of little link update bundles.
00086      */
00087     std::set<LinkStateGraph::Edge*> edges=graph_.edges();
00088     for(std::set<LinkStateGraph::Edge*>::iterator i=edges.begin(); i!=edges.end(); i++)
00089         send_announcement((*i), event->contact_->link(), 1);
00090 }
00091 
00092 void
00093 LinkStateRouter::handle_contact_down(ContactDownEvent* event)
00094 {
00095     // XXX/jakob - store this event in the link log!
00096     //             also, might want to trigger a schedule detection event here, since we have a new entry
00097     //             in the log. If there is a schedule detected, we might want to advertise it too!
00098 
00099     LinkStateGraph::Vertex *peer, *local;
00100 
00101     log_info("Contact Down. Removing edges %s <-> %s",
00102              BundleDaemon::instance()->local_eid().c_str(),
00103              event->contact_->link()->nexthop());
00104     
00105     peer=graph_.getVertex(event->contact_->link()->nexthop());
00106     local=graph_.getVertex(BundleDaemon::instance()->local_eid().c_str());
00107 
00108     /*
00109      *  Record this event in the Log for this edge.
00110      */
00111 //    e=graph_.getEdge(local,peer);
00112 //    e->contact_.duration=currentmillis()->e->contact_.start;    
00113 //    e->log_.push_back(e->contact_);
00114 
00115     /*
00116      *  XXX/jakob - ok, so here we probably want to run the find_schedule thingy.
00117      *              if we find a schedule, we would like to announce it to the world.
00118      *              however, there are some finer points here: what if it changes?
00119      *              what if it changes ever so slightly? when do we announce? always?
00120      */      
00121     // Log *schedule = find_schedule(e->log_);
00122     // if(schedule) announce it!
00123     // else ignore it
00124 
00125     /*
00126      * Contact Down means we can't send to a peer any more. This theoretically has nothing to do with our
00127      * ability to receive from that node. For now, we make the assumption of symmetric links here, tearing
00128      * down both directions of a link as one direction fails. If we don't do this, we might end up with
00129      * orphan links in the graph in the event of a graph partitioning.
00130      *
00131      * XXX/jakob - there must be a way to handle the tearing down of links assymetrically...
00132      */
00133     LinkStateGraph::Edge *e=local->outgoing_edges_[peer];
00134     if(e) {
00135         graph_.removeEdge(e);        
00136         flood_announcement(e,false);
00137     }
00138     e=local->incoming_edges_[peer];
00139     if(e) {
00140         graph_.removeEdge(e);        
00141         flood_announcement(e,false);
00142     }
00143 
00144     BundleRouter::handle_contact_down(event);
00145 }
00146 
00147 void
00148 LinkStateRouter::handle_bundle_received(BundleReceivedEvent* event)
00149 {
00150     Bundle* bundle=event->bundleref_.object();
00151 
00152     // we don't want any bundles that are already owned by someone
00153     if(bundle->owner_ != "") {
00154         log_debug("Skipping bundle ID %u owned by %s.\n",bundle->bundleid_,bundle->owner_.c_str());
00155         return;
00156     }
00157     
00158     ContactManager* cm = BundleDaemon::instance()->contactmgr();
00159     
00160     /* XXX/jakob
00161      *
00162      * This isn't going to work if there are more than one EID on a node. What needs to be done is to listen to
00163      * registration events to see what EID's are local. Then, when finding the next hop, we would start at 
00164      * any local EID but send the bundle directly to the next _non-local_ EID in the graph.
00165      */
00166     const char* local_eid = BundleDaemon::instance()->local_eid().c_str();
00167     LinkStateGraph::Vertex* nextHop=
00168         graph_.findNextHop(graph_.getVertex(local_eid),
00169                            // getMatchingVertex allows for some *-matching
00170                            graph_.getMatchingVertex(bundle->dest_.c_str())); 
00171     
00172     if(!nextHop) {
00173         log_debug("No LSRoute to destination %s",bundle->dest_.c_str());
00174         return;
00175     }
00176 
00177     log_debug("Next hop from %s to %s is %s.",
00178               local_eid,
00179               bundle->dest_.c_str(),
00180               nextHop->eid_);              
00181 
00182     // XXX/demmer fixme
00183     EndpointID eid(nextHop->eid_);
00184     ASSERT(eid.valid());
00185            
00186     Link* link=cm->find_link_to(NULL, "", eid);
00187 
00188     ASSERT(link!=0); // if the link is in the graph, it better exist too
00189 
00190     // Send the bundle on the appropriate link.
00191     // XXX/demmer fixme
00192     actions_->send_bundle(bundle, link, ForwardingInfo::FORWARD_ACTION,
00193                           CustodyTimerSpec::defaults_);
00194 }
00195 
00196 void
00197 LinkStateRouter::get_routing_state(oasys::StringBuffer* buf)
00198 {
00199     // dump the link state graph to the buffer.
00200     graph_.dumpGraph(buf);
00201 }
00202 
00203 
00204 /* 
00205  * flood_announcement sends link state announcements to all neighbors. For now, we're using
00206  * unicast to each and every neighbor. It would really be much better if we could use a 
00207  * broadcast, but the convergence layers don't support that yet.
00208  */
00209 void 
00210 LinkStateRouter::flood_announcement(LinkStateGraph::Edge* edge, bool exists)
00211 {
00212     ContactManager* cm = BundleDaemon::instance()->contactmgr();
00213     oasys::ScopeLock l(cm->lock(), "flood_announcement");
00214 
00215     const LinkSet* links=cm->links();
00216     for(LinkSet::const_iterator i=links->begin(); i!=links->end(); i++)
00217         send_announcement(edge, (*i), exists);
00218 }
00219 
00220 void
00221 LinkStateRouter::send_announcement(LinkStateGraph::Edge* edge,
00222                                    Link* outgoing_link, bool exists)
00223 {
00224     LinkStateAnnouncement lsa;
00225     memset(&lsa,0,sizeof(lsa));
00226 
00227     // XXX/jakob these announcements should be nicely encoded, not
00228     //           just send the whole char[]! Bad, lazy me!
00229     
00230     sprintf(lsa.from,"%s",(edge->from_)->eid_);
00231     sprintf(lsa.to,"%s",(edge->to_)->eid_);
00232     if(exists)
00233         lsa.cost=edge->cost_;
00234     else
00235         lsa.cost=LinkStateAnnouncement::LINK_DOWN;
00236 
00237     lsa.type=LS_ANNOUNCEMENT;
00238 
00239     // make a bundle
00240     Bundle *b=new Bundle();
00241     b->source_.assign(BundleDaemon::instance()->local_eid());
00242     b->replyto_.assign(EndpointID::NULL_EID());
00243     b->custodian_.assign(EndpointID::NULL_EID());
00244     b->dest_.assign(ROUTER_BCAST_EID); 
00245     b->payload_.set_data((const u_char*)&lsa,sizeof(lsa));
00246 
00247     // propagate it to the outgoing link
00248     actions_->inject_bundle(b);
00249     actions_->send_bundle(b, outgoing_link, ForwardingInfo::FORWARD_ACTION,
00250                           CustodyTimerSpec::defaults_);
00251 }
00252 
00253 LinkStateRouter::LSRegistration::LSRegistration(LinkStateRouter* router)
00254     : Registration(Registration::LINKSTATEROUTER_REGID,
00255                    EndpointID(ROUTER_BCAST_EID),
00256                    Registration::DEFER, 0)
00257 {
00258     logpathf("/reg/admin");
00259 
00260     router_=router;
00261 
00262     BundleDaemon::post(new RegistrationAddedEvent(this, EVENTSRC_ADMIN));
00263 }
00264 
00265 void
00266 LinkStateRouter::LSRegistration::deliver_bundle(Bundle* bundle)
00267 {
00268     u_char typecode;      
00269 
00270     log_info("LSRegistration Consuming bundle");
00271 
00272     size_t payload_len = bundle->payload_.length();
00273     const u_char* data = 0;
00274 
00275     oasys::StringBuffer payload_buf(payload_len);
00276 
00277     if (payload_len == 0) {
00278         log_err("linkstate registration got 0 byte bundle *%p", bundle);
00279         goto done;
00280     }
00281 
00282     data = bundle->payload_.read_data(0, payload_len, (u_char*)payload_buf.data());
00283 
00284     // first byte of any bundle sent to a LinkStateRouter EID is a type code
00285     typecode=*data;
00286 
00287     switch(typecode) {
00288     case LS_ANNOUNCEMENT:
00289     {
00290         LinkStateAnnouncement *lsa=(LinkStateAnnouncement*)data;
00291 
00292         LinkStateGraph *graph=router_->graph();
00293         LinkStateGraph::Edge *edge;
00294         
00295         if(lsa->cost==LinkStateAnnouncement::LINK_DOWN) {
00296             LinkStateGraph::Vertex *from=graph->getVertex(lsa->from);
00297             if(!from) {
00298                 log_debug("No such vertex %s.",lsa->from);
00299                 return;
00300             }
00301 
00302             LinkStateGraph::Vertex *to=graph->getVertex(lsa->to);
00303             if(!(edge=from->outgoing_edges_[to]))
00304             {
00305                 log_debug("No such edge %s -> %s.",lsa->from,lsa->to);
00306                 return;
00307             }
00308             graph->removeEdge(edge);
00309         }
00310         
00311         // addEdge returns the edge if an edge was added. If so, forward it to all neighbors
00312         if((edge=graph->addEdge(graph->getVertex(lsa->from), graph->getVertex(lsa->to), lsa->cost)))
00313         {
00314             router_->flood_announcement(edge, true);
00315         }        
00316         
00317         break;
00318     }
00319     default:
00320         log_warn("unexpected admin bundle with type 0x%x *%p",
00321                  typecode, bundle);
00322     }    
00323 
00324  done:
00325     BundleDaemon::post(new BundleDeliveredEvent(bundle, this));
00326 }
00327 
00328 } // namespace dtn

Generated on Thu Jun 7 12:54:28 2007 for DTN Reference Implementation by  doxygen 1.5.1