Transcript ppt - Suraj @ LUMS

IP Routing: GGP and RIP
Network Protocols and Standards
Autumn 2004-2005
Nov 04, 2004
CS573: Network Protocols and Standards
1
IP Routing Protocols


Autonomous System
Interior Gateway Protocols




Exterior Gateway Protocols




GGP
RIP
OSPF
BGP
EGP
IP Multicast Routing
MPLS
Nov 04, 2004
CS573: Network Protocols and Standards
2
IP Routing Protocols
Autonomous Systems
Nov 04, 2004
CS573: Network Protocols and Standards
3
Routing in the Internet

Routing Algorithms



Routing Protocols



Bellman-Ford
Dijkstra
Distance Vector
Link State
Routing Hierarchy



Interior Gateway Protocols (RIP, OSPF, IGRP)
Exterior Gateway Protocols (EGP, BGP, CIDR, Policy Routing)
Multicasting (IGMP)
Nov 04, 2004
CS573: Network Protocols and Standards
4
Internet from the start

First, there was ARPANET


Routers had complete information about all the possible
destinations – core routers
GGP (gateway-to-gateway) protocol was used for routing – a
distance vector protocol
R
R
H
R
R
Nov 04, 2004
H
H
CS573: Network Protocols and Standards
5
Internet from the start

Then, LANs were connected to ARPANET
ARPANET
R
LAN
Nov 04, 2004
R
LAN
R
Core Routers
LAN
CS573: Network Protocols and Standards
6
Internet from the start

Problems with above configuration:

Routing overhead increased with the number of
connected routers





Number of routes increased with the number of
connected segments
Frequency of routing exchanges increased
Higher likelihood that something went wrong somewhere
requiring updates
Number of different types of routers increased
Slow deployment of new versions of routing
algorithms
Nov 04, 2004
CS573: Network Protocols and Standards
7
Internet from the start
Backbone Network
R1
Core Router
Local Network
R2
Local Network
Nov 04, 2004
R3
Local Network
R4
CS573: Network Protocols and Standards
Local Network
8
Autonomous System
Backbone Network
R
AS
R
AS
R
Core Routers
AS
AS: Autonomous System
Nov 04, 2004
CS573: Network Protocols and Standards
9
Autonomous System

What is an autonomous system?

A set of routers and networks under the
same administration. Examples:




A single router directly connecting one local
network to the Internet
A corporate network linking several local
networks through a corporate backbone
A set of client networks served by a single ISP
NOTE: From a routing point of view, all
parts of an AS must remain connected
Nov 04, 2004
CS573: Network Protocols and Standards
10
Autonomous System

Internal connectivity within the AS means:




All routers must be connected
Parts of network connected through core AS (yes,
core is an AS!) cannot form an AS
All routers must exchange routing information in
order to maintain the connectivity (normally
achieved by using a single routing protocol)
Routers inside an AS are called “interior
gateway” and the protocol they use is called
Interior Gateway Protocol (IGP)
Nov 04, 2004
CS573: Network Protocols and Standards
11
Autonomous System


In 1982, the IGP of choice was GGP
IGPs in use today are:





RIP
OSPF
IGRP
Each AS is identified by a 16-bit number
Number is assigned by the numbering
authorities
Nov 04, 2004
CS573: Network Protocols and Standards
12
Autonomous System: Benefits






Routing overhead is lower
Network management becomes easy
Easier computation of new routes
Distribution of new software versions is
easier
Failing elements can be isolated easily
AS use an Exterior Gateway Protocol to
exchange information about reachability
Nov 04, 2004
CS573: Network Protocols and Standards
13
IP Routing Protocols
Gateway-to-Gateway Protocol
GGP
Nov 04, 2004
CS573: Network Protocols and Standards
14
GGP



The “old” ARPANET routing protocol
Defined in RFC 823
A distance-vector routing protocol



Only core routers participate in GGP
GGP messages travel in IP datagrams with
protocol type = 3
GGP measures distance in router hops. i.e.,
the number of hops along a path refers to the
number of routers
Nov 04, 2004
CS573: Network Protocols and Standards
15
GGP Message Types

4 types of GGP messages



GGP Routing Update message (type 12)
GGP Acknowledgment message (type 2/10)
GGP Echo Request or Reply (type 0 or 8)
Nov 04, 2004
CS573: Network Protocols and Standards
16
GGP Routing Update


A router sends this message to advertise the
destination networks it knows how to reach
To keep the size of message small, networks
are grouped by distance


In the message “Distance” is followed by a list of
“Net” addresses that are at this distance
Contains a field that tells how many distance
groups are being reported (3 in case below)



Nov 04, 2004
D1 – Net1, Net5, Net11
D2 – Net4, Net2, Net7, Net16
D3 – Net6, Net9
CS573: Network Protocols and Standards
17
IP Routing Protocols
Routing Information Protocol
RIP
Nov 04, 2004
CS573: Network Protocols and Standards
18
Routing Information Protocol








A distance vector based IGP
Similar to GGP
Designed at UC Berkeley
Based on Xerox XNS
Distributed with 4BSD UNIX (routed)
First RFC was 1058, current RFC is 2453
Started off in small networks and then
extended to larger networks
See Huitema, Chapter 5
Nov 04, 2004
CS573: Network Protocols and Standards
19
RIP Details

Routers are active machines


Hosts are passive machines



Advertise their routes (IP NET, distance) to others
They listen and update their routes but do not
advertise
RIP uses hop count metric
RIP messages are transmitted using UDP at
port 520
Nov 04, 2004
CS573: Network Protocols and Standards
20
RIP Route Computation

There is a cost associated with each link


Each router receives route advertisements from its
neighbors


Typically cost =1 i.e., number of hops
Advertisements show distances to all destinations in the
network
For each destination in the network:


The router takes each received advertisement and adds to it
the cost to reach that neighbor who sent this advertisement;
this gives the distance to the destination
The router selects lowest of these as path/cost to that
destination
Nov 04, 2004
CS573: Network Protocols and Standards
21
Algorithm Properties



Convergence is guaranteed in a finite time given that
topology remains static
Starting value of distance estimates to each
destination can be any non-negative number
No assumption is made as to when the updates are
sent or when the distances are computed


Each router can work based on its own clock and send its
updates asynchronously
If the network changes, routes converge to a new
equilibrium point
Nov 04, 2004
CS573: Network Protocols and Standards
22
Example
Advertisement:
Distance to A is 2
Distance to B is 3
Distance to C is 5
Cost = 1
P1
Cost = 3
Router
P3
Advertisement:
Distance to A is 1
Distance to B is 4
Distance to C is 1
P2
Cost = 2
Advertisement:
Distance to A is 2
Distance to B is 1
Distance to C is 3
Distance to
Nov 04, 2004
Through
Destination
Port P1
Port P2
Port P3
A
3
4
4
B
4
3
7
C
6
5
4
CS573: Network Protocols and Standards
23
Counting to Infinity
1
A
B
To reach target …
C
1
1
Routes to Target:
A: route via B, distance 3
B: route via D, distance 2
C: route via B, distance 3
D: direct, distance 1
10
D
1
Target
1
Assume that B to D link goes down, and B notices.
From
Via
Dist
Via
Dist
Via
Dist
Via
Dist
Via
Dist
Via
Dist
A
B
3
C
4
C
5
C
6
C
11
C
12
B
x
-
C
4
C
5
C
6
C
11
C
12
C
B
3
A
4
A
5
A
6
A
11
D
11
D
di
1
di
1
di
1
di
1
di
1
di
1
…
x = destination unreachable; di = directly connected
What if the link from C to D also goes down? Counting to Infinity!!!
Nov 04, 2004
CS573: Network Protocols and Standards
24
Some Solutions

Split Horizon



If A reaches a destination through B, it makes no sense for B
to reach the same destination through A
Instead of broadcasting the same distance vector on all
links, send different versions on each outgoing link by
removing the entries for the destinations that are reachable
through that link
Split Horizon with Poisonous Reverse


Include all the destinations in advertisements; even those
which were missing in split horizon, but…
Set those vector distances to infinity that were missing in
the simple version of split horizon
Nov 04, 2004
CS573: Network Protocols and Standards
25
Triggered Updates

Split Horizon can work in loops with two
gateways, but not with three or more


See example in book by Huitema
Another solution to deal with “count to
Infinity” problem is triggered updates


A gateway is required to send an immediate
update when any route changes. This reduces the
occurrence of loops
Flood of triggered updates resolves loops faster
when these happen
Nov 04, 2004
CS573: Network Protocols and Standards
26
RIPv2 Message Format
8
COMMAND (1-5)
16
24
VERSION (2)
31
AS NUMBER
FFFF
AUTHENTICATION TYPE
AUTHENTICATION HEADER
FAMILY OF NET 1
MUST BE ZERO
ADDRESS OF NET 1
MASK
NEXT HOP
DISTANCE TO NET 1
…………
Nov 04, 2004
CS573: Network Protocols and Standards
27
Message Format
Command
Nov 04, 2004
Meaning
1
Request for partial or full routing information
2
Response containing network-distance pairs from
sender’s routing table
3
Turn on trace mode (obsolete)
4
Turn off trace mode (obsolete)
5
Reserved for Sun Microsystems Internal Use
CS573: Network Protocols and Standards
28
RIPv2 Message Format



Address format is not limited to TCP/IP
RIP can be used with multiple network protocol
suites
Family of net i:



Identifies the protocol family under which the network
address should be interpreted
IP addresses are assigned value 2
Next hop

The sending router can specify another router’s IP address
as next hop for the network


Nov 04, 2004
Set to 0.0.0.0 for sender itself
Solves similar problem (extra hop) as ICMP redirect
CS573: Network Protocols and Standards
29
RIP Metrics and Updates

By default, RIP uses hop count as the
distance metric




Integers 1 through 15
16 denotes infinity
Packets are normally sent every 30sec
If a route is not refreshed within 180
seconds, distance is set to infinity and
later entry is removed
Nov 04, 2004
CS573: Network Protocols and Standards
30
Input Processing

How to process incoming RIP packets?


Examine entries one by one
Validation check





Address is valid class A, B, or C
Network number is not 127
Host port is not a “broadcast” address
Metric is not larger than infinity (16)
Incorrect entries are ignored

Nov 04, 2004
And should be reported as errors
CS573: Network Protocols and Standards
31
Input Processing


Metric for entry is increased by link cost
Routing table is searched for an entry
corresponding to the destination


If the entry is not present, it is added
If the entry is present but with a larger metric


Entry is present and next hop router is sender of
response message


Entry is updated and timer restarted
Metric is updated and timer restarted
For all other cases, entry is ignored
Nov 04, 2004
CS573: Network Protocols and Standards
32
RIP Responses

A separate response is prepared for all connected
interfaces/ports

Information sent on different ports may vary due to




Split Horizon processing
Subnet summarization
For triggered updates: may include only those entries that
have been updated since last transmission
Maximum message size: 512 bytes (up to 25 entries)



Multiple messages have to be sent if more than 512 bytes
Source IP address is that of the interface on which the
message is sent
Destination IP address is the broadcast address
Nov 04, 2004
CS573: Network Protocols and Standards
33