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.
<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>
Reblogged this on Bits and Pieces of Code and commented:
Really cool! Awesome.