[Back to Lecture Notes page]

Routing Algorithms

• If a router receives an incoming packet, which outgoing line should the packet be sent out on? – that is problem routing algorithms are trying to find a solution to.

• In virtual circuits, all routes are decided when we set up a circuit from a particular source to a destination

• Also called session routing since all packets belong to a particular session using that virtual circuit will be sent along the same route.

• In datagram subnets, this decision is made for each new packet independent of other packets

• The same algorithms below apply to both virtual circuits and datagram subnets.

Desirable Properties of Routing Algorithms

• Correctness – are the packets getting to the right destination?

• Simplicity – the simpler the algorithm and steps, the easier to understand, the easier to extend, modify and improve.

• Robustness – If something happens to the network (eg. some lines go down, some user in a machine starts sending out a huge amount of data, etc), does the algorithm cater for that?This is good if a network is very dynamic and changes occur frequently.

• Stability – Does the routes change all the time? If the routes are unstable, even when there are little changes to the network, the routers will incur the overhead of having to keep changing their routing tables for no reason. This must be balanced with robustness of the algorithm.

• Fairness – How well does the algorithm ensure all routers have the same shareof network utilization, and the same consideration when finding routes for them?

• Optimality – How well does the algorithm ensure that the cost (time, hops, distance, etc) is kept to a minimal? This is balanced against fairness.

Static vs Dynamic Routing

• Static (or non-adaptive) routing:

• All choices for a router determined before router comes on-line.

• Dynamic (or adaptive)

• Choices depends on changes to network topology and traffic

• But:
  • Where to look for information on changes?
  • How often to change the choices?
  • How to determine best new choice?

Finding a Sink Tree

• Optimality Principle:

• Optimality principle guarantees a unique set of connections which gives optimum path for all nodes – this is the sink tree.

• The object of the algorithms is to find this sink tree.

• Problem with always using a sink tree:

• Some nodes may go down – need to recompute sink tree.

Static Routing

• Shortest Path Routing

• Flooding

• Flow-based Routing

Shortest Path Routing

• Short as defined by either:

• Number of hops
• Geographical distance
• Delay Time

• Dijkstra's algorithm – computes the shortest path from a source to a destination. Requires complete knowledge of the topology.

Flooding

• Send a packet out on ALL lines except the one it came in.

• Guaranteed to reach destination in minimum time.

• Generates large amount of traffic.

• Needs damming mechanism – eg. put the past routers address into the packets, and if a routers sees its own address in a new packet, the packet must be a previously sent one and it doesn't send it out any more.

• Selective Flooding – not send out to EVERY possible line, but to a subset of lines which are in the general direction.

Flow Based Routing

• Using information about topology, line capacities and traffic characteristics to determine a "best" algorithm

• Steps:

• For each algorithm

• Compute all paths

• Combine all paths to determine the traffic and expected delay going through each node

• Select the algorithm which minimizes the overall load.

Dynamic Routing

• Distance Vector Routing

• Link State Routing

• Hierarchical Routing

• Routing for Mobile Hosts

• Broadcast and Multicast Routing

Distance Vector Routing

• Each router has a table of:

• Which line to use for which destination

• The delay to get to each destination

• Also called Bellman-Ford or Ford-Fulkerson algorithm – after the people who derived it.

• Used in the original ARPANET, now on the Internet as RIP (Routing Information Protocol)
  • Also early versions of Novell IPX
  • AppleTalk and Cisco uses improved versions.

• How it works:

• Each router must know the delay to its immediate neighbours

• Periodically, each router sends its estimates to all destinations to all its neighbours

• Each router re-computes which neighbour to send a certain packets meant for a certain destination.

Link State Routing

• To replace Distance Vector Routing

• Problem with Distance Vector Routing – uses only delay at a node – doesn't consider line capacity

• How it works. Each router

1. Discover its neighbours and addresses – this is done by sending out HELLO packets on start-up and receiving replies from neighbours.
2. Measure the cost to each neighbour – measure the round-trip time taken to send an ECHO packet and to receive a reply.
3. Construct link state packets and send all routers – these link state packets contains what each router knows about the cost to each of its neighbours. See figure 5-15 p362.
4. Compute the shortest path to each router based on received link state packets from other routers.

Hierarchical Routing

• What happens to table when network gets too big?

• Divide network into regions

• Each region has a main router

• All routers only need to know about their region's routers, other regions' main routers.

Figure 5-17 p366

Routing for Mobile Hosts

• How to find a portable host which could potentially be anywhere?

• Each mobile host has a home location, with a home agent.

• When the mobile host moves to a new location, it registers with a foreign agent

• Foreign agent lets home agent know

• When a sender sends a packet to the mobile host,

• Home agent forwards packet to foreign agent to pass to mobile host

• Home agent also notifies sender to send subsequent packets to mobile host's foreign agent

Broadcast Routing

• Sending packets to more than one host in the subnet.

• Possible ways:

• Sender sends one packet to each possible destination

• Flooding

• Multi-destination Routing

• Using spanning tree (sink tree) – a tree that covers all nodes but do not contain loops.

Multicast Routing

• Some hosts spread over a large network can be put into "multicast" groups – packets sent out to a group is sent to every member of a group.

• Can't use broadcast since some machines are not meant to receive the packets

• One way of doing multi-cast routing to a particular group:

• Compute a spanning tree joining all nodes – there may be more than one.

• Delete the links which do not lead to members of the group.

[Back to Lecture Notes page]