Transcript lecture
Introduction to
Computer Networks
Routing
University of Ilam
By: Dr. Mozafar Bag-Mohammadi
1
Outline
Routing process
Routing Algorithms
Scalability
2
Forwarding vs Routing
forwarding: to select an output port based on
destination address from the lookup table.
Minimize the lookup time.
routing: process by which the routing table is
built.
Optimize the calculating paths in case of changing
topology.
3
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
Not scale well- Broadcast storm.
4
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
5
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
6
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.
7
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
8
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
9
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
10
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
11
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
12
The count-to-infinity problem
13
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.
14
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
15
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
16
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 ))
17
Shortest Path Routing: Dijkstra Algorithm
18
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
19
Measuring Line Cost
A subnet in which the East and West parts are
connected by two lines.
20
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
21
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
22
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
23
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
Can put multiple subnets on one physical network
Subnets not visible from the rest of the Internet
24
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
25
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)
26
Collection of Subnetworks
27
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
28
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; uses a k-out-of-n rule
routing updates: peers periodically exchange their routing
tables (distance-vector)
29
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
30
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)
Speaker for backbone advertises
(AS 7)
networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be
reached along the path (AS1, AS2).
Speaker can cancel previously advertised paths
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
Routing in Ad Hoc Networks
Military vehicles on battlefield.
A fleet of ships at sea.
All moving all the time
Emergency works at earthquake.
No infrastructure.
The infrastructure destroyed.
A gathering of people with notebook
computers.
In an area lacking 802.11.
36
Ad Hoc Networks
Two nodes are neighbor if they can
communicate directly using their radio.
danger of asymmetry, limited bandwidth, low
battery life
every thing is variable:
location,
neighbor-ship,
IP address, topology
when you do not have any information about a
destination, you must discover a route for it
37
AODV (Ad hoc On-Demand Distance Vector): Route
Discovery
A wants to know about I. It broadcasts a ROUTE REQUEST
Arrows show possible reverse routes.
the request is broadcast until it reaches a node that knows
about destination.
then it forwarded along reverse path.
limited broadcast or ring search
38
Route Maintenance
D finds destinations that depend on G (i.e. E, G, I)
D finds active neighbors that use G to reach
somewhere ( i.e. A, B)
D tell them to purge their route that pass through
G,.
39