Transcript comm3380-slides-week07-review

Routing Algorithms
Distance Vector Routing
• Each node knows the distance (=cost) to its directly connected
neighbors
• A node sends periodically a list of routing updates to its
neighbors.
• If all nodes update their distances, the routing tables eventually
converge
• New nodes advertise themselves to their neighbors
2. Link State Routing
• Each node knows the distance to its neighbors
• The distance information (=link state) is broadcast to all nodes in
the network
• Each node calculates the routing tables independently
2008/2009
COMM3380
Slide 1
Distance Vector Protocol
Example
Routing Information Protocol (RIP)
2008/2009
COMM3380
Slide 2
Routing Information Protocol
(RIP)
•
•
•
•
RIP is an IGP for use within an autonomous system
Designed for small networks with same speed links
Uses UDP port 520
Request and Response messages - requests update
and responds with update
• Broadcasts request out every RIP configured
interface on start up of routing protocol.
• Upon receipt of response message, routes are
checked in current routing table, if absent, routes are
added, if existing, route only updated if it has a lower
hop count
2008/2009
COMM3380
Slide 3
RIP broadcast from a neighbouring
router
• If the destination is not in the table, then create a new
table entry for it.
• If the destination is already in the table via a different
route but the received list gives a shorter distance to
it, then change the table entry.
• If the destination is already in the table via the same
route, but the received list gives a distance that is
different then change the table entry.
• Otherwise do nothing with this destination/distance
pair of values.
2008/2009
COMM3380
Slide 4
RIP : Count to infinity problem
• B – X -> distance = 0
• A – X -> distance = 1
• If connection from B to X
fails -> B – X marked
unreachable
• A broadcasts DV list
• B sees A-X at distance 1
-> thinks link B-A-X exists
with distance 2 ->
updates table -> routing
loop between A and B for
traffic destined for X
2008/2009
COMM3380
Slide 5
RIP : Count to infinity problem
• Now B broadcast its DV list
with X reachable via A at
distance = 2
• A sees distance B-X has
changed from distance 0 to 2 > A updates A-X to distance =
3
• A broadcasts -> B see A-X with
distance=3 -> B updates entry
B-X to distance=4
• Continues until distance = 16
reached -> unreachable
2008/2009
COMM3380
Slide 6
Split Horizon
• Solves trivial count-to-infinity problem
• Routers never advertise the cost of a
destination back to its next hop, i.e.
where it learned it from
• Poison Reverse -> advertise back
infinity
2008/2009
COMM3380
Slide 7
Routing Loop Avoidance
• Routing loops can still occur in any
network due to router configuration
errors.
• To prevent -> IP packet has a time to
live (TTL) value in its header->
decremented by each router as it
receives the packet. If the TTL of a
packet becomes zero, the router
discards it.
2008/2009
COMM3380
Slide 8
RIP Message Format
IP header
20 bytes
UDP header
RIP message
8 bytes
RIP Frame Enscapsulated in UDP datagram
RIP
0
4
8
12
message
16
20
command (1-6)
version (1)
address family
24
28 ......31
all zeros
all zeros
32-bit IP address
all zero
all zero
metric (1-16)
upto 24 more route with same 20 byte format
:
2008/2009
COMM3380
Slide 9
RIP v1
• Command specifies Request = 1 or Response - 2
• Version Ripv1 = 1
• AFI - Address-Family Identifier - specifies protocol, IP
=2
• IP address of destination route
• Metric - hop count to destination
• Up to 25 routes - AFI, IP and Metric combinations
2008/2009
COMM3380
Slide 10
RIP Operations
1.
2.
3.
4.
5.
On start-up, RIP broadcast Request message out each RIP enabled interface.
From then on, it listens for Request and Response messages from others.
Neighbour routers respond to initial Request with full routing table in Response
Message(s) - 25 routes per Response packet.
On receipt of Response message,
•
If route entry is new, it is added to routing table with address of advertising
router.
•
If the route entry is not new and the hop count is the same, the timer is
updated.
•
If the route entry is not new and the hop count is lower, the new next hop
information is entered.
•
If the route entry if not new and the hop count is greater, the route is
marked as Hold down.
Routers continue to send gratuitous Response message(s) out each RIP
enable interface every 30 seconds
2008/2009
COMM3380
Slide 11
RIP Version 2 Changes
• Classless routing and subnet masks in
routing updates
• Routing update authentication
• Next-hop addresses for each route
• External route tags
• Multicast route updates, instead of broadcast
• Same procedures, timers & functions of v1
2008/2009
COMM3380
Slide 12
RIPv2 Packet
•
•
•
•
•
•
•
•
•
•
Command specifies Request = 1 or Response - 2
Version Ripv2 = 2
AFI - Address-Family Identifier - specifies protocol, IP = 2, 0xffff ->
Authentication Entry in place of first routing entry
Route Tag - mark external or redistributed routes into RIP
Network - IP address of destination route
Subnet Mask - allows for classless routing
Metric - hop count to destination
Up to 25 routes - AFI, IP and Metric combinations
Maximum datagram size 512 octets
Authentication by password in update
2008/2009
COMM3380
Slide 13
RIP v1 & v2
• Metric of hop count only allowable of 1-15. At 16, destination is
considered unreachable, to prevent routing loops. This limits
the depth of a network to run RIP.
• Update timer - Router sends gratuitous Response message out
each interface every 30 seconds with full routing table.
• Expiration timer - initialized to 180 seconds for a new route
and reset upon update of that route. If timer expires, hop count
set to 16, unreachable, but still advertised.
• Flush timer - set to 240 seconds upon initialization, once
expired, route is removed from routing table and no longer
advertise.
• Holddown timer - Cisco only - set for 180 seconds when
updated route has a higher hop count than previous
advertisement.
2008/2009
COMM3380
Slide 14