Computer Networks

(CS F303)
BITS Pilani Virendra Singh Shekhawat
Department of Computer Science and Information Systems
Pilani Campus
 BITS Pilani
Pilani Campus

Second Semester 2018-2019

Module-4 <Network Layer>
Lecture: 23-25 [5-9 Mar 2019]
What’s Next…

• Network Layer
– Network layer service models
– Forwarding versus routing
– How a router works
– IPv4 Datagram and Fragmentation
– IPv4 Addressing
• NAT
• Sub Netting
• IPv4 to IPv6 translation
• ICMP
– Routing (path selection) [BGP, RIP, OSPF]
– Multicast Routing
3
Computer Networks (CS F303) BITS Pilani, Pilani Campus
 Network layer

• Transport segment from sending to

receiving host
• On sending side encapsulates application
transport
segments into datagrams network
data link network
• On receiving side, delivers physical
network
data link
data link
physical
network
data link
physical
segments to transport layer physical
network
data link
physical network
data link
• Router examines header fields in physical

network
network
all IP datagrams passing through it data link
data link
physical
physical
network
data link application
physical transport
network
data link
physical

4
Computer Networks (CS F303) BITS Pilani, Pilani Campus
 Two Key Network-Layer
Functions
Forwarding: Move packets from input link to
output link within a router

routing algorithm

Routing: determine path taken by

local forwarding table
packets from source to destination. header value output link
0100 3
0101 2
0111 2
1001 1

value in arriving
packet’s header
0111 1
3 2

5
Computer Networks (CS F303) BITS Pilani, Pilani Campus
 Network Service Models
Example services for individual datagrams:
• Guaranteed delivery

• Guaranteed delivery with bounded delay (e.g., within 100 msec)

Example services for a flow of datagrams:

• In-order datagram delivery

• Guaranteed minimum bandwidth to flow

• Restrictions on changes in inter-packet spacing

• Security
6
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Network Layer Service Models

Guarantees ?
Network Service Congestion
Architecture Model Bandwidth Loss Order Timing feedback

Internet best effort none no no no no (inferred

via loss)
ATM CBR Guaranteed yes yes yes no
constant rate congestion
ATM VBR Guaranteed yes yes yes no
Rate congestion
ATM ABR Guaranteed no yes no yes
minimum

7
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Network Layer Connection and
Connection-less Service
• Datagram network
– Network-layer connectionless service
• VC Network
– Network-layer connection service
• Analogous to the transport-layer services, but
– Service: host-to-host
– No choice: network provides one or the other
– Implementation: in network core

8
Computer Networks (CS F303) BITS Pilani, Pilani Campus
What is VC ?

• VC consists of:
– Path from source to destination
– VC numbers (no destination address), one number
for each link along path
– Entries in forwarding tables in routers along path

9
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Forwarding table
VC number

12 22 32

1 3
2

Forwarding table in interface

number
router:
Incoming interface Incoming VC # Outgoing interface Outgoing VC #

1 12 3 22
2 63 1 18
3 7 2 17
1 97 3 87
… … … …

Routers maintain connection state information!

10
Computer Networks (CS F303) BITS Pilani, Pilani Campus
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
– Packets between same src-dest pair may take different paths

application
application
transport
transport
network
data link 1. Send data 2. Receive data network
data link
physical
physical

11
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Forwarding Table
Destination Address Range Link Interface

11001000 00010111 00010000 00000000

through 0
11001000 00010111 00010111 11111111

11001000 00010111 00011000 00000000

through 1
11001000 00010111 00011000 11111111

11001000 00010111 00011001 00000000

through 2
11001000 00010111 00011111 11111111

otherwise 3

12
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Longest Prefix Matching

Prefix Match Link Interface

11001000 00010111 00010 0
11001000 00010111 00011000 1
11001000 00010111 00011 2
otherwise 3
Examples
DA: 11001000 00010111 00010110 10100001 Which interface?

DA: 11001000 00010111 00011000 10101010 Which interface?

13
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Router Architecture Overview
[.1]

Two key router functions: Routing and Forwarding

14
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Router Architecture Overview
[..2]

15
Computer Networks (CS F303) BITS Pilani, Pilani Campus
 Input Port Functions

Physical layer:
bit-level reception
Decentralized switching:
Data link layer:
• Given datagram dest., lookup output port using
e.g., Ethernet forwarding table in input port memory
• Goal: complete input port processing at ‘line speed’

16
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Input Ports

Queuing: Fabric slower than input ports combined

Head Of Line (HOL) Blocking: queued datagram at front of

queue prevents others in queue from moving forward

17
Computer Networks (CS F303) BITS Pilani, Pilani Campus
 Switching Fabric
• Switching rate: rate at which packets can
be transferred from inputs to outputs
• N inputs: switching rate N times line
rate desirable

18
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Output Ports

• Buffering required when datagrams arrive from fabric faster than

the transmission rate
• Scheduling discipline chooses among queued datagrams for
transmission (FIFO, FQ, WFQ, RED)
• Queuing (delay) and loss due to output port buffer overflow!
19
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Output Port Queuing

Suppose Rswitch is N times faster than Rline

switch
switch
fabric
fabric

at t, packets move one packet-time later

from input to output

20
Computer Networks (CS F303) BITS Pilani, Pilani Campus
IP Datagram Format
IP protocol version 32 bits
number total datagram
header length length (bytes)
ver head. type of length
(bytes) len service for
“type” of data fragment fragmentation/
16-bit identifier flgs
offset reassembly
max number time to upper header
remaining hops live layer checksum Detect bit errors
(decremented at
32 bit source IP address In Datagram headers
each router)
32 bit destination IP address
upper layer protocol
to deliver payload to options (if any) e.g. timestamp,
record route
how much overhead? data taken, specify
(variable length, list of routers
 20 bytes of TCP
typically a TCP to visit.
 20 bytes of IP
or UDP segment)
 = 40 bytes + app
layer overhead
21
Computer Networks (CS F303) BITS Pilani, Pilani Campus
 IPv4 Addressing

• An IPv4 address is a 32-bit address

• Uniquely and universally defines the connection of a device (for
example, a computer or a router) to the Internet.
• The address space of IPv4 is 232 or 4,294,967,296

22
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Class full Addressing

Find the class of each address:

a. 00000001 00001011 00001011 11101111
b. 11000001 10000011 00011011 11111111
c. 14.23.120.8
d. 252.5.15.111

23
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Number of Blocks and Block Size

Default Masks for Class full Addressing

24
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Private Addresses

25
Computer Networks (CS F303) BITS Pilani, Pilani Campus
IP Addressing: Subnets [1]
223.1.1.1

223.1.2.1

223.1.1.2
223.1.1.4 223.1.2.9

223.1.3.27
223.1.1.3
223.1.2.2

223.1.3.1 223.1.3.2

26
Computer Networks (CS F303) BITS Pilani, Pilani Campus
IP Addressing: Subnets [2] 223.1.1.2

223.1.1.1 223.1.1.4

223.1.1.3

223.1.9.2 223.1.7.0

223.1.9.1 223.1.7.1
223.1.8.1 223.1.8.0

223.1.2.6 223.1.3.27

223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2

27
Computer Networks (CS F303) BITS Pilani, Pilani Campus
CIDR: Block of IP Addresses

28
Computer Networks (CS F303) BITS Pilani, Pilani Campus
 IPv4 Address Allocation

How does an ISP get block of addresses?

• ICANN: Internet Corporation for Assigned Names and Numbers
– Allocates addresses and manages DNS

ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20

Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23

Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23
Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23
... ….. …. ….
Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23

29
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Hierarchical Addressing: Route
Aggregation
Hierarchical addressing allows efficient advertisement of routing
information

Organization 0
200.23.16.0/23
Organization 1
“Send me anything
200.23.18.0/23 with addresses
Organization 2 beginning
200.23.20.0/23 . Fly-By-Night-ISP 200.23.16.0/20”
.
. . Internet
.
Organization 7 .
200.23.30.0/23
“Send me anything
ISPs-R-Us
with addresses
beginning
199.31.0.0/16”
30
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Hierarchical Addressing

ISPs-R-Us has a more specific route to Organization 1

Organization 0
200.23.16.0/23

“Send me anything
with addresses
Organization 2 beginning
200.23.20.0/23 . Fly-By-Night-ISP 200.23.16.0/20”
.
. . Internet
.
Organization 7 .
200.23.30.0/23
“Send me anything
ISPs-R-Us
with addresses
Organization 1 beginning 199.31.0.0/16
or 200.23.18.0/23”
200.23.18.0/23
31
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Exercise: Subnets

• An organization is given a block 17.12.14.0/26

– How many total addresses in the block???
– Range of addresses???
– Organization has Four departments. Wants to
divide the addresses into four sub-blocks of equal
size.
– Address of each subnet???

32
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Example: Different Size Subnets

• Organization has three departments. Wants to

divide the addresses into three sub-blocks of
32, 16, 16.

• Subnet mask for each subnet???

• Range of addresses in each subnet???

33
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Three Subnets

34
Computer Networks (CS F303) BITS Pilani, Pilani Campus
Thank You!

35
Computer Networks (CS F303) BITS Pilani, Pilani Campus