25 #include "ns3/abort.h"
26 #include "ns3/names.h"
27 #include "ns3/ipv4-list-routing.h"
29 #include "ipv4-nix-vector-routing.h"
35 NS_OBJECT_ENSURE_REGISTERED (Ipv4NixVectorRouting);
42 .AddConstructor<Ipv4NixVectorRouting> ()
47 Ipv4NixVectorRouting::Ipv4NixVectorRouting ()
48 : m_totalNeighbors (0)
53 Ipv4NixVectorRouting::~Ipv4NixVectorRouting ()
102 rp->FlushNixCache ();
103 rp->FlushIpv4RouteCache ();
108 Ipv4NixVectorRouting::FlushNixCache ()
115 Ipv4NixVectorRouting::FlushIpv4RouteCache ()
118 m_ipv4RouteCache.clear ();
122 Ipv4NixVectorRouting::GetNixVector (Ptr<Node> source, Ipv4Address dest, Ptr<NetDevice> oif)
126 Ptr<NixVector> nixVector = Create<NixVector> ();
131 Ptr<Node> destNode = GetNodeByIp (dest);
140 if (source == destNode)
149 std::vector< Ptr<Node> > parentVector;
153 if (BuildNixVector (parentVector, source->GetId (), destNode->GetId (), nixVector))
166 Ipv4NixVectorRouting::GetNixVectorInCache (Ipv4Address address)
170 NixMap_t::iterator iter = m_nixCache.find (address);
171 if (iter != m_nixCache.end ())
182 Ipv4NixVectorRouting::GetIpv4RouteInCache (Ipv4Address address)
186 Ipv4RouteMap_t::iterator iter = m_ipv4RouteCache.find (address);
187 if (iter != m_ipv4RouteCache.end ())
198 Ipv4NixVectorRouting::BuildNixVectorLocal (Ptr<NixVector> nixVector)
207 Ipv4Address loopback (
"127.0.0.1");
208 for (uint32_t i = 0; i < numberOfDevices; i++)
210 uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->
GetDevice (i));
211 Ipv4InterfaceAddress ifAddr = m_ipv4->GetAddress (interfaceIndex, 0);
212 if (ifAddr.GetLocal () == loopback)
215 NS_LOG_LOGIC (
"Adding Nix: " << i <<
" with " << nixVector->BitCount (numberOfDevices)
216 <<
" bits, for node " << m_node->
GetId ());
217 nixVector->AddNeighborIndex (i, nixVector->BitCount (numberOfDevices));
225 Ipv4NixVectorRouting::BuildNixVector (
const std::vector< Ptr<Node> > & parentVector, uint32_t source, uint32_t dest, Ptr<NixVector> nixVector)
234 if (parentVector.at (dest) == 0)
239 Ptr<Node> parentNode = parentVector.at (dest);
241 uint32_t numberOfDevices = parentNode->GetNDevices ();
243 uint32_t totalNeighbors = 0;
247 for (uint32_t i = 0; i < numberOfDevices; i++)
252 Ptr<NetDevice> localNetDevice = parentNode->GetDevice (i);
253 if (localNetDevice->IsBridge ())
257 Ptr<Channel> channel = localNetDevice->GetChannel ();
265 NetDeviceContainer netDeviceContainer;
266 GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
274 for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
276 Ptr<Node> remoteNode = (*iter)->GetNode ();
278 if (remoteNode->GetId () == dest)
280 destId = totalNeighbors + offset;
285 totalNeighbors += netDeviceContainer.GetN ();
288 << nixVector->BitCount (totalNeighbors) <<
" bits, for node " << parentNode->GetId ());
289 nixVector->AddNeighborIndex (destId, nixVector->BitCount (totalNeighbors));
293 BuildNixVector (parentVector, source, (parentVector.at (dest))->GetId (), nixVector);
298 Ipv4NixVectorRouting::GetAdjacentNetDevices (Ptr<NetDevice> netDevice, Ptr<Channel> channel, NetDeviceContainer & netDeviceContainer)
302 for (uint32_t i = 0; i < channel->GetNDevices (); i++)
304 Ptr<NetDevice> remoteDevice = channel->GetDevice (i);
305 if (remoteDevice != netDevice)
307 Ptr<BridgeNetDevice> bd = NetDeviceIsBridged (remoteDevice);
312 NS_LOG_LOGIC (
"Looking through bridge ports of bridge net device " << bd);
313 for (uint32_t j = 0; j < bd->GetNBridgePorts (); ++j)
315 Ptr<NetDevice> ndBridged = bd->GetBridgePort (j);
316 if (ndBridged == remoteDevice)
318 NS_LOG_LOGIC (
"That bridge port is me, don't walk backward");
321 Ptr<Channel> chBridged = ndBridged->GetChannel ();
326 GetAdjacentNetDevices (ndBridged, chBridged, netDeviceContainer);
331 netDeviceContainer.Add (channel->GetDevice (i));
338 Ipv4NixVectorRouting::GetNodeByIp (Ipv4Address dest)
345 for (NodeContainer::Iterator i = allNodes.Begin (); i != allNodes.End (); ++i)
348 Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
349 if (ipv4->GetInterfaceForAddress (dest) != -1)
358 NS_LOG_ERROR (
"Couldn't find dest node given the IP" << dest);
366 Ipv4NixVectorRouting::FindTotalNeighbors ()
369 uint32_t totalNeighbors = 0;
373 for (uint32_t i = 0; i < numberOfDevices; i++)
378 Ptr<NetDevice> localNetDevice = m_node->
GetDevice (i);
379 Ptr<Channel> channel = localNetDevice->GetChannel ();
387 NetDeviceContainer netDeviceContainer;
388 GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
390 totalNeighbors += netDeviceContainer.GetN ();
393 return totalNeighbors;
397 Ipv4NixVectorRouting::NetDeviceIsBridged (Ptr<NetDevice> nd)
const
401 Ptr<Node> node = nd->GetNode ();
402 uint32_t nDevices = node->GetNDevices ();
410 for (uint32_t i = 0; i < nDevices; ++i)
412 Ptr<NetDevice> ndTest = node->GetDevice (i);
415 if (ndTest->IsBridge ())
417 NS_LOG_LOGIC (
"device " << i <<
" is a bridge net device");
418 Ptr<BridgeNetDevice> bnd = ndTest->GetObject<BridgeNetDevice> ();
419 NS_ABORT_MSG_UNLESS (bnd,
"Ipv4NixVectorRouting::NetDeviceIsBridged (): GetObject for <BridgeNetDevice> failed");
421 for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
423 NS_LOG_LOGIC (
"Examine bridge port " << j <<
" " << bnd->GetBridgePort (j));
424 if (bnd->GetBridgePort (j) == nd)
426 NS_LOG_LOGIC (
"Net device " << nd <<
" is bridged by " << bnd);
432 NS_LOG_LOGIC (
"Net device " << nd <<
" is not bridged");
437 Ipv4NixVectorRouting::FindNetDeviceForNixIndex (uint32_t nodeIndex, Ipv4Address & gatewayIp)
441 uint32_t totalNeighbors = 0;
445 for (uint32_t i = 0; i < numberOfDevices; i++)
450 Ptr<NetDevice> localNetDevice = m_node->
GetDevice (i);
451 Ptr<Channel> channel = localNetDevice->GetChannel ();
459 NetDeviceContainer netDeviceContainer;
460 GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
463 if (nodeIndex < (totalNeighbors + netDeviceContainer.GetN ()))
467 Ptr<NetDevice> gatewayDevice = netDeviceContainer.Get (nodeIndex-totalNeighbors);
468 Ptr<Node> gatewayNode = gatewayDevice->GetNode ();
469 Ptr<Ipv4> ipv4 = gatewayNode->GetObject<Ipv4> ();
471 uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (gatewayDevice);
472 Ipv4InterfaceAddress ifAddr = ipv4->GetAddress (interfaceIndex, 0);
473 gatewayIp = ifAddr.GetLocal ();
476 totalNeighbors += netDeviceContainer.GetN ();
492 nixVectorInCache = GetNixVectorInCache (header.
GetDestination ());
495 if (!nixVectorInCache)
500 nixVectorInCache = GetNixVector (m_node, header.
GetDestination (), oif);
503 m_nixCache.insert (NixMap_t::value_type (header.
GetDestination (), nixVectorInCache));
507 if (nixVectorInCache)
509 NS_LOG_LOGIC (
"Nix-vector contents: " << *nixVectorInCache);
513 nixVectorForPacket = Create<NixVector> ();
514 nixVectorForPacket = nixVectorInCache->
Copy ();
518 if (m_totalNeighbors == 0)
520 m_totalNeighbors = FindTotalNeighbors ();
525 uint32_t numberOfBits = nixVectorForPacket->BitCount (m_totalNeighbors);
526 uint32_t nodeIndex = nixVectorForPacket->ExtractNeighborIndex (numberOfBits);
546 uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
547 int32_t interfaceIndex = 0;
551 interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->
GetDevice (index));
555 interfaceIndex = (m_ipv4)->GetInterfaceForDevice (oif);
558 NS_ASSERT_MSG (interfaceIndex != -1,
"Interface index not found for device");
563 rtentry = Create<Ipv4Route> ();
578 sockerr = Socket::ERROR_NOTERROR;
581 m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.
GetDestination (), rtentry));
584 NS_LOG_LOGIC (
"Nix-vector contents: " << *nixVectorInCache <<
" : Remaining bits: " << nixVectorForPacket->GetRemainingBits ());
590 NS_LOG_LOGIC (
"Adding Nix-vector to packet: " << *nixVectorForPacket);
591 p->SetNixVector (nixVectorForPacket);
597 sockerr = Socket::ERROR_NOROUTETOHOST;
620 if (m_totalNeighbors == 0)
622 m_totalNeighbors = FindTotalNeighbors ();
624 uint32_t numberOfBits = nixVector->
BitCount (m_totalNeighbors);
633 uint32_t index = FindNetDeviceForNixIndex (nodeIndex, gatewayIp);
634 uint32_t interfaceIndex = (m_ipv4)->GetInterfaceForDevice (m_node->
GetDevice (index));
638 rtentry = Create<Ipv4Route> ();
646 m_ipv4RouteCache.insert (Ipv4RouteMap_t::value_type (header.
GetDestination (), rtentry));
649 NS_LOG_LOGIC (
"At Node " << m_node->
GetId () <<
", Extracting " << numberOfBits <<
650 " bits from Nix-vector: " << nixVector <<
" : " << *nixVector);
656 ucb (rtentry, p, header);
666 *os <<
"NixCache:" << std::endl;
667 if (m_nixCache.size () > 0)
669 *os <<
"Destination NixVector" << std::endl;
670 for (NixMap_t::const_iterator it = m_nixCache.begin (); it != m_nixCache.end (); it++)
672 std::ostringstream dest;
674 *os << std::setiosflags (std::ios::left) << std::setw (16) << dest.str ();
675 *os << *(it->second) << std::endl;
678 *os <<
"Ipv4RouteCache:" << std::endl;
679 if (m_ipv4RouteCache.size () > 0)
681 *os <<
"Destination Gateway Source OutputDevice" << std::endl;
682 for (Ipv4RouteMap_t::const_iterator it = m_ipv4RouteCache.begin (); it != m_ipv4RouteCache.end (); it++)
684 std::ostringstream dest, gw, src;
685 dest << it->second->GetDestination ();
686 *os << std::setiosflags (std::ios::left) << std::setw (16) << dest.str ();
687 gw << it->second->GetGateway ();
688 *os << std::setiosflags (std::ios::left) << std::setw (16) << gw.str ();
689 src << it->second->GetSource ();
690 *os << std::setiosflags (std::ios::left) << std::setw (16) << src.str ();
698 *os << it->second->GetOutputDevice ()->GetIfIndex ();
728 Ipv4NixVectorRouting::BFS (uint32_t numberOfNodes,
Ptr<Node> source,
735 std::queue< Ptr<Node> > greyNodeList;
738 parentVector.clear ();
739 parentVector.reserve (
sizeof (
Ptr<Node>)*numberOfNodes);
740 parentVector.insert (parentVector.begin (),
sizeof (
Ptr<Node>)*numberOfNodes, 0);
743 greyNodeList.push (source);
744 parentVector.at (source->
GetId ()) = source;
747 while (greyNodeList.size () != 0)
749 Ptr<Node> currNode = greyNodeList.front ();
752 if (currNode == dest)
761 if (currNode == source && oif)
766 uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (oif);
767 if (!(ipv4->IsUp (interfaceIndex)))
773 if (!(oif->IsLinkUp ()))
778 Ptr<Channel> channel = oif->GetChannel ();
786 NetDeviceContainer netDeviceContainer;
787 GetAdjacentNetDevices (oif, channel, netDeviceContainer);
793 for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
795 Ptr<Node> remoteNode = (*iter)->GetNode ();
801 if (parentVector.at (remoteNode->GetId ()) == 0)
803 parentVector.at (remoteNode->GetId ()) = currNode;
804 greyNodeList.push (remoteNode);
812 for (uint32_t i = 0; i < (currNode->
GetNDevices ()); i++)
817 Ptr<NetDevice> localNetDevice = currNode->
GetDevice (i);
822 uint32_t interfaceIndex = (ipv4)->GetInterfaceForDevice (currNode->
GetDevice (i));
823 if (!(ipv4->IsUp (interfaceIndex)))
829 if (!(localNetDevice->IsLinkUp ()))
834 Ptr<Channel> channel = localNetDevice->GetChannel ();
842 NetDeviceContainer netDeviceContainer;
843 GetAdjacentNetDevices (localNetDevice, channel, netDeviceContainer);
849 for (NetDeviceContainer::Iterator iter = netDeviceContainer.Begin (); iter != netDeviceContainer.End (); iter++)
851 Ptr<Node> remoteNode = (*iter)->GetNode ();
857 if (parentVector.at (remoteNode->GetId ()) == 0)
859 parentVector.at (remoteNode->GetId ()) = currNode;
860 greyNodeList.push (remoteNode);
smart pointer class similar to boost::intrusive_ptr
#define NS_LOG_FUNCTION(parameters)
static uint32_t GetNNodes(void)
Ptr< NixVector > Copy(void) const
#define NS_ASSERT(condition)
#define NS_LOG_COMPONENT_DEFINE(name)
virtual void DoDispose(void)
#define NS_LOG_FUNCTION_NOARGS()
#define NS_ABORT_MSG_UNLESS(cond, msg)
Abnormal program termination if cond is false.
void SetSource(Ipv4Address src)
Ptr< NetDevice > GetOutputDevice(void) const
uint32_t ExtractNeighborIndex(uint32_t numberOfBits)
void SetNode(Ptr< Node > node)
Set the Node pointer of the node for which this routing protocol is to be placed. ...
void FlushGlobalNixRoutingCache(void)
Called when run-time link topology change occurs which iterates through the node list and flushes any...
void SetGateway(Ipv4Address gw)
static Iterator End(void)
Ptr< NetDevice > GetDevice(uint32_t index) const
static TypeId GetTypeId(void)
The Interface ID of the Global Router interface.
#define NS_LOG_LOGIC(msg)
virtual void NotifyInterfaceDown(uint32_t interface)
Access to the Ipv4 forwarding table, interfaces, and configuration.
uint32_t GetNDevices(void) const
virtual void NotifyInterfaceUp(uint32_t interface)
void SetOutputDevice(Ptr< NetDevice > outputDevice)
virtual void NotifyRemoveAddress(uint32_t interface, Ipv4InterfaceAddress address)
#define NS_ASSERT_MSG(condition, message)
static NodeContainer GetGlobal(void)
Create a NodeContainer that contains a list of all nodes created through NodeContainer::Create() and ...
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.
virtual void SetIpv4(Ptr< Ipv4 > ipv4)
Ipv4 addresses are stored in host order in this class.
uint32_t GetId(void) const
a class to store IPv4 address information on an interface
static Iterator Begin(void)
#define NS_LOG_DEBUG(msg)
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 std::string FindName(Ptr< Object > object)
Abstract base class for IPv4 routing protocols.
#define NS_LOG_ERROR(msg)
virtual void NotifyAddAddress(uint32_t interface, Ipv4InterfaceAddress address)
Ptr< T > GetObject(void) const
a unique identifier for an interface.
TypeId SetParent(TypeId tid)
virtual void PrintRoutingTable(Ptr< OutputStreamWrapper > stream) const
Print the Routing Table entries.
uint32_t BitCount(uint32_t numberOfNeighbors) const
std::ostream * GetStream(void)
void SetDestination(Ipv4Address dest)