程序代写代做代考 algorithm dns comp0023-lecture12-dvrouting

comp0023-lecture12-dvrouting

Introduction to�
Intra-Domain Routing

Stefano Vissicchio
UCL Computer Science

COMP0023

Agenda

•  We delve into network layer’s main functionality

1.  Setting
•  Context
•  Routing players

2.  Intra-domain routing problem definition

Let’s consider a network with several LANs

host host host DNS…

router router

5.6.7.0/24

5.6.7.11
host

1.2.3.156 1.2.3.48

DNS

1.2.3.19
1.2.2.0/23

router

Several LANs can belong to a single organization

host host host DNS…

router router

5.6.7.0/24

5.6.7.11
host

1.2.3.156 1.2.3.48

DNS

1.2.3.19
1.2.2.0/23

router

Internet

Domain
(e.g., UCL)

Collecting evidence from the real world

•  Traceroute exposes real Internet paths
– Unix: traceroute
– Windows: tracert

•  It displays all hops on the path between host where
launched and
–  it sends a sequence of carefully constructed packets

that “expire” after 1 hop, 2 hops, …
– each of those packets elicits ICMP error from

router that many hops from sender

A traceroute from UCL to Cambridge

traceroute to www.cl.cam.ac.uk (128.232.0.20), 64 hops max, 40 byte
packets

1 cisco (128.16.64.1) 0.370 ms 0.322 ms 0.361 ms
2 128.40.255.29 (128.40.255.29) 0.483 ms 0.348 ms 0.487 ms
3 128.40.20.1 (128.40.20.1) 0.486 ms 0.342 ms 0.362 ms
4 128.40.20.62 (128.40.20.62) 0.486 ms 0.474 ms 0.363 ms
5 ulcc-gsr.lmn.net.uk (194.83.101.5) 0.485 ms 0.346 ms 0.362 ms
6 london-bar1.ja.net (146.97.40.33) 0.485 ms 0.470 ms 0.488 ms
7 po10-0.lond-scr.ja.net (146.97.35.5) 0.735 ms 0.722 ms 0.610 ms
8 po0-0.cambridge-bar.ja.net (146.97.35.10) 5.232 ms 4.964 ms 4.734

ms
9 route-enet-3.cam.ac.uk (146.97.40.50) 4.982 ms 4.841 ms 4.860 ms
10 route-cent-3.cam.ac.uk (192.153.213.194) 4.984 ms 4.964 ms

4.861 ms

A traceroute from UCL to Cambridge

traceroute to www.cl.cam.ac.uk (128.232.0.20), 64 hops max, 40 byte
packets

ms
9 route-enet-3.cam.ac.uk (146.97.40.50) 4.982 ms 4.841 ms 4.860 ms
10 route-cent-3.cam.ac.uk (192.153.213.194) 4.984 ms 4.964 ms

4.861 ms

Router

Host
Interface 0
(IP address A)

Router

Interface 0
(IP address B) Interface 1

(IP address C)

Interface 0
(IP address D)

Subnet 2
128.40.255.29/24

The big picture emerging from the traceroute

…
Subnet 1
128.16.64.0/24

Three fields
•  Destination: destination IP
•  Outgoing interface: on which to forward packet for the

given destination
•  Metric: total cost to reach the destination

– depends on interfaces’ metrics (set by net admins)

Destination Interface Metric

A 0 0

B 1 0

Routers keep routing tables

•  Each host (interface) has unique 32-bit IP address
– E.g., 128.16.64.1

•  Must every router in entire Internet know about every
other router and host?
No; interfaces on same subnet share IP prefix

•  e.g., 128.16.64/24 for 128.16.64.1

•  IP routing destination is subnet’s prefix
– Not single IP addresses

Routers’ destinations are IP prefixes

•  Packet for destination D arrives
•  Router searches D in destination field of routing table

– using longest-prefix match
•  If more than one route match D, choose the route with

the longest prefix
•  Possible outcomes:

–  if entry for D, forward on interface in the entry
–  if no entry, no route known à drop packet

Routers use routing table to forward packets

•  Packet for destination D arrives
•  Router searches D in destination field of routing table

– using longest-prefix match
•  If more than one route match D, choose the route with

the longest prefix
•  Possible outcomes:

–  if entry for D, forward on interface in the entry
–  if no entry, no route known à drop packet

Routers use routing table to forward packets

How to populate routing tables
for any router in a domain?

Interface 0
(IP address A)

Router

Host

Router

Interface 0
(IP address B) Interface 1

(IP address C)

Interface 0
(IP address D)

At startup, a router initializes its routing table
for directly connected subnets

…

Subnet 2
128.40.255.0/24

Destination Interface Metric

128.16.64/24 0 0

128.40.255.0/24 1 0
Subnet 1
128.16.64.0/24

Interface 0
(IP address A)

Router

Host

Router

Interface 0
(IP address B) Interface 1

(IP address C)

Interface 0
(IP address D)

At startup, a router initializes its routing table
for directly connected subnets

…

Subnet 2
128.40.255.0/24

Destination Interface Metric

128.16.64/24 0 0

128.40.255.0/24 1 0
Subnet 1
128.16.64.0/24

Packets to other destinations
would be dropped

Interface 0
(IP address A)

Router

Host

Router

Interface 0
(IP address B) Interface 1

(IP address C)

Interface 0
(IP address D)

At startup, a router initializes its routing table
for directly connected subnets

…

Subnet 2
128.40.255.0/24

Destination Interface Metric

128.16.64/24 0 0

128.40.255.0/24 1 0
Subnet 1
128.16.64.0/24

Routing protocols are needed to add
information on remote destinations

Agenda

•  We delve into network layer’s main functionality

1.  Setting
•  Context
•  Routing players

2.  Intra-domain routing problem definition

•  Each router has an ID and
several interfaces
–  Linked to many other

routers and subnets

•  Each router must choose the
next-hop for received packets
–  Packets include info on

destinations (IP addresses)
•  But not on intermediate hops

Consider an arbitrary network

•  Routing protocols define
information and messages
exchanged by routers
–  For routers to accumulate

state (routing table entries)
to forward packets

•  Routing protocols also
determine how to choose
between alternative next-hops

Routing protocols build routing tables

•  Provide good performance
– Typically, choose “good” paths for any pair of routers

•  Automated path computation
–  Possibly, efficient in time and memory

•  Deal with failures
– Routes must be coherent with topology

Intra-domain routing goals

•  View network as weighted graph
– Routers are vertices, links are edges
– Link metrics are edge weights

Typical solution: shortest path routing

20
5

5
5

Shortest paths problem:
– What path between two vertices offers minimal sum of

edge weights?

•  Classic graph algorithms find single-source shortest paths
when the entire graph is known centrally
– Dijkstra’s Algorithm, Bellman-Ford Algorithm

•  Typically, no central knowledge of entire graph
–  Each router only knows its own interfaces’ addresses

Typical solution: shortest path routing

•  Network components are not reliable
–  Links may be cut, router or their interfaces may fail

•  Changing networks induce hazards
– Need for (fast) re-convergence to new, correct paths

after a failure
–  Potential for forwarding loops

•  Amplify traffic à congest links
– TTL will eventually expire, but typically too late

–  Possibility of temporary disconnections (i.e., blackholes)

Challenge: deal with changing networks

Distance Vector Routing

Stefano Vissicchio
UCL Computer Science

COMP0023

Agenda

•  We are now ready to study Distance Vector routing

1.  Algorithm

2.  Pathologies

3.  Optimizations

Basic Distance Vector Algorithm

•  Distributed Bellman-Ford (DBF)

•  Principle: “tell everything you know to your
neighbours”
– Periodically, send all your routing table entries

(destination and metric fields) to all your
neighbouring routers

Basic Distance Vector Algorithm: DBF �
(Failures Not Yet Considered)

Upon receipt of routing table entry for destination D with
metric m on interface i:

m += configured metric for interface i
rt = lookup(D) in rou0ng table
if (rt = “not found”) then
rt_new = new rou0ng table entry
rt_new.dst = D; rt_new.metric = m; rt_new.iface = i
add rt_new to rou0ng table

else if (m < rt.metric) then rt.metric = m; rt.iface = i 28 Distance Vector: Example •  Consider simple network where all nodes are routers, addresses are simply single letters •  Initial routing tables when routers first start: 29 A B C D E Dst I/f Metric A local 0 Dst I/f Metric D local 0 Dst I/f Metric B local 0 Dst I/f Metric E local 0 Dst I/f Metric C local 0 0 1 0 1 0 1 0 1 2 2 0 1 Dst Metric A 0 Dst Metric A 0 Distance Vector: Iteration 1 •  Routers incorporate received announcements: 30 A B C D E Dst I/f Metric A local 0 B 1 1 D 0 1 Dst I/f Metric D local 0 A 0 1 E 1 1 Dst I/f Metric B local 0 A 0 1 C 2 1 E 1 1 Dst I/f Metric E local 0 D 0 1 B 1 1 C 2 1 Dst I/f Metric C local 0 B 0 1 E 1 1 0 1 0 1 0 1 0 1 2 2 0 1 Distance Vector: Iteration 2 •  Routers incorporate received announcements: 31 Dst I/f Metric A local 0 B 1 1 D 0 1 E 0 2 C 1 2 Dst I/f Metric D local 0 A 0 1 E 1 1 B 0 2 C 1 2 Dst I/f Metric B local 0 A 0 1 C 2 1 E 1 1 D 1 2 Dst I/f Metric E local 0 D 0 1 B 1 1 C 2 1 A 1 2 Dst I/f Metric C local 0 B 0 1 E 1 1 A 0 2 D 1 2 A B C D E 0 1 0 1 0 1 0 1 2 2 0 1 Distance Vector: Iteration 2 •  Routers incorporate received announcements: 32 Dst I/f Metric A local 0 B 1 1 D 0 1 E 0 2 C 1 2 Dst I/f Metric D local 0 A 0 1 E 1 1 B 0 2 C 1 2 Dst I/f Metric B local 0 A 0 1 C 2 1 E 1 1 D 1 2 Dst I/f Metric E local 0 D 0 1 B 1 1 C 2 1 A 1 2 Dst I/f Metric C local 0 B 0 1 E 1 1 A 0 2 D 1 2 Convergence: routing tables no longer changing; routes reflect up-to-date knowledge of topology A B C D E 0 1 0 1 0 1 0 1 2 2 0 1 Link Failure (1) 33 Dst I/f Metric A local 0 B 1 1 D 0 1 E 0 2 C 1 2 Dst I/f Metric D local 0 A 0 1 E 1 1 B 0 2 C 1 2 Dst I/f Metric B local 0 A 0 1 C 2 1 E 1 1 D 1 2 Dst I/f Metric E local 0 D 0 1 B 1 1 C 2 1 A 1 2 Dst I/f Metric C local 0 B 0 1 E 1 1 A 0 2 D 1 2 A B C D E 0 1 0 1 0 1 0 1 2 2 0 1 ! ! Link Failure (1) 34 Dst I/f Metric A local 0 B 1 Inf D 0 1 E 0 2 C 1 Inf Dst I/f Metric D local 0 A 0 1 E 1 1 B 0 2 C 1 2 Dst I/f Metric B local 0 A 0 Inf C 2 1 E 1 1 D 1 2 Dst I/f Metric E local 0 D 0 1 B 1 1 C 2 1 A 1 2 Dst I/f Metric C local 0 B 0 1 E 1 1 A 0 2 D 1 2 A B C D E 0 1 0 1 0 1 0 1 2 2 0 1 Link Failure (2) 35 Dst I/f Metric A local 0 B 1 Inf D 0 1 E 0 2 C 1 Inf Dst I/f Metric D local 0 A 0 1 E 1 1 B 0 2 C 1 2 Dst I/f Metric B local 0 A 0 Inf C 2 1 E 1 1 D 1 2 Dst I/f Metric E local 0 D 0 1 B 1 1 C 2 1 A 1 2 Dst I/f Metric C local 0 B 0 1 E 1 1 A 0 2 D 1 2 A B C D E 0 1 0 1 0 1 0 1 2 2 0 1 Dst Metric A 0 B Inf D 1 E 2 C Inf Link Failure (2) 36 Dst I/f Metric A local 0 B 1 Inf D 0 1 E 0 2 C 1 Inf Dst I/f Metric D local 0 A 0 1 E 1 1 B 0 2 C 1 2 Dst I/f Metric B local 0 A 0 Inf C 2 1 E 1 1 D 1 2 Dst I/f Metric E local 0 D 0 1 B 1 1 C 2 1 A 1 2 Dst I/f Metric C local 0 B 0 1 E 1 1 A 0 2 D 1 2 A B C D E 0 1 0 1 0 1 0 1 2 2 0 1 Dst Metric A 0 B Inf D 1 E 2 C Inf Problem: D ignores the update for the route to B because the metric is worse than the one it already has. DV Algorithm, Revised •  Upon receipt of routing table entry for destination D with metric m on interface i: m += metric for interface i rt = lookup(D) in rou

Related Posts