TCP/IP-II:Internet Routing Protocols

Internet Routing Protocols

• The job of the internet routing protocols is to determine the path taken by a datagram between source and destination.
• The Global Internet consists of Autonomous Systems (AS) interconnected with each other. An Autonomous system (AS) is loosely defined as a set of routers or networks that are administered by a single organization.
• There is no restriction that an AS should run a single routing protocol within the AS.

There are three categories of Autonomous system (AS’s)

•  Stub AS: small corporation: one connection to other AS’s
•  Multihomed AS: large corporation (no transit): multiple connections to other AS’s, it carries only local traffic and does not support transit traffic.
•  Transit AS: provider, it has multiple connections to the outside world and can carry transit and local traffic.

Intra-AS Routing

• Also known as Interior Gateway Protocols (IGP)
• Most common Intra-AS routing protocols:

o RIP: Routing Information Protocol

o OSPF: Open Shortest Path First

o IGRP: Interior Gateway Routing Protocol (Cisco proprietary)

Routing Information Protocol (RIP)

• The Routing Information Protocol (RIP) is a dynamic routing protocol used in local and wide area networks.
• it is classified as an interior gateway protocol (IGP) using the distance-vector routing algorithm.
• A RIP run on top of UDP, port number 520 is used.
• RIP is a distance-vector routing protocol, Which employs the hop count as a routing metric.
• Suitable for small networks (local area environments)
• The maximum number of hops allowed with RIP is 15, and the hold down time is 180 seconds.
• Value of 16 is reserved to represent infinity, i.e. node is not reachable.
• Small number limits the count-to-infinity problem.
• Originally each RIP router transmits full updates every 30 seconds by default.
• A router expects to receive an update message from each of its neighbors within 180 seconds in the worst case
• If router does not receive update message from neighbor X within this limit, it assumes the link to X has failed and sets the corresponding minimum cost to 16 (infinity)
• Originally, routing tables were small enough that the traffic was not significant.
• RIP implements the split horizon, route poisoning and holddown mechanisms to prevent incorrect routing information from being propagated. These are some of the stability features of RIP.
• RIP is available in two versions, i.e. RIP1 and RIP2.
• In many current networking environments RIP would not be the preferred choice for routing as its time to converge and scalability are poor compared to EIGRP, OSPF
• The hop limit severely limits the size of network it can be used in.
• The periodic routing updates do not carry subnet information, lacking support for variable length subnet masks (VLSM). This limitation makes it impossible to have different-sized subnets inside of the same network class.

Command: - specifies the purpose of the message, two values are defined value 1 requests

the system to send its routing information and values 2 indicates a response containing the routing information.

Version: - two versions, RIPV1 and RIPV2

Address Family Identifier:-identifies type of address used currently only IP address is defined

IP address: - indicates the address of destination, which can be network or host address.

Open Shortest Path First (OSPF)

•  Open Shortest Path First (OSPF) routing protocol is a Link State protocol based on cost rather than hops or ticks (i.e. it is not a vector based routing protocol).
• OSPF is an Interior Gateway Protocol (IGP) Protocol, uses flooding of link state information and Dijkstra’s least-cost path algorithm.
• With OSPF, router constructs a complete topological map of the entire autonomous system. The router then locally runs the Dijkstra’s shortest-path algorithm to determine shortest-path tree to all networks with itself as rootnode.
• The router’s routing table is then obtained from this shortest-path tree.
• At steady state: All routers have same LS database, Know how many routers in network, Interfaces & links between routers, Cost of each link
• Occasional Hello messages (10 sec) & LS updates sent (30 min)

Advantages of OSPF:

• Changes in an OSPF network are propagated quickly.
• OSPF is hierarchical, using area 0 as the top of the hierarchy.
• OSPF is a Link State Algorithm.
• OSPF supports Variable Length Subnet Masks (VLSM).
• OSPF uses multicasting within areas.
• After initialization, OSPF only sends updates on routing table sections which have changed, it does not send the entire routing table.
• Using areas, OSPF networks can be logically segmented to decrease the size of routing tables. Table size can be further reduced by using route summarization.
• OSPF is an open standard, not related to any particular vendor.

Disadvantages of OSPF:

• OSPF maintains multiple copies of routing information, increasing the amount of memory needed.
• Using areas, OSPF can be logically segmented (this can be a good thing and a bad thing).
• OSPF is not as easy to learn as some other protocols.
• In the case where an entire network is running OSPF and one link within it is "bouncing" every few seconds, OSPF updates would dominate the network by informing every other router every time the link changed state.

OSPF Network

• To improve scalability, AS may be partitioned into areas. Area is identified by 32-bit Area ID
• Router in area only knows complete topology inside area & limits the flooding of link- state information to area
•  Area border routers summarize info from other areas, each area must be connected to backbone area (0.0.0.0)
• Distributes routing info between areas

o Internal router has all links to network within the same area i.e. these are in nonbackbone areas and perform only inter-AS routing

o Area border router has links to more than one area that belongs to both an area and backbone.

o Backbone router has links connected to the backbone, these routers perform routing within the backbone, but themselves are not area border routers. Within a nonbackbone area, internal routers learn of the existence of routers of other area from the information broadcast within the area by its backbone routers.

o Autonomous system boundary (ASB) router has links to another autonomous system. ASBR’s learn about routers outside the AS through an exterior gateway protocol such as BGP.

Neighbor & Adjacent Routers

•  Neighbor routers: two routers that have interfaces to a common network
• Neighbors are discovered dynamically by Hello protocol
•  Adjacent router: neighbor routers become adjacent when they synchronize topology databases by exchange of link state information
• Neighbors on point-to-point links become adjacent
• Routers on multi-access networks become adjacent only to designated & backup designated routers
• Reduces size of topological database & routing traffic

Designated Routers

Reduces number of adjacencies

Elected by each multi-access network after neighbor discovery by hello protocol

Election based on priority & id fields

Generates link advertisements that list routers attached to a multi-access network

Forms adjacencies with routers on multi-access

network

Backup prepared to take over if designated router fails

OSPF Operation: - The header format of OSPF is shown in below figure

Each OSPF packet consists of an OSPF header followed by the packet body (data) The description of each field in the OSPF header is given below:

Version: This field specifies the protocol version, current version is 2.

Type: This field specifies the type of OSPF packet. The following types are defined hello, database description, link-state request, link-state update, link-state acknowledgements. Packet length: This field specifies the length of OSPF packet in bytes, including OSPF header.

Router ID: This field identifies the sending router’s ip address.

Area ID: This field identifies the area this packet belongs to. The area ID of 0.0.0.0 is reserved for backbone.

Checksum: to detect errors in packet.

Authentication type and Authentication: Combination of these fields can be used to authenticate OSPF packets.

There are five types of OSPF packets

• Hello Packet
• Database description Packet
• Link-state request Packet
• Link-state update Packet and
• Link-state acknowledgement

The operation of OSPF can be explained in 3 steps.

Step1: Discovery of neighbors can be done by sending hello packets in point-to-point links and designated routers in multi-access networks. The format of hello packet is shown in below figure:-

• To discover, establish and maintain relationships, the OSPF transmit hello packet to each interface periodically, typically for every 10 to 30 sec.
• When a router receives a hello packet, it replies with a hello packet containing router ID of each neighbor it has seen.
• When a router receives a hello packet containing its router ID in one of the neighbor fields, the router is assured that communication to sender is bidirectional.

Step 2: Establishment of adjacent and synchronization of link-state databases

• Once the connection is established between two neighbor routers, the database description packet is used to synchronize their link-state databases
• One router acts as master and other as slave.
• The format of database description is as follows

The function of each field is given below

Step 3: Propagation of OSPF Link State Request and building routing tables

• When a router wants to update the link-state database, it sends a LS request packet to neighbor to update part of its link-state database
• vEach LSA request is specified by the link state type, link state ID, and the advertising router.