Unicast Routing Protocols - Rip, Ospf And Bgp 1s1h5v

COMPUTER NETWORKS 14CS3406

Mukesh Chinta Assistant Professor, CSE, VRSEC

 A protocol needs to define its domain of operation, the messages exchanged, communication between routers, and interaction with protocols in other domains.  The Internet has changed from a tree-like structure, with a single backbone, to a multibackbone structure run by different private corporations today.  The Internet today is made of a huge number of networks and routers that connect them. A single protocol is not sufficient to provide routing for the entire internet because of scalability and istrative problems.

2

▪ Hierarchical routing means considering each ISP as an autonomous system (AS). Each AS can run a routing protocol that meets its needs, but the global Internet runs a global protocol to glue all ASs together. ▪ An autonomous system (AS) is a group of networks and routers under the authority of a single istration. ▪ The routing protocol run in each AS is referred to as intra-AS routing protocol, intradomain routing protocol, or interior gateway protocol (IGP); the global routing protocol is referred to as inter-AS routing protocol, interdomain routing protocol, or exterior gateway protocol (EGP). ▪ Each AS is given an autonomous number (ASN) by the ICANN which is a 16-bit unsigned integer that uniquely defines an AS. The Autonomous systems are categorized according to the way they are connected to other AS’s. - A stub AS has only one connection to another AS. The data traffic can be either initiated or terminated in a stub AS; the data cannot through it. Example is the customer network which is either the source or the sink . A multihomed AS can have more than one connection to other ASs, but it does not allow data traffic to through it. . A transient AS is connected to more than one other AS and also allows the traffic to through. 3

4

⁂ The Routing Information Protocol (RIP) was written by C. Hedrick from Rutgers University in June 1988, and has since become the most common Internet routing protocol for routing within networks. ⁂ RIP is based on the computer program "routed", which was widely distributed with the Unix 4.3 Berkeley Software Distribution (BSD) operating system. ⁂ All RIP routing protocols are based on a distance vector algorithm called the Bellman-Ford algorithm.

⁂ The earliest RIP protocol was the PUP (PARC Universal protocol), which used the Gateway Information Protocol to exchange routing information, and was invented by a team that included R. M. Metcalfe, who later developed the Ethernet physical layer network protocol. ⁂ The PUP protocol was later upgraded to the Xerox Network Systems (XNS) architecture, and named "Routing Information Protocol", usually just called RIP. 5

 RIP routers the cost of reaching different network instead of reaching other nodes to enable a router in an AS to forward a packet to different networks in an AS.  To make the cost implementation simpler, the cost is defined as the number of hops, which means the number of networks (subnets) a packet needs to travel through, from the source router to the final destination host.  In RIP, the maximum cost of a path can be 15, which means 16 is considered as infinity (no connection).

 The routers in an autonomous system need to keep forwarding tables to forward packets to their destination networks 6

☼ A forwarding table in RIP is a three-column table in which the first column is the address of the destination network, the second column is the address of the next router to which

the packet should be forwarded, and the third column is the cost (the number of hops) to reach the destination network.

☼ Although a forwarding table in RIP defines only the next router in the second column, it gives the information about the whole least-cost tree. ☼ The third column is not needed for forwarding the packet, but it is needed for updating the forwarding table when there is a change in the route. 7

 RIP is implemented as a process that uses the service of UDP on the well-known port number 520.  In BSD, RIP is a daemon process (a process running in the background), named routed.  This means that, although RIP is a routing protocol to help IP route its datagrams through the AS, the RIP messages are encapsulated inside UDP datagrams, which in turn are encapsulated inside IP datagrams. RIP runs at the application layer, but creates forwarding tables for IP at the network later.  RIP has gone through two versions: RIP-l and RIP-2. The second version is backward compatible with the first. RIP-2 allows the use of more information in the RIP messages that were set to 0 in the first version.  RIP-2 defines the format of the message as shown. Part of the message, which we call entry, can be repeated as needed in a message. Each entry carries the information related to one line in the forwarding table of the router that sends the message.

8

 Command will always be set to either one, signifying a request message, or two, signifying a response message.  A request message is sent by a router that has just come up or by a router that has some time-out entries.  A request message can ask about specific entries or all entries.  A solicited response message is sent only in answer to a request message. It contains information about the destination specified in the corresponding request message.  An unsolicited response message, is sent periodically, every 30 seconds or when there RIPv2 updates can contain entries for up to 25 routes and is a change in the forwarding table. has a maximum datagram size (with an eight-byte UDP  Metric is a hop count between 1 and 16 header) of 512 octets. 9

 RIP implements the same algorithm as the distance-vector routing algorithm with a few changes to enable a router to update its forwarding table.  Instead of sending only distance vectors, a router needs to send the whole contents of its forwarding table in a response message. The receiver adds one hop to each cost and changes the next router field to the address of the sending router. The received router selects the old routes as the new ones except in the following three cases: 1. If the received route does not exist in the old forwarding table, it should be added to the route. 2. If the cost of the received route is lower than the cost of the old one, the received route should be selected as the new one. 3. If the cost of the received route is higher than the cost of the old one, but the value of the next router is the same in both routes, the received route should be selected as the new one.

 The new forwarding table needs to be sorted according to the destination route. 10

11

RIP uses three timers to its operation: : Each router has one periodic timer that is randomly set to a number between 25 and 35 seconds (to prevent all routers sending their messages at the same time and creating excess traffic). The timer counts down; when zero is reached, the update message is sent, and the timer is randomly set once again. : It governs the validity of a route. When a router receives update information for a route, the expiration timer is set to 180 seconds for that particular route. Every time a new update for the route is received, the timer is reset. If there is a problem on an internet and no update is received within the allotted 180 seconds, the route is considered expired and the hop count of the route is set to 16, which means the destination is unreachable. Every route has its own expiration timer. : It is used to purge a route from the forwarding table. When the information about a route becomes invalid, the router does not immediately purge that route from its table. Instead, it continues to the route with a metric value of 16. At the same time, a garbage collection timer is set to 120 seconds for that route. When the count reaches zero, the route is purged from the table. This timer allows neighbors to become aware of the invalidity of a route prior to purging.

12

The update messages in RIP have a very simple format and are sent only to neighbors; they are local. They do not normally create traffic because the routers try to avoid sending them at the same time. As it uses DVR, convergence is slow for a large domain. But RIP allows only 15 hops in a domain, it should not be a problem. The problems associated with count to infinity and loops are tackled by use of poison-reverse and split horizon strategies. As DVR is used, failure or corruption in one router, the problem will be propagated to all the routers and the forwarding in each router will be affected.

13

OPEN SHORTEST PATH FIRST (OSPF)

 Open Shortest Path First (OSPF) is also an intra-domain routing protocol like RIP, but it is based on the link-state routing protocol.  OSPF is an open protocol, which means that the specification is a public document.

 In OSPF, like RIP, the cost of reaching a destination from the host is calculated from the source router to the destination network. However, each link (network) can be assigned a weight based on the throughput, round-trip time, reliability, and so on.  Each OSPF router can create a forwarding table after finding the shortest-path tree between itself and the destination using Dijkstra's algorithm. Metric in OSPF

Forwarding tables in OSPF 15

 OSPF was designed to be able to handle routing in a small or large autonomous system. But in a large AS, flooding of LSP's creates a huge volume of traffic in a AS.  The OSPF divides or partitions the AS into smaller parts called “areas”. Each area acts as a small independent domain for flooding LSP’s.  OSPF uses another level of hierarchy in routing: the first level is the autonomous system, the second is the area. This reduces the amount of routing traffic that is sent through the AS and also reduces the amount of information a router must maintain about the full AS.



Each router in an area needs to know the information about the link states not only in its area but also in other areas. For this reason, one of the areas in the AS is designated as the backbone area, responsible for gluing the areas together.



The routers in the backbone area are responsible for ing the information collected by each area to all other areas. In this way, a router in an area can receive all LSPs generated in other areas.



For the purpose of communication, each area has an area identification. The area identification of the backbone is zero. 16

 At the border of an area, special router called area border routers are present.  A backbone area combines a set of independent areas into a single domain. The backbone acts as a hub for inter-area transit traffic and the distribution of routing information between areas. Each non-backbone area must be directly connected to the backbone area.  OSPF is based on the link-state routing algorithm, which requires that a router the state of each link to all neighbors for the formation of the LSDB.  In real world, we need different kinds of ments to the existence of different entities as nodes, the different types of links that connect each node to its neighbors, and the different types of cost associated with each link.  We have five types of link-state ments: router link, network link, summary link to network, summary link to AS border router, and external link.

: A router link s the existence of a router as a node. Router Link ments are ed within an area by all OSPF routers and describe the router links to the network. These are only flooded within a particular area.  Along with the address of the announcing router, this type of ment can define one or more types of links that connect the advertising router to other entities.  A transient link announces a link to a transient network, a network that is connected to the rest of the networks by one or more routers.  A stub link s a link to a stub network, a network that is not a through network.  Both the above ments should define the address of the network and the cost  A point-to-point link should define the address of the router at the end of the point-to-point line and the cost to get there. 18

: A network link s the network as a node. Since a network cannot do announcements itself (it is a ive entity), one of the routers is assigned as the designated router (DR) and does the advertising.  In addition to the address the designated router, this type of LSP announces the IP address of all routers. : This is done by an area border router; it s the summary of links collected by the backbone to an area or the summary of links collected by the area to the backbone.  Summary Link ments are ed between areas by ABRs and describes networks within an area.

19

19

: This is done by an AS router that s the summary link from other ASs to the backbone area of the current AS, information which later can be disseminated to the areas so that they will know about the networks in other AS's.  AS (Autonomous System) Summary Link ments are ed between areas and describe the path to the AS Boundary Router (ASBR).

This is also done by an AS router to announce the existence of a single network outside the AS to the backbone area to be disseminated into the areas.  AS External Link ments are ed between and flooded into areas by ASBRs and describe external destinations outside the Autonomous System. 20

 OSPF is implemented as a program in the network layer, using the service of the IP for propagation.

 An IP datagram that carries a message from OSPF sets the value of the protocol field to 89.  Although OSPF is a routing protocol to help IP to route its datagrams inside an AS, the OSPF messages are encapsulated inside datagrams.  OSPF has gone through two versions: version 1 and version 2. Most implementations use version-2

21

 OSPF is a very complex protocol; it uses five different types of messages.  All packets have a common header. Type is 1 to 5 based on the type of OSPF messages.  The link-state general header is used in some messages.

 The OSPF common header has a provision for authentication of sender, preventing malicious entities to send OSPF messages to a router.

OSPF common header

link-state general header 22

The hello message (type 1) is used by a router to introduce itself to the neighbors and announce all neighbors what it already knows. The database description message (type 2) is normally sent in response to the hello message to allow a newly ed router to acquire the full LSDB.

Database description message (type 2) Hello packet (Type 1 OSPF packet) 23

 The link state request message (type 3) is sent by a router that needs information about a specific LS.  The Link-state update message (type 4) is the main OSPF message used for building the LSDB and has five different versions (router link, network link, summary link to network, summary link to AS border router, and external link).  The link-state acknowledgment message (type 5) is used to create reliability in OSPF; each router that receives a link-state update message needs to acknowledge it.

Link state acknowledgment packet 24

Update messages. The link-state messages in OSPF have a somewhat complex format. They also are flooded to the whole area. If the area is large, these messages may create heavy traffic and use a lot of bandwidth. Convergence of Forwarding Tables. When the flooding of LSPs is completed, each router can create its own shortest-path tree and forwarding table; convergence is fairly quick.

Robustness. The OSPF protocol is more robust than RIP because, after receiving the completed LSDB, each router is independent and does not depend on other routers in the area. Corruption or failure in one router does not affect other routers as seriously as in RIP.

25

Review Example - 1 Give the router link LSA sent by router 10.24.7.9 in the following figure

26

Review Example - 2 Give the network link LSA for the following figure

27

Review Example - 3 For the following figure, which router(s) sends out router link LSAs?;; Which router(s) sends out the network link LSAs?

Solution -1 All routers router link LSAs. a. R1 has two links, N1 and N2. b. R2 has one link, N1. c. R3 has two links, N2 and N3.

Solution -2 All three network must network links: a)

ment for N1 is done by R1 because it is the only attached router and therefore the designated router.

b)

ment for N2 can be done by either R1, R2, or R3, depending on which one is chosen as the designated router.

c)

ment for N3 is done by R3 because it is the only attached router and therefore the designated router. 28

Review Example - 4

I D E N T I F Y

The summary link to network LSA is used by the area border router to announce the existence of other networks outside the area.

External link LSA (fifth kind of LSA)

Summary link to AS boundary router LSA (fourth kind of LSA)

29

BORDER GATEWAY PROTOCOL BGP4

 The Border Gateway Protocol version 4 (BGP4) is the only inter-domain routing protocol used in the Internet today. It first appeared in 1989 and has gone through 4 versions. It is based on the path-vector algorithm.  An example of an internet with four autonomous systems is shown. AS2, AS3 and AS4 are stub autonomous systems; AS1 is a transient one. In this example, data exchange between AS2, AS3, and AS4 should through AS1.  Each autonomous system in this figure uses one of the two common intradomain protocols RIP or OSPF. Each router in each AS knows how to reach a network that is in its own AS, but it does not know how to reach a network in another AS.

31

 To enable each router to route a packet to any network in the internet, first a variation of BGP4, called external BGP (eBGP) is installed on each border router (the one at the edge of each AS which is connected to a router at another AS).  Then install the second variation of BGP, called internal BGP (iBGP), on all routers. This means that the border routers will be running three routing protocols (intradomain, eBGP, and iBGP), but other routers are running two protocols (intradomain and iBGP).

32

 BGP is a kind of point-to-point protocol. When the software is installed on two routers, they try to create a T connection using the well-known port 179.  The eBGP variation of BGP allows two physically connected border routers in two different AS's to form pairs of eBGP speakers and exchange messages.  The routers that are eligible in our example form three pairs: RI-R5, R2-R6, and R4-R9. The connection between these pairs is established over three physical WANs (N5, N6, and N7).  There is a need for a logical T connection to be created over the physical connection to make the exchange of information possible. Each logical connection in BGP parlance is referred to as a session.

33

 The above figure also shows the simplified update messages sent by routers involved in the eBGP sessions.  For example, message number 1 is sent by router R1 and tells router R5 that N1, N2, N3 and N4 can be reached through router R1 (R1 gets this information from the corresponding intradomain forwarding table).  Router R5 can now add these pieces of information at the end of its forwarding table. When R5 receives any packet destined for these four networks, it can use its forwarding table and find that the next router is R1.  Though exchanged eBGP messages help some routers know how to route packets to some networks in the internet, but the reachability information is not complete.  There are two problems that need to be addressed: 1. Some border routers do not know how to route a packet destined for non-neighbor AS's. For example, R5 does not know how to route packets destined for networks in AS3 and AS4. 2. None of the nonborder routers know how to route a packet destined for any networks in other ASs. To address the above two problems, we need to allow all pairs of routers (border or nonborder) to run the second variation of the BGP protocol, iBGP. 34

 The iBGP protocol is similar to the eBGP protocol in that it uses the service of T on the well known port 179, but it creates a session between any possible pair of routers inside a autonomous system.  Few points are to be noted for iBGP  First, if an AS has only one router, there cannot be an iBGP session. For example, we cannot create an iBGP session inside AS2 or AS4 in our internet.  Second, if there are n routers in an autonomous system, there should iBGP sessions in that autonomous system (a fully connected mesh) to prevent lobe [n x (n - 1) / 2] ops in the system.  Each router needs to its own reachability to the peer in the session instead of flooding what it receives from another peer in another session.

Computer Networks - 14CS3406

35

⁂ At this stage only four messages are exchanged. The first message (numbered 1) is sent by R1 announcing that networks N8 and N9 are reachable through the path AS1-AS2, but the next router is R1. This message is sent, through separate sessions, to R2, R3, and R4. 36

⁂ Routers R2, R4, and R6 do the same thing but send different messages to different destinations. At this stage, R3, R7,and R8 create sessions with their peers, but they actually have no message to send.

⁂ The updating process does not stop here. For example, after R1 receives the update message from R2, it combines the reachability information about AS3 with the reachability information it already knows about AS1 and sends a new update message to R5.Now R5 knows how to reach networks in AS1 and AS3. ⁂ The process continues when R1 receives the update message from R4. There comes a point in time where there are no changes in the previous updates and all information is propagated through all AS's. ⁂ Each router combines the information received from eBGP and iBGP and creates what we may call a path table after applying the criteria for finding the best path,

37

38

 Router R1 now knows that any packet destined for networks N8 or N9 should go through AS1 and AS2 and the next router to deliver the packet to is router R5.  Similarly, router R4 knows that any packet destined for networks N10, N11, or N12 should go through AS1 and AS3 and the next router to deliver this packet to is router R1, and so on.

 The path tables collected and organized by BGP are not used, per se, for routing packets; they are injected into intradomain forwarding tables (RIP or OSPF) for routing packets.

 In the case of a stub AS, the only area border router adds a default entry at the end of its forwarding table and defines the next router to be the speaker router at the end of the eBGP connection.  R5 in AS2 defines R1 as the default router for all networks other than N8 and N9. The situation is the same for router R9 in AS4 with the default router to be R4. In AS3, R6 set its default router to be R2, but R7 and R8 set their default router to be R6. 39

 In the case of a transient AS, the situation is more complicated. R1 in AS1 needs to inject the whole contents of the path table for R1 into its intradomain forwarding table. The situation is the same for R2, R3, and R4.

 The most common solution to the cost value problem is to set the cost to the foreign networks at the same cost value as to reach the first AS in the path.  For example, the cost for R5 to reach all networks in other AS's is the cost to reach N5. The cost for R1 to reach networks N10 to N12 is the cost to reach N6, and so on. The cost is taken from the intradomain forwarding tables (RIP or OSPF).  When dealing the entire global internet, the intradomain forwarding tables obtained by BGP are quite huge. BGP employs a technique called Address Aggregation, which uses the prefixes as destination identifiers and allows the aggregation of these prefixes.  For example, prefixes 14.18.20.0/26, 14.18.20.64/26, 14.18.20.128/26, and 14.18.20.192/26, can be combined into 14.18.20.0/24 if all four subnets can be reached through one path. 40

 In both intradomain routing protocols (RIP or OSPF), a destination is normally associated with two pieces of information: next hop and cost.  Interdomain routing is more involved and requires more information about how to reach the final destination.

 In BGP these pieces are called path attributes. BGP allows a destination to be associated with up to seven path attributes.  Path attributes are divided into two broad categories: well-known and optional.  A well-known attribute must be recognized by all routers; an optional attribute need not be.  A well-known attribute can be mandatory, which means that it must be present in any BGP update message, or discretionary, which means it does not have to be.

 An optional attribute can be either transitive, which means it can to the next AS, or intransitive, which means it cannot. 41

O: Optional bit (set if attribute is optional) P: Partial bit (set if an optional attribute is lost in transit) T: Transitive bit (set if attribute is transitive) E: Extended bit (set if attribute length is two bytes)

The first byte in each attribute defines the four attribute flags. The next byte defines the type of attributes assigned by ICANN. The attribute value length defines the length of the attribute value field.

ORIGIN (type 1): This is a well-known mandatory attribute, which defines the source OF the routing information. This attribute can be defined by one of the three values: 1,2, and 3. Value 1 means that the information about the path has been taken from an intra domain protocol (RIP or OSPF). Value 2 means that the information comes from BGP. Value 3 means that it comes from an unknown source.

42

AS-PATH (type 2): This is a well-known mandatory attribute, which defines the list of autonomous systems through which the destination can be reached. The AS-PATH attribute, helps prevent a loop. Whenever an update message arrives at a router that lists the current AS as the path, the router drops that path. The AS-PATH can also be used in route selection.

NEXT-HOP (type 3): This is a well-known mandatory attribute, which defines the next router to which the data packet should be forwarded. This attribute helps to inject path information collected through the operations of eBGP and iBGP into the intradomain routing protocols such as RIP or OSPF.

MULT-EXIT-DISC (type 4). The multiple-exit discriminator is an optional intransitive attribute, which discriminates among multiple exit paths to a destination. The value of this attribute is normally defined by the metric in the corresponding intradomain protocol (an attribute value of 4-byte unsigned integer). For example, if a router has multiple paths to the destination with different values related to these attributes, the one with the lowest value is selected. Note that this attribute is intransitive, which means that it is not propagated from one AS to another. 43

LOCAL-PREF (type 5):

The local preference attribute is a well-known discretionary attribute. It is normally set by the , based on the organization policy. The routes the prefers are given a higher local preference value.

ATOMIC-AGGREGATE (type 6):

This is a well-known discretionary attribute, which defines the destination prefix as not aggregate; it only defines a single destination network. This attribute has no value field, which means the value of the length field is zero.

AGGREGATOR (type 7):

This is an optional transitive attribute, which emphasizes that the destination prefix is an aggregate. The attribute value gives the number of the last AS that did the aggregation followed by the IP address of the router that did so.

 Well-known Mandatory: Recognized and Included in all BGP Update messages.  Well-known Discretionary: Recognized and May or May not include in BGP Update messages  Optional Transitive: Even if Not ed it Still need to accept and Send in Update Message.

 Optional Non-transitive: Can be ignored and not to peers.

44

A route in BGP has some attributes attached to it and it may come from an eBGP session or an iBGP session. The router extracts the routes which meet the criteria in each step. If only one route is extracted, it is selected and the process stops; otherwise, the process continues with the next step.

Note that the first choice is related to the LOCAL-PREF attribute, which reflects the policy imposed by the istration on the route.

45

BOP uses four types of messages for communication between the BOP speakers across the ASs and inside an AS: open, update, keepalive, and notification. All BGP packets share the same common header.

. To create a neighborhood relationship, a router running BGP opens a rep connection with a neighbor and sends an open message. . The update message is the heart of the BGP protocol. It is used by a router to withdraw destinations that have been d previously, to announce a route to a new destination, or both. Note that BGP can withdraw several destinations that were d before, but it can only one new destination or multiple destinations with the same path attributes) in a single update message. . The BGP peers that are running, exchange keepalive messages regularly to tell each other that they are alive. A notification message is sent by a router whenever an error condition is detected or a router wants to close the session.

46

47

Marker: This 16-octet field is included for compatibility; it MUST be set to all ones. Length: This 2-octet unsigned integer indicates the total length of the message, including the header in octets. Type: This 1-octet unsigned integer indicates the type code of the message. This document defines the following type codes: 1 - OPEN 2 - UPDATE 3 - NOTIFICATION 4 - KEEPALIVE

Performance  BGP performance can be compared with RIP. BGP speakers exchange a lot of messages to create forwarding tables, but BGP is free from loops and count-to-infinity.  The same weakness mentioned for RIP about propagation of failure and corruption also exists in BGP.

48