Routing

Routing [ru ː tɪŋ ] (BE) / [ ru ː tɪŋ ], but also [ raʊtɪŋ ] (AE) (English " routing ", " route ", " traffic management " and " conduct ", " send ", " control " ) referred to in the telecommunications setting of paths for message streams for message delivery in computer networks. In particular, in packet- switched data networks routing and forwarding is to be distinguished between the two different processes: Routing determines the entire path of a stream of messages through the network; Forwarding the other hand, describes the decision making process of a single network node over which of its neighbors it should forward an existing message.

However, routing and forwarding are often mixed together under the term " routing "; In this case, routing generally refers to the transmission of messages over communication networks. In contrast to distributors ( hubs and switches ) routing without constraints also works in meshed networks.

The switching equipment designated by the term traffic management (English: routing) the selection of road segments in the construction of communications that can be done taking into account criteria such as the shortest distance. If it is a circuit switched connection, a transmission channel for the entire duration of the connection is selected, and all messages are routed through the same path. If, in contrast to a packet-switched data transmission, the path for each packet of each node is redefined.

In principle, three approaches can be distinguished:

• Static routing
• Alternative routing
• Adaptive routing

• 4.1 Intra -domain routing
• 4.2 Inter-Domain Routing
• 4.3 IP routing example
• 4.4 Interaction of protocols
• 4.5 Overview / Summary routing protocols

Routing packets

Packet-switched routing, as it takes place eg on the Internet, it is ensured that logically addressed packets get out of the originating network and be forwarded toward its destination network. Routing is the basis of the Internet - without routing the Internet would not exist, and all systems would be autonomous. The data packets can this happen many different intermediate networks on the way to their destination. Internet routing (typically ) is performed on the IP layer. In the ISO / OSI model routing is one of the essential tasks of the third layer.

Hubs and switches forward data only on the local network further, whereas the router knows also neighboring networks. This article describes a hardware-independent routing on Art For information on router even see the router products.

In order to know where packets are to be sent, one must know the structure of the network. In small networks, the routing to be very simple and is often configured by hand. We also speak of static routing. Large networks can have a complex topology, which may be changes frequently, which makes, among other routing to a complex matter. Here a dynamic routing is used in the rule.

Because routers the best routes in proportion to the number of can be determined only very slowly moving packets, they remember in one or more routing tables, the best, sometimes more routes to specific networks and the related routing metrics. The best way is often the shortest way; it can be, for example, using the algorithm of Dijkstra found.

Based on the entries in the routing table or the (n) a router called a forwarding table; it contains entries of the form destination pattern → output interface. In its forwarding table, a router proposes then for each newly arrived packet, on which interface to forward the packet.

Source Routing

In local networks, the so-called source routing is often used. In this case, the transmitting station is known, the full path to the destination station. The sending station transmits the address of the next node in the header of the message. Each following node addresses the next node along the already established route, directly in the message header. This method is used for example in Usenet mail service.

A popular example is the Dynamic Source Routing; this undergoes the sending station through the route discovery a valid route to the destination station. This route is entered in the header of each packet to the destination station and each intermediate node is required to forward the packet along this route. The correct forwarding can be controlled in two-way wireless networks also by the previous hop node (call screening ).

Routing protocols

Routing protocols provide for the exchange of routing information between networks and allow the routers to build their dynamic routing tables. Traditional IP routing is simple, as next-hop routing is used: The router sends the packet to those neighboring router from which he believes that he is most favorable to the destination network. To the further path of the packet, the router does not need to worry about. Even if he was wrong and the package has not sent to the "optimal" neighbors, the package should still arrive sooner or later at the destination.

Although dynamic routing can be very complex, it makes the Internet very flexible and allowed the exponential growth of the Internet since the introduction of IP in 1983. Upon the failure of parts of the backbone ( as happened for example in the summer of 2002, when the carrier KPNQwest had to shut its European fiber network due to bankruptcy ), can be propagated within seconds alternative routes and the affected areas of the network are bypassed widely.

The failure of the so-called default gateway - this is usually the first router seen from the transmitter - but acts dynamic routing does not prevent. Since a host normally has no alternative to the default gateway, this is the main router of the route. To solve this problem HSRP, VRRP and CARP have been developed.

Routing algorithms

Routing algorithms use two basic procedures:

• Parts of the world, who are your neighbors: link-state routing protocols (eg OSPF) ensure that after some time, each router knows the full topology of the network and can calculate the shortest path in itself.
• Share your neighbors, the world looks like for you: distance-vector routing protocols ( such as the Routing Information Protocol (RIP) ) ensure that the routers, just like to say as they are " good" connections to different destination nodes. By selecting the optimum for a particular target neighbor solving the shortest path problem is thus distributed on multiple routers. A more generalized form of distance vector protocols with an improved form of loop detection, the path vector protocols (such as Border Gateway Protocol ( BGP) ).

Routing algorithms continue to be based primarily on its centralization and their dynamics:

• Centralization: Where is the algorithm locates? Centrally located in a network control or decentralized distributed to the switching node?
• Dynamics: the method is not adaptive, that is, the routing table in the switch node remains constant over time, compared to the traffic change. Or the method is adaptive, that is, routing decisions depend on the state of the network. (Topology, load conditions )

From these points there is a conflict because, although central, non- adaptive method, the net burden themselves with less routing messages, but maybe outdated and / or incomplete information about the state of the network use. Each adaptive and distributed routing methods are, the better the information about the network are distributed. But the more this is also affected by the exchange of messages for routes. There are now a variety of algorithms, which 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 method in detail

Static Routing

This method is not adaptive, very simple and therefore is often used. Each node maintains a table with a row for each possible destination node. A row contains entries, which is the best, second best, etc. transmission line for this target, together with a weighting. Before forwarding a packet, the corresponding entry is selected from the table and put on one of the possible lines. The weighting here reflects the probability that this line is selected.

Centralized routing

Centralized routing is an adaptive method dar. It exists in the network routing control center ( RCC), in which each node periodically sends state information. (eg: list of all active neighbors, current queue length, amount of traffic since last report, ...) The RCC collects the state information and calculated on the basis of this knowledge across the entire network, the optimal path between all nodes. After that, the RCC shall provide each node a routing table based on which the node makes its routing decisions.

Advantage:

• RCC theoretically has the full overview, and can thus make "perfect" decisions
• Nodes need not perform complex calculations

Disadvantage:

• Calculation takes for large networks may very long
• Failure of the RCC paralyzes the entire network ( unless you have a backup computer is available)
• Global inconsistencies are possible, as nodes, which are close to the RCC, and sometimes much earlier obtain the new routing table as the next remote node
• Heavy loading of the RCC by the global function

The isolated routing

In this type of routing method, each node decides only on the basis of the information he gathers himself. There is no exchange of routing information. Adaptation to changes of traffic or the network topology (eg due to failure of nodes ) can be done only with limited information here so. Among the isolated routing methods:

• Broadcast routing
• Hot Potato
• Backward Learning
• Delta routing

Broadcast routing

In "Broadcast Routing" a packet is sent to all nodes. Here, two variants differ: Once that for each node a separate package is created, and on the other the floods. The flooding here is the simplest method and is not adaptive. Each incoming packet is transmitted on each transmission line, except for that on which it arrived. This also measures to stem the tide may be taken as:

• Detection of duplicates of packets, by numbering the packets
• Control the lifetime of packets by counting the covered section ( hops )
• Selective flooding ( forwarding not at all, but only on some lines )
• Random walk ( random selection of a line )

Hot Potato

Each node tries to forward incoming packets as soon as possible ( they treat the package as a hot potato, hence the name). In contrast, Cold Potato stand - process, here, the router will wait as long as necessary until a packet can be forwarded, for example, until a preferred output is free.

Operation: Theoretically, the Hot Potato method works even purposeful if no routing information about preferred paths are present, etc. (see Paul Baran ). Da ' possibly achieve by this method forwarded packets to their destination nodes late and after extensive detours, a combination of the Hot Potato method and the static routing is used in practice usually. Generally, there are then for each packet a preferred output ( more than one), the results from the static settings of the router ( best metric, minimal hops or similar). If this output is just free, it is also chosen by the Hot Potato procedures. If, however, pending several packages which want to leave the router through the same output, but only the first packet is then passed through the desired output, all other packets are forwarded to another suboptimal, just free output and even if the just another free outputs no preferred outputs represent ( metric not minimal, not hops minimal). As an alternative output but always a transmission line with a free queue (or one of the shortest queues) is selected.

Advantages:

• Fast decision-making
• Low computational complexity
• Hot Potato procedures ensure optimum utilization management

Cons:

• With increasing load, the routing is less optimal
• Packages can run in circles, so pass through a router multiple times

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

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

Backward Learning

In this process, the following information must be stored in the package:

• ID of the source node
• Counter that is incremented with each covered section ( hop ) by one

When a node now receives a packet, it can detect the hop count and white, via which input he has received it. Thus, each node can conclude from the obtained packets on which way he can reach the other nodes with the minimum number of hops. An entry in the routing table is replaced when a packet with a lower hop count reaches the node, as is registered in the table. The entries are also updated when a certain amount of time was obtained after no more packet with a certain hop count of each node. There are thus at fixed time intervals learning periods allowed in which better entries are overwritten with poorer if they are a certain amount of time old. ( Then you have to assume that the better connection no longer exists, and the next best choose ) results in the following problems:

• During the learning period, the routing is not optimized
• With short learning periods ( entries will be faster for the worse updated) take many routes packets of unknown quality
• At long learning periods is a bad adaptation behavior to the situation results in the net

Delta routing

This method is a combination between centralized and isolated routing dar. this case, each node periodically measures the cost of each transmission line ( for example: a function of the delay, utilization, capacity, ... ) and sends it to the RCC. The RCC now calculates the best paths from node to node (for all nodes ), where only paths are considered which differ in their initial line. The RCC sends the list of equivalent paths for all destinations on each node. For current routing, a node can select an equivalent way by chance, or decide on the basis of measured current costs. The eponymous Delta comes here from the function with which it is determined whether two paths are to be regarded as equivalent.

A distributed adaptive routing

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

• Number of hops
• Estimated delay in milliseconds
• Estimated total number of packets that are waiting along the way

These estimates are obtained from the time / distance to neighbors (eg by means of special echo packets with time stamp) and / or estimates of the neighbors. An exchange of routing information can be done either synchronously or asynchronously in certain update intervals are significant changes. For this method include, among others,

• Distance Vector Routing
• Link State Routing

Distance Vector Routing

Distance Vector protocols determine reachability by a vector of distance and direction. The metric is expressed in the number of passing to nodes. For the path determination usually the Bellman-Ford algorithm.

Once changes in the network topology are known, these are reflected in update messages. Discovered a router has a broken connection or the failure of its neighbor, it calculates the affected routes and newly sent change notifications to all reachable nodes. Each router that receives such a message, adjusts its routing table and propagates this change.

In practice, this method has a slow convergence to a consistent state for many routers, due to the "Count -to- Infinity " problem.

This class includes, for example RIP.

Link State Routing

Link - state protocols are considered an alternative to distance-vector approaches and therefore try to compensate for some of their weaknesses. In contrast to distance-vector protocols, which have only a limited view of the network topology, the router in link-state protocols have a complete overview of the structure of the network.

• Networks to be divided into areas ( so-called Areas).
• All routers within an area have the same data base. This database describes the complete topology of the area.
• Each router uses this database in order to derive the optimal path and to place it into its routing table. The determination of the path is based on the Dijkstra Shortest Path First algorithm.
• Hello packets to establish a contact with neighboring routers. Taking advantage of the multicast mechanism all neighboring routers to be addressed.

To update the data base, the link-state protocol uses no periodic updates, it sends a topology change only when a link-state update. This need arises when:

• A new router is discovered
• A router adjusts its service
• Change the cost of a link is
• Periodically every 30 minutes.

This class includes OSPF and IS -IS

Hierarchical routing

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

Metrics

A routing metric is a numerical value with the aid of a routing algorithm to determine whether a route as compared to another is better. Metrics can be taken into account information such as bandwidth, delay, hop count, path costs, load, MTU, reliability and communication costs. For example, if the distance is the decisive metric for the determination a route, the one with the lowest value ( that is, the lowest distance) is selected in the case of a plurality of possible routes. But not always possible to determine the best route based on the smallest value, since, for example, a higher bandwidth is represented by a higher metric value. In the routing table is often only the best routes are held while link-state or topological databases include all information.

Routing in the Internet

A basic distinction in the Internet, depending on the purpose, two different types of routing:

• Intra -domain routing takes place ( "AS" ) within an autonomous system;
• Inter-domain routing refers to the routing between autonomous systems.

Herein, the part of the name "domain" on the autonomic system; he has nothing to do with the " DNS domains " for example in web addresses.

Intra -domain routing

Intra -domain routing uses so-called Interior Gateway Protocols ( IGP). The focus for intra -domain routing in most cases on a technically efficient use of the network; it is typically based on a routing along shortest paths.

The administrator tries to maximize by skillfully configure routing the transmissible through the network data volume. This optimizing the routing taking into account the real existing data transfer needs between different parts of the network is called Traffic Engineering.

Inter-domain routing

Inter-domain routing uses so-called Exterior Gateway Protocols ( EGP), and is (almost ) always BGP. Since inter-domain routing The routing between different providers, the focus usually lies with the inter-domain routing on a financially efficient ( for-profit ) use of the network. The underlying idea here is that an autonomous system is not all its neighbors can get the same information ( routes). What information is shared and which are not, is first specified in the contracts and then einkonfiguriert in the routers; one speaks in this context of policy-based routing. For more information about policy- based routing is in the article on autonomous systems.

IP routing on the example

Simple protocols such as native NETBIOS know no routing; here are two stations identify exclusively with the MAC addresses of your network cards. This is also in IP communication within a common network so (without routing) - at least after the belonging to the IP address MAC address detected by ARP or NDP. Then, each packet contains the MAC address and the recipient as well as the MAC address and IP address of the sender, and optional user data IP address.

Lying sender and receiver but in different networks, a router is required. Want one via router -connected station to send a packet to a receiver outside of their network, for example to a Telnet server, the communication process works ( in simplified form ) as follows: First, the station determines the nearest to the desired destination router (see routing table) determined by ARP its MAC address and builds a package as follows: It receives as destination MAC address is the MAC address of the nearest router, the recipient's destination IP address, destination port address 23 for the Telnet server as well as the MAC address and IP address of the sender and a sender port (any straight free port, eg 5387 ) of the just inquiring Telnet session and other necessary data. The router receives and processes the packet, because it is addressed to the MAC address. When processing in the router forwards the packet in a slightly modified form is forwarded: The router determines the next router, determined by the MAC address of ARP and builds it as follows in order: It now receives as deviating destination MAC address is the MAC address the next router and as a source MAC address its own MAC address. The IP address of the consignee, destination port 23 and the IP address of the sender, sender port 5387 and the user data, however, remain the same. The means to layer 3 ( IP) packet is not changed. This process is repeated until a last router finds the destination station in a network directly connected; then the package is as follows: it contains the MAC address of the destination station, the MAC address of the last router - ie the data of the last layer 2 connection (Ethernet) - as well as the receiver ( = destination station 's IP address ), 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 for the return competent router (the return route is not necessarily the same ), the IP address of the requesting computer (formerly the sender), the destination port address 5387 (formerly sender port) as well as the MAC address and IP address of the Telnet server and the sender port, as well as response data. After all routers have been run, it is 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 the source port, and response data. If this Telnet session is terminated even port 5387 is enabled again.

Interaction of protocols

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

• Interior Gateway Protocols ( IGPs ) to exchange routing information within a single autonomous system. Commonly used: 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

• BGP (Border Gateway Protocol: since 2002 in Version BGP4 ) is now the world's de facto standard.
• EGP ( Exterior Gateway Protocol with the old, the Internet backbones were formerly connected. It is now obsolete. )

• OLSR is used mostly in the mobile space.
• AODV is mainly in smaller networks with static traffic use.

This routing protocols can also interact with each other. For example, new routes can be exported from the IGP to EGP. Other cases are possible: Varies, for example, by the failure of a link, the IGP metric for a path a ⇝ b within the AS 'X, then X is the metric change to all a ⇝ b ⇝ Y EGP paths, a ⇝ b ⇝ Z etc. transferred. It is also conceivable that some of the routes that a router has learned from different routing protocols mutually contradictory; In such cases, regulates a previously defined prioritization ( Administrative Distance ) the final decision of the router.

Overview / Summary of Routing Protocols

* Different (partly combinable ) metrics