CandidateList_t::iterator i = m_candidates.begin ();  

  CandidateList_t::iterator i = std::upper_bound (

    m_candidates.begin (), m_candidates.end (), vNew,

  for (; i != m_candidates.end (); i++)

    &CandidateQueue::CompareSPFVertex

    {

    );

      SPFVertex *v = *i;

  m_candidates.insert (i, vNew);

      if (vNew->GetDistanceFromRoot () < v->GetDistanceFromRoot ())

        {

          break;

        }

    }

  m_candidates.insert(i, vNew);

  while (!m_candidates.empty ()) {

  m_candidates.sort (&CandidateQueue::CompareSPFVertex);

    SPFVertex *v = m_candidates.front ();

  NS_LOG_LOGIC ("After reordering the CandidateQueue");

    m_candidates.pop_front ();

  NS_LOG_LOGIC (*this);

    temp.push_back(v);

}

  }

  while (!temp.empty ()) {

/*

    Push (temp.front ());

 * In this implementation, SPFVertex follows the ordering where

    temp.pop_front ();

 * a vertex is ranked first if its GetDistanceFromRoot () is smaller;

  }

 * In case of a tie, NetworkLSA is always ranked before RouterLSA.

 *

 * This ordering is necessary for implementing ECMP

 */

bool 

CandidateQueue::CompareSPFVertex (const SPFVertex* v1, const SPFVertex* v2)

{

  NS_LOG_FUNCTION (&v1 << &v2);

  bool result = false;

  if (v1->GetDistanceFromRoot () < v2->GetDistanceFromRoot ())

    {  

      result = true;

    }

  else if (v1->GetDistanceFromRoot () == v2->GetDistanceFromRoot ())

    {

      if (v1->GetVertexType () == SPFVertex::VertexNetwork 

          && v2->GetVertexType () == SPFVertex::VertexRouter)

        {

          result = true;

        }

    }

  return result;

  m_parent (0),

  m_parents (),

  m_parent (0),

  m_parents (),

  NS_LOG_FUNCTION_NOARGS ();

  NS_LOG_FUNCTION (m_vertexId);

  for ( ListOfSPFVertex_t::iterator i = m_children.begin ();

        i != m_children.end ();

  NS_LOG_LOGIC ("Children vertices - " << m_children);

        i++)

  NS_LOG_LOGIC ("Parent verteices - " << m_parents);

  // find this node from all its parents and remove the entry of this node

  // from all its parents

  for (ListOfSPFVertex_t::iterator piter = m_parents.begin (); 

      piter != m_parents.end (); 

      piter++)

      SPFVertex *p = *i;

      // remove the current vertex from its parent's children list. Check

      // if the size of the list is reduced, or the child<->parent relation

      // is not bidirectional

      uint32_t orgCount = (*piter)->m_children.size ();

      (*piter)->m_children.remove (this);

      uint32_t newCount = (*piter)->m_children.size ();

      NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex from its parents --- impossible!");

    }

  // delete children

  while (m_children.size () > 0)

    {

      // pop out children one by one. Some children may disapper 

      // when deleting some other children in the list. As a result,

      // it is necessary to use pop to walk through all children, instead

      // of using iterator.

      //

      // Note that m_children.pop_front () is not necessary as this

      // p is removed from the children list when p is deleted

      SPFVertex* p = m_children.front ();

      // 'p' == 0, this child is already deleted by its other parent

      if (p == 0) continue;

      NS_LOG_LOGIC ("Parent vertex-" << m_vertexId << " deleting its child vertex-" << p->GetVertexId ());

  void 

void 

  uint32_t 

uint32_t 

  m_parent = parent;

  // always maintain only one parent when using setter/getter methods

  m_parents.clear ();

  m_parents.push_back (parent);

SPFVertex::GetParent (void) const

SPFVertex::GetParent (uint32_t i) const

  return m_parent;

  // If the index i is out-of-range, return 0 and do nothing

  if (m_parents.size () <= i)

    {

      NS_LOG_LOGIC ("Index to SPFVertex's parent is out-of-range.");

      return 0;

    }

  ListOfSPFVertex_t::const_iterator iter = m_parents.begin ();

  while (i-- > 0) 

    {

      iter++;

    }

  return *iter;

  uint32_t 

void 

SPFVertex::MergeParent (const SPFVertex* v)

{

  NS_LOG_FUNCTION (v);

  NS_LOG_LOGIC ("Before merge, list of parents = " << m_parents);

  // combine the two lists first, and then remove any duplicated after

  m_parents.insert (m_parents.end (), 

    v->m_parents.begin (), v->m_parents.end ());

  // remove duplication

  m_parents.sort ();

  m_parents.unique ();

  NS_LOG_LOGIC ("After merge, list of parents = " << m_parents);

}

void 

SPFVertex::SetRootExitDirection (Ipv4Address nextHop, int32_t id)

{

  NS_LOG_FUNCTION (nextHop << id);

  // always maintain only one root's exit

  m_ecmpRootExits.clear ();

  m_ecmpRootExits.push_back (NodeExit_t (nextHop, id));

  // update the following in order to be backward compatitable with

  // GetNextHop and GetOutgoingInterface methods

  m_nextHop = nextHop;

  m_rootOif = id;

}

void 

SPFVertex::SetRootExitDirection (SPFVertex::NodeExit_t exit)

{

  NS_LOG_FUNCTION (exit);

  SetRootExitDirection (exit.first, exit.second);

}

SPFVertex::NodeExit_t

SPFVertex::GetRootExitDirection (uint32_t i) const

{

  NS_LOG_FUNCTION (i);

  typedef ListOfNodeExit_t::const_iterator CIter_t;

  NS_ASSERT_MSG (i < m_ecmpRootExits.size (), "Index out-of-range when accessing SPFVertex::m_ecmpRootExits!");

  CIter_t iter = m_ecmpRootExits.begin ();

  while (i-- > 0) {iter++;}

  return *iter;

}

SPFVertex::NodeExit_t 

SPFVertex::GetRootExitDirection () const

{

  NS_LOG_FUNCTION_NOARGS ();

  NS_ASSERT_MSG (m_ecmpRootExits.size () <= 1, "Assumed there is at most one exit from the root to this vertex");

  return GetRootExitDirection (0);

}

void 

SPFVertex::MergeRootExitDirections (const SPFVertex* vertex)

{

  NS_LOG_FUNCTION (vertex);

  // obtain the external list of exit directions

  //

  // Append the external list into 'this' and remove duplication afterward

  const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits;

  m_ecmpRootExits.insert (m_ecmpRootExits.end (), 

    extList.begin(), extList.end ());

  m_ecmpRootExits.sort ();

  m_ecmpRootExits.unique ();

}

void 

SPFVertex::InheritAllRootExitDirections (const SPFVertex* vertex)

{

  NS_LOG_FUNCTION (vertex);

  // discard all exit direction currently assoicated with this vertex,

  // and copy all the exit directions from the given vertex

  if (m_ecmpRootExits.size () > 0)

    {

      NS_LOG_WARN ("x root exit directions in this vertex are going to be discarded");

    }

  m_ecmpRootExits.clear ();

  m_ecmpRootExits.insert (m_ecmpRootExits.end (), 

      vertex->m_ecmpRootExits.begin (), vertex->m_ecmpRootExits.end ());

}

uint32_t 

SPFVertex::GetNRootExitDirections () const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_ecmpRootExits.size ();

}

uint32_t 

  m_spfroot (0) 

  m_spfroot (0)

//

// prepare vertex w

          w = new SPFVertex (w_lsa);

          w = candidate.Find (w_lsa->GetLinkStateId ());

          if (w->GetDistanceFromRoot () < distance)

/* (quagga-0.98.6) W is already on the candidate list; call it cw.

* Compare the previously calculated cost (cw->distance)

* with the cost we just determined (w->distance) to see

* if we've found a shorter path.

*/

          SPFVertex* cw;

          cw = candidate.Find (w_lsa->GetLinkStateId ());

          if (cw->GetDistanceFromRoot () < distance)

          else if (w->GetDistanceFromRoot () == distance)

          else if (cw->GetDistanceFromRoot () == distance)

// This path is one with an equal cost.  Do nothing for now -- we're not doing

// This path is one with an equal cost.  

// equal-cost multipath cases yet.

          else

          else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot ()

              if (SPFNexthopCalculation (v, w, l, distance))

              if (SPFNexthopCalculation (v, cw, l, distance))

            } // new lower cost path found   

            } // new lower cost path found  

          w->SetNextHop (linkRemote->GetLinkData ());

          Ipv4Address nextHop = linkRemote->GetLinkData ();

          w->SetOutgoingInterfaceId (

          uint32_t outIf = FindOutgoingInterfaceId (l->GetLinkData ());

            FindOutgoingInterfaceId (l->GetLinkData ()));

          w->SetRootExitDirection (nextHop, outIf);

            " goes through next hop " << w->GetNextHop () <<

            " goes through next hop " << nextHop <<

            " via outgoing interface " << w->GetOutgoingInterfaceId () <<

            " via outgoing interface " << outIf <<

          w->SetOutgoingInterfaceId (

          uint32_t outIf = FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), 

            FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), 

            w_lsa->GetNetworkLSANetworkMask () );

            w_lsa->GetNetworkLSANetworkMask () ));

// Set the next hop to 0.0.0.0 meaning "not exist"

          Ipv4Address nextHop = Ipv4Address::GetZero ();

          w->SetRootExitDirection (nextHop, outIf);

            " via outgoing interface " << w->GetOutgoingInterfaceId () <<

            " via outgoing interface " << outIf <<

                w->SetNextHop (linkRemote->GetLinkData ());

                Ipv4Address nextHop = linkRemote->GetLinkData ();

                w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ());

                uint32_t outIf = v->GetRootExitDirection ().second;

                w->SetRootExitDirection (nextHop, outIf);

                  " goes through next hop " << w->GetNextHop () <<

                  " goes through next hop " << nextHop <<

                  " via outgoing interface " << w->GetOutgoingInterfaceId ());

                  " via outgoing interface " << outIf);

          w->SetNextHop (v->GetNextHop ());

          w->SetRootExitDirection (v->GetRootExitDirection ());

          w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ());

      w->SetNextHop (v->GetNextHop ());

      w->InheritAllRootExitDirections (v);

      w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ());

// find all equal-cost paths. We don't do this at this moment, we should add

// find all equal-cost paths. 

// the treatment above codes. -- kunihiro. 

          if (v->GetOutgoingInterfaceId () >= 0)

          // walk through all next-hop-IPs and out-going-interfaces for reaching

          // the stub network gateway 'v' from the root node

          for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)

              gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), v->GetOutgoingInterfaceId ());

              SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i);

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

              Ipv4Address nextHop = exit.first;

                " add network route to " << tempip <<

              int32_t outIf = exit.second;

                " using next hop " << v->GetNextHop () <<

              if (outIf >= 0)

                " via interface " << v->GetOutgoingInterfaceId ());

                {

            }

                  gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);

          else

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

            {

                    " add network route to " << tempip <<

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

                    " using next hop " << nextHop <<

                " NOT able to add network route to " << tempip <<

                    " via interface " << outIf);

                " using next hop " << v->GetNextHop () <<

                }

                " since outgoing interface id is negative");

              else

                {

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

                    " NOT able to add network route to " << tempip <<

                    " using next hop " << nextHop <<

                    " since outgoing interface id is negative");

                }

              if (v->GetOutgoingInterfaceId () >= 0)

              // walk through all available exit directions due to ECMP,

                {

              // and add host route for each of the exit direction toward

                  gr->AddHostRouteTo (lr->GetLinkData (), v->GetNextHop (),

              // the vertex 'v'

                    v->GetOutgoingInterfaceId ());

              for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)

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

              {

                    " adding host route to " << lr->GetLinkData () <<

                SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i);

                    " using next hop " << v->GetNextHop () <<

                Ipv4Address nextHop = exit.first;

                    " and outgoing interface " << v->GetOutgoingInterfaceId ());

                int32_t outIf = exit.second;

                }

                if (outIf >= 0)

              else

                  {

                {

                    gr->AddHostRouteTo (lr->GetLinkData (), nextHop,

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

                      outIf);

                    " NOT able to add host route to " << lr->GetLinkData () <<

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

                    " using next hop " << v->GetNextHop () <<

                      " adding host route to " << lr->GetLinkData () <<

                    " since outgoing interface id is negative");

                      " using next hop " << nextHop <<

                }

                      " and outgoing interface " << outIf);

                  }

                else

                  {

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

                      " NOT able to add host route to " << lr->GetLinkData () <<

                      " using next hop " << nextHop <<

                      " since outgoing interface id is negative " << outIf);

                  }

              } // for all routes from the root the vertex 'v'

          if (v->GetOutgoingInterfaceId () >= 0)

          // walk through all available exit directions due to ECMP,

            {

          // and add host route for each of the exit direction toward

              gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (),

          // the vertex 'v'

                v->GetOutgoingInterfaceId ());

          for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)

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

          {

                " add network route to " << tempip <<

            SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i);

                " using next hop " << v->GetNextHop () <<

            Ipv4Address nextHop = exit.first;

                " via interface " << v->GetOutgoingInterfaceId ());

            int32_t outIf = exit.second;

            }

          else

            if (outIf >= 0)

            {

              {

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

                gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);

                " NOT able to add network route to " << tempip <<

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

                " using next hop " << v->GetNextHop () <<

                  " add network route to " << tempip <<

                " since outgoing interface id is negative");

                  " using next hop " << nextHop <<

                  " via interface " << outIf);

              }

            else

              {

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

                  " NOT able to add network route to " << tempip <<

                  " using next hop " << nextHop <<

                  " since outgoing interface id is negative " << outIf);

              }

  v->GetParent ()->AddChild (v);

  for (uint32_t i=0;;)

    {

      SPFVertex* parent;

      // check if all parents of vertex v

      if ((parent = v->GetParent (i++)) == 0) break;

      parent->AddChild (v);

    }

  uint32_t GetOutgoingInterfaceId (void) const;

  uint32_t GetOutgoingInterfaceId (void) const NS_DEPRECATED;

  void SetOutgoingInterfaceId (int32_t id);

  void SetOutgoingInterfaceId (int32_t id) NS_DEPRECATED;

  Ipv4Address GetNextHop (void) const;

  Ipv4Address GetNextHop (void) const NS_DEPRECATED;

  void SetNextHop (Ipv4Address nextHop);

  void SetNextHop (Ipv4Address nextHop) NS_DEPRECATED;

/**

 * @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;

/**

 * @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 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 inherrited

   *

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

  SPFVertex* GetParent (void) const;

  SPFVertex* GetParent (uint32_t i = 0) const;

  SPFVertex* m_parent;

  typedef std::list< NodeExit_t > ListOfNodeExit_t;

  /// store the multiple root's exits for supporting ECMP

  ListOfNodeExit_t m_ecmpRootExits;

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

          allRoutes.push_back (*i);

          route = (*i);

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

          found = true; 

          break;

  if (found == false)

  if (allRoutes.size () == 0) // if no host route is found

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

              allRoutes.push_back (*j);

              route = (*j);

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

              found = true;

              break;

  if (found == false)

  if (allRoutes.size () == 0)  // consider external if no host/network found

              found = true;

              allRoutes.push_back (*k);

  if (found == true)

  if (allRoutes.size () > 0 ) // if route(s) is found