Transcript An Introduction to Computer Networks

An Introduction
to
Computer Networks
Lecture 9: Routing
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
Univ. of Tehran
Introduction to Computer Network
1
Outline



Routing process
Routing Algorithms
Scalability
Univ. of Tehran
Introduction to Computer Network
2
Routing Process


Question? How to populate the lookup table?
Forwarding vs Routing

forwarding: to select an output port based on destination
address from the lookup table.


routing: process by which the routing table is built.


Minimize the lookup time.
Optimize the calculating paths in case of changing topology.
Primery 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
Not scale well- Broadcast storm.
Univ. of Tehran
Introduction to Computer Network
3
Overview

Network as a Graph
A
6
1
3
4
C



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
Univ. of Tehran
Introduction to Computer Network
4
Distance Vector

Each node maintains a set of triples
(Destination, Cost, NextHop)

Exchange updates 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
Univ. of Tehran
Introduction to Computer Network
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
Univ. of Tehran
Introduction to Computer Network
6
Bellman-Ford Algorithm
Example
R1


1
Calculate from
R8
R1
2
R3


4

1
step
Univ. of Tehran
R4
4
R5
R6
2
3
R8

2
R3

R7
2
1
R2
4
3


4
R4
R5
2
2nd
1
R2
2

2
4
3
2
Introduction to Computer Network
R7
3
R6
2
2
3
R8
7
Bellman-Ford Algorithm
6
1
R1
3rd
4
R2
2
2
step
4
Solution:
R1
2
R3
Univ. of Tehran
4
2
4
R6
3
R7
2
3
R8
5
1
R2
4
3
2
R5
4
1
R4
2
4
R3
5
1
6
2
R4
3
2
R5
R6
2
Introduction to Computer Network
R7 3
2
R8
8
Example
B
C
A
D
E
G
F
Destination Cost
A
1
C
1
D
2
E
2
F
2
G
3
NextHop
A
C
C
A
A
A
•Distance of other nodes from Node B.
• The cost between two nodes has been assumed 1.
•All nodes keep a routing table from themselves.
Univ. of Tehran
Introduction to Computer Network
9
Routing Loops

Example 1







F detects that link to G has failed
F sets distance to G to infinity and sends update t o 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
Example 2





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
AUniv.
decides
it can read
E in 4 hops; advertises this to C
of Tehran
Introduction to Computer Network
10
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.
Univ. of Tehran
Introduction to Computer Network
11
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
Univ. of Tehran
Introduction to Computer Network
12
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
Univ. of Tehran
Introduction to Computer Network
13
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)to Computer
+ l(w,
n ))
Univ.
of Tehran
Introduction
Network
14
Link state (Example)
•Two list confirmed and tentative
•Always, select the one with
minimum distance from the
tentative list.
B
5
A
10
3
C
11
D
2
Step
Confirmed
1
(D,0,-)
2
(D,0,-)
(B,11,B), (C,2,C)
3
(D,0,-), (C,2,C)
(B,5,C), (A, 13,C)
Univ. of Tehran
Tentative
Introduction to Computer Network
15
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
Univ. of Tehran
Introduction to Computer Network
16
Metrics

Original ARPANET metric



measures number of packets enqueued on each link
took neither latency or bandwidth into consideration
New ARPANET metric



stamp each incoming packet with its arrival time (AT)
record departure time (DT)
when link-level ACK arrives, compute
Delay = (DT - AT) + Transmit + Latency



if timeout, reset DT to departure time for retransmission
link cost = average delay over some time period
Fine Tuning


compressed dynamic range
replaced dynamic with link utilization
Univ. of Tehran
Introduction to Computer Network
17
How to Make Routing Scale


Flat versus Hierarchical Addresses
Inefficient use of Hierarchical Address Space



class C with 2 hosts (2/255 = 0.78% efficient)
class B with 256 hosts (256/65535 = 0.39%
efficient)
Still Too Many Networks


routing tables do not scale
route propagation protocols do not scale
Univ. of Tehran
Introduction to Computer Network
18
Internet Structure
Recent Past
NSFNET backbone
Stanford
ISU
BARRNET
MidNet
regional
regional
Westnet
regional
Berkeley
PARC
UNM
NCAR
UNL
KU
UA
Univ. of Tehran
Introduction to Computer Network
19
Internet Structure
Today
Large corporation
“Consumer
” ISP
Peering
point
Backbone service provider
Peering
point
“ Consumer ” ISP
Large corporation
“Consumer ”ISP
Small
corporation
Univ. of Tehran
Introduction to Computer Network
20
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
Univ. of Tehran
Subnet ID
Subnetted address
Host ID
Introduction to Computer Network
21
Subnet Example
Subnet
Net
host
Subnet mask: 255.255.255.128.
Subnet number: 128.96.34.0
128.96.34.15
H1
111….1.0xxx….x
128.96.34.1
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
H3
128.96.33.14
H2
R2
128.96.33.1 Forwarding
Subnet mask: 255.255.255.0
Subnet number: 128.96.33.0
Univ. of Tehran
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
Introduction to Computer Network
Next Hop
interface 0
interface 1
R2
22
Forwarding Algorithm
D = destination IP address
for each entry (SubnetNum, SubnetMask, NextHop)
D1 = SubnetMask & D
if D1 = SubnetNum
if NextHop is an interface
deliver datagram directly to D
else
deliver datagram to NextHop




Use a default router if nothing matches
Not necessary for all 1s in subnet mask to be
contiguous
Can put multiple subnets on one physical network
Subnets
not visible
fromtothe
rest
of the Internet 23
Univ. of Tehran
Introduction
Computer
Network
Supernetting



Assign block of contiguous network numbers to
nearby networks
Called CIDR: Classless Inter-Domain Routing
Represent blocks with a single pair
(first_network_address, count)



Restrict block sizes to powers of 2
Use a bit mask (CIDR mask) to identify block size
All routers must understand CIDR addressing
Univ. of Tehran
Introduction to Computer Network
24
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)
Univ. of Tehran
Introduction to Computer Network
25
EGP: Exterior Gateway Protocol

Overview



Designed for tree-structured Internet
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;
routing updates: peers periodically exchange their routing
tables (distance-vector)
Univ. of Tehran
Introduction to Computer Network
26
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
Univ. of Tehran
Introduction to Computer Network
27
BGP Example

Speaker for AS2 advertises reachability to P and Q

network 128.96, 192.4.153, 192.4.32, and 192.4.3, can
be reached directly from AS2
Customer P
(AS 4)
128.96
192.4.153
Customer Q
(AS 5)
192.4.32
192.4.3
Customer R
(AS 6)
192.12.69
Customer S
192.4.54
192.4.23
Regional provider A
(AS 2)
Backbone network
(AS
1)
Regional provider B
(AS 3)
(AS 7)

Speaker for backbone advertises


networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can
be reached along the path (AS1, AS2).
Univ. of Tehran
Introduction to Computer Network
Speaker
can cancel
previously advertised paths
28