Internet Routing

Internet Routing RIP, OSPF, BGP4 By D . C. Sonkhla, SDE

ROUTING PROCESS No

Packet received Header & Checksum valid Decremental TTL>=0?

No

Yes Route table Lookup Based on Destination Address

Route found

Send ICMP To Originator

No No

Received ARP reply

Route is available Search for MAC Address in ARP CACHE

No

Discard Original Message Default route Available

Yes

MAC Address Found

No

Yes

Build new packet with MAC address Found, route packet through port found In routing table

Send ARP Request & wait for response

Received ARP Reply Insert MAC and IP Address into ARP table

D.C.Sonkhla,SDE(Computer)

Internet Routing 

Hosts and Gateways are presented with datagram addressed to some host.



Routing is the method by which the host or Gateway decides, where to send the datagram.



It may be able to send the Datagram directly to the destination if it is connected to that n/w or gateway directly.



If the destination is not directly reachable, then it will try to send the datagram to a gateway that is nearer to the destination.

Internet Routing 

The goal of routing protocol is simple: It supply the information that is needed to do the routing.



There are many type of Routing protocols used, but for the NIB nodes following are the routing protocols recommended : 

RIP



OSPF



bgp4

Routing Information Protocol (RIP) 

RIP is the routing protocol based on the Bellmanford (distance vector) algorithm.



Name distance vector is derived from the fact that routes are advertise as vector of (distance,direction), where distance is defined in forms of a metric and direction in terms of the next-hop router.



This algorithm for routing computations in the computer n/w is since the days of ARPANET.

Routing Information Protocol (RIP) 

It has become an defacto standard for exchange of routing information among



gateways & hosts. It is most useful as IGP (interior gateway protocol)

Routing Protocols 

Building Routing Tables 



Interior Gateway Protocol (IGP) 

Routing Information Protocol version 1



RIP version 2



Open Short Path first (OSPF)

Exterior Gateway Protocol (EGP) 

Border Gateway Protocol (BGP4)



Inter Domain routing Protocol (IDRP)

Routing Protocols Interior Gateway Protocols & Exterior Gateway Protocols 

Static Routing

Interior Gateway Protocols & Exterior Gateway Protocol 





Static Routing Interior Gateway Protocol Dynamic Routing Routing Information Protocol (RIP) Open Short Path First (OSPF) Exterior Gateway Protocols Border gateway Protocol

IP Routing Tables - RIP 

Routing table is created by the Routing Protocol Port IP address (i.e., 132.2.2.2)

132.2.0.0

Routing Table Network Number 132.2.0.0 133.3.0.0 130.1.0.0 134.4.0.0

2.2 1

133.3.0.0 2 3.3

1.1 3 130.1.0.0 Next Hop Direct Direct Direct Indirect

3.4

Hops 1 1 1 2

•Adapts to changing Network Conditions

133.4.0.0 4.5

Learned from RIP RIP RIP RIP

Port 1 2 3 2

Default Router (Default Gateway) 130.1.1.1 Default Route 0.0.0.0 129.1.1.2

Default Route 130.1.1.1

129.1.1.1

129.1.1.2 Default Route 129.1.1.1

In PC configuration Fable write route (IP address) 0.0.0.0 (Default rt.) Dial in subscriber may also be treated as LAN user

Routing Protocols - Distance Vector 0 Hop

134.4.0.0

1 2 134.3.0.0 1Hop 2Hop 134.5.0.0

•Metric used byRIP is hop count, with 1 signifying a directly connected network of the advertising router & 16 signifying unreachable network

Updating Other Routers (Distance Vectors) 

Upon initialization, each router reads its preconfigured IP address and metric (cost in hops) of all its active ports.



Each router transmits a portion of its routing table (network ID, metric) to each “neighbor” router.



Each router uses the most recent updates from each neighbor



Each router uses the update information to calculate its own “shortest path” (distance in hops) to a network.



Tables are updated only:



If the received information indicates a shorter path to the destination network.



If the received update information indicates a network is no longer reachable



If a new network is found.

Routing Information Protocol (RIP) 



   

RIP is distance vector protocol designed to serve as an IGP for the exchange of routing information within an autonomous system. RIP is a simple protocol suitable for use in networks of relatively small size not requiring complex metrics. Hop count is used as the metric for path selection RIP supports point-point links and broadcast networks Max, allowable hop count is 15 (16 is unreachable

RIP Parameters 

RIP packets are carried over UDP and for routing purposes use port 520



Unless triggered by a configuration change RIP packets are sent every 30 seconds.



If no update packets re received for within 180 seconds the distance for that route is set to infinity and will subsequently be removed from the routing table.



The address 0.0.0.0. Represents the default route to exit the AS.

Routing Information Protocol (Version 1)     

RIP process operates from UDP port 420 RIP defines two message type: Request Messages and Response Messages Router sends a Response message out to every RIPenabled interface every 30 seconds RIP Header UDP Header IP Header DA

SA

TF

Data

RIP Data

UDP Data

IP Data CRC

RIP Operational Types 







RIP can operate in either ACTIVE or PASSIVE mode Active means that it builds routing tables and response to RIP requests. Passive means that it can build a routing table for its own use, but it does not respond to any RIP requests. Most works stations (PCs) use a default gateway (I.e., router) and not a routing update protocol like RIP

RIP Algorithm 



RIP defines the “best” route as the one with least number of routing hops Once a router is installed, or started, it should send messages to all of its neighbors

A

B

C

D

A

B

C

D

E

A Bigger Update Z Y

Z

Router A

Route Hop Route Hop

1 1

X Y Z

Y

Network Hop Router Port W 1 Local 2 X 1 Local 1 Y 2 B 1 Z 3 B 1

Route HopX Route Hop Route Hop W X Y Z

1 1 2 3

1 1 2

Which Rout is chosen by RIP Source Router C

Router D 10.1.4.0 64k

10.1.5.0 9.6 k

? 10.1.1.0

10.1.3.0

Router E

E1 E1

10.1.2.0

Router A

E3

Router B

•RIP will select 64k-9.6k Route as it has got ess hop than other E1-E3-E1 Route

Target

Routers & Subnet-Masks

•RIPv1 requires that a subnet mask be uniform across an entire network •RIPv1 does not supply a subnet-mask entry in its Routing updates •It assumes that the mask the same for the learned Subnet of the same network ID as its configured port 150.1.0.0

160.1.0.0 160.1.0.0 255.255.255.0

150.1.1.0 255.255.255.0

150.1.3.0 150.1.3.0 255.255.255.0

• RIVv1 supports only one subnet-mask for Network ID

RIPv2 -- Multicast Support

•RIPv2 uses the multicast address of 224.0.0.9

to multicast

Does not broadcast its table. •MAC address of01-00-5E-00-00-09.

•RIPv1 uses a broadcast address in both the IP header

And the MAC header

•RIPv1 only-version 1 messages will be sent

•RIPv1 compatibility – RIP 2 messages a broadcast •RIPv2-Messages are multicast

OSPF •High Functionality •Non-propriety (IGP Internet Gate way Protocol For TCP/IP protocol family •OSPF based on link state technology •Authentication of routing updates Supports •VLSM (Variable Length Subnet Mark), CIDR super netting (It won’t Support RIP) •Route Summarization •OSPF uses IP multicast to send link state updates. This ensures less processing on routers that are not listening to OSPF packets. •Updates are sent only in case of routing changes occur instead Of periodically.

•Better use of Bandwidth •Better convergence •No Limitation of hop count •The intelligent use of VLSM & Super netting & efficient IP address allocation. •Supports fully class less behaviors •Uses IP multicast to send link state updates. •Better convergence than RIP, this is because routing changes are propagated instance only and not periodically. •Routing authentication by different method of password authentication. •Keeps tracks of external routes injected by external Protocol such as BGP



Link State

OSPF is a link state, we can think of a link as being an Interface and of its relationship to its neighboring routers A descriptions of interface include: IP address of interface, the Mark, the type of N/W it is connected to, routers connected to that N/W. The collection of all these link state, would from Link State Database. Link State Algorithm 

OSPF uses link state Algorithm to build and calculate the shortest path to all its known destination.



Upon initialization or due to any change in routing information, a router will generate a link state advertisement



All router will exchange link states by means of flooding.



Each router that receives a link state update should store a copy In its link state database and then propagate the update to other routers.



After the database of each router is completed the router

6.

with calculate the shortest path Tree for all destinations (using Digastrics Algorithm )

•

•

In case of no changes in the OSPF N/W occur such as cost of link or a N/W being added or deleted, OSPF should be very quite. Any changes that are occur are communicated via link state packets, and the Digastrics algorithm is recalculated to find shortest path.

Shortest Path Algorithm: Algorithm places each router at the root of a tree and calculate Shortest path to each destination based on the communication cost required to reach that destination OSPF cost: •Cost (called metric) of an interface in OSPF is overhead required To send packets across a certain interface. •Cost is inversely proportional to the Bandwidth of that interface. •Higher Bandwidth indicates lover cost.

Area and Router Types •OSPF uses folding to exchange link state updates bet routers. •Any change in routing flooded to all routers in the N/W •Areas are introduced to put a boundary on the explosion Of link state updates. •Dikastra algorithm on a router limited to within an area. •All routers within an area have the exact link state database •Routers that belongs to multiple areas, called Area Border Routers (ABR) •ABR disseminating routing information or routing changes between areas.

•A router that has all of its interfaces with in the same area is called An Internet Router (IR) •Router that has interface in multiple areas is called Area Border Router (ABR) •ABR connect one or more areas to backbone and act as a gateway for inter area traffic. •An ABR has at least one interface that belongs to backbone and Maintain separate link state dataface for each of its area. •That is why ABR has more memory and powerful processor. •All ABR are backbone router but all backbone router are not ABR •An IR whose interfaces all belong to areas is also backbone router. •ASBR (Asynchronous System Boundary router) are gateways for external traffic, injecting traffic routes into OSPF domain that were Learned from some other protocol, such as the BGP and EIGRP Processes. •An ASBR can be located anywhere within the OSPF as, it may be IR, backbone Router or ABR

A Routing Protocol Comparison Function/Feature Standard Number Link State Protocol Large Range of Metrics Update Policy Update address Dead Interval Supports authentication Convergence Time

Variable Length Subnets Supports Super netting Type of Service (TOS) Multipath routing Network Diameter Easy to use

RIVv1 RFC 1058

RIPv2 RFC 1723

OSPF

No

No

Yes

RFC 2178

Hop Count Hop Count Yes, based on (16=infinity) (16=infinity) 1=655335 Route Table Route Table Link State changes every 30 sec. every 30 sec. every 30 minutes. Broadcast Broadcast, Multicast Multicast 300 secs. Total 300 secs. total Uptp 300 seconds total. Usually shorter No Yes Yes Variable based on Variable based on Media Delay+Dead (numbers of routers numbers of routers interval x dead interval) x dead interval) No Yes Yes

No

Yes

Yes

No No 15 hops

No No 15 hops

Yes

Yes

Yes Yes N/A but up to 65535 No

OSPF Overview •Upon initialization, each router records information about all its Interfaces. •Each router builds a packet know as the Link State •Advertisement (LSA) Contains a listing of all recently seen routers and their cost LASs are restricted to being forwarded only in the Originated area. •Received LSAs are flooded to all other routers. Each router makes a copy of the most recently “seen” LSA

OSPF Overview •Each outer has complete knowledge of the topology of the Area to which it belongs. •Adjacencies are formed between a Designated Router (and Backup DR) and other routers on a network. •Shortest Path Trees are constructed after routers exchange •Their databases using Dijkstra’s algorithm •Router algorithm only when changes occur (or every 30 minutes, Whichever is shorter.

Stub areas Area 0

AS 2

Area 1

Does not Contain AS2 Route entries

Contain AS2 Route entries Area 2

•An area that has only one entry and one exit point (must be the same area). •Used to reduce the number of external advertisements. •A stub area blocks AS external link advertisements. Stub Network: A network which is connected to only one router e.g. a LAN to a router.

Network Types: OSPF Media Support OSPF Defines 5 Network Types • Broadcast Networks- Networks such as Ethernet, Token Ring, and FDDI • Non-broadcast Multi access (NBMA) Networks-access that does not support broadcast but allows for multiple station access such as ATM, Frame Relay, and X.25. • Point-to-Point Networks-Links that only have two networks attachments, such as two routers connected by a serial line. • Point to Multipoint Networks • Virtual Links — Not all neighbors become adjacent-whether an adjacency is formed or not depends on type of network to which two neighbors are attached — Network type also influence the way in which OSPF packets are transmitted.   

Two routers are neighbors when connected by physical link (or logical link) virtual link) Hello packet (Router ID + Network address of link + Hello interval) After Hello, the two neighbor should synchronies their database (i.e. protocol parameters, firms, optional capabilities etc.) to establish ‘adjacency’.

•LSA Received •Is Entry in topological Database? Yes-Reset Timer for entry No-Add to database •Flood LSA •Run SPF to calculate new table

Link State Protocol

1

Routing table Topological Database

Link State advertisements 5

2

3 SPF Algorithm

4

LSA is sent only only in case of charge of network topology or 30 minutes whichever is earlier. Normal keep Alive is ‘Hello’ at an interval of 30 seconds to neighbors LSA is flooding (if asynchronous) and floods from one to another immediately (not wait for timer to finish interval)

Maintaining the Database • After Dijkstra runs, the database is checked for consistency. • Uses the flooding procedure:  Receive an LSA  Check for the information in the database  Determine whether or not to forward this LSA to an adjacency • Reliability checked using an acknowledgement procedure • Each LSA contains an age entry • Sequence numbers are generated for every LSA.

OSPF Route Summarisation

Area 1 Area 2 1.1.1.1 RTA

ABR

2.2.2.2 RTB

Summarization

Area 0 Backbone Area

•Consolidates multiple Routes into single advertisement •Requires Contigues Addressing •Make efficient use of Bandwidth •Although network link is down, the topology change will not propogate into the backnone area

ABR

4

RA

4

5

5 RG

4 2

RD 3

2

3

5

1

2

10

RB

8

RE

RC

1

2

5

2 2

1

RH

8 6

2 RF

Link State Protocol

Topological Database Router D RA RA RA RB

Neighbor RB RD RE

RB

RA RC

RB RC

RE RB

RC RD RD

RF RA

RD RE

Cost 2 4 4 2

Router D RE RE RE RE

Neighbor RB RD RF

Cost 2 3 2 1

1 10 5

RE

RG RH

RF RF

RC RE

RF RG RG

RH RD

RE

2 4 3

RE

4 5 1

RG RA

5 5

RH RH

RE RE

8 6

8 2 2

The Hello Protocol The Hello protocol serves several purpose: •It is the means by which parameters on which two routers must agree Before they can become neighbors. •Hello packets are as keep alives between neighbors •It ensures bi-directional communication between neighbors. •It elects Designated Routers (DRs) and Backup Designated Routers (BDRs) On Broadcast and Non-broadcast Multi-access (NBMA) networks. # ip ospf hello interval #Ip ospt dead interval

(10 secs)

(4 x hello interval) Broad cast Ethernet NBMA X.25, Frame Relay, ISDN

Each Hello packet contains the following information: •The Router ID of the originating router. •The Area ID of the originating router interface •The address mask of the originating interface •The authentication type and authentication information for the originating interface •The Hello Interval of the originating interface •The router Dead Interval of the originating interface •The Router Priority •The DR and BDR •Five flag bits signifying optional optional capabilities •The Router Ids of the originating router’s neighbors. This list contains only Routers from which Hellos were heard on the originating interface within the Last Router Dead Interval ‘Hello’ proper

Neighbor

Establish Adjacency (logical)

OSPF defines five network types. 3. Point to point networks (PPP, TI & EI) 4. Broadcast Networks (Ethernet), Token Ring, Elect DR, BDR 5. Non Broadcast Multi-access (NBMA) networks (X.25, Frame Relay) ATM 4. Point to multi-point networks (PMP) NBA with multi drop, No DR or BDR 9. Virtual links. Unnumbered point to point networks Transit Network 2 or more attached router Just passing through packets Stub Network Only one attached router

STATIC ROUTING The Route Table Each route entry in the database contain two items: • A destination address-address of the network the router can reach

A pointer to the destination Destination Network is directly connected to the router, it will Indicate the address of another router on a directly connected Network.

Procedure for static routing 10. For each data link within the internetwork, identify all address (subnet or network) 12. For each router, identify all data links not directly connected to that router. 14. For each router, write a route statement for each data link mot directly connected to it.

E0: 10.1.5.1

E0: 10.1.1.1

E0: S0: 10.1.3.1 10.1.2.1

CARROLL

SI: 10.1.6.1 S0: 10.1.4.2 S0: 10.1.6.2

S0: 10.1.2.2 SI: 10.1.4.1

NETWORK NEXT HOP NETWORK NEXT HOP 10.1.1.0 10.1.2.0 10.1.3.0 10.1.4.0 10.1.5.0 10.1.6.0 10.1.7.0

directly connected directly connected 10.1.2.2 10.1.2.2 10.1.2.2 10.1.2.2 10.1.2.2

DAHI NETWORK NEXT HOP 10.1.2.0 10.13.0 10.14.0 10.1.5.0 10.1.6.0 10.1.7.0

directly connected directly connected directly connected 10.1.4.2 10.1.4.2 10.1.4.2

LEWIS

NETWORK NEXT HOP 10.1.1.0 10.1.2.0 10.1.3.0 10.1.4.0 10.1.5.0 10.1.6.0 10.1.6.0

10.1.4.1 10.1.4.1 10.1.4.2 directly connected directly connected directly connected 10.1.6.2

E0: 10.1.7.1

BAUM

NETWORK NEXT HOP 10.1.1.0 10.1.2.0 10.1.3.0 10.1.4.0 10.1.5.0 10.1.6.0 10.1.7.0

10.1.6.1 10.1.6.1 10.1.6.1 10.1.6.1 10.1.6.1 directly connected directly connected

Lewis # show IP route Codes: C-Connected, S-static, I =GRP, R- RIP, M-Mobile, B = BGP, D= EIGRP O- OSPF Gateway of last resort is not set 10.0.0.0/24 is submitted, 7 subnets S 10.1.3.0 (1/0) via 10.1.4.1 S 10.1.2.0 (1/0) via 10.1.4.1 S 10.1.1.0 (1/0) via 10.1.4.1 S 10.1.7.0 (1/0) via 10.1.6.2 C 10.1.6.0 is directly connected, serial 1 C 10.1.5.0 is directly connected, ethernet C 10.1.4.0 is directly connected, serial 0 Lewis # - Default route not defined (1/0) (Administrate distance/ Lost metric)

192.168.1.65/27 192.168.1.1/27

POOH

TIGGER

192.168.1.193/27

192.168.1194/27

192.168.1.66/27 10.4.6.1/24

10.4.6.2/24

10.4.7.1/27

10.1.5.1/16

STARIC ROUTE CONTRIBUTION Internetwork has six subnets •10.1.0.0/16 •10.4.6.0/24 •10.4.7.0/24 •192.168.1.192/27 •192.168.164/27 •192.168.1.0/27

Procedure 1. 2. 3.

For each datalink, identify all addresses (subnet or network) For each ROUTER identify all routes NOT directly connected For each router, write route statement for each data link not directly connected

Static routes for Piglet •10.4.6.0/24 •10.4.7.0/24 •192.168.1.192/27 •192.168.164/27 Piglet’s static routesPiglet (config.)# ip route 192.168.1.0 Piglet (config.) # ip route 192.168.1.64 Piglet (config.) # ip route 10.4.6.0 Piglet (config.) # ip route 10.4.7.0

255.255.255.224 255.255.255.224 255.255.255. 255.255.255.224

192.168.1.193 192.168.1.193 192.168.1.193 192.168.1.193

Route entries for Tigger (Alternative approach through on interface Tigger(config.)# ip route 192.168.1.0 255.255.255.224 S0 Tigger (config.) # ip route 10.1.0.0 255.255.0.0 E0 Tigger(config.) # ip route 10.4.7.0 255.255.255.0 S1 # ip route address Mask address Next hop router interface address to which this link directly connected.

•Routers are advertised between a pair of BGP routers in update messages •Incase of information changes, such as route being unreachable or a having better path, BGP informs its neighbors by withdrawing invalid routes and injecting new routing information •Keep alive message sent periodically 60 second ( if routing change.)

How BGP works •Path Vector Protocol carry information between AS, • Path Vector comes from the fact that BGP routing information's carries a sequence of AS numbers • Which indicates the path a route has traversed. • BGP uses TCP (port 179) • Two BGP routers from a Transport Protocol connection between each other are peers or neighbors • Peer routers exchange multiple messages to open and confirm the connection parameters • In case disagreement between notification errors are sent and peers connection does not get established. • Initially all candidates BGP routes are exchanged

BGP (Border Gateway Protocol) BGP provides loop free inter domain routing between Autonomous System (A.S) An AS is a set of routers that operates under the same administration BGP often run among the N/Ws of Internet Service Providers (ISPs) BGP construct a graph of Ass based on the information exchanged between BGP neighbor The directed graph environment is sometimes referred to as a Tree. As for as BGP is concerned, the whole internet is a graph of AS, with each AS identified by an AS number. Connections between two AS, together from a path, and collection of path information forms a route to reach a destination. AS2 AS1

AS3 AS n-1 AS4

AS n AS5

Autonomous System •

An, AS is a way of reporting to “Someone Network” (VSNL, BSNL, MTNL etc.)

•

Normally an AS will have Someone or ones responsible for it (a point of contract, typically called a NOC, or Network Operation Centre)

•

And one or multiple “Border Routers” (Where Routers in that ‘AS’ peer and exchange routes with other ASs)

•

As well as a simple or complicated internal routing scheme so that every router in that AS known how to get to every other router and destination within that AS.

•

When you “advertise” routes to other ‘AS’, One way of thinking of those route “advertisements” is as “promise” to carry data to the IP space represented in the route Being advertised. e.g. if you advertise 192.202.4.0/24, the class ‘C’ starting at 192.202.4.0 and Ending at 192.202.4.255. You promise that if someone send you data destined for any address in 192.202.4.0/24, You know how to carry that data to its ultimate destination

How BGP Works •Path Vector Protocol carry information between Ass. •Path Vector comes form the fact that BGP routing information carries a sequence of AS numbers •Which indicates the path a route has transferred. BGP user TCP (Port 179) •Two BGP routers forms a transport protocol connection between each other are peers or neighbors •Peer routers exchange multiple message to open and each confirm the connection parameters •In case of disagreement, notification errors are sent and peer connection does not get established •Initially all candidate BGP routes are exchanged •Routers are advertised between a pair of BGP routes are exchanged •In case of information changes, such as route being unreachable or having a better path, BGP informs its neighbors by with drawing invalid routes and injecting new routing information •Keep alive message sent periodically every 60 seconds (if no routing change)