Routing Algorithms

 

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).

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.

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.

• 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.

• 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.

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.

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.

 

Hierarchical Routing

Because of the global nature of Internet system, it becomes more difficult to centralize the system management and operation. For this reason, the system must be hierarchical such that it is organized into multiple levels with several group loops connected with one another at each level. Therefore, hierarchical routing is commonly used for such a system.

1. A set of networks interconnected by routers within a specific area using the same routing protocol is called domain.
2. Two or more domains may be further combined to form a higher-order domain.
3. A router within a specific domain is called intra-domain router. A router connecting domains is called inter-domain router.
4. A network composed of inter-domain routers is called backbone.

Each domain, which is also called operation domain, is a point where the system operation is divided into plural organizations in charge of operation. Domains are determined according to the territory occupied by each organization.

Routing protocol in such an Internet system can be broadly divided into two types:

1. Intra-domain routing

2.    Inter-domain routing

Each of these protocols is hierarchically organized. For communication within a domain, only the former routing is used. However, both of them are used for communication between two or more domains.

In the following pages, we will look at description of Routing information Protocol (RIP), Open Shortest Path First (OSPF), and IS-IS, that are intra-domain protocols. RIP and OSPF will be covered later in detail.