5.2 – Routing Algorithms

• Routing algorithms: whose goal is to determine good paths, form the sender to receivers, through the network of routers.
• Typically, a “good” path is one that has the least cost. We’ll see that in practice, however, real-world concerns such as policy issues also comes into play.
• We note that whether the network control plane adopts a per-router control approach or a logically centralized approach, there must always be a well-defined sequence of routers that a packet will cross in traveling from sending to receiving host. Thus, the routing algorithms that compute these paths are of fundamental importance, and another candidate for our top-10 list of fundamentally important networking concepts.
• A graph is used to formulate routing problems. A graph $$G = (N,E)$$ is a set N of nodes and a collection E of edges, where each edge is a pair of nodes from N. In the context of network-layer routing, the nodes in the graph represent routers, the points at which packet-forwarding decisions are made. And the edges connection these nodes represent the physical links between these routers.
  • We’ll only consider undirected graphs in our discussion. So that edge $$(x,y)$$ is the same as edge $$(y,x)$$ and that $$c(x,y)=c(y,x)$$.
  • Typically an edge’s cost may reflect the physical length of the corresponding link, the link speed, or the monetary cost associated with a link.
  • For any edge $$(x,y)$$ in E, we denote $$c(x,y)$$ as the cost of the edge between nodes x and y. If the pair $$(x,y)$$ does not belong to E, we set $$c(x,y)=\infty$$.
  • A node y is said to be a neighbor of node x if $$(x,y)$$ belongs to E.
  • The goal of a routing algorithm is to identify the least costly paths between sources and destinations.
  • To make this problem more precise, recall that a path in a graph $$G=(N,E)$$ is a sequence of nodes $$(x1,x_2,...,x_p)$$ such that each of the pairs $$(x_1,x_2),(x_2,x_3), ..., (x{p-1},xp)$$ are edges in E. The cost of a path $$(x_1,x_2,...,x_p)$$ is simply the sum of all the edges costs along the path, that is, $$c(x_1,x_2)+c(x_2,x_3)+...+c(x{p-1},x_p)$$. Given any two nodes x and y, there are typically many paths between the two nodes, with each path having a cost.
    • One or more of these paths is a least-cost path. The least-cost problem is to find a path between the source and destination that has least cost.
      • Note that if all edges in the graph have the same cost, then the least cost path is also the shortest path.
• A centralized routing algorithm:
  • Computes the least-cost path using complete, global knowledge about the network. That is, the algorithm takes the connectivity between all nodes and all link costs as inputs. This then requires that the algorithm somehow obtain this information before actually performing the calculation.
  • The calculation itself can be run at one site or could be replicated in the routing component of each and every router.
  • The algorithm has complete information about connectivity and link costs. Algorithms with global state information are often referred to as link-state (LS) algorithms, since the algorithm must be aware of the cost of each link in the network.
• A decentralized routing algorithm:
  • The calculation of the least-cost path is carried out in an iterative, distributed manner by the routers. No node has complete information about the costs of all network links. Instead, each node begins with only the knowledge of the cost of its own directly attached links. Then, through an iterative process of calculation and exchange of information with its neighboring nodes, a node gradually calculates the least-cost path to a destination or set of destinations.
  • One Decentralized algorithm is called Distance-vector (DV):
    • Because each node maintains a vector of estimates of the costs (distances) to all other nodes in the network.
• In static routing algorithms, routes change very slowly over time, often as a result of human intervention.
• Dynamic routing algorithms change the routing paths as the network traffic loads or topology change. A dynamic algorithm can run either periodically or in a direct response to topology or link cost changes. While dynamic algorithms are more responsive to network changes, they are also more susceptible to problems such as routing loops and route oscillation.
• In a load-sensitive algorithm, link costs vary dynamically to reflect the current level of congestion in the underlying link. If a high cost is associated with a link that is currently congested, a routing algorithm will tend to choose routes around such a congested link.
• Today’s Internet routing algorithms are load-insensitive, as a link’s cost does not explicitly reflect its current level of congestion.