Computer Networks

Network Layer - Routing

Prof. Dr. Oliver Hahm

2024-01-12

Inter-Networking

Inter-Networking

  • In the Internet we have multiple networks using different layer 1 and 2 technologies
  • The network layer is now tasked to interconnect these networks
  • Possible scenario for Inter-Networking:

Example Scenario

Assumption

In this scenario, all communication partners have public IP addresses

  • X wants to transmit an IP packet to Y
  • \(\Rightarrow\) X needs to know the logical address, i.e., IP address, of Y
  • X applies its netmask to its own and to Y’s IP address
  • Different network IDs \(\Rightarrow\) X and Y are in different logical networks
  • \(\longrightarrow\) In this scenario we have communication across logical and physical network boundaries
  • The IP packet for Y is carried as payload inside the frame towards the router
  • It has the IP address of X as source address and the IP address of Y as destination address
  • The router receives the IP packet
    • It checks its local forwarding table to find the correct interface to forward the packet
    • The forwarding table contains information about all logical networks the router is connected to
  • The router is connected via one of its NICs with the physical network, to which Y is connected
  • The router finds out the MAC address of Y via address resolution with ARP
  • The Router encapsulates the IP packet into a frame
    • The sender address field contains the MAC address of the Router
    • The destination address field contains the MAC address of Y
  • Maybe the Maximum Transmission Unit of network B is smaller than of network A
  • \(\Longrightarrow\) depending on the size of the forwarded IP packet, that the router fragments the packet
  • The IP addresses of the sender (X) and the receiver (Y) in the IP packet are not modified during the transmission

Autonomous Systems

  • The Internet consists of a large number of Autonomous Systems (AS)
  • The AS are interconnected via routers that are called gateways
  • Each AS consists of a group of logical networks, which…
    • are operated and managed by the same organization (e.g., an Internet Service Provider, a corporation or university)
    • use the same routing protocol, which is called the Interior Gateway Protocol (IGP) or Intra-Domain Routing Protocol
  • The routing between the various AS uses an Exterior Gateway Protocol (EGP) or Inter-Domain Routing Protocol

Autonomous Systems Number (ASN)

  • Each AS has a unique Autonomous System Number (ASN)
  • The ASNs are assigned by the IANA in blocks to the Regional Internet Registries (RIRs)
  • The RIRs assign ASNs to entities inside their areas

Map of the Internet in 2017

  • Shows the IPv4 AS of the Internet
  • Various variations of Internet maps are available

Source: https://www.caida.org/projects/cartography/as-core/2017/

Explanation of the author “The CAIDA AS Core visualization depicts the Internet’s Autonomous Systems’ (ASes) geographic locations, number of customers, and interconnections. Each AS approximately corresponds to an Internet Service Provider (ISP). The geographic location of the individual AS is inferred from the weighted centroid of its address space according to NetAcuity, a commercial geolocation service. The number of direct or indirect customers of an ASA is inferred using its customer cone.”

Routing vs. Forwarding

  • Routing describes the path determination in a network
    • It is a distributed process among routers in the network
    • Based on the topology detection and path finding
    • As auxiliary tables routers usually use Routing Information Bases (RIBs)
  • Forwarding describes the forwarding of packets
    • A local process on one host
    • Incoming packets will be passed to the outgoing port
    • The forwarding happens based on forwarding tables
    • These tables, the Forwarding Information Bases (FIBs) are results from a local routing decision

You can check your local FIB using the command netstat -r (Windows and Linux) or ip route show (Linux only).

Routing Schemes

Routing Schemes

  • Static routing tables are not flexible enough for the rapidly changing topologies of the Internet

  • A routing scheme monitors and exchanges network topology information between routers to allow correct forwarding decisions on each router

  • These protocols base on adequate routing algorithms that update the local forwarding tables

Requirements for a routing scheme

  • Scalability
  • Low overhead (local and network resources)
  • Fault-tolerance
  • Loop freedom

Routing Algorithms

Local Routing Algorithms

How to make local routing decisions?

  • Flooding
    • epidemic principle: each router forwards each packet on all its interfaces (except the one where it was received on)
    • Advantage: very simple and safe against router failures
    • Drawbacks: tremendous overhead, requires loop detection to avoid broadcast storms
  • Hot Potato
    • Each router immediately forwards any packet on the next available port
    • Advantage: simple, very fast, reduces traffic load on the local network
    • Drawback: inefficient

Source Routing vs. Hop-by-Hop Routing

Who decides which path to take?

  • Source routing
    • The path is specified by the source node
    • Whole path is included in each packet
    • Advantage: intermediate routers do not need state
    • Drawback: no fault tolerance if a downstream router/link breaks

  • Hop-by-hop routing

    • The path is determined by each intermediate router

    • Advantage: fault tolerance if a downstream router/link breaks

    • Drawback: Additional effort per router

Reactive vs. Proactive Routing

When do search the path?

  • Reactive routing
    • A path is discovered and maintained only on demand
    • Advantage: less control overhead
    • Drawback: path acquisition delay, user data buffering needed
  • Proactive routing
    • All possible paths are discovered and maintained in advance
    • Advantage: no path acquisition delay, no user data buffering needed
    • Drawback: overhead due to control traffic

Routing Metrics

  • How do determine the best path?
  • How to compare the alternatives?
  • The routing protocol defines the costs per link:
    the routing metric
  • Typical routing metrics are:
    • Hop count
    • Maximum throughput
    • Latency
    • Link quality (e.g., ETX (Estimated Transmission Count))
    • Energy resources
    • …

Distance Vector Routing

Distance Vector Routing

  • Goal: Each router maintains a list of cheapest paths for each possible destination
  • Each router periodically disseminates its forwarding table to its direct neighbors
  • If received information contains a path to a new destination or a cheaper path to a known destination, the router updates its own forwarding table
  • Implement the Bellman-Ford algorithm

Bellman-Ford Algorithm

  • Initialization of the tables:
    Hop\(_{ij} \longleftarrow\) ?
    Metric\(_{ij} \longleftarrow\infty\) for \(i\neq j\)
    Hop\(_{ij} \longleftarrow\) R\(_{i}\)
    Metric\(_{ij} \longleftarrow 0\) for \(i=j\)

  • For each direct neighbor R\(_{j}\) of R\(_{i}\) this information is stored:
    Hop\(_{ij} \longleftarrow\) R\(_{j}\)
    Metric\(_{ij} \longleftarrow\) Distance\((R_{i},R_{j} )\)

  • Each direct neighbor R\(_{j}\) of R\(_{i}\) sends his routing table to R\(_{i}\)

  • For each table entry to R\(_{k}\) it is verified if Metric\(_{ij}\ +\) Metric\(_{jk}<\) Metric\(_{ik}\)

  • If this is true, these assignments are made:
    Hop\(_{ik} \longleftarrow\) R\(_{j}\) and
    Metric\(_{ik} \longleftarrow\) Metric\(_{ij}\ +\) Metric\(_{jk}\)

Distance Vector Routing Protocol – Example

  • Initialize tables
  • Store distances to the direct neighbors
  • Compare each entry in the local routing table with the tables of the direct neighbors and adjust table entries when necessary
  • State of convergence is reached!

Source: Jörg Roth. Prüfungstrainer Rechnernetze: Aufgaben und Lösungen. Vieweg (2010)

Count-to-Infinity Problem

  • Drawback of the algorithm
    • Slow propagation of bad news
  • Example:

  • With each advertisement round the distance values (route and cost) to router A are propagated more and more

    • The table contains the stored distance to router R\(_{A}\) inside the routing tables of R\(_{A}\), R\(_{B}\) and R\(_{C}\)
A B C
0 \(\infty\) \(\infty\) Initial record
0 1 \(\infty\) After advertisement round 1
0 1 2 After advertisement round 2
⋮ ⋮ ⋮ ⋮
A B C
0 1 2 Initial record
0 3 2 After advertisement round 1
0 3 4 After advertisement round 2
0 5 4 After advertisement round 3
0 5 6 After advertisement round 4
0 7 6 After advertisement round 5
0 7 8 After advertisement round 6
0 9 8 After advertisement round 7
0 9 10 After advertisement round 8
0 11 10 After advertisement round 9
0 11 12 After advertisement round 10
0 13 12 After advertisement round 11
0 13 14 After advertisement round 12
0 15 14 After advertisement round 13
0 15 \(\infty\) After advertisement round 14
0 \(\infty\) \(\infty\) After advertisement round 15

\(\Longrightarrow\) Count-to-Infinity

  • Scenario: The link to router A fails

  • During advertisement round 1, R\(_{B}\) gets no more information from R\(_{A}\) and supposes that the best path to reach R\(_{A}\) is via R\(_{C}\)

  • During advertisement round 2, R\(_{C}\) receives the information that its neighbor R\(_{B}\) can reach R\(_{A}\) with 3 hops and therefore it stores hop count value 4 in its local routing table

  • …

Count-to-Infinity Countermeasures

  • Distance Vector Routing protocols typically define a finite value as \(\infty\)
  • However, still a lot of time may be wasted until the inaccessibility of a route is detected

Calculation

  • Advertisement messages are exchanged every 30 s.
  • \(\infty\) is defined as 15

\(\Rightarrow\) Without triggered updates, it may take up to \(15*30\) s = 7:30 minutes until a network failure between 2 routers is detected and the affected routes get marked as not available in the routing tables

Split Horizon

  • Solution in some use cases: Split Horizon
  • A routing information must not be published via the port through which it was received
    • This prevents a router from transmitting back a routing information to the router, from which it learned the route
  • In order to implement Split Horizon, not only the hop count and the address of the next router (next hop) needs to be recorded in the routing table for every destination network, but also the information from which router (port) the information was received

Split Horizon – Example

  • R\(_{c}\) learned from R\(_{B}\) that R\(_{A}\) can be reached via R\(_{B}\)
  • Scenario: R\(_{A}\) cannot be reached any more

  • Effect of split horizon:
    • R\(_{B}\) informs with its next advertisement to R\(_{C}\) that R\(_{A}\) is not reachable any more
    • R\(_{C}\) modifies its routing table and neither now nor in the future sends routing information for R\(_{A}\) to R\(_{B}\)
  • Problem: Split horizon fails in many cases \(\rightarrow\) Poison Reversed can be used to mark this path as non reachable in the reverse direction

Routing Information Protocol (RIP)

  • The first IGP used in the Internet
  • Specified in RFC 1058
  • Proactive algorithm
  • Functioning of RIP:
    • RIP messages are exchanged every 30 seconds as UDP datagrams between neighbors
    • Used metric is hop count
    • The maximum number of hops is limited to 15 (\(\infty\) := 16)
    • In a message (only) up to 25 entries of the routing table can be sent
  • RIPv2
    • Specified in RFC 2453
    • Support for subnets, CIDR, authentication, multicast, etc.
  • RIPng adds support for IPv6

RIP – Conclusion

  • RIPv1 (RFC 1058) was developed and became established at a time, when computer networks were relatively small
    • RIPv1 only supports network classes and no subnets
  • When RIPv1 was developed, computer networks contained seldom different transmission media with significant differences regarding connection quality and transmission rate

  • Today, the hop count metric often results in routes, which are not optimal, because all network segments have an equal weight

Open Shortest Path First (OSPF)

  • Allows routing inside autonomous systems (Intra-AS routing)

  • OSPF messages are transmitted directly, without a Transport Layer protocol, in the payload section of IPv4 packets

    • In the header of the IPv4 packet, the field protocol ID contains value 89

  • The functioning of OSPF is complicated compared with RIP

    • RFC 2328 contains a detailed description of the protocol :::

Constructing Routing Hierarchies with OSPF

  • Big difference compared to RIP:
    • With OSPF, routing hierarchies can be created
  • For this, autonomous systems are split into areas
    • Each area consists of a group of routers
    • Each area is invisible for other areas of the autonomous system
    • Each router can be assigned to multiple areas
  • An advantage, which results from routing hierarchies:
    • Better scalability
    • Improved security

Helpful OSPF resources Ethernet, Jörg Rech, Heise (2008)
Computernetzwerke, James F. Kurose, Keith W. Ross, Pearson (2008)
TCP/IP, Gerhard Lienemann, Dirk Larisch, Heise (2011)

OSPF is far more complex compared with RIP and it will not be discussed in this course in detail

Dijkstra Algorithm

  • Calculates the shortest path between a start node (initial node) and all other nodes in an edge-weighted graph
  • Steps:
    1. Assign to every node the properties distance and predecessor
      • Set the distance to \(0\) for the initial node and to \(\infty\) for all other nodes
    2. As long as there are unvisited nodes, select the node with the minimal distance
      • Mark the node as visited
      • Compute for all unvisited neighbors, the sum of the edge weights via the current node
      • If this value is smaller than the stored distance for a node, update the distance and set the current node as predecessor

If only the path to a specific node needs to be determined, the algorithm can stop during step 2, if the requested node is the active one

Dijkstra Algorithm – Example

  • Step 1: Initialize with 0 and \(\infty\)
    • A is the starting node
    • A has the minimum distance
  • Nodes visited = \(\{\)\(\}\)
  • Shortest paths = \(\{\)\(\}\)

  • Step 2: Calculate the sum of the edge weights
    • B has the minimum distance
  • Nodes visited = \(\{\)A\(\}\)
  • Shortest paths = \(\{\)A\(\}\)

  • Step 3: Visit node B
    • No change to C
    • C has the minimum distance
  • Nodes visited = \(\{\)A, B\(\}\)
  • Shortest paths = \(\{\)A, A\(\rightarrow\)B\(\}\)

  • Step 4: Visit node C
    • No change to B
    • Change to D (path via C is shorter than the direct path)
    • D has the minimum distance
  • Nodes visited = \(\{\)A, B, C\(\}\)
  • Shortest paths = \(\{\)A, A\(\rightarrow\)B, A\(\rightarrow\)C\(\}\)

  • Step 5: Visit node D
    • No change to C
    • No change to E
    • E has the minimum distance
  • Nodes visited = \(\{\)A, B, C, D\(\}\)
  • Shortest paths = \(\{\)A, A\(\rightarrow\)B, A\(\rightarrow\)C, C\(\rightarrow\)D\(\}\)

  • Step 6: Visit node E
    • No change to D
    • Change to F (path via E is shorter than the direct path)
    • F has the minimum distance
  • Nodes visited = \(\{\)A, B, C, D, E\(\}\)
  • Shortest paths = \(\{\)A, A\(\rightarrow\)B, A\(\rightarrow\)C, C\(\rightarrow\)D, A\(\rightarrow\)E\(\}\)

  • Step 7: Visit node F
    • No change to E
  • Nodes visited = \(\{\)A, B, C, D, E, F\(\}\)
  • Shortest paths = \(\{\)A, A\(\rightarrow\)B, A\(\rightarrow\)C, C\(\rightarrow\)D, A\(\rightarrow\)E, E\(\rightarrow\)F\(\}\)

  • Result: Shortest path spanning tree
Distance
d\(_{A}\) = 0
d\(_{B}\) = \(\infty\)
d\(_{C}\) = \(\infty\)
d\(_{D}\) = \(\infty\)
d\(_{E}\) = \(\infty\)
d\(_{F}\) = \(\infty\)
Distance
d\(_{A}\) = 0 visited
d\(_{B}\) = 1 \(\leftarrow\) minimum distance
d\(_{C}\) = 2
d\(_{D}\) = 4
d\(_{E}\) = 4
d\(_{F}\) = 6
Distance
d\(_{A}\) = 0 visited
d\(_{B}\) = 1 visited
d\(_{C}\) = 2 \(\leftarrow\) minimum distance
d\(_{D}\) = 4
d\(_{E}\) = 4
d\(_{F}\) = 6
Distance
d\(_{A}\) = 0 visited
d\(_{B}\) = 1 visited
d\(_{C}\) = 2 visited
d\(_{D}\) = 3 \(\leftarrow\) minimum distance
d\(_{E}\) = 4
d\(_{F}\) = 6
Distance
d\(_{A}\) = 0 visited
d\(_{B}\) = 1 visited
d\(_{C}\) = 2 visited
d\(_{D}\) = 3 visited
d\(_{E}\) = 4 \(\leftarrow\) minimum distance
d\(_{F}\) = 6
Distance
d\(_{A}\) = 0 visited
d\(_{B}\) = 1 visited
d\(_{C}\) = 2 visited
d\(_{D}\) = 3 visited
d\(_{E}\) = 4 visited
d\(_{F}\) = 5 \(\leftarrow\) minimum distance
Distance
d\(_{A}\) = 0 visited
d\(_{B}\) = 1 visited
d\(_{C}\) = 2 visited
d\(_{D}\) = 3 visited
d\(_{E}\) = 4 visited
d\(_{F}\) = 5 visited

More Routing Protocols

Intermediate System to Intermediate System (IS-IS)

  • Standardized in the context of OSI for the connectionless layer 3 protocol
  • Republished by IETF as RFC 1142
  • Very similar to OSPF, proactive link-state protocol
  • Neutral to layer 3 protocol \(\rightarrow\) faster support for IPv6 in IS-IS in contrast to OSPF
  • Routers also build a map of the network, calculate shortest path
  • Lower overhead compared to OSPF
  • Often used by network operators with large networks in terms number of routers

Border Gateway Protocol (BGP)

  • Specified by IETF in RFCs 1771 – 1773, BGP4 specified in RFC 4271
  • Currently the most common inter-domain routing protocol
  • A path vector protocol (different from distance vector or link-state)
  • BGP routers exchange path vectors with BGP neighbors (peers)
  • Typically neighbors are connected directly or via a switch
  • BGP peers accept or discard paths based on policies (e.g., shortest path, preferred neighbors, hot potato or cold potato)
  • BGP router decide based on policies which advertisements to send

BGP – Path Vector Routing

  • BGP router discover AS paths to the prefixes of their neighbors \(\rightarrow\) their BGP peers
  • Theses paths are stored in a table: the BGP RIB
    • This may include redundant paths
  • BGP defines a default-free zone \(\Rightarrow\) all participating routers must provide a complete RIB \(\Rightarrow\) no default route
  • Example:

BGP Selection Criteria

BGP router have to select paths and make forwarding decisions:

  1. Preference

    • Assign all RIB entries a preference - based on local policies and attributes

  2. Route Selection

    • For each prefix the router selects based on the following criteria:
      1. Highest preference
      2. Shortest path
      3. Additional tie breaker rules
    • Selected routes are put into the FIB

  3. Route Forwarding

    • Before the propagation of the FIB entries these are filtered according to the policies

Routing Protocol for Low power, Lossy Networks (RPL)

  • Specified by IETF RFC 6550
  • Developed for resource-constrained node networks with lossy links
  • Based on distance vector, proactive, tree-based
  • Support for hop-by-hop and source routing to accommodate lack of memory
  • Assumption on data traffic \(\rightarrow\) mainly convergecast towards a sink
  • Use of flexible Objective Function (OF) as metric
  • P2P-RPL: extension to allow paths across the tree (see RFC 6997)

Summary

You should now be able to answer the following questions:

  • What is the difference between routing and forwarding?
  • What are routing metrics?
  • Which different types of routing protocols do exist?
  • How is the Internet structured and which purposes are fulfilled with IGP and EGP?
  • Which algorithm is implemented in a Distance Vector Routing and how does it work?
  • Which algorithm is implemented in a Link State Routing and how does it work?

Computer Networks - Network Layer - Routing - WS 23/24