To implement the Dijikstra’s link state routing in ns3, we calculate the shortest path among nodes that need to make a custom routing protocol by use of dijikstra’s technique. This is usually describes how the link state routing protocol works in network simulator.
Here is the procedure on how to implement the dijikstra’s link state routing in ns3.
Step-by-Step Implementation
- Set Up ns3 Environment: Make sure ns3 is installed in the computer.
- Include Necessary Libraries: To contain essential ns3 libraries in the script.
- Define Network Topology: For the network topology we need to make nodes and links.
- Install Internet Stack: Download the Internet stack on your nodes.
- Implement Dijkstra’s Link State Routing Protocol: To calculates the shortest path using Dijkstra’s algorithm to make custom routing protocol class.
- Integrate the Custom Routing Protocol: Incorporate your custom routing protocol into the ns3 stack.
- Set Up Applications: To generate traffic and test the routing by downloading the application.
- Run the Simulation: Organise the simulation parameters and run it.
Example Implementation in C++
The given below is the sample on how to simulate the dijikstra’s link state routing protocol in ns3:
- Include Libraries:
#include “ns3/core-module.h”
#include “ns3/network-module.h”
#include “ns3/internet-module.h”
#include “ns3/point-to-point-module.h”
#include “ns3/applications-module.h”
#include “ns3/ipv4-routing-protocol.h”
#include “ns3/ipv4-list-routing-helper.h”
- Define Network Topology:
using namespace ns3;
int main(int argc, char *argv[]) {
CommandLine cmd;
cmd.Parse(argc, argv);
NodeContainer nodes;
nodes.Create(4);
PointToPointHelper pointToPoint;
pointToPoint.SetDeviceAttribute(“DataRate”, StringValue(“5Mbps”));
pointToPoint.SetChannelAttribute(“Delay”, StringValue(“2ms”));
NetDeviceContainer devices01, devices12, devices23, devices30;
devices01 = pointToPoint.Install(nodes.Get(0), nodes.Get(1)));
devices12 = pointToPoint.Install(nodes.Get(1), nodes.Get(2)));
devices23 = pointToPoint.Install(nodes.Get(2), nodes.Get(3)));
devices30 = pointToPoint.Install(nodes.Get(3), nodes.Get(0)));
InternetStackHelper stack;
stack.Install(nodes);
Ipv4AddressHelper address;
address.SetBase(“10.1.1.0”, “255.255.255.0”);
Ipv4InterfaceContainer interfaces01 = address.Assign(devices01);
address.SetBase(“10.1.2.0”, “255.255.255.0”);
Ipv4InterfaceContainer interfaces12 = address.Assign(devices12);
address.SetBase(“10.1.3.0”, “255.255.255.0”);
Ipv4InterfaceContainer interfaces23 = address.Assign(devices23);
address.SetBase(“10.1.4.0”, “255.255.255.0”);
Ipv4InterfaceContainer interfaces30 = address.Assign(devices30);
- Implement Dijkstra’s Link State Routing Protocol:
- Create a new header file dijkstra-routing.h:
#ifndef DIJKSTRA_ROUTING_H
#define DIJKSTRA_ROUTING_H
#include “ns3/ipv4-routing-protocol.h”
#include “ns3/ipv4.h”
#include “ns3/net-device.h”
#include “ns3/ptr.h”
#include “ns3/socket.h”
#include <map>
#include <vector>
namespace ns3 {
class DijkstraRouting : public Ipv4RoutingProtocol {
public:
static TypeId GetTypeId(void);
DijkstraRouting();
virtual ~DijkstraRouting();
virtual Ptr<Ipv4Route> RouteOutput(
Ptr<Packet> p, const Ipv4Header &header,
Ptr<NetDevice> oif, Socket::SocketErrno &sockerr);
virtual bool RouteInput(
Ptr<const Packet> p, const Ipv4Header &header,
Ptr<const NetDevice> idev,
UnicastForwardCallback ucb, MulticastForwardCallback mcb,
LocalDeliverCallback lcb, ErrorCallback ecb);
virtual void NotifyInterfaceUp(uint32_t interface);
virtual void NotifyInterfaceDown(uint32_t interface);
virtual void NotifyAddAddress(uint32_t interface, Ipv4InterfaceAddress address);
virtual void NotifyRemoveAddress(uint32_t interface, Ipv4InterfaceAddress address);
virtual void SetIpv4(Ptr<Ipv4> ipv4);
void Start();
private:
void CalculateShortestPaths();
void BroadcastLinkStateUpdates();
void ReceiveLinkStateUpdates(Ptr<Socket> socket);
void ProcessLinkStatePacket(Ptr<Packet> packet);
Ptr<Ipv4> m_ipv4;
std::map<Ipv4Address, std::map<Ipv4Address, uint32_t>> m_linkStateTable;
std::map<Ipv4Address, Ipv4Address> m_routingTable;
std::map<uint32_t, Ptr<Socket>> m_socketMap;
Time m_updateInterval;
EventId m_updateEvent;
};
}
#endif // DIJKSTRA_ROUTING_H
Create the corresponding implementation file dijkstra-routing.cc:
#include “dijkstra-routing.h”
#include “ns3/log.h”
#include “ns3/ipv4-routing-table-entry.h”
#include “ns3/simulator.h”
#include “ns3/inet-socket-address.h”
namespace ns3 {
NS_LOG_COMPONENT_DEFINE(“DijkstraRouting”);
NS_OBJECT_ENSURE_REGISTERED(DijkstraRouting);
TypeId DijkstraRouting::GetTypeId(void) {
static TypeId tid = TypeId(“ns3::DijkstraRouting”)
.SetParent<Ipv4RoutingProtocol>()
.SetGroupName(“Internet”)
.AddConstructor<DijkstraRouting>();
return tid;
}
DijkstraRouting::DijkstraRouting() : m_updateInterval(Seconds(5)) {
NS_LOG_FUNCTION(this);
Simulator::Schedule(Seconds(1.0), &DijkstraRouting::Start, this);
}
DijkstraRouting::~DijkstraRouting() {
NS_LOG_FUNCTION(this);
}
void DijkstraRouting::SetIpv4(Ptr<Ipv4> ipv4) {
NS_LOG_FUNCTION(this << ipv4);
m_ipv4 = ipv4;
}
void DijkstraRouting::Start() {
NS_LOG_FUNCTION(this);
CalculateShortestPaths();
BroadcastLinkStateUpdates();
m_updateEvent = Simulator::Schedule(m_updateInterval, &DijkstraRouting::Start, this);
}
void DijkstraRouting::CalculateShortestPaths() {
NS_LOG_FUNCTION(this);
Ipv4Address src = m_ipv4->GetAddress(1, 0).GetLocal();
std::map<Ipv4Address, uint32_t> dist;
std::map<Ipv4Address, bool> visited;
std::map<Ipv4Address, Ipv4Address> prev;
for (auto const &link : m_linkStateTable) {
dist[link.first] = UINT32_MAX;
visited[link.first] = false;
}
dist[src] = 0;
for (size_t i = 0; i < m_linkStateTable.size(); ++i) {
Ipv4Address u;
uint32_t minDist = UINT32_MAX;
for (auto const &link : m_linkStateTable) {
if (!visited[link.first] && dist[link.first] <= minDist) {
minDist = dist[link.first];
u = link.first;
}
}
visited[u] = true;
for (auto const &neighbor : m_linkStateTable[u]) {
Ipv4Address v = neighbor.first;
uint32_t weight = neighbor.second;
if (!visited[v] && dist[u] != UINT32_MAX && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
prev[v] = u;
}
}
}
m_routingTable.clear();
for (auto const &link : m_linkStateTable) {
Ipv4Address dest = link.first;
if (dest != src) {
Ipv4Address nextHop = dest;
while (prev[nextHop] != src) {
nextHop = prev[nextHop];
}
m_routingTable[dest] = nextHop;
}
}
}
void DijkstraRouting::BroadcastLinkStateUpdates() {
NS_LOG_FUNCTION(this);
Ptr<Packet> packet = Create<Packet>();
for (auto const &link : m_linkStateTable) {
Ipv4Address addr = link.first;
for (auto const &neighbor : link.second) {
Ipv4Address neighborAddr = neighbor.first;
uint32_t cost = neighbor.second;
packet->AddHeader(Ipv4Header(addr, neighborAddr, cost, 0));
}
}
for (uint32_t i = 0; i < m_ipv4->GetNInterfaces(); ++i) {
Ptr<Socket> socket = m_socketMap[i];
socket->SendTo(packet, 0, InetSocketAddress(Ipv4Address::GetBroadcast(), 80));
}
}
void DijkstraRouting::ReceiveLinkStateUpdates(Ptr<Socket> socket) {
NS_LOG_FUNCTION(this);
Ptr<Packet> packet = socket->Recv();
ProcessLinkStatePacket(packet);
}
void DijkstraRouting::ProcessLinkStatePacket(Ptr<Packet> packet) {
NS_LOG_FUNCTION(this);
Ipv4Header header;
packet->RemoveHeader(header);
Ipv4Address addr = header.GetSource();
Ipv4Address neighborAddr = header.GetDestination();
uint32_t cost = header.GetIdentification();
m_linkStateTable[addr][neighborAddr] = cost;
CalculateShortestPaths();
}
Ptr<Ipv4Route> DijkstraRouting::RouteOutput(
Ptr<Packet> p, const Ipv4Header &header, Ptr<NetDevice> oif,
Socket::SocketErrno &sockerr) {
NS_LOG_FUNCTION(this << p << header << oif << sockerr);
Ipv4Address dest = header.GetDestination();
if (m_routingTable.find(dest) == m_routingTable.end()) {
sockerr = Socket::ERROR_NOROUTETOHOST;
return 0;
}
Ptr<Ipv4Route> route = Create<Ipv4Route>();
route->SetDestination(dest);
route->SetGateway(m_routingTable[dest]);
route->SetOutputDevice(oif);
return route;
}
bool DijkstraRouting::RouteInput(
Ptr<const Packet> p, const Ipv4Header &header,
Ptr<const NetDevice> idev, UnicastForwardCallback ucb,
MulticastForwardCallback mcb, LocalDeliverCallback lcb,
ErrorCallback ecb) {
NS_LOG_FUNCTION(this << p << header << idev << ucb << mcb << lcb << ecb);
Ipv4Address dest = header.GetDestination();
if (dest == m_ipv4->GetAddress(1, 0).GetLocal()) {
lcb(p, header, idev);
return true;
}
if (m_routingTable.find(dest) == m_routingTable.end()) {
ecb(p, header, Socket::ERROR_NOROUTETOHOST);
return false;
}
Ptr<Ipv4Route> route = Create<Ipv4Route>();
route->SetDestination(dest);
route->SetGateway(m_routingTable[dest]);
route->SetOutputDevice(idev);
ucb(route, p, header);
return true;
}
void DijkstraRouting::NotifyInterfaceUp(uint32_t interface) {
NS_LOG_FUNCTION(this << interface);
Ptr<Socket> socket = Socket::CreateSocket(GetObject<Node>(), TypeId::LookupByName(“ns3::UdpSocketFactory”));
socket->SetAllowBroadcast(true);
socket->BindToNetDevice(m_ipv4->GetNetDevice(interface));
socket->Bind(InetSocketAddress(Ipv4Address::GetAny(), 80));
socket->SetRecvCallback(MakeCallback(&DijkstraRouting::ReceiveLinkStateUpdates, this));
m_socketMap[interface] = socket;
}
void DijkstraRouting::NotifyInterfaceDown(uint32_t interface) {
NS_LOG_FUNCTION(this << interface);
m_socketMap[interface]->Close();
m_socketMap.erase(interface);
}
void DijkstraRouting::NotifyAddAddress(uint32_t interface, Ipv4InterfaceAddress address) {
NS_LOG_FUNCTION(this << interface << address);
}
void DijkstraRouting::NotifyRemoveAddress(uint32_t interface,
Ipv4InterfaceAddress address) {
NS_LOG_FUNCTION(this << interface << address);
}
}
- Integrate the Custom Routing Protocol:
#include “dijkstra-routing.h”
int main(int argc, char *argv[]) {
CommandLine cmd;
cmd.Parse(argc, argv);
NodeContainer nodes;
nodes.Create(4);
PointToPointHelper pointToPoint;
pointToPoint.SetDeviceAttribute(“DataRate”, StringValue(“5Mbps”));
pointToPoint.SetChannelAttribute(“Delay”, StringValue(“2ms”));
NetDeviceContainer devices01, devices12, devices23, devices30;
devices01 = pointToPoint.Install(nodes.Get(0), nodes.Get(1)));
devices12 = pointToPoint.Install(nodes.Get(1), nodes.Get(2)));
devices23 = pointToPoint.Install(nodes.Get(2), nodes.Get(3)));
devices30 = pointToPoint.Install(nodes.Get(3), nodes.Get(0)));
InternetStackHelper stack;
DijkstraRoutingHelper dijkstraRouting;
Ipv4ListRoutingHelper list;
list.Add(dijkstraRouting, 0);
stack.SetRoutingHelper(list);
stack.Install(nodes);
Ipv4AddressHelper address;
address.SetBase(“10.1.1.0”, “255.255.255.0”);
address.Assign(devices01);
address.SetBase(“10.1.2.0”, “255.255.255.0”);
address.Assign(devices12);
address.SetBase(“10.1.3.0”, “255.255.255.0”);
address.Assign(devices23);
address.SetBase(“10.1.4.0”, “255.255.255.0”);
address.Assign(devices30);
// Set up applications
uint16_t port = 9;
UdpEchoServerHelper server(port);
ApplicationContainer apps = server.Install(nodes.Get(3));
apps.Start(Seconds(1.0));
apps.Stop(Seconds(10.0));
UdpEchoClientHelper client(address.GetAddress(3), port);
client.SetAttribute(“MaxPackets”, UintegerValue(1));
client.SetAttribute(“Interval”, TimeValue(Seconds(1.0)));
client.SetAttribute(“PacketSize”, UintegerValue(1024));
apps = client.Install(nodes.Get(0));
apps.Start(Seconds(2.0));
apps.Stop(Seconds(10.0));
Simulator::Run();
Simulator::Destroy();
return 0;
}
Explanation
At this point we have demonstrated the description for the process:
- Network Topology: The code sets up a network topology with four nodes connected in a ring.
- Dijkstra’s Link State Routing Protocol: A custom Dijkstra’s link state routing protocol class (DijkstraRouting) is implemented. This class handles the computation of shortest paths using Dijkstra’s algorithm.
- Shortest Path Calculation: The CalculateShortestPaths method computes the shortest paths from a source node to all other nodes using Dijkstra’s algorithm.
- Link State Updates: The BroadcastLinkStateUpdates method broadcasts link state updates to neighbors, and ReceiveLinkStateUpdates processes incoming updates.
- Route Input and Output: The RouteInput and RouteOutput methods handle packet routing using the computed shortest paths.
- Integrate Custom Routing Protocol: The custom routing protocol is integrated into the ns-3 stack using the DijkstraRoutingHelper.
- Applications: UdpEchoServer and UdpEchoClient applications are set up to test the routing.
Running the Code
- Save your script to a file, for example, dijkstra-routing.cc.
- Compile the script using the ns-3 build system:
./waf configure –enable-examples
./waf build
./waf –run scratch/dijkstra-routing
Finally, we explore the basic implementation procedures how to simulate the Dijikstra algorithm in ns3 tool and we also provide related comparative analysis about Dijikstra’s routing protocol.