Transcript First note set for IP

IP
Internet Protocol
 Address Resolution Protocol (ARP)
 Reverse Address Resolution Protocol
(RARP)
 Internet Control Message Protocol
(ICMP)

Internet Protocol
• What role does IP play?
• IP packet header
• IP routing
• Subnet addressing and masks
• Special case of IP addresses
What can IP do?
• End-to-end connectivity over a network
• Connectionless: no state maintained about
successive packets (flows)
• Unreliable: packets may get lost or thrown
away, or received out of order
• Best effort service, ``I will do my best, but
nothing is guaranteed”
IP: Packet Header
Payload
IP: Packet Header
Header
•
•
•
•
Payload
Source address
Destination address
Version: Currently IPV4, also IPV6
Header Length: # of 32 bit words in the
header
• Total Length (16 bit number): in bytes
Max packet size = 65535 bytes
IP: Packet Header
• 8-bit Type of Service (TOS)
• 3-bit precedence field & D,T,R
• TOS bits:
• Minimize delay
• Maximize throughput
• Maximize reliability
• Minimize monetary cost
• Unused bit set to 0
IP: Packet Header
• 8-bit Time to Live (TTL): It’s decremented
every time the packet is forwarded
• 16-bit Checksum: Error detection for
the header only. 16-bit ones complement
• 8-bit Protocol Field: identifies the protocol
that the IP packet is servicing (TCP,
UDP, ICMP,...)
IP: Packet Header
• 16-bit Identification: Normally increments
by one each time a datagram is sent
• 13-bit fragmentation offset in 64-bit chunks
• 3-bits of flags
• Don’t Fragment (DF)
• More Fragments (MF)
• Unused = 0
IP: Packet Header
• Options
– Security and handling restrictions
– Record route (have each router record
its IP address)
– Time stamp (have each router record
its IP address and time)
– Loose source routing
– Strict source routing
– Padding is zeros
IP Routing
Packet
• Is it for me?
• Forward according
to routing table
Host/Route
Interfaces
Ethernet
Routing Table Entry
• Dest IP address
• IP address of next-hop router
• Flags
• Interface to pass packet to
IP Routing
Actions taken for routing
• Search routing table for an entry that exactly
matches the complete destination IP address.
If found then forward accordingly
• Default: send according to default entry
IP Routing: Addressing
Address hierarchy
net id
host id
Class A, B, C.
net id
subnet id
host id
IP address
Special IP address
Subnet
A campus network consisting of LANs for various departments
IP Routing: Addressing
Hierarchy
Net
Net
Subnet Subnet Subnet
Subnet Subnet Subnet
IP Routing: Addressing
Post Office Routing Table
Destination Address
USA 96822 1234 Dole Street
USA 96822 4567 E-W Center Rd
USA 96822 8901 Univ. Ave
USA 96817 xxx
USA 12485 xxx
JPN xxx
GBR xxx
Next PO
A
A
A
D
G
H
N
IP Routing: Addressing
Routing Table Look Up
• Find an exact, complete match of IP dest addr
• If unsuccessful then find a match of subnet id
• If unsuccessful then find a match of net id
• Go to default
[root@localhost jsac2]# route
Kernel IP routing table
Destination
Gateway
Genmask
Flags Metric Ref Use Iface
128.172.167.0 *
255.255.255.0
U
0
0
0 eth0
169.254.0.0
*
255.255.0.0
U
0
0
0 eth0
127.0.0.0
*
255.0.0.0
U
0
0
0 lo
UG
0
0
0 eth0
default
oli1-gw.cns.vcu 0.0.0.0
IP Routing: Masks
Subnet id entry in Routing Table
net id, subnet id
mask
net id
subnet id 00000000
1111111111111111111111100000000
Finding a match
IP dest addr
Bit-wise AND
=?
Mask
Yes, then
a match
IP Routing: Masks
Net id entry in Routing Table
net id
Finding a match
Compare net id in table with net id of IP dest addr
of packet
IP: Special Case IP
Addresses
netid subnetid hostid
Description
0
0
Host on this net
0
hostid
Specify host on this net
127
anything
Loopback address
-1
-1
Limited broadcast
netid
-1
Net directed broadcast
netid subnetid
-1
Subnet-directed broadcast
netid
-1
-1 All-subnets-directed broadcast
to netid
NAT
1.
Uniqueness of IP address
2.
Connectionless service?
3.
4.
5.
Layered approach?
What about Non TCP/UDP protocol?
Some use IP address as a test in payload such as
FTP, internet telephony protocol H.323
6.
We have limit on port number too.
IPv6?
Internet Control Protocol
Neighbor Greeting: ARP and
RARP
End nodes and routers find out their neighbors
Point-to-point link
Network
E
R
Configured with IP address and mask for each link
Neighbor Greeting: ARP and
RARP
End nodes
attached
via LANs
E4
Network
R1
R2
Ethernet
E1
E2
E3
Neighbor Greeting: ARP and
RARP
End nodes
attached
via LANs
R1
Ethernet
E1
E2
Ethernet packet
dst addr src addr
???
rest of the packet
Neighbor Greeting: ARP
ARP request
broadcast “E1
where are you?”
ARP reply:
“I am here (give
ethernet address)”
R1
E1
E2
R1
E1
E2
Neighbor Greeting: ARP
Proxy ARP
Router responding to
ARP messages for
another node
Proxy R
Gratuitous ARP:
Request to your own IP address
1. Detect another node with the same IP address
2. Update ARP cache entries if hardware addr
changes
Neighbor Greeting: RARP
S RARP server
RARP request
broadcast “What’s my
IP address (give
E1
ethernet address) ?” Doesn’t
know IP addr
RARP reply:
S
“Your IP address is
xxxx”
E1
E2
Look up IP
address
E2
Neighbor Greeting: ARP and
RARP
Ethernet packet
Header
Payload
Header
• Ethernet dst and src addresses
• Ethernet frame type = 0x0806 for ARP request
or reply
= 0x0805 for RARP request or
or reply
Neighbor Greeting: ARP and
RARP
Payload
• Hardware type = 1 for ethernet
• Protocol type = 0x800 for IP
• Length in octets of layer 2 address = 6 for ethernet
• Length in octets of layer 3 address = 4 for IP
• Operation
– 1 = ARP request
– 2 = ARP reply
– 3 = RARP request
– 4 = RARP reply
Neighbor Greeting: ARP and
RARP
Payload
• Sender layer 2 address
• Sender layer 3 address
• Target layer 2 address
• Target layer 3 address
Neighbor Greeting: ARP and
RARP
R1
Ethernet
E1
E2
ARP Cache
IP dest
Ethernet physical addr
Time outs flush
cache of old
entries
Internet Control Message
Protocol: ICMP
•
•
•
•
•
For the control plane
Uses IP packets
Deals with connectivity
Errors
Redirection
Internet Control Message
Protocol: ICMP
IP Header
ICMP Message
8-bit Type 8-bit Code 16-bit Checksum
Internet Control Message
Protocol: ICMP
type
0
3
4
5
8
9
10
11
Description
echo reply (ping reply)
destination unreachable
source quench
redirect
echo request (ping request)
router advertisement
router solicitation
time exceeded: Time-to-live = 0
Internet Control Message
Protocol: ICMP
type Description
12 Parameter problem: IP header bad or
required option missing
13 Time stamp request
14 Time stamp reply
15 Information request (obsolete)
16 Information reply (obsolete)
17 address mask request
18 address mask reply
ICMP: Address Mask
Request and Reply
• It’s used by diskless systems to obtain their
subnet mask
type
code (0)
identifier
checksum
sequence number
32-bit subnet mask
Used to match requests with replies
ICMP: Time Stamp Request
and Reply
It’s used to get the current time (# ms since midnite)
type
code (0)
identifier
checksum
sequence number
32-bit originate time stamp
req sent
32-bit receive time stamp
req recvd
32-bit transmit time stamp
reply sent
ICMP: Port Unreachable
Error
Node Z
Can’t forward
to X for some
reason
dst src
X Y
Header
ICMP Y Z
dst src
Tells Y that
there’s a
problem with
forwarding
to X at Z
ICMP: Port Unreachable
Error
Reasons why a packet can’t be forwarded:
• Network or host can’t be reached because
– Not in routing table
– Administrative or TOS prohibited
• Must fragment but packet indicates no fragmentation
• Source route failed
• Ports or protocol are unavailable
ICMP: Port Unreachable
Error
ICMP unreachable message
type(3)
code
checksum
Unused (must be 0)
IP header (including options)
+ first 8 bytes of original IP
datagram data
First 8 bytes of original IP datagram includes
src & dst port numbers for UDP and TCP headers
More on IP Packets: Options
0
Vers
15 16
HL
TOS
Total Length
Identification
TTL
31
Flags
Protocol
Header Checksum
Source Address
Destination Address
Options
Data
Offset
More on IP Packets: Options
• Options field is at most 40 bytes
• Record Route Option
• Timestamp Option
• Source Routing
Record Route Option
Packet records route: list of IP addreses
39 bytes
code len
1
1
ptr IP addr #1 IP addr #2 ... IP addr #9
1
ptr=4
4 bytes
4 bytes
ptr=8
4 bytes
ptr=36
• Code = 7
• len = total number of bytes
• ptr = points to where the next IP addr goes
IP Timestamp Option
Records time stamps along the route
OF FL
code len
1
1
ptr
timestamp #1
1
4 bytes
... timestamp #9
4 bytes
• code = 0x44
• Records time stamps
• len, ptr
• Records TS and addr
• FL flags field
• Init w. addr & TS=0
• OF field: incr every ovflow
then TS is filled in
Source Routing Option
• Strict source routing
• Loose source routing
• List of IP addresses in the packet
• Strictly defined = follow list exactly
• Loosely defined = follow list but other nodes can
be in between
Source Routing Option
Header
A,B,C,D
Strictly defined
A
B
Loosely defined
D
C
B
A
C
D
Source Routing Option
Packet follows the route in its list
39 bytes
code len
1
1
ptr IP addr #1 IP addr #2 ... IP addr #9
1
4 bytes
4 bytes
4 bytes
ptr=4
ptr=8
ptr=36
• Code = 0x83 (loose) or 0x89 (strict)
• len = total number of bytes
• ptr = points to where the next IP addr goes
Source Routing: Example
Header
dest
Payload
options
dest=D
{R1,R2,R3}
dest=R1
S {R2,R3,D}
ptr
D
dest=R2
R1
{R1,R3,D}
ptr
dest=D
{R1,R2,R3}
ptr
dest=R3
R2
R2
{R1,R2,D}
D
ptr
IP Routing
•
•
•
•
Routing principles
ICMP unreachable errors
ICMP redirects
Fast table lookups
Routing Principles
• Routing mechanism: search routing table and
decide which interface to send the packet
• Routing policy: rules to decide which routes
go into the routing tables
Routing Principles:
processing done at the IP
layer
route
command
routing
Daemon
netstate
command
IP
layer
ICMP
Routing
Table
redirects
Next interface
to forward to
Routing Principles: simple
routing table
Destination
140.252.13.65
127.0.0.1
default
140.252.13.32
Gateway
140.252.13.35
127.0.0.1
140.252.13.33
140.252.13.34
emd0
.35
.34
.33
Flags Refcnt Use
UGH 0
0
UH
1
0
UG
0
0
U
4
25
Interface
emd0
lo0
emd0
emd0
# packets
Loopback
# active connections
Routing Principles: simple
routing table
Flags
• U: Route is up
• G: Route is to a gateway (router; “indirect route”).
If not then the dest is directly connected
(“direct route)
• H: Host, destination address must be matched
completely. Without H, destination is a net or
subnet
• D: Route was created by a redirect
• M: Route was modified by a redirect
Routing Principles: simple
routing table
End
R
End
Direct
routes
Indirect route
ICMP Unreachable Errors
• When a packet cannot be forwarded then
IP sends an ICMP unreachable error
message back to the source
ICMP Redirects
I just sent a message
out from where I
received it
ICMP
redirect
R1
3
1
• Dest=X
• No Routing Table Entry
• Default = R1
Forward
2
R2
ICMP redirects updates
routing tables
ICMP Redirect Message
type(5) code(0-3)
checksum
router IP address that should be used
IP header (including options) +
first 8 bytes of original IP datagram
code
Description
0
redirect for network
1
redirect for host
2
redirect for TOS and network
3
redirect for TOS and host
ICMP Router Discovery
Messages
• Boot
• No entries in routing table
• Send router solicitation
(rs) message
H
rs
ra + list
R1
Other nodes reply
• Router advertisement
(ra)
• List of destinations it
has in its routing
tables
ra + list R2
ICMP Router Discovery
Messages
type(10) code(0-3)
checksum
Unused (sent as 0)
Format of ICMP router solicitation message
ICMP Router Discovery
Messages
type(9)
# addr
addr
entry
size
code(0)
checksum
2
lifetime
router address[1]
preference level[1]
router address[2]
preference level[2]
Format of ICMP router advertisement message
Fast Forwarding
Table look-ups are a bottleneck to packet processing
• Let’s assume each IP address (as a destination)
in the routing table has a mask.
• An IP address that would be flagged H (requiring
a complete match) would have a mask
1111....11111
• Table look-up: find the longest prefix match
Fast Forwarding: Example
11001111 01011100 00000000 10000111
Routing table entries:
1. value: 11001111 01011100 00000000 10000111
mask: 11111111 11111111 11111111 11111111
2. value: 11001111 01011100 00000000 00000000
mask: 11111111 11111111 00000000 00000000
3. value: 11001111 01011100 00000000 00000000
mask: 11111111 11111111 11100000 00000000
Longest prefix match
Fast Forwarding: Example
11001111 01011100 00001000 10000111
Routing table entries:
1. value: 11001111 01011100 00000000 10000111
mask: 11111111 11111111 11111111 11111111
2. value: 11001111 01011100 00000000 00000000
mask: 11111111 11111111 00000000 00000000
3. value: 11001111 01011100 00000000 00000000
mask: 11111111 11111111 11100000 00000000
Longest prefix match
Fast Forwarding
• Tries
• Hash functions and binary search
Tries
Binary tree
leaf
root
Each node has
at most two
children
Tries
• Binary tree
• Each node represents a prefix or part of a prefix
• Each node has a pointer to data for that prefix
E.g., outgoing interface for the prefix
• A child node extends a parent node by an
additional bit
Tries
Prefix for a subnet
01*
0
010
No children
so it is the longest
prefix with these bits
1
Not a prefix
011
1
0111*
Prefix for a subnet
Tries
{}
0
00*
000
001*
0001*
1
01
010
0101*
10
101*
1010*
11*
111*
Tries
Searching a trie:
• Start from the root
• Continue going down the trie matching the IP
address of the packet
• If any * is encountered then record that as
the “longest prefix so far”
• Return the longest prefix so far
Tries: Improvements
Collapsing a long nonbranching path
1
1
11
1111*
111
1111*
Tries: Improvements
• Trading memory for search time: k-ary trees
I.e., trees with up to k children per child
• Trees are shorter so search time is faster
• k should be a power of two, e.g., 8 or 16
Tries: Improvements
101
101
1010*
1011
10100*
Binary Trie
10110*
10100 10101 10110 10111
What forwarding info
should be stored at
each entry?
Tries: Improvements
101
101
1010*
1011
10100*
Binary Trie
10100 10101 10110 10111
10110*
10100* 1010*
1010*
10110*
Tries: Hashing and Binary
Search
Implementation of a routing table:
Suppose the table was for exact IP address matches
Implementation 1:
• Have a memory with 32 address bits
• Each address A has an entry for the IP dest A
• Problem: Big memory (4 billion) even though the
number of IP destinations may be much smaller
Tries: Hashing and Binary
Search
IP Packet
dst
Routing Table
Addresses Entries
(32 bits)
Sparsely filled
Return
outgoing
interface
Tries: Hashing function
IP Packet
dst
h(dst)
Smaller Routing Table
Addresses Entries
(16 bits)
denser
Return
outgoing
interface
Tries: Hashing Function
• The hashing function maps the 32-bit number
(IP address) into a 16-bit number (memory address
of the routing table).
• Mapping tries to be uniform. Ideally each 32-bit
number gets mapped to a distinct 16-bit number
• Example hashing function:
h(dst) = (a * dst + b) mod 216
Tries: Hashing Function
• Two distinct IP addresses dstA and dstB could
give the same hashing function output, i.e.,
h(dstA) = h(dstB). CONTENTION!
IP Packet
dst
h(dst)
Store all
dsts that
map to the
same output
as a linked
list
Tries: Hashing Function
• That’s for complete IP address matches
• What about for longest prefixes?
– Each prefix entry (e.g., 01001*) is mapped
by the hashing function to a linked list
Tries: Linear Search
How do we find the longest prefix match?
Approach 1 (linear search):
IP address
11001111 01011100 00001000 10000111
To find an entry, search for
•1
(first bit)
• then 11 (first 2 bits)
• then 110 (first 3 bits)
• and so on for all possible 32-bit prefixes
Tries: Binary Search
Approach 2 (binary search):
IP address
11001111 01011100 00001000 10000111
To find an entry, search for
• 11001111 01011100
(first 16 bits)
• if unsuccessful search for first 8 bits
• else
search for first 24 bits
• and so on until we find the longest prefix match
Tries: Binary Search
Approach 2 (binary search):
Suppose the table has the following entries
11001111 01011100 00001000 10000111*
11001111 0101110*
Then it must also have the entries
11001111 01011100 0&
11001111 01011100 00&
Etc
& means that
there’s a bigger
prefix