Link State Routing Protocol Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Autonomous Systems can be grouped into three categories. They are categorized according to their connectivity and operating policy.

A Multihomed Autonomous System is an Autonomous System that is connected to more than one AS. The advantage of a multihomed Autonomous System is that it allows an AS to remain connected to the Internet in the event of a failure of one of the connections. In a Multihomed Autonomous System traffic from one AS is not allowed to pass through to another AS.

A Stub Autonomous System is an Autonomous System that is connected to only one AS.

A Transit Autonomous System is an Autonomous System that provides connections through itself to other networks.

Interior Routing Protocols

An interior gateway protocol (IGP) is a routing protocol used within an Autonomous System (AS). The interior gateway protocols can be divided into two categories;

Link-state routing protocol

In Link-state routing protocols, each node has information about the network topology and therefore each node is able to calculate the next best hop for every possible destination in the network using the information of the topology. This collection of the next best hops forms the routing table for the particular node. The following are examples of Link-state routing protocols;

Open Shortest Path First

Open Shortest Path First (OSPF) is a link-state routing protocol that operates within a single autonomous system. OSPF routes Internet Protocol packets within a single routing domain (within a single autonomous system). It gathers link state information from available routers and constructs a topology map of the network. The routing table is presented to the Internet Layer which makes the routing decisions based on the destination IP address that is found in IP datagrams. OSPF also supports variable-length subnet masking (VLSM) or Classless Inter-Domain Routing (CIDR) addressing models. Open Shortest Path First uses Dijkstra's algorithm, a shortest path first algorithm to determine the shortest path tree for each route.

Routers at each end of a point-to-point telecommunication link form adjacencies when they detect each other. This detection occurs when a router identifies itself in a hello Open Shortest Path First protocol packet. This is called the two-way state. The routers in a network select a designated router (DR) and a backup designated router (BDR) which acts as a hub to reduce traffic between routers. Open Shortest Path First uses both unicast and multicast to send hello packets.

The following are the areas that an Open Shortest Path First domain is divided into;

Backbone area

The backbone area is also known as area 0 or area and it forms the core of an Open Shortest Path First network. It is the logical and physical structure for the Open Shortest Path First domain. The backbone area is responsible for distributing routing information between the non-backbone areas.

Stub area

A stub area is the area which does not receive route advertisements that are external to the autonomous system. Routing within the stub area is along a default route.

Not-so-stubby area

A not-so-stubby area (NSSA) is a type of stub area that can import autonomous system external routes and send them to the other areas, but it cannot receive them.

Transit area

A transit area is the area with two or more Open Shortest Path First border routers. It is used to pass network traffic from one area to another.

Open Shortest Path First defines the following router types:

Area border router

An area border router (ABR) connects one or more areas to the main backbone network.

Autonomous system boundary router

An autonomous system boundary router (ASBR) is connected to more than one autonomous system. The autonomous system boundary router exchanges routing information with routers in other autonomous systems.

Internal router

An internal router is a router that has Open Shortest Path First neighbor relationships with interfaces that are in the same area.

Backbone router

Backbone routers are all the routers that are connected to the Open Shortest Path First backbone.

Intermediate system to intermediate system

Intermediate system to intermediate system (IS-IS) is a protocol used by routers to determine the best route to forward datagrams through a packet-switched network. This process is called routing. Intermediate system to intermediate system is used within an administrative domain. Intermediate system to intermediate system operates by flooding the topology information throughout a network of routers. Each router builds its own picture of the network topology. The Dijkstra's algorithm is used to compute the best path through the network.

Distance-vector routing protocol

Distance-vector routing protocol use the Bellman-Ford algorithm. Since each router does not have information concerning the full network topology, it advertises its distances to other routers and receives similar advertisements from other routers. Using these received routing advertisements each router populates its routing table. In the next advertisement cycle, the router advertises the updated information from its routing table. This advertisement cycle process continues until the routing tables of each router have stable values. The main disadvantage of these protocols is slow convergence. The following are examples of Distance vector routing protocol;

Routing Information Protocol

Routing Information Protocol (RIP) is a dynamic routing protocol used in local and wide area networks and uses the distance-vector routing algorithm. The distance-vector routing algorithm used in RIP is the Bellman-Ford algorithm, which was first used in 1967 in a computer network, as the initial routing algorithm of the ARPANET.

Routing Information Protocol is a distance-vector routing protocol which uses the hop count as a routing metric. Routing Information Protocol prevents routing loops because it implements a limit on the number of hops that are allowed in a path from the source to the destination. The maximum number of hops allowed is 15. Routing Information Protocol prevents the propagation of incorrect routing information by implementing the split horizon, route poisoning and hold-down mechanisms. Routing Information Protocol is implemented on top of User Datagram Protocol. The reserved port number is 520.

Interior Gateway Routing Protocol

Interior Gateway Routing Protocol (IGRP) was invented by Cisco and is used by routers to exchange routing data within an autonomous system. Interior Gateway Routing Protocol was mainly created to overcome the limitations of Routing Information Protocol. Interior Gateway Routing Protocol supports multiple line metrics for each route. The maximum hop count of Interior Gateway Routing Protocol-routed packets is 255 and the default is 100. The routing updates are broadcast every 90 seconds.

Enhanced Interior Gateway Routing Protocol

Enhanced Interior Gateway Routing Protocol (EIGRP) was invented by Cisco. Enhanced Interior Gateway Routing Protocol minimizes the routing instability that occurs after topology changes and the use of bandwidth and processing power in the router.

Data collected by the Enhanced Interior Gateway Routing Protocol is stored in three tables;

Neighbor Table stores the data about the neighboring routers.

Topology Table contains the aggregation of the routing tables gathered from all directly connected neighbors.

Routing table stores the actual routes to all destinations.

Exterior Routing Protocols

Exterior Gateway Protocol (EGP) is a simple reachability protocol. Border Gateway Protocol (BGP) is the accepted standard for Internet routing.

Border Gateway Protocol

Border Gateway Protocol (BGP) is a core routing protocol of the Internet. Border Gateway Protocol maintains a table of IP networks which designate network reachability among autonomous. It is also called a path vector protocol. Border Gateway Protocol was mainly created to replace Exterior Gateway Protocol to allow a complete decentralized routing for the removal of the NSFNet Internet backbone network.


When a class address is divided into a number of smaller networks each with a number of hosts, The smaller networks are called subnets. The process in which the host field is split into a subnet is called subnetting. The boundary between the subnet and host fields can be between two bits and this is decided using a subnet mask. The IP address now has a three-level hierarch; the NetID which is the main network site, the SubNetID which is the physical subnet and the HostID which points the connection of a host to a subnetwork. Purposes of subnetting include organization, control network traffic, different physical media usage, preservation of address space, and security.

A simple way to subnet is to take the octet in the subnet mask that covers the first unassigned octet in the IP address block and make all its bits high (a high bit is a 1).

The following are the seven main steps needed to calculate a subnet;

Determining Number of Subnets Needed

Determining Number of Bits You Can Borrow

Determining Number of Bits You Must Borrow to Get Needed Number of Subnets

Turning On Borrowed Bits and Determining Decimal Value

Determining New Subnet Mask

Finding Host/Subnet Variable

Determining Range of Addresses

Determine the network class (A, B or C) based on IP address;

If an IP address begins with 1 to 126 then it is Class A.

If an IP address begins with 128 to 191 then it is Class B.

If an IP address begins with 192 to 223 then it is Class C.

For example, For the IP address the network is class C since the IP address start with 192.

Determine number of bits needed to define subnets.

Using the following formulas the number of bits are calculated.

Number of subnets = (2^Number of bits) - 2.

Number of bits = Log2 (Number of subnets + 2).

For example, if there are six subnets:

Number of bits = Log2(6 + 2) = Log2(8) = 3.

Therefore three bits in the IP address are used for the subnet.

Compose the subnet mask in binary form by extending the default subnet mask with subnet bits. Default subnet mask for the different classes are as follows;

11111111.00000000.00000000.00000000 (Class A, network part is 8 bits)

11111111.11111111.00000000.00000000 (Class B, network part is 16 bits)

11111111.11111111.11111111.00000000 (Class C, network part is 24 bits)

For example, the extension of the default class C subnet mask with 3 bits results in the subnet mask


Using the following set of rules convert the binary subnet mask to the decimal-dot form. The binary form contains four octets (8 bits in each).

For 1111111 octet, the decimal is 255 and for 00000000 octet, the decimal is 0.

If the octet contains both 1 and 0 the formula is used;

Integer number = (128 x n) + (64 x n) + (32 x n) + (16 x n) + (8 x n) + (4 x n) + (2 x n) + (1 x n)

For the above example 11111111.11111111.11111111.11100000

11111111 ---> 255

11111111 ---> 255

11111111 ---> 255

11100000---> (128 x 1) + (64 x 1) + (32 x 1) + (16 x 0) + (8 x 0) + (4 x 0) + (2 x 0) + (1 x 0) = 224

Subnet mask is