Routing

Introduction to Networks and Security

  • Instructor: Alireza Esfahani
    • Qualifications: BSc, MSc, PhD, FHEA, M IEEE, M ECSO
    • Position: Senior Lecturer in Cyber Security, Cyber Security Course Leader
    • Institution: School of Engineering and Computing, University of West London

Module Content Schedule

  • Week 1 (12 Feb): Networking Fundamentals
  • Week 2 (19 Feb): Network and Internet Protocol
  • Week 3 (26 Feb): IP Communication
  • Week 4 (5 Mar): Internet Layer
  • Week 5 (12 Mar): Internet Layer - Routing
  • Week 6 (19 Mar): Transport Layer
  • Week 7 (26 Mar): Security Protocols, Firewalls
  • Spring Break
  • Week 8 (9 Apr): VPN, and IDS
  • Week 9 (16 Apr): Wireless and Mobile Networks
  • Week 10 (23 Apr): Complementary session (IoT)
  • Week 11 (30 Apr): Revision
  • Week 12 (7 May): In-class Test (CP50088 @ 2025-26)

Week 5: Internet Layer - Routing

  • Lecture slides adapted from:
    • Textbook: "Computer Networking: A Top-Down Approach, 8th edition" by Jim Kurose and Keith Ross, Pearson, 2020
  • Today's Agenda:
    • Routing Protocols
    • Link State & Distance Vector
    • Protocols: RIP, OSPF, and BGP

Routing

Network-layer functions

  • Control Plane Structuring Approaches:
    • Per-router Control (traditional)
    • Logically Centralized Control (software-defined networking)
  • Key Functions:
    • Forwarding: Movement of packets from a router’s input to appropriate output
    • Routing: Determining the route taken by packets from source to destination

Routing Protocols

  • Link State
    • Each router constructs a complete map of the network topology
    • Utilizes Dijkstra's Algorithm to compute the shortest path to all destinations
  • Distance Vector
    • Routers share distance information only with neighbors
    • Employs Bellman-Ford Algorithm to determine optimal route based on hop count or other metrics

Interplay between Routing and Forwarding

  1. IP destination address found in the incoming packet’s header
  2. Routing Algorithm: Determines the end-to-end path through the network
  3. Forwarding Table: Dictates local forwarding at this router
    • Example:
    • Address-range mapping allows routers to determine next hop based on destination address

Goals of Routing Protocols

  • Aim to identify efficient paths from sending hosts to receiving hosts across networks of routers
  • Defining “good” paths:
    • Criteria:
    • Least cost
    • Fastest route
    • Least congested
  • Routing is a substantial networking challenge

Per-router Control Plane

  • Involves individual routing algorithms on every router interacting within the control plane
  • Data plane and control plane coordination illustrated

Software-Defined Networking (SDN)

  • Features a remote controller that computes and installs forwarding tables in routers

Comparison: Per-router vs. SDN Control Plane

  • Per-router Control Plane:
    • Local forwarding tables based on incoming packet headers
  • SDN Control Plane:
    • Centralized management via a remote controller

Graph Abstraction

  • Definition: Link costs represented in graph form
    • Let G = (N, E)
    • Where N: set of routers {u, v, w, x, y, z}
    • E: set of links such as {(u,v), (u,x), (v,x), etc.}
  • Link Costs:
    • Cost defined by the network operator; may vary based on bandwidth or congestion

Dijkstra’s Link-State Routing Algorithm

  • Centralized Knowledge: All nodes possess complete knowledge of network topology and link costs via “link state broadcast”
    • Computes least-cost paths starting from the source to all other nodes
    • Iteration Details:
    • After k iterations, know the least cost path to k destinations
  • Definitions:
    • Let cx,y = cost of the direct link from node x to y
    • D(v) = current estimate of cost for least-cost path from source to destination v
    • p(v) = predecessor node along the path from source to v
    • N' = set of nodes with known least-cost paths

Dijkstra’s Algorithm Steps

  1. Initialization:
    • Set N' = {u} (source node)
  2. For each node v:
    • If v is adjacent to u, set D(v) = cu,v (direct path cost)
    • If not adjacent, set D(v) = ∞
  3. Loop until all nodes in N' are identified
    • Identify the node not in N' with the minimum D value
    • Update the D(v) values for all adjacent nodes

Dijkstra’s Algorithm Examples

Example I Overview

  • Steps described for calculating least-cost paths and updating forwarding tables from the source to various destinations
  • Key Variables: Nodes, costs, and forwarding actions clearly laid out

Example II Overview

  • Further illustrate the stepwise process of computing least-cost paths under a different network configuration

Distance Vector Algorithm

  • Foundational Concept: Each node sends its distance vector estimates periodically to neighbors
    • Each node uses the Bellman-Ford equation to update its own DV estimates
  • Key Components:
    • Costs and minimum distance calculated based on neighbor data
  • Features:
    • Iterative, asynchronous updates depending on local changes or messages received

Advantages and Disadvantages of Distance Vector Algorithm

  • Advantages: Simplicity and lower overhead given limited information sharing
  • Disadvantages: Susceptibility to incorrect information propagation and longer convergence times

Overview of Routing Protocols

  • Classification and Comparison:
    • Link State vs. Distance Vector highlighted across various features such as speed, scalability, and overhead

Intra-AS vs Inter-AS Routing

Autonomous System (AS)

  • A collection of IP networks and routers governed by a single entity

Intra-AS Routing (Interior Gateway Protocols)

  • Common protocols include: RIP, OSPF, and IGRP

RIP (Routing Information Protocol)

  • Focused on hop count; maximum 15 hops allowed
Advantages
  • Easy configuration, extensive router support
Disadvantages
  • Based solely on hop count, high bandwidth usage for periodic updates

OSPF (Open Shortest Path First)

  • Publicly available, primarily utilizing a link-state algorithm with routing done via Dijkstra’s

BGP (Border Gateway Protocol)

  • The principal inter-domain routing protocol

BGP Path Advertisement

  • Description of the mechanics of BGP including eBGP and iBGP interactions

Summary

  • Topics covered include classification of routing algorithms, protocols such as OSPF and BGP, and detailed processes of routing dynamics

Questions

  • Open floor for inquiries related to materials presented or further clarification needed.