Computer Networks - Routing and Routing Protocols

Why Routing and Routing Protocols?

  1. Routing is the underlying mechanism of the Internet, essential for transferring data across global distances and disparate networks. It ensures that data packets reach their intended destinations efficiently and reliably.

  2. Theory: Key functional and performance aspects of contemporary networks depend on routing functions. Understanding routing algorithms and protocols is crucial for optimizing network performance, minimizing latency, and ensuring efficient resource utilization.

  3. Practice: Designing and coding performance-sensitive networked applications requires understanding routing. Knowledge of routing principles enables developers to create applications that can adapt to network conditions, optimize data transfer, and provide a seamless user experience.

  4. Practice: Managing any network requires understanding routing. Network administrators need to understand routing protocols, configure routing devices, and troubleshoot routing issues to maintain network stability and performance.

OSI Context

The lecture goes over the OSI and TCP/IP models and the datalink MAC sublayer.

OSI and TCP/IP Models

The OSI model consists of seven layers: Application, Presentation, Session, Transport, Network, Data Link, and Physical. The TCP/IP model consists of four layers: Application, Transport, Internet, and Link. The presentation and session layers are not present in the TCP/IP model. The IEEE 802 reference model includes Logical Link Control (LLC) and Medium Access Control (MAC) sublayers within the Data Link layer.

Network / Internet Layer

The structure of a packet is as follows: MAC header, LLC header, IP header, TCP header, Application data, TCP trailer, IP datagram, LLC protocol data unit, and MAC frame.

OSI Context - Protocols

Protocols in context: MIME, BGP, FTP, HTTP, SMTP, TELNET, SNMP, TCP, IP, UDP, ICMP, IGMP, OSPF, RSVP.

Routing and Routing Protocols

Routing entails route discovery and route management. Routing protocols are used to implement routing. Routing protocols define the rules and procedures for exchanging routing information, determining the optimal paths, and adapting to network changes.

Route Discovery versus Management

Route discovery: Finding the most suitable route from source to destination (usually lowest latency). Route discovery algorithms explore the network topology to identify the best path based on various metrics such as distance, bandwidth, and congestion.

Route management: Monitoring route status to deal with congestion, degraded links, or broken links. Route management mechanisms continuously monitor the network conditions and dynamically adjust routing paths to maintain connectivity and performance.

Excessive router workload leads to queuing delays and increased latency. Link dropouts are common in wireless links. Effective route management strategies are essential for mitigating the impact of network congestion and link failures.

Packet Switching Networks

Store-and-forward packet switching involves routers forwarding packets. A packet travels from Host H1 through routers (ISP's equipment) to Host H2. Routers examine the destination address in each packet and forward it to the next hop along the optimal path.

Transport Layer Services

Services are independent of router technology. The transport layer is shielded from the number, type, and topology of routers. Network addresses use a uniform numbering plan across LANs and WANs. The transport layer provides reliable end-to-end communication between applications, regardless of the underlying network infrastructure.

Implementation of Connectionless Service (Datagram)

In a datagram network, each packet contains the full source and destination address. Routers do not hold state information about connections. Each packet is routed independently. Datagram networks offer flexibility and scalability, but they may experience higher latency and packet loss compared to connection-oriented networks.

Implementation of Connection-Oriented Service (Virtual Circuit)

In a virtual-circuit network, each packet contains a short VC number. Each VC requires router table space per connection. The route is chosen when the VC is set up, and all packets follow it. Virtual-circuit networks provide guaranteed bandwidth and low latency, but they require more overhead for connection setup and maintenance.

Comparison of Virtual-Circuit and Datagram Networks

Routing Algorithms

Objective: Find the best-performing path (lowest end-to-end latency).

Latency depends on:

A. Channel throughput (Megabits/s or Gigabits/s)

B. Router packet transfer throughput (packets/s)

C. Traffic load on a routing node (queuing theory models can estimate latency)

D. Error rates and packet losses (retry attempts increase latency)

Routing algorithms use metrics like "cost" to model latency.

Real-world latency depends strongly on traffic load. Advanced routing algorithms consider real-time traffic conditions and dynamically adjust paths to minimize latency and avoid congestion.

Routing Algorithms in a Single Network

Algorithms include:

  • Optimality principle

  • Shortest path algorithm

  • Flooding (DSR / Dynamic Source Routing Protocol)

  • Distance vector routing (RIP / Routing Information Protocol, Cisco’s IGRP/Interior Gateway Routing Protocol) - Bellman-Ford Algorithm

  • Link state routing (OSPF / Open Shortest Path First)

  • Hierarchical routing within a network

  • Broadcast routing

  • Multicast routing

  • Anycast routing

The Optimality Principle

If router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route. A sink tree (DAG) for router B (Bellman) is a visual representation of this principle, showing all the optimal routes from router B to all other routers in the network.

Shortest Path Algorithm

Compute the shortest path from A to D. Metrics: physical distance or hop count?

Dijkstra’s algorithm computes the shortest path through a graph. Dijkstra's algorithm is a widely used algorithm for finding the shortest path between nodes in a graph, with applications in network routing, transportation planning, and resource allocation.

Distance Vector Routing

Each router maintains a table (vector) with the best-known distance to each destination and the link to use. Tables are updated by exchanging information with neighbors.

Also known as the distributed Bellman-Ford routing algorithm.

Used in the original ARPANET and the Internet (RIP). Distance vector routing is a simple and distributed routing algorithm that relies on exchanging distance vectors between neighboring routers to determine the shortest paths.

Convergence Failure - The Count-to-Infinity Problem

This occurs when routing loops form, and distance vectors increase indefinitely as routers exchange information about unreachable destinations. This issue motivated a transition from distance vector to link-state routing in the ARPANET. The count-to-infinity problem is a major limitation of distance vector routing, which can lead to routing instability and network congestion.

Link State Routing

Each router:

  1. Discovers its neighbors and learns their network addresses.

  2. Sets the distance/cost metric to each neighbor (e.g., echo).

  3. Constructs a packet telling all it has just learned.

  4. Sends this packet to and receives packets from all other routers (e.g., flooding).

  5. Computes the shortest path to every other router (Dijkstra).

Complete topology distributed to every router.

Variants IS-IS and OSPF are widely used inside large networks and the Internet. Link-state routing is a more sophisticated routing algorithm that provides faster convergence, better scalability, and improved reliability compared to distance vector routing.

Learning about the Neighbors

Routers use hello packets to discover neighbors on a broadcast LAN. A graph model represents the network. Hello packets are small control packets that are periodically exchanged between neighboring routers to establish and maintain adjacencies.

Building Link State Packets

Each router creates a link-state packet (LSP) containing information about its neighbors and the cost to reach them. These packets include sequence numbers and ages to ensure they are up-to-date. Link-state packets are used to disseminate information about the network topology and link costs to all routers in the network.

Distributing the Link State Packets

LSPs are distributed through flooding. Each router maintains a packet buffer to track which LSPs it has sent and received to avoid infinite loops. Flooding ensures that all routers in the network receive the latest link-state information, allowing them to construct an accurate view of the network topology.

Hierarchical Routing within a Network

Routing is organized hierarchically to reduce table size. Full tables exist for local regions; hierarchical tables aggregate information about distant regions. Hierarchical routing improves scalability and reduces routing overhead by organizing the network into a hierarchy of routing domains.

Broadcast Routing – All Nodes in Network

Reverse path forwarding is used. The router sends a received message out on all its ports except the one on which it was received. This creates a sink tree. Broadcast routing is used to transmit a message to all nodes in the network, typically for control and management purposes.

Multicast Routing

Multicast involves sending to a group of nodes. Spanning trees and multicast trees are used to efficiently route traffic to group members. Core-based trees are also used. Multicast routing enables efficient delivery of data to a subset of nodes in the network, reducing bandwidth consumption and improving network performance.

Routing Protocols - OSPF

  • Intradomain routing – IGP (Interior Gateway Protocols)

  • RIP (Routing Information Protocol) – Works well in small systems

  • OSPF (Open Shortest Path First) – Widely used in company / organization networks

  • IS-IS (Intermediate-System to Intermediate-System) – Widely used in ISP networks

OSPF—An Interior Gateway Routing Protocol

OSPF supports:

  • Variety of distance metrics

  • Dynamic routing

  • Routing based on type of service

  • Load balancing

  • Hierarchical systems

  • Security

  • Dealing with routers connected via a tunnel

  • Multiaccess networks

OSPF Areas

Autonomous systems (ASes) are divided into areas. Area 0 is the backbone area. Area border routers connect areas to the backbone. Internal routers reside within an area. AS boundary routers connect to other ASes. OSPF areas provide a hierarchical routing structure that improves scalability and reduces routing overhead in large networks.

OSPF Message Types

  • Hello: Used to discover neighbors.

  • Link state update: Provides sender's costs to neighbors.

  • Link state ack: Acknowledges link state update.

  • Database description: Announces which updates the sender has.

  • Link state request: Requests information from the partner.

Open Shortest Path First - Stallings

  • IGP of Internet

  • Replaced Routing Information Protocol (RIP)

  • Uses Link State Routing Algorithm

  • Each router keeps a list of the state of local links to the network.

  • Transmits update state info

  • Little traffic as messages are small and not sent often

  • Defined in RFC 2328

  • Route computed on least cost based on user cost metric

Topology is stored as a directed graph with vertices (routers and networks - transit, stub) and edges (connections between routers or router to network).

Routing Protocols - BGP

  • For use with TCP/IP internets

  • Preferred EGP of the Internet

  • Messages sent over TCP connections (Open, Update, Keep alive, Notification)

  • Procedures: Neighbor acquisition, Neighbor reachability, Network reachability

BGP Routing Information Exchange - Stallings

Within an AS, a router builds a topology picture using IGP. The router issues an Update message to other routers outside the AS using BGP. Routers exchange info with other routers in other AS and then decide best routes.

BGP Messages – Stallings

Border Gateway Protocol (BGP) messages:

  • Open message

  • Update message

  • Keepalive message

  • Notification message

BGP—The Exterior Gateway Routing Protocol

Routing constraints include:

a. Do not carry commercial traffic on the educational network

b. Never send traffic from government sites on a route through a foreign country

c. Use TeliaSonera instead of Verizon because it is cheaper

d. Don’t use AT&T in Australia because performance is poor

e. Traffic starting or ending at Apple should not transit Google

BGP advertisements propagate through autonomous systems (AS). Routing policies can be Transit (TR), Customer (CU), or Peer (PE). BGP is a path vector protocol that enables autonomous systems to exchange routing information and make routing decisions based on policies and preferences.

Interdomain Traffic Engineering

Tuning parameters and configuration network protocols to manage utilization and congestion. Includes inbound and outbound traffic engineering. Strategies include setting local preference, AS path prepending, leveraging longest prefix match, and splitting prefixes. Interdomain traffic engineering techniques optimize traffic flow across autonomous systems, improving network performance and reducing congestion.

Internet Multicasting

One-to-many communication using class D IP addresses. Each class D address identifies a group of hosts (over 250 million groups). Packets are delivered on a best-effort basis. Internet multicasting enables efficient delivery of content to a large number of recipients, reducing bandwidth consumption and improving scalability.

Policy at the Network Layer

Peering disputes, traffic prioritization. Generally agreed upon bright-line rules include no blocking, no throttling, no paid prioritization, and disclosure of any prioritization practices. Network layer policies govern how traffic is handled and prioritized, ensuring fair access and preventing discriminatory practices.

Ad Hoc Routing Protocols

In an Ad Hoc network, every node carries its own router, and all nodes cooperate in carrying traffic. This differs from the structured, hierarchical models of traditional networks. Routing is performed by the network in infrastructure networks, whereas in ad hoc networks, nodes perform routing. Ad hoc routing protocols enable mobile devices to form self-organizing networks without relying on a fixed infrastructure.

Ad Hoc Routing Protocols

Ad Hoc networks are highly time-variant in topology. They can be wireless radio networks between vehicles, ships, aircraft, or people on foot, operating in a geographical area with no networking infrastructure. Examples are “hot spot” networks, vehicular networks, and some types of IoT network. Ad hoc networks are characterized by their dynamic topology, limited bandwidth, and energy constraints.

Ad Hoc Network Examples - Suburban and Vehicular

Wireless links connect mobile ad-hoc networks enabling self-organizing, self-healing, redundant, and resilient networks. Students and staff can connect around a university campus using this type of network. Vehicular ad hoc networks (VANETs) enable vehicles to communicate with each other and with roadside infrastructure, improving safety, traffic efficiency, and infotainment services.

Ad hoc On-Demand Distance Vector (AODV) Routing Protocol

  • AODV is intended for use by mobile nodes in an ad hoc network.

  • Offers quick adaptation to dynamic link conditions, low processing and memory overhead, low network utilization, and determines unicast routes to destinations within the ad hoc network.

  • It uses destination sequence numbers to ensure loop freedom at all times

  • Adaptation of Bellman-Ford algorithm for Ad Hoc networks

Dynamic Source Routing protocol (DSR)

  • DSR is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes.

  • DSR allows the network to be completely self-organizing and self-configuring, without the need for any existing network infrastructure or administration.

  • Adaptation of flooding algorithm for Ad Hoc networks

Bellman-Ford Algorithm

  • Determine the shortest path to a destination node by calculating the cost to the destination through each of its neighbors and then picking the minimum.

  • Iterative approach.

  • Algorithm:

    • d_i - Current estimation of the minimum cost from node i to the destination.

    • c_{ij} - Link cost from node i to j.

    • d - Destination node

    • Step 1: Initialization: di = \infty for all nodes except the destination node, where dd = 0

    • Step 2: Updating: d*i = \minj [c{ij} + d_j]

    • Step 3: Repeat step 2 to until no more changes.

Bellman-Ford Algorithm Example

Using an iteratively updated table, the algorithm determines a lowest cost and outgoing node using previously calculated information.

Bellman-Ford Algorithm - Distance Vector Routing

  • Asynchronous, real-time distributed implementation.

  • Each node independently computes its minimum cost to each destination and periodically broadcast the vector of minimum costs to its neighbors.

  • Nodes do not need the information of network topology.

  • Also known as “Distance Vector Routing” protocol.

  • Each node i computes the following equation. di = \minj [c{ij} + dj]

  • Upon updating, node i broadcasts the vector

  • In Distance Vector, hop-count and line delay are often used as metrics. They can be measured relatively easily.

Distance Vector Routing: Example

The distance vector published by A, I, H, K to J is used to calculate J's new distance vector and routing table:

Dijkstra’s Algorithm

  • D(i) - Current minimum cost from source node (s) to node i.

  • c(i,j) - Link cost from node i to j.

  • N - Set of nodes whose shortest paths have been determined.

    • Step 1: Initialization:

      • N = {s}

      • D(i) = c(s, i) for all nodes i directly connected to s;

      • D(i) = \infty for all other nodes i.

    • Step 2: Finding the next closest node.

      • Find node w not in N such that D(w) is minimum.

      • Add w to N. If N contains all the nodes, stop.

    • Step 3: Update the minimum cost after node i added to N.

      • D(i) = \min [D(i), D(w) + c(w, i)] for all i not in N.

    • Go to step 2.

Link State Routing Steps

Steps involved in Link State Routing:

  1. Meeting Neighbors.

  2. Measuring Link Costs.

  3. Constructing Link State Advertisement packet (LSA).

  4. Distributing LSA. ◄◄◄◄ bandwidth consuming

  5. Computing Routes. ◄◄◄◄◄ time consuming

Link State Routing: Meeting Neighbors

Neighbor discovery involves a router transmitting a HELLO packet to each of its neighbors. The neighbors then identify themselves to the router.

Link State Routing: Measuring Link Costs

Link cost measurement involves a router transmitting an ECHO packet to each of its neighbors. The neighbors then return the received ECHO.

Link State Routing: Distributing LSA

LSAs are distributed based on flooding routing.

Two more fields are added into each LSA to avoid issues:

  1. Sequence number.

  2. Age.

Link State Routing: Computing Routes

An example is given of shortest route computed from a diagram.