Transcript address

Routing Protocols
RIP and OSPF
1
Introduction - IP Protocol
2
Classful IP Addresses
 IP address
 IPv4: 32-bit address
dotted-quad or dotted decimal
ex. 130.221.203.154 decimal = 82.DD.CB.9A hex
 = 1000 0010 . 1101 1101 . 1100 1011 . 1001 1010 binary
only 232 (4,294,967,296) IPv4 addresses available
 2 parts: netid & hostid
 “Classful” addressing
 Class A
 Class B
 Class C
 Class D - Mulitcast
 Class E - Reserved for future use
3
Classful IP Addresses - Class A
 starts with binary 0
 27 - 2 (126) Class A networks
2 reserved Class A networks
00000000 ( 0.0.0.0 )
01111111 ( 127.0.0.0 )
: default route
: loopback
 224 - 2 (16,777,214) hosts per Class A network
all 0’s
all 1’s
: ‘this network’
: ‘broadcast’
Lowest network address :
1.0.0.0
Highest network address: 126.0.0.0
0 1 2 3 4
0
netid
7 bits
8
16
24
31
hostid
24 bits
4
Classful IP Addresses - Class B
 Start with 10
 Second Octet also included in network address
 214 = 16,384 class B addresses
Lowest address : 128.0.0.0
Highest address: 191.255.0.0
0 1 2 3 4
8
1 0
netid
14 bits
15 16
24
31
hostid
16 bits
5
Classful IP Addresses - Class C
 Start with 110
 Second and third octet also part of network address
 221 = 2,097,152 addresses
Lowest address : 192.0.0.0
Highest address: 223.255.255.0
0 1 2 3
1 1 0
7
15
netid
21 bits
23 24
hostid
8 bits
31
6
Classful IP Addresses - Class D
 Start with 1110
 IP Multicasting
Lowest address : 224.0.0.0
Highest address: 239.255.255.255
0 1 2 3
1 1 1 0
7
15
23 24
28 bits
31
7
Classful IP Addresses - Class E
 Start with 1111
 Experimental
Lowest address : 240.0.0.0
Highest address: 255.255.255.254
0 1 2 3
1 1 1 1
7
15
28 bits
23 24
31
8
Classless Interdomain Routing (CIDR)
 pronounced “cider”
 RFC 1518 & 1519
 addresses two scaling problems on the Internet
 growth of backbone routing tables
 potential for the 32-bit IP address space to be exhausted
 Current IP address inefficiency exists because of the address
Class requirements (i.e., A, B, C, etc.)
 a network with 2 hosts needs a Class C network address space
(2/254 = 0.79%)
 for 256 hosts ->Class B (256/65,534 = 0.39%)
 Class B exhaustion is more severe - so give out multiple Class C’s
If one AS has 16 Class C’s, each backbone router would need 16 routing
table entries for that one AS
9
CIDR
 CIDR helps to aggregate routes
hand out contiguous blocks of Class C addresses
ex: 192.4.16 - 192.4.31
16 Class C’s
They all start with 1100 0000 - 0000 0100 - 0001 . . .
looks like a 20-bit network number - something between a Class
B and a Class C
each block must contain a number of Class C networks that is a
power of 2
 need a routing protocol that can deal with these
“classless” addresses (i.e., a non-standard network number)
 BGP version 4 is able to do this
 Network numbers are represented by (length, value) pairs
example above would have length = 20
similar to the (mask, value) for subnets
10
IP Routing
 In a packet-switched network, routing relates to the
process of choosing a link to send the packets over.
Router: the computer that makes this choice.
 an internet is composed of multiple physical networks
interconnected by computers (or network devices)
called routers
 forwarding: take a packet, look at its destination
address, consult a table, send packet to its
destination based on that table
 routing: process which builds the forwarding tables
11
IP Routing
 For routing to scale, a hierarchical routing
infrastructure is used (Internet)
 Autonomous System (AS)
a group of routers exchanging info with a common routing
protocol
a set of routers and networks managed by a single
organization
connected (except during failures): a path exists between
any two pair of nodes
 Interior Gateway Protocols (IGPs) - within an AS
 Exterior Gateway Protocols (EGPs) - between ASs
12
IP Routing
IGP1
AS #1
BGP
IGP2
AS #2
Interior Gateway Protocol (IGP)
Exterior Gateway Protocol (EGP)
13
IP Routing
 routing: graph theory problem
3
C
4
B
9
6
A
E
1
D 1
edge (link)
node (router)
F
2
cost
 nodes : hosts, switches, routers, or networks
initial case: consider all nodes as routers
 edges of graph: network links
(assume undirected)
cost is associated with each edge
relates to desirability of sending traffic over particular link
routing problem: find the lowest-cost path between any two
nodes
cost = sum of costs of all of the edges that form the path
14
IP routing
 for a simple network
calculate all shortest paths and store in a table
problems with this static approach:
does not handle node or link failures
does not consider addition of new nodes or links
assumes fixed edge costs (may want to adjust cost upward for
increased loading)
 to deal with the static routing problems, routing
protocols are used between nodes to discover the
lowest cost paths and are
distributed
centralization inhibits scalability
distributed algorithms may cause synchronization problems
dynamic
15
IP intradomain routing
 Look at two main classes of IGPs
distance vector (RIP)
link state (OSPF)
 assume all edge costs are known
16
Routing Information Protocol (RIP)
 built on a Distance-Vector algorithm
also called Bellman-Ford algorithm, after the inventors
each node constructs a one-dimensional array (a vector) of
the “distances” (costs) to all of the other nodes and
distributes the vector to its immediate neighbors
assumes that each node knows the cost of the links to its
immediate (directly connected) neighbors
a link outage is assigned an infinite cost
assume each link cost = 1, so now least-cost path is the
fewest number of router hops
 One of the most widely-used routing protocols
 RFC 1058
17
RIP example
Destination Cost NextHop
B
C
D
E
F
G
1
1

1
1

B
C
E
F
-
initial routing table at node A
Info Stored
at node
Distance to reach node
A
B
C
D
E
F
G
0
1
1

1
1

A B C D E F G
1
0
1




1  1 1 
1   
0 1  
1 0 1
  0
  0 1
 1 1 0
initial distances/costs stored at each node
18
RIP example, cont.
Destination Cost NextHop
B
C
D
E
F
G
1
1
2
1
1
2
B
C
C
E
F
F
final routing table at node A
Info Stored
at node
Distance to reach node
A
B
C
D
E
F
G
0
1
1
2
1
1
2
A B C D E F G
1
0
1
2
2
2
3
1
1
0
1
2
2
2
2
2
1
0
3
2
1
1 1 2
2 2 3
2 2 2
3 2 1
0 2 3
2 0 1
3 1 0
final distances/costs stored at each node
19
RIP example, cont
 in the absence of any topology changes, only a few exchanges
are required between neighbors before each node has
completed its routing table
 convergence: the process of getting consistent routing
information to all of the nodes
 there is no one node in the network that has all of the
information in the complete routing table
 each node only has knowledge of its own routing table
 each node has a consistent view of the network in the absence
of any centralized authority
 routing updates
 periodic (seconds to minutes)
 triggered
20
RIP, example
 RIP packets advertise costs to reach networks
(rather than routers/ nodes)
command: ‘1’ (request), ‘2’ (reply)
version: ‘1’ (or ‘2’ for RIPv2)
address family: ‘2’ (IP)
address: IP address
distance: cost metric - hop count
up to 25 routes per RIP message
well-known RIP port: UDP 520
RIP packet format
21
RIP
 RIP messages carried in UDP datagrams
 RIP version 2 (RFC 1388)
RIP-2
pass additional information
routing domain, route tag, subnet mask
interoperable with RIP
 cisco’s proprietary distance-vector Interior Gateway
Routing Protocol (IGRP)
22
Open Shortest Path First (OSPF)
 another intradomain or interior gateway protocol (IGP)
 Link-state
 ‘Open’ : non-proprietary (IETF) vs. proprietary EIGRP (cisco)
 RFC 1247
 each node is assumed to be capable of finding the state of the
link to its neighbors (up or down) and the cost of each link
 assume
reliable dissemination of link-state info
reliable flooding (all of node’s L-S info to all attached nodes)
update packet (link-state packet [LSP])
calculation of routes from the sum of all the accumulated
link-state knowledge
Dijkstra’s shortest-path algorithm
23
OSPF
 Uses IP directly (does not use UDP or TCP)
has it’s own value (protocol ID) in the IP header
 can calculate a separate set of routes for each IP type-ofservice
there can be multiple routing table entries for any
destination, one for each TOS
 each interface is assigned a dimensionless cost
can be throughput, RTT, reliability, etc.
separate cost for each TOS
24
OSPF
 when more than one equal-cost routes exist to a destination,
OSPF distributes traffic equally among routes (load balancing)
 supports subnets: an associated subnet mask with
each advertised route
allows a single IP address of any class to be broken into
multiple subnets of various sizes (variable-length subnets)
 simple authentication scheme (cleartext password,
similar to RIP-2) can be used
 replaces RIP
25
Exterior Gateway Protocols (EGPs)
 interdomain routing protocols
 used between routers of different AS’s
 historically, the predominant EGP was a protocol
called EGP (confusing)
 the newer EGP is the Border Gateway Protocol (BGP)
version 3 (RFC 1267)
RFC 1268 (use of BGP in the Internet)
version 4 (RFC 1654)
message types (RFC 1771)
updates sent using TCP
26