LinkStateRouter.cc

Go to the documentation of this file.
00001 /*
00002  * IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. By
00003  * downloading, copying, installing or using the software you agree to
00004  * this license. If you do not agree to this license, do not download,
00005  * install, copy or use the software.
00006  * 
00007  * Intel Open Source License 
00008  * 
00009  * Copyright (c) 2004 Intel Corporation. All rights reserved. 
00010  * 
00011  * Redistribution and use in source and binary forms, with or without
00012  * modification, are permitted provided that the following conditions are
00013  * met:
00014  * 
00015  *   Redistributions of source code must retain the above copyright
00016  *   notice, this list of conditions and the following disclaimer.
00017  * 
00018  *   Redistributions in binary form must reproduce the above copyright
00019  *   notice, this list of conditions and the following disclaimer in the
00020  *   documentation and/or other materials provided with the distribution.
00021  * 
00022  *   Neither the name of the Intel Corporation nor the names of its
00023  *   contributors may be used to endorse or promote products derived from
00024  *   this software without specific prior written permission.
00025  *  
00026  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00027  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00028  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00029  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE INTEL OR
00030  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00031  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
00032  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00033  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00034  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00035  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00036  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037  */
00038 
00039 #include "BundleRouter.h"
00040 #include "RouteTable.h"
00041 #include "bundling/Bundle.h"
00042 #include "bundling/BundleActions.h"
00043 #include "bundling/BundleDaemon.h"
00044 #include "bundling/BundleList.h"
00045 #include "contacts/Contact.h"
00046 #include "contacts/ContactManager.h"
00047 
00048 #include "reg/Registration.h"
00049 #include "reg/RegistrationTable.h"
00050 #include <stdlib.h>
00051 
00052 #include "LinkStateRouter.h"
00053 #include "LinkStateGraph.h"
00054 
00055 namespace dtn {
00056 
00057 #define ROUTER_BCAST_EID "str://linkstate.router"
00058 
00059 LinkStateRouter::LinkStateRouter()
00060     : BundleRouter("LinkStateRouter", "linkstate")
00061 {
00062 }
00063 
00064 void 
00065 LinkStateRouter::initialize() 
00066 {
00067     reg_=new LSRegistration(this);
00068     BundleDaemon::instance()->post(new RegistrationAddedEvent(reg_, EVENTSRC_ADMIN));
00069 }
00070 
00071 void
00072 LinkStateRouter::handle_contact_up(ContactUpEvent* event)
00073 {
00074     BundleRouter::handle_contact_up(event);
00075     LinkStateGraph::Vertex *peer, *local;
00076 
00077     log_info("Contact Up. Adding edges %s <-> %s",
00078              BundleDaemon::instance()->local_eid().c_str(),
00079              event->contact_->link()->nexthop());
00080 
00081     // XXX/demmer this is bogus too... fix this whole implementation
00082     
00083     local=graph_.getVertex(BundleDaemon::instance()->local_eid().c_str());
00084     peer=graph_.getVertex(event->contact_->link()->nexthop());
00085 
00086     /* 
00087      *  Contact Up means we are able to transmit to the node at the other side. 
00088      *  Although we _could_ make an assumption of symmetric links, we don't really
00089      *  need to, the peer node will send an update about the other direction.
00090      */
00091     LinkStateGraph::Edge *e=graph_.addEdge(local, peer, 1);
00092     if(e) flood_announcement(e, true);
00093 
00094     /*
00095      *  Now record this event in the Log for this edge.
00096      */
00097     e=graph_.getEdge(local,peer);
00098     //  e->contact_.start = currentmillis()?
00099     //  e->contact_.duration = 0;
00100 
00101     /*
00102      *  Finally, transmit the entire link state database over to the newly discovered peer.
00103      *  An optimized implementation would send multiple updates in a single bundle, and 
00104      *  possibly use bloom filters to minimize the amount of state we need to send.
00105      *
00106      *  For now, we'll just send a lot of little link update bundles.
00107      */
00108     std::set<LinkStateGraph::Edge*> edges=graph_.edges();
00109     for(std::set<LinkStateGraph::Edge*>::iterator i=edges.begin(); i!=edges.end(); i++)
00110         send_announcement((*i), event->contact_->link(), 1);
00111 }
00112 
00113 void
00114 LinkStateRouter::handle_contact_down(ContactDownEvent* event)
00115 {
00116     // XXX/jakob - store this event in the link log!
00117     //             also, might want to trigger a schedule detection event here, since we have a new entry
00118     //             in the log. If there is a schedule detected, we might want to advertise it too!
00119 
00120     LinkStateGraph::Vertex *peer, *local;
00121 
00122     log_info("Contact Down. Removing edges %s <-> %s",
00123              BundleDaemon::instance()->local_eid().c_str(),
00124              event->contact_->link()->nexthop());
00125     
00126     peer=graph_.getVertex(event->contact_->link()->nexthop());
00127     local=graph_.getVertex(BundleDaemon::instance()->local_eid().c_str());
00128 
00129     /*
00130      *  Record this event in the Log for this edge.
00131      */
00132 //    e=graph_.getEdge(local,peer);
00133 //    e->contact_.duration=currentmillis()->e->contact_.start;    
00134 //    e->log_.push_back(e->contact_);
00135 
00136     /*
00137      *  XXX/jakob - ok, so here we probably want to run the find_schedule thingy.
00138      *              if we find a schedule, we would like to announce it to the world.
00139      *              however, there are some finer points here: what if it changes?
00140      *              what if it changes ever so slightly? when do we announce? always?
00141      */      
00142     // Log *schedule = find_schedule(e->log_);
00143     // if(schedule) announce it!
00144     // else ignore it
00145 
00146     /*
00147      * Contact Down means we can't send to a peer any more. This theoretically has nothing to do with our
00148      * ability to receive from that node. For now, we make the assumption of symmetric links here, tearing
00149      * down both directions of a link as one direction fails. If we don't do this, we might end up with
00150      * orphan links in the graph in the event of a graph partitioning.
00151      *
00152      * XXX/jakob - there must be a way to handle the tearing down of links assymetrically...
00153      */
00154     LinkStateGraph::Edge *e=local->outgoing_edges_[peer];
00155     if(e) {
00156         graph_.removeEdge(e);        
00157         flood_announcement(e,false);
00158     }
00159     e=local->incoming_edges_[peer];
00160     if(e) {
00161         graph_.removeEdge(e);        
00162         flood_announcement(e,false);
00163     }
00164 
00165     BundleRouter::handle_contact_down(event);
00166 }
00167 
00168 void
00169 LinkStateRouter::handle_bundle_received(BundleReceivedEvent* event)
00170 {
00171     Bundle* bundle=event->bundleref_.object();
00172 
00173     // we don't want any bundles that are already owned by someone
00174     if(bundle->owner_ != "") {
00175         log_debug("Skipping bundle ID %u owned by %s.\n",bundle->bundleid_,bundle->owner_.c_str());
00176         return;
00177     }
00178     
00179     ContactManager* cm = BundleDaemon::instance()->contactmgr();
00180     
00181     /* XXX/jakob
00182      *
00183      * 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
00184      * registration events to see what EID's are local. Then, when finding the next hop, we would start at 
00185      * any local EID but send the bundle directly to the next _non-local_ EID in the graph.
00186      */
00187     const char* local_eid = BundleDaemon::instance()->local_eid().c_str();
00188     LinkStateGraph::Vertex* nextHop=
00189         graph_.findNextHop(graph_.getVertex(local_eid),
00190                            // getMatchingVertex allows for some *-matching
00191                            graph_.getMatchingVertex(bundle->dest_.c_str())); 
00192     
00193     if(!nextHop) {
00194         log_debug("No LSRoute to destination %s",bundle->dest_.c_str());
00195         return;
00196     }
00197 
00198     log_debug("Next hop from %s to %s is %s.",
00199               local_eid,
00200               bundle->dest_.c_str(),
00201               nextHop->eid_);              
00202 
00203     // XXX/demmer fixme
00204     EndpointID eid(nextHop->eid_);
00205     ASSERT(eid.valid());
00206            
00207     Link* link=cm->find_link_to(NULL, "", eid);
00208 
00209     ASSERT(link!=0); // if the link is in the graph, it better exist too
00210 
00211     // Send the bundle on the appropriate link.
00212     // XXX/demmer fixme
00213     actions_->send_bundle(bundle, link, ForwardingInfo::FORWARD_ACTION,
00214                           CustodyTimerSpec::defaults_);
00215 }
00216 
00217 void
00218 LinkStateRouter::get_routing_state(oasys::StringBuffer* buf)
00219 {
00220     // dump the link state graph to the buffer.
00221     graph_.dumpGraph(buf);
00222 }
00223 
00224 
00225 /* 
00226  * flood_announcement sends link state announcements to all neighbors. For now, we're using
00227  * unicast to each and every neighbor. It would really be much better if we could use a 
00228  * broadcast, but the convergence layers don't support that yet.
00229  */
00230 void 
00231 LinkStateRouter::flood_announcement(LinkStateGraph::Edge* edge, bool exists)
00232 {
00233     ContactManager* cm = BundleDaemon::instance()->contactmgr();
00234     oasys::ScopeLock l(cm->lock(), "flood_announcement");
00235 
00236     const LinkSet* links=cm->links();
00237     for(LinkSet::const_iterator i=links->begin(); i!=links->end(); i++)
00238         send_announcement(edge, (*i), exists);
00239 }
00240 
00241 void
00242 LinkStateRouter::send_announcement(LinkStateGraph::Edge* edge,
00243                                    Link* outgoing_link, bool exists)
00244 {
00245     LinkStateAnnouncement lsa;
00246     memset(&lsa,0,sizeof(lsa));
00247 
00248     // XXX/jakob these announcements should be nicely encoded, not
00249     //           just send the whole char[]! Bad, lazy me!
00250     
00251     sprintf(lsa.from,"%s",(edge->from_)->eid_);
00252     sprintf(lsa.to,"%s",(edge->to_)->eid_);
00253     if(exists)
00254         lsa.cost=edge->cost_;
00255     else
00256         lsa.cost=LinkStateAnnouncement::LINK_DOWN;
00257 
00258     lsa.type=LS_ANNOUNCEMENT;
00259 
00260     // make a bundle
00261     Bundle *b=new Bundle();
00262     b->source_.assign(BundleDaemon::instance()->local_eid());
00263     b->replyto_.assign(EndpointID::NULL_EID());
00264     b->custodian_.assign(EndpointID::NULL_EID());
00265     b->dest_.assign(ROUTER_BCAST_EID); 
00266     b->payload_.set_data((const u_char*)&lsa,sizeof(lsa));
00267 
00268     // propagate it to the outgoing link
00269     actions_->inject_bundle(b);
00270     actions_->send_bundle(b, outgoing_link, ForwardingInfo::FORWARD_ACTION,
00271                           CustodyTimerSpec::defaults_);
00272 }
00273 
00274 LinkStateRouter::LSRegistration::LSRegistration(LinkStateRouter* router)
00275     : Registration(Registration::LINKSTATEROUTER_REGID,
00276                    EndpointID(ROUTER_BCAST_EID),
00277                    Registration::DEFER, 0)
00278 {
00279     logpathf("/reg/admin");
00280 
00281     router_=router;
00282 
00283     BundleDaemon::post(new RegistrationAddedEvent(this, EVENTSRC_ADMIN));
00284 }
00285 
00286 void
00287 LinkStateRouter::LSRegistration::deliver_bundle(Bundle* bundle)
00288 {
00289     u_char typecode;      
00290 
00291     log_info("LSRegistration Consuming bundle");
00292 
00293     size_t payload_len = bundle->payload_.length();
00294     const u_char* data = 0;
00295 
00296     oasys::StringBuffer payload_buf(payload_len);
00297 
00298     if (payload_len == 0) {
00299         log_err("linkstate registration got 0 byte bundle *%p", bundle);
00300         goto done;
00301     }
00302 
00303     data = bundle->payload_.read_data(0, payload_len, (u_char*)payload_buf.data());
00304 
00305     // first byte of any bundle sent to a LinkStateRouter EID is a type code
00306     typecode=*data;
00307 
00308     switch(typecode) {
00309     case LS_ANNOUNCEMENT:
00310     {
00311         LinkStateAnnouncement *lsa=(LinkStateAnnouncement*)data;
00312 
00313         LinkStateGraph *graph=router_->graph();
00314         LinkStateGraph::Edge *edge;
00315         
00316         if(lsa->cost==LinkStateAnnouncement::LINK_DOWN) {
00317             LinkStateGraph::Vertex *from=graph->getVertex(lsa->from);
00318             if(!from) {
00319                 log_debug("No such vertex %s.",lsa->from);
00320                 return;
00321             }
00322 
00323             LinkStateGraph::Vertex *to=graph->getVertex(lsa->to);
00324             if(!(edge=from->outgoing_edges_[to]))
00325             {
00326                 log_debug("No such edge %s -> %s.",lsa->from,lsa->to);
00327                 return;
00328             }
00329             graph->removeEdge(edge);
00330         }
00331         
00332         // addEdge returns the edge if an edge was added. If so, forward it to all neighbors
00333         if((edge=graph->addEdge(graph->getVertex(lsa->from), graph->getVertex(lsa->to), lsa->cost)))
00334         {
00335             router_->flood_announcement(edge, true);
00336         }        
00337         
00338         break;
00339     }
00340     default:
00341         log_warn("unexpected admin bundle with type 0x%x *%p",
00342                  typecode, bundle);
00343     }    
00344 
00345  done:
00346     BundleDaemon::post(new BundleDeliveredEvent(bundle, this));
00347 }
00348 
00349 } // namespace dtn

Generated on Fri Dec 22 14:47:59 2006 for DTN Reference Implementation by  doxygen 1.5.1