• Intra-domain Routing Protocol

    • Link State - i.e. Open Shortest Path First (OSPF)
    • Distance Vector - i.e. Routing Information Protocol (RIP)
  • Inter-domain Routing Protocol

    • Path Vector i.e. Border Gateway Protocol (BGP)

Routing Algorithms

All routers have knowledge of the costs of each router to their peers.

When a new link state message is received, the router forwards the message to its peers.

Dijkstra’s Algorithm - Find best route via costs

By using Dijkstra’s algorithm, a forwarding table can be constructed which tells the router which peer to send a packet to next, to best deliver that packet to a node.


  • Scalability - Requires O(nodes * edges) complexity
  • Scalability - O(N^2) operation for Dijkstra’s Algorithm
  • Transient Disruptions - Network failures
    • All routers may not have the same shared best path, and may send back to the previous host
  • Incorrect link cost may be advertised

Distance Vector (Decentralised)

Each router only has knowledge of its adjacent peers.

  • Bellman-Ford equation

  • Each router maintains its shortest distance to every destination via its neighbours

  • Each router computes its shortest distance to every destination via any of its neighbours

Distance vector is created and shared between routers - like a shared table, as opposed the link state where each router makes calls to every other router

This is a better method as:

  • Distributed - Shared distance vector
  • Asynchronous - Only happens when a cost changes

  • Initialise with immediate peers

  • Kth simultaneous rounds - Best K+1 hop paths


  • Count to Infinity Problem
    • Negative changes to the network update slowly (because all devices prefer to use the best-case/shortest link)
    • Solution - Poisoned Reverse Rule
    • A -> B -> C
    • A tells B that A->C is infinity, so that B won’t route back to A
  • Advertise incorrect path cost

Internet Control Message Protocol (ICMP)

Used by hosts and routers to communicate network level information.

It uses IP datagrams

  • Error reporting - unreachable network, host or port
  • Echo requests and replies

Message: Type, Code, IP Header, First 8 bytes of IP datagram payload (containing TCP/UDP port numbers)

00echo reply (ping)
30destination network unreachable
31destination host unreachable
33destination port unreachable
34fragmentation needed - DF (Do-not-fragment) flag was set
80echo request (ping)
110TTL expired
111fragment reassembly time expired
120bad IP header

The n-th set of UDP segments has TTL=n.

When the n=th set reaches the n’th router, TTL expire is returned, along with the IP address of the router