global-route-manager-impl.h

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright 2007 University of Washington
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation;
 *
 * 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:  Craig Dowell (craigdo@ee.washington.edu)
 *           Tom Henderson (tomhend@u.washington.edu)
 */

#ifndef GLOBAL_ROUTE_MANAGER_IMPL_H
#define GLOBAL_ROUTE_MANAGER_IMPL_H

#include <stdint.h>
#include <list>
#include <queue>
#include <map>
#include <vector>
#include "ns3/object.h"
#include "ns3/ptr.h"
#include "ns3/ipv4-address.h"
#include "global-router-interface.h"

namespace ns3 {

const uint32_t SPF_INFINITY = 0xffffffff;

class CandidateQueue;
class Ipv4GlobalRouting;

class SPFVertex
{
public:
  enum VertexType {
    VertexUnknown = 0,  
    VertexRouter,       
    VertexNetwork       
  };

  SPFVertex();

  SPFVertex(GlobalRoutingLSA* lsa);

  ~SPFVertex();

  VertexType GetVertexType (void) const;

  void SetVertexType (VertexType type);

  Ipv4Address GetVertexId (void) const;

  void SetVertexId (Ipv4Address id);

  GlobalRoutingLSA* GetLSA (void) const;

  void SetLSA (GlobalRoutingLSA* lsa);

  uint32_t GetDistanceFromRoot (void) const;

  void SetDistanceFromRoot (uint32_t distance);

  void SetRootExitDirection (Ipv4Address nextHop, int32_t id = SPF_INFINITY);
  typedef std::pair<Ipv4Address, int32_t> NodeExit_t;
  void SetRootExitDirection (SPFVertex::NodeExit_t exit);
  NodeExit_t GetRootExitDirection (uint32_t i) const;
  NodeExit_t GetRootExitDirection () const;
  void MergeRootExitDirections (const SPFVertex* vertex);
  void InheritAllRootExitDirections (const SPFVertex* vertex);
  uint32_t GetNRootExitDirections () const;

  SPFVertex* GetParent (uint32_t i = 0) const;

  void SetParent (SPFVertex* parent);
  void MergeParent (const SPFVertex* v);

  uint32_t GetNChildren (void) const;

  SPFVertex* GetChild (uint32_t n) const;

  uint32_t AddChild (SPFVertex* child);

  void SetVertexProcessed (bool value);

  bool IsVertexProcessed (void) const;

  void ClearVertexProcessed (void);

private:
  VertexType m_vertexType;
  Ipv4Address m_vertexId;
  GlobalRoutingLSA* m_lsa;
  uint32_t m_distanceFromRoot;
  int32_t m_rootOif;
  Ipv4Address m_nextHop;
  typedef std::list< NodeExit_t > ListOfNodeExit_t;
  ListOfNodeExit_t m_ecmpRootExits;
  typedef std::list<SPFVertex*> ListOfSPFVertex_t;
  ListOfSPFVertex_t m_parents;
  ListOfSPFVertex_t m_children;
  bool m_vertexProcessed; 

  SPFVertex (SPFVertex& v);

  SPFVertex& operator= (SPFVertex& v);

  //friend std::ostream& operator<< (std::ostream& os, const ListOfIf_t& ifs);
  //friend std::ostream& operator<< (std::ostream& os, const ListOfAddr_t& addrs);
  friend std::ostream& operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs);
};

class GlobalRouteManagerLSDB
{
public:
  GlobalRouteManagerLSDB ();

  ~GlobalRouteManagerLSDB ();

  void Insert (Ipv4Address addr, GlobalRoutingLSA* lsa);

  GlobalRoutingLSA* GetLSA (Ipv4Address addr) const;
  GlobalRoutingLSA* GetLSAByLinkData (Ipv4Address addr) const;

  void Initialize ();

  GlobalRoutingLSA* GetExtLSA (uint32_t index) const;
  uint32_t GetNumExtLSAs () const;


private:
  typedef std::map<Ipv4Address, GlobalRoutingLSA*> LSDBMap_t;
  typedef std::pair<Ipv4Address, GlobalRoutingLSA*> LSDBPair_t;

  LSDBMap_t m_database;
  std::vector<GlobalRoutingLSA*> m_extdatabase;

  GlobalRouteManagerLSDB (GlobalRouteManagerLSDB& lsdb);

  GlobalRouteManagerLSDB& operator= (GlobalRouteManagerLSDB& lsdb);
};

class GlobalRouteManagerImpl
{
public:
  GlobalRouteManagerImpl ();
  virtual ~GlobalRouteManagerImpl ();
  virtual void DeleteGlobalRoutes ();

  virtual void BuildGlobalRoutingDatabase ();

  virtual void InitializeRoutes ();

  void DebugUseLsdb (GlobalRouteManagerLSDB*);

  void DebugSPFCalculate (Ipv4Address root);

private:
  GlobalRouteManagerImpl (GlobalRouteManagerImpl& srmi);

  GlobalRouteManagerImpl& operator= (GlobalRouteManagerImpl& srmi);

  SPFVertex* m_spfroot;
  GlobalRouteManagerLSDB* m_lsdb;
  bool CheckForStubNode (Ipv4Address root);
  void SPFCalculate (Ipv4Address root);
  void SPFProcessStubs (SPFVertex* v);
  void ProcessASExternals (SPFVertex* v, GlobalRoutingLSA* extlsa);
  void SPFNext (SPFVertex*, CandidateQueue&);
  int SPFNexthopCalculation (SPFVertex* v, SPFVertex* w, 
                             GlobalRoutingLinkRecord* l, uint32_t distance);
  void SPFVertexAddParent (SPFVertex* v);
  GlobalRoutingLinkRecord* SPFGetNextLink (SPFVertex* v, SPFVertex* w, 
                                           GlobalRoutingLinkRecord* prev_link);
  void SPFIntraAddRouter (SPFVertex* v);
  void SPFIntraAddTransit (SPFVertex* v);
  void SPFIntraAddStub (GlobalRoutingLinkRecord *l, SPFVertex* v);
  void SPFAddASExternal (GlobalRoutingLSA *extlsa, SPFVertex *v);
  int32_t FindOutgoingInterfaceId (Ipv4Address a, 
                                   Ipv4Mask amask = Ipv4Mask ("255.255.255.255"));
};

} // namespace ns3

#endif /* GLOBAL_ROUTE_MANAGER_IMPL_H */