Transcript Network layer

Wide Area Networks and Internet
CT1403
Lecture-8: Internet Network Layer (Part-3)
By : Najla Al-Nabhan
1
Lecture goals:

understand principles behind:
 Address Resolution Protocol (ARP) in the Internet
 Network layer service models (Connection &
Connectionless)
 forwarding versus routing
 how a router works
 routing (path selection)
 Internet broadcast, multicast
Network layer: Recall!





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
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
application
transport
network
data link
physical
The Internet network layer
host, router network layer functions:
transport layer: TCP,
UDP
IP protocol
routing protocols
network
layer
• path selection
• RIP, OSPF, BGP
forwarding
table
• addressing conventions
• datagram format
• packet handling
conventions
ICMP protocol
• error reporting
• router “signaling”
link
layer
physical
layer
Network Layer4-33
IP Routing Process




When packet arrives, look up dest addr
local network?
 send immediately to destination
distant network?
 forward to next router on the interface given in
routing table
not in the routing table?
 forward to default gateway
Address Resolution Protocol
(ARP)
Address Resolution Protocol (ARP)




Because there are both network -layer addresses (IP address) and linklayer addresses (that is MAC address), there is a need to translate
between them
For Internet, this translation is the job of the Address Resolution
Protocol (ARB)
MAC address allocation administered by IEEE. Manufacturer buys portion
of MAC address space (to ensure uniqueness)
Analogy:
 MAC address: like Social Security Number
 IP address: like postal address
ARP: address resolution protocol
Question: how to determine
interface’s MAC address, knowing its IP address?
ARP table: each IP node (host, router) on LAN has
table
137.196.7.78
1A-2F-BB-76-09-AD
< IP address; MAC address; TTL>
137.196.7.23
137.196.7.14
LAN
71-65-F7-2B-08-53
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
137.196.7.88
 IP/MAC address
mappings for some LAN
nodes:
 TTL (Time To Live):
time after which address
mapping will be
forgotten (typically 20
min)
ARP protocol in the Internet: same LAN
1.
A wants to send
datagram to B
B’s MAC address not in A’s
ARP table.
2.
A broadcasts ARP query
packet, containing B's IP
address
dest MAC address = FF-FF-FFFF-FF-FF
all nodes on LAN receive ARP
query
3.
B receives ARP packet,
replies to A with its (B's)
MAC address
frame sent to A’s MAC address
(unicast)
4.
A caches (saves) IP-toMAC address pair in its ARP
table until information becomes
old (times out)
soft state: information
that times out (goes
away) unless refreshed
5. ARP is “plug-and-play”:
nodes create their ARP
tables without intervention
from net administrator
Addressing: routing to another LAN
walkthrough: send datagram from A to B via R
focus on addressing – at IP (datagram) and MAC layer
(frame)
assume A knows B’s IP address
assume A knows IP address of first hop router, R (how?)
assume A knows R’s MAC address (how?)
B
A
R
111.111.111.11
1
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.11
2
CC-49-DE-D0-AB-7D
111.111.111.11
0
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN

A creates IP datagram with IP source A, destination B

A creates link-layer frame with R's MAC address as dest, frame contains A-to-B IP datagram
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
B
A
R
111.111.111.11
1
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.11
2
CC-49-DE-D0-AB-7D
111.111.111.11
0
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN

R forwards datagram with IP source A, destination B

R creates link-layer frame with B's MAC address as dest, frame contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
IP
Eth
Phy
B
A
R
111.111.111.11
1
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.11
2
CC-49-DE-D0-AB-7D
111.111.111.11
0
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN

R forwards datagram with IP source A, destination B

R creates link-layer frame with B's MAC address as dest, frame contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP
Eth
Phy
IP
Eth
Phy
IP src: 111.111.111.111
IP dest: 222.222.222.222
B
A
R
111.111.111.11
1
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.11
2
CC-49-DE-D0-AB-7D
111.111.111.11
0
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN

R forwards datagram with IP source A, destination B

R creates link-layer frame with B's MAC address as dest, frame contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
B
A
R
111.111.111.11
1
74-29-9C-E8-FF-55
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.11
2
CC-49-DE-D0-AB-7D
111.111.111.11
0
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Two key network-layer functions

network layer has
three major functions:
1. forwarding: move
packets from
router’s input to
appropriate router
output
analogy:
routing: process of planning
trip from source to dest
forwarding: process of
2. routing: determine
getting through single
route taken by
packets from source interchange
to dest.
 routing algorithms
Interplay between routing and
forwarding
routing algorithm
routing algorithm determines
end-end-path through network
local forwarding table
header value output link
forwarding table determines
local forwarding at this router
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
0111
1
3 2
Connection setup
Connection setup is the 3rd important function in
some network architectures; (such as ATM, frame
relay, X.25)
Occurs before data transfer:


3-way handshake in TCP Connection
 All routers in the Virtual Circuit (VC) need to handshake with
each other in order to establish virtual connection
 routers get involved


network vs transport layer connection service:
 network: between two hosts (may also involve intervening
routers in case of VCs)
 transport: between two processes
Network service model
Q: What service model for “channel” transporting
datagrams from sender to receiver?
example services for an
individual datagram:


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
Network layer service models:
Network Service
Architecture Model
Internet best effort
ATM CBR
ATM ABR
Guarantees ?
Bandwidth
No loss
Order Timing
none
no
no
no
constant
rate
guaranteed
minimum
yes
yes
yes
no
yes
no
Congestion
feedback
no (inferred
via loss)
no
congestion
yes (indicated)
virtual circuit and datagram
networks
Connection, connection-less service


Transport layer provides connection & connection-less
services between two processes
Network layer provides connection OR connection-less
services between two hosts
 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 (not both)
 implementation: in network core
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
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)
VC implementation
a VC consists of:
1.
2.
3.
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
(rather than dest address)
VC number can be changed on each link.



new VC number comes from forwarding table
VC forwarding table
22
12
1
VC number
interface
number
forwarding table in
northwest router:
Incoming interface
Incoming VC #
2
Outgoing interface
32
3
Outgoing VC
#
1
2
3
1
…
12
63
7
97
…
3
1
2
3
22
18
17
87
…
…
VC routers maintain connection state information!
Virtual circuits: signaling protocols



used to setup, maintain and terminate
VC
used in ATM, frame-relay, X.25
not used in today’s Internet
application
transport
network
data link
physical
5. data flow
begins
4. call
1.connected
initiate
call
6. receive
3. data
accept
call
2. incoming
call
application
transport
network
data link
physical
Datagram networks


no call setup at network layer
routers: no state about end-to-end connections
 no network-level concept of “connection”

packets forwarded using destination host address
application
transport
network
data link
physical
1. send
datagrams
2. receive
datagrams
application
transport
network
data link
physical
Datagram forwarding table
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
IP destination address in
arriving packet’s header
1
3 2
4 billion IP addresses, so
rather than list individual
destination address
list range of addresses
(aggregate table entries)
Datagram forwarding table
Destination Address Range
Link Interface
11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111
0
11001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111
1
11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111
2
otherwise
Q: but what happens if ranges don’t divide up so nicely?
3
Longest prefix matching
longest prefix matching
when looking for forwarding table entry for given
destination address, use longest address prefix that
matches destination address.
Destination Address Range
Link interface
11001000 00010111 00010*** *********
0
11001000 00010111 00011000 *********
1
11001000 00010111 00011*** *********
2
otherwise
3
examples:
DA: 11001000 00010111 00010110 10100001
DA: 11001000 00010111 00011000 10101010
which interface?
which interface?
Datagram or VC network: why?
Internet (datagram)

data exchange among
computers
ATM (VC)


 strict timing, reliability
requirements
 need for guaranteed service
 “elastic” service, no strict
timing req.

many link types
 different characteristics
 uniform service difficult

“smart” end systems
(computers)
 can adapt, perform control,
error recovery
 simple inside network,
complexity at “edge”
evolved from telephony
human conversation:

“dumb” end systems
 telephones
 complexity inside network
what’s inside a router
Router architecture overview
two key router functions:


run routing algorithms/protocol (RIP, OSPF, BGP)
forwarding datagrams from incoming to outgoing link
forwarding tables computed,
pushed to input ports
routing
processor
routing, management
control plane (software)
forwarding data plane
(hardware)
high-seed
switching
fabric
router input ports
router output ports
Input port functions
link
layer
protocol
(receive)
line
termination
lookup,
forwarding
switch
fabric
queueing
physical layer:
bit-level reception
data link layer:
e.g., Ethernet
see chapter 5
decentralized switching:



given datagram dest., lookup output port
using forwarding table in input port memory
(“match plus action”)
goal: complete input port processing at ‘line
speed’
queuing: if datagrams arrive faster than
forwarding rate into switch fabric
Switching fabrics


transfer packet from input buffer to appropriate
output buffer
switching rate: rate at which packets can be
transfer from inputs to outputs
 often measured as multiple of input/output line rate
 N inputs: switching rate N times line rate desirable

three types of switching fabrics
memory
memory
bus
crossbar
Switching via memory
first generation routers:
 traditional
computers with switching under direct control of CPU
 packet copied to system’s memory
 speed limited by memory bandwidth (2 bus crossings per datagram)
input
port
(e.g.,
Ethernet)
memory
output
port
(e.g.,
Ethernet)
system bus
Switching via a bus
datagram from input port memory
to output port memory via a
shared bus

bus contention: switching speed
limited by bus bandwidth

32 Gbps bus, Cisco 5600:
sufficient speed for access and
enterprise routers

bus
Switching via interconnection network




overcome bus bandwidth
limitations
banyan networks, crossbar, other
interconnection nets initially
developed to connect processors
in multiprocessor
advanced design: fragmenting
datagram into fixed length cells,
switch cells through the fabric.
Cisco 12000: switches 60 Gbps
through the interconnection
network
crossbar
Output ports
switch
fabric
datagram
buffer
queueing


link
layer
protocol
(send)
line
termination
buffering required when datagrams arrive from fabric faster than the
transmission rate
scheduling discipline chooses among queued datagrams for transmission
Output port queueing
switch
fabric
at t, packets more
from input to output


switch
fabric
one packet time later
buffering when arrival rate via switch exceeds output line
speed
queueing (delay) and loss due to output port buffer overflow!
Input port queuing


fabric slower than input ports combined -> queueing may
occur at input queues
 queueing delay and loss due to input buffer overflow!
Head-of-the-Line (HOL) blocking: queued datagram at front
of queue prevents others in queue from moving forward
switch
fabric
output port contention:
only one red datagram can be
transferred.
lower red packet is blocked
switch
fabric
one packet time later:
green packet
experiences HOL
blocking
Midterm Revision:
Your Questions: Please Ask!
Difficult to Understand
Topics?