Chapter 4: Network Layer Chapter 4: Network Layer

Chapter goals: ˆ 4. 1 Introduction ˆ 4.5 Routing algorithms

ˆ 4.2 Virtual circuit and Link state
ˆ understand principles behind network layer


datagram networks Distance Vector

services: 
Hierarchical routing
ˆ 4.3 What’s inside a

 network layer service models
router ˆ 4.6 Routing in the
 forwarding versus routing
ˆ 4.4 IP: Internet
Internet
 how a router works
RIP
 routing (path selection)
Protocol 
 OSPF
Datagram format
 dealing with scale

 BGP
 IPv4 addressing
 advanced topics: IPv6, mobility ˆ 4.7 Broadcast and
 ICMP
ˆ instantiation, implementation in the Internet  IPv6 multicast routing

Network Layer 4-1 Network Layer 4-2

Network layer Two Key Network-Layer Functions

ˆ transport segment from application
transport

sending to receiving host network

ˆ forwarding: move analogy:

data link
physical

ˆ on sending side network network

encapsulates segments
network
data link
physical
data link
physical packets from router’s
ˆ routing: process of
data link

into datagrams
physical network network
data link input to appropriate
planning trip from
data link

router output
physical physical

ˆ on rcving side, delivers

segments to transport
network
data link
network
data link source to dest
ˆ routing: determine
physical physical
network
layer data link
physical
application
route taken by ˆ forwarding: process
ˆ network layer protocols
of getting through
network transport

packets from source

data link network

in every host, router

network
physical data link
network data link

single interchange
physical
data link physical

ˆ router examines header

physical
to dest.
fields in all IP datagrams
 routing algorithms
passing through it
Network Layer 4-3 Network Layer 4-4

1
 Interplay between routing and forwarding
Network service model
routing algorithm
Q: What service model for “channel” transporting
datagrams from sender to receiver?
local forwarding table

Example services for a

header value output link
0100 3 Example services for
0101
0111
2
2 individual datagrams: flow of datagrams:
ˆ guaranteed delivery ˆ in-order datagram
1001 1

ˆ guaranteed delivery delivery

value in arriving
packet’s header with less than 40 msec ˆ guaranteed minimum
0111 1 delay bandwidth to flow
3 2 ˆ restrictions on
changes in inter-
packet spacing

Network Layer 4-5 Network Layer 4-6

Network layer service models: Chapter 4: Network Layer

Guarantees ?
Network Service Congestion ˆ 4. 1 Introduction ˆ 4.5 Routing algorithms
Architecture Model Bandwidth Loss Order Timing feedback
ˆ 4.2 Virtual circuit and  Link state
Internet best effort none no no no no (inferred datagram networks  Distance Vector
Hierarchical routing
ˆ 4.3 What’s inside a
via loss) 

4.6 Routing in the

ATM CBR constant yes yes yes no
rate congestion router ˆ
ATM VBR guaranteed yes yes yes no ˆ 4.4 IP: Internet
Internet
RIP
rate congestion Protocol 
ATM ABR guaranteed no yes no yes  OSPF
minimum  Datagram format
 BGP
ATM UBR none no yes no no  IPv4 addressing
 ICMP ˆ 4.7 Broadcast and
 IPv6 multicast routing

Network Layer 4-7 Network Layer 4-8

2
Network layer connection and
connection-less service Virtual circuits
ˆ datagram network provides network-layer “source-to-dest path behaves much like telephone
circuit”
connectionless service  performance-wise
ˆ VC network provides network-layer  network actions along source-to-dest path
connection service
ˆ analogous to the transport-layer services, ˆ call setup, teardown for each call before data can flow
ˆ each packet carries VC identifier (not destination host
but: address)
 service:host-to-host ˆ every router on source-dest path maintains “state” for
 no choice: network provides one or the other each passing connection
ˆ link, router resources (bandwidth, buffers) may be
 implementation: in network core
allocated to VC (dedicated resources = predictable service)

Network Layer 4-9 Network Layer 4-10

VC implementation Forwarding table VC number

12 22 32

a VC consists of: 1
2
3

1. path from source to destination

2. VC numbers, one number for each link along Forwarding table in interface
number
path northwest router:
3. entries in forwarding tables in routers along Incoming interface Incoming VC # Outgoing interface Outgoing VC #

path 1 12 3 22
2 63 1 18
ˆ packet belonging to VC carries VC number 3 7 2 17
(rather than dest address) 1 97 3 87
… … … …
ˆ VC number can be changed on each link.
 New VC number comes from forwarding table
Routers maintain connection state information!
Network Layer 4-11 Network Layer 4-12

3
Virtual circuits: signaling protocols Datagram networks
ˆ no call setup at network layer
ˆ routers: no state about end-to-end connections
ˆ used to setup, maintain teardown VC
 no network-level concept of “connection”
ˆ used in ATM, frame-relay, X.25
ˆ packets forwarded using destination host address
ˆ not used in today’s Internet  packets between same source-dest pair may take
different paths

application
6. Receive data application
transport 5. Data flow begins application
3. Accept call transport application
network 4. Call connected transport
2. incoming call network transport
data link 1. Initiate call network
physical
data link data link 1. Send data 2. Receive data network
physical data link
physical
physical

Network Layer 4-13 Network Layer 4-14

4 billion
Forwarding table possible entries Longest prefix matching

Destination Address Range Link Interface Prefix Match Link Interface

11001000 00010111 00010 0
11001000 00010111 00010000 00000000 11001000 00010111 00011000 1
through 0 11001000 00010111 00011 2
11001000 00010111 00010111 11111111 otherwise 3

11001000 00010111 00011000 00000000

through 1 Examples
11001000 00010111 00011000 11111111 Which interface?
DA: 11001000 00010111 00010110 10100001
11001000 00010111 00011001 00000000
through 2 DA: 11001000 00010111 00011000 10101010 Which interface?
11001000 00010111 00011111 11111111

otherwise 3

Network Layer 4-15 Network Layer 4-16

4
Datagram or VC network: why? Chapter 4: Network Layer
Internet (datagram) ATM (VC) ˆ 4. 1 Introduction ˆ 4.5 Routing algorithms
ˆ data exchange among ˆ evolved from telephony ˆ 4.2 Virtual circuit and  Link state
computers
ˆ human conversation: datagram networks  Distance Vector
 “elastic” service, no strict
 strict timing, reliability Hierarchical routing
ˆ 4.3 What’s inside a

timing req.
requirements
ˆ “smart” end systems router ˆ 4.6 Routing in the
 need for guaranteed
(computers)
service ˆ 4.4 IP: Internet
Internet
 can adapt, perform RIP
ˆ “dumb” end systems Protocol 
control, error recovery  OSPF
 telephones  Datagram format
 simple inside network,  BGP
 complexity inside IPv4 addressing
complexity at “edge” 
network ICMP ˆ 4.7 Broadcast and
ˆ many link types 
IPv6 multicast routing
 different characteristics 

 uniform service difficult

Network Layer 4-17 Network Layer 4-18

Router Router Architecture Overview

Two key router functions:
ˆ run routing algorithms/protocol (RIP, OSPF, BGP)
ˆ forwarding datagrams from incoming to outgoing link

Photo courtesy Newstream.com

Network Layer 4-19 Network Layer 4-20

5
 Input Port Functions Three types of switching fabrics

Physical layer:
bit-level reception
Data link layer: Decentralized switching:
e.g., Ethernet ˆ given datagram dest., lookup output port
see chapter 5 using forwarding table in input port
memory
ˆ goal: complete input port processing at
‘line speed’
ˆ queuing: if datagrams arrive faster than
forwarding rate into switch fabric

Network Layer 4-21 Network Layer 4-22

Switching Via Memory

First generation routers: Switching Via a Bus
ˆ traditional computers with switching under direct
control of CPU
ˆpacket copied to system’s memory
ˆ datagram from input port memory
ˆ speed limited by memory bandwidth (2 bus
to output port memory via a shared
crossings per datagram)
bus
Memory
ˆ bus contention: switching speed
Input Output
Port Port
limited by bus bandwidth
ˆ 1 Gbps bus, Cisco 1900: sufficient
speed for access and enterprise
System Bus
routers (not regional or backbone)

Network Layer 4-23 Network Layer 4-24

6
Switching Via An Interconnection Output Ports
Network

ˆ overcome bus bandwidth limitations

ˆ Banyan networks, other interconnection nets
initially developed to connect processors in
multiprocessor
ˆ Advanced design: fragmenting datagram into fixed
length cells, switch cells through the fabric.
ˆ Buffering required when datagrams arrive from
ˆ Cisco 12000: switches Gbps through the
fabric faster than the transmission rate
interconnection network
ˆ Scheduling discipline chooses among queued
datagrams for transmission

Network Layer 4-25 Network Layer 4-26

Output port queueing How much buffering?

ˆ RFC 3439 rule of thumb: average buffering
equal to “typical” RTT (say 250 msec) times
link capacity C
 e.g., C = 10 Gps link: 2.5 Gbit buffer
ˆ Recent recommendation: with N flows,
buffering equal to RTT. C
N
ˆ buffering when arrival rate via switch exceeds
output line speed
ˆ queueing (delay) and loss due to output port
buffer overflow!
Network Layer 4-27 Network Layer 4-28

7
Input Port Queuing
ˆ Fabric slower than input ports combined -> queueing
may occur at input queues
ˆ Head-of-the-Line (HOL) blocking: queued datagram
at front of queue prevents others in queue from
moving forward
ˆ queueing delay and loss due to input buffer overflow!

Network Layer 4-29