Routing Overview

anchored to 143.00_anchor

also covered in 143.03_dynamic_routing


What is meant with Routing ?

This section was taken from the - now archived - wiki from Cisco, linke here:

[!Definition] Routing Routing is the act of moving information across an internetwork from a source to a destination. Along the way, at least one intermediate node typically is encountered. Routing is often contrasted with bridging, which might seem to accomplish precisely the same thing to the casual observer. The primary difference between the two is that bridging occurs at Layer 2 (the link layer) of the OSI reference model, whereas routing occurs at Layer 3 (the network layer). This distinction provides routing and bridging with different information to use in the process of moving information from source to destination, so the two functions accomplish their tasks in different ways.

Routing involves two basic activities: determining optimal routing paths and transporting information groups (typically called packets) through an internetwork. In the context of the routing process, the latter of these is referred to as packet switching. Although packet switching is relatively straightforward, path determination can be very complex.

Path Determination

For routing and forwarding packets within a network efficiently we need means to evaluate which path to take - and which to define/consider best. This requires certain metrics to be added / defined in order to calculate the costs for different paths in the network.

[!Definition] Metrics (for graphs) #card Generally speaking a metric is nothing but a standard of measurement based on different aspects, like path bandwidth, hop count or similar.

In the context of routing within a network we establish and populate certain routing tables why? #card We use routing tables to denote the best possibility for a given router to forward packets assigned for a given subnet/address. Here each entry is denoting a path for a given subnet/host-id and further which interface and device to assign this to. Further each entry is usually the calculated minima of all possible routes --> Shortest path problems 111.22_Graphen_SSSP_dijkstra

Routing Metrics

Routing tables contain information used by switching software to select the best route. But how, specifically, are routing tables built? What is the specific nature of the information that they contain? How do routing algorithms determine that one route is preferable to others?

Routing algorithms have used many different metrics to determine the best route. Sophisticated routing algorithms can base route selection on multiple metrics, combining them in a single (hybrid) metric. All the following metrics have been used:

  • Path length
  • Reliability
  • Delay
  • Bandwidth
  • Load
  • Communication cost

Path length is the most common routing metric. Some routing protocols allow network administrators to assign arbitrary costs to each network link. In this case, path length is the sum of the costs associated with each link traversed. Other routing protocols define hop count, a metric that specifies the number of passes through internetworking products, such as routers, that a packet must take en route from a source to a destination.

Reliability, in the context of routing algorithms, refers to the dependability (usually described in terms of the bit-error rate) of each network link. Some network links might go down more often than others. After a network fails, certain network links might be repaired more easily or more quickly than other links. Any reliability factors can be taken into account in the assignment of the reliability ratings, which are arbitrary numeric values usually assigned to network links by network administrators.

Routing delay refers to the length of time required to move a packet from source to destination through the internetwork. Delay depends on many factors, including the bandwidth of intermediate network links, the port queues at each router along the way, network congestion on all intermediate network links, and the physical distance to be traveled. Because delay is a conglomeration of several important variables, it is a common and useful metric.

Bandwidth refers to the available traffic capacity of a link. All other things being equal, a 10-Mbps Ethernet link would be preferable to a 64-kbps leased line. Although bandwidth is a rating of the maximum attainable throughput on a link, routes through links with greater bandwidth do not necessarily provide better routes than routes through slower links. For example, if a faster link is busier, the actual time required to send a packet to the destination could be greater.

Load refers to the degree to which a network resource, such as a router, is busy. Load can be calculated in a variety of ways, including CPU utilization and packets processed per second. Monitoring these parameters on a continual basis can be resource-intensive itself.

Communication cost is another important metric, especially because some companies may not care about performance as much as they care about operating expenditures. Although line delay may be longer, they will send packets over their own lines rather than through the public lines that cost money for usage time.

Packet Switching

adapted from: https://archive.is/cvzE1#selection-761.321-761.403

Considering a host to send a packet to a given router - wanting it to process and forward the packet sent - this is usually done with the packet being addressed to the routers mac-address while also adding the ip-address ( so both L2 and L3!).

The Router observing this packet will check its routing table and either find a path for the given ip-address to forward the packet to or not.

If there's no route available it will be discarded by the router. And if its known how / where to send the packet it will change the physical Address (L2) and send the packet in that direction. --> I then proceeds the same until the destination was met.

[!Tip] Important observation for packet-switching what can we observe regarding the addresses? #card During the process of packet switching we can observe that the physical address is prone to change throughout the process While the ip-address (L3) stays the same and points towards the destination host.

The preceding discussion describes switching between a source and a destination end system. The International Organization for Standardization (ISO) has developed a hierarchical terminology that is useful in describing this process. Using this terminology, network devices without the capability to forward packets between subnetworks are called end systems (ESs), whereas network devices with these capabilities are called intermediate systems (ISs). ISs are further divided into those that can communicate within routing domains (intradomain ISs) and those that communicate both within and between routing domains (interdomain ISs). A routing domain generally is considered a portion of an internetwork under common administrative authority that is regulated by a particular set of administrative guidelines. Routing domains are also called autonomous systems. With certain protocols, routing domains can be divided into routing areas, but intradomain routing protocols are still used for switching both within and between areas.

Routing-Tables

Consider two systems that are spread across the globe: They would like to exchange packets from a to b now which is going to take resources where they have to jump between different networks -> until they reach the destination.

At the edge of each network we will have a router that does the routing. how do they decide where to send a packet? #card Routers use Routing-Tables where they store information about addresses and how to reach them - or how to take the next step to get closer to them. Consider a router with 3 interfaces where each goes to a different network: 1: 10.10.1.0/24, 2: 10.10.2.0/24, 3: 10.10.3.0/24: If we sent a packet with destination 10.10.3.20 it would hand this request over to interface 3 as this network seems to reachable from there - likely the closest too -> which is denoted by dynamic routing! <-

[!Definition] Longest Prefix Matching: whats meant with that? #card
In case our requested address matches against many interfaces / entries in the table, we should then take the entry with the longest match --> where the prefix is equal the longest. this is important whenever we have large subnets with smaller ones within --> we match against the most specific because thats where the dest-address will be found in.

When a router or host performs a lookup in the routing table, it searches for an entry that has the longest match with the prefix of the destination IP address of the datagram. This is referred to as a longest prefix match. First the routing table is searched for a match on all 32 bits of the IP destination address. Since a match with a 32-bit prefix can occur only for a host route, host routes always take precedence over network routes. If there is no 32-bit prefix match, the routing table is searched for an entry that has a 31-bit prefix match. Then the routing table is searched for a 30-bit prefix match, and so on. If there is no match with a host route or a network route, then the default route is selected. Since the default route is searched last, routing tables often represent the default route as destination address 0.0.0.0/0, that is, a destination address with a 0-bit prefix. If there no match is found and there is no default route in the routing table, the datagram is discarded and an ICMP network unreachable error message is sent to the source IP address of the datagram.

Static Routing

-> statically setting how to reach something / where to send a packet with a given prefix. This might make sense for smaller networks but is tedious to maintain and generally not adaptable to changing circumstances.