Transcript IP - Rudra Dutta

IP - Networking in the Internet
Rudra Dutta
CSC 401- Fall 2011, Section 001
Outline

Overview
–

Historical development
Addressing
–
Layer 3 addressing was an innovation of the Internet
– Addressing scheme has gone through changes
– Some basic principles remain - notably, flexibility

Forwarding
–
–

Routing
–

Much the same as the context-less packet-switching we have
discussed
Introduction of context later
Destination-only based, single next-hop, shortest path routing
Routing Mechanism
–
DV approach: Route Information Protocol (early)
– LSA approach: Open Shortest Path First (later)
– Sophisticated DV-like approach: Border Gateway Protocol
Copyright Rudra Dutta, NCSU, Fall 2011
2
Original Motivation

Interconnecting widely separated (physical)
networks, with possibly dissimilar DLC
 Fundamental characteristics:
–
–

Bandwidth is precious
Traffic is bursty
Many other goals/assumptions
–
BUT: flexibility built in
Copyright Rudra Dutta, NCSU, Fall 2011
3
Some Design Philosophies







KIS,S
Performance, efficiency, cost
Objects should not require context
Working solution in hand is worth more than
perfect solution in bush
Scalability
Modularity (of protocols)
Endpoint control
Copyright Rudra Dutta, NCSU, Fall 2011
4
Evolution of Architecture

Initially, an adaptation of the hierarchical structure of
POTS
–

But with flexibility in topology at each level
Number of levels also flexible
–
–
Core routing phase of the Internet
Core also called “backbone”
Copyright Rudra Dutta, NCSU, Fall 2011
5
It’s Who You Know

Know a smarter router!
–
If you are a host, know your local router
– If .. Local router, .. Site router
– If .. Site router, .. Core router
– If .. Core router, you have to know everything !

Ends up being an hierarchy - but loose in the Internet
Copyright Rudra Dutta, NCSU, Fall 2011
6
Evolution of Architecture

From one to multiple backbones (ISPs)
–

Exchange points connect backbones
CAIDA MAPNET Link
Copyright Rudra Dutta, NCSU, Fall 2011
7
Who Manages/Controls the Internet?

ISOC (Internet Society): non-profit organization
established to foster interest in the Internet
–
–

IAB (Internet Architecture Board)
–


originally set up by DoD to oversee ARPAnet
IETF: concentrates on short-, medium-term engineering
problems, develops standards
IESG: (committee consisting of IETF chair and area
managers)
–

organizes conferences (similar to ACM or IEEE)
hosts IANA (assigns numbers used in TCP/IP protocols)
coordinates IETF activities and approves standards
IRTF: concentrates on long-term research issues
Copyright Rudra Dutta, NCSU, Fall 2011
8
IETF




Small, focused efforts preferred to larger comprehensive ones
Published goals and milestones
No formal voting
Disputes resolved by discussion and demonstration (mostly)
–




“Rough consensus and running code” (D. Clark)
Mailing list and face-to-face meetings
Open, no-fee membership (compare: ATM Forum)
Standardization only after several implementations
Specifications, in text format, available without charge by FTP or
HTTP (compare: ITU, IEEE)
Copyright Rudra Dutta, NCSU, Fall 2011
9
RFCs, including Internet Standards




“Request for Comments”, since 1969
“A series of notes that contain surveys,
measurements, ideas, techniques, and observations,
as well as proposed and accepted TCP/IP protocol
standards” (Comer)
Many RFCs are not standards
Internet drafts: working documents, but often used for
prototypes
–

edited, but not refereed
RFCs numbered sequentially
–
Currently at:
RFC6415
Web Host Metadata E. Hammer-Lahav, Ed.,
B. Cook
October 2011 ASCII
PROPOSED
STANDARD
Copyright Rudra Dutta, NCSU, Fall 2011
10
IP Header

Various fields have different uses
Not all are used by core IP
–
Version
(4)
Hdr Len
(4)
TOS (8)
Identification (16 bits)
Time to Live (8)
Total Length in bytes (16)
Flags (3)
Protocol (8)
Fragment Offset (13)
Header Checksum (16)
Source IP Address
Destination IP Address
Options (if any)
PAD
Data Field
Copyright Rudra Dutta, NCSU, Fall 2011
11
Addressing
Design Principles (Names and Addresses)
No hardcoded addresses
2. Single naming structure
3. Addresses must be unambiguous
4. Upper-layer protocols must be able to identify endpoints unambiguously
5. Standardize on compact, binary addresses that make
computations (e.g., selection of a route) efficient
6. Name should be case-insensitive ASCII
1.
Copyright Rudra Dutta, NCSU, Fall 2011
13
Internet Addresses


32-bit addresses
Each Internet host has one globally unique IP
addresses that is used in all communication with that
host. But…
–
–
–

Two-level hierarchy (initially)  three-level (later)
–

the IP address may change (dial-in)
may have several addresses (routers  multi-homed hosts)
an IP address specifies an interface (network connection),
not a host!
2-level addressing: (network, host)
Class A, B, or C (initially)  Classless interdomain
routing (CIDR) (later)
–
aggregation, routing based on prefix and mask
Copyright Rudra Dutta, NCSU, Fall 2011
14
IP Address Classes
Class
First Byte
# Networks
Hosts per Network
Comments
A
< 128
27 (128)
224 –2 (16M)
Mostly used
B
128…191
214 (16384)
216 – 2 (65534)
Mostly used
C
192…223
221 (2M)
28 – 2 (254)
D
224…239
228 (268M)
-
Dynamic, multicast
E
240…255
227 (134M)
-
reserved
Copyright Rudra Dutta, NCSU, Fall 2011
15
Dotted decimal notation
Host Name
myhost.csc.ncsu.edu
32-bit address
1001 1000 0000 0001 0011 0110 0011 0000
Dotted decimal
152.1.54.48

Dotted decimal is just a different representation
of the 32-bit form - 1-to-1 mapping
 Names are very different - a “registry” system
(Domain Naming System)
Copyright Rudra Dutta, NCSU, Fall 2011
16
Address Space
0.0.0.0
255.255.255.255
Copyright Rudra Dutta, NCSU, Fall 2011
17
Contextless One-hop Forwarding



Roughly layer 3 functionality
Router-to-router, or between router and host
Contextless or connectionless paradigm
–
–

Each packet forwarded independently
Low overhead
Unreliable
–
–
Possible error, loss, reordering, duplication
Not necessarily bad
Copyright Rudra Dutta, NCSU, Fall 2011
18
Multihop - IP Forwarding


Routers look at destination IP address of
packet to make decisions
What do I do with this packet, based upon its
IP destination address only
B
B?
D?
Router A
D
Packet
Copyright Rudra Dutta, NCSU, Fall 2011
C?
C
19
IP Fragmentation

If IP packet is longer than the MTU, the router
breaks packet into smaller packets
–
–
Called IP fragments
Fragments are still IP packets

–
Only data, header is replicated
Router performs fragmentation
MTU
IP Packet
3
Fragmentation
Copyright Rudra Dutta, NCSU, Fall 2006
2
1
IP Packets
20
Multiple Fragmentations

Original packet may be fragmented multiple
times along its route
Source
Host
Internet
Process
Destination
Host
Internet
Process
Fragmentation
Copyright Rudra Dutta, NCSU, Fall 2006
21
Defragmentation


Internet layer process on destination host
defragments, restoring the original packet
IP Defragmentation only occurs once
Source
Host
Internet
Process
Destination
Host
Internet
Process
Defragmentation
Copyright Rudra Dutta, NCSU, Fall 2006
22
Fragmentation and IP Fields

More Fragments field (1 bit)
–
–
–
–
–

1 if more fragments
0 if not
Source host internet process sets to 0
If router fragments, sets More Fragments field in last fragment
to 0
In all other fragments, sets to 1
Don’t Fragment field (1 bit)
0
Original IP Packet
Copyright Rudra Dutta, NCSU, Fall 2006
0
1
1
Fragments
23
Router Forwarding Tables

Major duty
–

Provide “destination IP address”  “which router
to forward to” mapping
Index into table by network part of destination
IP
Network/Subnet
Delivery
128.171.17.
Local
142.99.
Next-Hop Router A
Copyright Rudra Dutta, NCSU, Fall 2011
24
FIB Explosion / Address Waste

Each FIB entry is towards a “block
of addresses”
–
–
–
–


Naturally maps to the network of an
organization
But blocks of only a few sizes –
indicated by Class
Either waste IP addresses, or increase
FIB entries
FIB entries proliferate anyway
Different routers need have
different levels of forwarding
knowledge
Must be able to specify size of
block, individually at each FIB
Copyright Rudra Dutta, NCSU, Fall 2011
25
Router Forwarding Tables

Enable “size of block” by including a “mask”
column
–
–
–

Provide mask with each table entry
No decision points
Automatic implementation of masking by bit-AND
Destination ID and Mask are both 32-bit
numbers in the actual table
Net/Subnet
Mask
Destination
128.171.17.0 24
Local
142.0.0.0
Next-Hop
Router A
Copyright Rudra Dutta, NCSU, Fall 2011
8
26
Router Forwarding Tables

Example
–
–
–
Destination IP Address is
128.171.17.13
Mask is 24, so only look at
128.171.17.0
Matches row’s network/subnet bits,
so use Local (direct) delivery
Net/Subnet
Mask
Destination
128.171.17.0 24
Local
142.0.0.0
Next-Hop
Router A
Copyright Rudra Dutta, NCSU, Fall 2011
8
27
Default routes – “Everywhere else”

Strictly speaking, need next hop
information for every network in the
Internet
–

Instead, keep detailed routes only for
local neighborhood
–
–

Even with size of block, very large number
of entries
For unknown destinations, use a default
router
Reduces size of routing tables, potentially
drastically
But “everywhere else” may not be a
nice block
–
Can handle elegantly, by including: “more
specific rule wins”
Copyright Rudra Dutta, NCSU, Fall 2011
28
Forwarding Table Selection Rules

Compare destination IP address of an arriving packet
against ALL rows within the router forwarding table
because there may be multiple matches

Select a single row that matches

If multiple rows match, select the longest match

If multiple rows tie on the longest match, select the
row with the largest or smallest metric, depending on
the specific metric

(If there is no match, select the default row)
–
Syntactic solution - always include 0.0.0.0 as a net / mask
Copyright Rudra Dutta, NCSU, Fall 2011
29
Example
Line
Destination Address Netmask Metric (Cost)
Interface Next-Hop Router
1
2
3
4
5
6
7
8
9
10
11
12
152.19.0.0
152.15.33.0
152.1.0.0
152.40.0.0
152.229.0.0
152.40.6.0
152.19.17.0
152.229.0.0
152.40.8.0
152.15.12.0
152.15.122.0
0.0.0.0
2
1
2
2
1
3
4
3
1
2
3
3





16
24
16
16
16
24
24
16
24
24
24
0
47
0
12
33
34
47
55
20
23
9
3
5
B
Local
B
B
D
E
H
E
D
Local
Local
H
Default router?
152.1.1.211 – which router/rule?
152.15.12.99 ?
152.40.8.44 ?
125.1.2.3 ?
Copyright Rudra Dutta, NCSU, Fall 2011
30
Classless InterDomain Routing (CIDR)

Basic idea: allocate multiple IP addresses in a
way that results in a smaller number of routing
table entries
–

A block of contiguous addresses is collapsed, or
summarized, into a single logical network
–

IP addresses must share the same high-order bits
Thus facilitates route aggregation
Such networks are also units of routing
Copyright Rudra Dutta, NCSU, Fall 2011
31
Route Aggregation Example

If networks are contiguous, one starts where the
last one left off
–
–
2n of them can be aggregated
Must be “aligned”
192.15.00010000.00000000
192.15.32.0
255.255.255.0
192.15.00010001.00000000
192.15.33.0
255.255.255.0
192.15.00010010.00000000
192.15.34.0
255.255.255.0
192.15.00010011.00000000
192.15.35.0
255.255.255.0
192.15.32.0
Copyright Rudra Dutta, NCSU, Fall 2011
R
R
R
R
255.255.252.0 R
192.15.32.0
192.15.32.1
192.15.32.2
.
.
.
192.15.32.254
192.15.32.255
32
CIDR Example

Block of 131,072 Class C networks (32M total
addresses), starting at 194.0.0.0
Address
Dotted Decimal
Binary
Lowest
194.0.0.0
11000010 00000000 00000000 00000000
Highest
195.255.255.255
11000011 11111111 11111111 11111111
Mask
254.0.0.0
11111110 00000000 00000000 00000000
CIDR address block “alignment”
Start of a 2n-block must be aligned to a 2n boundary
That is, starting address must be multiple of 2n
Consequence of using masking as the enabling mechanism
Copyright Rudra Dutta, NCSU, Fall 2011
33
Allocation of Class C Address Space
Lowest
194.0.0.0
198.0.0.0
200.0.0.0
202.0.0.0
204.0.0.0


Allocation
Europe
North America
Central and South America
Asia and the Pacific
Reserved
All sites in Europe have a common prefix
CIDR summarizes 32M addresses into one entry
–

Highest
195.255.255.255
199.255.255.255
201.255.255.255
203.255.255.255
223.255.255.255
only a single entry needed in most U.S. routers
Once the packet gets to Europe, more detailed routing tables
are needed
Copyright Rudra Dutta, NCSU, Fall 2011
34
CIDR Example

Three sites in Europe ask for 2048, 1024, and
4096 addresses, respectively
Site
Lowest
Highest
Mask
“Count”
1
194.24.0.0
194.24.7.255
255.255.248.0
2048 = 211
2
194.24.8.0
194.24.11.255
255.255.252.0
1024 = 210
3
194.24.16.0
194.24.31.255
255.255.240.0
4096 = 212
Copyright Rudra Dutta, NCSU, Fall 2011
35
CIDR Example (cont'd)

Routers all over Europe are now updated with
three entries:
Network Address
Mask
Next
Hop
11000010 00011000 00000000 00000000
11111111 11111111 11111000 00000000
R1
11000010 00011000 00001000 00000000
11111111 11111111 11111100 00000000
R2
11000010 00011000 00010000 00000000
11111111 11111111 11110000 00000000
R3
Copyright Rudra Dutta, NCSU, Fall 2011
36
CIDR Example (cont'd)




Network Address
Mask
Next
Hop
11000010 00011000 00000000 00000000
11111111 11111111 11111000 00000000
R1
11000010 00011000 00001000 00000000
11111111 11111111 11111100 00000000
R2
11000010 00011000 00010000 00000000
11111111 11111111 11110000 00000000
R3
Packet comes in addressed to 194.24.17.4:
11000010 00011000 00010001 00000100
Boolean ANDed with Site 1 mask =
11000010 00011000 00010000 00000000
–


Boolean ANDed with Site 2 mask =
11000010 00011000 00010000 00000000
–


does not match Site 1 base address
does not match Site 2 base address
Boolean ANDed with Site 3 mask =
11000010 00011000 00010000 00000000
–
matches Site 3 base address  sent to R3
Copyright Rudra Dutta, NCSU, Fall 2011
37
Introduction of Context in Forwarding

Original motivation - router efficiency
–

Labels - short local identifiers that a router could cache,
and look up easily
–
–

–

In short, VC or context identifier
Post-dates ATM developments
Header space needed
–

Routers could not keep up with forwarding
Reuse unused header space in IP, or create new header
Latter choice - provides more flexibility
Later, recognized as Traffic Engineering possibility
(Generalized) Multi-Protocol Label Switching
–
Coupled with suite of signaling protocols to distribute labels, etc.
Copyright Rudra Dutta, NCSU, Fall 2011
38
Address Resolution
Address Resolution Problem

Higher-level applications should work only with
IP addresses
–
–
illusion of a single, virtual network
Communication is carried out by physical networks

IP datagrams are encapsulated in MAC frames
 MAC (hardware) addresses are needed
 Address resolution problem: mapping highlevel (IP) addresses to physical (MAC)
addresses
–
“Last net” problem
Copyright Rudra Dutta, NCSU, Fall 2011
40
Solutions
1.
Direct mapping: function f maps IP addresses
to hardware addresses
–
–
2.
Configuration file provides the mapping
–
–
3.
computation of f must be efficient
works well when physical addresses are small and
configurable
not scalable
not easy to update
Dynamic binding: ARP (RFC 826)
–
–
for broadcast networks such as Ethernet, Token
Ring, etc.
(why not just broadcast all packets?)
Copyright Rudra Dutta, NCSU, Fall 2011
41
ARP vs. RARP
Copyright Rudra Dutta, NCSU, Fall 2011
42
ARP Operation
Copyright Rudra Dutta, NCSU, Fall 2011
43
Using ARP: Case 1
Copyright Rudra Dutta, NCSU, Fall 2011
44
Using ARP: Case 2
Copyright Rudra Dutta, NCSU, Fall 2011
45
ARP Cache

Sending n packets to destination x: n ARP
Requests?
–
–
–

Inefficient; one ARP Request per data packet!
Better: cache ARP Replies
Also, upon receipt of an ARP Request, all machines
update their cache entry for the sender of the request
Problems with caching
–
–
–
cache space may be limited
hosts move or change IP addresses
solution: drop (invalidate) cache entries after “a
while” (20 minutes)
Copyright Rudra Dutta, NCSU, Fall 2011
46
Diskless workstations (Web PCs):

Small startup program in ROM
–
–

startup program cannot contain machine's IP address
(why not?)
Startup program is used to obtain:
–
–
–
machine's IP address
IP address of file server and of nearest router
initial boot image to execute
Copyright Rudra Dutta, NCSU, Fall 2011
47
Reverse ARP
Copyright Rudra Dutta, NCSU, Fall 2011
48
RARP

One or more RARP servers store IP addresses for hosts on their
network
–

Link level protocol – only local (physical) network
A diskless client uses physical network addressing to obtain its
IP address from the server(s)
–
RARP Request is broadcast
– RARP uses the same message format as ARP, except

Ethernet frame type= 0x8035
 Op field = 3 for RARP request, 4 for RARP reply

Client repeats request if no reply is received
–
how many times?
– how much delay (time-out) between retransmissions?

BOOTP (RFC 951) extends to larger network
–
Works over UDP
– Also supplies boot image
Copyright Rudra Dutta, NCSU, Fall 2011
49
Dynamic Configuration

RARP, BOOTP designed for a relatively static
environment
–
–
manual configuration appropriate
cannot dynamically assign values to individual
machines

One problem: mobile clients
 Another problem: need to reuse pool of IP
addresses
–
–
IP address pool may be small, pool of potential
clients may be large (e.g., dialup)
automated mechanism needed
Copyright Rudra Dutta, NCSU, Fall 2011
50
DHCP (RFC 2131)

Extends BOOTP to handle dynamic address assignment
–
–

“leases” an address for a limited time (1 sec to 100 years)
Backwards compatible with BOOTP clients, message format is
the same
The DHCP server
–
Is given a set of addresses to manage

–
–
–
management algorithm is not standardized
leases addresses to clients (for how long?)
informs client of lease period, during which it will not lease same
address to another client
at end of the lease period, the client must either renew or stop
using the address
Copyright Rudra Dutta, NCSU, Fall 2011
51
ICMP (RFC 792)

Special purpose message mechanism
–

Error reporting only
–
–

used to communicate network-level errors or
information about unexpected circumstances
does not fully specify the action to be taken for
each error
IP/TCP/UDP entities or user processes must then
take action
Encapsulated within IP datagrams (i.e., not
part of IP)
–
But required part of IP implementation
Copyright Rudra Dutta, NCSU, Spring, 2003
52
Error – Destination Unreachable Message

IP is best-effort delivery, but discarding
datagrams should not be taken lightly
–

Upon failure to forward/deliver, router sends ICMP
message to source before dropping datagram
Several reasons for failure
–
Network, host, protocol or port unreachable
– Fragmentation needed and DF-flag set
– Source route failed
– others

But not all errors can be detected
–
powered down destination on Ethernet?
Copyright Rudra Dutta, NCSU, Spring, 2003
53
Echo Request/Reply Messages

PING (Packet InterNet Groper) program
 Checks if host is reachable, alive
–
–
first check for “reachability”
However, even if you can’t ping a host, it might be
reachable (i.e., ping is disabled on that host but other
services are not)

Ping client = user process, server = in kernel
 Step 1: client sends ICMP echo request
 Step 2: server sends ICMP echo reply
–
The data sent in the echo request must be returned
in the echo reply
Copyright Rudra Dutta, NCSU, Spring, 2003
54
PING

Sequence number starts at 0 and is
incremented by each successive request
–

Can tell if replies are missing, duplicated, or
reordered
Round-trip time calculated
–
Client puts sending time into request, subtracts
from receiving time when reply comes back

Record-route option inviting routers to record
their IDs
 But, route length severely limited
Copyright Rudra Dutta, NCSU, Spring, 2003
55
Error – Time Exceeded Message
Version
(4)
Hdr Len
(4)
TOS (8)
Identification (16 bits)
Time to Live (8)
Total Length in bytes (16)
Flags (3)
Protocol (8)
Fragment Offset (13)
Header Checksum (16)
Source IP Address
Destination IP Address
Options (if any)
PAD
Data Field
Routers decrease “Time To Live” when forwarding
 Sent when datagram is discarded because

–
–
The hop count (TTL) has reached zero (code 0), or
Timed out while waiting for fragments to arrive (code 1)
Copyright Rudra Dutta, NCSU, Spring, 2003
56
Traceroute Program

Another approach to find path taken by the packet
–

why not use IP record route option?
Send UDP datagram with TTL=1
–
–
first router decrements TTL, notices it is 0, sends ICMP “time
exceeded” error message back to sender
this error message has IP address of the router generating
the error – now we know the first hop!


Now send UDP datagram with TTL=2
–

uses the IP address of the interface on which the UDP
datagram arrives
second router sends back “time exceeded” message, with its
IP address
Etc.
Copyright Rudra Dutta, NCSU, Spring, 2003
57
Traceroute (cont’d)

How get a response from the destination?
–
the UDP datagram is addressed to an “unlikely”
port (>30,000)

–
or to a sequence of such unlikely ports
error message sent by destination is “port
unreachable” ICMP error message rather than
“time exceeded”

Sender calculates round-trip time
 Sender sets source port number to XOR of its
process number with 32768
–
allows replies to be matched to sending process
Copyright Rudra Dutta, NCSU, Spring, 2003
58
IP Version 6 Goals
•
Support billions of hosts
•
Reduce routing table size
• Simplify protocol
• Better security
• Attention to type of service
• Aid multicasting
• Roaming host without changing address
• Allow future protocol evolution
•
Permit coexistence of old, new protocols. . .
IP Version 6 (1)

One fixed, simpler
header
 Optional extension
headers
–

Mostly of fixed
length, and E2E
only
Fragmentation is
limited to ends
 Different address
types
IP Version 6 (2)
IPv6 extension headers
IP Version 6 (3)
The hop-by-hop extension header for
large datagrams (jumbograms).
IP Version 6 (4)
The extension header for routing.
Tunneling IPv6 in IPv4
Tunneling a car from France to England
Summary

Internet - a flexible suite of protocols
–

Originally designed to interconnect unlike LANs
IP - Forwarding layer in the Internet
–
Basic contextless switching

Addressing schemes - original and later
 Automatic address resolution with lower layer
 Introduction of context - label switching, later in
IPv6
Copyright Rudra Dutta, NCSU, Fall 2011
65