Routing in IPv4

Network-Layer Functions

  • Forwarding - move packets from router’s input to appropriate router output

    • Data plane

  • Routing - determine route taken by packets from source to destination

    • Control plane

Per-Router Control Plane

Individual routing algorithm components in each and every router interact in the control plane

Routing Protocols

  • Routing protocol goal - determine “good” paths (equivalently, routes), from sending hosts to receiving host, through network of routers

    • Path - sequence of routers packets traverse from given initial source host to final destination host

    • “good” - least “cost”, “fastest”, “least congested”

    • Routing - a “top-10” networking challenge

Graph Abstraction Link Costs

N: set of routers = { u, v, w, x, y, z }
E: set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

Routing Algorithm Classification

Dijkstra's Link-State Routing Algorithm

  • Centralised - network topology, link costs known to all nodes

    • Accomplished via “link state broadcast”

    • All nodes have same info

  • Computes least cost paths from one node (“source”) to all other nodes

    • Gives forwarding table for that node

  • Iterative - after k iterations, know least cost path to k destinations

Notation

  • c_{x,y} - direct link cost from node x to y; =\infty if not direct neighbours

  • D(v) - current estimate of cost of least-cost-path from source to destination v

  • p(v) - predecessor node along path from source to v

  • N' - set of nodes whose least-cost-path definitively known

Why it works?

  • At each iteration, select the node with the smallest tentative distance (from the source) that hasn’t been processed

    • Finalise the shortest path to this node, and update the tentative distances of its neighbours

  • Once a node's shortest path is finalised, it cannot be improved later because

    • The shortest paths have the optimal substructure property (as long as the link costs are not negative)

  • Optimal substructure property - any sub-portion of a shortest path starting from the source is itself a shortest path

    • Example - if the shortest path from S to D is S→A→B→D then

    • S→A→B is the shortest path from S to B

    • S→A is the shortest path from S to A

Algorithm Complexity - n Nodes

  • Each of n iteration - need to check all nodes w not in N

  • n(n+1)/2 comparisons: O(n^2) complexity

  • More efficient implementations possible: O(nlog(n))

Message Complexity

  • Each router must broadcast its link state information to other n routers

  • Efficient broadcast algorithms - O(n) link crossings to disseminate a broadcast message from one source

  • Each router’s message crosses O(n) links - overall message complexity - O(n^2)

Oscillations Possible

  • When link costs depend on traffic volume, route oscillations possible

  • Sample scenario:

    • Routing to destination a, traffic entering at d, c, e with rates 1, e (<1), 1

    • Link costs are directional, and volume-dependent

Making Routing Scalable

Our routing study thus far - idealized

  • All routers identical

  • Network “flat”

  • … Not true in practice

  • Scale - billions of destinations

    • Can’t store all destinations in routing tables

    • Routing table exchange would swamp links

Internet Approach

Aggregate routers into regions known as “autonomous systems” (AS) (a.k.a. “domains”)

Intra-AS (aka “intra-domain”)

Routing among routers within same AS (“network”)

  • All outers in AS must run same intradomain protocol

  • Routers in different AS can run different intra-domain routing protocols

  • Gateway router: at “edge” of its own AS, has link(s) to router(s) in other AS’es

Inter-AS (aka “inter-domain”)

Routing among AS’es

  • Gateways perform inter-domain routing (as well as intra-domain routing)

Interconnected ASes

Forwarding table configured by intra- and inter-AS routing algorithms

  • Intra-AS routing determine entries for destinations within AS

  • Inter-AS & intra-AS determine entries for external destinations

Intra-AS routing - routing within an AS

Most common intra-AS routing protocols:

  • RIP - Routing Information Protocol [RFC 1723]

    • Classic DV - DVs exchanged every 30 secs

    • No longer widely used

  • EIGRP - Enhanced Interior Gateway Routing Protocol

    • DV based

    • Formerly Cisco-proprietary for decades (became open in 2013 [RFC 7868])

  • OSPF - Open Shortest Path First [RFC 2328]

    • Link-state routing

    • IS-IS protocol (ISO standard, not RFC standard) essentially same as OSPF

OSPF (Open Shortest Path First) Routing

  • “open” - publicly available

  • Classic link-state

    • Each router floods OSPF link-state advertisements (directly over IP rather than using TCP/UDP) to all other routers in entire AS

    • Multiple link costs metrics possible: bandwidth, delay

    • Each router has full topology, uses Dijkstra’s algorithm to compute forwarding table

  • Security - all OSPF messages authenticated (to prevent malicious intrusion)

Hierarchical OSPF

Two-level hierarchy - local area, backbone

  • Link-state advertisements flooded only in area, or backbone

  • Each node has detailed area topology; only knows direction to reach other destinations