Back

Background

As we have seen, network topology and network architecture have a great impact on the performance of networks. The interconnection of these networks is often complex, where routers must pass information to each other about the best way to get to a destination. They could thus base their judgement on many things, such as the:

Hop count. Number of routers that they cross over to get to the destination(a hop count).
Latency. Time taken for a data packet to cross a route (the latency).
Bandwidth. This defines the capacity of routes.
Cost. This is the financial cost of routes.
Error rate. This defines the error rate on routes.
And so on.

For example in Figure 1, there are several ways that can be used to travel between the two networks (Network A and Network B), such as:

If we were basing our routing on the number of hops, then the route ABH would be chosen. For this Router H would tell Router B and Router G that it can reach Network B in one hop. Router B would then inform Router A that it could reach Network B in two hops, and so on. Thus Router A would choose Router B to go to Network B, and Network B would choose Router H rather than Router E, and so on.

Figure 1:

Most routers can implement the hop count principle to determine the best route, but this is not an efficient method, as it is too simplistic, and does not take into account other metrics. Thus routing algorithms are used to determine the best way to get to a node. One of the best known was invented in the 1950s by EW Dijstra, and is known as Dijkstra's Algorithm. For this he defined:

Analyse a part of a route that goes from one routing node to another, and reject the worst routes, so that it reduces the complexity of the problem

This continually reduces the complexity of the route until it can be simplified into a number of alternative routes which can be easily measured against each other. For example, let's say that we need to find the best route from Glasgow to Edinburgh. Figure 2 illustrates the routes which are defined as:

Our task is to determine the shortest route. This of course may not be the best metric, as a route may be shorter, but the speed limit on the route may reduce it so much that a longer route may be quicker.

Figure 2:

First we analyse routes, and delete the ones which are inferior. An easy place to start is the route from Glasgow to Stirling. From this, we can delete the Oban to Inverness to Stirling route as it takes 190 miles, as apposed to 120 miles going straight from Oban to Stirling, as illustrated on the right-hand side of Figure 3. Also we can be delete the direct route from Stirling to Edinburgh, as the route via Dunfermline is shorter.

Figure 3:

It is now difficult to reduce it any more (apart from obviously dismissing the route via Oban), so we can just list the alternatives:

Thus the best route is via Falkirk, Stirling and Dunfermline.

Research 2

1. What is the name of the routing protocol which uses a hop count to determine the best route to get to a destination:

2. With the routing protocol used in Q1, what is the maximum number of hops that it can take to get to a route:

3. Determine some other widely used routing protocols, and the metrics that they may use:

4. Routing protocols are often differentiated between interior and exterior routing protocols. What is basic difference between interior and exterior routing protocols:

5. For the infrastructure given in Figure 2, determine the number of possible routes between Glasgow and Edinburgh:

6. Using in the infrastructure given in Figure 2 and Dijkstra's Algorithm, determine the longest route from Glasgow to Edinburgh.

7. Using the basic router metrics of financial cost, hop count, bandwidth, delay and error rates, outline how these metrics would equate to real metrics that someone would use in a journey, such as speed limit of a route, average delays on the route (such as from traffic lights, or roundabouts), probability of an accident, road tolls, and number of interconnected roads.