Routing Algorithms

A Routing Algorithm is a method for determining the routing of packets in a node. For each node of a network, the algorithm determines a routing table, which in each destination, matches an output line. The algorithm should lead to a consistent routing, that is to say without loop. This means that you should not route a packet a node to another node that could send back the package.

There are three main types of routing algorithms:

• Distance Vector (distance-vector routing);

• To link state (link state routing);

• Path to vector (path-vector routing).

Distance vector routing algorithms require that each node exchanges information between neighbors, that is to say between nodes directly connected. Therefore, each node can keep updated a table by adding information on all its neighbors. This table shows the distance is each node and each network to be reached. First to be implemented in the Arpanet, this technique quickly becomes cumbersome when the number of nodes increases since we must carry a lot of information node to node. RIP (Routing Information Protocol) is the best example of a protocol using distance vector.

In this type of algorithm, each router broadcasts to its neighbors a vector that lists each network it can reach the metric associated with, that is to say the  number of hops. Each router can therefore build a routing table with information received from its neighbors but has no idea of ​​the identity of routers that are on the selected route. Therefore, the use of this solution poses numerous problems for external routing protocols. Indeed, it is assumed that all routers use the same metric, which may not be the case between autonomous systems. Furthermore, an autonomous system can have special reasons to behave differently from another autonomous system. In particular, if an autonomous system needs to determine how else autonomous system will pass its messages, e.g. for security reasons, he can not know.

The algorithms link state had initially intended to overcome the shortcomings of distance vector routing. When a router is initialized, it must define the cost of each of its links connected to another node. The node then broadcasts the information to all nodes in the autonomous system, and therefore not only to its neighbors. From all this information, the nodes can perform their calculation for obtaining a routing table indicating the cost of achieving each destination. When a router receives information that alters its routing table, it notifies all intervening routers in its configuration. As each node has the network topology and costs of each link, routing can be seen as central in each node. OSPF (Open Shortest Path First) implements this technique, which is the second generation of Internet protocols.

The algorithms link state solves the problems mentioned above for external routing but raise other. The various autonomous systems may have different metrics and specific restrictions, so it is not possible to achieve a coherent route. The dissemination of all information necessary for all the autonomous systems can also quickly become unmanageable.

The purpose of the path-vector algorithms is to overcome the shortcomings of the first two categories by providing metrics and seeking to know which network can be reached by any node and autonomous systems which must be crossed for it. This approach is very different from that distance-vector because the paths vectors do not take into account the distances or costs. In addition, the fact that each list routing information all autonomous systems that must be traversed to reach the destination router, the path vector approach is much more directed towards the external routing systems. BGP (Border Gateway Protocol) belongs to this category.

RIP (Routing Information Protocol)

RIP is the most widely used protocol in the TCP / IP environment to route packets between the gateways of the Internet. It is a protocol IGP (Interior Gateway Protocol), which uses an algorithm to find the shortest path.

By the way, refers to the number of nodes crossed, which must be between 1 and 15. The value 16 indicates impossibility. In other words, if the path to get from one point to another of the Internet is above 15, the connection can not be established. RIP messages to establish the routing tables are sent approximately every 30 seconds. If a RIP message does not reach its neighbor after three minutes, the latter considers that the link is no longer valid; the number of links is greater than 15. RIP is based on a periodic distribution of states network from a router to its neighbors. The release includes a RIP2 routing subnet, message authentication, multipoint transmission, etc.

OSPF (Open Shortest Path First)

OSPF is part of the second generation of routing protocols. Much more complex than RIP, but at higher performance rates, it uses a distributed database that keeps track of the link state. This information forms a description of the network topology and the status of nodes, which defines the routing algorithm by calculating the shortest paths.

The algorithm allows OSPF, from a node, to calculate the shortest path, with the constraints specified in the content associated with each link. OSPF routers communicate with each other via the OSPF protocol, placed on top of IP. Now look at this protocol a bit more detail.

The assumption for link state protocols is that each node can detect link status with its neighbors (on or off) and the cost of this link. We must give to each node enough information to enable him to find the cheapest route to any destination. Each node must have knowledge of its neighbors. If each node to the knowledge of other nodes, a complete map of the network can be established. An algorithm based on the state of the neighboring requires two mechanisms: the dissemination of reliable information on the state of the links and the calculation of routes by summing the accumulated knowledge of the link state.

One solution is to provide a reliable flood of information, to ensure that each node receives his copy of the information from all other nodes. In fact, each node floods its neighbors, which, in turn, flood their own neighbors. Specifically, each node creates its own update packets, called LSP (Link-State Packet), containing the following information:

• Identity of the node that creates the LSP.

• List of neighboring nodes with the cost of the associated link.

• Sequence Number.

• Timer (Time to Live) for this message.

The first two information is needed to calculate routes. The last two aim to make reliable flooding. The sequence number allows to put in order the information that would have been received out of order. The protocol has error detection and retransmission elements.

The route calculation is performed after receiving all the information on the links. From the complete map of the network and costs of links, it is possible to calculate the best route. The calculation is performed using Dijkstra’s algorithm on the shortest path.

In the acronym OSPF (Open Shortest Path First) Open the word indicates that the algorithm is open and supported by the IETF. Using the mechanisms outlined above, the OSPF protocol adds the following additional properties:

• Authentication of routing messages. Malfunction can lead to disasters. For example, a node that, following the receipt of wrong messages, intentionally or not, or a striker messages modifying its routing table, calculates a routing table in which all nodes can be achieved at a cost zero automatically receives all network packets. These problems can be avoided by authenticating issuer’s messages. Early versions had a OSPF authentication password of 8 bytes. The latest versions have much stronger authentication.

• New hierarchy. This hierarchy allows for better scalability. OSPF introduces another level of hierarchy by partitioning the areas into eras (area). This means that a router within a domain does not need to know how to reach all the networks in the field. Just that he knows how to reach the right age. This results in a reduction of information to be transmitted and stored.

There are several types of OSPF messages, but they all use the same header, which is shown in Figure.

The current version is 2. Five types were defined with values ​​from 1 to 5. The source address indicates the sender of the message. The identification of the era indicates the era in which lies the sending node. The authentication type has the value 0 if there is no authentication, 1 if the authentication password and 2 if an authentication technique is implemented and described in the following 4 bytes.

The five types of messages have the Hello message as Type 1. This message is sent by a node to its neighbors to tell them that it is always present and not broken. The four other types are used to send information such as queries, shipments or acquittals LSP messages. These messages mainly carrying LSA (Link-State Advertisement), that is to say, information about link state. A message can contain several OSPF LSA.

The figure illustrates a type of OSPF LSA carrying a message 1.

IS-IS

The IS-IS algorithm was primarily developed by ISO (ISO 10589). It discloses a hierarchical routing based on the decomposition of communication networks into domains. In one area, the nodes indicate their state to IS-IS routers related. The cross-domain communications are performed by a routing to a domain access point determined by the routers responsible for external communications field.

IGRP (Interior Gateway Routing Protocol)

Improved version of RIP, IGRP was designed by Cisco Systems for its own routers. It integrates multipath routing, management of default routes, dissemination of information every 90 seconds instead of every 30 seconds, detection of closures, that is to say, returns to a point whereby the packet has already passed, etc. The protocol itself has been extended for better protection against the loops by EIGRP (Extended IGRP).

EGP (Exterior Gateway Protocol)

EGP is the first routing algorithms have been developed in the early 1980 for routing a packet of an autonomous system to another.

It has three essential procedures that allow the exchange of information. The first procedure concerns the definition of a nearby bridge. The latter is known, a second procedure determines the link that allows the two neighbors to communicate. The third procedure for the exchange of packets between two neighbors connected by a link. The weaknesses of EGP have emerged with the exponential growth of the Internet and the need to avoid some politically sensitive areas.

BGP (Border Gateway Protocol)

To address the weaknesses of EGP, a new algorithm has been initiated by the IETF under the name of BGP. A first version, BGP-1, was implemented in 1990, followed closely by BGP-2 and BGP-3. After a few years was deployed BGP-4, which can handle a lot more effectively large routing tables by bringing together in a single line multiple subnets.

BGP provides new properties compared to EGP, especially to manage loops, which became common in EGP protocol since it deals only couples neighbors, without taking into account possible loop backs by a third autonomous network.

The messages exchanged via BGP-4 are:

• OPEN: to open a relationship with a neighboring node.

• UPDATE: to convey information about a single route or request the destruction of roads that are no longer available.

• KEEPALIVE: to pay the OPEN messages and confirm that the neighbor relationship is still alive.

• NOTICE: To send an error message.

The following three functional procedures are defined in BGP:

• Acquisition of the neighboring nodes;

• Ability to reach the neighbor;

• Ability to reach networks.

Two routers are considered neighbors if they are in the same network. If the two routers are in separate autonomous areas, they may need to exchange routing information. For this, we must first carry out an acquisition of the neighbors, that is to say, allow two nodes that are not in the same autonomous system to share routing information. The acquisition must be made by a formal procedure since the two nodes may not want to exchange routing information. To complete the acquisition, a node transmits the message OPEN. If the remote router accepts the connection, it sends a KEEPALIVE. Once the relationship, to maintain active relationship nodes are exchanged KEEPALIVE. Each node maintains a database of networks it can reach and the route for arriving at these different networks. When a change occurs, the router broadcasts an update message to other routers, which allows them to be updated.

The figure illustrates the format of BGP update packet.

The Marker field is reserved for authentication. The transmitter can put a cipher text that can be decrypted by the receiver with the encryption key. Length gives the message length in bytes. The message types are OPEN, UPDATE, KEEPALIVE, and NOTIFICATION.

To set up a neighborhood relationship, the starting router initiates a TCP connection and sends an OPEN message. This message indicates the autonomous system in which the transmitter is located and the IP address of the router. It also includes a HOLD TIME PARAMETER, which indicates the number of seconds available for the Hold Timer to determine the maximum time between two messages from the transmitter (KEEPALIVE, UPDATE). If the remote accepts the connection, it calculates the minimum of its own Hold Timer and that of the transmitter and sends it to the transmitter.

The fields of the OPEN package are shown in Figure. These fields are:

• Version: one-byte value indicating the BGP protocol version used (4 for BGP-4).

• My Autonomous System (my autonomous system): 2-byte value indicating the Autonomous System number of the sender.

• Hold Time (retention time): 2-byte field indicating the number of seconds that the sender proposes for the chosen counter. This avoids the endless closures in the autonomous systems. Once a device receives a BGP OPEN message, it must calculate the value of the hold-down timer that will be used. For this, he chose the smaller of the retaining counter he just received his OPEN message and the value that was set for himself. The selected value is actually the number of seconds between receipt of KEEPALIVE and UPDATE messages sent by the transmitter.

• Identify BGP (BGP identifier): 4-byte field indicating the BGP identifier. This identifier is based on the IP address assigned to the BGP device.

• Optional Parameters Length: one-byte field indicating the total size of the Optional Parameters field in byte. If the value is 0, there are no optional parameters.

• Optional Parameters: field containing the list of optional parameters that are represented by triplets Parameter Type, Length and Parameter Value. The Parameter Type field uniquely identifies each optional parameter. The Parameter Length field indicates the size in bytes of the Parameter Value field. The Parameter Value field is a variable size field (which is why its size is shown in the Parameter Length field) containing the optional parameter itself.

The KEEPALIVE message takes into account the BGP message header. It must be issued often enough to the Hold Timer does not fire. UPDATE messages are used to route two types of messages:

• Information about a single road, which are recorded in databases of information routers.

• Information about a list of routes that will be destroyed. The NOTIFICATION messages are sent when an error has been detected. The following errors may be issued:

• MESSAGE HEADER ERROR: an error in the header of the message was detected as an authentication failure or a syntax error.

• OPEN MESSAGE ERROR: an error in the syntax of the OPEN message or a rejection of the value of the Hold Timer has been detected.

• UPDATE ERROR MESSAGE: An error in the UPDATE message was detected as a syntax error.

• HOLD TIMER EXPIRED: the Hold Timer has expired, and neighborhood session is closed.

• FINITE STATE MACHINE ERROR: a procedural error occurred.

• CEASE: to close a connection to another router in a circumstance not taken care of by the previous messages.

IDRP (Inter domain Routing Protocol)

Estimates planned departure Internet would consist of dozens of networks and hundreds of machines. These figures have been multiplied by 10, 100 and 1000 for networks and by 1000, 10 000 and 100 000 for the machines. These gear ratios are not the only developers of Internet success. The measurements show that the flow passing over the network goes far beyond that represented by all telephone words exchanged worldwide.

Such an explosion is the question of the capacity of the routing mechanisms to bear the load. To reduce the risk of saturation and extend the current arrangements, the immediate solution is to generalize the subnetting. The subnetting is to give a special joint address, subnet mask, to all stations participating in the same logical network, even if the IP address of the logical network stations are from different subnets. This allows routing tables to grow more slowly.

In the IPv6 environment, a new protocol, IDRP, the result of studies on the routing between routing domains (routing domain) by ISO, was adapted to the internet world to achieve routing between autonomous systems. The role of IDRP is slightly different from that of protocols operating within a domain, as it defines a policy routing between autonomous systems and not only a routing algorithm. The policy defined in this proposal leads routers in an autonomous system to agree to, for example, do not go through a particular area or not allow other autonomous systems to send IP packets to a standalone system determined. In other words, there must be consultation between routers to provide only the information corresponding to the defined policy.

The OSPF or RIP routing algorithms kind applied by routers that have the same goal: finding the best possible route, minimizing the number of jump, the time of crossing the network, or by optimizing the transport capacity. These algorithms are based on notions of weight if the links have weight or the path taken is the one for which the sum of the weights of links traversed is lowest. The IDRP routing also aims to find the right paths, but with restrictions for each autonomous system. The algorithm based on distance vectors (Path Vector Routing), taking into account the end-to-end path in addition to the weight to go to neighboring nodes.

As the number of autonomous systems can grow rapidly with increasing routers processing capabilities, it was decided to group the autonomous systems in confederations. The IDRP protocol works on the routing between these confederations. To convey routing information, IDRP uses specific packets carried in IP packets. In the IP area, the Next header field has the number 45 indicates the IDRP protocol.