Home / Networking Basics / Routing Approaches

Routing Approaches

Here are the major approaches in IP routing.

Flooding

    • copies of a packet are flooded on all the network links
    • a packet that arrives to a node is copied to all interfaces except the one on which it came
    • no state is maintained
    • may lead to a loop
    • ensures that the end host gets the packet
    • there is no routing table involved
    • used when we have no idea of the network topology or when we can not trust it
    • used also in some network state transitions

Source Routing

    • the work happens at the end host.
    • is a good example of the end-to-end design principle in networking
    • the source host knows about the network topology
    • the source host controls the path of the packet: the source host provides in advance the list of nodes through which the packet traverses. The IP addresses of these nodes are written into the packet
    • there is no routing table involved

Spanning Trees

Before learning about spanning trees, let’s recall the construct of forwarding tables.

 Forwarding table

    • we talked about the forwarding table in more detail in this post
    • at each hop, a forwarding table is built and it allows to determine the next hop of each learned network address
routing-forwarding-table-1

Figure: Using a forwarding table at each hop © phoenix.goucher.edu

    • in the end-to-end design principle, the forwarding table is an optimization made at the network level, and not at the end hosts. The network participates in populating the forwarding table.
routing-approaches-spanning-tree-keyboardbanger

Figure: a spanning tree in routing © Stanford University

A spanning tree is a set of logical links built between the source host and the end host. It is called spanning because it spans all the nodes in the path. And it’s called tree because it is loop free.

Spanning trees are used by routing algorithms to build and update the forwarding table at each hop

 

Routing algorithms need to know which metric we are using, in order to be able to determine the minimum-cost spanning tree. Metrics can be of many types:

  • number of hops
  • link cost
  • link reliability
  • link bandwidth
  • link security (“is there a VPN on it?”)
  • the minimum-cost spanning tree is then translated into a forwarding table entry.

Multipath

  • distributes packet among many paths as evenly as possible
  • helps reduce the load on links that are used by many flows

Multicast

  • this technology leverages the network to optimize the propagation of the packet. In fact, the source host sends one instance of the packet. And the packet is replicated at each node towards a select number of end hosts.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Adsense black background: