25 #include "ns3/abort.h" 26 #include "ns3/names.h" 27 #include "ns3/ipv4-list-routing.h" 42 static TypeId tid = TypeId (
"ns3::Ipv4NixVectorRouting")
44 .SetGroupName (
"NixVectorRouting")
51 : m_totalNeighbors (0)
105 rp->FlushNixCache ();
106 rp->FlushIpv4RouteCache ();
129 Ptr<NixVector> nixVector = Create<NixVector> ();
144 if (source == destNode)
153 std::vector< Ptr<Node> > parentVector;
157 if (
BuildNixVector (parentVector, source->GetId (), destNode->GetId (), nixVector))
215 Ipv4Address loopback (
"127.0.0.1");
216 for (uint32_t i = 0; i < numberOfDevices; i++)
219 Ipv4InterfaceAddress ifAddr =
m_ipv4->GetAddress (interfaceIndex, 0);
220 if (ifAddr.GetLocal () == loopback)
223 NS_LOG_LOGIC (
"Adding Nix: " << i <<
" with " << nixVector->BitCount (numberOfDevices)
225 nixVector->AddNeighborIndex (i, nixVector->BitCount (numberOfDevices));
242 if (parentVector.at (dest) == 0)
247 Ptr<Node> parentNode = parentVector.at (dest);
249 uint32_t numberOfDevices = parentNode->GetNDevices ();
251 uint32_t totalNeighbors = 0;
255 for (uint32_t i = 0; i < numberOfDevices; i++)
260 Ptr<NetDevice> localNetDevice = parentNode->GetDevice (i);
261 if (localNetDevice->IsBridge ())
265 Ptr<Channel>
channel = localNetDevice->GetChannel ();
273 NetDeviceContainer netDeviceContainer;
284 Ptr<Node> remoteNode = (*iter)->GetNode ();
286 if (remoteNode->GetId () == dest)
288 destId = totalNeighbors + offset;
293 totalNeighbors += netDeviceContainer.GetN ();
296 << nixVector->BitCount (totalNeighbors) <<
" bits, for node " << parentNode->GetId ());
297 nixVector->AddNeighborIndex (destId, nixVector->BitCount (totalNeighbors));
301 BuildNixVector (parentVector, source, (parentVector.at (dest))->GetId (), nixVector);
310 for (std::size_t i = 0; i <
channel->GetNDevices (); i++)
312 Ptr<NetDevice> remoteDevice =
channel->GetDevice (i);
313 if (remoteDevice != netDevice)
320 NS_LOG_LOGIC (
"Looking through bridge ports of bridge net device " << bd);
321 for (uint32_t j = 0; j < bd->GetNBridgePorts (); ++j)
323 Ptr<NetDevice> ndBridged = bd->GetBridgePort (j);
324 if (ndBridged == remoteDevice)
326 NS_LOG_LOGIC (
"That bridge port is me, don't walk backward");
329 Ptr<Channel> chBridged = ndBridged->GetChannel ();
339 netDeviceContainer.Add (
channel->GetDevice (i));
356 Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
357 if (ipv4->GetInterfaceForAddress (dest) != -1)
366 NS_LOG_ERROR (
"Couldn't find dest node given the IP" << dest);
377 uint32_t totalNeighbors = 0;
381 for (uint32_t i = 0; i < numberOfDevices; i++)
387 Ptr<Channel>
channel = localNetDevice->GetChannel ();
395 NetDeviceContainer netDeviceContainer;
398 totalNeighbors += netDeviceContainer.GetN ();
401 return totalNeighbors;
409 Ptr<Node> node = nd->GetNode ();
410 uint32_t nDevices = node->GetNDevices ();
418 for (uint32_t i = 0; i < nDevices; ++i)
420 Ptr<NetDevice> ndTest = node->GetDevice (i);
423 if (ndTest->IsBridge ())
425 NS_LOG_LOGIC (
"device " << i <<
" is a bridge net device");
426 Ptr<BridgeNetDevice> bnd = ndTest->GetObject<BridgeNetDevice> ();
427 NS_ABORT_MSG_UNLESS (bnd,
"Ipv4NixVectorRouting::NetDeviceIsBridged (): GetObject for <BridgeNetDevice> failed");
429 for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
431 NS_LOG_LOGIC (
"Examine bridge port " << j <<
" " << bnd->GetBridgePort (j));
432 if (bnd->GetBridgePort (j) == nd)
434 NS_LOG_LOGIC (
"Net device " << nd <<
" is bridged by " << bnd);
440 NS_LOG_LOGIC (
"Net device " << nd <<
" is not bridged");
449 uint32_t totalNeighbors = 0;
453 for (uint32_t i = 0; i < numberOfDevices; i++)
459 Ptr<Channel>
channel = localNetDevice->GetChannel ();
467 NetDeviceContainer netDeviceContainer;
471 if (nodeIndex < (totalNeighbors + netDeviceContainer.GetN ()))
475 Ptr<NetDevice> gatewayDevice = netDeviceContainer.Get (nodeIndex-totalNeighbors);
476 Ptr<Node> gatewayNode = gatewayDevice->GetNode ();
477 Ptr<Ipv4> ipv4 = gatewayNode->GetObject<Ipv4> ();
479 uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (gatewayDevice);
480 Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, 0);
481 gatewayIp = ifAddr.GetLocal ();
484 totalNeighbors += netDeviceContainer.GetN ();
494 Ptr<Ipv4Route> rtentry;
495 Ptr<NixVector> nixVectorInCache;
496 Ptr<NixVector> nixVectorForPacket;
500 NS_LOG_DEBUG (
"Dest IP from header: " << header.GetDestination ());
505 if (!nixVectorInCache)
513 m_nixCache.insert (NixMap_t::value_type (header.GetDestination (), nixVectorInCache));
517 if (nixVectorInCache)
519 NS_LOG_LOGIC (
"Nix-vector contents: " << *nixVectorInCache);
523 nixVectorForPacket = Create<NixVector> ();
524 nixVectorForPacket = nixVectorInCache->Copy ();
536 uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
542 if (!rtentry || !(rtentry->GetOutputDevice () == oif))
555 Ipv4Address gatewayIp;
557 int32_t interfaceIndex = 0;
565 interfaceIndex = (
m_ipv4)->GetInterfaceForDevice (oif);
568 NS_ASSERT_MSG (interfaceIndex != -1,
"Interface index not found for device");
570 Ipv4InterfaceAddress ifAddr =
m_ipv4->GetAddress (interfaceIndex, 0);
573 rtentry = Create<Ipv4Route> ();
574 rtentry->SetSource (ifAddr.GetLocal ());
576 rtentry->SetGateway (gatewayIp);
577 rtentry->SetDestination (header.GetDestination ());
581 rtentry->SetOutputDevice (
m_ipv4->GetNetDevice (interfaceIndex));
585 rtentry->SetOutputDevice (oif);
591 m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.GetDestination (), rtentry));
594 NS_LOG_LOGIC (
"Nix-vector contents: " << *nixVectorInCache <<
" : Remaining bits: " << nixVectorForPacket->GetRemainingBits ());
600 NS_LOG_LOGIC (
"Adding Nix-vector to packet: " << *nixVectorForPacket);
601 p->SetNixVector (nixVectorForPacket);
606 NS_LOG_ERROR (
"No path to the dest: " << header.GetDestination ());
615 UnicastForwardCallback ucb, MulticastForwardCallback mcb,
616 LocalDeliverCallback lcb, ErrorCallback ecb)
625 uint32_t iif =
m_ipv4->GetInterfaceForDevice (idev);
628 if (
m_ipv4->IsDestinationAddress (header.GetDestination (), iif))
632 NS_LOG_LOGIC (
"Local delivery to " << header.GetDestination ());
633 lcb (p, header, iif);
647 Ptr<Ipv4Route> rtentry;
650 Ptr<NixVector> nixVector = p->GetNixVector ();
662 uint32_t nodeIndex = nixVector->ExtractNeighborIndex (numberOfBits);
669 Ipv4Address gatewayIp;
672 Ipv4InterfaceAddress ifAddr =
m_ipv4->GetAddress (interfaceIndex, 0);
675 rtentry = Create<Ipv4Route> ();
676 rtentry->SetSource (ifAddr.GetLocal ());
678 rtentry->SetGateway (gatewayIp);
679 rtentry->SetDestination (header.GetDestination ());
680 rtentry->SetOutputDevice (
m_ipv4->GetNetDevice (interfaceIndex));
683 m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.GetDestination (), rtentry));
687 " bits from Nix-vector: " << nixVector <<
" : " << *nixVector);
693 ucb (rtentry, p, header);
704 std::ostream* os = stream->GetStream ();
706 *os <<
"Node: " <<
m_ipv4->GetObject<Node> ()->GetId ()
707 <<
", Time: " <<
Now().
As (unit)
708 <<
", Local time: " << GetObject<Node> ()->GetLocalTime ().As (unit)
709 <<
", Nix Routing" << std::endl;
711 *os <<
"NixCache:" << std::endl;
714 *os <<
"Destination NixVector" << std::endl;
717 std::ostringstream dest;
719 *os << std::setiosflags (std::ios::left) << std::setw (16) << dest.str ();
720 *os << *(it->second) << std::endl;
723 *os <<
"Ipv4RouteCache:" << std::endl;
726 *os <<
"Destination Gateway Source OutputDevice" << std::endl;
729 std::ostringstream dest, gw, src;
730 dest << it->second->GetDestination ();
731 *os << std::setiosflags (std::ios::left) << std::setw (16) << dest.str ();
732 gw << it->second->GetGateway ();
733 *os << std::setiosflags (std::ios::left) << std::setw (16) << gw.str ();
734 src << it->second->GetSource ();
735 *os << std::setiosflags (std::ios::left) << std::setw (16) << src.str ();
743 *os << it->second->GetOutputDevice ()->GetIfIndex ();
775 Ptr<Node> dest, std::vector< Ptr<Node> > & parentVector,
780 NS_LOG_LOGIC (
"Going from Node " << source->GetId () <<
" to Node " << dest->GetId ());
781 std::queue< Ptr<Node> > greyNodeList;
784 parentVector.clear ();
785 parentVector.reserve (
sizeof (Ptr<Node>)*numberOfNodes);
786 parentVector.insert (parentVector.begin (),
sizeof (Ptr<Node>)*numberOfNodes, 0);
789 greyNodeList.push (source);
790 parentVector.at (source->GetId ()) = source;
793 while (greyNodeList.size () != 0)
795 Ptr<Node> currNode = greyNodeList.front ();
796 Ptr<Ipv4> ipv4 = currNode->GetObject<Ipv4> ();
798 if (currNode == dest)
800 NS_LOG_LOGIC (
"Made it to Node " << currNode->GetId ());
807 if (currNode == source && oif)
812 uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (oif);
813 if (!(ipv4->IsUp (interfaceIndex)))
819 if (!(oif->IsLinkUp ()))
824 Ptr<Channel>
channel = oif->GetChannel ();
832 NetDeviceContainer netDeviceContainer;
841 Ptr<Node> remoteNode = (*iter)->GetNode ();
847 if (parentVector.at (remoteNode->GetId ()) == 0)
849 parentVector.at (remoteNode->GetId ()) = currNode;
850 greyNodeList.push (remoteNode);
858 for (uint32_t i = 0; i < (currNode->GetNDevices ()); i++)
863 Ptr<NetDevice> localNetDevice = currNode->GetDevice (i);
868 uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (currNode->GetDevice (i));
869 if (!(ipv4->IsUp (interfaceIndex)))
875 if (!(localNetDevice->IsLinkUp ()))
880 Ptr<Channel>
channel = localNetDevice->GetChannel ();
888 NetDeviceContainer netDeviceContainer;
897 Ptr<Node> remoteNode = (*iter)->GetNode ();
903 if (parentVector.at (remoteNode->GetId ()) == 0)
905 parentVector.at (remoteNode->GetId ()) = currNode;
906 greyNodeList.push (remoteNode);
void FlushGlobalNixRoutingCache(void) const
Called when run-time link topology change occurs which iterates through the node list and flushes any...
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
TypeId AddConstructor(void)
Record in this TypeId the fact that the default constructor is accessible.
static uint32_t GetNNodes(void)
uint32_t GetId(void) const
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
std::vector< Ptr< Node > >::const_iterator Iterator
Node container iterator.
virtual Ptr< Ipv4Route > RouteOutput(Ptr< Packet > p, const Ipv4Header &header, Ptr< NetDevice > oif, Socket::SocketErrno &sockerr)
Query routing cache for an existing route, for an outbound packet.
NS_ASSERT_MSG(false, "Ipv4AddressGenerator::MaskToIndex(): Impossible")
bool BuildNixVectorLocal(Ptr< NixVector > nixVector)
Special variation of BuildNixVector for when a node is sending to itself.
Ptr< NetDevice > GetDevice(uint32_t index) const
Retrieve the index-th NetDevice associated to this node.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file...
void DoDispose(void)
Destructor implementation.
Ptr< Ipv4 > m_ipv4
IPv4 object.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
void FlushIpv4RouteCache(void) const
Flushes the cache which stores the Ipv4 route based on the destination IP.
Ptr< NixVector > GetNixVector(Ptr< Node > source, Ipv4Address dest, Ptr< NetDevice > oif)
Takes in the source node and dest IP and calls GetNodeByIp, BFS, accounting for any output interface ...
virtual void DoDispose(void)
Destructor implementation.
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
TimeWithUnit As(const enum Unit unit) const
Attach a unit to a Time, to facilitate output in a specific unit.
SocketErrno
Enumeration of the possible errors returned by a socket.
uint32_t FindNetDeviceForNixIndex(uint32_t nodeIndex, Ipv4Address &gatewayIp)
Nix index is with respect to the neighbors.
uint32_t FindTotalNeighbors(void)
Simple iterates through the nodes net-devices and determines how many neighbors it has...
static TypeId GetTypeId(void)
The Interface ID of the Global Router interface.
void FlushNixCache(void) const
Flushes the cache which stores nix-vector based on destination IP.
void GetAdjacentNetDevices(Ptr< NetDevice > netDevice, Ptr< Channel > channel, NetDeviceContainer &netDeviceContainer)
Given a net-device returns all the adjacent net-devices, essentially getting the neighbors on that ch...
virtual void NotifyAddAddress(uint32_t interface, Ipv4InterfaceAddress address)
Ptr< Node > m_node
Node object.
void SetNode(Ptr< Node > node)
Set the Node pointer of the node for which this routing protocol is to be placed. ...
static Iterator End(void)
Unit
The unit to use to interpret a number representing time.
virtual void NotifyRemoveAddress(uint32_t interface, Ipv4InterfaceAddress address)
virtual void NotifyInterfaceUp(uint32_t interface)
Every class exported by the ns3 library is enclosed in the ns3 namespace.
std::vector< Ptr< Node > >::const_iterator Iterator
Node container iterator.
NixMap_t m_nixCache
Cache stores nix-vectors based on destination ip.
virtual bool RouteInput(Ptr< const Packet > p, const Ipv4Header &header, Ptr< const NetDevice > idev, UnicastForwardCallback ucb, MulticastForwardCallback mcb, LocalDeliverCallback lcb, ErrorCallback ecb)
Route an input packet (to be forwarded or locally delivered)
static bool g_isCacheDirty
Flag to mark when caches are dirty and need to be flushed.
Ptr< BridgeNetDevice > NetDeviceIsBridged(Ptr< NetDevice > nd) const
Determine if the NetDevice is bridged.
Ptr< Ipv4Route > GetIpv4RouteInCache(Ipv4Address address)
Checks the cache based on dest IP for the Ipv4Route.
NS_LOG_LOGIC("Net device "<< nd<< " is not bridged")
virtual void PrintRoutingTable(Ptr< OutputStreamWrapper > stream, Time::Unit unit=Time::S) const
Print the Routing Table entries.
bool BuildNixVector(const std::vector< Ptr< Node > > &parentVector, uint32_t source, uint32_t dest, Ptr< NixVector > nixVector)
Recurses the parent vector, created by BFS and actually builds the nixvector.
static NodeContainer GetGlobal(void)
Create a NodeContainer that contains a list of all nodes created through NodeContainer::Create() and ...
uint32_t m_totalNeighbors
Total neighbors used for nix-vector to determine number of bits.
#define NS_ABORT_MSG_UNLESS(cond, msg)
Abnormal program termination if a condition is false, with a message.
static Iterator Begin(void)
Ptr< NixVector > GetNixVectorInCache(Ipv4Address address)
Checks the cache based on dest IP for the nix-vector.
std::vector< Ptr< NetDevice > >::const_iterator Iterator
NetDevice container iterator.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Ipv4RouteMap_t m_ipv4RouteCache
Cache stores Ipv4Routes based on destination ip.
static std::string FindName(Ptr< Object > object)
Given a pointer to an object, look to see if that object has a name associated with it and...
Time Now(void)
create an ns3::Time instance which contains the current simulation time.
#define NS_LOG_ERROR(msg)
Use NS_LOG to output a message of level LOG_ERROR.
Ptr< Node > GetNodeByIp(Ipv4Address dest)
Iterates through the node list and finds the one corresponding to the given Ipv4Address.
void CheckCacheStateAndFlush(void) const
Flushes routing caches if required.
virtual void SetIpv4(Ptr< Ipv4 > ipv4)
TypeId SetParent(TypeId tid)
Set the parent TypeId.
virtual void NotifyInterfaceDown(uint32_t interface)
uint32_t GetNDevices(void) const
bool BFS(uint32_t numberOfNodes, Ptr< Node > source, Ptr< Node > dest, std::vector< Ptr< Node > > &parentVector, Ptr< NetDevice > oif)
Breadth first search algorithm.