Routing Basics, Rip

ROUTING BASICS, RIP

Iskra Djonova-Popova

Why are Routers Necessary? One of the key components of the technical infrastructure of the network ■ Connect networks ■ Provide the best path from the source to destination Budapest, August 1999 ■

A

Routing basics, RIP

B R1

R2

R3

R4

R5 C Iskra Dj. Popova

2

Sending Packets through the Network Sending packets on the same subnet ■ Default router ■ Discovering the local router ■

■

Using redirects

A

Internet R2

R1 B Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

3

The Internal Elements of a Router Routing table Interfaces Destination Next hop Interface ... ...

... ...

1 2

1 2 3

Routing Engine

Budapest, August 1999

Routing basics, RIP

4 Iskra Dj. Popova

4

Schematic View of a Router

ncoming packets

Outgoing packets Processing

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

5

The Routing Table ■

The crucial element of the router – –

■

defines the topology of the network must be consistent with other router’s tables

Static and dynamic routing tables – static - when constructed by network administrator – dynamic - when constructed by routing protocols

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

6

Static Routes ■

Advantages – predictability – no overhead – simplicity

■

Disadvantages – lack of scalability – can not adapt to a failure in a network

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

7

Example:

172.16.5.0/24 172.16.3.0/24 hostname Router1 172.16.5.1 172.16.3.1 R2 172.16.3.2 interface e0 172.16.1.2 R3 IP 172.16.1.1 172.16.4.1 172.16.2.0/24 255.255.255.0 172.16.2.1 172.16.4.0/24interface e1 R1 IP 172.16.2.1 172.16.1.1 255.255.255.0 IP route 172.16.3.0 255.25.255.0 172.16.1.0 172.16.1.2 /24 IP route 172.16.5.0 255.25.255.0 172.16.1.2 IP route 172.16.4.0 255.25.255.0 8 Budapest, August 1999 Routing basics, RIP Iskra Dj. Popova 172.16.1.2

Dynamic Routes ■

Advantages – adapt to a failure in a network – work in large networks

■

Disadvantages – increase in complexity – overhead on the lines and routers

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

9

Hybrid Routing Schemes ■

Some parts use static and some parts dynamic routing

Core

R1 R2 Distribution

– static routing on R5 the access network R4 Access – dynamic routing on the core and distribution network Budapest, August 1999 Routing basics, RIP Iskra Dj. Popova

R3

R6

10

Classification of the Routing Protocols ■

Where the protocol is used – Interior protocols (IGP) – Exterior protocols (EGP)

■

Kind of information that is carried and the way the routing table are calculated – Distance-vector protocols – Link-state protocols

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

11

IGP Vs EGP ■

Interior Gateway Protocols – within a single autonomous system single network administration ■ unique routing policy ■ make best use of network resources ■

■

Exterior Gateway Protocols – among different autonomous systems independent administrative entities ■ communication between independent network infrastructures ■

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

12

Distance-Vector Vs LinkState ■

Distance-vector protocols – Each router periodically sends to his neighbors ■

■

how far is the destination the next hop to get there

■

Link-state protocols – Each router sends information about ■

links to which it is attached

■

state of these links

– it is flooded throughout the network

– Install routes directly – every router in tables calculates its routing Budapest, August 1999 13 Routing basics, RIP Iskra Dj. Popova

The Role of IGPs Maintain a coherent picture of the network topology and address domain in the router ■ Distribute this information to the other routers ■ Maintain consistent routing tables, such that the path to every destination is “optimal” ■ Converge quickly when there are Budapest, August 1999 14 RIP Iskra Dj. Popova changes inRouting thebasics, network ■

R1

Example: Choosing an Optimal Path R4

5 5

R7 40

10

R6 6

R2 A

10

R8

10

4

Budapest, August 1999

B

15

20

R3

5

5 Routing basics, RIP

10 R5 Iskra Dj. Popova

15

The Link Metric ■

Possible metrics – – – – – –

■

hop count inverse of the link bandwidth delay dynamically calculated administratively assigned combination

Traffic should be monitored and metrics adjusted

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

16

Example for Bad Metrics

A 256K 10

Bandw. 256K Metric 14 1024K 2

1024K 2

2048K 1

1 3 768K

Budapest, August 1999

3

3 768K 7 68K Bandw. 768K Metric 17 Routing basics, RIP

3 3 768K768K

Iskra Dj. Popova

B

2048K

17

RIP - Routing Information Protocol IGP, distance-vector protocol ■ First used in XNS (Xerox Network Systems) ■ Designed as a component of the networking code for the BSD release of UNIX ■

■

■

incorporated in program “routed” (rote management daemon)

First documented in rfc 1058

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

18

RIP - Characteristics Packets are sent every 30 seconds or faster when necessary ■ Route is considered down if not refreshed within 180 sec. (distance set to infinity) ■ Two kinds of messages ■

request ■ response ■

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

19

RIP - Characteristics ■

The metric is a hop-count ■

The value of 1 to 15 is used (16 denotes infinity)

Bellman-Ford algorithm is used to find the shortest paths ■ Doesn't support classless routing ■ Used only in IP networks ■

■

at first the intention was to be used in variety of networks

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

20

Dest. Link Hop A local 0 Dest. Link B 1 1 Hop B local E 2 1 0 A A 1 1 1B C 4 1 4 E 3 2 3 1

E F E HopDest. Link Hop Dest. Link E A B

local 2 3

0 F 1 C 1 G

Budapest, August 1999

local 6 8

0 1 1

Example:

6

Dest. Link Hop C local 0 B 4 1C D 5 5 1 F 6 1

Dest. Link Hop D local 0 C 5 1 G 7 1

D

7 8

Routing basics, RIP

Dest. Link Hop G G local 0 D 7 1 F 8 1

Iskra Dj. Popova

21

A 1

B C

4 2

3 E

5

6

D

table for node A

7 F After two iteratio Dest. Link ns Hop

A local 0 B 1 1 C 1 Budapest, August 21999 E 2

8 G

After three iterations

Dest. Link Hop A local 0 B 1 1 C 1 2 D 1Iskra Dj. Popova Routing basics, RIP 3

After four iteratio Dest. Link ns Hop A 0 B 1 C 2 D 3 E

local 1 1 1 2

22

A

1

B C

4 2

6

3 E

Dest. Link Hop E local 0 A 2 1 B 3 1 C 3 2 D August 3 1999 Budapest, 3

5

F

8

D

In Case of a Link Failure

Routing table of node 7 after A the before the failure of failure of link 1 link 3 G Dest. Link Dest. Link

Hop A 0 B C D Routing basics, RIP E

Hop local A 0 B 2 C 3 D 4 Iskra Dj. Popova 2 E

local 2 2 2 2

23

Split-Horizon and Poison Reverse ■

Split-horizon – the information about destination routed on the link is omitted

■

Poison reverse – the corresponding distance is set to infinity if the destination is routed on the link

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

24

Triggered Updates ■

A timer is associated with each entry in the routing table – much longer than the period of transmission of information

■

Triggered updates – request nodes to send messages as soon as they notice a change in the routing table

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

25

Advantages and Disadvantages ■

Advantages

– Simple to implement – Low requirement in processing and memory at the nodes – Suitable for small networks

■

Disadvantages – – –

Slow convergence Bouncing effect Counting to infinity problem

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

26

RIP - Message Format 0

31

Command(1) Version (1) Address family identifier (2)

Must be zero(2) Must be zero(2)

IP address (4) Must be zero(4) Must be zero(4) Metric (4)

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

27

RIP - Limitations ■

Maximum hop count of 15 – restricts the use of RIP in larger networks, but prevents the count to infinity problem (endless loops)

■

Difference in links speed is not reflected in the hop-count metrics – congested links can be still included in the best path

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

28

RIP II - Why Was Developed? Many superior IGP exists (RIP is often referred as Rest In Peace) ■ There are still many implementations of RIP ■ Given that RIP will still be used, it deserves improvements ■ RIP II is documented in RFC-1287, RFC1388 and RFC-2453 ■

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

29

RIP II - Message Format Command (1)

Version (1)

Routing domain(2)

Address family identifier (2)

Route Tag(2)

IP address(4) Subnet Mask(4) Next Hop(4) Metric(4) Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

30

RIP II - The Added Fields ■

Routing domain – used together with the next hop field to allow multiple autonomous systems to share a single wire

■

Route tag – to flag external routes (for use by EGP and BGP)

■

Subnet mask – to support subnets

■

Metric

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

31

RIP II - Improvements ■

Authentication – uses a simple password procedure

Routing per subnet ■ Support of multiple metrics ■

– hop count, throughput, measured as 10logC

Routing domains ■ Multicasting ■ August Compatible with RIP Budapest, 1999 Routing basics, RIP ■

Iskra Dj. Popova

32

RIP is not alone! IGRP and EIGRP Interior Gateway Protocol was developed in the mid1980s by Cisco Systems, Inc. ■ Designed to overcome the limitations of RIP ■ Initially worked in IP environment, but latter ported to OSI CLNP networks ■

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

33

IGRP - Main Characteristics Distance vector protocol ■ Uses a combination of metrics ■

– internetwork, delay, bandwidth, reliability and load ■

the weighting factors are set either by administrators or default values are used

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

34

IGRP - Additional flexibility ■

Wide metric ranges – allow satisfactory metric setting in internetworks with widely varying performance characteristics

■

Permits multipath routing – dual equal-bandwidth lines may run a single stream of traffic in round-robin fashion

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

35

EIGRP Enhanced version of IGRP ■ Improvements ■

– convergence properties ■

The Distributed Update Algorithm (DUAL) is used to obtain loop-freedom throughout a route computation

– operational efficiency ■

Provides compatibility with IGRP

Budapest, August 1999

Routing basics, RIP

Iskra Dj. Popova

36