CS计算机代考程序代写 algorithm PowerPoint Presentation

PowerPoint Presentation

Network Layer
All material copyright 1996-2012
J.F Kurose and K.W. Ross, All Rights Reserved
George Parisis
School of Engineering and Informatics
University of Sussex

Network Layer
4-*
Network Layer
objectives:
understand principles behind network layer services:

network layer service models
forwarding versus routing
how a router works
routing (path selection)
broadcast
instantiation, implementation in the Internet

Network Layer

Network Layer
4-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol

datagram format
IPv4 addressing
ICMP, IPv6
routing algorithms

link state, distance vector
hierarchical routing
routing in the Internet

RIP, OSPF
BGP
broadcast routing

Outline

Network Layer

Network Layer
4-*
Network layer
transport segment from sending to receiving host
on sending side encapsulates segments into datagrams
on receiving side, delivers segments to transport layer
network layer protocols in every host, router
router examines header fields in all IP datagrams passing through it

application
transport
network
data link
physical

application
transport
network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

network
data link
physical

Network Layer

Network Layer
4-*
Two key network-layer functions
forwarding: move packets from router’s input to appropriate router output
routing: determine route taken by packets from source to destination

routing algorithms

Network Layer

Network Layer
4-*
Interplay between routing and forwarding

1
2
3

0111
value in arriving
packet’s header

routing algorithm

local forwarding table
header value
output link

0100
0101
0111
1001
3
2
2
1

routing algorithm determines
end-end-path through network

forwarding table determines
local forwarding at this router

Network Layer

Network Layer
4-*
Network service model
Q: What service model for “channel” transporting datagrams from sender to receiver?
example services for individual datagrams:
guaranteed delivery
guaranteed delivery with less than 40 msec delay

example services for a flow of datagrams:
in-order datagram delivery
guaranteed minimum bandwidth to flow
restrictions on changes in inter-packet spacing
security

Network Layer

Network Layer
4-*
Network layer service models:
Network
Architecture

Internet

ATM

ATM

ATM

ATM
Service
Model

best effort

CBR

VBR

ABR

UBR
Bandwidth

none

constant
rate
guaranteed
rate
guaranteed
minimum
none
Loss

no

yes

yes

no

no
Order

no

yes

yes

yes

yes
Timing

no

yes

yes

no

no
Congestion
feedback

no (inferred
via loss)
no
congestion
no
congestion
yes

no
Guarantees ?

Network Layer

Network Layer
4-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol

datagram format
IPv4 addressing
ICMP, IPv6
routing algorithms

link state, distance vector
hierarchical routing
routing in the Internet

RIP, OSPF
BGP
broadcast routing

Outline

Network Layer

Network Layer
4-*
Connection, connection-less service
datagram network provides network-layer connectionless service
virtual-circuit network provides network-layer connection service
analogous to TCP/UDP connection-oriented / connectionless transport-layer services, but:

service: host-to-host
no choice: network provides one or the other
implementation: in network core

Network Layer

Network Layer
4-*
Virtual circuits
call setup, teardown for each call before data can flow
each packet carries VC identifier (not destination host address)
every router on source-dest path maintains “state” for each passing connection
link, router resources (bandwidth, buffers) may be allocated to VC (dedicated resources = predictable service)

“source-to-destination path behaves much like telephone circuit”
performance-wise
network actions along source-to-destination path

Network Layer

Network Layer
4-*
VC implementation
a VC consists of:
path from source to destination
VC numbers, one number for each link along path
entries in forwarding tables in routers along path
packet belonging to VC carries VC number

VC number can be changed on each link

new VC number comes from forwarding table

Network Layer

Network Layer
4-*
Virtual circuits: signaling protocols
used to setup, maintain teardown VC
used in ATM, frame-relay, X.25
not used in today’s Internet

1. initiate call
2. incoming call
3. accept call
4. call connected
5. data flow begins
6. receive data

application
transport
network
data link
physical

application
transport
network
data link
physical

Network Layer

Network Layer
4-*
VC forwarding table
12
22
32
1
2
3
VC number
interface
number
Incoming interface Incoming VC # Outgoing interface Outgoing VC #
1 12 3 22
2 63 1 18
3 7 2 17
1 97 3 87
… … … …

forwarding table in
northwest router:
VC routers maintain connection state information!

Network Layer

Network Layer
4-*
Datagram networks
no VC setup at network layer
routers: no state about end-to-end connections

no network-level concept of “connection”
packets forwarded using destination host address

1. send datagrams
2. receive datagrams

application
transport
network
data link
physical

application
transport
network
data link
physical

Network Layer

Network Layer
4-*
Datagram forwarding table

IP destination address in
arriving packet’s header
routing algorithm

local forwarding table
dest address
output link
address-range 1
address-range 2
address-range 3
address-range 4
3
2
2
1

1
2
3

4 billion IP addresses, so rather than list individual destination address
list range of addresses
(aggregate table entries)

Network Layer

Network Layer
4-*
Destination Address Range

11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111

11001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111

11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111

otherwise
Link Interface

0

1

2

3

Datagram forwarding table

Network Layer

Network Layer
4-*

Longest prefix matching
Destination Address Range
11001000 00010111 00010*** *********
11001000 00010111 00011000 *********
11001000 00010111 00011*** *********
otherwise
dst addr: 11001000 00010111 00011000 10101010
examples:
dst addr: 11001000 00010111 00010110 10100001
which interface?
which interface?
when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.
longest prefix matching

Link interface
0
1
2
3

Network Layer

Network Layer
4-*
virtual circuit and datagram networks
network layer service models

Summary

Network Layer