Transcript 10-NL-IPv4
Datagram Networks:
Internet Protocol (IPv4)
1
The Internet Network layer: IP
• Internet Network Layer Components:
– IP protocol (addressing, datagram format and
handling), Routing Protocols and ICMP protocol
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
forwarding
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
2
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 each
interface
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
1
1
1
3
IP Addressing
• IP address:
– network part (high order
bits)
– host part (low order bits)
– NetworkID.HostID
• What’s an IP network ?
– device interfaces with
same network part of IP
address
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.3.1
– Hosts within the same IP
network can reach each
other without intervening
router
223.1.2.9
223.1.3.27
223.1.2.2
223.1.3.2
network consisting of 3 IP networks:
223.1.1.0, 223.1.2.0, 223.1.3.0
4
IP Addressing
• IP networks are not
restricted to
Ethernet segments
223.1.1.2
223.1.1.1
223.1.1.4
223.1.1.3
– Here we have 3 pointto-point links and each
have a different IP
network defined over
them.
223.1.9.2
223.1.7.0
223.1.9.1
223.1.7.1
223.1.8.1
Interconnected
system consisting
of 6 IP networks
223.1.8.0
223.1.2.6
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
5
IP Addressing
•
223.1.1.2
How to find IP
networks?
223.1.1.1
1. Detach each
interface from
router, host
2. Create “islands of
isolated IP
networks
3. Each island defines
an IP network
4. Internet consists
of millions of such
IP networks
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.2.1
Interconnected
system consisting
of 6 IP networks
223.1.1.4
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
6
IP Addresses
• given notion of “IP network”, let’s re-examine IP
addresses:
– We have “class-full” addressing
– Original Internet design
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
multicast address
host
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
32 bits
7
IP addressing: CIDR
• 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
– No longer used in the current Internet
• Solution? Classless Inter Domain Routing (CIDR)
• CIDR: Classless InterDomain Routing
– Standardized in 1993
– 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
8
Netmask
• With CIDR a new way is needed to determine
the IP network given an IP address:
– Solution: Define a netmask
– Given an IP address of the form networkID.hostID, the netmask
of the IP address is obtained by putting all “1”s in the networkID
portion and all “0”s in the hostID portion
network
part
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
11111111 11111111 11111110 00000000 = 255.255.254.0
Given an IPAddr and a netmask, we bit-wise AND IPAddr and
netmask to obtain the IP network. The rest is the hostID.
NetworkID = IPAddr & Netmask
HostID = IPAddr & ~Netmask
9
IP Layer Broadcast
• Recall that a host can send a LL
broadcast message by putting FF-FF-FFFF-FF-FF in destination MAC address
• How can a host send IP-layer broadcast
packet? 2 ways:
– Put 255.255.255.255 in destination IP
• Means that all IP hosts within the same LL broadcast
domain will receive this IP datagram
– Make <hostID> all 1’s
• Means that all hosts within the same IP subnet will receive
this datagram
• Example: If IP subnet is 192.169.34.0, then a packet with a
destination IP: 192.169.34.255 will be received by all hosts
whose IP subnet is 192.169.34.0
10
IP addresses: how to get one?
Q: How does a host get an IP address?
– hard-coded by system admin in a file
• Wintel: control-panel->network->configuration>tcp/ip->properties
• UNIX: /etc/rc.config
– DHCP: Dynamic Host Configuration Protocol:
dynamically get address from as server
• “plug-and-play” (more shortly)
11
IP addresses: how to get one?
Q: How does network get network part of IP
addr?
A: gets allocated portion of its provider ISP’s
address space
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
Organization 1
Organization 2
...
11001000 00010111 00010000 00000000
11001000 00010111 00010010 00000000
11001000 00010111 00010100 00000000
…..
….
200.23.16.0/23
200.23.18.0/23
200.23.20.0/23
….
Organization 7
11001000 00010111 00011110 00000000
200.23.30.0/23
12
Hierarchical addressing: route aggregation
• CIDRized addresses facilitate hierarchical routing
• Fly-By-Night-ISP advertises that any IP datagram whose addresses
begin with 200.23.16.0/20 should be sent to it. The rest of the world
need not that there are 8 other organizations each with its own IP
network. This is called route aggregation
• Dividing an IP network into smaller IP networks as done in here is
called subnetting. Each organization can further divide their IP
address range into smaller IP subnets
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
“Send me anything
with addresses
beginning
199.31.0.0/16”
13
Hierarchical addressing: more specific
routes
ISPs-R-Us has a more specific route to Organization 1. By the longest
prefix matching rule, packets with destination addresses beginning with
200.23.18.0/23 are sent to ISPs-R-Us
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
“Send me anything
with addresses
beginning 199.31.0.0/16
or 200.23.18.0/23”
14
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 root servers
– assigns domain names, resolves disputes
15
IP datagram format
IP protocol version
number
header length
(bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
upper layer protocol
to deliver payload to
how much overhead
with TCP?
• 20 bytes of TCP
• 20 bytes of IP
• = 40 bytes + app
layer overhead
32 bits
head. type of
length
ver
len service
fragment
16-bit identifier flgs
offset
upper
time to
Header
layer
live
checksum
total datagram
length (bytes)
for
fragmentation/
reassembly
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
E.g. timestamp,
record route
taken, specify
list of routers
to visit.
16
Forwarding: Getting a datagram from
source to dest.
forwarding table in A
Dest. Net. Next Hop 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
from source to destination
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
223.1.3.2
17
E
Forwarding: Getting a datagram from
source to dest.
forwarding table in A
misc
data
fields 223.1.1.1 223.1.1.3
Starting at A, send IP
datagram addressed to
B:
• look up network address of B
in forwarding table
• find B is on same net. as A
• B and A are directly
connected
– link layer will send datagram
directly to B inside link-layer
frame. How?
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
223.1.3.2
18
E
Delivering the packet from A to B
A
• Starting at A, given IP
datagram addressed to B:
223.1.2.1
– look up net. address of B, find
B on same net. as A
– link layer send datagram to B
inside link-layer frame
– How does A know the MAC
address of B? ARP protocol
frame source,
dest address
B’s MAC A’s MAC
addr
addr
223.1.1.1
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.27
223.1.3.1
223.1.3.2
datagram source,
dest address
A’s IP
addr
B’s IP
addr
IP payload
datagram
frame
19
E
ARP: Address Resolution Protocol
Question: how to determine
MAC address of B
given B’s IP address?
• Each IP node (Host,
Router) on LAN has
ARP module, table
• ARP Table: IP/MAC
address mappings for
some LAN nodes
< IP address; MAC address; TTL>
<
………………………….. >
– TTL (Time To Live): time
after which address
mapping will be forgotten
(typically 20 min)
20
ARP protocol
• A knows B's IP address, wants to learn
MAC address of B
• A broadcasts ARP query pkt, containing B's
IP address
– all machines on LAN receive ARP query
• B receives ARP packet, replies to A with its
(B's) MAC address
• A caches (saves) IP-to-MAC address pairs
until information becomes old (times out)
– soft state: information that times out
(goes away) unless refreshed
21
Forwarding: Getting a datagram from
source to dest.
forwarding table in A
misc
data
fields 223.1.1.1 223.1.2.3
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
Starting at A, dest. E:
• look up network address of E
in forwarding table
• E on different network
– A, E not directly attached
• routing table: next hop
router to E is 223.1.1.4
• link layer sends datagram to
router 223.1.1.4 inside linklayer frame
• datagram arrives at 223.1.1.4
• continued…..
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
223.1.3.2
22
E
Forwarding: Getting a datagram from
source to dest.
misc
data
fields 223.1.1.1 223.1.2.3
Arriving at 223.1.4,
destined for 223.1.2.2
• look up network address of E
in router’s forwarding table
• E on same network as router’s
interface 223.1.2.9
– router, E directly attached
• 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
forwarding table in router
Dest. Net router Nhops interface
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
B
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
223.1.3.2
23
E
Another IP Packet Forwarding Example
– A creates IP packet with source A, destination E
– A uses ARP to get R’s MAC address for 111.111.111.110
– A creates Ethernet frame with R's MAC as dest, Ethernet
frame contains A-to-E IP datagram
– A’s data link layer sends Ethernet frame to R
– R’s data link layer receives Ethernet frame
– R removes IP datagram from Ethernet frame, sees its destined
to E
– R uses ARP to get E’s MAC address
– R creates frame containing A-to-E IP datagram sends to E
A
R
E
24
IP packet forwarding algorithm
D = destination IP address
Bool found = false;
For each forwarding table entry (SubnetNumber, SubnetMask, NextHop) do {
D1 = SubnetMask & D;
if (D1 == SubnetNumber) {
if (NextHop is an Interface) {
Deliver the datagram directly to the destination within a LL frame
} else {
Deliver the datagram to NextHop (a router)
} //end-else
found = true;
break;
} //end-if
} //end-for
If (!found) {
if (there is a <default> router) Deliver the datagram to the <default> router
else “Report: Destination unreachable”
} //end-if
25
IP packet forwarding: Example
Subnet Number
SubnetMask
NextHop
128.96.34.0
255.255.255.128
Interface0
128.96.34.128
128.96.33.0
255.255.255.128
255.255.255.0
Interface1
R2
<default>
R3
• Assume Destination IP = 128.96.34.68
– D1 = 128.96.34.68 & 255.255.255.128 = 128.96.34.0 Deliver the datagram to
the destination over Interface0
• Assume Destination IP = 128.96.34.150
– D1 = 128.96.34.150 & 255.255.255.128 = 128.96.34.128 Deliver datagram to
the destination over Interface1
• Assume Destination IP = 128.96.35.44
– IP subnet will not match any of the known IP subnetsDeliver the
packet to the <default> router, R3
26
IP Fragmentation & Reassembly
•
•
network links have MTU
(max.transfer unit) - 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
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
27
IP Fragmentation & Reassembly
Example
• 4000 byte datagram
– 3980 byte payload
• MTU = 1500 bytes
– 1st packet payload:
1480 bytes
– 2nd packet payload:
1480 bytes
– 3rd packet payload:
1020 bytes
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
28
ICMP: Internet Control Message Protocol
•
Used by hosts, routers, gateways
to communication network-level
information
– error reporting: unreachable
host, network, port, protocol
– echo request/reply (used by
ping)
•
ICMP runs over IP:
– ICMP msgs carried in IP
datagrams
•
ICMP message: type, code plus
first 8 bytes of IP datagram
causing error
Type
0
3
3
3
3
3
3
4
Code
0
0
1
2
3
6
7
0
8
9
10
11
12
0
0
0
0
0
description
echo reply (ping)
dest. network unreachable
dest host unreachable
dest protocol unreachable
dest port unreachable
dest network unknown
dest host unknown
source quench (congestion
control - not used)
echo request (ping)
route advertisement
router discovery
TTL expired
bad IP header
29
Host IP Address Configuration
Q: How does a host get an IP address?
– hard-coded by system admin in a file
• Wintel: control-panel->network->configuration>tcp/ip->properties
• UNIX: /etc/rc.config
– DHCP: Dynamic Host Configuration Protocol:
dynamically get address from as server
• “plug-and-play” (more shortly)
30
DHCP: Dynamic Host Configuration Protocol
Goal: allow host to dynamically obtain its IP address
from network server when it joins network
Can renew its lease on address in use
Allows reuse of addresses (only hold address while connected
an “on”
Support for mobile users who want to join network (more
shortly)
DHCP overview:
– 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
31
DHCP client-server scenario
A
B
223.1.2.1
DHCP
server
223.1.1.1
223.1.1.2
223.1.1.4
223.1.2.9
223.1.2.2
223.1.1.3
223.1.3.1
223.1.3.27
223.1.3.2
E
arriving DHCP
client needs
address in this
network
32
DHCP client-server scenario
DHCP server: 223.1.2.5
DHCP discover
arriving
client
src : 0.0.0.0, 68
dest.: 255.255.255.255,67
yiaddr: 0.0.0.0
transaction ID: 654
DHCP offer
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 654
Lifetime: 3600 secs
DHCP request
time
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
yiaddrr: 223.1.2.4
transaction ID: 655
Lifetime: 3600 secs
DHCP ACK
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 655
Lifetime: 3600 secs
33
NAT: Network Address Translation
rest of
Internet
local network
(e.g., home network)
10.0.0/24
10.0.0.4
10.0.0.1
10.0.0.2
138.76.29.7
10.0.0.3
All datagrams leaving local
network have same single source
NAT IP address: 138.76.29.7,
different source port numbers
Datagrams with source or
destination in this network
have 10.0.0/24 address for
source, destination (as usual)
34
NAT: Network Address Translation
• Motivation: local network uses just one IP address as
far as outside word is concerned:
– no need to be allocated range of addresses from ISP:
- just one IP address is used for all devices
– can change addresses of devices in local network
without notifying outside world
– can change ISP without changing addresses of
devices in local network
– devices inside local net not explicitly addressable,
visible by outside world (a security plus).
35
NAT: Network Address Translation
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
2
NAT translation table
WAN side addr
LAN side addr
1: host 10.0.0.1
sends datagram to
128.119.40, 80
138.76.29.7, 5001 10.0.0.1, 3345
……
……
S: 10.0.0.1, 3345
D: 128.119.40.186, 80
S: 138.76.29.7, 5001
D: 128.119.40.186, 80
138.76.29.7
S: 128.119.40.186, 80
D: 138.76.29.7, 5001
3: Reply arrives
dest. address:
138.76.29.7, 5001
3
1
10.0.0.4
S: 128.119.40.186, 80
D: 10.0.0.1, 3345
10.0.0.1
10.0.0.2
4
10.0.0.3
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 10.0.0.1, 3345
36
NAT: Network Address Translation
Implementation: NAT router must:
– outgoing datagrams: replace (source IP address, port #) of
every outgoing datagram to (NAT IP address, new port #)
. . . remote clients/servers will respond using (NAT IP
address, new port #) as destination addr.
– remember (in NAT translation table) every (source IP
address, port #) to (NAT IP address, new port #) translation
pair
– incoming datagrams: replace (NAT IP address, new port #) in
dest fields of every incoming datagram with corresponding
(source IP address, port #) stored in NAT table
37
NAT: Network Address Translation
• 16-bit port-number field:
– ~60,000 simultaneous connections with a single
LAN-side address!
• NAT is controversial:
– routers should only process up to layer 3
– violates end-to-end argument
• NAT possibility must be taken into account by app
designers, eg, P2P applications
– What about embedded IP addresses?
• FTP, SMTP, SIP etc.
– address shortage should instead be solved by IPv6
38