ECSE-4670: Computer

Communication Networks (CCN)

Network Layer
Shivkumar Kalyanaraman: shivkuma@[Link]
Biplab Sikdar: sikdab@[Link]
[Link]

1
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Chapter
Goals

• understand principles behind network

layer services:
– Internetworking concepts
– The network layer
– IP
– routing (path selection)
– how a router works
2
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Overview

• Internetworking
• network layer services
• IP
• routing principle: path selection
• hierarchical routing
• Internet routing protocols reliable transfer
– intra-domain
– inter-domain
• what’s inside a router?

3
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 The Internetworking Problem
• Two nodes communicating across a
“network of networks”…
– How to transport packets through
this heterogeneous mass ?
A B

C lo u d

C lo u d

C lo u d

4
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 The Internetworking Problem
• Problems: heterogeneity and scaling
• Heterogeneity:
– How to interconnect a large number of
disparate networks ? (lower layers)
– How to support a wide variety of applications
? (upper layers)
• Scaling:
– How to support a large number of end-nodes
and applications in this interconnected
network ?

5
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Heterogeneity: Solutions
• Translation (eg: bridges): specify a
separate mapping between every pair of
protocols
(+) No software changes in networks required.

() Need to specify N mappings when a new

lower layer protocol is added to the list
() When many networks, subset = 0
() Mapping may be asymmetric

6
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Heterogeneity: Solutions
– Overlay model: Define a new protocol (IP)
and map all networks to IP
(+) Require only one mapping (IP -> new
protocol) when a new protocol is added
(+) Global address space can be created
for universal addressibility and scaling

() Requires changes in lower networks

(eg: protocol type field for IP)

7
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Heterogeneity: Solutions
() IP has to be necessarily simple else
mapping will be hard.
– Even in its current form mapping
IP to ATM has proven to be really
hard.
– Basis for “best-effort” forwarding
() Protocol mapping infrastructure
needed: address hierarchy, address
resolution, fragmentation

8
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 The Internet Network layer
Host, router network layer functions:

Transport layer: TCP, UDP

Routing protocols IP protocol

•path selection •addressing conventions
•RIP, OSPF, BGP •datagram format
Network •packet handling conventions
layer routing
table ICMP protocol
•error reporting
•router “signaling”

Link layer

physical layer

9
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP Addressing: introduction
• IP address: 32-bit
[Link]
identifier for host,
router interface [Link]
[Link]
• interface: connection [Link] [Link]
between host, router [Link]
and physical link [Link] [Link]

– router’s typically have

multiple interfaces
– host may have multiple [Link] [Link]
interfaces
– IP addresses associated
with interface, not host,
router [Link] = 11011111 00000001 00000001 00000001

223 1 1 1
10
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP Addressing - 1
• IP address:
[Link]
– network part (high order
bits) [Link]
[Link]
– host part (low order bits) [Link] [Link]
• What’s a network ?
[Link]
(from IP address [Link] [Link]
perspective)
– device interfaces with LAN
same network part of IP
[Link] [Link]
address
– can physically reach
each other without
intervening router network consisting of 3 IP networks
(for IP addresses starting with 223,
first 24 bits are network address)

11
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP Addressing - 2
How to find the
networks? [Link] [Link]
[Link]

• Detach each [Link]

interface from
router, host [Link] [Link]

• create
“islands of
[Link] [Link]
isolated [Link] [Link]
networks [Link] [Link]

Interconnected [Link] [Link] [Link] [Link]

system consisting
of six networks
12
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP Addresses
given notion of “network”, let’s re-examine IP addresses:

“class-full” addressing:
class
[Link] to
A 0 network host [Link]

B network [Link] to
10 host
[Link]
[Link] to
C 110 network host
[Link]
[Link] to
D 1110 multicast address
[Link]

32 bits
13
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Some Special IP Addresses
• All-0s  This computer
• All-1s  All hosts on this net (limited
broadcast: don’t forward out of this net)
• All-0 host suffix  Network Address (‘0’
means ‘this’)
• All-1 host suffix  All hosts on the
destination net (directed broadcast).
• 127.*.*.*  Loopback through IP layer

14
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP addressing: CIDR - 1

• classful addressing:
– inefficient use of address space,
address space exhaustion
– e.g., class B net allocated enough
addresses for 65K hosts, even if only
2K hosts in that network

15
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP addressing: CIDR - 2
• CIDR: Classless InterDomain
Routing
– network portion of address of arbitrary
length
– address format: a.b.c.d/x, where x is #
bits in network portion of address

network host
part part
11001000 00010111 00010000 00000000
[Link]/23
16
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Subnet Addressing

– External routers need to store entries

only for the “network ID”
– Internal routers & hosts use subnet
mask to identify “subnet ID” and route
packets between “subnets” within the
“network”.
– Eg: Mask: [Link] => subnet ID =
8 bits with upto 62 hosts/subnet

17
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
Subnet Addressing (Continued)

– Route table lookup:

• IF ((Mask[i] & Destination Addr) = =
Destination[i])
Forward to NextHop[i]
– Subnet mask can end on any bit.
– Mask must have contiguous 1s followed
by contiguous zeros. Routers do not
support other types of masks.

18
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Route Table Lookup: Example
[Link] [Link] [Link]
[Link]
[Link] [Link]
[Link] [Link]
[Link] [Link]
[Link]

[Link] [Link] [Link]

Destination Mask Next Hop

[Link] [Link] [Link]
[Link] [Link] Deliver direct
[Link] [Link] Deliver direct
[Link] [Link] [Link]
19
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP addresses: how to get one?
Hosts (host portion):
• hard-coded by system admin in a file
• DHCP: Dynamic Host Configuration
Protocol: dynamically get address: “plug-and-
play”
– host broadcasts “DHCP discover” msg
– DHCP server responds with “DHCP offer” msg
– host requests IP address: “DHCP request”
msg
– DHCP server sends address: “DHCP ack” msg
20
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP addresses: how to get one?
Network (network portion):
• get allocated portion of ISP’s
address space:
ISP's block 11001000 00010111 00010000 00000000 [Link]/20

Organization 0 11001000 00010111 00010000 00000000 [Link]/23

Organization 1 11001000 00010111 00010010 00000000 [Link]/23

Organization 2 11001000 00010111 00010100 00000000 [Link]/23

... ….. …. ….

Organization 7 11001000 00010111 00011110 00000000 [Link]/23

21
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Hierarchical addressing:
route aggregation
Hierarchical addressing allows efficient advertisement of routing
information:

Organization 0
[Link]/23
Organization 1
“Send me anything
[Link]/23 with addresses
Organization 2 beginning
[Link]/23 . Fly-By-Night-ISP [Link]/20”
.
. . Internet
.
Organization 7 .
[Link]/23
“Send me anything
ISPs-R-Us
with addresses
beginning
[Link]/16”

22
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Hierarchical addressing:
more specific routes

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

Organization 0
[Link]/23

“Send me anything
with addresses
Organization 2 beginning
[Link]/23 . Fly-By-Night-ISP [Link]/20”
.
. . Internet
.
Organization 7 .
[Link]/23
“Send me anything
ISPs-R-Us
with addresses
Organization 1 beginning [Link]/16
or [Link]/23”
[Link]/23

23
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP addressing: the last word...

Q: How does an ISP get block of

addresses?
A: ICANN: Internet Corporation for Assigned
Names and Numbers
– allocates addresses
– manages DNS
– assigns domain names, resolves
disputes

24
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Getting a datagram
from source to dest. - 1
routing table in A
Dest. Net. next router Nhops
223.1.1 1
223.1.2 [Link] 2
IP datagram: 223.1.3 [Link] 2
misc source dest
data
fields IP addr IP addr A [Link]

datagram remains [Link]

[Link]
unchanged, as it travels
[Link] [Link]
source to destination
B
addr fields of interest here [Link]
[Link] [Link] E

[Link] [Link]

25
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Getting a datagram
from source to dest. - 2
misc Dest. Net. next router Nhops
data
fields [Link] [Link]
223.1.1 1
223.1.2 [Link] 2
Starting at A, given IP 223.1.3 [Link] 2
datagram addressed to B:
look up net. address of B A [Link]
find B is on same net. as A
link layer will send datagram [Link]
[Link]
directly to B inside link-layer
[Link] [Link]
frame
B
B and A are directly [Link]
[Link]
E
[Link]
connected
[Link] [Link]

26
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Getting a datagram
from source to dest. - 3
misc Dest. Net. next router Nhops
data
fields [Link] [Link]
223.1.1 1
223.1.2 [Link] 2
Starting at A, dest. E:
223.1.3 [Link] 2
look up network address of E
E on different network
A [Link]
A, E not directly
attached [Link]
[Link]
routing table: next hop router to [Link] [Link]
E is [Link] B
link layer sends datagram to [Link]
[Link] [Link] E
router [Link] inside link-layer
frame [Link] [Link]
datagram arrives at [Link]
continued…..
27
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Getting a datagram
from source to dest. – 4
Dest. next
misc network router Nhops interface
data
fields [Link] [Link]
223.1.1 - 1 [Link]
Arriving at 223.1.4, 223.1.2 - 1 [Link]
223.1.3 - 1 [Link]
destined for [Link]
look up network address of E
A [Link]
E on same network as router’s
interface [Link] [Link]
[Link]
router, E directly [Link] [Link]
attached B
[Link]
link layer sends datagram to [Link] [Link] E
[Link] inside link-layer frame
[Link] [Link]
via interface [Link]
datagram arrives at [Link]!!!
(hooray!)
28
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP Features
• Connectionless service
• Addressing
• Data forwarding
• Fragmentation and reassembly
• Supports variable size datagrams
• Best-effort delivery
• Provides only “Send” and “Delivery” services.
Error and control messages generated by
Internet Control Message Protocol (ICMP)

29
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 What IP does NOT provide

• End-to-end data reliability & flow

control (done by TCP or application
layer protocols)
• Sequencing of packets (like TCP)
• Error detection in payload (TCP, UDP
or other transport layers)
• Error reporting (ICMP)

30
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 What IP does NOT provide
(Continued)
• Setting up route tables (RIP, OSPF,
BGP etc)
• Connection setup (it is
connectionless)
• Address/Name resolution (ARP,
RARP, DNS)
• Configuration (BOOTP, DHCP)
• Multicast (IGMP, MBONE)

31
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 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 Internet
remaining hops live layer checksum
(decremented at
32 bit source IP address
each router)
32 bit destination IP address
upper layer protocol
to deliver payload to Options (if any) E.g. timestamp,
record route
data taken, pecify
(variable length, list of routers
typically a TCP to visit.
or UDP segment)

32
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 IP Fragmentation & Reassembly - 1
• network links have MTU
([Link] size) -
largest possible link-level
frame. fragmentation:
– different link types, in: one large datagram
different MTUs out: 3 smaller datagrams
• large IP datagram divided
(“fragmented”) within net
– one datagram becomes
reassembly
several datagrams
– “reassembled” only at
final destination
– IP header bits used to
identify, order related
fragments

33
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
IP Fragmentation and Reassembly - 2

length ID fragflag offset

=4000 =x =0 =0

One large datagram becomes

several smaller datagrams

length ID fragflag offset

=1500 =x =1 =0

length ID fragflag offset

=1500 =x =1 =1480

length ID fragflag offset

=1040 =x =0 =2960

34
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar
 Summary

• Internet architectural principles

• IP addressing and header
• Fragmentation/Reassembly, Path
MTU discovery

35
Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar