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 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* v, CandidateQueue& candidate);

  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 */