1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ 2 /* 3 * Copyright (c) 2009 The Georgia Institute of Technology 4 * Copyright (c) 2021 NITK Surathkal 5 * 6 * This program is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License version 2 as 8 * published by the Free Software Foundation; 9 * 10 * This program is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program; if not, write to the Free Software 17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 18 * 19 * This file is adapted from the old ipv4-nix-vector-routing.h. 20 * 21 * Authors: Josh Pelkey <jpelkey@gatech.edu> 22 * 23 * Modified by: Ameya Deshpande <ameyanrd@outlook.com> 24 */ 25 26 #ifndef NIX_VECTOR_ROUTING_H 27 #define NIX_VECTOR_ROUTING_H 28 29 #include "ns3/channel.h" 30 #include "ns3/node-container.h" 31 #include "ns3/node-list.h" 32 #include "ns3/net-device-container.h" 33 #include "ns3/ipv4-routing-protocol.h" 34 #include "ns3/ipv4-route.h" 35 #include "ns3/ipv6-route.h" 36 #include "ns3/ipv6-routing-protocol.h" 37 #include "ns3/nix-vector.h" 38 #include "ns3/bridge-net-device.h" 39 #include "ns3/nstime.h" 40 #include "ns3/ipv4-interface.h" 41 #include "ns3/ipv6-interface.h" 42 #include "ns3/ipv4-l3-protocol.h" 43 #include "ns3/ipv6-l3-protocol.h" 44 45 #include <map> 46 #include <unordered_map> 47 48 namespace ns3 { 49 50 /** 51 * \defgroup nix-vector-routing Nix-Vector Routing 52 * 53 * Nix-vector routing is a simulation specific routing protocol and is 54 * intended for large network topologies. 55 */ 56 57 /** 58 * \ingroup nix-vector-routing 59 * Nix-vector routing protocol 60 * 61 * \internal 62 * Since this class is meant to be specialized only by Ipv4RoutingProtocol or 63 * Ipv6RoutingProtocol the implementation of this class doesn't need to be 64 * exposed here; it is in nix-vector-routing.cc. 65 */ 66 template <typename T> 67 class NixVectorRouting : public std::enable_if<std::is_same<Ipv4RoutingProtocol, T>::value || std::is_same<Ipv6RoutingProtocol, T>::value, T>::type 68 { 69 /// Alias for determining whether the parent is Ipv4RoutingProtocol or Ipv6RoutingProtocol 70 using IsIpv4 = std::is_same <Ipv4RoutingProtocol, T>; 71 72 /// Alias for Ipv4 and Ipv6 classes 73 using Ip = typename std::conditional <IsIpv4::value, Ipv4, Ipv6>::type; 74 75 /// Alias for Ipv4Address and Ipv6Address classes 76 using IpAddress = typename std::conditional<IsIpv4::value, Ipv4Address, Ipv6Address>::type; 77 78 /// Alias for Ipv4Route and Ipv6Route classes 79 using IpRoute = typename std::conditional<IsIpv4::value, Ipv4Route, Ipv6Route>::type; 80 81 /// Alias for Ipv4AddressHash and Ipv6AddressHash classes 82 using IpAddressHash = typename std::conditional<IsIpv4::value, Ipv4AddressHash, Ipv6AddressHash>::type; 83 84 /// Alias for Ipv4Header and Ipv6Header classes 85 using IpHeader = typename std::conditional<IsIpv4::value, Ipv4Header, Ipv6Header>::type; 86 87 /// Alias for Ipv4InterfaceAddress and Ipv6InterfaceAddress classes 88 using IpInterfaceAddress = typename std::conditional<IsIpv4::value, Ipv4InterfaceAddress, Ipv6InterfaceAddress>::type; 89 90 /// Alias for Ipv4Interface and Ipv6Interface classes 91 using IpInterface = typename std::conditional<IsIpv4::value, Ipv4Interface, Ipv6Interface>::type; 92 93 /// Alias for Ipv4L3Protocol and Ipv4L3Protocol classes 94 using IpL3Protocol = typename std::conditional<IsIpv4::value, Ipv4L3Protocol, Ipv6L3Protocol>::type; 95 96 public: 97 NixVectorRouting (); 98 ~NixVectorRouting (); 99 /** 100 * @brief The Interface ID of the Global Router interface. 101 * @return The Interface ID 102 * @see Object::GetObject () 103 */ 104 static TypeId GetTypeId (void); 105 /** 106 * @brief Set the Node pointer of the node for which this 107 * routing protocol is to be placed 108 * 109 * @param node Node pointer 110 */ 111 void SetNode (Ptr<Node> node); 112 113 /** 114 * @brief Called when run-time link topology change occurs 115 * which iterates through the node list and flushes any 116 * nix vector caches 117 * 118 * \internal 119 * \c const is used here due to need to potentially flush the cache 120 * in const methods such as PrintRoutingTable. Caches are stored in 121 * mutable variables and flushed in const methods. 122 */ 123 void FlushGlobalNixRoutingCache (void) const; 124 125 /** 126 * @brief Print the Routing Path according to Nix Routing 127 * \param source Source node 128 * \param dest Destination node address 129 * \param stream The ostream the Routing path is printed to 130 * \param unit the time unit to be used in the report 131 * 132 * \note IpAddress is alias for either Ipv4Address or Ipv6Address 133 * depending on on whether the network is IPv4 or IPv6 respectively. 134 */ 135 void PrintRoutingPath (Ptr<Node> source, IpAddress dest, Ptr<OutputStreamWrapper> stream, Time::Unit unit) const; 136 137 138 private: 139 140 /** 141 * Flushes the cache which stores nix-vector based on 142 * destination IP 143 */ 144 void FlushNixCache (void) const; 145 146 /** 147 * Flushes the cache which stores the Ip route 148 * based on the destination IP 149 */ 150 void FlushIpRouteCache (void) const; 151 152 /** 153 * Upon a run-time topology change caches are 154 * flushed and the total number of neighbors is 155 * reset to zero 156 */ 157 void ResetTotalNeighbors (void); 158 159 /** 160 * Takes in the source node and dest IP and calls GetNodeByIp, 161 * BFS, accounting for any output interface specified, and finally 162 * BuildNixVector to return the built nix-vector 163 * 164 * \param source Source node 165 * \param dest Destination node address 166 * \param oif Preferred output interface 167 * \returns The NixVector to be used in routing. 168 */ 169 Ptr<NixVector> GetNixVector (Ptr<Node> source, IpAddress dest, Ptr<NetDevice> oif) const; 170 171 /** 172 * Checks the cache based on dest IP for the nix-vector 173 * \param address Address to check 174 * \param foundInCache Address found in cache 175 * \returns The NixVector to be used in routing. 176 */ 177 Ptr<NixVector> GetNixVectorInCache (const IpAddress &address, bool &foundInCache) const; 178 179 /** 180 * Checks the cache based on dest IP for the IpRoute 181 * \param address Address to check 182 * \returns The cached route. 183 */ 184 Ptr<IpRoute> GetIpRouteInCache (IpAddress address); 185 186 /** 187 * Given a net-device returns all the adjacent net-devices, 188 * essentially getting the neighbors on that channel 189 * \param [in] netDevice the NetDevice attached to the channel. 190 * \param [in] channel the channel to check 191 * \param [out] netDeviceContainer the NetDeviceContainer of the NetDevices in the channel. 192 */ 193 void GetAdjacentNetDevices (Ptr<NetDevice> netDevice, Ptr<Channel> channel, NetDeviceContainer & netDeviceContainer) const; 194 195 /** 196 * Iterates through the node list and finds the one 197 * corresponding to the given IpAddress 198 * \param dest destination node IP 199 * \return The node with the specified IP. 200 */ 201 Ptr<Node> GetNodeByIp (IpAddress dest) const; 202 203 /** 204 * Iterates through the node list and finds the one 205 * corresponding to the given IpAddress 206 * \param netDevice NetDevice pointer 207 * \return The node with the specified IP. 208 */ 209 Ptr<IpInterface> GetInterfaceByNetDevice (Ptr<NetDevice> netDevice) const; 210 211 /** 212 * Recurses the T vector, created by BFS and actually builds the nixvector 213 * \param [in] parentVector Parent vector for retracing routes 214 * \param [in] source Source Node index 215 * \param [in] dest Destination Node index 216 * \param [out] nixVector the NixVector to be used for routing 217 * \returns true on success, false otherwise. 218 */ 219 bool BuildNixVector (const std::vector< Ptr<Node> > & parentVector, uint32_t source, uint32_t dest, Ptr<NixVector> nixVector) const; 220 221 /** 222 * Special variation of BuildNixVector for when a node is sending to itself 223 * \param [out] nixVector the NixVector to be used for routing 224 * \returns true on success, false otherwise. 225 */ 226 bool BuildNixVectorLocal (Ptr<NixVector> nixVector); 227 228 /** 229 * Simply iterates through the nodes net-devices and determines 230 * how many neighbors the node has. 231 * \param [in] node node pointer 232 * \returns the number of neighbors of m_node. 233 */ 234 uint32_t FindTotalNeighbors (Ptr<Node> node) const; 235 236 237 /** 238 * Determine if the NetDevice is bridged 239 * \param nd the NetDevice to check 240 * \returns the bridging NetDevice (or null if the NetDevice is not bridged) 241 */ 242 Ptr<BridgeNetDevice> NetDeviceIsBridged (Ptr<NetDevice> nd) const; 243 244 245 /** 246 * Nix index is with respect to the neighbors. The net-device index must be 247 * derived from this 248 * \param [in] node the current node under consideration 249 * \param [in] nodeIndex Nix Node index 250 * \param [out] gatewayIp IP address of the gateway 251 * \returns the index of the NetDevice in the node. 252 */ 253 uint32_t FindNetDeviceForNixIndex (Ptr<Node> node, uint32_t nodeIndex, IpAddress & gatewayIp) const; 254 255 /** 256 * \brief Breadth first search algorithm. 257 * \param [in] numberOfNodes total number of nodes 258 * \param [in] source Source Node 259 * \param [in] dest Destination Node 260 * \param [out] parentVector Parent vector for retracing routes 261 * \param [in] oif specific output interface to use from source node, if not null 262 * \returns false if dest not found, true o.w. 263 */ 264 bool BFS (uint32_t numberOfNodes, 265 Ptr<Node> source, 266 Ptr<Node> dest, 267 std::vector< Ptr<Node> > & parentVector, 268 Ptr<NetDevice> oif) const; 269 270 /** 271 * \sa Ipv4RoutingProtocol::DoInitialize 272 * \sa Ipv6RoutingProtocol::DoInitialize 273 */ 274 void DoInitialize (); 275 276 /** 277 * \sa Ipv4RoutingProtocol::DoDispose 278 * \sa Ipv6RoutingProtocol::DoDispose 279 */ 280 void DoDispose (void); 281 282 /// Map of IpAddress to NixVector 283 typedef std::map<IpAddress, Ptr<NixVector> > NixMap_t; 284 /// Map of IpAddress to IpRoute 285 typedef std::map<IpAddress, Ptr<IpRoute> > IpRouteMap_t; 286 287 /// Callback for IPv4 unicast packets to be forwarded 288 typedef Callback<void, Ptr<IpRoute>, Ptr<const Packet>, const IpHeader &> UnicastForwardCallbackv4; 289 290 /// Callback for IPv6 unicast packets to be forwarded 291 typedef Callback<void, Ptr<const NetDevice>, Ptr<IpRoute>, Ptr<const Packet>, const IpHeader &> UnicastForwardCallbackv6; 292 293 /// Callback for unicast packets to be forwarded 294 typedef typename std::conditional<IsIpv4::value, UnicastForwardCallbackv4, UnicastForwardCallbackv6>::type UnicastForwardCallback; 295 296 /// Callback for IPv4 multicast packets to be forwarded 297 typedef Callback<void, Ptr<Ipv4MulticastRoute>, Ptr<const Packet>, const IpHeader &> MulticastForwardCallbackv4; 298 299 /// Callback for IPv6 multicast packets to be forwarded 300 typedef Callback<void, Ptr<const NetDevice>, Ptr<Ipv6MulticastRoute>, Ptr<const Packet>, const IpHeader &> MulticastForwardCallbackv6; 301 302 /// Callback for multicast packets to be forwarded 303 typedef typename std::conditional<IsIpv4::value, MulticastForwardCallbackv4, MulticastForwardCallbackv6>::type MulticastForwardCallback; 304 305 /// Callback for packets to be locally delivered 306 typedef Callback<void, Ptr<const Packet>, const IpHeader &, uint32_t > LocalDeliverCallback; 307 308 /// Callback for routing errors (e.g., no route found) 309 typedef Callback<void, Ptr<const Packet>, const IpHeader &, Socket::SocketErrno > ErrorCallback; 310 311 /* From Ipv4RoutingProtocol and Ipv6RoutingProtocol */ 312 /** 313 * \brief Query routing cache for an existing route, for an outbound packet 314 * \param p packet to be routed. Note that this method may modify the packet. 315 * Callers may also pass in a null pointer. 316 * \param header input parameter (used to form key to search for the route) 317 * \param oif Output interface Netdevice. May be zero, or may be bound via 318 * socket options to a particular output interface. 319 * \param sockerr Output parameter; socket errno 320 * 321 * \returns a code that indicates what happened in the lookup 322 * 323 * \sa Ipv4RoutingProtocol::RouteOutput 324 * \sa Ipv6RoutingProtocol::RouteOutput 325 */ 326 virtual Ptr<IpRoute> RouteOutput (Ptr<Packet> p, const IpHeader &header, Ptr<NetDevice> oif, Socket::SocketErrno &sockerr); 327 328 /** 329 * \brief Route an input packet (to be forwarded or locally delivered) 330 * \param p received packet 331 * \param header input parameter used to form a search key for a route 332 * \param idev Pointer to ingress network device 333 * \param ucb Callback for the case in which the packet is to be forwarded 334 * as unicast 335 * \param mcb Callback for the case in which the packet is to be forwarded 336 * as multicast 337 * \param lcb Callback for the case in which the packet is to be locally 338 * delivered 339 * \param ecb Callback to call if there is an error in forwarding 340 * 341 * \returns true if NixVectorRouting class takes responsibility for 342 * forwarding or delivering the packet, false otherwise 343 * 344 * \sa Ipv4RoutingProtocol::RouteInput 345 * \sa Ipv6RoutingProtocol::RouteInput 346 */ 347 virtual bool RouteInput (Ptr<const Packet> p, const IpHeader &header, Ptr<const NetDevice> idev, 348 UnicastForwardCallback ucb, MulticastForwardCallback mcb, 349 LocalDeliverCallback lcb, ErrorCallback ecb); 350 351 /** 352 * \param interface the index of the interface we are being notified about 353 * 354 * \sa Ipv4RoutingProtocol::NotifyInterfaceUp 355 * \sa Ipv6RoutingProtocol::NotifyInterfaceUp 356 */ 357 virtual void NotifyInterfaceUp (uint32_t interface); 358 359 /** 360 * \param interface the index of the interface we are being notified about 361 * 362 * \sa Ipv4RoutingProtocol::NotifyInterfaceDown 363 * \sa Ipv6RoutingProtocol::NotifyInterfaceDown 364 */ 365 virtual void NotifyInterfaceDown (uint32_t interface); 366 367 /** 368 * \param interface the index of the interface we are being notified about 369 * \param address a new address being added to an interface 370 * 371 * \sa Ipv4RoutingProtocol::NotifyAddAddress 372 * \sa Ipv6RoutingProtocol::NotifyAddAddress 373 */ 374 virtual void NotifyAddAddress (uint32_t interface, IpInterfaceAddress address); 375 376 /** 377 * \param interface the index of the interface we are being notified about 378 * \param address a new address being added to an interface 379 * 380 * \sa Ipv4RoutingProtocol::NotifyRemoveAddress 381 * \sa Ipv6RoutingProtocol::NotifyRemoveAddress 382 */ 383 virtual void NotifyRemoveAddress (uint32_t interface, IpInterfaceAddress address); 384 385 /** 386 * \brief Print the Routing Table entries 387 * 388 * \param stream The ostream the Routing table is printed to 389 * \param unit The time unit to be used in the report 390 * 391 * \sa Ipv4RoutingProtocol::PrintRoutingTable 392 * \sa Ipv6RoutingProtocol::PrintRoutingTable 393 */ 394 virtual void PrintRoutingTable (Ptr<OutputStreamWrapper> stream, Time::Unit unit = Time::S) const; 395 396 /* From IPv4RoutingProtocol */ 397 /** 398 * \brief Typically, invoked directly or indirectly from ns3::Ipv4::SetRoutingProtocol 399 * 400 * \param ipv4 the ipv4 object this routing protocol is being associated with 401 * 402 * \sa Ipv4RoutingProtocol::SetIpv4 403 */ 404 virtual void SetIpv4 (Ptr<Ip> ipv4); 405 406 /* From IPv6RoutingProtocol */ 407 /** 408 * \brief Typically, invoked directly or indirectly from ns3::Ipv6::SetRoutingProtocol 409 * 410 * \param ipv6 the ipv6 object this routing protocol is being associated with 411 * 412 * \sa Ipv6RoutingProtocol::SetIpv6 413 */ 414 virtual void SetIpv6 (Ptr<Ip> ipv6); 415 416 /** 417 * \brief Notify a new route. 418 * 419 * \param dst destination address 420 * \param mask destination mask 421 * \param nextHop nextHop for this destination 422 * \param interface output interface 423 * \param prefixToUse prefix to use as source with this route 424 * 425 * \sa Ipv6RoutingProtocol::NotifyAddRoute 426 */ 427 virtual void NotifyAddRoute (IpAddress dst, Ipv6Prefix mask, IpAddress nextHop, uint32_t interface, IpAddress prefixToUse = IpAddress::GetZero ()); 428 429 /** 430 * \brief Notify route removing. 431 * 432 * \param dst destination address 433 * \param mask destination mask 434 * \param nextHop nextHop for this destination 435 * \param interface output interface 436 * \param prefixToUse prefix to use as source with this route 437 * 438 * \sa Ipv6RoutingProtocol::NotifyRemoveRoute 439 */ 440 virtual void NotifyRemoveRoute (IpAddress dst, Ipv6Prefix mask, IpAddress nextHop, uint32_t interface, IpAddress prefixToUse = IpAddress::GetZero ()); 441 442 /** 443 * Flushes routing caches if required. 444 */ 445 void CheckCacheStateAndFlush (void) const; 446 447 /** 448 * Build map from IP Address to Node for faster lookup. 449 */ 450 void BuildIpAddressToNodeMap (void) const; 451 452 /** 453 * Flag to mark when caches are dirty and need to be flushed. 454 * Used for lazy cleanup of caches when there are many topology changes. 455 */ 456 static bool g_isCacheDirty; 457 458 /** Cache stores nix-vectors based on destination ip */ 459 mutable NixMap_t m_nixCache; 460 461 /** Cache stores IpRoutes based on destination ip */ 462 mutable IpRouteMap_t m_ipRouteCache; 463 464 Ptr<Ip> m_ip; //!< IP object 465 Ptr<Node> m_node; //!< Node object 466 467 /** Total neighbors used for nix-vector to determine number of bits */ 468 uint32_t m_totalNeighbors; 469 470 471 /** 472 * Mapping of IP address to ns-3 node. 473 * 474 * Used to avoid linear searching of nodes/devices to find a node in 475 * GetNodeByIp() method. NIX vector routing assumes IP addresses 476 * are unique so mapping can be done without duplication. 477 **/ 478 typedef std::unordered_map<IpAddress, ns3::Ptr<ns3::Node>, IpAddressHash > IpAddressToNodeMap; 479 static IpAddressToNodeMap g_ipAddressToNodeMap; //!< Address to node map. 480 481 /// Mapping of Ptr<NetDevice> to Ptr<IpInterface>. 482 typedef std::unordered_map<Ptr<NetDevice>, Ptr<IpInterface>> NetDeviceToIpInterfaceMap; 483 static NetDeviceToIpInterfaceMap g_netdeviceToIpInterfaceMap; //!< NetDevice pointer to IpInterface pointer map 484 }; 485 486 487 /** 488 * \ingroup nix-vector-routing 489 * Create the typedef Ipv4NixVectorRouting with T as Ipv4RoutingProtocol 490 * 491 * Note: This typedef enables also backwards compatibility with original Ipv4NixVectorRouting. 492 */ 493 typedef NixVectorRouting<Ipv4RoutingProtocol> Ipv4NixVectorRouting; 494 495 /** 496 * \ingroup nix-vector-routing 497 * Create the typedef Ipv6NixVectorRouting with T as Ipv6RoutingProtocol 498 */ 499 typedef NixVectorRouting<Ipv6RoutingProtocol> Ipv6NixVectorRouting; 500 } // namespace ns3 501 502 #endif /* NIX_VECTOR_ROUTING_H */ 503