1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/internet-stack/ipv4-global-routing.cc Mon Dec 01 21:34:33 2008 -0800
1.3 @@ -0,0 +1,293 @@
1.4 +// -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*-
1.5 +//
1.6 +// Copyright (c) 2008 University of Washington
1.7 +//
1.8 +// This program is free software; you can redistribute it and/or modify
1.9 +// it under the terms of the GNU General Public License version 2 as
1.10 +// published by the Free Software Foundation;
1.11 +//
1.12 +// This program is distributed in the hope that it will be useful,
1.13 +// but WITHOUT ANY WARRANTY; without even the implied warranty of
1.14 +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1.15 +// GNU General Public License for more details.
1.16 +//
1.17 +// You should have received a copy of the GNU General Public License
1.18 +// along with this program; if not, write to the Free Software
1.19 +// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
1.20 +//
1.21 +
1.22 +#include "ns3/log.h"
1.23 +#include "ns3/object.h"
1.24 +#include "ipv4-global-routing.h"
1.25 +#include "ns3/packet.h"
1.26 +#include "ns3/node.h"
1.27 +
1.28 +NS_LOG_COMPONENT_DEFINE ("Ipv4GlobalRouting");
1.29 +
1.30 +namespace ns3 {
1.31 +
1.32 +NS_OBJECT_ENSURE_REGISTERED (Ipv4GlobalRouting);
1.33 +
1.34 +TypeId
1.35 +Ipv4GlobalRouting::GetTypeId (void)
1.36 +{
1.37 + static TypeId tid = TypeId ("ns3::Ipv4GlobalRouting")
1.38 + .SetParent<Object> ()
1.39 + ;
1.40 + return tid;
1.41 +}
1.42 +
1.43 +Ipv4GlobalRouting::Ipv4GlobalRouting ()
1.44 +{
1.45 + NS_LOG_FUNCTION_NOARGS ();
1.46 +}
1.47 +
1.48 +void
1.49 +Ipv4GlobalRouting::AddHostRouteTo (Ipv4Address dest,
1.50 + Ipv4Address nextHop,
1.51 + uint32_t interface)
1.52 +{
1.53 + NS_LOG_FUNCTION (dest << nextHop << interface);
1.54 + Ipv4Route *route = new Ipv4Route ();
1.55 + *route = Ipv4Route::CreateHostRouteTo (dest, nextHop, interface);
1.56 + m_hostRoutes.push_back (route);
1.57 +}
1.58 +
1.59 +void
1.60 +Ipv4GlobalRouting::AddHostRouteTo (Ipv4Address dest,
1.61 + uint32_t interface)
1.62 +{
1.63 + NS_LOG_FUNCTION (dest << interface);
1.64 + Ipv4Route *route = new Ipv4Route ();
1.65 + *route = Ipv4Route::CreateHostRouteTo (dest, interface);
1.66 + m_hostRoutes.push_back (route);
1.67 +}
1.68 +
1.69 +void
1.70 +Ipv4GlobalRouting::AddNetworkRouteTo (Ipv4Address network,
1.71 + Ipv4Mask networkMask,
1.72 + Ipv4Address nextHop,
1.73 + uint32_t interface)
1.74 +{
1.75 + NS_LOG_FUNCTION (network << networkMask << nextHop << interface);
1.76 + Ipv4Route *route = new Ipv4Route ();
1.77 + *route = Ipv4Route::CreateNetworkRouteTo (network,
1.78 + networkMask,
1.79 + nextHop,
1.80 + interface);
1.81 + m_networkRoutes.push_back (route);
1.82 +}
1.83 +
1.84 +void
1.85 +Ipv4GlobalRouting::AddNetworkRouteTo (Ipv4Address network,
1.86 + Ipv4Mask networkMask,
1.87 + uint32_t interface)
1.88 +{
1.89 + NS_LOG_FUNCTION (network << networkMask << interface);
1.90 + Ipv4Route *route = new Ipv4Route ();
1.91 + *route = Ipv4Route::CreateNetworkRouteTo (network,
1.92 + networkMask,
1.93 + interface);
1.94 + m_networkRoutes.push_back (route);
1.95 +}
1.96 +
1.97 +Ipv4Route *
1.98 +Ipv4GlobalRouting::LookupGlobal (Ipv4Address dest)
1.99 +{
1.100 + NS_LOG_FUNCTION_NOARGS ();
1.101 + for (HostRoutesCI i = m_hostRoutes.begin ();
1.102 + i != m_hostRoutes.end ();
1.103 + i++)
1.104 + {
1.105 + NS_ASSERT ((*i)->IsHost ());
1.106 + if ((*i)->GetDest ().IsEqual (dest))
1.107 + {
1.108 + NS_LOG_LOGIC ("Found global host route" << *i);
1.109 + return (*i);
1.110 + }
1.111 + }
1.112 + for (NetworkRoutesI j = m_networkRoutes.begin ();
1.113 + j != m_networkRoutes.end ();
1.114 + j++)
1.115 + {
1.116 + NS_ASSERT ((*j)->IsNetwork ());
1.117 + Ipv4Mask mask = (*j)->GetDestNetworkMask ();
1.118 + Ipv4Address entry = (*j)->GetDestNetwork ();
1.119 + if (mask.IsMatch (dest, entry))
1.120 + {
1.121 + NS_LOG_LOGIC ("Found global network route" << *j);
1.122 + return (*j);
1.123 + }
1.124 + }
1.125 + return 0;
1.126 +}
1.127 +
1.128 +uint32_t
1.129 +Ipv4GlobalRouting::GetNRoutes (void)
1.130 +{
1.131 + NS_LOG_FUNCTION_NOARGS ();
1.132 + uint32_t n = 0;
1.133 + n += m_hostRoutes.size ();
1.134 + n += m_networkRoutes.size ();
1.135 + return n;
1.136 +}
1.137 +
1.138 +Ipv4Route *
1.139 +Ipv4GlobalRouting::GetRoute (uint32_t index)
1.140 +{
1.141 + NS_LOG_FUNCTION (index);
1.142 + if (index < m_hostRoutes.size ())
1.143 + {
1.144 + uint32_t tmp = 0;
1.145 + for (HostRoutesCI i = m_hostRoutes.begin ();
1.146 + i != m_hostRoutes.end ();
1.147 + i++)
1.148 + {
1.149 + if (tmp == index)
1.150 + {
1.151 + return *i;
1.152 + }
1.153 + tmp++;
1.154 + }
1.155 + }
1.156 + index -= m_hostRoutes.size ();
1.157 + uint32_t tmp = 0;
1.158 + for (NetworkRoutesI j = m_networkRoutes.begin ();
1.159 + j != m_networkRoutes.end ();
1.160 + j++)
1.161 + {
1.162 + if (tmp == index)
1.163 + {
1.164 + return *j;
1.165 + }
1.166 + tmp++;
1.167 + }
1.168 + NS_ASSERT (false);
1.169 + // quiet compiler.
1.170 + return 0;
1.171 +}
1.172 +void
1.173 +Ipv4GlobalRouting::RemoveRoute (uint32_t index)
1.174 +{
1.175 + NS_LOG_FUNCTION (index);
1.176 + if (index < m_hostRoutes.size ())
1.177 + {
1.178 + uint32_t tmp = 0;
1.179 + for (HostRoutesI i = m_hostRoutes.begin ();
1.180 + i != m_hostRoutes.end ();
1.181 + i++)
1.182 + {
1.183 + if (tmp == index)
1.184 + {
1.185 + NS_LOG_LOGIC ("Removing route " << index << "; size = " << m_hostRoutes.size());
1.186 + delete *i;
1.187 + m_hostRoutes.erase (i);
1.188 + NS_LOG_LOGIC ("Done removing host route " << index << "; host route remaining size = " << m_hostRoutes.size());
1.189 + return;
1.190 + }
1.191 + tmp++;
1.192 + }
1.193 + }
1.194 + index -= m_hostRoutes.size ();
1.195 + uint32_t tmp = 0;
1.196 + for (NetworkRoutesI j = m_networkRoutes.begin ();
1.197 + j != m_networkRoutes.end ();
1.198 + j++)
1.199 + {
1.200 + if (tmp == index)
1.201 + {
1.202 + NS_LOG_LOGIC ("Removing route " << index << "; size = " << m_networkRoutes.size());
1.203 + delete *j;
1.204 + m_networkRoutes.erase (j);
1.205 + NS_LOG_LOGIC ("Done removing network route " << index << "; network route remaining size = " << m_networkRoutes.size());
1.206 + return;
1.207 + }
1.208 + tmp++;
1.209 + }
1.210 + NS_ASSERT (false);
1.211 +}
1.212 +
1.213 +bool
1.214 +Ipv4GlobalRouting::RequestRoute (
1.215 + uint32_t ifIndex,
1.216 + Ipv4Header const &ipHeader,
1.217 + Ptr<Packet> packet,
1.218 + RouteReplyCallback routeReply)
1.219 +{
1.220 + NS_LOG_FUNCTION (this << ifIndex << &ipHeader << packet << &routeReply);
1.221 +
1.222 + NS_LOG_LOGIC ("source = " << ipHeader.GetSource ());
1.223 +
1.224 + NS_LOG_LOGIC ("destination = " << ipHeader.GetDestination ());
1.225 +
1.226 + if (ipHeader.GetDestination ().IsMulticast ())
1.227 + {
1.228 + NS_LOG_LOGIC ("Multicast destination-- returning false");
1.229 + return false; // Let other routing protocols try to handle this
1.230 + }
1.231 +
1.232 +// This is a unicast packet. Check to see if we have a route for it.
1.233 +//
1.234 + NS_LOG_LOGIC ("Unicast destination- looking up");
1.235 + Ipv4Route *route = LookupGlobal (ipHeader.GetDestination ());
1.236 + if (route != 0)
1.237 + {
1.238 + routeReply (true, *route, packet, ipHeader);
1.239 + return true;
1.240 + }
1.241 + else
1.242 + {
1.243 + return false; // Let other routing protocols try to handle this
1.244 + // route request.
1.245 + }
1.246 +}
1.247 +
1.248 +bool
1.249 +Ipv4GlobalRouting::RequestIfIndex (Ipv4Address destination, uint32_t& ifIndex)
1.250 +{
1.251 + NS_LOG_FUNCTION (this << destination << &ifIndex);
1.252 +//
1.253 +// First, see if this is a multicast packet we have a route for. If we
1.254 +// have a route, then send the packet down each of the specified interfaces.
1.255 +//
1.256 + if (destination.IsMulticast ())
1.257 + {
1.258 + NS_LOG_LOGIC ("Multicast destination-- returning false");
1.259 + return false; // Let other routing protocols try to handle this
1.260 + }
1.261 +//
1.262 +// See if this is a unicast packet we have a route for.
1.263 +//
1.264 + NS_LOG_LOGIC ("Unicast destination- looking up");
1.265 + Ipv4Route *route = LookupGlobal (destination);
1.266 + if (route)
1.267 + {
1.268 + ifIndex = route->GetInterface ();
1.269 + return true;
1.270 + }
1.271 + else
1.272 + {
1.273 + return false;
1.274 + }
1.275 +}
1.276 +
1.277 +void
1.278 +Ipv4GlobalRouting::DoDispose (void)
1.279 +{
1.280 + NS_LOG_FUNCTION_NOARGS ();
1.281 + for (HostRoutesI i = m_hostRoutes.begin ();
1.282 + i != m_hostRoutes.end ();
1.283 + i = m_hostRoutes.erase (i))
1.284 + {
1.285 + delete (*i);
1.286 + }
1.287 + for (NetworkRoutesI j = m_networkRoutes.begin ();
1.288 + j != m_networkRoutes.end ();
1.289 + j = m_networkRoutes.erase (j))
1.290 + {
1.291 + delete (*j);
1.292 + }
1.293 + Ipv4RoutingProtocol::DoDispose ();
1.294 +}
1.295 +
1.296 +}//namespace ns3
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/internet-stack/ipv4-global-routing.h Mon Dec 01 21:34:33 2008 -0800
2.3 @@ -0,0 +1,270 @@
2.4 +// -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*-
2.5 +//
2.6 +// Copyright (c) 2008 University of Washington
2.7 +//
2.8 +// This program is free software; you can redistribute it and/or modify
2.9 +// it under the terms of the GNU General Public License version 2 as
2.10 +// published by the Free Software Foundation;
2.11 +//
2.12 +// This program is distributed in the hope that it will be useful,
2.13 +// but WITHOUT ANY WARRANTY; without even the implied warranty of
2.14 +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2.15 +// GNU General Public License for more details.
2.16 +//
2.17 +// You should have received a copy of the GNU General Public License
2.18 +// along with this program; if not, write to the Free Software
2.19 +// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
2.20 +//
2.21 +//
2.22 +
2.23 +#ifndef IPV4_GLOBAL_ROUTING_H
2.24 +#define IPV4_GLOBAL_ROUTING_H
2.25 +
2.26 +#include <list>
2.27 +#include <stdint.h>
2.28 +#include "ns3/ipv4-address.h"
2.29 +#include "ns3/ipv4-header.h"
2.30 +#include "ns3/ptr.h"
2.31 +#include "ns3/ipv4.h"
2.32 +
2.33 +namespace ns3 {
2.34 +
2.35 +class Packet;
2.36 +class NetDevice;
2.37 +class Ipv4Interface;
2.38 +class Ipv4Address;
2.39 +class Ipv4Header;
2.40 +class Ipv4Route;
2.41 +class Node;
2.42 +
2.43 +
2.44 +/**
2.45 + * @brief Global routing protocol for IP version 4 stacks.
2.46 + *
2.47 + * In ns-3 we have the concept of a pluggable routing protocol. Routing
2.48 + * protocols are added to a list maintained by the Ipv4L3Protocol. Every
2.49 + * stack gets one routing protocol for free -- the Ipv4StaticRouting routing
2.50 + * protocol is added in the constructor of the Ipv4L3Protocol (this is the
2.51 + * piece of code that implements the functionality of the IP layer).
2.52 + *
2.53 + * As an option to running a dynamic routing protocol, a GlobalRouteManager
2.54 + * object has been created to allow users to build routes for all participating
2.55 + * nodes. One can think of this object as a "routing oracle"; it has
2.56 + * an omniscient view of the topology, and can construct shortest path
2.57 + * routes between all pairs of nodes. These routes must be stored
2.58 + * somewhere in the node, so therefore this class Ipv4GlobalRouting
2.59 + * is used as one of the pluggable routing protocols. It is kept distinct
2.60 + * from Ipv4StaticRouting because these routes may be dynamically cleared
2.61 + * and rebuilt in the middle of the simulation, while manually entered
2.62 + * routes into the Ipv4StaticRouting may need to be kept distinct.
2.63 + *
2.64 + * This class deals with Ipv4 unicast routes only.
2.65 + *
2.66 + * @see Ipv4RoutingProtocol
2.67 + * @see GlobalRouteManager
2.68 + */
2.69 +class Ipv4GlobalRouting : public Ipv4RoutingProtocol
2.70 +{
2.71 +public:
2.72 + static TypeId GetTypeId (void);
2.73 +/**
2.74 + * @brief Construct an empty Ipv4GlobalRouting routing protocol,
2.75 + *
2.76 + * The Ipv4GlobalRouting class supports host and network unicast routes.
2.77 + * This method initializes the lists containing these routes to empty.
2.78 + *
2.79 + * @see Ipv4GlobalRouting
2.80 + */
2.81 + Ipv4GlobalRouting ();
2.82 +
2.83 +/**
2.84 + * @brief Request that a check for a route bw performed and if a route is found
2.85 + * that the packet be sent on its way using the pre-packaged send callback.
2.86 + *
2.87 + * The source and destination IP addresses for the packet in question are found
2.88 + * in the provided Ipv4Header. There are two major processing forks depending
2.89 + * on the type of destination address.
2.90 + *
2.91 + * If the destination address is unicast then the routing table is consulted
2.92 + * for a route to the destination and if it is found, the routeReply callback
2.93 + * is executed to send the packet (with the found route).
2.94 + *
2.95 + * If the destination address is a multicast, then the method will return
2.96 + * false.
2.97 + *
2.98 + * @param ifIndex The network interface index over which the packed was
2.99 + * received. If the packet is from a local source, ifIndex will be set to
2.100 + * Ipv4RoutingProtocol::IF_INDEX_ANY.
2.101 + * @param ipHeader the Ipv4Header containing the source and destination IP
2.102 + * addresses for the packet.
2.103 + * @param packet The packet to be sent if a route is found.
2.104 + * @param routeReply A callback that packaged up the call to actually send the
2.105 + * packet.
2.106 + * @return Returns true if a route is found and the packet has been sent,
2.107 + * otherwise returns false indicating that the next routing protocol should
2.108 + * be consulted.
2.109 + *
2.110 + * @see Ipv4GlobalRouting
2.111 + * @see Ipv4RoutingProtocol
2.112 + */
2.113 + virtual bool RequestRoute (uint32_t ifIndex,
2.114 + Ipv4Header const &ipHeader,
2.115 + Ptr<Packet> packet,
2.116 + RouteReplyCallback routeReply);
2.117 +
2.118 +/**
2.119 + * @brief Check to see if we can determine the interface index that will be
2.120 + * used if a packet is sent to this destination.
2.121 + *
2.122 + * This method addresses a problem in the IP stack where a destination address
2.123 + * must be present and checksummed into the IP header before the actual
2.124 + * interface over which the packet is sent can be determined. The answer is
2.125 + * to implement a known and intentional cross-layer violation. This is the
2.126 + * endpoint of a call chain that started up quite high in the stack (sockets)
2.127 + * and has found its way down to the Ipv4L3Protocol which is consulting the
2.128 + * routing protocols for what they would do if presented with a packet of the
2.129 + * given destination.
2.130 + *
2.131 + * If there are multiple paths out of the node, the resolution is performed
2.132 + * by Ipv4L3Protocol::GetIfIndexforDestination which has access to more
2.133 + * contextual information that is useful for making a determination.
2.134 + *
2.135 + * This method will return false on a multicast address.
2.136 + *
2.137 + * @param destination The Ipv4Address if the destination of a hypothetical
2.138 + * packet. This may be a multicast group address.
2.139 + * @param ifIndex A reference to the interface index over which a packet
2.140 + * sent to this destination would be sent.
2.141 + * @return Returns true if a route is found to the destination that involves
2.142 + * a single output interface index, otherwise returns false indicating that
2.143 + * the next routing protocol should be consulted.
2.144 + *
2.145 + * @see Ipv4GlobalRouting
2.146 + * @see Ipv4RoutingProtocol
2.147 + * @see Ipv4L3Protocol
2.148 + */
2.149 + virtual bool RequestIfIndex (Ipv4Address destination, uint32_t& ifIndex);
2.150 +
2.151 +/**
2.152 + * @brief Add a host route to the global routing table.
2.153 + *
2.154 + * @param dest The Ipv4Address destination for this route.
2.155 + * @param nextHop The Ipv4Address of the next hop in the route.
2.156 + * @param interface The network interface index used to send packets to the
2.157 + * destination.
2.158 + *
2.159 + * @see Ipv4Address
2.160 + */
2.161 + void AddHostRouteTo (Ipv4Address dest,
2.162 + Ipv4Address nextHop,
2.163 + uint32_t interface);
2.164 +/**
2.165 + * @brief Add a host route to the global routing table.
2.166 + *
2.167 + * @param dest The Ipv4Address destination for this route.
2.168 + * @param interface The network interface index used to send packets to the
2.169 + * destination.
2.170 + *
2.171 + * @see Ipv4Address
2.172 + */
2.173 + void AddHostRouteTo (Ipv4Address dest,
2.174 + uint32_t interface);
2.175 +
2.176 +/**
2.177 + * @brief Add a network route to the global routing table.
2.178 + *
2.179 + * @param network The Ipv4Address network for this route.
2.180 + * @param networkMask The Ipv4Mask to extract the network.
2.181 + * @param nextHop The next hop in the route to the destination network.
2.182 + * @param interface The network interface index used to send packets to the
2.183 + * destination.
2.184 + *
2.185 + * @see Ipv4Address
2.186 + */
2.187 + void AddNetworkRouteTo (Ipv4Address network,
2.188 + Ipv4Mask networkMask,
2.189 + Ipv4Address nextHop,
2.190 + uint32_t interface);
2.191 +
2.192 +/**
2.193 + * @brief Add a network route to the global routing table.
2.194 + *
2.195 + * @param network The Ipv4Address network for this route.
2.196 + * @param networkMask The Ipv4Mask to extract the network.
2.197 + * @param interface The network interface index used to send packets to the
2.198 + * destination.
2.199 + *
2.200 + * @see Ipv4Address
2.201 + */
2.202 + void AddNetworkRouteTo (Ipv4Address network,
2.203 + Ipv4Mask networkMask,
2.204 + uint32_t interface);
2.205 +
2.206 +/**
2.207 + * @brief Get the number of individual unicast routes that have been added
2.208 + * to the routing table.
2.209 + *
2.210 + * @warning The default route counts as one of the routes.
2.211 + */
2.212 + uint32_t GetNRoutes (void);
2.213 +
2.214 +/**
2.215 + * @brief Get a route from the global unicast routing table.
2.216 + *
2.217 + * Externally, the unicast global routing table appears simply as a table with
2.218 + * n entries. The one sublety of note is that if a default route has been set
2.219 + * it will appear as the zeroth entry in the table. This means that if you
2.220 + * add only a default route, the table will have one entry that can be accessed
2.221 + * either by explicity calling GetDefaultRoute () or by calling GetRoute (0).
2.222 + *
2.223 + * Similarly, if the default route has been set, calling RemoveRoute (0) will
2.224 + * remove the default route.
2.225 + *
2.226 + * @param i The index (into the routing table) of the route to retrieve. If
2.227 + * the default route has been set, it will occupy index zero.
2.228 + * @return If route is set, a pointer to that Ipv4Route is returned, otherwise
2.229 + * a zero pointer is returned.
2.230 + *
2.231 + * @see Ipv4Route
2.232 + * @see Ipv4GlobalRouting::RemoveRoute
2.233 + */
2.234 + Ipv4Route *GetRoute (uint32_t i);
2.235 +
2.236 +/**
2.237 + * @brief Remove a route from the global unicast routing table.
2.238 + *
2.239 + * Externally, the unicast global routing table appears simply as a table with
2.240 + * n entries. The one sublety of note is that if a default route has been set
2.241 + * it will appear as the zeroth entry in the table. This means that if the
2.242 + * default route has been set, calling RemoveRoute (0) will remove the
2.243 + * default route.
2.244 + *
2.245 + * @param i The index (into the routing table) of the route to remove. If
2.246 + * the default route has been set, it will occupy index zero.
2.247 + *
2.248 + * @see Ipv4Route
2.249 + * @see Ipv4GlobalRouting::GetRoute
2.250 + * @see Ipv4GlobalRouting::AddRoute
2.251 + */
2.252 + void RemoveRoute (uint32_t i);
2.253 +
2.254 +protected:
2.255 + void DoDispose (void);
2.256 +
2.257 +private:
2.258 + typedef std::list<Ipv4Route *> HostRoutes;
2.259 + typedef std::list<Ipv4Route *>::const_iterator HostRoutesCI;
2.260 + typedef std::list<Ipv4Route *>::iterator HostRoutesI;
2.261 + typedef std::list<Ipv4Route *> NetworkRoutes;
2.262 + typedef std::list<Ipv4Route *>::const_iterator NetworkRoutesCI;
2.263 + typedef std::list<Ipv4Route *>::iterator NetworkRoutesI;
2.264 +
2.265 + Ipv4Route *LookupGlobal (Ipv4Address dest);
2.266 +
2.267 + HostRoutes m_hostRoutes;
2.268 + NetworkRoutes m_networkRoutes;
2.269 +};
2.270 +
2.271 +} // Namespace ns3
2.272 +
2.273 +#endif /* IPV4_GLOBAL_ROUTING_H */