Routing

Routing [ ruːtɪŋ ] ( BE ) / [ ruːtɪŋ ] but also [ raʊtɪŋ ] ( AE ) ( engl. "Switching", "routing", "routing", "traffic control" as well as "direct", "control", "Send" ) describes in telecommunications the definition of routes for message streams during message transmission in computer networks . In particular in packet-switched data networks, a distinction must be made between the two different processes routing and forwarding : Routing determines the entire path of a message stream through the network; Forwarding, on the other hand, describes the decision-making process of an individual network node over which of its neighbors it should forward a message.

Often, however, routing and forwarding are mixed up under the term "routing"; In this case, routing generally refers to the transmission of messages via communication networks . In contrast to distributors (hubs and switches), routing works without restrictions, even in meshed networks .

The switching technology uses the term traffic control (English: routing ) to describe the selection of the route sections when setting up communication links , which can take place taking into account criteria such as the shortest distance. If it is a circuit-switched connection, a transmission channel is selected for the entire duration of the connection and all messages are routed over the same path. If, on the other hand, it is a packet-switched data transmission , the route for each packet is redefined by each network node .

In principle, a distinction is made between three approaches:

static routing
alternative routing
adaptive routing

Routing of packets

When packet-switched routing, as it is z. B. takes place on the Internet , it is ensured that logically addressed data packets come out of the source network and are forwarded in the direction of their destination network. Routing is the basis of the Internet - without routing the Internet would not exist and all networks would be autonomous. The data packets can pass through many different intermediate networks on the way to their destination. In the Internet, routing is (usually) carried out on the IP layer. In the ISO / OSI model , routing is one of the essential tasks of the third layer.

Hubs and switches only forward data in the local network, whereas the router also knows neighboring networks. This article describes routing in a hardware-independent way. For information about routers themselves, see the Router article.

In order to know where packets should be sent, one has to know the structure of the network. In small networks, routing can be very simple and is often configured manually. One then speaks of static routing . Large networks can have a complex topology that can change frequently, making routing complex, among other things. Dynamic routing is usually used here.

Since routers can only determine the best routes in relation to the number of packets to be moved very slowly, they note the best possible routes, some of them additional routes to certain networks and the associated routing metrics in one or more routing tables . The best possible route is often the shortest route; it can be found, for example, with Dijkstra's algorithm .

Based on the entries in the routing table (s), a router calculates a so-called forwarding table ; it contains entries of the form destination address pattern → output interface . In its forwarding table, a router then looks up for each newly arrived packet which interface it must use to forward the packet.

Source routing

Source routing is often used in local networks . In this case, the sending station knows the full path to the destination station. The sending station enters the address of the next network node in the header of the message. Each subsequent network node addresses the next node along the route that has already been defined, directly in the header of the message. This method is z. B. used in the Usenet mail service .

A popular example is dynamic source routing ; Here the sending station learns a valid route to the destination station through the route discovery. This route is entered in the header of every packet to the destination station and every intermediate node is obliged to forward the packet along this route. Correct forwarding in bidirectional wireless networks can also be checked (listen in) by the previous hop node.

Routing protocols

Routing protocols ensure the exchange of routing information between the networks and allow the routers to set up their routing tables dynamically. Traditional IP routing remains simple because next-hop routing is used: the router sends the packet to the neighboring router that it believes is the most convenient to the destination network. The router does not need to worry about the further path of the packet. Even if he was wrong and did not send the package to the “optimal” neighbor, the package should still arrive at its destination sooner or later.

Although dynamic routing can get very complex, it makes the Internet very flexible and has allowed the Internet to grow exponentially since the introduction of IP in 1983 . If parts of the backbones fail (as happened e.g. in the summer of 2002 , when the carrier KPNQwest had to shut down its Europe-wide fiber optic network due to bankruptcy), alternative routes can be propagated within seconds and the affected network areas can be bypassed over a wide area.

However, dynamic routing does not counteract the failure of the so-called standard gateway - this is usually the first router seen from the sender. Since a host normally has no alternative to the standard gateway, this is the most important router on the route. HSRP , VRRP and CARP were developed to solve this problem .

Routing algorithms

Routing algorithms use two basic approaches:

Let the world know who your neighbors are: Link-state routing protocols (e.g. OSPF ) ensure that after a while every router knows the complete topology of the network and can calculate the shortest routes for itself.

Let your neighbors know what the world looks like for you: Distance vector protocols (such as the Routing Information Protocol (RIP)) ensure that the routers only tell each other how “well” they are connected to different destination nodes . By selecting the optimal neighbor for a specific destination, the solution of the shortest path problem is distributed over several routers.
A somewhat generalized form of the distance vector protocols with an improved form of loop detection are the path vector protocols (such as the Border Gateway Protocol (BGP)).

Furthermore, routing algorithms can essentially be assessed according to their centralization and their dynamics :

Centralization: where is the algorithm located? Centrally in a network control center or decentrally distributed to the switching nodes?
Dynamics: Is the process not adaptive, i.e. H. the routing table in the switching node remains constant over a longer period of time compared with the traffic change. Or is the process adaptive, ie the routing decisions depend on the state of the network. (Topology, load conditions)

A conflict of objectives arises from these points because, although central, non-adaptive processes burden the network itself less with routing messages, they may use outdated and / or incomplete information about the state of the network. The more adaptive and distributed the routing method, the better the information is distributed over the network. But the more this is burdened by the exchange of messages about routes. There are now a large number of algorithms that have different degrees of centralization and dynamics:

Static routing
Centralized routing
Delta routing
Broadcast routing
Hot potato
Backward learning, distributed adaptive routing ( RIP , OSPF , IS-IS , ...)

The procedures in detail

Static routing

This method is not adaptive , it is very simple and is therefore often used. Each node maintains a table with one row for each possible target node. One line contains entries indicating which is the best, second best, etc. transmission line for this goal, along with a weight. Before a packet is forwarded, the corresponding entry is selected from the table and placed on one of the possible lines. The weighting here reflects the probability that this line will be selected.

Centralized routing

Centralized routing is an adaptive process. There is a Routing Control Center (RCC) in the network , to which each node periodically sends status information. (E.g .: list of all active neighbors, current queue length, volume of traffic since the last message, ...) The RCC collects the status information and uses this knowledge to calculate the optimal path length between all nodes over the entire network. The RCC then transmits a routing table to each node, which the node uses to make its routing decisions.

Advantage:

Theoretically, RCC has a complete overview and can therefore make “perfect” decisions
Nodes do not have to perform any complex calculations

Disadvantage:

Calculation takes time for large networks and U. very long
Failure of the RCC paralyzes the whole network (if there is no backup computer)
Global inconsistencies are possible because nodes that are close to the RCC sometimes receive the new routing tables much earlier than the more distant nodes
heavy burden on the RCC from the global function

Isolated routing

With this type of routing procedure, each node only makes a decision based on the information it collects itself. There is no exchange of routing information. The adaptation to changes in the traffic or the topology of the network (e.g. due to failure of nodes) can therefore only be carried out with limited information. The isolated routing procedures include:

Broadcast routing
Hot potato
Backward learning
Delta routing

Broadcast routing

With "Broadcast Routing" a packet is sent to all nodes. There are two variants here: On the one hand, a separate package is created for each node , and on the other hand, flooding . Flooding is the simplest method here and is not adaptive. Every incoming packet is forwarded on every transmission line except the one on which it arrived. Measures to contain the flood can also be taken, such as:

Detection of duplicates of packages by numbering the packages
Checking the lifespan of parcels by counting the distance covered (hops)
Selective flooding (forwarding not on all, but only on some lines)
Random Walk (random selection of a line)

Hot potato

Each node tries to forward incoming packets as quickly as possible (they treat the packet like a hot potato, hence the name). In contrast to this, there are cold potato processes, in which the router waits as long as necessary until a packet can be forwarded, e.g. B. until a preferred exit is available.

How it works: Theoretically, the Hot Potato method works effectively even if there is no routing information about preferred paths, etc. (see Paul Baran ). Since packets forwarded according to this method may only reach their destination node late and after extensive detours, in practice a combination of the hot potato method and static routing is usually used. In general, there is then a preferred output (even several) for each packet, which results from the static settings of the router (best metrics, minimum hops or similar). If this output is currently free, it is also selected using the Hot Potato method. However, if there are several packets that want to leave the router through the same exit, only the first packet is then routed through the desired exit, all other packets are forwarded to another, suboptimal, currently free exit, even if the other currently free outputs do not represent preferred outputs (metric not minimal, hops not minimal). A transmission line with a free queue (or one of the shortest queues) is always selected as an alternative output.

Advantages:

Quick decision making
Little computing effort
Hot Potato processes ensure optimal line utilization

Disadvantage:

The routing becomes less optimal with increasing load
Packets can go in a circle, i.e. pass a router several times

There are also combinations of this procedure with those of the static "Cold Potato" routing:

Selection of the best transmission line according to the static method, as long as its queue length remains below a certain threshold.
Selection of the transmission line with the shortest queue if its weight is too low (see static routing above).

Backward learning

This procedure requires the following information to be stored in the package:

Identification of the source node
Counter that is incremented by one with each hop

When a node now receives a packet, it can recognize the number of hops and knows which input it received it from. In this way, each node can deduce from the packets received how it can reach the other nodes with the minimum number of hops. An entry in the routing table is replaced if a packet reaches the node with a lower number of hops than is entered in the table. The entries are also updated if no packet with a certain number of hops has been received from the respective node for a certain period of time. So learning periods are allowed at fixed time intervals in which better entries are overwritten with worse ones if they are a certain time old. (Then one must assume that the better connection no longer exists and choose the next best one) This leads to the following problems:

the routing is not optimal during the learning period
with short learning periods (entries are updated faster for the worse), many packages take paths of unknown quality
long learning periods result in poor adaptation behavior to the situation in the network

Delta routing

This procedure represents a combination between centralized and isolated routing. Each node periodically measures the costs of each transmission line (e.g .: a function of delay, load, capacity, ...) and sends these to the RCC. The RCC now calculates the best routes from node to node (for all nodes , ), only taking into account routes that differ in their initial line. The RCC sends the list of all equivalent routes for all destinations to each node. For the current routing, a node can choose an equivalent route at random or decide on the basis of currently measured costs. The eponymous delta comes from the function that is used to determine whether two paths are to be regarded as equivalent. ${\ displaystyle k}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle i}$ ${\ displaystyle j}$

Distributed adaptive routing

In this method, each node periodically exchanges routing information with each of its neighbors. Here, too, each node maintains a routing table that contains an entry for every other node in the network. This table can contain the preferred transmission line for this node and an estimate of the time or distance to this node:

Number of nodes ("hops") to the destination
estimated delay in milliseconds
total estimated number of packages waiting along the way

These estimates are obtained from the time / distance to the neighbors (e.g. using special echo packets with a time stamp) and / or estimates of the neighbors. The routing information can be exchanged either synchronously at specific update intervals or asynchronously in the event of significant changes. This procedure includes, among other things

Distance vector routing
Link state routing

Distance vector routing

Distance vector protocols determine the reachability by a vector from distance and direction. The metric is expressed in the number of nodes to be passed. The Bellman-Ford algorithm is usually used to determine the path .

As soon as changes in the network topology become known, these are reflected in update messages. If a router detects an interrupted connection or the failure of its neighbor, it recalculates the affected routes and sends change notifications to all accessible nodes. Every router that receives such a message adapts its routing table and propagates this change.

In practice, this method converges too slowly to a consistent state for many routers due to the " count-to-infinity " problem.

RIP, for example, belongs to this class .

Link state routing

Link-state protocols are seen as an alternative to distance vector approaches and therefore try to compensate for some of their weaknesses. In contrast to distance vector protocols, which only have a limited view of the network topology, the routers with link-state protocols have a complete overview of the structure of the network. The overview (topology database) consists of link state information and is comparable to a city map, which is identical on every router within an area.

Networks can be divided into areas (so-called areas). This allows the size of the topology database to be reduced and changes in the area do not necessarily affect other areas.
All routers within an area have the same database. This database describes the complete topology of the area (topology database).
Each router uses this database to derive the optimal path for a destination (IP network or host) and to put this in its routing table. The determination of the path is based on Dijkstra's Shortest Path First algorithm.
Hellopackets establish contact with the neighboring routers. All neighboring routers are addressed using the multicast mechanism.

The link state protocol does not use periodic updates to update the database, but only sends a link state update when the topology changes. This need arises when:

a new router is discovered
a router stops working
the cost of a connection changes
periodically every 30 minutes.

OSPF and IS-IS belong to this class.

Hierarchical routing

The basis of hierarchical routing is the division of large networks into regions. The nodes of a region only have routing information about their own region. In each region there is one or more distinguished nodes, which serve as an interface to other regions. In very large networks, further hierarchies are possible due to the increasing size of the networks (regions, clusters, zones, groups, ...).

Metric

A routing metric is a numerical value that a routing algorithm can use to determine whether one route is better than another. Metrics can include information such as B. bandwidth , delay, hop count , path costs, load, MTU , reliability and communication costs. If z. For example, if the distance is the decisive metric in determining a route, in the case of several possible routes the one with the smallest value (i.e. the lowest distance) is chosen. However, it is not always possible to determine the best route based on the smallest value. B. a higher bandwidth is represented by a higher metric value. Often only the best possible routes are kept in the routing table, while link state or topological databases from which the routing table is obtained contain all the information. Which metric is used depends on the routing protocol. For example, RIP only uses the hop count as a distinguishing criterion for choosing the best route to a destination network, thus ignoring the bandwidth, for example.

Routing on the Internet

In principle, there are two different types of routing on the Internet, depending on the purpose:

Int ra domain routing takes place within a autonomous system instead ( "AS");
Int er domain routing describes the routing between autonomous systems.

Here the part of the name "domain" refers to the autonomous system; so it has nothing to do with the “ DNS domains ”, for example for web addresses.

Intradomain routing

Intradomain routing uses so-called Interior Gateway Protocols (IGP). In most cases, the focus of intradomain routing is on the technically efficient use of the network; it is typically based on a route selection along the shortest paths.

The administrator tries to maximize the data volume that can be transmitted through the network by cleverly configuring the routing. This optimization of the routing, taking into account the actual data transmission requirements between different parts of the network, is called traffic engineering .

Interdomain routing

Interdomain routing uses so-called Exterior Gateway Protocols (EGP), and (almost) always BGP . Since interdomain routing regulates the routing between different providers, the focus of interdomain routing is usually on financially efficient (profit-oriented) use of the network. The underlying idea here is that an autonomous system does not allow all of its neighbors to receive the same information (routes). Which information is exchanged and which is not is first specified in contracts and then configured in the routers; In this context one speaks of policy-based routing .

IP routing using the example

Simple protocols such as B. native NETBIOS do not know routing; here two stations identify themselves exclusively through the MAC addresses of their network cards. This is also the case with IP communication within a shared network (without routing) - at least after the MAC address belonging to the IP address has been determined via ARP or NDP . Each packet then contains the MAC and IP address of the recipient as well as the MAC and IP address of the sender as well as optional user data.

If the sender and recipient are in different networks, a router is required. If a station connected via a router wants to send a packet to a recipient outside of its network, for example to a Telnet server, the communication process (shown in simplified form) works as follows: First the station determines the router closest to the desired destination (see routing table ), determines its MAC address via ARP and assembles a packet as follows: It receives the MAC address of the nearest router, the destination IP address of the recipient, the destination port address 23 for the Telnet server as the destination MAC address as well as the MAC and IP address of the sender and a sender port (any currently free port, e.g. 5387) for the Telnet session currently requesting as well as other required data. The router receives and processes the packet because it is directed to its MAC address. When processing in the router, the packet is forwarded in a slightly modified form: The router determines the next router , determines its MAC address via ARP and converts the packet as follows: It now receives the MAC address as the destination MAC address of the next router and your own MAC address as the source MAC address. The IP address of the recipient, destination port 23 and the IP address of the sender, sender port 5387 and the user data, however, remain the same. This means: the packet is not changed on layer 3 ( IP ). This process is repeated until a last router finds the target station in a directly connected network; then the packet is composed as follows: it contains the MAC address of the destination station, the MAC address of the last router - i.e. the data of the last layer 2 connection ( Ethernet ) - and the IP address of the recipient (= destination station ), Destination port 23 and the IP address of the sender, sender port 5387 and of course user data.

After successful processing by the Telnet server, the response is then compiled as follows: MAC address of the router responsible for the return route (although the outward and return routes do not necessarily have to be identical), the IP address of the requesting computer (formerly the sender), the destination port address 5387 (previously the sender port) and the MAC and IP address of the Telnet server and its sender port, as well as response data. After all routers have been run through, this becomes in the last router: MAC address and IP address of the requesting computer, the MAC address of the last router, the destination port address 5387 and the IP address of the Telnet server and its sender port, as well Response data. If this Telnet session is ended, port 5387 is also released again.

Interaction of protocols

Depending on whether a router is part of an autonomous system or even forms its boundary, it often uses routing protocols from different classes at the same time:

Interior Gateway Protocols ( IGPs ) exchange routing information in a single autonomous system. Frequently used are:
- IGRP / EIGRP (Interior Gateway Routing Protocol / Enhanced IGRP)
- OSPF (Open Shortest Path First)
- IS-IS (Intermediate System to Intermediate System)
- RIP (Routing Information Protocol)
- R-SMLT Routing SMLT
Exterior Gateway Protocols ( EGPs ) regulate the routing between different autonomous systems. This includes:
- BGP (Border Gateway Protocol: BGP4 version since 2002 ) is the de facto standard worldwide today.
- EGP (the old Exterior Gateway Protocol used to connect the Internet backbones. It is now obsolete.)
Ad hoc routing protocols are used in networks with little or no infrastructure.
- OLSR is mostly used in the mobile area.
- AODV is used in smaller networks with mainly static traffic.

Routing protocols can also interact with one another. For example, new routes can be exported from the IGP to the EGP. Other cases are also conceivable: If it changes, e.g. B. If a link fails , the IGP metric for a path a ⇝ b within the AS X , then X can transfer the metric change to all EGP paths a ⇝ b ⇝ Y , a ⇝ b ⇝ Z , etc. It is also conceivable that some routes that a router has learned from different routing protocols contradict each other; In such cases, a previously defined prioritization ( administrative distance ) regulates the router's ultimate decision.

Overview / summary of routing protocols

Routing protocol	Routing algorithm	Shortest Path Algorithm	commitment	Metric	Remarks
BGP	Path-Vector	Bellman-Ford	EGP	Policies	De facto standard, prevents grinding
RIP	DV	Bellman-Ford	IGP	Hop count	Count-to-infinity problem
OSPF	LS	Dijkstra	IGP	*	hierarchical routing
IS-IS	LS	Dijkstra	IGP	*	ISO standard, cf. with OSPF
EIGRP	DV	DUAL	IGP	*	Cisco standard

* different (partially combinable) metrics

Individual evidence

↑ Anett Mehler-Bicher, Frank Mehler, Nicolai Kuntze, Sibylle Kunz, Bernhard Ostheimer, Lothar Steiger, Hans-Peter Weih: Wirtschaftsinformatik Klipp und Klar . ISBN 978-3-658-26494-9 , pp. 113 .

↑ Andreas Iselt: Failure safety and uninterrupted backup switching in communication networks with redundancy domains . Herbert Utz Verlag, ISBN 3-89675-621-4 , p. 24 .

↑ route: Dictionary (MACMILLAN DICTIONARY) From the "Macmillan Dictionary"

↑ routing: Dictionary (BEOLINGUS, TU Chemnitz) From the Beolingus dictionary - a service of the TU Chemnitz

↑ BGP routing policies in ISP networks (PDF; 168 kB). IEEE Network Magazine, special issue on Interdomain Routing, Nov / Dec 2005, Matthew Caesar and Jennifer Rexford.

^ Digital Simulation of Hot-Potato Routing in a Broadband Distributed Communications Network , Paul Baran, 1964

↑ Understanding and mitigating the effects of count to infinity in Ethernet networks Khaled Elmeleegy; Alan L. Cox; TS Eugene Ng 2009

Web links

Link catalog on routing and routing at curlie.org (formerly DMOZ )

Routing metrics overview (PDF file; 7.09 MB)

[1] Anett Mehler-Bicher, Frank Mehler, Nicolai Kuntze, Sibylle Kunz, Bernhard Ostheimer, Lothar Steiger, Hans-Peter Weih: Wirtschaftsinformatik Klipp und Klar . ISBN 978-3-658-26494-9 , pp. 113 .