A Link-State Routing Algorithm

(Dynamic Algorithm)

Dijkstra’s algorithm
• net topology, link costs known notation:
to all nodes
• c(x,y): link cost from
– accomplished via “link state node x to y; = ∞ if not
broadcast” direct neighbors
– all nodes have same info • D(v): current value of
• computes least cost paths from cost of path from source to
one node (‘source”) to all dest. v
other nodes • p(v): predecessor node
– gives forwarding table for along path from source to
that node v
• iterative: after k iterations, • N': set of nodes whose
know least cost path to k dest.’s least cost path definitively
known
14
 Link State Routing
1. Discover neighbors, learn network addresses.
2. Set distance/cost metric to each neighbor.
3. Construct packet telling all learned.
4. Send packet to, receive packets from other routers.
5. Compute shortest path to every other router.

15
 Dijkstra’s algorithm: example
resulting shortest-path tree from u:

v w
u z
x y
5
resulting forwarding table in u: v 3 w
destination link u 2 5z
2 3 1
v (u,v) 1 x y 2
x (u,x) 1
y (u,x)
w (u,x)
z (u,x) 16
 Dijkstra’s algorithm, discussion
algorithm complexity: n nodes
 each iteration: need to check all nodes, w, not in N
 n(n+1)/2 comparisons
oscillations possible:
e.g., link cost equals amount of carried traffic:
given these costs, new routing resulting in new costs

17
 Building Link State Packets

(a) A network. (b) The link state packets for this network.
18
 Distance Vector Routing algorithm
• Distance Vector routing is intra-domain protocols,
inside Autonomous system, but not between Autonomous
system.( inside one region)
• distance-vector routing are based on the least-cost goal.
• Distance Vector developed by Bellman-Ford algorithm.
• Bellman equation is used to find the least cost (shortest
distance) between a source to destination.
• Base on RIP protocol.

19
 How Does D.V Works
• A distance vector routing algorithm operates by
having each router maintain a table (i.e., a vector)
giving the best known distance to each destination
and which link to use to get there.

• These tables are updated by exchanging information

with the neighbors router. Every router knows the
best link to reach each destination.
20
 Distance vector algorithm
Bellman-Ford equation (dynamic programming)
let
dx(y) := cost of least-cost path from x to y
Then
dx(y) = min {c(x,v) + dv(y) }
v
cost from neighbor v to destination y
cost to neighbor v
min taken over all neighbors v of x
Note: v,x are the neighbors' of source

21
 Distance vector algorithm
key idea:
 from time-to-time, each node sends its own distance vector
estimate to neighbors
 when x receives new DV estimate from neighbor, it
updates its own DV using B-F equation:

Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N

 under minor, natural conditions, the estimate Dx(y)

converge to the actual least cost dx(y)

22
Bellman-Ford example
clearly Distance V of sources to destination
5 dv(z) = 5, dx(z) = 3, dw(z) = 3
v 3 w ( neighbors' of source)
u 2 5z then B-F equation says:
2 3 1 du(z) = min { c(u,v) + dv(z),
1 x y 2 c(u,x) + dx(z),
1 c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
node achieving minimum is next
hop in shortest path, used in forwarding table
23
 Comparison of LS and DV algorithms
message complexity Robustness (Failure): what
• LS: with n nodes, E links, O(nE) happens if router malfunctions?
msgs sent LS:
• DV: exchange between neighbors – node can advertise incorrect
only link cost
– convergence time varies – each node computes only its
own table
speed of convergence DV:
• LS: O(n2)
algorithm requires
– DV node can advertise
O(nE) msgs
incorrect path cost
– may have oscillations
– each node’s table used by
• DV: convergence time varies others
– may be routing loops – error propagate thru network
– count-to-infinity problem
24
 Hierarchical Routing
• As networks grow in size, the router routing
tables grow proportionally.
• Not only the router memory consumed by
ever-increasing tables, but more CPU time
is needed to scan them and more bandwidth
is needed to send status reports about them.
• So router can not have table about the entire
network.

25
 Hierarchical Routing
• When hierarchical routing is used, the routers
are divided into what we will call regions.

• Each router knows all the details about how to

route packets to destinations within its own
region but knows nothing about the internal
structure of other regions.(ie EGRP protocol IGRP)
26
 Hierarchical routing
• routers into regions,
“autonomous systems” (AS)
• routers in same AS run same
routing protocol called: IGBP
( Interior Gate Way Protocol)
• routers in different AS can run
different intra-AS routing protocol
called:EGBP ( Exterior Gate Way
Protocol.)

27
 Inter-AS tasks Example:
 suppose router in AS1 AS1 must:
receives datagram 1. learn which dests are
destined outside of AS1: reachable through
 router should forward AS2,and which through
packet to gateway AS3
router, but which one? 2. propagate this reach
ability info to all routers
in AS1
3c job of inter-AS routing!
3a
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1
28
Hierarchical routing.

29
 RIP ( Routing Information Protocol)
• It is a very simple protocol based on distance vector routing.
• distance vector algorithm
– distance metric: # hops (max = 15 hops), each link has cost 1
– DVs exchanged with neighbors every 30 sec in response message (aka
advertisement)
– each advertisement: list of up to 25 destination subnets (in IP addressing
sense)
from router A to destination subnets:
u v subnet hops
A B w u 1
v 2
z x w 2
C D x 3
y y 3
z 2 30
 RIP Characteristics
• Distance vector routing protocol.

• Uses hop count as a path selection metric.

• Three types of timers.

• Multiple stability features.

31
Timers in RIP

32
 Rip timer
• The periodic timer controls the advertising of regular update

messages.

• Expiration Timer if there is a problem on an internet and no update

is received within the allotted 180 s, the route is considered expired

and the hop count of the route is set to 16, which means the

destination is unreachable.( Because 15 hop max)

• Garbage Collection Timer When the information about a route

becomes invalid.

33
Hop Count -- 15 Hop Limit

Note: After 15 hop the

destination unreachable

34
RIP: example

z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
z B 7
x -- 1
…. ....
35
RIP: example

z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
A 5
z B 7
x -- 1
…. ....
36
 OSPF (Open Shortest Path First)
• “open”: publicly available
• uses link state algorithm
– LS packet dissemination
– topology map at each node
– route computation using Dijkstra’s algorithm
• OSPF advertisement carries one entry per neighbor
• advertisements flooded to entire AS
– carried in OSPF messages directly over IP (rather than TCP
or UDP
• security: all OSPF messages authenticated (to prevent
malicious intrusion)
• multiple same-cost paths allowed (only one path in RIP)
37
Hierarchical OSPF
boundary router
backbone router

backbone
area
border
routers

area 3
internal
routers
area 1
area 2
38
Hierarchical OSPF
• two-level hierarchy: local area, backbone.
– link-state advertisements only in area
– each nodes has detailed area topology; only know
direction (shortest path) to nets in other areas.
• area border routers: “summarize” distances to nets
in own area, advertise to other Area Border routers.
• backbone routers: run OSPF routing limited to
backbone.
• boundary routers: connect to other AS’s.

39
 OSPF—An Interior Gateway
Routing Protocol

The relation between ASes, backbones, and

aa 40
are as in OSPF.
OSPF—An Interior Gateway
Routing Protocol

The five types of OSPF messages

41
 Internet inter-AS routing: BGP

• BGP (Border Gateway Protocol): inter-domain routing

protocol
– “ holds the Internet together”
• BGP provides :
– eBGP: obtain subnet reach ability information from
neighboring ASs.
– iBGP: propagate reach ability information to all AS-
internal routers.
• allows subnet to advertise its existence to rest of Internet:

42
 BGP basics
 BGP session: two BGP routers (“peers”) exchange BGP
messages:
 advertising paths to different destination network prefixes (“path vector”
protocol)
 exchanged over semi-permanent TCP connections

• The IBGP used to connect different routers have same AS(same company)
• The EBGP used to connect different routers have different AS(different company)

3c
BGP
3a message
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1
43
BGP basics: distributing path information
 using eBGP session between 3a and 1c, AS3 sends prefix
reachability info to AS1.
 1c can then use iBGP do distribute new prefix info to all routers in
AS1
 1b can then re-advertise new reachability info to AS2 over 1b-to-
2a eBGP session
 when router learns of new prefix, it creates entry for prefix
in its forwarding table.

eBGP session
3a iBGP session
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1
44
 BGP messages

• BGP messages exchanged between peers over TCP connection

• BGP messages:
– OPEN: opens TCP connection to peer and
authenticates sender
– UPDATE: advertises new path (or withdraws old)
– KEEP ALIVE: keeps connection alive in absence
of UPDATES; also ACKs OPEN request
– NOTIFICATION: reports errors in previous msg;
also used to close connection

45
DHCP &IP addresses: how to get one
Q: How does a host get IP address?
• hard-coded by system admin in a file
– Windows: control-panel->network-
>configuration->tcp/ip->properties
– UNIX: /etc/[Link]
DHCP: Dynamic Host Configuration Protocol:
dynamically get address from as server
– “plug-and-play”

46
DHCP: Dynamic Host Configuration Protocol
goal: allow host to dynamically obtain its IP address from
network server when it joins network
DHCP overview: (pool operation)
– host broadcasts “DHCP discover” msg [optional]
– DHCP server responds with “DHCP offer” msg [optional]
– host requests IP address: “DHCP request” msg
– DHCP server sends address: “DHCP ack” msg

47
DHCP: more than IP addresses

DHCP can return more than just allocated IP

address on subnet:
 address of first-hop router for client
 name and IP address of DNS sever

48
 DHCP: example • DCP server formulates
DHCP ACK containing
DHCP DHCP client’s IP address, IP
DHCP UDP address of first-hop
DHCP IP router for client, name &
DHCP Eth
Phy IP address of DNS server

 encapsulation of DHCP
DHCP DHCP server, frame forwarded
DHCP UDP to client, demuxing up to
DHCP IP DHCP at client
DHCP Eth router with DHCP
DHCP
Phy server built into  client now knows its IP
router address, name and IP
address of DNS server, IP
address of its first-hop
router

49
 ICMP: internet control message protocol
• used by hosts & routers to Type Code description
communicate network- 0 0 echo reply (ping)
level information 3 0 dest. network unreachable
– error reporting: unreachable 3 1 dest host unreachable
host, network, port, 3 2 dest protocol unreachable
protocol 3 3 dest port unreachable
3 6 dest network unknown
– echo request/reply (used by
3 7 dest host unknown
ping)
4 0 source quench (congestion
– ICMP msgs carried in IP control - not used)
datagrams 8 0 echo request (ping)
• ICMP message: type, code 9 0 route advertisement
plus first 8 bytes of IP 10 0 router discovery
11 0 TTL expired
datagram causing error 12 0 bad IP header

50
 ICMP Applications

 PING: The ping checks whether a host is alive & reachable or

not. This is done by sending an ICMP Echo Request packet to the host,
and waiting for an ICMP Echo Reply from the host.

 TRACE ROUTE: Trace route is a used to records the route

through the Internet between your computer and a specified

destination computer. It also calculates and displays the amount of

time each hop took.

51
 Trace route and ICMP
 source sends series of UDP  when ICMP messages
segments to dest arrives, source records
 first set has TTL =1 RTTs
 second set has TTL=2, etc. stopping criteria:
 unlikely port number  UDP segment eventually
 when nth set of datagrams arrives at destination host
arrives to nth router:  destination returns ICMP
 router discards datagrams “port unreachable”
 and sends source ICMP message (type 3, code 3)
messages (type 11, code 0)  source stops

 ICMP messages includes

name of router & IP address
3 probes 3 probes

3 probes 52
 ICMP
• ICMP messages carried on IP packet.

53