CS计算机代考程序代写 database assembly algorithm 9.Routing

9.Routing

COMP 3331/9331:
Computer Networks and

Applications
Week 8

Network Layer: Data Plane + Control Plane
(Routing)

Chapter 4: Section 4.3
Chapter 5: Section 5.1 – 5.2, 5.6

1

4.1 Overview of Network layer
§ data plane
§ control plane

4.2 What’s inside a router
4.3 IP: Internet Protocol

§ datagram format
§ fragmentation
§ IPv4 addressing
§ network address translation
§ IPv6

Network Layer, data plane: outline

2

IPv6: motivation

v initial motivation: 32-bit address space soon
to be completely allocated.

v additional motivation:
§ header format helps speed

processing/forwarding
§ header changes to facilitate QoS

IPv6 datagram format:
§ fixed-length 40-byte header
§ no fragmentation allowed

3

https://www.google.com/intl/en/ipv6/statistics.html

IPv6 datagram format

priority: identify priority among datagrams in flow (traffic class)
flow Label: identify datagrams in same “flow.”

(concept of“flow” not well defined).
next header: identify upper layer protocol for data

data

destination address
(128 bits)

source address
(128 bits)

payload len next hdr hop limit
flow labelpriver

32 bits

4

Other changes from IPv4

v checksum: removed entirely to reduce processing
time at each hop

v options: allowed, but outside of header, indicated
by “Next Header” field

v ICMPv6: new version of ICMP
§ additional message types, e.g., “Packet Too Big”
§ multicast group management functions

5

Transition from IPv4 to IPv6
v not all routers can be upgraded

simultaneously
§ no “flag days”
§ how will network operate with mixed IPv4 and IPv6

routers?

v tunneling: IPv6 datagram carried as payload
in IPv4 datagram among IPv4 routers

IPv4 source, dest addr
IPv4 header fields

IPv4 datagram
IPv6 datagram

IPv4 payload

UDP/TCP payload
IPv6 source dest addr

IPv6 header fields

6

Tunneling (IPv6 over IPv4)

physical view:
IPv4 IPv4

A B

IPv6 IPv6

E

IPv6 IPv6

FC D

logical view:

IPv4 tunnel
connecting IPv6 routers E

IPv6 IPv6

FA B

IPv6 IPv6

7

flow: X
src: A
dest: F

data

A-to-B:
IPv6

Flow: X
Src: A
Dest: F

data

src:B
dest: E

B-to-C:
IPv6 inside

IPv4

E-to-F:
IPv6

flow: X
src: A
dest: F

data

B-to-C:
IPv6 inside

IPv4

Flow: X
Src: A
Dest: F

data

src:B
dest: E

physical view:
A B

IPv6 IPv6

E

IPv6 IPv6

FC D

logical view:

IPv4 tunnel
connecting IPv6 routers E

IPv6 IPv6

FA B

IPv6 IPv6

Tunneling (IPv6 over IPv4)

IPv4 IPv4

8

flow: X
src: A
dest: F

data

A-to-B:
IPv4

Flow: X
Src: A
Dest: F

data

src:B
dest: E

B-to-C:
IPv4 inside

IPv4

E-to-F:
IPv4

flow: X
src: A
dest: F

data

B-to-C:
IPv4 inside

IPv4

Flow: X
Src: A
Dest: F

data

src:B
dest: E

physical view:
A B

IPv4 IPv4

E

IPv4 IPv4

FC D

logical view:

IPv4 tunnel
connecting IPv4 routers E

IPv4 IPv4

FA B

IPv4 IPv4

Tunneling (IPv4 over IPv4)

IPv4 IPv4

9

Used in VPNs

5.1 introduction
5.2 routing protocols
v link state
v distance vector
v hierarchical routing

5.6 ICMP: The Internet
Control Message
Protocol

Network layer, control plane: outline

Self study (not on
exam)

10

Network-layer functions

v forwarding: move packets
from router’s input to
appropriate router output

data plane

control plane

Two approaches to structuring network control plane:
§ per-router control (traditional)
§ logically centralized control (software defined networking)

Recall: two network-layer functions:

§ routing: determine route
taken by packets from source
to destination

11

Per-router control plane

Routing
Algorithm

Individual routing algorithm components in each and every
router interact with each other in control plane to compute
forwarding tables

data
plane

control
plane

4.1 • OVERVIEW OF NETWORK LAYER 309

tables. In this example, a routing algorithm runs in each and every router and both
forwarding and routing functions are contained within a router. As we’ll see in Sec-
tions 5.3 and 5.4, the routing algorithm function in one router communicates with
the routing algorithm function in other routers to compute the values for its forward-
ing table. How is this communication performed? By exchanging routing messages
containing routing information according to a routing protocol! We’ll cover routing
algorithms and protocols in Sections 5.2 through 5.4.

The distinct and different purposes of the forwarding and routing functions can
be further illustrated by considering the hypothetical (and unrealistic, but technically
feasible) case of a network in which all forwarding tables are configured directly by
human network operators physically present at the routers. In this case, no routing
protocols would be required! Of course, the human operators would need to interact
with each other to ensure that the forwarding tables were configured in such a way
that packets reached their intended destinations. It’s also likely that human configu-
ration would be more error-prone and much slower to respond to changes in the net-
work topology than a routing protocol. We’re thus fortunate that all networks have
both a forwarding and a routing function!

Values in arriving
packet’s header

1

2
3

Local forwarding
table

header

0100
0110
0111
1001

1101

3
2
2
1

output

Control plane

Data plane

Routing algorithm

Figure 4.2 ! Routing algorithms determine values in forward tables

M04_KURO4140_07_SE_C04.indd 309 11/02/16 3:14 PM

12

data
plane

control
plane

Logically centralized control plane
A distinct (typically remote) controller interacts with local
control agents (CAs) in routers to compute forwarding tables

Remote Controller

CA

CA CA CA CA

13

5.1 introduction
5.2 routing protocols
v link state
v distance vector
v Hierarchical routing

5.6 ICMP: The Internet
Control Message
Protocol

Network layer, control plane: outline

14

Context and Terminology
“End hosts”

“Clients”, “Users”
“End points”

“Interior Routers”

“Border Routers”

“Autonomous System (AS)” or “Domain”
Region of a network under a single administrative entity

“Route” or “Path”

15

Internet Routing

v Internet Routing works at two levels

v Each AS runs an intra-domain routing protocol that
establishes routes within its domain
§ AS — region of network under a single administrative entity
§ Link State, e.g., Open Shortest Path First (OSPF)
§ Distance Vector, e.g., Routing Information Protocol (RIP)

v ASes participate in an inter-domain routing protocol that
establishes routes between domains
§ Path Vector, e.g., Border Gateway Protocol (BGP)

16

u

yx

wv

z
2

2
1

3

1

1

2

5
3

5

graph: G = (N,E)

N = set of routers = { u, v, w, x, y, z }

E = set of links ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

Graph abstraction

17

Graph abstraction: costs

u

yx

wv

z
2

2
1

3

1

1

2

5
3

5 c(x,x’) = cost of link (x,x’)
e.g., c(w,z) = 5

cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

key question: what is the least-cost path between u and z ?
routing algorithm: algorithm that finds that least cost path

18

Link Cost

v Typically simple: all links are equal

v Least-cost paths => shortest paths (hop count)

v Network operators add policy exceptions
§ Lower operational costs
§ Peering agreements
§ Security concerns

19

5.1 introduction
5.2 routing protocols
v link state
v distance vector
v hierarchical routing

5.6 ICMP: The Internet
Control Message
Protocol

Network layer, control plane: outline

20

Routing algorithm classes

Link State (Global)

• Routers maintain cost of each
link in the network

• Connectivity/cost changes
flooded to all routers

• Converges quickly (less
inconsistency, looping, etc.)

• Limited network sizes

Distance Vector (Decentralised)

• Routers maintain next hop &
cost of each destination.

• Connectivity/cost changes
iteratively propagate form
neighbour to neighbour

• Requires multiple rounds to
converge

• Scales to large networks

21

Link State Routing
v Each node maintains its local “link state” (LS)

§ i.e., a list of its directly attached links and their costs

(R1,R2, 2)
(R1,R4, 3)
(R1,R5, 2)

Host A

Host B
Host E

Host D

Host C

R1 R2

R3

R4

R5

R7R6
22

2

2
3

Link State Routing
v Each node maintains its local “link state” (LS)
v Each node floods its local link state

§ on receiving a new LS message, a router forwards the message
to all its neighbors other than the one it received the message from

Host A

Host B
Host E

Host D

Host C

R1 R2

R3

R4

R5

R7R6

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)

23

Flooding LSAs

v Routers transmit Link State Advertisement (LSA)
on links
§ A neighbouring router forwards out on all links except

incoming
§ Keep a copy locally; don’t forward previously-seen LSAs

v Challenges
§ Packet loss
§ Out of order arrival

v Solutions
§ Acknowledgements and retransmissions
§ Sequence numbers
§ Time-to-live for each packet

24

Link State Routing
v Each node maintains its local “link state” (LS)
v Each node floods its local link state
v Eventually, each node learns the entire network topology

§ Can use Dijkstra’s to compute the shortest paths between nodes

Host A

Host B
Host E

Host D

Host C

R1 R2

R3

R4

R5

R7R6

A

B
E

D
C

A

B
E

D
C

A

B
E

D
C

A

B
E

D
C

A

B
E

D
C

A

B
E

D
C

A

B
E

D
C

25

A Link-State Routing Algorithm

Dijkstra’s algorithm
v net topology, link costs

known to all nodes
§ accomplished via “link state

broadcast”
§ all nodes have same info

v computes least cost paths
from one node (‘source”)
to all other nodes
§ gives forwarding table for

that node
v iterative: after k

iterations, know least cost
path to k dest.’s

notation:
v c(x,y): link cost from

node x to y; = ∞ if not
direct neighbors

v D(v): current value of
cost of path from source
to dest. v

v p(v): predecessor node
along path from source to
v

v N’: set of nodes whose
least cost path definitively
known

26

Dijsktra’s Algorithm

1 Initialization:
2 N’ = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in N’ such that D(w) is a minimum
10 add w to N’
11 update D(v) for all v adjacent to w and not in N’ :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N’

27

Example: Dijkstra’s Algorithm

Step
0
1
2
3
4
5

Set N’
A

D(B),p(B)
2,A

D(C),p(C)
5,A

D(D),p(D)
1,A

D(E),p(E) D(F),p(F)

A

ED

CB

F
2

2
1

3

1

1

2

5
3

5

∞ ∞

1 Initialization:
2 N’ = {A};
3 for all nodes v
4 if v adjacent to A
5 then D(v) = c(A,v);
6 else D(v) = ;

28

Example: Dijkstra’s Algorithm

Step
0
1
2
3
4
5

Set N’
A

D(B),p(B)
2,A

D(C),p(C)
5,A


8 Loop
9 find w not in N’ s.t. D(w) is a minimum;
10 add w to N’;
11 update D(v) for all v adjacent

to w and not in N’:
12 If D(w) + c(w,v) < D(v) then 13 D(v) = D(w) + c(w,v); p(v) = w; 14 until all nodes in N’; A ED CB F 2 2 1 3 1 1 2 5 3 5 D(D),p(D) 1,A D(E),p(E) D(F),p(F) ∞ ∞ 29 Example: Dijkstra’s Algorithm Step 0 1 2 3 4 5 Set N’ A AD D(B),p(B) 2,A D(C),p(C) 5,A D(D),p(D) 1,A D(E),p(E) D(F),p(F) A ED CB F 2 2 1 3 1 1 2 5 3 5 ∞ ∞ … 8 Loop 9 find w not in N’ s.t. D(w) is a minimum; 10 add w to N’; 11 update D(v) for all v adjacent to w and not in N’: 12 If D(w) + c(w,v) < D(v) then 13 D(v) = D(w) + c(w,v); p(v) = w; 14 until all nodes in N’; 30 Example: Dijkstra’s Algorithm Step 0 1 2 3 4 5 Set N’ A AD D(B),p(B) 2,A D(C),p(C) 5,A 4,D D(D),p(D) 1,A D(E),p(E) 2,D D(F),p(F) A ED CB F 2 2 1 3 1 1 2 5 3 5 ∞ ∞ … 8 Loop 9 find w not in N’ s.t. D(w) is a minimum; 10 add w to N’; 11 update D(v) for all v adjacent to w and not in N’: 12 If D(w) + c(w,v) < D(v) then 13 D(v) = D(w) + c(w,v); p(v) = w; 14 until all nodes in N’; 2, A 31 Example: Dijkstra’s Algorithm Step 0 1 2 3 4 5 Set N’ A AD ADE D(B),p(B) 2,A D(C),p(C) 5,A 4,D 3,E D(D),p(D) 1,A D(E),p(E) 2,D D(F),p(F) 4,E ∞ ∞ A ED CB F 2 2 1 3 1 1 2 5 3 5 … 8 Loop 9 find w not in N’ s.t. D(w) is a minimum; 10 add w to N’; 11 update D(v) for all v adjacent to w and not in N’: 12 If D(w) + c(w,v) < D(v) then 13 D(v) = D(w) + c(w,v); p(v) = w; 14 until all nodes in N’; 2, A 2, A 32 Example: Dijkstra’s Algorithm Step 0 1 2 3 4 5 Set N’ A AD ADE ADEB D(B),p(B) 2,A D(C),p(C) 5,A 4,D 3,E D(D),p(D) 1,A D(E),p(E) 2,D D(F),p(F) 4,E ∞ ∞ A ED CB F 2 2 1 3 1 1 2 5 3 5 … 8 Loop 9 find w not in N’ s.t. D(w) is a minimum; 10 add w to N’; 11 update D(v) for all v adjacent to w and not in N’: 12 If D(w) + c(w,v) < D(v) then 13 D(v) = D(w) + c(w,v); p(v) = w; 14 until all nodes in N’; 2,A 2,A 3,E 4,E 33 Example: Dijkstra’s Algorithm Step 0 1 2 3 4 5 Set N’ A AD ADE ADEB ADEBC D(B),p(B) 2,A D(C),p(C) 5,A 4,D 3,E D(D),p(D) 1,A D(E),p(E) 2,D D(F),p(F) 4,E ∞ ∞ A ED CB F 2 2 1 3 1 1 2 5 3 5 … 8 Loop 9 find w not in N’ s.t. D(w) is a minimum; 10 add w to N’; 11 update D(v) for all v adjacent to w and not in N’: 12 If D(w) + c(w,v) < D(v) then 13 D(v) = D(w) + c(w,v); p(v) = w; 14 until all nodes in N’; 4,E 4,E 3,E 2,A 2,A 34 Example: Dijkstra’s Algorithm Step 0 1 2 3 4 5 Set N’ A AD ADE ADEB ADEBC ADEBCF D(B),p(B) 2,A D(C),p(C) 5,A 4,D 3,E D(D),p(D) 1,A D(E),p(E) 2,D D(F),p(F) 4,E ∞ ∞ A ED CB F 2 2 1 3 1 1 2 5 3 5 … 8 Loop 9 find w not in N’ s.t. D(w) is a minimum; 10 add w to N’; 11 update D(v) for all v adjacent to w and not in N’: 12 If D(w) + c(w,v) < D(v) then 13 D(v) = D(w) + c(w,v); p(v) = w; 14 until all nodes in N’; 4,E 4,E 3,E 2,A 2,A 35 Example: Dijkstra’s Algorithm Step 0 1 2 3 4 5 Set N’ A AD ADE ADEB ADEBC ADEBCF D(B),p(B) 2,A D(C),p(C) 5,A 4,D 3,E D(D),p(D) 1,A D(E),p(E) 2,D D(F),p(F) 4,E ∞ ∞ A ED CB F 2 2 1 3 1 1 2 5 3 5 To determine path A ® C (say), work backward from C via p(v) 36 • Running Dijkstra at node A gives the shortest path from A to all destinations • We then construct the forwarding table The Forwarding Table Destination Link B (A,B) C (A,D) D (A,D) E (A,D) F (A,D) A ED CB F resulting shortest-path tree from A: 37 Issue #1: Scalability v How many messages needed to flood link state messages? § O(N x E), where N is #nodes; E is #edges in graph v Processing complexity for Dijkstra’s algorithm? § O(N2), because we check all nodes w not in N’ at each iteration and we have O(N) iterations v How many entries in the LS topology database? O(E) v How many entries in the forwarding table? O(N) 38 v Inconsistent link-state database § Some routers know about failure before others § The shortest paths are no longer consistent § Can cause transient forwarding loops Issue#2: Transient Disruptions A ED CB F A and D think that this is the path to C E thinks that this is the path to C A ED CB F Loop! 39 Oscillations oscillations possible: v e.g., suppose link cost equals amount of carried traffic: A D C B 1 1+e e0 e 1 1 0 0 initially A D C B given these costs, find new routing…. resulting in new costs 2+e 0 00 1+e 1 A D C B given these costs, find new routing…. resulting in new costs 0 2+e 1+e1 0 0 A D C B given these costs, find new routing…. resulting in new costs 2+e 0 00 1+e 1 40 5.1 introduction 5.2 routing protocols v link state v distance vector v hierarchical routing 5.6 ICMP: The Internet Control Message Protocol Network layer, control plane: outline 41 Distance vector algorithm Bellman-Ford equation let dx(y) := cost of least-cost path from x to y then dx(y) = min {c(x,v) + dv(y) }v cost to neighbor v min taken over all neighbors v of x cost from neighbor v to destination y 42 Bellman-Ford example u yx wv z 2 2 1 3 1 1 2 5 3 5 clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3 du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), 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 B-F equation says: 43 How Distance-Vector (DV) works Each router maintains its shortest distance to every destination via each of its neighbours via B via C to B to C to D From node A Neighbour (next-hop) Destinations distC(A, D): shortest distance from A to D via C A 44 How Distance-Vector (DV) works Each router computes its shortest distance to every destination via any of its neighbors via B via C to B to C to D MIN { distB(A,B), distC(A, B) } A min dist to B to C to D From node A A’s distance vector (DV) 45 How Distance-Vector (DV) works How does A initialize its dist() table and DV? via B via C to B ? ? to C ? ? to D ? ? From node A A min dist to B ? to C ? to D ? A’s DV 46 How Distance-Vector (DV) works A B C c(A ,B ) c(A,C) Link costs How does A initialize its dist() table and DV? 47 How Distance-Vector (DV) works Each router initializes its dist() table based on its immediate neighbors and link costs via B via C to B c(A,B) ∞ to C ∞ c(A,C) to D ∞ ∞ From node A A B C c(A ,B ) c(A,C) mindist to B c(A,B) to C c(A,C) to D ∞ A’s DV 48 How Distance-Vector (DV) works Each router sends its DV to its immediate neighbors via B via C to B c(A,B) ∞ to C ∞ c(A,C) to D ∞ ∞ From node A A B C mindist to B c(A,B) to C c(A,C) to D ∞ A’s DV mindist to B 5 to C 6 to D 2 c(A ,B ) c(A,C) 49 Assume that A’s DV is as follows at some later time How Distance-Vector (DV) works Routers process received DVs A B C A’s DV mi n to B 5 to C 6 to D 2 c(A ,B ) c(A,C) via A via C to A 5 ∞ to C 15 1 to D ∞ ∞ From node B B’s DV mindist to A 5 to C 1 to D ∞ 5 50 How Distance-Vector (DV) works A B C A’s DV mi n to B 5 to C 6 to D 2 c(A,C) via A via C to A 5 ∞ to C 15 1 to D ∞ ∞ From node B B’s DV mindist to A 5 to C 1 to D ∞ new = c(B,A) + mindist(A, C) 5 new = c(B,A) + mindist(A, D) 11 7 Routers process received DVs And repeat… 51 7 Distance Vector Routing v Each router knows the links to its neighbors v Each router has provisional “shortest path” to every other router -- its distance vector (DV) v Routers exchange this DV with their neighbors v Routers look over the set of options offered by their neighbors and select the best one v Iterative process converges to set of shortest paths 52 iterative, asynchronous: each local iteration caused by: v local link cost change v DV update message from neighbor distributed: v each node notifies neighbors only when its DV changes § neighbors then notify their neighbors if necessary wait for (change in local link cost or msg from neighbor) recompute estimates if DV to any dest has changed, notify neighbors each node: Distance vector routing 53 Distance Vector v c(i,j): link cost from node i to j v distz(A,V): shortest dist. from A to V via Z v mindist(A,V): shortest dist. from A to V 0 At node A 1 Initialization: 2 for all destinations V do 3 if V is neighbor of A 4 distV(A, V) = mindist(A,V) = c(A,V); 5 else 6 distV(A, V) = mindist(A,V) = ∞; 7 send mindist(A, *) to all neighbors loop: 8 wait (until A sees a link cost change to neighbor V /* case 1 */ 9 or until A receives mindist(V,*) from neighbor V) /* case 2 */ 10 if (c(A,V) changes by ±d) /* Ü case 1 */ 11 for all destinations Y do 12 distV(A,Y) = distV(A,Y) ± d 13 else /* Ü case 2: */ 14 for all destinations Y do 15 distV(A,Y) = c(A,V) + mindist(V, Y); 16 update mindist(A,*) 15 if (there is a change in mindist(A, *)) 16 send mindist(A, *) to all neighbors 17 forever 54 Distance Vector v c(i,j): link cost from node i to j v distZ(A,V): shortest dist. from A to V via Z v mindist(A,V): shortest dist. from A to V 0 At node A 1 Initialization: 2 for all destinations V do 3 if V is neighbor of A 4 distV(A, V) = mindist(A,V) = c(A,V); 5 else 6 distV(A, V) = mindist(A,V) = ∞; 7 send mindist(A, *) to all neighbors loop: 8 wait (until A sees a link cost change to neighbor V /* case 1 */ 9 or until A receives mindist(V,*) from neighbor V) /* case 2 */ 10 if (c(A,V) changes by ±d) /* Ü case 1 */ 11 for all destinations Y do 12 distV(A,Y) = distV(A,Y) ± d 13 else /* Ü case 2: */ 14 for all destinations Y do 15 distV(A,Y) = c(A,V) + mindist(V, Y); 16 update mindist(A,*) 15 if (there is a change in mindist(A, *)) 16 send mindist(A, *) to all neighbors 17 forever 55 Example: Initialization A C 12 7 B D3 1 via B via C to A - - to B 2 ∞ to C ∞ 7 to D ∞ ∞ from Node A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist to A 0 to B 2 to C 7 to D ∞ min dist 0 2 7 ∞ min dist 2 0 1 3 min dist ∞ 3 1 0 min dist 7 1 0 1 56 Example: C sends update to A via B via C to A - - to B 2 ∞ to C ∞ 7 to D ∞ ∞ from Node A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist 0 2 7 ∞ min dist ∞ 3 1 0 min dist 7 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 3 57 Example: C sends update to A via B via C to A - - to B 2 ∞ to C ∞ 7 to D ∞ ∞ from Node A min dist 0 2 7 ∞ A C 12 7 B D3 1 min dist 7 1 0 1 58 Example: C sends update to A via B via C to A - - to B 2 8 to C ∞ 7 to D ∞ 8 from Node A min dist 0 2 7 ∞ A C 12 7 B D3 1 min dist 7 1 0 1 59 Example: C sends update to A via B via C to A - - to B 2 8 to C ∞ 7 to D ∞ 8 from Node A min dist 0 2 7 8 A C 12 7 B D3 1 60 Example: now B sends update to A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist ∞ 3 1 0 min dist 7 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 3 via B via C to A - - to B 2 8 to C ∞ 7 to D ∞ 8 from Node A min dist 0 2 7 8 61 Example: now B sends update to A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist ∞ 3 1 0 min dist 7 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 3 via B via C to A - - to B 2 8 to C ∞ 7 to D ∞ 8 from Node A min dist 0 2 7 8 62 Example: now B sends update to A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist ∞ 3 1 0 min dist 7 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 3 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 from Node A min dist 0 2 7 8 Make sure you know why this is 5, not 4! 63 Example: now B sends update to A via A via C via D to A 2 ∞ ∞ to B - - - to C ∞ 1 ∞ to D ∞ ∞ 3 from Node B from Node C via A via B via D to A 7 ∞ ∞ to B ∞ 1 ∞ to C - - - to D ∞ ∞ 1 via B via C to A ∞ ∞ to B 3 ∞ to C ∞ 1 to D - - from Node D min dist ∞ 3 1 0 min dist 7 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 3 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 from Node A min dist 0 2 3 5 64 Example: After 1st Full Exchange via A via C via D to A 2 8 ∞ to B - - - to C 9 1 4 to D ∞ 2 3 from Node B from Node C via A via B via D to A 7 3 ∞ to B 9 1 4 to C - - - to D ∞ 4 1 via B via C to A 5 8 to B 3 2 to C 4 1 to D - - from Node D min dist 5 2 1 0 min dist 3 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 2 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 from Node A min dist 0 2 3 5 Make sure you understand why some entries are still ∞ All nodes know the best two-hop paths. Make sure you believe this 65 Example: Now A sends update to B from Node B from Node C from Node D min dist 5 2 1 0 min dist 3 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 2 from Node A min dist 0 2 3 5 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 via A via B via D to A 7 3 ∞ to B 9 1 4 to C - - - to D ∞ 4 1 via B via C to A 5 8 to B 3 2 to C 4 1 to D - - via A via C via D to A 2 8 ∞ to B - - - to C 9 1 4 to D ∞ 2 3 66 Example: Now A sends update to B via A via C via D to A 2 8 ∞ to B - - - to C 5 1 4 to D 7 2 3 from Node B from Node C from Node D min dist 5 2 1 0 min dist 3 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 2 from Node A min dist 0 2 3 5 via B via C to A - - to B 2 8 to C 3 7 to D 5 8 Updated via A via B via D to A 7 3 ∞ to B 9 1 4 to C - - - to D ∞ 4 1 via B via C to A 5 8 to B 3 2 to C 4 1 to D - - 67 Example: End of 2nd Full Exchange via A via C via D to A 2 4 8 to B - - - to C 5 1 4 to D 7 2 3 from Node B from Node C from Node D min dist 4 2 1 0 min dist 3 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 2 from Node A min dist 0 2 3 4 via B via C to A - - to B 2 8 to C 3 7 to D 4 8 via A via B via D to A 7 3 6 to B 9 1 3 to C - - - to D 12 3 1 via B via C to A 5 4 to B 3 2 to C 4 1 to D - - Check Check: All nodes know the best three-hop paths. 68 Example: End of 3nd Full Exchange via A via C via D to A 2 4 7 to B - - - to C 5 1 4 to D 6 2 3 from Node B from Node C from Node D min dist 4 2 1 0 min dist 3 1 0 1 A C 12 7 B D3 1 min dist 2 0 1 2 from Node A min dist 0 2 3 4 via B via C to A - - to B 2 8 to C 3 7 to D 4 8 via A via B via D to A 7 3 5 to B 9 1 3 to C - - - to D 11 3 1 via B via C to A 5 4 to B 3 2 to C 4 1 to D - - No further change in DVs à Convergence! 69 Intuition v Initial state: best one-hop paths v One simultaneous round: best two-hop paths v Two simultaneous rounds: best three-hop paths v … v Kth simultaneous round: best (k+1) hop paths v Must eventually converge § as soon as it reaches longest best path v …..but how does it respond to changes in cost? 70 Problems with Distance Vector Ø A number of problems can occur in a network using distance vector algorithm Ø Most of these problems are caused by slow convergence or routers converging on incorrect information Ø Convergence is the time during which all routers come to an agreement about the best paths through the internetwork • whenever topology changes there is a period of instability in the network as the routers converge Ø Reacts rapidly to good news, but leisurely to bad news 71 DV: Link Cost Changes A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 1 6 C 6 1 A B A 50 5 B 54 1 A C A 1 6 C 3 1 A B A 50 5 B 51 1 A C A 1 6 C 3 1 A B A 50 2 B 51 1 B C B 4 51 C 5 50 Node A B C B 1 51 C 2 50 B C B 1 51 C 2 50 B C B 1 51 C 2 50 A C A 1 3 C 3 1 A B A 50 2 B 51 1 B C B 1 51 C 2 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C C sends its DV to A, B A C 14 50 B1 “good news travels fast” to via Note: none of B’s paths use link (A,C) deduct 3 from distances distB(A,*) and distA(B,*) 72 DV: Link Cost Changes A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 Stable state A-B changed A C 14 50 B60 to via add 56 to distances distB(A,*) and distA(B,*) 73 DV: Link Cost Changes A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 A C A 60 6 C 110 1 A B A 50 5 B 101 1 A C A 60 6 C 110 1 A B A 50 7 B 101 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 B C B 60 51 C 61 50 B C B 60 51 C 61 50 A C A 60 8 C 110 1 A B A 50 7 B 101 1 B C B 60 51 C 61 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C C sends its DV to A, B A C 14 50 B60 “bad news travels slowly” (not yet converged) to via This is the “Counting to Infinity” Problem 74 The “Poisoned Reverse” Rule v Heuristic to avoid count-to-infinity v If B routes via C to get to A: § B tells C its (B’s) distance to A is infinite (so C won’t route to A via B) 75 DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C B C B 4 51 C 5 50 Node A Stable state A C 14 50 B to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ Mindist 4 5 Mindist 4 5∞ Mindist 5 1 Mindist 5 1 ∞ 76 DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 Stable state A-B changed A C 14 50 B60 to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ 77 DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 A C A 60 6 C 110 1 A B A 50 5 B 101 1 A C A 60 6 C 110 1 A B A 50 7 B 101 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 B C B 60 51 C 61 50 B C B 60 51 C 61 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C A C 14 50 B60 to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 78 DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 A C A 60 6 C 110 1 A B A 50 5 B 101 1 A C A 60 6 C 110 1 A B A 50 61 B 101 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 B C B 60 51 C 61 50 B C B 60 51 C 61 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C A C 14 50 B60 to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 79 DV: Poisoned Reverse A C A 4 6 C 9 1 Node B A B A 50 5 B 54 1 Node C Link cost changes here A C A 60 6 C 65 1 A B A 50 5 B 54 1 A C A 60 6 C 110 1 A B A 50 5 B 101 1 A C A 60 6 C 110 1 A B A 50 61 B 101 1 B C B 4 51 C 5 50 Node A B C B 60 51 C 61 50 B C B 60 51 C 61 50 B C B 60 51 C 61 50 A B A 50 61 B 101 1 B C B 60 51 C 61 50 Stable state A-B changed A sends its DV to B, C B sends its DV to A, C C sends its DV to A, B A C 14 50 B60 to via If B routes through C to get to A: B tells C its (B’s) distance to A is infinite ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A C A 60 51 C 110 1 Converges after C receives another update from B ∞ 80 Will Poison-Reverse Completely Solve the Count-to-Infinity Problem? A C 1 B D 1 1 1 1 1 2 2 ∞ ∞ ∞ 100 100 100 3 ∞ 4 ∞ 4 5 6 Numbers in blue denote the best cost to destination D advertised along the link 81 Quiz: Link-state routing v In link state routing, each node sends information of its direct links (i.e., link state) to ________? A. Immediate neighbours B. All nodes in the network C. Any one neighbor D. No one 82 www.zeetings.com/salil Answer: B Answer: B Quiz: Distance-vector routing v In distance vector routing, each node shares its distance table with ________? A. All Immediate neighbours B. All nodes in the network C. Any one neighbor D. No one 83 www.zeetings.com/salil Answer: A Answer: A Quiz: Distance-vector routing v Which of the following is true of distance vector routing? A. Convergence delay depends on the topology (nodes and links) and link weights B. Convergence delay depends on the number of nodes and links C. Each node knows the entire topology D. A and C E. B and C 84 www.zeetings.com/salil Answer: A Answer: A Comparison of LS and DV algorithms message complexity v LS: with n nodes, E links, O(nE) msgs sent v DV: exchange between neighbors only § convergence time varies speed of convergence v LS: O(n2) algorithm requires O(nE) msgs § may have oscillations v DV: convergence time varies § may be routing loops § count-to-infinity problem robustness: what happens if router malfunctions? LS: § node can advertise incorrect link cost § each node computes only its own table DV: § DV node can advertise incorrect path cost § each node’s table used by others • error propagate thru network 85 Real Protocols Link State Open Shortest Path First (OSPF) Intermediate system to intermediate system (IS- IS) Distance Vector Routing Information Protocol (RIP) Interior Gateway Routing Protocol (IGRP-Cisco) Border Gateway Protocol (BGP) 86 5.1 introduction 5.2 routing protocols v link state v distance vector v hierarchical routing 5.6 ICMP: The Internet Control Message Protocol Network layer, control plane: outline Self study (not on exam) 87 ICMP: Internet Control Message Protocol v Used by hosts & routers to communicate network level infromation § Error reporting: unreachable host, network, port § Echo request/reply (used by ping) v Works above IP layer § ICMP messages carried in IP datagrams v ICMP message: type, code plus IP header and first 8 bytes of IP datagram payload causing error IP Header IP HeaderICMP Header 8 Bytes Contains source address, checksum etc. Contains TCP/UDP port numbers 88 ICMP: Internet Control Message Protocol v Type Code Description 0 0 echo reply(ping) 3 0 dest. network unreachable 3 1 dest host unreachable 3 3 dest port unreachable 3 4 frag needed; DF set 8 0 echo request(ping) 11 0 TTL expired 11 1 frag reassembly time exceeded 12 0 bad IP header 89 Traceroute and ICMP Ø Source sends series of UDP segments to dest • first set has TTL =1 • second set has TTL=2, etc. • unlikely port number Ø When nth set of datagrams arrives to nth router: • router discards datagrams • and sends source ICMP messages (type 11, code 0) • ICMP messages includes IP address of router Ø when ICMP messages arrives, source records RTTs stopping criteria: Ø UDP segment eventually arrives at destination host Ø destination returns ICMP “port unreachable” message (type 3, code 3) Ø source stops 3 probes 3 probes 3 probes 90 Summary v Network Layer: Data Plane § Overview § IP v Network Layer: Control Plane § Routing Protocols • Link—state • Distance Vector § ICMP 91 COMP 3331/9331: Computer Networks and Applications Week 9 Data link Layer Reading Guide: Chapter 6, Sections 6.1 – 6.4, 6.7 Link layer and LANs our goals: v understand principles behind link layer services: § error detection, correction § sharing a broadcast channel: multiple access § link layer addressing § local area networks: Ethernet 93 Link layer, LANs: outline 6.1 introduction, services 6.2 error detection, correction 6.3 multiple access protocols 6.4 Switched LANs § addressing, ARP § Ethernet § Switches § VLANS (EXCLUDED) 6.5 link virtualization: MPLS (EXCLUDED) 6.6 data center networking (EXCLUDED) 6.7 a day in the life of a web request 94 From Macro- to Micro- 95 From Macro- to Micro- • Previously, we looked at Internet scale… Customer AS Destination AS Customer’s ISP Other Networks Other Networks Link layer focus: Within a Subnet 96 Within a Subnet Router Link layer: introduction terminology: v hosts and routers: nodes v communication channels that connect adjacent nodes along communication path: links § wired links § wireless links § LANs v layer-2 packet: frame, encapsulates datagram data-link layer has responsibility of transferring datagram from one node to physically adjacent node over a link global ISP 97 Link layer: context v datagram transferred by different link protocols over different links: § e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last link v each link protocol provides different services § e.g., may or may not provide rdt over link transportation analogy: v trip from Princeton to Lausanne § limo: Princeton to JFK § plane: JFK to Geneva § train: Geneva to Lausanne v tourist = datagram v transport segment = communication link v transportation mode = link layer protocol v travel agent = routing algorithm 98 Link layer services v framing, link access: § encapsulate datagram into frame, adding header, trailer § channel access if shared medium § “MAC” addresses used in frame headers to identify source, dest • different from IP address! v reliable delivery between adjacent nodes § we learned how to do this already (chapter 3)! § seldom used on low bit-error link (fiber, some twisted pair) § wireless links: high error rates • Q: why both link-level and end-end reliability? 99 v flow control: § pacing between adjacent sending and receiving nodes v error detection: § errors caused by signal attenuation, noise. § receiver detects presence of errors: • signals sender for retransmission or drops frame v error correction: § receiver identifies and corrects bit error(s) without resorting to retransmission v half-duplex and full-duplex § with half duplex, nodes at both ends of link can transmit, but not at same time Link layer services (more) 100 Where is the link layer implemented? v in each and every host v link layer implemented in “adaptor” (aka network interface card NIC) or on a chip § Ethernet card, 802.11 card; Ethernet chipset § implements link, physical layer v attaches into host’s system buses v combination of hardware, software, firmware controller physical transmission cpu memory host bus (e.g., PCI) network adapter card application transport network link link physical 101 Adaptors communicating v sending side: § encapsulates datagram in frame § adds error checking bits, rdt, flow control, etc. v receiving side § looks for errors, rdt, flow control, etc § extracts datagram, passes to upper layer at receiving side controller controller sending host receiving host datagram datagram datagram frame 102 103 What is framing? Ø Physical layer talks in terms of bits. Ø How do we identify frames within the sequence of bits? Ø Need to do Framing • Delimit the start and end of the frame Ø Ethernet Framing • Timing/Physical layer 104 Framing in Ethernet Ø Start of frame is recognized by • Preamble : Seven bytes with pattern 10101010 • Start of Frame Delimiter (SFD) : 10101011 Ø Inter Frame Gap is 12 Bytes (96 bits) of idle state • 0.96 microsec for 100 Mbit/s Ethernet • 0.096 microsec for Gigabit/s Ethernet Preamble 7 Bytes SFD 1 Byte Dest MAC 6 Bytes Source MAC 6 Bytes Type/Le ngth 2 Bytes Payload 46-1500 Bytes FCS/C RC 4 Bytes Inter Frame Gap