Routing protocols

Routing protocols
All routing protocols can be separated into two categories: Distance-Vector and Link- State. These two categories are defined by the algorithms that are used to calculate the best route.

Distance-vector routing protocols:
Uses metrics (hop counts) to determine the best route. Updates are broadcasted every 30 seconds. During this broadcast the router sends its routing table to the neighbor routers. To prevent routing loops, Distance-vector protocols are limited to 15 hops. If the destination network is more then 15 hops away (separated by more than 15 routers, the packet will be dropped) .

Link-state routing protocol
Uses the combination of metrics and bandwidth to determine the best route. In addition to routing table, the router builds and maintains a topology map of the network. Router use LSP (link state packets) broadcasts to send routing information to other routers. Updates are broadcasted every 2 hours. Link-state protocols can make more accurate routing decisions. Link-State protocols require more processing power and RAM than Distance-vector protocols.

Balanced Hybrid
is a combination of the Distance-vector and Link-State protocols. Balanced Hybrid routing protocols can calculate the best route more accurately than Distance-Vector with less overhead than Link-State protocol.
A Cisco router can be configured to use more than one routing protocol at the same time and can maintain routing tables for many different routing protocols simultaneously.

Distance-Vector protocols

RIP - Routing information protocol
RIP is a distance vector protocol. Suitable for small and medium size networks. Low overhead, simple to implement. The main limitation is 15 hops maximum (can't route through more than 15 routers). To start RIP on the router, type router rip from the router configuration mode, and then add network number that you want RIP to advertise. For example, Router(config-router)#network 122.122.0.0There are different version of RIP- RIP1, RIP2, and newer RIPng designed to be compatible with IPv6. Different versions of RIP are incompatible with each other. RIP version number is included in the RIP packet. RIP sends a copy of a routing table to other routers on the network every 30 seconds. The receiving router compares the routing table it receives from neighbor router with its own routing table, and if it detects changes, updates its routing table and sends updates to another neighbor router.When the router configured with RIP first starts up, it issues a request broadcast requesting the initial routing information from the neighbor routers.RIP is defined in RFC 1058 and RFC 1723.

IGRP - Interior Gateway Routing Protocol
IGRP is a Cisco's proprietary protocol initially introduced in 1988. Just like RIP, IGRP relies on broadcasts to update routing tables. There are many important differences between IGRP and RIP that make IGRP a much more advance routing protocol.Maximum hop counts is 255. In addition to hop count, IGRP uses Composite metrics: bandwidth, reliability, load, delay values to determine the best route. These values can be adjusted by the administrator. Updates are sent every 90 seconds to neighbor routers.Multipath routing - a data can be split end send over multiple links. This increases fault tolerance and provides more throughput.IGRP is suitable for large networks with complex topologies.To enable IGRP, type router igrp [autonomous system number]. For example, router igrp 100 will enable IGRP on the router and will assign the autonomous system number of 100. Then, from the router configuration prompt enter the network number that you want the router to advertise. For example: Router(router-config)#network 222.122.122.100

Link state protocols

OSPF - Open Shortest Path First
Link state protocol, developed by IETF for use on the Internet. OSPF is a very complex protocol with high overhead. Advantages of OSPF: More precise computation of the best route, ability to split network traffic between multiple paths, fast convergency.Link state routing tables are broadcasted only when the change (or link failure) is detected by a router.Support for Variable Length subnet masks. This means that unlike the RIP that only understands the major network numbers, OSPF can be used to route traffic between subnets.Support for broadcast networks (Ethernet, Token ring) and non-broadcast networks (ATM, x.25)OSPF protocol runs on top of IP protocol and consists of 3 subprotocols: Hello, Exchange, Flooding. Flooding protocol is used to transmit updates when change in topology is detected by a router responsible for the link. Database updates are transmitted in an encrypted form. OSPF messages can be secured by a password.OSPF routers exchange information with other OSPF routers within the same autonomous system, but can also be configured to send and receive updates from other autonomous systems.

EIGRP
Enhanced Interior Routing Protocol. Cisco's proprietary routing protocol, an improved version of IGRP. EIGRP uses "Distributed update algorithm" or "DUAL", it combines the Link-state and Distance-Vector algorithms. EIGRP is considered balanced hybrid protocol. Unlike IGRP that only understands major network numbers, EIGRP can be configured to use subnet masks and supernet masks. The format of the EIGRP routing table is different from IGRP routing table.Advantages of EIGRP are: Fast convergence, Support for multiple protocols, requires less bandwidth than Distance-vector protocols because only partial updates are broadcasted and only when changes in topology are detected. EIGRP does not use periodic broadcasts. Improved loop detection and prevention.

EGP
Exterior Gateway Protocol is a Distance-Vector protocol. EGP was designed to enable the exchange of routing information between different Autonomous Systems (AS) An AS is a set of routers and networks under the same administration. All parts of an AS must remain connected. Normally, routers in the AS only exchange routing information with other on the same AS. The purpose of the EGP is to exchange routing information and reachability information between Autonomous Systems.EGP has three procedures:Neighbor acquisition - determines whether 2 adjacent gateways agree to become neighbors. Neighbor Acquisition is a "two-way handshake" Becoming neighbors means that 2 Autonomous Systems agree to relay each other's traffic. An administrator defines the set of routers that can define a list of potential neighbors. The router will then accept a neighbor acquisition request only with members on the list. If a router receives a request from a router that has not been configured as a potential neighbor, it will reply with a Neighbor Acquisition Refusal. Neighbor Acquisition can also be refused if the router has ran out of memory and does not have enough space for extra routing table.Neighbor reachability - the procedure in which a router sends "hello" packets and another router suppose to reply with "I hear you" packets. Network administrator can configure the frequency of "hello" packets. The normal frequency is 30 seconds. One neighbor router can be configured to only send "hello" packets and another to only send "I hear you" packets. Also both routers can be configured to send both "hello" and "I hear you" packets.Network reachability - the procedure in which neighbor routers exchange the list of networks that can be reached through each neighbor. This information is used to update the routing tables in each of the Autonomous Systems. The EGP router polls its partner for a list of available networks.EGP was developed in 1982-1984, and is not capable of handling today's complex topologies. It is being replaced by the BGP. EGP cannot detect and prevent routing loops and heavily depends on the manual configuration by the administrator.

BGP - Border Gateway Protocol

Was designed to replace the EGP. The design started in 1989, and the most recent version is BGP-4. BGP uses "Path Vector" instead of "Distance Vector". Path Vector enable detection and prevention of loops in complex topology.BGP runs over TCP, and relies on TCP for error checking and resequensing packets.BGP-4 supports Classless Inter-Domain Routing (CIDR). Concept of CIDR is to have IP address and subnet mask independent of the IP address class. CIDR is the concept behind supernetting. In supernetting several class C addresses can be combined into one subnet. This solves the problem in which a medium size network needs more than one class C network (more than 254 hosts), but does not need class B address. By combining several adjacent class C addresses into one network address, only one additional entry has to be made in the routing table. Routing updates are sent only when change in topology is detected.BGP can be used to connect Autonomous Systems, to relay routing tables between Autonomous Systems , and can also be used for routing within Autonomous Systems.Running BGP requires a lot of manual configuration.

Potential problems with routing protocols.
Routing Loops
Routing loops occur when routing tables are not updated fast enough when one of the networks becomes unreachable. Due to the slow convergence (updates of routing table between all routers), some routers will end up with incorrect routing table and will broadcast that routing table to other routers. This incorrect routing tables will cause packets to travel repeatedly in circles.

Counting to infinity
Counting to infinity happens when packets end up in a routing loop. The hop count increases with every pass through a router on the network.

Solutions

Defining the maximum number of hops
When the number of hops reaches this predefined value, the distance is considered infinite and the network considered unreachable. This will not stop routing loops, but only limit the time that packet can travel inside the loop.
Split horizon
The packets can not be send back to the same interface that they originally came from. During the updates, one router does not send updates to the router that it received the information from.
Route poisoning
The router sets the cost of infinity for the unreachable network.
Split horizon with poisonous reverse
Combination of split horizon and route poisoning.
Triggered updates
The router sends updates of the routing table as soon as it detects changes in the network.
Hold-Downs
After the router detects unreachable network, the routers waits for a specified time before announcing that a network is unreachable. The router will also wait for a period of time before it updates its routing table after it detects that another router came online. Hold-downs can only partially prevent counting to infinity problem.