Transcript Part I: Introduction - Rensselaer Polytechnic Institute

ECSE-4670: Computer
Communication Networks (CCN)
Network Layer
Shivkumar Kalyanaraman: [email protected]
Biplab Sikdar: [email protected]
http://www.ecse.rpi.edu/Homepages/shivkuma
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
1
Chapter
Goals
• understand principles behind network
layer services:
– Internetworking concepts
– The network layer
– IP
– routing (path selection)
– how a router works
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
2
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?
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
3
The Internetworking Problem
• Two nodes communicating across a
“network of networks”…
– How to transport packets through
this heterogeneous mass ?
A
B
Cloud
Cloud
Cloud
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
4
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 endnodes and applications in this
interconnected network ?
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
5
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
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
6
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)
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
7
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
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
8
The Internet Network layer
Host, router network layer functions:
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
routing
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
9
IP Addressing: introduction
• IP address: 32-bit
identifier for host,
router interface
• interface: connection
between host, router
and physical link
– router’s typically have
multiple interfaces
– host may have
multiple interfaces
– IP addresses
associated with
interface, not host,
router
Rensselaer Polytechnic Institute
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
223.1.3.2
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223
© Shivkumar Kalvanaraman &
1
© Biplab Sikdar
1
1
10
IP Addressing - 1
• IP address:
– network part (high
order bits)
– host part (low order
bits)
• What’s a network ?
(from IP address
perspective)
– device interfaces with
same network part of
IP address
– can physically reach
each other without
intervening router
Rensselaer Polytechnic Institute
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
LAN
223.1.3.1
223.1.3.2
network consisting of 3 IP networks
(for IP addresses starting with 223,
first 24 bits are network address)
© Shivkumar Kalvanaraman &
© Biplab Sikdar
11
IP Addressing - 2
How to find the
networks?
• Detach each
interface from
router, host
• create
“islands of
isolated
networks
Interconnected
system consisting
of six networks
Rensselaer Polytechnic Institute
223.1.1.2
223.1.1.1
223.1.1.4
223.1.1.3
223.1.7.0
223.1.9.2
223.1.9.1
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
223.1.2.1
223.1.3.27
223.1.2.2 223.1.3.1
© Shivkumar Kalvanaraman &
© Biplab Sikdar
223.1.3.2
12
IP Addresses
given notion of “network”, let’s re-examine
IP addresses:
“class-full” addressing:
class
A
0 network
B
10
C
110
D
1110
1.0.0.0 to
127.255.255.255
host
network
128.0.0.0 to
191.255.255.255
host
network
host
multicast address
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
32 bits
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
13
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
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
14
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
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
15
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
part
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
16
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: 255.255.255.0 => subnet ID =
8 bits with upto 62 hosts/subnet
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
17
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.
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
18
Route Table Lookup: Example
30.0.0.7
30.0.0.0
40.0.0.8
40.0.0.0
40.0.0.7
128.1.0.9
128.1.0.0
128.1.0.8
192.4.0.0
192.4.10.9
Destination
Mask
Next Hop
30.0.0.0
255.0.0.0
40.0.0.7
40.0.0.0
255.0.0.0 Deliver direct
128.1.0.0 255.255.0.0 Deliver direct
192.4.10.0 255.255.255.0 128.1.0.9
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
19
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
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
20
IP addresses: how to get one?
Network (network portion):
• get allocated portion of ISP’s
address space:
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
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
21
Hierarchical addressing:
route aggregation
Hierarchical addressing allows efficient advertisement of routing
information:
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
Rensselaer Polytechnic Institute
“Send me anything
with addresses
beginning
199.31.0.0/16”
© Shivkumar Kalvanaraman &
© Biplab Sikdar
22
Hierarchical addressing:
more specific routes
ISPs-R-Us has a more specific route to Organization 1
Organization 0
200.23.16.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
Organization 1
200.23.18.0/23
Rensselaer Polytechnic Institute
“Send me anything
with addresses
beginning 199.31.0.0/16
or 200.23.18.0/23”
© Shivkumar Kalvanaraman &
© Biplab Sikdar
23
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
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
24
Getting a datagram
from source to dest. - 1
routing table in A
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
IP datagram:
misc source dest
fields IP addr IP addr
data
datagram remains
unchanged, as it travels
source to destination
addr fields of interest here
A
223.1.1.4
223.1.1.4
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.3.27
223.1.1.3
223.1.3.1
Rensselaer Polytechnic Institute
1
2
2
© Shivkumar Kalvanaraman &
© Biplab Sikdar
223.1.2.2
223.1.3.2
25
E
Getting a datagram
from source to dest. - 2
Dest. Net. next router Nhops
misc
data
fields 223.1.1.1 223.1.1.3
223.1.1
223.1.2
223.1.3
Starting at A, given IP
datagram addressed to B:
look up net. address of B
find B is on same net. as A
link layer will send datagram
directly to B inside link-layer
frame
B and A are directly
connected
A
223.1.1.4
223.1.1.4
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.3.27
223.1.1.3
223.1.3.1
Rensselaer Polytechnic Institute
1
2
2
© Shivkumar Kalvanaraman &
© Biplab Sikdar
223.1.2.2
223.1.3.2
26
E
Getting a datagram
from source to dest. - 3
Dest. Net. next router Nhops
misc
data
fields 223.1.1.1 223.1.2.2
223.1.1
223.1.2
223.1.3
Starting at A, dest. E:
look up network address of E
E on different network
A, E not directly
attached
223.1.1.1
223.1.2.1
routing table: next hop router to
E is 223.1.1.4
link layer sends datagram to
router 223.1.1.4 inside link-layer
frame
datagram arrives at 223.1.1.4
continued…..
Rensselaer Polytechnic Institute
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.3.27
223.1.1.3
223.1.3.1
© Shivkumar Kalvanaraman &
© Biplab Sikdar
223.1.2.2
223.1.3.2
27
E
Getting a datagram
from source to dest. – 4
misc
data
fields 223.1.1.1 223.1.2.2
Arriving at 223.1.4,
destined for 223.1.2.2
look up network address of E
E on same network as router’s
interface 223.1.2.9
router, E directly
attached
223.1.1
223.1.2
223.1.3
A
-
1
1
1
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
link layer sends datagram to
223.1.2.2 inside link-layer frame
via interface 223.1.2.9
datagram arrives at 223.1.2.2!!!
(hooray!)
Rensselaer Polytechnic Institute
Dest.
next
network router Nhops interface
223.1.3.27
223.1.1.3
223.1.3.1
© Shivkumar Kalvanaraman &
© Biplab Sikdar
223.1.2.2
223.1.3.2
28
E
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)
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
29
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)
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
30
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)
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
31
IP datagram format
IP protocol version
number
header length
(bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
32 bits
ver head. type of
len service
total datagram
length (bytes)
length
fragment
16-bit identifier flgs
offset
time to upper
Internet
layer
live
checksum
upper layer protocol
to deliver payload to
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
Rensselaer Polytechnic Institute
for
fragmentation/
reassembly
© Shivkumar Kalvanaraman &
E.g. timestamp,
record route
taken, pecify
list of routers
to visit.
© Biplab Sikdar
32
IP Fragmentation & Reassembly - 1
• network links have MTU
(max.transfer size) largest possible link-level
frame.
– different link types,
different MTUs
• large IP datagram divided
(“fragmented”) within net
– one datagram becomes
several datagrams
– “reassembled” only at
final destination
– IP header bits used to
identify, order related
fragments
Rensselaer Polytechnic Institute
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
© Shivkumar Kalvanaraman &
© Biplab Sikdar
33
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
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
34
Summary
• Internet architectural principles
• IP addressing and header
• Fragmentation/Reassembly, Path
MTU discovery
Rensselaer Polytechnic Institute
© Shivkumar Kalvanaraman &
© Biplab Sikdar
35