/* -*- 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; //!< "infinite" distance between nodes

class CandidateQueue;

class Ipv4GlobalRouting;

/**

 * @brief Vertex used in shortest path first (SPF) computations. See \RFC{2328},

 * Section 16.

 *

 * Each router in the simulation is associated with an SPFVertex object.  When

 * calculating routes, each of these routers is, in turn, chosen as the "root"

 * of the calculation and routes to all of the other routers are eventually

 * saved in the routing tables of each of the chosen nodes.  Each of these 

 * routers in the calculation has an associated SPFVertex.

 *

 * The "Root" vertex is the SPFVertex representing the router that is having

 * its routing tables set.  The SPFVertex objects representing other routers

 * or networks in the simulation are arranged in the SPF tree.  It is this 

 * tree that represents the Shortest Paths to the other networks.

 *

 * Each SPFVertex has a pointer to the Global Router Link State Advertisement

 * (LSA) that its underlying router has exported.  Within these LSAs are

 * Global Router Link Records that describe the point to point links from the

 * underlying router to other nodes (represented by other SPFVertex objects)

 * in the simulation topology.  The combination of the arrangement of the 

 * SPFVertex objects in the SPF tree, along with the details of the link

 * records that connect them provide the information required to construct the

 * required routes.

 */

class SPFVertex

{

public:

/**

 * @brief Enumeration of the possible types of SPFVertex objects.

 * @internal

 *

 * Currently we use VertexRouter to identify objects that represent a router 

 * in the simulation topology, and VertexNetwork to identify objects that 

 * represent a network.

 */

  enum VertexType {

    VertexUnknown = 0,  /**< Uninitialized Link Record */

    VertexRouter,       /**< Vertex representing a router in the topology */

    VertexNetwork       /**< Vertex representing a network in the topology */

  };

/**

 * @brief Construct an empty ("uninitialized") SPFVertex (Shortest Path First 

 * Vertex).

 * @internal

 *

 * The Vertex Type is set to VertexUnknown, the Vertex ID is set to 

 * 255.255.255.255, and the distance from root is set to infinity 

 * (UINT32_MAX).  The referenced Link State Advertisement (LSA) is set to 

 * null as is the parent SPFVertex.  The outgoing interface index is set to

 * infinity, the next hop address is set to 0.0.0.0 and the list of children

 * of the SPFVertex is initialized to empty.

 *

 * @see VertexType

 */

  SPFVertex();

/**

 * @brief Construct an initialized SPFVertex (Shortest Path First Vertex).

 * @internal

 *

 * The Vertex Type is initialized to VertexRouter and the Vertex ID is found

 * from the Link State ID of the Link State Advertisement (LSA) passed as a

 * parameter.  The Link State ID is set to the Router ID of the advertising

 * router.  The referenced LSA (m_lsa) is set to the given LSA.  Other than 

 * these members, initialization is as in the default constructor.

 * of the SPFVertex is initialized to empty.

 *

 * @see SPFVertex::SPFVertex ()

 * @see VertexType

 * @see GlobalRoutingLSA

 * @param lsa The Link State Advertisement used for finding initial values.

 */

  SPFVertex(GlobalRoutingLSA* lsa);

/**

 * @brief Destroy an SPFVertex (Shortest Path First Vertex).

 * @internal

 *

 * The children vertices of the SPFVertex are recursively deleted.

 *

 * @see SPFVertex::SPFVertex ()

 */

  ~SPFVertex();

/**

 * @brief Get the Vertex Type field of a SPFVertex object.

 * @internal

 *

 * The Vertex Type describes the kind of simulation object a given SPFVertex

 * represents.

 *

 * @see VertexType

 * @returns The VertexType of the current SPFVertex object.

 */

  VertexType GetVertexType (void) const;

/**

 * @brief Set the Vertex Type field of a SPFVertex object.

 * @internal

 *

 * The Vertex Type describes the kind of simulation object a given SPFVertex

 * represents.

 *

 * @see VertexType

 * @param type The new VertexType for the current SPFVertex object.

 */

  void SetVertexType (VertexType type);

/**

 * @brief Get the Vertex ID field of a SPFVertex object.

 * @internal

 *

 * The Vertex ID uniquely identifies the simulation object a given SPFVertex

 * represents.  Typically, this is the Router ID for SPFVertex objects 

 * representing routers, and comes from the Link State Advertisement of a 

 * router aggregated to a node in the simulation.  These IDs are allocated

 * automatically by the routing environment and look like IP addresses 

 * beginning at 0.0.0.0 and monotonically increasing as new routers are

 * instantiated.

 *

 * @returns The Ipv4Address Vertex ID of the current SPFVertex object.

 */

  Ipv4Address GetVertexId (void) const;

/**

 * @brief Set the Vertex ID field of a SPFVertex object.

 * @internal

 *

 * The Vertex ID uniquely identifies the simulation object a given SPFVertex

 * represents.  Typically, this is the Router ID for SPFVertex objects 

 * representing routers, and comes from the Link State Advertisement of a 

 * router aggregated to a node in the simulation.  These IDs are allocated

 * automatically by the routing environment and look like IP addresses 

 * beginning at 0.0.0.0 and monotonically increase as new routers are

 * instantiated.  This method is an explicit override of the automatically

 * generated value.

 *

 * @param id The new Ipv4Address Vertex ID for the current SPFVertex object.

 */

  void SetVertexId (Ipv4Address id);

/**

 * @brief Get the Global Router Link State Advertisement returned by the 

 * Global Router represented by this SPFVertex during the route discovery 

 * process.

 * @internal

 *

 * @see GlobalRouter

 * @see GlobalRoutingLSA

 * @see GlobalRouter::DiscoverLSAs ()

 * @returns A pointer to the GlobalRoutingLSA found by the router represented

 * by this SPFVertex object.

 */

  GlobalRoutingLSA* GetLSA (void) const;

/**

 * @brief Set the Global Router Link State Advertisement returned by the 

 * Global Router represented by this SPFVertex during the route discovery 

 * process.

 * @internal

 *

 * @see SPFVertex::GetLSA ()

 * @see GlobalRouter

 * @see GlobalRoutingLSA

 * @see GlobalRouter::DiscoverLSAs ()

 * @warning Ownership of the LSA is transferred to the "this" SPFVertex.  You

 * must not delete the LSA after calling this method.

 * @param lsa A pointer to the GlobalRoutingLSA.

 */

  void SetLSA (GlobalRoutingLSA* lsa);

/**

 * @brief Get the distance from the root vertex to "this" SPFVertex object.

 * @internal

 *

 * Each router in the simulation is associated with an SPFVertex object.  When

 * calculating routes, each of these routers is, in turn, chosen as the "root"

 * of the calculation and routes to all of the other routers are eventually

 * saved in the routing tables of each of the chosen nodes.  Each of these 

 * routers in the calculation has an associated SPFVertex.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set.  The "this" SPFVertex is the vertex to which

 * a route is being calculated from the root.  The distance from the root that

 * we're asking for is the number of hops from the root vertex to the vertex

 * in question.

 *

 * The distance is calculated during route discovery and is stored in a

 * member variable.  This method simply fetches that value.

 *

 * @returns The distance, in hops, from the root SPFVertex to "this" SPFVertex.

 */

  uint32_t GetDistanceFromRoot (void) const;

/**

 * @brief Set the distance from the root vertex to "this" SPFVertex object.

 * @internal

 *

 * Each router in the simulation is associated with an SPFVertex object.  When

 * calculating routes, each of these routers is, in turn, chosen as the "root"

 * of the calculation and routes to all of the other routers are eventually

 * saved in the routing tables of each of the chosen nodes.  Each of these 

 * routers in the calculation has an associated SPFVertex.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set.  The "this" SPFVertex is the vertex to which

 * a route is being calculated from the root.  The distance from the root that

 * we're asking for is the number of hops from the root vertex to the vertex

 * in question.

 *

 * @param distance The distance, in hops, from the root SPFVertex to "this"

 * SPFVertex.

 */

  void SetDistanceFromRoot (uint32_t distance);

/**

 * @brief Set the IP address and outgoing interface index that should be used 

 * to begin forwarding packets from the root SPFVertex to "this" SPFVertex.

 * @internal

 *

 * Each router node in the simulation is associated with an SPFVertex object.

 * When calculating routes, each of these routers is, in turn, chosen as the 

 * "root" of the calculation and routes to all of the other routers are

 * eventually saved in the routing tables of each of the chosen nodes.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set.  The "this" SPFVertex is the vertex that

 * represents the host or network to which a route is being calculated from 

 * the root.  The IP address that we're asking for is the address on the 

 * remote side of a link off of the root node that should be used as the

 * destination for packets along the path to "this" vertex.

 *

 * When initializing the root SPFVertex, the IP address used when forwarding

 * packets is determined by examining the Global Router Link Records of the

 * Link State Advertisement generated by the root node's GlobalRouter.  This

 * address is used to forward packets off of the root's network down those

 * links.  As other vertices / nodes are discovered which are further away

 * from the root, they will be accessible down one of the paths via a link

 * described by one of these Global Router Link Records.

 * 

 * To forward packets to these hosts or networks, the root node must begin

 * the forwarding process by sending the packets to a first hop router down

 * an interface.  This means that the first hop address and interface ID must

 * be the same for all downstream SPFVertices.  We call this "inheriting"

 * the interface and next hop.

 *

 * In this method we are telling the root node which exit direction it should send

 * should I send a packet to the network or host represented by 'this' SPFVertex.

 *

 * @see GlobalRouter

 * @see GlobalRoutingLSA

 * @see GlobalRoutingLinkRecord

 * @param nextHop The IP address to use when forwarding packets to the host

 * or network represented by "this" SPFVertex.

 * @param id The interface index to use when forwarding packets to the host or

 * network represented by "this" SPFVertex.

 */

  void SetRootExitDirection (Ipv4Address nextHop, int32_t id = SPF_INFINITY);

  typedef std::pair<Ipv4Address, int32_t> NodeExit_t; //!< IPv4 / interface container for exit nodes.

/**

 * @brief Set the IP address and outgoing interface index that should be used 

 * to begin forwarding packets from the root SPFVertex to "this" SPFVertex.

 * @internal

 *

 * Each router node in the simulation is associated with an SPFVertex object.

 * When calculating routes, each of these routers is, in turn, chosen as the 

 * "root" of the calculation and routes to all of the other routers are

 * eventually saved in the routing tables of each of the chosen nodes.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set.  The "this" SPFVertex is the vertex that

 * represents the host or network to which a route is being calculated from 

 * the root.  The IP address that we're asking for is the address on the 

 * remote side of a link off of the root node that should be used as the

 * destination for packets along the path to "this" vertex.

 *

 * When initializing the root SPFVertex, the IP address used when forwarding

 * packets is determined by examining the Global Router Link Records of the

 * Link State Advertisement generated by the root node's GlobalRouter.  This

 * address is used to forward packets off of the root's network down those

 * links.  As other vertices / nodes are discovered which are further away

 * from the root, they will be accessible down one of the paths via a link

 * described by one of these Global Router Link Records.

 * 

 * To forward packets to these hosts or networks, the root node must begin

 * the forwarding process by sending the packets to a first hop router down

 * an interface.  This means that the first hop address and interface ID must

 * be the same for all downstream SPFVertices.  We call this "inheriting"

 * the interface and next hop.

 *

 * In this method we are telling the root node which exit direction it should send

 * should I send a packet to the network or host represented by 'this' SPFVertex.

 *

 * @see GlobalRouter

 * @see GlobalRoutingLSA

 * @see GlobalRoutingLinkRecord

 * @param exit The pair of next-hop-IP and outgoing-interface-index to use when 

 * forwarding packets to the host or network represented by "this" SPFVertex.

 */

  void SetRootExitDirection (SPFVertex::NodeExit_t exit);

  /**

   * \brief Obtain a pair indicating the exit direction from the root

   *

   * \param i An index to a pair

   * \return A pair of next-hop-IP and outgoing-interface-index for

   * indicating an exit direction from the root. It is 0 if the index 'i'

   * is out-of-range

   */

  NodeExit_t GetRootExitDirection (uint32_t i) const;

  /**

   * \brief Obtain a pair indicating the exit direction from the root

   *

   * This method assumes there is only a single exit direction from the root.

   * Error occur if this assumption is invalid.

   *

   * \return The pair of next-hop-IP and outgoing-interface-index for reaching

   * 'this' vertex from the root

   */

  NodeExit_t GetRootExitDirection () const;

  /**

   * \brief Merge into 'this' vertex the list of exit directions from

   * another vertex

   *

   * This merge is necessary when ECMP are found. 

   *

   * \param vertex From which the list of exit directions are obtain

   * and are merged into 'this' vertex

   */

  void MergeRootExitDirections (const SPFVertex* vertex);

  /**

   * \brief Inherit all root exit directions from a given vertex to 'this' vertex

   * \param vertex The vertex from which all root exit directions are to be inherited

   *

   * After the call of this method, the original root exit directions

   * in 'this' vertex are all lost.

   */

  void InheritAllRootExitDirections (const SPFVertex* vertex);

  /**

   * \brief Get the number of exit directions from root for reaching 'this' vertex

   * \return The number of exit directions from root

   */

  uint32_t GetNRootExitDirections () const;

/**

 * @brief Get a pointer to the SPFVector that is the parent of "this" 

 * SPFVertex.

 * @internal

 *

 * Each router node in the simulation is associated with an SPFVertex object.

 * When calculating routes, each of these routers is, in turn, chosen as the 

 * "root" of the calculation and routes to all of the other routers are

 * eventually saved in the routing tables of each of the chosen nodes.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set and is the root of the SPF tree.

 *

 * This method returns a pointer to the parent node of "this" SPFVertex

 * (both of which reside in that SPF tree).

 *

 * @param i The index to one of the parents

 * @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex

 * in the SPF tree.

 */

  SPFVertex* GetParent (uint32_t i = 0) const;

/**

 * @brief Set the pointer to the SPFVector that is the parent of "this" 

 * SPFVertex.

 * @internal

 *

 * Each router node in the simulation is associated with an SPFVertex object.

 * When calculating routes, each of these routers is, in turn, chosen as the 

 * "root" of the calculation and routes to all of the other routers are

 * eventually saved in the routing tables of each of the chosen nodes.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set and is the root of the SPF tree.

 *

 * This method sets the parent pointer of "this" SPFVertex (both of which

 * reside in that SPF tree).

 *

 * @param parent A pointer to the SPFVertex that is the parent of "this" 

 * SPFVertex* in the SPF tree.

 */

  void SetParent (SPFVertex* parent);

  /**

   * \brief Merge the Parent list from the v into this vertex

   *

   * \param v The vertex from which its list of Parent is read

   * and then merged into the list of Parent of *this* vertex.

   * Note that the list in v remains intact

   */

  void MergeParent (const SPFVertex* v);

/**

 * @brief Get the number of children of "this" SPFVertex.

 * @internal

 *

 * Each router node in the simulation is associated with an SPFVertex object.

 * When calculating routes, each of these routers is, in turn, chosen as the 

 * "root" of the calculation and routes to all of the other routers are

 * eventually saved in the routing tables of each of the chosen nodes.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set and is the root of the SPF tree.  Each vertex

 * in the SPF tree can have a number of children that represent host or 

 * network routes available via that vertex.

 *

 * This method returns the number of children of "this" SPFVertex (which 

 * reside in the SPF tree).

 *

 * @returns The number of children of "this" SPFVertex (which reside in the

 * SPF tree).

 */

  uint32_t GetNChildren (void) const;

/**

 * @brief Get a borrowed SPFVertex pointer to the specified child of "this" 

 * SPFVertex.

 * @internal

 *

 * Each router node in the simulation is associated with an SPFVertex object.

 * When calculating routes, each of these routers is, in turn, chosen as the 

 * "root" of the calculation and routes to all of the other routers are

 * eventually saved in the routing tables of each of the chosen nodes.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set and is the root of the SPF tree.  Each vertex

 * in the SPF tree can have a number of children that represent host or 

 * network routes available via that vertex.

 *

 * This method the number of children of "this" SPFVertex (which reside in

 * the SPF tree.

 *

 * @see SPFVertex::GetNChildren

 * @param n The index (from 0 to the number of children minus 1) of the 

 * child SPFVertex to return.

 * @warning The pointer returned by GetChild () is a borrowed pointer.  You

 * do not have any ownership of the underlying object and must not delete

 * that object.

 * @returns A pointer to the specified child SPFVertex (which resides in the

 * SPF tree).

 */

  SPFVertex* GetChild (uint32_t n) const;

/**

 * @brief Get a borrowed SPFVertex pointer to the specified child of "this" 

 * SPFVertex.

 * @internal

 *

 * Each router node in the simulation is associated with an SPFVertex object.

 * When calculating routes, each of these routers is, in turn, chosen as the 

 * "root" of the calculation and routes to all of the other routers are

 * eventually saved in the routing tables of each of the chosen nodes.

 *

 * The "Root" vertex is then the SPFVertex representing the router that is

 * having its routing tables set and is the root of the SPF tree.  Each vertex

 * in the SPF tree can have a number of children that represent host or 

 * network routes available via that vertex.

 *

 * This method the number of children of "this" SPFVertex (which reside in

 * the SPF tree.

 *

 * @see SPFVertex::GetNChildren

 * @warning Ownership of the pointer added to the children of "this"