COMP 3331/9331: Computer Networks and Applications
Week 7
Network Layer Chapter 4, Sections:4.1 – 4.3
Assignment 1
v Hard deadline: NO EXTENSIONS
v IMPORTANT: Make sure you test your program
on CSE machines as per the demo setup
v Demonstration Schedule for Week 8 is linked to assignment page
§ YOU MUST ATTEND YOUR ALLOCATED SLOT
v MONDAY: PUBLIC HOLIDAY
§ Demo in Week 9
§ Monday lab schedule will be pushed back by one week
Network Layer 2
Chapter 4: network layer
Our goals:
v understand principles behind network layer services:
§ network layer service models § forwarding versus routing § how a router works § routing (path selection) § broadcast, multicast
v instantiation, implementation in the Internet Network Layer 3
Network Layer: outline
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol § datagram format
§ IPv4 addressing
§ ICMP
§ IPv6
4.5 routing algorithms § link state
§ distance vector
§ hierarchical routing
4.6 routing in the Internet § RIP
§ OSPF § BGP
4.7 broadcast and multicast routing
Network Layer 4
Some background
v 1968: DARPAnet/ARPAnet (precursor to Internet) § (Defense) Advanced Research Projects Agency Network
v Mid 1970’s: new networks emerge § SATNet,PacketRadio,Ethernet
§ All “islands” to themselves – didn’t work together
v Big question: How to connect these networks?
Network Layer 5
Internet Protocol Stack
• Application: Email, Web, … Internetworking
• Transport: TCP, UDP, … • Network:IP
v Cerf & Kahn in 1974,
• Link: Ethernet, WiFi, ATM, …
§ “A Protocol for Packet Network Intercommunication”
• Physical: copper, fiber, air, … § Foundation for the modern Internet
v Routers forward packets from source to destination
• “Hourglass” model, “thin waist”, “narrow waist” § May cross many separate networks along the
way
v All packets use a common Internet
Protocol
§ Any underlying data link protocol
§ Any higher layer transport protocol
Network Layer 6
Email
Web
UDP
TCP
IP
Ethernet ATM
…
Network layer
v transport segment from sending to receiving host
v on sending side encapsulates segments into datagrams
v on receiving side, delivers segments to transport layer
v network layer protocols in every host, router
v router examines header fields in all IP datagrams passing through it
application
transport
network
data link
physical
network
network
data link
data link
network
data link
physical
physical
physical
network
network
data link
data link
physical
physical
network
network
data link
physical
network
net
data link physical
work
data link
physical
application
transport
data link
network
network
physical
data link
network
data link
data link physical
physical
physical
Network Layer 7
Two key network-layer functions
v forwarding: move packets from router’s input to appropriate router output
v routing: determine route taken by packets from source to dest.
§ routing algorithms
analogy:
v routing: process of planning trip from source
to dest
v forwarding: process of getting through single
interchange
Network Layer 8
Quiz: When should a router perform routing? Fowarding
A: Do both when a packet arrives
B: Route in advance, forward when a packet arrives C: Forward in advance, route when a packet arrives D: Do both in advance
E: Some other combination
Network Layer 9
Interplay between routing and forwarding
routing algorithm
local forwarding table
header value
0100 0101 0111 1001
output link
3 2 2 1
0111
routing algorithm determines end-end-path through network
forwarding table determines local forwarding at this router
value in arriving packet’s header
3
1 2
Network Layer 10
Connection setup
v 3rd important function in some network architectures:
§ ATM, frame relay, X.25
v before datagrams flow, two end hosts and intervening routers establish virtual connection
§ routers get involved
v network vs transport layer connection
service:
§ network: between two hosts (may also involve intervening routers in case of VCs)
§ transport: between two processes
Network Layer 11
Network service model
Self Study
Q: What service model for “channel” transporting datagrams from sender to receiver?
example services for individual datagrams:
v guaranteed delivery
v guaranteed delivery with less than 40 msec delay
example services for a flow of datagrams:
v in-order datagram delivery
v guaranteed minimum bandwidth to flow
v restrictions on changes in inter-packet spacing
Network Layer 12
Network layer service models:
Self Study
Network Architecture
Internet ATM ATM ATM ATM
Service Model
best effort CBR VBR ABR UBR
Guarantees ? Bandwidth Loss Order Timing
Congestion feedback
no (inferred via loss) no congestion no congestion yes
no
none
constant rate
no no no
yes yes yes
guaranteed yes yes yes
rate
guaranteed no yes no
minimum
none no yes no
Network Layer 13
Network Layer: outline
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol § datagram format
§ IPv4 addressing
§ ICMP
§ IPv6
4.5 routing algorithms § link state
§ distance vector
§ hierarchical routing
4.6 routing in the Internet § RIP
§ OSPF § BGP
4.7 broadcast and multicast routing
Network Layer 14
Connection, connection-less service
v datagram network provides network-layer connectionless service
v virtual-circuit network provides network- layer connection service
v analogous to TCP/UDP connecton- oriented / connectionless transport-layer services, but:
§ service: host-to-host
§ no choice: network provides one or the other § implementation: in network core
Network Layer 15
Virtual circuits
“source-to-dest path behaves much like telephone circuit”
§ performance-wise
§ network actions along source-to-dest path
v call setup, teardown for each call before data can flow v each packet carries VC identifier (not destination host
address)
v every router on source-dest path maintains “state” for each passing connection
v link, router resources (bandwidth, buffers) may be allocated to VC (dedicated resources = predictable service)
Network Layer 16
VC implementation
a VC consists of:
v v
1. path from source to destination
2. VC numbers, one number for each link along path
3. 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.
§ newVCnumbercomesfromforwardingtable Network Layer 17
VC forwarding table
32
22
12
Host A 12 1
VC number
interface number
R1 22 R2
3
Host B
32
forwarding table in Router R1:
Incoming interface
Incoming VC # Outgoing interface Outgoing VC #
2
1 12 3 22 2 63 1 18 3 7 2 17 1 97 3 87 …………
VC routers maintain connection state information!
Network Layer 18
ATM ABR guaranteed no yes no yes
s
’
ATM UBR
minimum
none no yes no no
” dynamically
CS357b 93
Self Study
Virtual Circuit Setup – Example
2312
0 Switch Z 43
SwitchY
1
0
Z’s table Y’s table
Host B
Host A
In VCI
In port
Out port
Out VCI
In VCI
In port
Out port
Out
CI
1
Signal
V
Network Layer 19
2
0
B
Y
no
” dynamically set up on per-call basis
no
57b 93
CS357b 94
Example (contd.)
Self Study
2312
0 Switch Z 43
SwitchY
1
0
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
SHigonsatlAB
In VCI
In port
Out port
Out
CI
V
Network Layer 20
1
3
2
CS3
Example (contd.)
Self Study
2
1
0
Host A
312 0 Switch Z
43
Swigintcahl BY
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
In VCI
In port
Out port
Out
CI
1
V
30
Network Layer 21
2
Signal B
0
Y’s 4
3
t
2
Example (contd.)
Self Study
2
1
0
312 0 Switch Z
43
Z’s table Y’s table
Host B
Host A
Swigintcahl BY
In VCI
In port
Out port
Out port
CI
Out VCI
In VCI
In port
Out
3
0
4
V
Switch Y chooses to use VC # 3 for this connection on the link connecting Host A to Switch Y
Why? – VC #’s 0, 1 and 2 may be already in use
Network Layer 22
1
3
304
Example (contd.)
Self Study
2
3
1
2
1
Switch Y
403 0
Z’s table Y’s table
Host B
Host A
Out port
CI
SwigintcahlBZ
In VCI
In port
Out port
Out VCI
In VCI
In port
Out
3
0
4
1
V
30
Network Layer 23
2
0
Y’ 4
s
304
2
Example (contd.)
Self Study
2
3
1
2
SwigintcahlBZ
403 0
1
Switch Y
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
Host A
Out port
CI
12
0
3
In VCI
In port
Out
3
0
4
V
Switch Z chooses to use VC # 12 for this connection on the link connecting Switch Y to Switch Z Note: VC # on each link are chosen independently
Network Layer 48
1
Signal B
3
121
304 304
Example (contd.)
Self Study
2312
0 Switch Z 43
Z’s table Y’s table
SwitchY
1
0
SHigonsatl B B
In VCI
In port
Out port
Out VCI
Host A
In port
CI
12
0
3
In VCI
Out port
Out
3
0
4
1
V
30
Network Layer 25
2
0
Y’ 4
s
1
3
Si 3
2
304
Example (contd.)
Self Study
2312
0 Switch Z 43
Z’s table Y’s table
SwitchY
1
0
AHCosKtB7
In VCI
In port
Out port
Out VCI
Host A
Out port
CI
12
0
3
In VCI
In port
Out
3
0
4
gnal B
V
Host B chooses to use VC # 7 for this connection on the link connecting Switch Z to Host B Network Layer 26
Example (contd.)
Self Study
2
3
1
2
SAwCitcKh7Z
1
Switch Y
403 0
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
Host A
In port
Out port
CI
12
0
3
In VCI
Out
3
0
4
1
V
30
ACK message informs upstream switch about the VC # to use on out-going link Network Layer 27
2
0
Y’ 4
s
Example (contd.)
Self Study
2
3
1
2
SAwCitKch1Z2
403 0
1
Switch Y
Z’s table Y’s table
Host B
Host A
In VCI
In port
Out port
Out VCI
Out port
CI
12
0
3
7
In VCI
In port
Out
3
0
4
2
V
Network Layer 28
1
ACK 7
3
3
2
304 304
Example (contd.)
Self Study
2
1
0
Host A
312 0 Switch Z
43
Switch Y
ACK 12
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
In port
CI
12
0
3
7
In VCI
Out port
Out
3
0
4
2
1
0
V
30
Network Layer 29
3
ACK 3
Y’s t 4
4
a
304
2
Example (contd.)
Self Study
2
1
0
Host A
312 0 Switch Z
43
SAwCitKch3Y
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
12
0
3
7
In VCI
In port
Out port
Out
CI
3
0
4
12
7
V
Network Layer 30
1
3
e 03
l
2
304 304
Example (contd.)
VC Setup is now complete
Self Study
2312
0 Switch Z 43
SwitchY
1
0
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
AHCosKtA3
12
0
3
7
In VCI
In port
Out port
Out
CI
3
0
4
12
1
V
I love yo 3
ACK message informs sender (Host A) about the VC # to be used for this connection Network Layer 31
2
0
u! 3 04
Y
’
1
3
2
3
3 0 4 12
Example (contd.)
Data Transmission begins
Self Study
2312
SwitchY
0 Switch Z 43
1
0
IloHveosytoAu!3
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
12
0
3
7
In VCI
In port
Out port
Out
CI
3
0
4
12
7
V
Network Layer 32
Example (contd.)
Self Study
23
IloSvweitycohuY!3 0
12
Switch Z
1
0 43
Z’s table Y’s table
Host B
Host A
In VCI
In port
Out port
Out VCI
12
0
3
In VCI
In port
Out port
Out
7
CI
3
0
4
12
1 Il
V
30
Network Layer 33
2
ove you!
0
Y’s 4
23123
3
1
t
2
Example (contd.)
Self Study
2
1
0
Host A
3
0
12
Switch Z
3
Host B
Switch Y
I love you! 12
Z’s table Y’s table
Out port
4
In VCI
In port
Out port
Out VCI
12
0
3
7
In VCI
In port
Out
CI
3
0
4
12
7
V
Network Layer 34
1
3
3
121
4
3 0 4 12
3 0
Self Study
Example (contd.)
2
3
1
2
IloSvweitycohuZ!12 403
Switch Y
1
0
Host A
Z’s table Y’s table
Host B
In VCI
In port
Out port
Out VCI
12
0
3
7
In VCI
In port
Out port
Out
CI
3
0
4
12
2
1
0
V
30
Network Layer 35
Y’s t 4
3
4
a
0
3 7
Y’s table 12 0
3 7
12
3 0 4 12
Example (contd.)
Self Study
2
3
1
2
IloSwveitcyhouZ!7 0 3
1
SwitchY 4 0
Z’s table Y’s table
Host B
Host A
In VCI
In port
Out port
Out VCI
12
0
3
7
In VCI
In port
Out port
Out
CI
3
0
4
12
2
7
V
Network Layer 36
1
love you!
3
e 03
l
3 0 4 12
3 0 4
Example (contd.)
Self Study
2312
0 Switch Z 43
Z’s table Y’s table
SwitchY
1
0
IloHveosytoBu!7
Host A
In VCI
In port
Out port
Out VCI
12
0
3
7
In VCI
In port
Out port
Out
CI
3
0
4
12
V
Ad • Ad
set-
• Vir for
• Thi an
•
Network Layer 37
dres dresses a
up (“sign
tual Circ sending
s doesn’t entry in e
Or does it
s r
u m
Virtual circuits: signaling protocols
v used to setup, maintain teardown VC v used in ATM, frame-relay, X.25
v not widely used in today’s Internet
application
transport
5. data flow begins
4. call connected
1. initiate call
6. receive data
3. accept call 2. incoming call
transport
network
network
data link
physical
application
data link
physical
Network Layer 38
IN PRACTICE
Virtual Circuits in Action
v MPLS (Multi-protocol Label Switching): RFC 3031 § Packets pre-fixed with “labels”
• A 20-bit label value
• a 3-bit Traffic Class field for Quality of Service (QoS) priority and ECN
(Explicit Congestion Notification)
• a 1-bit bottom of stack flag.
– If this is set, it signifies that the current label is the last in the stack
• 8-bit TTL field
§ Labels can be stacked on top of another
§ Virtual circuit (label-switched path) established between Label Edge Routers (LERs)
§ Often used to setup Virtual Private Networks (VPN)
Network Layer 39
Datagram networks
v no call setup at network layer
v routers: no state about end-to-end connections
§ no network-level concept of “connection”
v packets forwarded using destination host address
application
transport
application
1. send datagrams
2. receive datagram
transport
network
s
network
data link
physical
data link
physical
Network Layer 40
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
4 billion IP addresses, so rather than list individual
destination address list range of addresses (aggregate table entries)
IP destination address in arriving packet’s header
1 32
Network Layer 41
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
3
Q: but what happens if ranges don’t divide up so nicely?
Network Layer 42
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:
which interface? DA: 11001000 00010111 00011000 10101010 which interface?
DA: 11001000 00010111 00010110 10100001
Network Layer 43
Datagram or VC network: why?
Internet (datagram)
v data exchange among computers
§ “elastic” service, no strict timing req.
v many link types
§ different characteristics § uniform service difficult
v “smart”endsystems (computers)
§ can adapt, perform control, error recovery
§ simple inside network, complexity at “edge”
ATM (VC)
v evolved from telephony v human conversation:
§ strict timing, reliability requirements
§ need for guaranteed service
v “dumb”endsystems § telephones
§ complexity inside network
Network Layer 44
Quiz: Connection state
v Which of the following relies on connection state in routers in the network? Pick one.
A. TCP
B. Internet
C. Virtual circuit network D. UDP
E. A and C
Network Layer 45
Quiz: Virtual circuit
v Which of the following is true? Pick one.
A. A virtual circuit uses a different VC number
for each link along a route
B. A virtual circuit uses the same VC number for all packets in a connection
C. A virtual circuit router uses the destination address (among other fields) in order to determine the outgoing interface
D. A and C
Network Layer 46
Quiz: Longest prefix matching
v On which outgoing interface will a packet destined to 11011001 be forwarded?
Prefix
Interface
1*
A
11*
B
111*
C
Default
D
Network Layer 47
Network Layer: outline
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol § datagram format
§ IPv4 addressing
§ ICMP
§ IPv6
4.5 routing algorithms § link state
§ distance vector
§ hierarchical routing
4.6 routing in the Internet § RIP
§ OSPF § BGP
4.7 broadcast and multicast routing
Network Layer 48
IP Routers
v Core building block of the Internet infrastructure
v $120B+ industry
v Vendors: Cisco, Huawei, Juniper, Alcatel- Lucent (account for >90%)
Network Layer 49
Router definitions
1 N
N-1
2 3
…
5
R bits/sec 4
• N = number of external router “ports” • R = speed (“line rate”) of a port
• Router capacity = N x R
Network Layer 50
Networks and routers
UNSW
home, small business
Optus
core
edge (ISP)
core
edge (enterprise)
IBM
UoW
Network Layer 51
Examples of routers (core)
Juniper T4000
• R= 10/40 Gbps • NR=4Tbps
Cisco CRS
• R=10/40/100 Gbps • NR = 322 Tbps
72 racks, 1MW
Network Layer 52
Examples of routers (edge)
Cisco ASR 1006
• R=1/10 Gbps • NR = 40 Gbps
Juniper M120
• R= 2.5/10 Gbps • NR = 120 Gbps
Network Layer 53
Examples of routers (small business)
Cisco 3945E
• R = 10/100/1000 Mbps • NR < 10 Gbps
Network Layer 54
What’s inside a router?
Processes packets on their way in
Linecards (input)
Input and Output for the same port are on one
physical linecard
Processes packets
Linecards (output)
before they leave
Transfers packets from input to
ts
Route/Control Processor
1
1
2
Interconnect (Switching) Fabric
2
N
output por
N
Network Layer 55
What’s inside a router?
Linecards (input)
(1) Implement IGP
and BGP protocols; (2) Push forwarding
compute routing tables tables to the line cards
Linecards (output)
Route/Control Processor
1
2
Interconnect (Switching) Fabric
1
2
N
N
Network Layer 56
What’s inside a router?
Linecards (input)
Constitutes the control plane
Constitutes the data plane
Linecards (output)
Route/Control Processor
1
2
Interconnect Fabric
1
2
N
N
Network Layer 57
Input Linecards
Version
Header Length
Type of Service (TOS)
Total Length (Bytes)
16-bit Identification
Flags
Fragment Offset
Time to Live (TTL)
Protocol
Header Checksum
Source IP Address
Destination IP Address
Options (if any)
Payload
Network Layer 58
Input Linecards
v Tasks
§ Receive incoming packets (physical layer stuff) § Update the IP header
• TTL, Checksum, Options (maybe), Fragment (maybe) § Lookup the output port for the destination IP address
§ Queue the packet at the switch fabric
v Challenge: speed!
§ 100B packets @ 40Gbps à new packet every 20 nano secs!
v Typically implemented with specialized hardware § ASICs, specialized “network processors”
§ “exception” processing often done at control processor
Network Layer 59
IP Lookup
v IP addressing and routing (to be discussed)
§ For scalability, multiple IP addresses are aggregated
§ Routing protocols operates on IP address prefixes ( “a.b.c.d/n” notation)
§ IP routing tables maintain a mapping from IP prefixes to output interfaces
v Route lookupàfind the longest prefix in the table that matches the packet destination address
§ Longest Prefix Match (LPM) lookup
Network Layer 60
Longest Prefix Match Lookup
v Packet with destination address 12.82.100.101 is sent to interface 2, as 12.82.100.xxx is the longest prefix matching packet’s destination address
128.16.120.xxx
1
12.82.xxx.xxx
3
12.82.100.xxx
2
...
...
1 2
12.82.100.101
128.16.120.111
Network Layer 61
Example #1: 4 Prefixes, 4 Ports
Port 1
ISP Router
Port 4
Port 2
Port 3
201.143.0.0/22
201.143.4.0/24 201.143.5.0/24
201.143.6.0/23
Prefix
Port
201.143.0.0/22
Port 1
201.143.4.0.0/24
Port 2
201.143.5.0.0/24
Port 3
201.143.6.0/23
Port 4
Network Layer 62
Finding the Match
10001111
000000−−
−−−−−−−
201.143.0.0/22
201.143.4.0/24
11001001
10001111
00000100
−−−−−−−
201.143.5.0/24
11001001
201.143.6.0/23
11001001
10001111
10001111
0000011−
−−−−−−−
11001001
v Consider 11001001100011110000010111010010 § First 21 bits match 4 partial prefixes
§ First 22 bits match 3 partial prefixes
§ First 23 bits match 2 partial prefixes
§ First 24 bits match exactly one full prefix
00000101
−−−−−−−
Network Layer 63
Finding Match Efficiently
v Testing each entry to find a match scales poorly § On average: O(number of entries)
v Leverage tree structure of binary strings § Set up tree-like data structure
v Return to example:
Prefix Prefix
Port Port
1100100110001111000000**********
1100100110001111000000**********
1 1
110010011000111100000100********
110010011000111100000100********
2 2
110010011000111100000101********
110010011000111100000101********
3 3
11001001100011110000011*********
11001001100011110000011*********
4 4
Network Layer 64
Consider four three-bit prefixes
v Just focusing on the bits where all the action is....
v 0**èPort1 v 100èPort2 v 101èPort3 v 11*èPort4
Network Layer 65
Tree Structure
***
0** è 100 è 101 è 11* è
Port 1 Port 2 Port 3 Port 4
0
01 01
1
0**
1**
00*
01
01* 10*
11*
010101
000
001 010 011 100 101 110 111
Network Layer 66
Walk Tree: Stop at Prefix
Entries
0** è 100 è 101 è 11* è
Port 1 Port 2 Port 3 Port 4
***
0
01 01
1
0**
1**
00*
01
01* 10*
11*
010101
000
001 010 011 100 101 110 111
Network Layer 67
Walk Tree: Stop at Prefix
Entries
0** è 100 è 101 è 11* è
Port 1 Port 2 Port 3 Port 4
***
0
0P11 01
1
0**
1**
00*
01
000
01* 10*
11*
0 1 0 1 0P41 001 010 011 100 101 110 111
P2 P3
Network Layer 68
Slightly Different Example
v Several of the unique prefixes go to same port
v 0**èPort1 v 100èPort2 v 101èPort1 v 11*èPort1
Network Layer 69
Prefix Tree
***
0** è 100 è 101 è 11* è
Port 1 Port 2 Port 1 Port 1
0
0P11 01
1
0**
1**
00*
01
000
01* 10*
11*
0 1 0 1 0P11 001 010 011 100 101 110 111
P2 P1
Network Layer 70
LPM in real routers
v Real routers use far more advanced/ complex solutions than the approaches I just described
§ but what we discussed is their starting point v With many heuristics and optimizations
that leverage real-world patterns
§ Some destinations more popular than others § Some ports lead to more destinations § Typical prefix granularities
Network Layer 71
Recap: Input linecards
v Main challenge is processing speeds
v Tasks involved:
§ Update packet header (easy)
§ LPM lookup on destination address (harder)
v Mostly implemented with specialized hardware
Network Layer 72
l
l l
Output Linecard
Packet classification: map each packet to a “flow”
l Flow (for now): set of packets between two particular endpoints
Buffer management: decide when and which packet to drop Scheduler: decide when and which packet to transmit
Buffer management
flow 1 flow 2
flow n
Classifier
Scheduler
1 2
Network Layer 73
Output Linecard
l Packet classification: map each packet to a “flow”
l Flow (for now): set of packets between two particular endpoints
l Buffer management: decide when and which packet to drop l Scheduler: decide when and which packet to transmit
l Used to implement various forms of policy
l Deny all e-mail traffic from ISP-X to Y (access control)
l Route IP telephony traffic from X to Y via PHY_CIRCUIT (policy) l Ensure that no more than 50 Mbps are injected from ISP-X (QoS)
Network Layer 74
Simplest: FIFO Router
v No classification
v Drop-tail buffer management: when buffer is full drop the
incoming packet
v First-In-First-Out (FIFO) Scheduling: schedule packets in the same order they arrive
Buffer
Scheduler
1 2
Network Layer 75
Packet Classification
v Classify an IP packet based on a number of fields in the packet header, e.g.,
§ source/destination IP address (32 bits)
§ source/destination TCP port number (16 bits) § Type of service (TOS) byte (8 bits)
§ Type of protocol (8 bits)
v In general fields are specified by range
§ classification requires a multi-dimensional range search!
Buffer management
flow 1 flow 2
flow n
Classifier
Scheduler
1 2
Network Layer 76
Scheduler
v One queue per “flow”
v Scheduler decides when and from which queue to send a
packet
v Goals of a scheduling algorithm: § Fast!
§ Depends on the policy being implemented (fairness, priority, etc.)
Buffer management
flow 1 flow 2
flow n
Classifier
Scheduler
1 2
Network Layer 77
Example: Priority Scheduler
v Priority scheduler: packets in the highest priority queue are always served before the packets in lower priority queues
High priority
Medium priority
Low priority
Priority Scheduler
Network Layer 78
Example: Round Robin Scheduler
v Round robin: packets are served from each queue in turn
High priority
Medium priority
Low priority
Fair Scheduler
Network Layer 79
Switching
Linecards (input) Linecards (output)
Route/Control Processor
1
1
2
Interconnect Fabric
2
N
N
Network Layer 80
Shared Memory (1st Generation) Shared Backplane
CPU
Route Table
Buffer
Memory
Line Interface
MAC
Line Interface
MAC
Line Interface
MAC
Limited by rate of shared memory
(* Slide by Nick McKeown, Stanford Univ.)
Network Layer 81
Shared Bus (2nd Generation)
Limited by shared bus
Line Card
CPU
Route Table
Buffer
Memory
Line Card
Buffer Memory
Fwding Cache
MAC
Line Card
Buffer Memory
Buffer Memory
Fwding Cache
Fwding Cache
MAC
MAC
(* Slide by Nick McKeown)
Network Layer 82
Point-to-Point Switch (3rd Generation) Switched Backplane
CPU Card
Line Card
Routing Table
Local Buffer Memory
Fwding Table
MAC
Line Card
Local Buffer Memory
Fwding Table
MAC
(*Slide by Nick McKeown)
Network Layer 83
3rd Gen. Router: Switched Interconnects
NxR
This is called an “output queued” switch
© Nick McKeown 2006 Network Layer 84
3rd Gen. Router: Switched Interconnects
This is called an “input queued” switch
© Nick McKeown 2006 Network Layer 85
Two challenges with input queuing
1) Need an internal fabric scheduler!
Network Layer 86
3rd Gen. Router: Switched Interconnects
© Nick McKeown 2006
Fabric Scheduler 87
1xR
Two challenges with input queuing
1) Need an internal fabric scheduler!
2) Must avoid “head-of-line” blocking
Network Layer 88
Head of Line Blocking
HoL blocking limits throughput to approximately
58% of capacity Network Layer 89
“Virtual Output Queues”
Network Layer 90
3rd Gen. Router: Switched Interconnects
© Nick McKeown 2006
Fabric Scheduler 91
1xR
Reality is more complicated
v Commercial (high-speed) routers use
§ combination of input and output queuing
§ complex multi-stage switching topologies (Clos, Benes)
§ distributed, multi-stage schedulers (for scalability)
Network Layer 92
Summary
What we’ve covered today:
v Network layer services
v Virtual Circuit and Datagram Networks v Router Internals
To be continued:
v IP
v IP addressing
v Fragmentation
v ICMP
v NAT
v Routing Algorithms
Network Layer 93