A Network Routing Simulation in JavaScript with the Bellman-Ford Algorithm

Posted on 2016/11/04 by thiscouldbebetter

The JavaScript code below, when run, simulates routing of packets within a simple computer network using the Bellman-Ford routing algorithm. To see it in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

The simulation will be updated once per second, as packets are routed towards their destination nodes. New packets can be created by entering the appropriate text in the box and clicking the “Do” button. The nodes will share routing tables among themselves every 5 seconds.

networkroutingsimulator




<html>
<body>

<script type="text/javascript">

// main

function main()
{
	var display = new Display
	(
		new Coords(400, 300), // sizeInPixels
		10, // fontHeightInPixels
		"White", // colorBackground
		"Gray" // colorForeground
	);

	var network = new Network
	(
		new Coords(20, 20), // nodeSizeInPixels
		5, // timerTicksPerRouteShare
		// nodes
		[
			new Node("Node0", new Coords(30, 30)),
			new Node("Node1", new Coords(90, 90)),
			new Node("Node2", new Coords(150, 150)),
			new Node("Node3", new Coords(90, 210)),

		],
		// links
		[
			new Link( ["Node0", "Node1"], 8),
			new Link( ["Node1", "Node2"], 8),
			new Link( ["Node2", "Node3"], 8),
		], 
		// packets
		[
			// todo
		]
	);

	Globals.Instance.initialize
	(
		display,
		1, // timerTicksPerSecond
		network
	);
}

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.addLookups = function(keyName)
	{
		for (var i = 0; i < this.length; i++)
		{
			var element = this[i];
			var key = element[keyName];
			this[key] = element;
		}

		return this;
	}

	Array.prototype.remove = function(element)
	{
		var indexOfElement = this.indexOf(element);
		if (indexOfElement >= 0)
		{
			this.splice(indexOfElement, 1);
		}
		return this;
	}
}

// classes

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	// instances

	Coords.Instances = new Coords_Instances();

	function Coords_Instances()
	{
		this.Zeroes = new Coords(0, 0);
	}

	// methods

	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		return this;
	}

	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;
		return this;
	}

}

function Display(sizeInPixels, fontHeightInPixels, colorBackground, colorBorder)
{
	this.sizeInPixels = sizeInPixels;
	this.fontHeightInPixels = fontHeightInPixels;
	this.colorBackground = colorBackground;
	this.colorBorder = colorBorder;
}
{
	Display.prototype.clear = function()
	{
		this.drawRectangle
		(
			Coords.Instances.Zeroes, 
			this.sizeInPixels, 
			this.colorBackground,
			this.colorBorder
		);
	}

	Display.prototype.drawLine = function(posFrom, posTo, color)
	{
		this.graphics.strokeStyle = color;
		this.graphics.beginPath();
		this.graphics.moveTo(posFrom.x, posFrom.y);
		this.graphics.lineTo(posTo.x, posTo.y);
		this.graphics.stroke();
	}

	Display.prototype.drawRectangle = function(pos, size, colorFill, colorBorder)
	{
		this.graphics.fillStyle = colorFill;
		this.graphics.fillRect(pos.x, pos.y, size.x, size.y);

		this.graphics.strokeStyle = colorBorder;
		this.graphics.strokeRect(pos.x, pos.y, size.x, size.y);	
	}

	Display.prototype.drawText = function(text, pos, color)
	{
		this.graphics.fillStyle = color;
		this.graphics.fillText
		(
			text, pos.x, pos.y
		);
	}

	Display.prototype.initialize = function()
	{
		var canvas = document.createElement("canvas");
		canvas.width = this.sizeInPixels.x;
		canvas.height = this.sizeInPixels.y;

		this.graphics = canvas.getContext("2d");

		this.graphics.font = 
			this.fontHeightInPixels + "px sans-serif";

		document.body.appendChild(canvas);
	}

}

function Globals()
{
	// do nothing
}
{
	// instance

	Globals.Instance = new Globals();
	
	// methods

	Globals.prototype.initialize = function
	(
		display, timerTicksPerSecond, network
	)
	{
		this.display = display;
		this.display.initialize();

		this.network = network;
		this.network.initialize();

		var millisecondsPerTimerTick = 
			1000 / timerTicksPerSecond;

		this.timerTicksSoFar = 0;

		this.handleEventTimerTick();

		this.timer = setInterval
		(
			this.handleEventTimerTick.bind(this),
			millisecondsPerTimerTick
		);
	}

	Globals.prototype.handleEventTimerTick = function()
	{
		this.network.updateForTimerTick();
		this.network.drawToDisplay(this.display);

		this.timerTicksSoFar++;
	}
}

function Link(namesOfNodesLinked, costToTraverse)
{
	this.namesOfNodesLinked = namesOfNodesLinked;
	this.costToTraverse = costToTraverse;
}
{
	Link.prototype.node0 = function()
	{
		return Globals.Instance.network.nodes[this.namesOfNodesLinked[0]];
	}

	Link.prototype.node1 = function()
	{
		return Globals.Instance.network.nodes[this.namesOfNodesLinked[1]];
	}

	Link.prototype.nodes = function()
	{
		return [ this.node0(), this.node1() ];
	}

	// drawable

	Link.prototype.drawToDisplay = function(display)
	{
		var node0Center = this.node0().center(); 
		var node1Center = this.node1().center();

		display.drawLine
		(
			node0Center, node1Center, "Gray"
		);

		var midpoint = node0Center.add
		(
			node1Center
		).divideScalar(2);

		display.drawText
		(
			"" + this.costToTraverse, 
			midpoint,
			"Gray"
		);
	}	
}

function Network(nodeSizeInPixels, timerTicksPerRouteShare, nodes, links, packets)
{
	this.nodeSizeInPixels = nodeSizeInPixels;
	this.timerTicksPerRouteShare = timerTicksPerRouteShare;
	this.nodes = nodes;
	this.links = links;
	this.packets = packets;

	this.nodes.addLookups("name");
	this.packetsToRemove = [];
}
{
	Network.prototype.initialize = function()
	{
		for (var i = 0; i < this.links.length; i++)
		{
			var link = this.links[i];
			var nodesLinked = link.nodes();
			for (var n = 0; n < nodesLinked.length; n++)
			{
				var nodeSource = nodesLinked[n];
				var nodeTarget = nodesLinked[1 - n]; 

				var linkToNeighbor = new Link
				(
					[
						nodeSource.name, 
						nodeTarget.name,
					],
					link.costToTraverse
				);

				nodeSource.linksToNeighbors.push(linkToNeighbor);				
			}
		}

		for (var i = 0; i < this.nodes.length; i++)
		{
			var node = this.nodes[i];
			node.initialize();
		}

		this.domElementUpdate();
	}

	Network.prototype.routesShareAmongNodes = function()
	{
		for (var i = 0; i < this.nodes.length; i++)
		{
			var node = this.nodes[i];
			node.routesShareWithNeighbors();
		}
	}

	Network.prototype.updateForTimerTick = function()
	{
		var timerTicksSoFar = Globals.Instance.timerTicksSoFar;
		if 
		(
			timerTicksSoFar != 0 
			&& timerTicksSoFar % this.timerTicksPerRouteShare == 0
		)
		{
			this.routesShareAmongNodes();	
		}

		this.packetsToRemove.length = 0;

		for (var i = 0; i < this.packets.length; i++)
		{
			var packet = this.packets[i];
			if (packet.isDelivered() == true)
			{
				this.packetsToRemove.push(packet);
				packet.nodeCurrent().packetsDelivered.push(packet);
			}
			else
			{
				packet.updateForTimerTick();
			}
		}

		for (var i = 0; i < this.packetsToRemove.length; i++)
		{
			var packet = this.packetsToRemove[i];
			this.packets.remove(packet);
		}		
	}

	// dom

	Network.prototype.domElementUpdate = function()
	{
		if (this.domElement == null)
		{
			var divNetwork = document.createElement("div");

			var divControls = document.createElement("div");

			var labelCommand = document.createElement("label");
			labelCommand.innerHTML = "Command:";
			divControls.appendChild(labelCommand);

			var inputCommandText = document.createElement("input");
			inputCommandText.id = "inputCommandText";
			inputCommandText.value = "packet Node0 Node3 data"
			divControls.appendChild(inputCommandText);
			
			var buttonCommandPerform = document.createElement("button");
			buttonCommandPerform.innerHTML = "Do";
			buttonCommandPerform.onclick = this.buttonCommandPerform_Clicked.bind(this);
			divControls.appendChild(buttonCommandPerform);

			var buttonCommandHelp = document.createElement("button");
			buttonCommandHelp.innerHTML = "Help";
			buttonCommandHelp.onclick = this.buttonCommandHelp_Clicked.bind(this);
			divControls.appendChild(buttonCommandHelp);

			divNetwork.appendChild(divControls);

			document.body.appendChild(divNetwork);

			this.domElement = divNetwork;
		}
	}

	Network.prototype.buttonCommandHelp_Clicked = function()
	{
		var message = "Valid command format: 'packet [from] [to] [data]'";
		alert(message);
	}

	Network.prototype.buttonCommandPerform_Clicked = function()
	{
		var inputCommandText = document.getElementById("inputCommandText");
		var commandText = inputCommandText.value;
		var commandArguments = commandText.split(" ");
		var operationName = commandArguments[0];
		
		if (operationName == "packet")
		{
			if (commandArguments.length != 4)
			{
				alert("Wrong number of arguments!");
			}

			var nodeNameSource = commandArguments[1]; 
			var nodeTargetName = commandArguments[2];
			var payload = commandArguments[3];

			var nodeSource = this.nodes[nodeNameSource];
			var nodeTarget = this.nodes[nodeTargetName];

			if (nodeSource == null)
			{
				alert("Invalid source node name: " + nodeNameSource);
			}
			else if (nodeSource == null)
			{
				alert("Invalid target node name: " + nodeNameSource);
			}
			else
			{
				var packet = new Packet
				(
					nodeNameSource, nodeTargetName, payload
				);
				this.packets.push(packet);

			}
		}
		else
		{
			alert("Unrecognized command!");
		}
	}

	// drawable

	Network.prototype.drawToDisplay = function(display)
	{
		display.clear();

		for (var i = 0; i < this.links.length; i++)
		{
			var link = this.links[i];
			link.drawToDisplay(display);
		}

		for (var i = 0; i < this.nodes.length; i++)
		{
			var node = this.nodes[i];
			node.drawToDisplay(display);
		}

		for (var i = 0; i < this.packets.length; i++)
		{
			var packet = this.packets[i];
			packet.drawToDisplay(display);
		}

		display.drawText
		(
			"Time:" + Globals.Instance.timerTicksSoFar, 
			new Coords(10, 10), 
			"Gray"
		);

		display.drawText
		(
			"Routes shared every " 
				+ this.timerTicksPerRouteShare 
				+ " ticks.", 
			new Coords(10, 20), 
			"Gray"
		);
	}
}

function Node(name, pos)
{
	this.name = name;
	this.pos = pos;
	
	this.linksToNeighbors = [];
	this.routes = [];
	this.packetsDelivered = [];
}
{
	Node.prototype.center = function()
	{
		return this.size().clone().divideScalar(2).add(this.pos);
	}

	Node.prototype.initialize = function()
	{
		for (var i = 0; i < this.linksToNeighbors.length; i++)
		{
			var link = this.linksToNeighbors[i];

			var neighborName = link.namesOfNodesLinked[1];

			this.linksToNeighbors[neighborName] = link;

			var route = new Route
			(
				neighborName, // nodeTargetName, 
				link.costToTraverse, // totalCostToTarget, 
				neighborName // nodeNextName
			);
			this.routes.push(route);
		}

		this.routes.addLookups("nodeTargetName");
	}

	Node.prototype.routesShareWithNeighbors = function()
	{
		for (var n = 0; n < this.linksToNeighbors.length; n++)
		{
			var link = this.linksToNeighbors[n];
			var nodeNeighbor = link.node1();
			nodeNeighbor.routesUpdateFromNeighbor
			(
				this.name, 
				link.costToTraverse, 
				this.routes
			);
		}
	}

	Node.prototype.routesUpdateFromNeighbor = function
	(
		neighborName, costToNeighbor, routesFromNeighbor
	)
	{
		for (var r = 0; r < routesFromNeighbor.length; r++)
		{
			var routeFromNeighbor = routesFromNeighbor[r];

			var totalCostToTargetThroughNeighbor = 
				costToNeighbor + routeFromNeighbor.totalCostToTarget;

			var nodeTargetName = routeFromNeighbor.nodeTargetName;

			if (nodeTargetName == this.name)
			{
				// do nothing
			}
			else 
			{
				var routeExisting = this.routes[nodeTargetName];
				if (routeExisting == null)
				{
					var routeNew = new Route
					(
						nodeTargetName, // target
						totalCostToTargetThroughNeighbor, 
						neighborName // nodeNextName
					);
	
					this.routes.push(routeNew);
					this.routes[nodeTargetName] = routeNew;
				}
				else if (routeExisting.totalCostToTarget > totalCostToTargetThroughNeighbor)
				{
					routeExisting.totalCostToTarget = totalCostToTargetThroughNeighbor;
					routeExisting.nodeNextName = neighborName;
				}
			}
		}
	}

	Node.prototype.size = function()
	{
		return Globals.Instance.network.nodeSizeInPixels;
	}

	// drawable

	Node.prototype.drawToDisplay = function(display)
	{
		var network = Globals.Instance.network;

		display.drawRectangle
		(
			this.pos, network.nodeSizeInPixels, "White", "Gray"
		);
		display.drawText(this.name, this.pos, "Gray"); 


		var textPos = this.center();
		textPos.y += display.fontHeightInPixels;

		for (var i = 0; i < this.routes.length; i++)
		{
			var route = this.routes[i];
			display.drawText(route.toString(), textPos, "Blue");
			textPos.y += display.fontHeightInPixels;
		}

		for (var i = 0; i < this.packetsDelivered.length; i++)
		{
			var packet = this.packetsDelivered[i];
			display.drawText(packet.toString(), textPos, "DarkGreen");
			textPos.y += display.fontHeightInPixels;
		}

	}
}

function Packet(nodeSourceName, nodeTargetName, payload)
{
	this.nodeSourceName = nodeSourceName;
	this.nodeCurrentName = this.nodeSourceName;
	this.nodeTargetName = nodeTargetName;
	this.payload = payload;

	this.nodeNextName = null;
	this.ticksTowardNodeNext = 0;
}
{
	Packet.prototype.fractionTowardNodeNext = function()
	{
		var returnValue = 
			this.ticksTowardNodeNext 
			/ this.linkCurrent().costToTraverse;

		return returnValue;		
	}

	Packet.prototype.isDelivered = function()
	{
		return (this.nodeCurrentName == this.nodeTargetName);
	}

	Packet.prototype.linkCurrent = function()
	{
		return this.nodeCurrent().linksToNeighbors[this.nodeNextName];
	}

	Packet.prototype.nodeCurrent = function()
	{
		return Globals.Instance.network.nodes[this.nodeCurrentName];
	}

	Packet.prototype.nodeNext = function()
	{
		return Globals.Instance.network.nodes[this.nodeNextName];
	}

	Packet.prototype.updateForTimerTick = function()
	{
		if (this.nodeNextName == null)
		{
			var nodeCurrent = this.nodeCurrent();
			var route = nodeCurrent.routes[this.nodeTargetName];
			if (route == null)
			{
				// Drop the packet?
			}
			else
			{
				this.nodeNextName = route.nodeNextName;
			}
		}
		else
		{
			var linkCurrent = this.linkCurrent();
			if (linkCurrent != null)
			{
				this.ticksTowardNodeNext++;

				if (this.ticksTowardNodeNext < linkCurrent.costToTraverse)
				{
					// todo
				}
				else
				{
					this.nodeCurrentName = this.nodeNextName;	
					this.nodeNextName = null;
					this.ticksTowardNodeNext = 0;
				}
			}

		}
	}

	// drawable

	Packet.prototype.drawToDisplay = function(display, network)
	{
		var pos = this.nodeCurrent().center().clone();

		if (this.nodeNextName != null)
		{
			var fractionTowardNodeNext = 
				this.fractionTowardNodeNext();

			pos.multiplyScalar
			(
				1 - fractionTowardNodeNext
			).add
			(
				this.nodeNext().center().clone().multiplyScalar
				(
					fractionTowardNodeNext
				)
			);
		}


		display.drawText(this.toString(), pos, "Red"); 
	}

	// string

	Packet.prototype.toString = function()
	{
		var returnValue = 
			"[packet"
			+ " from:" + this.nodeSourceName 
			+ " to:" + this.nodeTargetName
			+ " data:" + this.payload 
			+ "]";

		return returnValue;
	}

}

function Route(nodeTargetName, totalCostToTarget, nodeNextName)
{
	this.nodeTargetName = nodeTargetName;
	this.totalCostToTarget = totalCostToTarget;
	this.nodeNextName = nodeNextName;
}
{
	// string

	Route.prototype.toString = function()
	{
		var returnValue = 
			"[route"
			+ " to:" + this.nodeTargetName
			+ " cost:" + this.totalCostToTarget
			+ "]";

		return returnValue;
	}
}

// run 

main();

</script>

</body>
</html>
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

1 Response to A Network Routing Simulation in JavaScript with the Bellman-Ford Algorithm

  1. Karim Oumghar says:
    2016/11/04 at 20:56

    Reblogged this on Bits and Pieces of Code and commented:
    Really cool! Awesome.

    Reply

Leave a comment