Quick Links


General

 Home
 Teachers
 Module Organiser
 Exams
 Activities
 Ask a Question
 Index


Emulators
 Router
 Switch
 UNIX
 Wireless
 5-router
 Modem
 Host

Material
 Notes
 Presentations
 Tutorials
 Challenge
 Worksheets

Sockets
 VB Sockets
 Java Sockets
 VB Code
 Java Code

Quizzes
 Pub Challenge
 OSI Model  
 Bits, bytes and frames
 Hangman
 Subnetting
 IQ Test

Free Updates

Network Emulators
CNDS site

 

 

 

cnds research 2: Routes
Back | Research 1 | Research 2  | Research 3  |[CNDS] 

PDF Version

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:

Route

Hops

ABH

3

ABCDFGH

7

ABEH

4

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:

Glasgow to Falkirk

50 miles

Glasgow to Oban

100 miles

Oban to Inverness

90 miles

Oban to Stirling

120 miles

Inverness to Stirling

100 miles

Stirling to Falkirk

5 miles

Stirling to Edinburgh

60 miles

Stirling to Dunfermline

20 miles

Falkirk to Edinburgh

70 miles

Dunfermline to Edinburgh

15 miles

 

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:

Glasgow, Oban, Stirling, Dunfermline, Edinburgh

255 miles

Glasgow, Oban, Stirling, Falkirk, Edinburgh

295 miles

Glasgow, Falkirk, Edinburgh

120 miles

Glasgow, Falkirk, Stirling, Dunfermline, Edinburgh

90 miles

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


Research 2

Name:

Email:

Matriculation number:

Programme:

Institution:

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.