IT Computer Networks Lab Lab 9 OSPF Routing Protocol Solution

    1. Introduction

In order to transfer packets from a sending host to the destination host, the network layer must determine the path or route that the packets are to follow. Routing is usually performed by a dedicated device called a router. Routing is a key feature of the Internet because it enables messages to pass from one computer to another and eventually reach the target machine. Each intermediary computer performs routing by passing along the message to the next computer. At the heart of any routing protocol is the algorithm that determines the path for a packet. The purpose of a routing algorithm is simple: given a set of routers, with links connecting the routers, a routing algorithm finds a "good" path from source to destination. Typically, a good path is one that has the least cost.

Broadly, one way in which we can classify routing algorithms is according to whether they are global or decentralized.

1.1.    Global Routing Algorithm:

It computes the least-cost path between a source and destination using complete, global knowledge about the network. That is, the algorithm takes the connectivity between all nodes and all link costs as inputs. This then requires that the algorithm somehow obtain this information before actually performing the calculation. The calculation itself can be run at one site or replicated at multiple sites. The key distinguishing feature here, however, is that a global algorithm has complete information about connectivity and link costs. In practice, algorithms with global state information are often referred to as link-state (LS) algorithms, since the algorithm must be aware of the cost of each link in the network.

1.2.    Decentralized Routing Algorithm:

In a decentralized routing algorithm, the calculation of the least-cost path is carried out in an iterative, distributed manner. No node has complete information about the costs of all network links. Instead, each node begins with only the knowledge of the costs of its own directly attached links. Then, through an iterative process of calculation and exchange of information with its neighboring nodes, a node gradually calculates the least-cost path to a destination or set of destinations. The decentralized routing algorithm are often referred to as
distance-vector (DV) algorithm, because each node maintains a vector of estimates of the costs (distances) to all other nodes in the network.



    2. OSPF Routing Algorithm

The OSPF protocol is a link-state routing protocol, which means that the routers exchange topology information with their nearest neighbors. The topology information is flooded throughout the AS, so that every router within the AS has a complete picture of the topology of the AS. This picture is then used to calculate end-to-end paths through the AS, normally using a variant of the Dijkstra algorithm. Therefore, in a link-state routing protocol, the next hop address to which data is forwarded is determined by choosing the best end-to-end path to the eventual destination.

Each OSPF router distributes information about its local state (usable interfaces and reachable neighbors, and the cost of using each interface) to other routers using a Link State Advertisement (LSA) message. Each router uses the received messages to build up an identical database that describes the topology of the AS.

Steps in Formation of OSPF Routing Table:

    I. OSPF- speaking routers send Hello packets out all OSPF-enabled interfaces. If two routers sharing a common link agree on certain parameters specified in their respective Hello packets, they will become neighbors.

    II. Adjacencies which can be thought of as of virtual point to point links are formed between some neighbors . OSPF defines several network type and several router type, the establishment of an adjacency is determined by the type of routers exchanging Hellos and the type of network over which the Hellos are exchanged.

    III. Each router sends Link State Advertisement (LSA’s) overall adjacencies. The LSA’s describe all the routers links, or interfaces , the router’s neighbors and the state of links.

IV.

Each router receiving an LSA from a neighbor records the LSA in its link- state database and sends a copy of the LSA to all of its neighbors.

    V. By flooding LSA’s throughput an area, all routers will build identical link-state database.

VI.
When the database are complete, each router uses the SPF algorithm (Dijkstra

algorithm) to calculate a loop-free graph describing the shortest  path to every

known destination, with itself as root. This graph is SPF.
VII.
Each router builds it tree from SPF tree.

    3. Analyzing working of OSPF routing


3.1.    Experiment

Create the following Scenario.























Step-1: Click and drop Routers, Wired nodes and links them as shown in above figure.

Step-2: Set properties on Router A: Go to Application layer and Select Routing Protocol to OSPF.

Step-3: create a CBR application (By default) from source node G to destination

H.

Step-4: Node Properties: In wired Node G, go to transport layer and Disable TCP.

Step-5: set the properties of links as given in a and b in turn .

Step-6: Run simulation for 10 seconds.

Step-7: Observe the animation, analyse the OSPF packets exchanged and path

taken by data packets for these two scenarios. Answer the following questions.

a.    Set link's Properties:

Link
L1
L2
L3
L4
L5
L6
L7








Uplink
100
100
100
100
100
100
100
speed















b.    set Link's properties:

Link
L1
L2
L3
L4
L5
L6
L7








Uplink
100
100
100
100
100
10
10
speed
















3.2. Exercise

    1) Explain the packets used in OSPF: LSR, LSA, D-D, LSU and Hello packet.

            i) Is it exchanged between neighbours or all routers?

            ii) What is its use?

            iii) What is the time duration of its exchange in theory? Write time duration you observed during your simulation [Hint: use Packet trace]?

iv)Explain the core fields of the packet.[Hint: Refer 5.1]

        2) What is the cost of each link in each scenario? [Hint: See the router's table]

        3) How the cost is calculated in NetSim?[Hint: Refer 5.2]

        4) What is the total cost of two paths in each scenario? Show the cost of each link in a graph.

        5) Write your observation from the two scenarios.

3.3. Create the following scenario and set the properties of links.


























-

Link
L1
L2
L3
L4
L5
L6
L7
L8
L9
L10
L11












Uplink
10
10
10
10
10
10
10
20
20
20
20
speed
























    I. What is cost for all three paths?

        II. What path the data packets take and why? Explain in detail.


    4. Question Set

4.1.    Answer the following:

    I. Does all the interfaces of routers belong to same network or different network? List down all interfaces of Router A and Router C of exercise 3.3 .

    II. Does the router sharing same link belong to same network or different? Observe for any link and write down their Network IP address .

4.2.    Observe and list down parameters of Routing table in detail.


    5. References

5.1.    For types of message:

https://sites.google.com/site/amitsciscozone/home/important-tips/ospf/ospf-packet

-types

5.2.    The link Cost is calculate using following formula link-Cost = (Reference Bandwidth) / (UpLink Speed) Where Reference bandwidth =100Mbps