Transcript pptx

CMPT 471
Networking II
RIP
1
Dynamic Routing
 In very simple small and stable networks static
routing may be adequate.
 As networks grow, become more complex, include
multiple or redundant paths between hosts and
routers, or change frequently, static routing
becomes difficult to manage
 Redundant routes are only useful if they can be
used immediately on failure of the original route
 In a large network the reporting of failure and
response by a network manager cannot be
accomplished on a short enough time scale for
the redundant routes to be useful
© Janice Regan, 2006
2
Dynamic Routing
 A routing algorithm to update the routing tables
to respond to changes and failures in the network
becomes a necessary component of the system
 Addition of a routing algorithm does not change
the forwarding algorithm used to deliver packets,
segments …
 Addition of a routing algorithm allows dynamic
changes to the entries in the routing table, so
those entries can be updated to respond to
 Changes in network topology
 Changes in load through the network
© Janice Regan, 2006
3
Autonomous Systems (AS)
 Group of connected networks and routers, or
nodes, controlled by a single administrative
authority.
 May contain one or more networks (need not be
subnets of one network, or networks of the same
hardware type)
 There is at least one route between any pair of
nodes in the AS
 Administrative authority can specify if packets
originating in their AS are permitted to pass
through any other AS (Company A may not wish
it’s data to pass through Company B’s routers)
© Janice Regan, 2006
4
Autonomous Systems (AS)
 Routers within an AS use a common routing
protocol (interior routing protocol or IRP) for all
members of the group
 Defines mechanisms for discovering,
validating, and maintaining routes within the
autonomous system
 Some routers in the autonomous system (those
connected to the larger Internet) also support a
routing protocol for propagating subset of
routing information to other autonomous
systems on the internet (Exterior routing
protocol or ERP)
© Janice Regan, 2006
5
Conceptual view of AS
© Janice
Regan,
2006
Figure
16.3
Comer (2000)
6
Sample routing protocols
 IRP (Internal routing protocol, within AS)
 GGP: gateway to gateway protocol (no longer used)
 RIP: routing information protocol (implemented using
routed, for simple networks only)
 OSPF: Open Shortest Path First
 ERP (External routing protocol, between AS’s)
 BGP: ERP usually used in the internet.
© Janice Regan, 2006
7
Routing algorithm
 A routing algorithm or routing protocol process
determines
 How much information is sent to other routers
 Which information is sent to other routers
 How often information is sent to other routers
 Which other routers to exchange information with
 best route from present router to every other router
in the AS
 When and on what basis to change routes due to
changes in the AS
© Janice Regan, 2006
8
Static Routing
 All routing information specified by
administrator and installed at system boot time.
Details are determined by the operating system
being used
 For Ubuntu LINUX,


Default static routing information can be found in
/etc/network/network/interfaces
To add additional static routes through the
interface
up route add [-net|-host] <host/net>/<mask> gw <host/IP> dev <Interface>
© Janice Regan, 2006
9
Distance-Vector Routing
 Each node exchanges information only with
neighbor nodes
 Neighbors are both directly connected to same AS
 Each node maintains vector of link costs for each
directly attached node and distance and next-hop
values for each destination node in the system
 A node must transmit large amounts of
information
 Distance vector to all neighbors, Containing estimated
path cost to all nodes in a configuration and possibly
next hop labels
© Janice Regan, 2006
10
Distance-Vector Routing
 Changes take long time to propagate
(count to infinity)
 Used by first generation routing algorithm
for ARPANET and by Routing Information
Protocol (RIP, routed) RIP is an internal
gateway protocol (IGP) used between
routers within an AS
 There is no built in mechanism to prevent
routing loops
© Janice Regan, 2006
11
Distance Vector Routing
 Once every T seconds each node i, sends each
of its neighbors (one hop distant) a list, of
estimated delays from itself to every other node j.
 Similarly each node will receive routing
information from each of its neighbors every T
sec.
 The routing data received are used to update
the routing table of the node
© Janice Regan, 2006
12
Distance Vector Routing
 Similarly each station will receive routing
information from each of its neighbors every T
sec.
 Note: the existing routing table for station i at
time t is not used directly to compute the
routing table for station i at time t+T, the
‘distance’ to each neighbor station k, lki, and
the delay vectors from each neighbor
station j, dij are used d kj  min [d ij  lki ]
iA
© Janice Regan, 2006
13
Updating the routing table
 Use the distributed version of the Bellman-Ford
algorithm.
 d i1 
d 
i2 

Di 
  
to j d 
 iN 
 si1 
s 
i2 

Si 
  
 
 siN 
d kj  min [d ij  lki ]
iA
© Janice Regan, 2006
Di delay vector from node i
Si successor node vector
sij next node in minimum
delay route from i
N # of nodes in network
lki current estimate of
delay between neighbors k, I
The set of neighbor nodes
14
Distance Vector Routing : from node J
Original network and original delays
A
5
B
2
1
F
2
4
J
D
4
8
H
G
4
5
4
4
I
6
2
3
4
C
4
E
I
6
3
2
K
L
F
I
A
A 2
E
3
F
6
F
7
B
B 4
F
7
F
8
F
9
C
G 8
F 11
F
12
H 12
D
G 6
F
9
F
10
H
8
E
A 3
E
2
I
6
F
8
F
0 0
F
3
F
4
F
5
G
G 2
F
5
F
6
F
7
H
K 5
J 11
K
7
H
4
I
I 3
0
0
I
4
J
7
J
J 4
J
4
0
0
J
3
K
K 5
J
7
K
3
0
0
L
K 7
J
9
K
5
L
2
Delay lJi
© Janice Regan, 2006
lJF
4
lJI
4
J
K
lJK
3
15
Calculate new routes at node J
iA
Delay vectors received
Measured
Delay lJi
lJF
4
lJK
3
lJI
4
SF DF SI DI
5
SK DK
A
A 2
E
B
A 7
E 10
F 10
C
G 9
F 13
H
9
D
G 7
F 11
H
6
E
A 5
E
2
F
8
F
0 0
F
4
F
3
G
G 3
F
7
F
6
H
K 3
F 10
H
4
I
I 4
0
0
F
7
J
J 2
J
3
J
4
K
K 3
J
7
0
0
L
3
L
K 6
F 10
Janice Regan © 2005-1012
skj  i
d kj  min [d ij  lki ]
Later time, some routes
weights have changed
F
5
DK  [d k1 , d k 2 ,, d kN ]T
DF+IJF
DF+4
DI+IJI
DI+4
6
11
13
11
9
4
7
7
8
6
7
10
9
14
17
15
6
8
11
14
4
7
11
14
DK+IJK
DK+3
8
13
12
9
11
6
9
7
10
7
3
6
New table
for node J
SJ
DJ
F
F
K
K
I
F
F
K
I
0
K
K
6
11
12
9
6
4
7
7
4
0
3
6
16
Actual Practice
 The routing table is updated each time a packet
of routing information arrives from a neighbor
 The updating process consists of
 Comparing the sum of the delay to the particular
node from which the update came and the cost of
propagation to that node to the present cost.
 If the cost decreases replace the path for that
node
 If there is presently no such route add the route
 Always replace the cost to the directly connected
nodes
© Janice Regan, 2006
17
Problems: distance vector routing
 Changes take long time to propagate
(count to infinity)
 slow convergence
 There is no built in mechanism to prevent
routing loops
 Oscillation and instability is possible
© Janice Regan, 2006
18
Count to Infinity problem
 In practice when conditions in a
network change, the change will take
time to propagate across the network.
 Good news propagates quickly across
a network
 Bad news propagates slowly across
the network
© Janice Regan, 2006
19
Count to Infinity problem:
 Consider a linear network with 6 stations
A
B
C
D
E
F
 A is down initially and all other stations know this
 A comes up, at the time of the first exchange of routing
information after A comes up B learns that A is alive
 At the time of the second exchange of routing
information after A comes up C learns that A is alive
 This pattern continues till the time of the sixth data
exchange after A comes up, when F learns that A is
alive. At this point all stations in the network have
learned the good news
© Janice Regan, 2006
20
Count to Infinity problem:
A
B
C
 Initially B can reach A and C can reach A through B
 When the link from B to A fails then B updates its routing table




to indicate it cannot reach A directly.
When a update arrives at B from C, B notices that C has a
route to A with a cost of 2, and adopts that route. The new
route has a cost of (2+1)=3
When an update from B reaches C, C notices the cost of the
route to A through B has increased to 3 so it updates it own
routes cost to A to (3+1)=4
The process continues as the cost to route A counts to infinity.
In the more general network the costs increment as shown on
the next slides
© Janice Regan, 2006
21
Count to Infinity problem:
 Linear network with 6 stations (all single hop
costs 1)
A
B
C
D
E
F
 The number of iterations necessary to indicate
that the link to 1 is down (cost infinite) is in fact
infinite. It is clear that the delay increases as
the number of iterations increase, but it is still
necessary to ‘count to infinity’ to reach the
correct link costs for link A-B down.
© Janice Regan, 2006
22
Count to Infinity problem:
 Linear network with 6 stations (all single hop costs 1)
A
B
C
D
E
F
 A is up initially and all other stations know this
 A goes down, at the time of the first exchange of routing
information after A goes down B hears nothing from A.
Since there is no direct path to A, B chooses an indirect
path to A through C (which actually goes through B itself,
but B doesn’t know this)
 The first eight exchanges are illustrated on the next slide.
© Janice Regan, 2006
23
Count to Infinity problem:
 Linear network with 6 stations, single hop costs 1)
A
INITIALLY
AFTER 1 EXCHANGE
AFTER 2 EXCHANGES
AFTER 3 EXCHANGES
AFTER 4 EXCHANGES
AFTER 5 EXCHANGES
AFTER 6 EXCHANGES
AFTER 7 EXCHANGES
AFTER 8 EXCHANGES
© Janice Regan, 2006
B
C
D
E
F
1
3
3
5
5
7
7
9
9
2
2
4
4
6
6
8
8
10
3
3
3
5
5
7
7
9
9
4
4
4
4
6
6
8
8
10
5
5
5
5
5
7
7
9
9
24
Routing Information Protocol
 RIP, The simplest dynamic distance vector




routing protocol still in use, was built and adopted
before a formal standard was available (RFC
1058 RIPv1, 2453 RIPv2 )
Implemented in LINUX as the routed process.
Adequate only for small and stable ASs
based on the Bellman-Ford (or distance vector)
algorithm
helps control count to infinity problem by
specifying a maximum hop count of 15
© Janice Regan, 2006
25
Routing Information Protocol
 Uses a simple metric, hop count
 Not designed to deal with more complicated
dynamic metrics such as delay, reliability or
load (these can cause route oscillations)
 Helps control oscillation between equal cost
routes by retaining original route unless a route
with a lower cost is found.
 Helps prevent slow convergence (after changes
in the topology of the network) by sending update
messages immediately after updates have been
completed (triggered updates)
© Janice Regan, 2006
26
Routing Information Protocol
 Helps prevent routing loops by
 omitting routes learned from a particular neighbor in the
updates sent to that neighbor or other neighbors reached
through the same network interface (split-horizon)
 advertising routes learned from a particular neighbor with
cost 16 (∞) in the updates sent to that neighbor or other
neighbors on the same broadcast network (split-horizon
with poison reverse),
 Nodes are either active (routers) or passive (silent hosts)
 Active nodes advertise their routing information
 Passive nodes listen for advertisements and update their
routing tables accordingly
© Janice Regan, 2006
27
Count to Infinity: split infinity
A
B
C




A learns the route to C from B
C learns the route to A from B
Initially B can reach A and C can reach A through B
When the link from B to A fails then B updates its routing table
to indicate it cannot reach A directly.
 Without split infinity: When a update arrives at B from C, B
notices that C has a route to A with a cost of 2, and adopts that
route. The new route has a cost of (2+1)=3
 Split infinity: When an update arrives at B from C, it does not
include an entry for A because C learned the route to A from B.
B does not update its entry for A, it has no alternative for the
broken direct route to A. Eventually, C’s route to A times out .
© Janice Regan, 2006
28
Count to ∞ : split infinity poison reverse
A




B
C
A learns the route to C from B
C learns the route to A from B
Initially B can reach A and C can reach A through B
When the link from B to A fails then B updates its routing table
to indicate it cannot reach A directly.
 Without split infinity: When a update arrives at B from C, B
notices that C has a route to A with a cost of 2, and adopts that
route. The new route has a cost of (2+1)=3
 Split infinity with poison reverse: B sends an update with a cost
of infinity back to C. If C really has a route that is not through B
the route sent by B will never be used, otherwise C will
immediately update its path cost to A to infinity (Protects
reverse routes)
29
© Janice Regan, 2006
Nodes in RIP
 Nodes can be hosts or routers
 Each node keeps a routing table for every
possible destination network (or active host) in
the AS. Each entry in the table includes
 network or host address, gateway router address,
metric and interface
 a timer measuring the amount of time since the entry
was last updated.
 Active nodes send routing information to all
neighbors
© Janice Regan, 2006
30
Neighbors in RIP
 All hosts or routers 1 hop from a node are the
neighbors of that node
 This means that all hosts on a network
segment, including the router or routers for that
segment (with a single broadcast address) are
neighbors
 Directly connected routers are also neighbors
 Update messages containing routing
information are sent only to neighbors
© Janice Regan, 2006
31
Initialization: RIP
 Each node needs to know its own address
 Each node must be able to identify the links (interfaces)
to which it is attached.
 Each node starts with a routing table that contains a
single entry, its own localhost
 Each router broadcasts (advertises) that single entry
through its interfaces to all attached networks. The
information reaches all neighbor nodes (directly
connected routers)
 All nodes directly connected to a network segment
receive the information from all routers on that network
segment, and add that information to their routing
tables.
© Janice Regan, 2006
32
Updating and RIP
 Then tables are updated or maintained
 Each router will periodically broadcast its
routing table
 Each router will process the received
updates, adding new entries, updating
entries for which a lower cost path has been
located and updating entries for directly
connected nodes whose cost changed
 If the routing information changes during the
update process the router will immediately
broadcast the modified tables to its
neighbors (called a triggered broadcast)
© Janice Regan, 2006
33
Updating and RIP
 When no further changes occur the
routing table has converged to the
topology of the network
 When a change is made to the network
topology (removing, adding, or modifying
a node)
 The neighbor nodes will detect the change
and update their routing tables
 the routing algorithm will converges to a new
topology consistent with the changes
© Janice Regan, 2006
34
Timers in RIP
 RIP uses three timers
 The first timer keeps track of the route
advertisement time. Each time it expires
(usually every 30 seconds) a message
containing the routing information is sent
 The second and third types of timers are
associated with each entry in the routing
table. Each route is given an expiration timer
and a garbage collection timer
© Janice Regan, 2006
35
Timers in RIP
 RIP uses three timers
 The second and third types of timers are an
expiration timer and a garbage collection timer

If no update information is received before the
expiration timer (usually 180 seconds) expires
the route is considered unreachable and its cost
is set to ∞ (16)
 When the expiration timer expires a garbage
collection timer is set (usually 120 seconds).
When the garbage collection timer expires the
routing table entry is deleted
© Janice Regan, 2006
36
RIP1 message format
© Janice Regan, 2006
Comer
2000: fig 16.5
37
RIP2 message format
© Janice Regan, 2006
Comer
2000: fig 16.6
38
RIP messages
 RIP messages are sent encapsulated in UDP
packets (port 520). The length of the message
is transmitted only by UDP
 RIPv1 cannot be used for variable length
subnets or for CIDR addresses (must use
RIPv2). If subnets are used all receivers must
be able to interpret them.
 Family gives the family of protocols used
(TCP/IP 2)
 0.0.0.0 is address for default route
© Janice Regan, 2006
39
RIP messages (RIPv1 and RIPv2)
 Two types of messages request (1) and
response (2)
 A router may request routing information
 A router may reply to a request by sending a
response
 Solicited responses will contain only the
requested routes, not all available routes
 A router may sent unsolicited responses
(periodic broadcasts of routing table
information for all routes)
© Janice Regan, 2006
40
Improvements in RIP2
 Next hop field helps eliminate “double
hops” a-b-a
 The netmask means that RIP2
 Can handle subnet routing (not just within
subnetted network, extension to RIP1 could
do that)
 Can deal with CIDR addresses
 The route tag identifier

Used to flag external (to AS) routes
© Janice Regan, 2006
41
Improvements in RIP2
 Includes an authentication procedure
 The first entry in a packet can be replaced by
an authentication segment (command will
become a 32 bit field containing the
command and authentication information,
packet length, key … see RFC 2453, 2082
for details )
 RIP2 uses random variations on time delays
 Triggered updates are delayed by 1-5 s
 Periodic advertisements are randomized by
adding between -5 and 5 seconds
© Janice Regan, 2006
42
Why use RIP2
 “With the advent of OSPF and IS-IS,
there are those who believe that RIP is
obsolete. While it is true that the newer
IGP routing protocols are far superior to
RIP, RIP does have some advantages.
Primarily, in a small network, RIP has
very little overhead in terms of bandwidth
used and configuration and management
time. RIP is also very easy to implement,
especially in relation to the newer IGPs. “
 Quote from RFC 2453 (RIP2)
© Janice Regan, 2006
43