// -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*-

//

// Copyright (c) 2008 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

//

#include "ns3/log.h"

#include "ns3/object.h"

#include "ipv4-global-routing.h"

#include "ns3/packet.h"

#include "ns3/node.h"

NS_LOG_COMPONENT_DEFINE ("Ipv4GlobalRouting");

namespace ns3 {

NS_OBJECT_ENSURE_REGISTERED (Ipv4GlobalRouting);

TypeId 

Ipv4GlobalRouting::GetTypeId (void)

{ 

  static TypeId tid = TypeId ("ns3::Ipv4GlobalRouting")

    .SetParent<Object> ()

    ;

  return tid;

}

Ipv4GlobalRouting::Ipv4GlobalRouting () 

{

  NS_LOG_FUNCTION_NOARGS ();

}

void 

Ipv4GlobalRouting::AddHostRouteTo (Ipv4Address dest, 

                                   Ipv4Address nextHop, 

                                   uint32_t interface)

{

  Ptr<Node> n = this->GetObject<Node> ();

  NS_LOG_FUNCTION (n->GetId() << dest << nextHop << interface);

  Ipv4Route *route = new Ipv4Route ();

  *route = Ipv4Route::CreateHostRouteTo (dest, nextHop, interface);

  m_hostRoutes.push_back (route);

}

void 

Ipv4GlobalRouting::AddHostRouteTo (Ipv4Address dest, 

                                   uint32_t interface)

{

  NS_LOG_FUNCTION (dest << interface);

  Ipv4Route *route = new Ipv4Route ();

  *route = Ipv4Route::CreateHostRouteTo (dest, interface);

  m_hostRoutes.push_back (route);

}

void 

Ipv4GlobalRouting::AddNetworkRouteTo (Ipv4Address network, 

                                      Ipv4Mask networkMask, 

                                      Ipv4Address nextHop, 

                                      uint32_t interface)

{

  Ptr<Node> n = this->GetObject<Node> ();

  NS_LOG_FUNCTION (n->GetId () << network << networkMask << nextHop << interface);

  Ipv4Route *route = new Ipv4Route ();

  *route = Ipv4Route::CreateNetworkRouteTo (network,

                                            networkMask,

                                            nextHop,

                                            interface);

  m_networkRoutes.push_back (route);

}

void 

Ipv4GlobalRouting::AddNetworkRouteTo (Ipv4Address network, 

                                      Ipv4Mask networkMask, 

                                      uint32_t interface)

{

  NS_LOG_FUNCTION (network << networkMask << interface);

  Ipv4Route *route = new Ipv4Route ();

  *route = Ipv4Route::CreateNetworkRouteTo (network,

                                            networkMask,

                                            interface);

  m_networkRoutes.push_back (route);

}

Ipv4Route *

Ipv4GlobalRouting::LookupGlobal (Ipv4Address dest)

{

  NS_LOG_FUNCTION_NOARGS ();

  for (HostRoutesCI i = m_hostRoutes.begin (); 

       i != m_hostRoutes.end (); 

       i++) 

    {

      NS_ASSERT ((*i)->IsHost ());

      if ((*i)->GetDest ().IsEqual (dest)) 

        {

          NS_LOG_LOGIC ("Found global host route" << *i); 

          return (*i);

        }

    }

  for (NetworkRoutesI j = m_networkRoutes.begin (); 

       j != m_networkRoutes.end (); 

       j++) 

    {

      NS_ASSERT ((*j)->IsNetwork ());

      Ipv4Mask mask = (*j)->GetDestNetworkMask ();

      Ipv4Address entry = (*j)->GetDestNetwork ();

      if (mask.IsMatch (dest, entry)) 

        {

          NS_LOG_LOGIC ("Found global network route" << *j); 

          return (*j);

        }

    }

  return 0;

}

uint32_t 

Ipv4GlobalRouting::GetNRoutes (void)

{

  NS_LOG_FUNCTION_NOARGS ();

  uint32_t n = 0;

  n += m_hostRoutes.size ();

  n += m_networkRoutes.size ();

  return n;

}

Ipv4Route *

Ipv4GlobalRouting::GetRoute (uint32_t index)

{

  NS_LOG_FUNCTION (index);

  if (index < m_hostRoutes.size ())

    {

      uint32_t tmp = 0;

      for (HostRoutesCI i = m_hostRoutes.begin (); 

           i != m_hostRoutes.end (); 

           i++) 

        {

          if (tmp  == index)

            {

              return *i;

            }

          tmp++;

        }

    }

  index -= m_hostRoutes.size ();

  uint32_t tmp = 0;

  for (NetworkRoutesI j = m_networkRoutes.begin (); 

       j != m_networkRoutes.end (); 

       j++) 

    {

      if (tmp == index)

        {

          return *j;

        }

      tmp++;

    }

  NS_ASSERT (false);

  // quiet compiler.

  return 0;

}

void 

Ipv4GlobalRouting::RemoveRoute (uint32_t index)

{

  NS_LOG_FUNCTION (index);

  if (index < m_hostRoutes.size ())

    {

      uint32_t tmp = 0;

      for (HostRoutesI i = m_hostRoutes.begin (); 

           i != m_hostRoutes.end (); 

           i++) 

        {

          if (tmp  == index)

            {

              NS_LOG_LOGIC ("Removing route " << index << "; size = " << m_hostRoutes.size());

              delete *i;

              m_hostRoutes.erase (i);

              NS_LOG_LOGIC ("Done removing host route " << index << "; host route remaining size = " << m_hostRoutes.size());

              return;

            }

          tmp++;

        }

    }

  index -= m_hostRoutes.size ();

  uint32_t tmp = 0;

  for (NetworkRoutesI j = m_networkRoutes.begin (); 

       j != m_networkRoutes.end (); 

       j++) 

    {

      if (tmp == index)

        {

          NS_LOG_LOGIC ("Removing route " << index << "; size = " << m_networkRoutes.size());

          delete *j;

          m_networkRoutes.erase (j);

          NS_LOG_LOGIC ("Done removing network route " << index << "; network route remaining size = " << m_networkRoutes.size());

          return;

        }

      tmp++;

    }

  NS_ASSERT (false);

}

bool

Ipv4GlobalRouting::RequestRoute (

  uint32_t ifIndex,

  Ipv4Header const &ipHeader,

  Ptr<Packet> packet,

  RouteReplyCallback routeReply)

{

  NS_LOG_FUNCTION (this << ifIndex << &ipHeader << packet << &routeReply);

  NS_LOG_LOGIC ("source = " << ipHeader.GetSource ());

  NS_LOG_LOGIC ("destination = " << ipHeader.GetDestination ());

  if (ipHeader.GetDestination ().IsMulticast ())

    {

      NS_LOG_LOGIC ("Multicast destination-- returning false");

      return false; // Let other routing protocols try to handle this

    }

// This is a unicast packet.  Check to see if we have a route for it.

//

  NS_LOG_LOGIC ("Unicast destination- looking up");

  Ipv4Route *route = LookupGlobal (ipHeader.GetDestination ());

  if (route != 0)

    {

      routeReply (true, *route, packet, ipHeader);

      return true;

    }

  else

    {

      return false; // Let other routing protocols try to handle this

                    // route request.

    }

}

bool

Ipv4GlobalRouting::RequestIfIndex (Ipv4Address destination, uint32_t& ifIndex)

{

  NS_LOG_FUNCTION (this << destination << &ifIndex);

//

// First, see if this is a multicast packet we have a route for.  If we

// have a route, then send the packet down each of the specified interfaces.

//

  if (destination.IsMulticast ())

    {

      NS_LOG_LOGIC ("Multicast destination-- returning false");

      return false; // Let other routing protocols try to handle this

    }

//

// See if this is a unicast packet we have a route for.

//

  NS_LOG_LOGIC ("Unicast destination- looking up");

  Ipv4Route *route = LookupGlobal (destination);

  if (route)

    {

      ifIndex = route->GetInterface ();

      return true;

    }

  else

    {

      return false;

    }

}

void

Ipv4GlobalRouting::DoDispose (void)

{

  NS_LOG_FUNCTION_NOARGS ();

  for (HostRoutesI i = m_hostRoutes.begin (); 

       i != m_hostRoutes.end (); 

       i = m_hostRoutes.erase (i)) 

    {

      delete (*i);

    }

  for (NetworkRoutesI j = m_networkRoutes.begin (); 

       j != m_networkRoutes.end (); 

       j = m_networkRoutes.erase (j)) 

    {

      delete (*j);

    }

  Ipv4RoutingProtocol::DoDispose ();

}

}//namespace ns3

// -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*-

//

// Copyright (c) 2008 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

//

//

#ifndef IPV4_GLOBAL_ROUTING_H

#define IPV4_GLOBAL_ROUTING_H

#include <list>

#include <stdint.h>

#include "ns3/ipv4-address.h"

#include "ns3/ipv4-header.h"

#include "ns3/ptr.h"

#include "ns3/ipv4.h"

namespace ns3 {

class Packet;

class NetDevice;

class Ipv4Interface;

class Ipv4Address;

class Ipv4Header;

class Ipv4Route;

class Node;

/**

 * @brief Global routing protocol for IP version 4 stacks.

 *

 * In ns-3 we have the concept of a pluggable routing protocol.  Routing

 * protocols are added to a list maintained by the Ipv4L3Protocol.  Every 

 * stack gets one routing protocol for free -- the Ipv4StaticRouting routing

 * protocol is added in the constructor of the Ipv4L3Protocol (this is the 

 * piece of code that implements the functionality of the IP layer).

 *

 * As an option to running a dynamic routing protocol, a GlobalRouteManager

 * object has been created to allow users to build routes for all participating

 * nodes.  One can think of this object as a "routing oracle"; it has

 * an omniscient view of the topology, and can construct shortest path

 * routes between all pairs of nodes.  These routes must be stored 

 * somewhere in the node, so therefore this class Ipv4GlobalRouting

 * is used as one of the pluggable routing protocols.  It is kept distinct

 * from Ipv4StaticRouting because these routes may be dynamically cleared

 * and rebuilt in the middle of the simulation, while manually entered

 * routes into the Ipv4StaticRouting may need to be kept distinct.

 *

 * This class deals with Ipv4 unicast routes only.

 *

 * @see Ipv4RoutingProtocol

 * @see GlobalRouteManager

 */

class Ipv4GlobalRouting : public Ipv4RoutingProtocol

{

public:

  static TypeId GetTypeId (void);

/**

 * @brief Construct an empty Ipv4GlobalRouting routing protocol,

 *

 * The Ipv4GlobalRouting class supports host and network unicast routes.

 * This method initializes the lists containing these routes to empty.

 *

 * @see Ipv4GlobalRouting

 */

  Ipv4GlobalRouting ();

/**

 * @brief Request that a check for a route bw performed and if a route is found

 * that the packet be sent on its way using the pre-packaged send callback.

 *

 * The source and destination IP addresses for the packet in question are found

 * in the provided Ipv4Header.  There are two major processing forks depending

 * on the type of destination address.  

 *

 * If the destination address is unicast then the routing table is consulted 

 * for a route to the destination and if it is found, the routeReply callback

 * is executed to send the packet (with the found route).

 * 

 * If the destination address is a multicast, then the method will return

 * false.

 *

 * @param ifIndex The network interface index over which the packed was 

 * received.  If the packet is from a local source, ifIndex will be set to

 * Ipv4RoutingProtocol::IF_INDEX_ANY.

 * @param ipHeader the Ipv4Header containing the source and destination IP

 * addresses for the packet.

 * @param packet The packet to be sent if a route is found.

 * @param routeReply A callback that packaged up the call to actually send the

 * packet.

 * @return Returns true if a route is found and the packet has been sent,

 * otherwise returns false indicating that the next routing protocol should

 * be consulted.  

 *

 * @see Ipv4GlobalRouting

 * @see Ipv4RoutingProtocol

 */

  virtual bool RequestRoute (uint32_t ifIndex,

                             Ipv4Header const &ipHeader,

                             Ptr<Packet> packet,

                             RouteReplyCallback routeReply);

/**

 * @brief Check to see if we can determine the interface index that will be

 * used if a packet is sent to this destination.

 *

 * This method addresses a problem in the IP stack where a destination address

 * must be present and checksummed into the IP header before the actual 

 * interface over which the packet is sent can be determined.  The answer is

 * to implement a known and intentional cross-layer violation.  This is the

 * endpoint of a call chain that started up quite high in the stack (sockets)

 * and has found its way down to the Ipv4L3Protocol which is consulting the

 * routing protocols for what they would do if presented with a packet of the

 * given destination.

 *

 * If there are multiple paths out of the node, the resolution is performed

 * by Ipv4L3Protocol::GetIfIndexforDestination which has access to more 

 * contextual information that is useful for making a determination.

 *

 * This method will return false on a multicast address.

 *

 * @param destination The Ipv4Address if the destination of a hypothetical 

 * packet.  This may be a multicast group address.

 * @param ifIndex A reference to the interface index over which a packet

 * sent to this destination would be sent.

 * @return Returns true if a route is found to the destination that involves

 * a single output interface index, otherwise returns false indicating that

 * the next routing protocol should be consulted.  

 *

 * @see Ipv4GlobalRouting

 * @see Ipv4RoutingProtocol

 * @see Ipv4L3Protocol

 */

  virtual bool RequestIfIndex (Ipv4Address destination, uint32_t& ifIndex);

/**

 * @brief Add a host route to the global routing table.

 *

 * @param dest The Ipv4Address destination for this route.

 * @param nextHop The Ipv4Address of the next hop in the route.

 * @param interface The network interface index used to send packets to the

 * destination.

 *

 * @see Ipv4Address

 */

  void AddHostRouteTo (Ipv4Address dest, 

                       Ipv4Address nextHop, 

                       uint32_t interface);

/**

 * @brief Add a host route to the global routing table.

 *

 * @param dest The Ipv4Address destination for this route.

 * @param interface The network interface index used to send packets to the

 * destination.

 *

 * @see Ipv4Address

 */

  void AddHostRouteTo (Ipv4Address dest, 

                       uint32_t interface);

/**

 * @brief Add a network route to the global routing table.

 *

 * @param network The Ipv4Address network for this route.

 * @param networkMask The Ipv4Mask to extract the network.

 * @param nextHop The next hop in the route to the destination network.

 * @param interface The network interface index used to send packets to the

 * destination.

 *

 * @see Ipv4Address

 */

  void AddNetworkRouteTo (Ipv4Address network, 

                          Ipv4Mask networkMask, 

                          Ipv4Address nextHop, 

                          uint32_t interface);

/**

 * @brief Add a network route to the global routing table.

 *

 * @param network The Ipv4Address network for this route.

 * @param networkMask The Ipv4Mask to extract the network.

 * @param interface The network interface index used to send packets to the

 * destination.

 *

 * @see Ipv4Address

 */

  void AddNetworkRouteTo (Ipv4Address network, 

                          Ipv4Mask networkMask, 

                          uint32_t interface);

/**

 * @brief Get the number of individual unicast routes that have been added

 * to the routing table.

 *

 * @warning The default route counts as one of the routes.

 */

  uint32_t GetNRoutes (void);

/**

 * @brief Get a route from the global unicast routing table.

 *

 * Externally, the unicast global routing table appears simply as a table with

 * n entries.  The one sublety of note is that if a default route has been set

 * it will appear as the zeroth entry in the table.  This means that if you

 * add only a default route, the table will have one entry that can be accessed

 * either by explicity calling GetDefaultRoute () or by calling GetRoute (0).

 * 

 * Similarly, if the default route has been set, calling RemoveRoute (0) will

 * remove the default route.

 *

 * @param i The index (into the routing table) of the route to retrieve.  If

 * the default route has been set, it will occupy index zero.

 * @return If route is set, a pointer to that Ipv4Route is returned, otherwise

 * a zero pointer is returned.

 *

 * @see Ipv4Route

 * @see Ipv4GlobalRouting::RemoveRoute

 */

  Ipv4Route *GetRoute (uint32_t i);

/**

 * @brief Remove a route from the global unicast routing table.

 *

 * Externally, the unicast global routing table appears simply as a table with

 * n entries.  The one sublety of note is that if a default route has been set

 * it will appear as the zeroth entry in the table.  This means that if the

 * default route has been set, calling RemoveRoute (0) will remove the

 * default route.

 *

 * @param i The index (into the routing table) of the route to remove.  If

 * the default route has been set, it will occupy index zero.

 *

 * @see Ipv4Route

 * @see Ipv4GlobalRouting::GetRoute

 * @see Ipv4GlobalRouting::AddRoute

 */

  void RemoveRoute (uint32_t i);

protected:

  void DoDispose (void);

private:

  typedef std::list<Ipv4Route *> HostRoutes;

  typedef std::list<Ipv4Route *>::const_iterator HostRoutesCI;

  typedef std::list<Ipv4Route *>::iterator HostRoutesI;

  typedef std::list<Ipv4Route *> NetworkRoutes;

  typedef std::list<Ipv4Route *>::const_iterator NetworkRoutesCI;

  typedef std::list<Ipv4Route *>::iterator NetworkRoutesI;

  Ipv4Route *LookupGlobal (Ipv4Address dest);

  HostRoutes m_hostRoutes;

  NetworkRoutes m_networkRoutes;

};

} // Namespace ns3

#endif /* IPV4_GLOBAL_ROUTING_H */

        'ipv4-global-routing.cc',

        'ipv4-global-routing.h',

#include "ns3/ipv4-global-routing.h"

  void

GlobalRouteManagerImpl::DeleteGlobalRoutes ()

{

  NS_LOG_FUNCTION_NOARGS ();

  for (NodeList::Iterator i = NodeList::Begin (); i != NodeList::End (); i++)

    {

      Ptr<Node> node = *i;

      Ptr<Ipv4GlobalRouting> gr = node->GetObject<Ipv4GlobalRouting> ();

      uint32_t j = 0;

      uint32_t nRoutes = gr->GetNRoutes ();

      NS_LOG_LOGIC ("Deleting " << gr->GetNRoutes ()<< " routes from node " << node->GetId ());

      // Each time we delete route 0, the route index shifts downward

      // We can delete all routes if we delete the route numbered 0

      // nRoutes times

      for (j = 0; j < nRoutes; j++)

        {

          NS_LOG_LOGIC ("Deleting global route " << j << " from node " << node->GetId ());

          gr->RemoveRoute (0);        

        }

      NS_LOG_LOGIC ("Deleted " << j << " global routes from node "<< node->GetId ());

    }

  if (m_lsdb)

    {

      NS_LOG_LOGIC ("Deleting LSDB, creating new one");

      delete m_lsdb;

      m_lsdb = new GlobalRouteManagerLSDB ();

    }

}

      NS_LOG_LOGIC ("Adding GlobalRouting Protocol to node " << node->GetId ());

      Ptr<Ipv4GlobalRouting> globalRouting = CreateObject<Ipv4GlobalRouting> ();

      // This is the object that will keep the global routes.  We insert it

      // at slightly higher priority than static routing (which is at zero).

      // This means that global routes (e.g. host routes) will be consulted

      // before static routes

      Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();

      NS_ASSERT_MSG (ipv4, "GlobalRouteManagerImpl::SelectRouterNodes (): "

        "GetObject for <Ipv4> interface failed");

      // XXX make the below  priority value an attribute

      ipv4->AddRoutingProtocol (globalRouting, 3);  

      // XXX here is another temporary hack until IP refactoring is done.

      // we will need a way to get a handle to this globalRouting, but

      // there is no public API in ns3::Ipv4 to get it.  Therefore, 

      // rather than create new temporary public API, we use aggregation

      node->AggregateObject (globalRouting);

          NS_LOG_LOGIC (" Node " << node->GetId () <<

             " found " << nLinkRecords << " link records in LSA " << lsa << "with LinkStateId "<< lsa->GetLinkStateId ());

/**

 * @brief Delete all static routes on all nodes that have a

 * GlobalRouterInterface

 *

 * TODO:  separate manually assigned static routes from static routes that

 * the global routing code injects, and only delete the latter

 * @internal

 *

 */

  virtual void DeleteGlobalRoutes ();

GlobalRouteManager::RecomputeRoutingTables ()

{

  DeleteGlobalRoutes ();

  BuildGlobalRoutingDatabase ();

  InitializeRoutes ();

}

  void

GlobalRouteManager::DeleteGlobalRoutes ()

{

  SimulationSingleton<GlobalRouteManagerImpl>::Get ()->

    DeleteGlobalRoutes ();

}

  void

 * @see SelectRouterNodes ();

 /**

  *@brief Remove all routes that were previously installed in a prior call

 * to either PopulateRoutingTables() or RecomputeRoutingTables(), and 

 * add a new set of routes.  

 * 

 * This method does not change the set of nodes

 * over which GlobalRouting is being used, but it will dynamically update

 * its representation of the global topology before recomputing routes.

 * Users must first call PopulateRoutingTables() and then may subsequently

 * call RecomputeRoutingTables() at any later time in the simulation.

 *

 * @see DeleteGlobalRoutes ();

 * @see BuildGlobalRoutingDatabase ();

 * @see InitializeRoutes ();

 */

 static void RecomputeRoutingTables ();

/**

 * @brief Delete all static routes on all nodes that have a 

 * GlobalRouterInterface

 *

 * TODO:  separate manually assigned static routes from static routes that

 * the global routing code injects, and only delete the latter

 * @internal

 */

  static void DeleteGlobalRoutes ();

          if (!ipv4Remote->IsUp (ifIndexRemote))

            {

              continue;

            }