Bài giảng Mạng máy tính - Chapter 4: Network Layer (Part I) - Hồ Phương Đắc
Chapter 4: Network Layer
Chapter goals:
understand principles
behind network layer
services:
Overview:
network layer services
routing principle: path
selection
routing (path selection)
dealing with scale
how a router works
hierarchical routing
IP
Internet routing protocols
advanced topics: IPv6,
reliable transfer
multicast
intra-domain
inter-domain
instantiation and
implementation in the
Internet
what’s inside a router?
IPv6
multicast routing
4: Network Layer
4a-1
Network layer functions
transport packet from
application
transport
network
data link
physical
sending to receiving hosts
network
data link
physical
network layer protocols in
network
data link
physical
network
data link
physical
every host, router
network
data link
physical
three important functions:
network
data link
physical
path determination: route
taken by packets from source
to dest. Routing algorithms
network
data link
physical
network
data link
physical
network
data link
physical
switching: move packets from
router’s input to appropriate
router output
application
transport
network
data link
physical
call setup: some network
architectures require router
call setup along path before
data flows
4: Network Layer
4a-2
Network service model
Q: What service model
for “channel”
The most important
abstraction provided
by network layer:
transporting packets
from sender to
receiver?
guaranteed bandwidth?
virtual circuit
preservation of inter-packet
or
?
timing (no jitter)?
datagram?
?
loss-free delivery?
in-order delivery?
?
congestion feedback to
sender?
4: Network Layer
4a-3
Virtual circuits
“source-to-dest path behaves much like telephone
circuit”
performance-wise
network actions along source-to-dest path
call setup, teardown for each call before data can flow
each packet carries VC identifier (not destination host OD)
every router on source-dest path s maintain “state” for
each passing connection
transport-layer connection only involved two end systems
link, router resources (bandwidth, buffers) may be
allocated to VC
to get circuit-like perf.
4: Network Layer
4a-4
Virtual circuits: signaling protocols
used to setup, maintain teardown VC
used in ATM, frame-relay, X.25
not used in today’s Internet
application
application
6. Receive data
3. Accept call
2. incoming call
5. Data flow begins
4. Call connected
1. Initiate call
transport
network
data link
physical
transport
network
data link
physical
4: Network Layer
4a-5
Datagram networks: the Internet model
no call setup at network layer
routers: no state about end-to-end connections
no network-level concept of “connection”
packets typically routed using destination host ID
packets between same source-dest pair may take
different paths
application
application
transport
network
data link
physical
transport
network
data link
physical
1. Send data
2. Receive data
4: Network Layer
4a-6
Network layer service models:
Guarantees ?
Network Service
Congestion
feedback
Bandwidth Loss
Architecture Model
Internet best effort
ATM CBR
Order Timing
none
no
no no
no (inferred
via loss)
no
congestion
no
congestion
yes
constant yes
rate
guaranteed yes
rate
yes yes
yes yes
yes no
yes no
ATM VBR
guaranteed no
minimum
ATM ABR
none
no
ATM UBR
no
Internet model being extented: Intserv, Diffserv
Chapter 6
4: Network Layer
4a-7
Datagram or VC network: why?
Internet
ATM
data exchange among
evolved from telephony
human conversation:
computers
“elastic” service, no strict
strict timing, reliability
timing req.
requirements
“smart” end systems
need for guaranteed
(computers)
service
can adapt, perform
“dumb” end systems
telephones
control, error recovery
simple inside network,
complexity inside
complexity at “edge”
network
many link types
different characteristics
uniform service difficult
4: Network Layer
4a-8
Routing
Routing protocol
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
5
3
B
C
5
2
A
F
2
1
3
Graph abstraction for
routing algorithms:
1
2
D
E
1
graph nodes are
routers
“good” path:
typically means minimum
graph edges are
cost path
other def’s possible
physical links
link cost: delay, $ cost,
or congestion level
4: Network Layer
4a-9
Routing Algorithm classification
Global or decentralized
information?
Global:
Static or dynamic?
Static:
routes change slowly over
time
Dynamic:
all routers have complete
topology, link cost info
“link state” algorithms
Decentralized:
routes change more quickly
periodic update
router knows physically-
connected neighbors, link
costs to neighbors
in response to link cost
changes
iterative process of
computation, exchange of
info with neighbors
“distance vector” algorithms
4: Network Layer
4a-10
A Link-State Routing Algorithm
Dijkstra’s algorithm
Notation:
c(i,j): link cost from node i
to j. cost infinite if not
direct neighbors
net topology, link costs
known to all nodes
accomplished via “link
state broadcast”
D(v): current value of cost
of path from source to
dest. V
all nodes have same info
computes least cost paths
from one node (‘source”) to
all other nodes
p(v): predecessor node
along path from source to
v, that is next v
gives routing table for
that node
N: set of nodes whose
least cost path definitively
known
iterative: after k
iterations, know least cost
path to k dest.’s
4: Network Layer
4a-11
Dijsktra’s Algorithm
1 Initialization:
2 N = {A}
3 for all nodes v
4 if v adjacent to A
5
6
7
then D(v) = c(A,v)
else D(v) = infty
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
4: Network Layer
4a-12
Dijkstra’s algorithm: example
D(B),p(B)
2,A
D(D),p(D)
1,A
D(C),p(C)
5,A
D(E),p(E)
infinity
2,D
Step
start N
A
D(F),p(F)
infinity
infinity
4,E
0
1
2
3
4
5
2,A
4,D
AD
2,A
3,E
3,E
ADE
ADEB
ADEBC
ADEBCF
4,E
4,E
5
3
B
C
5
2
A
F
2
1
3
1
2
D
E
1
4: Network Layer
4a-13
Dijkstra’s algorithm, discussion
Algorithm complexity: n nodes
each iteration: need to check all nodes, w, not in N
n*(n+1)/2 comparisons: O(n**2)
more efficient implementations possible: O(nlogn)
Oscillations possible:
e.g., link cost = amount of carried traffic
A
A
A
A
1
1+e
2+e
0
2+e
0
2+e
0
D
B
D
D
B
B
D
B
0
0
1
1+e
0
0
C
1
1+e
e
0
0
0
e
1
C
1+e
0
C
C
1
1
e
… recompute
… recompute
… recompute
initially
routing
4: Network Layer
4a-14
Distance Vector Routing Algorithm
iterative:
Distance Table data structure
continues until no
each node has its own
nodes exchange info.
row for each possible destination
self-terminating: no
column for each directly-
“signal” to stop
attached neighbor to node
asynchronous:
nodes need not
exchange info/iterate
in lock step!
example: in node X, for dest. Y
via neighbor Z:
distance from X to
distributed:
each node
=
=
X
Y, via Z as next hop
D (Y,Z)
communicates only with
directly-attached
neighbors
Z
c(X,Z) + min {D (Y,w)}
w
4: Network Layer
4a-15
Distance Table: example
cost to destination via
1
B
C
DE()
A
1
7
6
4
B
14
8
D
5
5
4
2
7
A
2
8
A
B
C
D
1
E
D
2
E
D
c(E,D) + min {D (C,w)}
2+2 = 4
D (C,D)
=
=
w
9
E
D
c(E,D) + min {D (A,w)}
D (A,D)
=
=
w
2+3 = 5
loop!
11
E
B
c(E,B) + min {D (A,w)}
8+6 = 14
D (A,B)
=
=
w
loop!
4: Network Layer
4a-16
Distance table gives routing table
cost to destination via
Outgoing link
DE()
A
1
7
6
4
B
14
8
D
5
5
4
2
to use, cost
A
B
C
D
A A,1
B D,5
C D,4
9
11
D
D,4
Routing table
Distance table
4: Network Layer
4a-17
Distance Vector Routing: overview
Iterative, asynchronous:
each local iteration caused
by:
Each node:
wait for (change in local link
local link cost change
cost of msg from neighbor)
message from neighbor: its
least cost path change
from neighbor
recompute distance table
Distributed:
each node notifies
neighbors only when its
least cost path to any
destination changes
if least cost path to any dest
has changed, notify
neighbors
neighbors then notify
their neighbors if
necessary
4: Network Layer
4a-18
Distance Vector Algorithm:
At all nodes, X:
1 Initialization:
2 for all adjacent nodes v:
X
3 D (*,v) = infty
/* the * operator means "for all rows" */
X
4 D (v,v) = c(X,v)
5 for all destinations, y
6 send min D (y,w) to each neighbor /* w over all X's neighbors */
X
w
4: Network Layer
4a-19
Distance Vector Algorithm (cont.):
8 loop
9 wait (until I see a link cost change to neighbor V
10
11
or until I receive update from neighbor V)
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 */
X
X
15 for all destinations y: D (y,V) = D (y,V) + d
16
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) */
w
20 /* call this received new value is "newval" */
X
21 for the single destination y: D (Y,V) = c(X,V) + newval
22
X
23 if we have a new min D (Y,w)for any destination Y
w
X
24 send new value of min D (Y,w) to all neighbors
w
25
4: Network Layer
26 forever
4a-20
Tải về để xem bản đầy đủ
45 trang
18600
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng máy tính - Chapter 4: Network Layer (Part I) - Hồ Phương Đắc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mang_may_tinh_chapter_4_network_layer_part_i_ho_ph.ppt
