6. 1 Dynamic Routing Protocols

The routing table of each router in a network has to be populated. This can be achieved using manual entry of information, and is called static routing. In a relatively large network, this is a slow and time consuming process as the network topology changes, routing table entries has to be updated.In general static routing leads to the network not responsive to dynamic chsanges to its topology.

To keep pace with network topology changes many schemes to dynamically update routing table entries has been adopted. Some of these schemes are proprietary whilst others are standards based, and are presented below. The goal of dynamic routing is for each router to advertise its routing information to all other routers. The protocol concerned then populates the routing table based on the criteria of each protocol.

It is important to understand that routing protocol is not part of OSI layer 3, but helps to modify the information of the router's routing table. Routing protocols uses IP datagrams to exchange information between peers.

The diagram below depicts what routing protocols are typically used where.

Each IP based network on the above diagram called an Administrative System (AS) is controlled by an individual organisation or a service provider. In a path between the source and the destination, IP datagrams may traverse several AS networks. BGP is used to exchange external networks routing information between Administrative Systems. Typically routers on the edge of AS networks will run BGP. Internal routers and edge routers in a network runs IGP. RIP is an example of IGP and runs on internal routers and network server hosts (usually Linux and UNIX). ARP is run on hosts and gateways that are connected on a shared medium such as an Ethernet. ARP provides address resolution mapping for IP addresses and shared media MAC addresses.

Dynamic routing algorithms fall into two main groups. These are referred to as distance vector and link state based routing protocols.

6.1.1 Distance Vector Protocol

In a distance vector based algorithms, periodically each router transmits to its neighbours information it has in its routing table (that is the prefix, distance associated with that prefix and the routers interface IP address). Examples of distance are link bandwidth, delay, cost, number of router hops. The receiving router acts on this information and updates its routing table if a lower cost route is found than it currently has. The receiving router at the next periodic update interval sends its routing table information to all neighbours except for the routes information it learned from that neighbour. Each router also maintains a refresh period for all dynamic routes it has learned. If no information concerning a particular route is refreshed within this period, the particular route is flushed from the routing table. For routes which information is received, the refresh timer is reset.

Depending on the size of the network, in terms of routers and subnets, the amount of routing information update traffic generated by distance based routing protocols can be considerable. Therefore a limit on the size of network usually based on the hop count is implemented. This limits the number of serial hops a path can take. The size of network also impacts on the amount of router memory required for routing table entries.

Topology changes in the network can take considerable time to propagate throughout the network as the basic technique used to reflect changes are only updated at the router’s periodic refresh time. Each protocol type may use different techniques instead of the basic to minimise the propagation time. The time taken for the network to reach a steady state is called the protocol convergence period.

With link state protocols, the idea is for each router to flood the entire network with the state information of its attached links once. This is achieved by a router advertising link state information to its attached neighbours. Each neighbour then stores this information in its link state database and then forwards the received advertisement to its neighbours. In this way each router builds its own topology of the whole network. Once the topology is built, each router then calculates the shortest path to each destination prefix and populates the routing table.

Since in principle there are no periodic updates of link states and changes to network topology are updated as incremental, the network traffic generated by the routing algorithm is very minimal. Since incremental changes are advertised within a short period of time, this makes protocol convergence very fast.

However link state protocols are complex and additional processing power and storage is required at each router to store link state information and generate the routing tables.

RIP is based on the distance vector principles. It is the first protocol that was standardised Internet Engineering Task Force (IETF) for use on IP based networks. Distance metric used with RIP is the hop count. During a periodic update, a router receiving information first increments the hop count and then compares it with that already stored in the routing table. The routing table is only populated if the received information is better than already in the routing table, that is the hop count is less. If after incrementing the hop count is 16 or more the routing information is discarded.

Because of the hop count limitation, RIP is only suitable for small networks. If the network configuration changes it takes a considerable time for the information to be consistent on all routers, hence there is potential for transient loops.

Because decision is based on the minimum hop count, in some configuration it leads to problems. One such example is depicted below:

In the above configuration using RIP, datagrams destined to C will always be forwarded on 64Kbs as there is only one hop, compared to 2 hops via router B. Because of a data rate of 2 Mbs, routing via B would be a better choice.

OSPF is a link state protocol and was developed by the Internet Engineering Task Force (IETF) as an intended replacement for RIP.

OSPF uses different packet types to maintain link state database. These packet types use a format called Link State Advertisement (LSA). There are several types of LSAs that are specific to different type of information required in the link state database.

OSPF can be used on small networks as well as very large corporate networks. It is complex protocol to implement and on large networks it can generate a large amount of link data that has to be maintained by each router.

At the cost of setup complexity, the network can be sub divided into a number of areas and the routers are configured accordingly to reflect the topology. There are several area and router types and are depicted below:



6.3.1 Backbone Area

In OSPF terms there is a backbone area. All other areas a connected to this area, either physically or through virtual links. The backbone area is used for carrying routing traffic information between areas that enables routers to setup and maintain routing tables. A router that connects two or more areas together is called an Area Border Router (ABR). A backbone area connected to another area implies an ABR is employed between them.

A normal area is an area that can receive all kinds of routing information from the ABR including information on external networks that are not part of the AS. The normal area can also be connected to external networks. The router that makes this possible is called an Autonomous System Border Router (ASBR). External networks may not be running OSPF, hence the ASBR need to run other routing protocols in addition to OSPF. The ASBR floods external networks routing information to all AS areas except the stub area.

There are several versions of stub areas depending on the type of routing information that can be carried.

In general a normal area whose IP packets leave only through one router to the backbone area can be configured as a stub area on the ABR router. Since there is only one exit router, there is no need for all the internal routers in the stub area to contain external networks routing information. Instead a default route is assigned for all external networks traffic, thus extensively reducing the CPU load and memory required for link state database and routing tables.

Stub Area Variations are described below.

Link states are advertised throughout the network using LSAs. There are several types of LSAs and they are described below.

To avoid this situation all routers elect a designated router and each router then forms an adjacency with this elected router. The designated router is responsible for advertising the common media link information as Type 2 LSA to the rest of the area. The Type 2 LSA also includes the IP address of each router connected to the common media. A backup designated router is also elected. In the event of designated router failure, the backup takes over and another backup is elected.

Each router advertises other LSA types to its adjacent routers, that also include the designated router. The designated router floods the received LSAs to its other adjacent routes that also include other attached routers on the common segment.

Type 3 - Summary LSA
The scope of type 1 and 2 LSA is within the area. To propagate network prefixes within the area to other areas make use of Type 3 LSA. The Area Border Router (ABR) generates the prefix and distance information (relative to itself) and advertises this to the backbone area using Type 3 LSAs. The other backbone routers use this information together with Type 3 LSAs it received from other ABRs to generate shortest path prefix and distance information (relative to the ABR concerned). The specific ABR then advertises this information into its attached areas (not the backbone) using Type 3 LSAs.

Routers in the area use Type 3 LSA information and add its distance to the ABR with the distance in the Type 3 LSA for each network prefix. The router then stores this prefix vector in its routing table. In this way network routes to other areas in the AS are learned and the routing table updated.

EIGRP is a Cisco Inc. proprietary protocl that combines the concepts of diatance vector and link state protocols.

This section not ready for publication





6.5 Border Gateways Protocol

When networks in different autonomous areas are connected together, such as the Internet, routers are required to exchange routing information between these networks. Because these networks are managed by different organisations, specific topology information is usually confidential, therefore is not advertised. For this and other reasons, distance information is not available, hence some other information is required. This is usually the AS number allocated to an autonomous system.

Autonomous System (AS) is independent and can run its own internal routing protocols. For example each AS in the above diagram is running RIP, OSPF and IS-IS.

Routers that connect external networks are referred to as border gateways. The routing protocol for IP networks is Border Gateways Protocol 4 (BGP 4). Each external network may have several border gateways, hence they may have to be connected together using internal routers. To cope with this requirement, the BGP protocol is divided into Internal and External BGP commonly referred to as IBGP and EBGP.

A BGP router transmits and receives packets from other AS BGP routers. When a router transmits a packet to a BGP router in some one else’s AS, traffic is referred to as egress. When it is received it is called ingress.

With BGP a facility to incorporate policy is required as this will enable different organisations to agree on type of information that can be carried or rejected across their networks. In BGP, each external network prefix can have several attributes associated with it. Policy can be implemented with attributes. Some attributes are mandatory whilst others are optional. The AS number is a mandatory attribute and is added to each route packet by the BGP router connected to the other external network. By having this AS attribute, loops can be detected. For example when routing information packet is received by the ingress router, it checks to see if its AS number is included in the prefix’s list of AS numbers. If it is then this packet is rejected.

AS number is only added by the egress router. If it was added by the ingress router, then when the routing information reaches the egress router, it would drop the packet, as both routers will have the same AS number. This is an example where the functionality between the IBGP is different from EBGP.

BGP is modelled on distance vector methods, which means periodically all or part of the routing table has to be transmitted to all its neighbours. With large complex networks, the routing table of a router could have hundreds of thousand entries. This could mean the network could be overwhelmed with routing traffic. To avoid this BGP only transmit incremental changes, this means very little routing information is exchanged under a steady state condition. If a new BGP router is brought into service, BGP simply asks for an entire routing table update from its neighbour. Since this update is local between two adjacent routers, it will not affect the network.

As can be seen from the above diagram, two BGP routers can have several internal routers, which may lead to loss of routing packets. To avoid this, designers of BGP decided to use TCP connection between two BGP routers for reliable transfer of information. One problem with TCP is that if no packets are flowing over a TCP connection nothing happens even if a physical link goes down, which means BGP will not be aware of this and packets could be routed to nowhere. To overcome this BGP sends small hello packets over the TCP connection. If hello packets are not acknowledged by the far end, TCP disconnects. Through this mechanism BGP may be able to reroute traffic.