Network Layer
Network Layer
understand principles behind network layer services:
Copyright By PowCoder代写 加微信 powcoder
routing (path selection)
how a router works
instantiation and implementation in the Internet
network layer services
routing principle: path selection
hierarchical routing
what’s inside a router?
Postal-service mail carrier
Network layer functions
transport packet from sending to receiving host
network layer protocols in every host, router
Important functions:
Routing/Path determination: network-wide process that calculates the route that the packet will take through the network (from source to dest); Routing algorithms
Forwarding/switching:
router-local action of moving a packet arriving at an input port to the appropriate output port
application
application
Interplay between routing and forwarding
DATAGRAM ROUTING (The internet model)
routers: no state about end-to-end connections
no network-level concept of ‘connection’
packets are typically routed using destination host ID
packets between the same source-destination pair may take different paths
1. Send data
2. Receive data
application
application
Each router has a forwarding table that maps destination addresses to link interfaces
Graph (undirected) abstraction for routing algorithms:
nodes represent routers
Lines/graph edges are physical links
link cost: delay, cost of sending a packet across link, or congestion level
Goal: determine good path
(sequence of routers) through
network from source to destination.
Routing protocol
‘good’ path:
typically means minimum cost path
other definitions possible
Physical distance, link speed, monetary cost, etc.
Classification of Routing Algorithms
Global or decentralized information?
Global Routing:
Least-cost path is computed using complete, global knowledge of the network:
topology, link cost info
Link State (LS) algorithm
Decentralized Routing:
Least-cost path is calculated in an iterative, distributed manner
router only knows physically-connected neighbours, link costs to neighbours
Involves an iterative process of calculation & exchange of distance vector information with neighbours
Distance Vector (DV) algorithm
Static or dynamic?
routes change slowly over time; small networks may use manually configured routing tables
routes change more quickly
periodic update
in response to topology or link cost changes
routing tables are constructed automatically
Distance Vector Routing Algorithm
Decentralised, dynamic environments
Distance Vector Routing Algorithm
iterative:
continues until no nodes exchange information anymore
self-terminating: no signal to stop
asynchronous:
nodes need not exchange information/iterate in lock step!
distributed:
each node communicates only with directly-attached neighbours
Distance Vector Algorithm
Bellman-Ford Equation (dynamic programming)
dx(y) := cost of least-cost path from x to y
dx(y) = min {c(x,v) + dv(y) }
where min is taken over all neighbors v of x
Bellman-Ford example
By inspection from the graph,
we can see that:
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,
5 + 3} = 4
The node that arrives with the minimum cost = the next
hop neighbour along the shortest path ➜ forwarding table
B-F equation says:
The least cost path from node u to z is one of the
paths that passes through node u’s neighbors
Distance Vector Routing Algorithm
Distance Table data structure
row for each possible destination
column for each directly-attached neighbor
cost to destination via
destination
Directly attached neighbors of E
Each time a node is looking for the shortest path to a destination, it simply consults its distance table.
Here’s an example of a Distance Table for node E.
Distance Vector Routing Algorithm
Distance Table data structure
row for each possible destination
column for each directly-attached neighbor
Calculation of values
example: Node X, routing for destination Y via directly attached neighbor Z:
distance from X to
Y, via Z as next hop
c(X,Z) + min {D (Y,w)}
cost to destination via
destination
Directly attached neighbors of E
Currently known minimum-cost path from Z to Y
Node Z will have to inform node X regarding its shortest path to Y.
DISTANCE TABLE: Example
cost to destination via
destination
c(E,D) + min {D (C,w)}
c(E,D) + min {D (A,w)}
c(E,B) + min {D (A,w)}
ENTRIES IN THE DATA TABLE for NODE E (after DV converges)
Node E to C via D
Node E to A via D
Node E to A via B
Direct link
Any possible path from D to C
Distance table gives routing table
cost to destination via
destination
Outgoing link
to use, cost
destination
Distance table
Routing table
Distance Vector Routing: (more details)
Iterative, asynchronous:
Each local iteration (Distance Table update) caused by:
Change of cost of an attached link
Receipt of message update from neighbour
Distributed:
each node notifies neighbours only when its least-cost path to any destination changes
wait for (change in local link cost or msg from neighbor)
recompute distance table
if a least-cost path to any destination has changed, notify neighbors
Each node:
BELLMAN-FORD ALGORITHM – Internet RIP, BGP, IDRP, PX, ARPANet
Let’s look at the sequence of steps that implement the Distance Vector Routing Algorithm
Distance Vector Algorithm:
1 Initialization:
2 for all adjacent nodes v:
3 D (*,v) =infinite ( the * operator means “for all rows” )
4 D (v,v) = c(X,v)
5 for all destinations, y
send min D (y,w) to each neighbor (w over all X’s neighbors )
At each node, X:
Initially, set all link costs to all destination nodes to infinite (∞)
Send a table of vectors to each neighbor of X
Update distance table of X
Distance Vector Algorithm (cont.):
9 wait (until I see a link cost change to neighbor V
10 or until I receive an update from neighbor V)
11 //link cost change
12 if (c(X,V) changes by d)
13 /* change cost to all dest’s via neighbor v by d */
14 /* note: d could be positive or negative */
15 for all destinations y: D (y,V) = D (y,V) + d
16 //receipt of distance vector from neighbor V
17 else if (update received from V wrt destination Y)
18 /* shortest path from V to some Y has changed */
19 /* V has sent a new value for its min DV(Y,w) */
20 /* call this received new value as newval */
21 for the single destination y: D (Y,V) = c(X,V) + newval
22 //new least-cost to any destination Y found
23 if we have a new min D (Y,w) for any destination Y
24 send new value of min D (Y,w) to all neighbors
26 forever
Change in link cost;
therefore, update
Entire column in
distance table
Received one update from
neighbor v; therefore,
Calculate new
link cost in distance
Distance-Vector Algorithm
Distance Vector Algorithm: example
c(X,Y) + min {D (Z,w)}
Let’s examine one sample computation here
From x to z, via y:
Routing update from neighbour y, destination z
Routing update from neighbour z, destination y
Distance Vector Algorithm: example
c(X,Z) + min {D (Y,w)}
c(X,Y) + min {D (Z,w)}
Let’s examine one sample computation here
From x to y, via z:
From x to z, via y:
Routing update from neighbour y, destination z
Routing update from neighbour z, destination y
Distance Vector Algorithm: example
Examine which table finds a new minimum cost value after an update
Routers will keep on sending updates to each other until no new shortest path is discovered anymore.
Distance Vector: link cost changes
Link cost changes:
node detects local link cost change
updates distance table (line 15)
if cost change in least cost path, notify neighbours (lines 23,24)
terminates
good news travels fast
Note: The illustrations limit the exchange of packets between nodes Y and Z only.
Distance Vector: link cost changes
Routing loop bet. Y & Z – will persist after 44 iterations
bad news travels slow – ‘count to infinity’ problem!
Distance Vector: link cost changes
Link-cost change: the new link-cost to X changes from 4 to 60.
ROUTING LOOP! Node Y doesn’t know that Z would pass through Y itself to get to X (at this point in time, Z is still using the old least-cost path (from Node Y to X is equal to 4)
Routing Table for Node Y
Routing Table for Node Z
Sometime after t0: Node Y calculates the new least-cost path, and finds that passing through Z is more cost effective to reach Node X
At time t1: Node Y broadcasts the new least-cost path to Z (neighbor)
Sometime after t1: Node Z receives the new least-cost to Node X from Y, then computes a new least-cost to X
Node Z computes the new least-cost to X, then updates its Routing Table
t2: Node Z informs y of its new least-cost to X, since it has changed (increased)
And so on, and so forth (44 iterations)…
bad news travels slow – ‘count to infinity’ problem!
Distance Vector: poisoned reverse
If Z routes through Y to get to X :
Z tells Y its (Z’s) distance to X is infinite (so Y won’t route to X via Z)
will this completely solve count to infinity problem?
terminates
It does not. Loops with nodes >= 3 will not be detected!
Poisoned Reverse Algorithm
How to apply the Poisoned Reverse Algorithm?
Eventually, the value 8 will turn to ∞ because it is not a direct link, and it is not the least-cost path for destination C
If the link is NOT a direct link and if the link-cost is NOT equal to the minimum cost for a given destination node, then set the link-cost = ∞ (infinity)
via neighbour
destination
Inspect each row,
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com