Transcript lecture

Introduction to
Computer Networks
Routing
University of Ilam
By: Dr. Mozafar Bag-Mohammadi
1
Routing Process

Question? How to populate the lookup table?

Primary solutions:


Build the lookup table Manually? Is it practical?
The answer is no.
Flooding- Broadcast to all node except the one we
have received the packet.


Waste the bandwidth
Does not scale well.
2
Overview
A

Network as a Graph
C


1
3
4

6
2
1
B
9
E
F
1
D
Problem: Find lowest cost, or shortest, path between
two nodes
The process is distributed and this makes it
complicated, i.e, it may create loop.
Factors


static: topology
dynamic: load
3
Distance Vector

Each node maintains a set of triples
(Destination, Cost, NextHop)

Exchange updates with directly connected neighbors



periodically ( on the order of several seconds)
whenever its table changes (called triggered update)
Each update is a list of pairs:
(Destination, Cost)

Update local table if receive a “better” route



smaller cost
came from next-hop
Refresh existing routes; delete if they time out
4
Example
B
C
A
D
E
F
Destination
A
C
D
E
F
G
Cost
1
1
2
2
2
3
NextHop
A
C
C
A
A
A
G
•Distance of other nodes from Node B.
•The cost between two nodes has been assumed 1.
•All nodes keep a routing table from themselves.
5
The Bellman-Ford Algorithm
•Bellman-Ford algorithm solve the distance
Vector problem in general case.
1. Set: Xo = (  ,  ,  ,…,  ).
2. Send updates of components of Xn to neighbors
3. Calculate: Xn+1 = F(Xn)
4. If Xn+1
 Xn then go to (2)
5. Stop
6
Bellman-Ford Algorithm
Example:

Calculate from R8

1
R1
2


R1

4
R6
3
2
4
2
4
R4
2
R3
3
R7
2
1
R2
2
step
2
R8

1
R6

3


4
R4
R5
4
R3
2nd
1
R2
2

R5
2
R7
2
3
3
R8
7
Bellman-Ford Algorithm
6
R1
4
R2
1
1
4
4
R3
5
R1
Result:
R4
R7
2
2
3
5
1
R2
R5
4
R6
3
2
4
2
R4
2
R3
R6
R8
4
1
4
3
2
R5
2
step
2
3
2
3rd
6
2
2
R7 3
R8
8
Node Failure






F detects that link to G has failed
F sets distance to G to infinity and sends update to A
A sets distance to G to infinity since it uses F to reach G
A receives periodic update from C with 2-hop path to G
A sets distance to G to 3 and sends update to F
F decides it can reach G in 4 hops via A
B
C
A
D
E
F
G
9
Routing Loops






link from A to E fails
A advertises distance of infinity to E
B and C advertise a distance of 2 to E
B decides it can reach E in 3 hops; advertises this to A
A decides it can read E in 4 hops; advertises this to C
C decides that it can reach E in 5 hops…
B
C
A
D
E
F
G
10
The count-to-infinity problem
11
Loop-Breaking Heuristics

Set infinity to a reasonably small number. For
instance, RIP sets to 16

Split horizon: Don’t announce the distance to
the node the distance has been gotten from.

Split horizon with poison reverse: Instead of
not announcing the distance put negative
numbers.
12
Link State

Strategy


send to all nodes (not just neighbors) information
about directly connected links (not entire routing
table)
Link State Packet (LSP)




id of the node that created the LSP
cost of the link to each directly connected neighbor
sequence number (SEQNO)
time-to-live (TTL) for this packet
13
Link State (cont.)

Reliable flooding



store most recent LSP from each node
forward LSP to all nodes but one that sent
it
generate new LSP periodically



increment SEQNO
start SEQNO at 0 when reboot
decrement TTL of each stored LSP

discard when TTL=0
14
Route Calculation


Dijkstra’s shortest path algorithm
Let
 N denotes set of nodes in the graph
 l (i, j) denotes non-negative cost (weight) for edge (i, j)
 s denotes this node
 M denotes the set of nodes incorporated so far
 C(n) denotes cost of the path from s to node n
M = {s}
for each n in N - {s}
C(n) = l(s, n)
while (N != M)
M = M union {w} such that C(w)
is the minimum for all w in (N - M)
for each n in (N - M)
C(n) = MIN(C(n), C (w) + l(w, n ))
15
Shortest Path Routing: Dijkstra Algorithm
16
Subnetting



Add another level to address/routing hierarchy:
subnet
Subnet masks define variable partition of host part
Subnets visible only within site
Network number
Host number
Class B address
1111111111111111111
0000000000000000
Subnet mask (255.255.0.0)
Network number
Subnet ID
Host ID
Subnetted address
17
Subnet Example
Subnet
Net
host
Subnet mask: 255.255.255.128.
Subnet number: 128.96.34.0
128.96.34.15
128.96.34.1
111….1.0xxx….x
H1
R1
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.128
128.96.34.130
128.96.34.139
128.96.34.129
H2
R2
H3
128.96.33.14
128.96.33.1
Subnet mask: 255.255.255.0
Subnet number: 128.96.33.0
Forwarding table at router R1
Subnet #
128.96.34.0
128.96.34.128
128.96.33.0
Subnet Mask
255.255.255.128
255.255.255.128
255.255.255.0
Next Hop
interface 0
interface 1
R2
18
Route Propagation

Know a smarter router





Autonomous System (AS)




hosts know local router
local routers know site routers
site routers know core router
core routers know everything
corresponds to an administrative domain
examples: University, company, backbone network
assign each AS a 16-bit number
Two-level route propagation hierarchy


interior gateway protocol (each AS selects its own)
exterior gateway protocol (Internet-wide standard)
19
Architecture of Routing Protocols
Interior Gateway
Protocols (IGP) :
inside autonomous
systems
UUNet
OSPF, IS-IS,
RIP, EIGRP, ...
IGP
AS 701
Metric Based
AS 6431
BGP
Policy Based
IGP
IGP
AT&T Research
Exterior Gateway
Protocols (EGP) :
between autonomous
systems
EGP
AT&T
Common Backbone
AS 7018
20
The Most Common Routing Protocols
BGP
RIP
Cisco proprietary
TCP
UDP
IP
OSPF IS-IS EIGRP
(and ICMP)
Routing protocols exchange network
reachability information between routers.
21
Interior Gateway Protocols

RIP: Route Information Protocol





developed for XNS
distributed with Unix
distance-vector algorithm
based on hop-count
OSPF: Open Shortest Path First




recent Internet standard
uses link-state algorithm
supports load balancing
supports authentication
22
EGP: Exterior Gateway Protocol


concerned with reachability, not optimal routes
Protocol messages



neighbor acquisition: one router requests that
another be its peer; peers exchange reachability
information
neighbor reachability: one router periodically tests
if the another is still reachable; exchange
HELLO/ACK messages; uses a k-out-of-n rule
routing updates: peers periodically exchange their
routing tables (distance-vector)
23
BGP-4

BGP = Border Gateway Protocol

Is a Policy-Based routing protocol

Is the de facto EGP of today’s global Internet

Relatively simple protocol, but configuration is complex and the
entire world can see, and be impacted by, your mistakes.
•
1989 : BGP-1 [RFC 1105]
–
Replacement for EGP (1984, RFC 904)
•
1990 : BGP-2 [RFC 1163]
•
1991 : BGP-3 [RFC 1267]
•
1995 : BGP-4 [RFC 1771]
–
Support for Classless Interdomain Routing (CIDR)
24
BGP-4: Border Gateway Protocol

AS Types

stub AS: has a single connection to one other AS


multihomed AS: has connections to more than one AS


refuses to carry transit traffic
transit AS: has connections to more than one AS


carries local traffic only
carries both transit and local traffic
Each AS has:


one or more border routers
one BGP speaker that advertises:



local networks
other reachable networks (transit AS only)
gives path information
25
Policy-Based vs. Distance-Based Routing?
Minimizing
“hop count” can
violate commercial
relationships that
constrain interdomain routing.
Host 1
Cust1
YES
ISP1
NO
ISP3
ISP2
Cust3
Host 2
Cust2
26
Why not minimize “AS hop count”?
National
ISP1
National
ISP2
YES
NO
Regional
ISP3
Cust3
Regional
ISP2
Cust1
Regional
ISP1
Cust2
27
BGP Operations Simplified
Establish Peering on
TCP port 179
AS1
BGP
Peers Exchange
All Routes
AS2
Exchange Incremental
Updates
While connection
is ALIVE exchange
route UPDATE messages
28
Two Types of BGP Neighbor Relationships
AS1
• External Neighbor (eBGP) in a
different Autonomous Systems
• Internal Neighbor (iBGP) in the
same Autonomous System
eBGP
iBGP
Physical Connection
AS2
Logical (TCP) Connection
29
Four Types of BGP Messages

Open : Establish a peering session.

Keep Alive : Handshake at regular intervals.

Notification : Shuts down a peering session.

Update : Announcing new routes or withdrawing
previously announced routes.
announcement
=
Network prefix + attributes
30
AS Path Attribute (cont.)
BGP at AS YYY will
never accept a route
whose AS Path
contains YYY. This
avoids interdomain
routing loops.
AS702
UUnet
10.22.0.0/16
AS Path = 1 333 702 877
Don’t Accept!
31
IP Version 6

Features








128-bit addresses (classless)
multicast
real-time service
authentication and security
autoconfiguration
end-to-end fragmentation
protocol extensions
Header


40-byte “base” header
extension headers (fixed order, mostly fixed length)




fragmentation
source routing
authentication and security
other options
32
Tunneling
33
Routing for Mobile Hosts
1- finding location of the mobile host
2- hand-off
3- security
34
Routing for Mobile Hosts (2)
Packet routing for mobile users.
35