Transcript Addressing

371-1-0291: An Introduction to
Computer Networks
Homepage
http://help.cse.bgu.ac.il/cse/Courses/list.asp
Handout #3: IP
Additional Reading
Text book: Chap. 4.1,4.3
1
Outline
• IP: The Internet Protocol
–
–
–
–
–
–
Service characteristics
The IP Datagram format
IP addresses
Classless Interdomain Routing (CIDR)
An aside: Turning names into addresses (DNS)
Forwarding IP Datagrams
2
The Internet Protocol (IP)
Protocol Stack
App
Transport
TCP / UDP
Network
IP
Data
Data
TCP Segment
Hdr
Hdr
IP Datagram
Link
3
The Internet Protocol (IP)
•
Characteristics of IP
 CONNECTIONLESS:
miss-sequencing
 UNRELIABLE:
may drop packets…
 BEST EFFORT:
… but only if necessary
 DATAGRAM:
individually routed
Source
D
A
D
R2
H
R1
R3
R4
H
B
Destination
•Architecture
•Links
•Topology
Transparent
4
The IP Datagram
vers
HLen
TOS
ID
Hop count
TTL
Total Length
Flags
Protocol
FRAGMA Offset
checksum
Offset within
original packet
SRC IP Address
60 >=
Octets
DST IP Address
(OPTIONS)
(PAD)
<=64 K Bytes
5
Fragmentation
Problem: A router may receive a packet larger than the maximum
transmission unit (MTU) of the outgoing link.
Source
Destination
A
B
Ethernet
MTU=1500 bytes
R1
MTU=1500 bytes
MTU<1500 bytes
R2
Solution: R1 fragments the IP datagram into multiple, self-contained datagrams.
Data
Offset>0
More Frag=0
Data
HDR (ID=x)
Data
HDR (ID=x)
HDR (ID=x)
Offset=0
More Frag=1
Data
HDR (ID=x)
6
Fragmentation
MTU examples
H
Token Ring – Variable MTU
MTU = 1500 bytes
R2
FDDI – Variable MTU
Ethernet
Berkeley UNIX SLIP MTU = 1006+TCP/UDP and IP header
H
R2
SLIP - Serial Line IP
(IP datagrams on serial lines)
H
Negotiable MTU
R2
PPP – Point to Point Protocol
(used in dialup modems)
7
Fragmentation
• Fragments are re-assembled by the destination host; not by
intermediate routers.
• To avoid fragmentation, hosts commonly use path MTU
discovery to find the smallest MTU along the path.
• Path MTU discovery involves sending various size datagrams
until they do not require fragmentation along the path.
• Most links use MTU>=1500bytes today.
• Try: traceroute –f www.mit.edu 1500 and
traceroute –f www.mit.edu 1501
• DF=1 set in the IP Flags header field means Don’t Fragment;
– Routers send “ICMP” (Protocol header field = 1) error message
• Can you find a destination for which the path MTU < 1500
bytes?
8
IP Addresses
Why a new addressing scheme?






Why not using MAC addresses?
There are different LAN protocols with different MAC addr
schemes
IP is designed as to connect all LANs untouched
A format lending itself to easy Routing
Flexible no. of networks and network sizes
Multi-homing – A single host with multiple addresses
9
IP Addresses
Originally there were 5 classes:
1
CLASS “A”
CLASS “B”
CLASS “C”
CLASS “D”
CLASS “E”
0
A
24
7
Host-ID
0 Net ID
2
10
3
110
16
14
Host-ID
Net ID
8
21
Host-ID
Net ID
4
28
1110
Multicast Group ID
5
27
11110
Reserved
B
C
D
232-1
10
IP Addresses - Examples


Dotted Decimal Notation of IP addr: e.g., 18.181.0.31
Internal representation is in 32 bit string
 10101100 00010000 00001010 00000010 => 172.16.10.2



Net ID = 0 means this network
IP = 0.0.0.0 means this host on this network
IP = 127.0.0.1 is reserved for loopback testing
Class “A” address: www.mit.edu
18.181.0.31
(18<128 => Class A)
Class “B” address: techunix.technion.ac.il
132.68.1.28
(128=< 132 <128+64 => Class B)
11
IP Addresses
Class Philosophy






Hierarchical structure for efficient routing
Flexibility to build different network sizes (LAN-Class C;
campus – Class B; medium large-Class A)
Multicast addresses
Routers connecting two networks need two IP addresses
• IP address is associated with a network adaptor NOT host
The all zeros and all ones are not used for Host ID
Note: IP addresses ARE NOT Domain names which are ASCII
strings!
12
IP Addresses
Choosing the Right Class



If you setup a private network – anything goes
If you access the Internet via ISP – you’ll be assigned its Net
ID as part of your address
Free addresses that are blocked by ISP are
10.n.n.n
- A single class A network
 172.16.n.n - A single class B network
 192.168.n.n - 254 class C networks

13
IP “Classful” Addressing
Problem:




Address classes were too “rigid”. For most organizations,
Class C were too small and Class B too big. Led to very
inefficient use of address space, and a shortage of
addresses.
Organizations with internal routers needed to have a
separate (Class C) network ID for each link.
And then every other router in the Internet had to know
about every network ID in every organization, which led to
large address tables.
Small organizations wanted Class B in case they grew to
more than 255 hosts. But there were only about 16,000
Class B network IDs.
14
IP Addressing
Two solutions were introduced:



Sub-netting is used within an organization to subdivide the
organization’s network ID.
Classless Interdomain Routing (CIDR) was introduced in
1993 to provide more efficient and flexible use of IP
address space across the whole Internet.
CIDR is also known as “super-netting”.
15
Sub-netting
CLASS “B”
e.g. Company
e.g. Site
2
10
2
10
Net ID
0000
Subnet ID (20)
e.g. Dept
2
10
Subnet ID (22)
2
Host-ID
10
16
000000
2
Host-ID
Subnet
Host ID (10)
16
14
Net ID
1111
Subnet ID (20)
Subnet
Host ID (12)
14
Net ID
Host-ID
Net ID
16
14
16
14
10
Subnet
Host ID (12)
16
14
Net ID
Subnet ID (26)
Host-ID
1111011011
Host-ID
Subnet
Host ID (6)
16
Sub-netting
• Sub-netting is a form of hierarchical routing.
• Subnets are usually represented via an address
plus a subnet mask or “net-mask”.
• e.g.
inet 171.64.15.82 netmask 255.255.255.0
• Net-mask 255.255.255.0: the first 24 bits are the
subnet ID, and the last 8 bits are the host ID.
• Can also be represented by a “prefix + length”, e.g.
171.64.15.0/24.
17
Example of sub-netting
Subnet
128.96.34.128/25
Class B sub-netting
128.96.0.0/25
host ID =
1xxx xxxx
Subnet
128.96.34.0/25
128.96.34.139
host ID =
0xxx xxxx
128.96.34.15
Host 2
Subnet
128.96.33.0/24
128.96.34.129
R2
Host 1
128.96.33.1
128.96.33.14
Host 3
128.96.34.1
R1
host ID =
xxxx xxxx
128.96.34.130
18
Classless Interdomain Routing (CIDR)
Addressing
Why is it Needed ?

Backbone routing tables grow behind efficient handling


A row for each Net ID specifying the next hop
IP 32-bit addresses could get exhausted before the 4th billionth host is
attached to the Internet

Rigid class structure wastes addresses

With CIDR - a single entry specifies the next hop for many Net Ids

Instead of e.g., allocating 16 arbitrary class C Net Ids, we may allocate the
block 192.4.16 – 192.4.31



The top 20 bits in this block are the same (11000000 00000100 0001)
This creates a 20 bit Net ID between class B and C Ids in terms of
supporting hosts
Many “Classful” Net ID are merged into one routing table entry
19
Classless Interdomain Routing (CIDR)
Addressing




The IP address space is broken into blocks of continuous addr
Each block segment is described by a pair (value, length).
The pair is of the form v/l, where v is the prefix value of all
addresses subnet block, and l is the length of the prefix.
e.g. The prefix 128.9/16 represents the line segment containing
addresses in the range: 128.9.0.0 … 128.9.255.255.
142.12/19
65/8
0
128.9/16
216
232-1
128.9.16.14
20
Classless Interdomain Routing (CIDR)
Addressing
Multiple Representation
of the same subnet
128.9.19/24 (128.9.[00010011.xxxxxxxx])
128.9.25/24 (128.9.[00011001.xxxxxxxx])
(128.9.[0001xxxx.xxxxxxxx]) 128.9.16/20
128.9.176/20
128.9/16
0
128.9.19.14
In all the following:
232-1
128.9/16 ; 128.9.16/20 ; 128.9.19/24
Most specific route = “longest matching prefix”
21
Classless Interdomain Routing (CIDR)
Addressing
Prefix aggregation:


If a service provider serves organizations with different
prefixes, it can (sometimes) aggregate them to form a
larger prefix. Other routers can refer to this larger prefix,
and so reduce the size of their address table.
E.g. ISP serves 128.9.14.0/24 and 128.9.15.0/24, it can tell
other routers to send it all packets belonging to the prefix
128.9.14.0/23.
ISP Choice:

In principle, an organization can keep its prefix if it changes
service providers.
22
Size of the Routing Table at the core
of the Internet
Source: http://www.telstra.net/ops/bgptable.html
23
Prefix Length Distribution
Number of Prefixes
70000
60000
50000
40000
30000
20000
10000
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Prefix Length
Source: Geoff Huston, Oct 2001
24
Mapping Computer Names to IP addresses
The Domain Naming System (DNS)
Names are hierarchical and belong to a domain:
– e.g. elaine17.stanford.edu
– Common domain names: .com, .edu, .gov, .org, .net, .il, (or other
country-specific domain).
– Top-level names are assigned by the Internet Corporation for
Assigned Names and Numbers (ICANN).
– A unique name is assigned to each organization.
DNS Client-Server Model
– DNS maintains a hierarchical, distributed database of names.
– Servers are arranged in a hierarchy.
– Each domain has a “root” server.
– An application needing an IP address is a DNS client.
25
Mapping Computer Names to IP addresses
The Domain Naming System (DNS)
A DNS Query
1. Client asks local DNS server.
2. If local DNS server does not have address, it asks the root
server of the requested domain.
3. Addresses are cached in case they are requested again.
E.g. www.eecs.berkeley.edu
“What is the IP address of
www.eecs.berkeley.edu?”
Client
application e.g. gethostbyname()
.stanford.edu
.edu
.berkeley.edu
.eecs.berkeley.edu
Example: On your local desktop, type “nslookup www.msn.com”
26
An example of names and addresses
Mapping the path between two hosts
E:\>nslookup www.msn.com
Server: dns.netvision.net.il
Address: 194.90.1.5
Non-authoritative answer:
Name:
www.msn.com
Addresses: 207.68.173.254, 207.68.171.244, 207.68.171.245, 207.68.172.234
---------------------------------------------------------------E:\>tracert www.mit.edu
Tracing route to DANDELION-PATCH.mit.edu [18.181.0.31]
over a maximum of 30 hops:
1
121 ms
120 ms
130 ms ras2-L1.hfa.netvision.net.il [212.143.200.231]
2
111 ms
130 ms
130 ms rs2-fa-1-0.hfa.netvision.net.il [212.143.200.26]
3
121 ms
130 ms
110 ms gi10-0.core1.hfa.nv.net.il [212.143.8.69]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
491 ms
510 ms
511 ms so-4-0-0.bstnma1-nbr2.bbnplanet.net [4.24.6.49]
11
491 ms
511 ms
511 ms p2-0.bstnma1-cr5.bbnplanet.net [4.24.4.201]
12
510 ms
531 ms
521 ms p0-0.mit3.bbnplanet.net [4.24.88.50]
13
521 ms
511 ms
500 ms NW12-RTR-2-BACKBONE.MIT.EDU [18.168.0.21]
14
510 ms
531 ms
521 ms DANDELION-PATCH.MIT.EDU [18.181.0.31]
Trace complete.
27
Example
Mapping the path between two hosts
Subnet
128.96.34.128/25
Class B sub-netting
128.96.0.0/25
host ID =
1xxx xxxx
Subnet
128.96.34.0/25
128.96.34.139
host ID =
0xxx xxxx
128.96.34.15
Host 2
Subnet
128.96.33.0/24
128.96.34.129
R2
Host 1
128.96.33.1
128.96.33.14
Host 3
128.96.34.1
R1
host ID =
xxxx xxxx
128.96.34.130
28
An aside:
Error Reporting (ICMP) and traceroute
Internet Control Message Protocol:
– Used by a router/end-host to report some types of error:
– E.g. Destination Unreachable: packet can’t be forwarded
to/towards its destination.
– E.g. Time Exceeded: TTL reached zero, or fragment didn’t
arrive in time. Traceroute uses this error to its advantage.
– An ICMP message is an IP datagram, and is sent back to the
source of the packet that caused the error.
29
How a Router Forwards Datagrams
e.g. 128.9.16.14 => Port 2
128.17.20.1
Most specific address
R2
1
R1 2
3
R3
128.17.14.1
R4
128.17.16.1
Prefix
Next-hop
Port
65/8
128.9/16
128.9.16/20
128.9.19/24
128.9.25/24
128.9.176/20
142.12/19
128.17.16.1
128.17.14.1
128.17.14.1
128.17.10.1
128.17.14.1
128.17.20.1
128.17.16.1
3
2
2
7
2
1
3
Forwarding/routing table
30
How a Router Forwards Datagrams
Every datagram contains a destination
address.
 The router determines the prefix to which
the address belongs, and routes it to
the“Network ID” uniquely identifies a
physical network.
 All hosts and routers sharing a Network ID
share same physical network.

31
Forwarding Datagrams
Is the datagram for a host on directly
attached network?
 If no, consult forwarding table to find
next-hop.

32
Inside a Router
1.
Forwarding
Table
2.
3.
Output
Scheduling
Interconnect
Forwarding
Decision
Forwarding
Table
Forwarding
Decision
Forwarding
Table
Forwarding
Decision
33
Forwarding in an IP Router
• Lookup packet DA in forwarding table.
– If known, forward to correct port.
– If unknown, drop packet.
• Decrement TTL, update header Checksum.
• Forward packet to outgoing interface.
• Transmit packet onto link.
Question: How is the address looked up in a real router?
34
Making a Forwarding Decision
Classful addressing
IP Address Space
Class A
Class B
Class A
212.17.9.4
Class B
Class C
Class C
D
Routing Table:
Exact
Match
212.17.9.0
212.17.9.0 Port 4
Exact Match: There are many well-known ways to find an exact match in a table.
35
Direct Lookup
IP Address
Memory
Next-hop, Port
Problem: With 232 addresses, the memory would require 4 billion entries.
36
Associative Lookups
“Contents addressable memory” (CAM)
Advantages:
• Simple
Associative
Memory or CAM
Search
Data
32
Network
Address
Port
Number
Disadvantages
Port
Number
Hit?
• Slow
• High Power
• Expensive
37
Hashed Lookups
Hashing
Function
16
Memory
Data
32
Address
Search
Data
Associated
Data
{
Hit?
Address
Space reduced
38
Lookups Using Hashing
An example
Memory
#1
Search
Data
32
Hashing Function
16
Linked list of entries
with same hash key.
#2
#3
#4
Associated
Data
#1
#2
#1
#2
Hit?
#3
39
Lookups Using Hashing
Advantages:
• Simple
• Expected lookup time can be small
Disadvantages
• Non-deterministic lookup time
• Inefficient use of memory
40
Trees and Tries
Binary Search Tree:
<
>
>
<
N entries
>
log2N
<
Binary Search Trie:
0
0
1
1
010
0
1
111
Requires 32 memory references,
regardless of number of addresses.
41
Search Tries
Multiway tries reduce the number of memory references
16-ary Search Trie
0000, ptr
0000, ptr
1111, ptr
000011110000
1111, ptr
0000, ptr
1111, ptr
111111111111
Question: Why not keep increasing the degree of the trie?
42
Classless Addressing
CIDR
128.9.19/24
128.9.25/24
128.9.16/20 128.9.176/20
128.9/16
0
232-1
128.9.16.14
Most specific route = “longest matching prefix”
Question: How can we look up addresses if they are not an exact match?
43
Ternary CAMs
Associative Memory
Value
Mask
Port
255.255.255.255
1
10.1.1.0
255.255.255.0
2
10.1.3.0
255.255.255.0
3
10.1.0.0
255.255.0.0
4
10.0.0.0
255.0.0.0
4
10.1.1.32
Note: Most specific routes appear closest to top of table
44
Longest prefix matches using
Binary Tries
0
f
d
e
abc
1
g
h
i
wasteful
Example
a)
b)
c)
d)
e)
f)
g)
h)
i)
j)
Prefixes:
00001
00010
00011
001
0101
011
100
1010
1100
11110000
j
45
Patricia Tries
0
f
d
e
abc
1
g
h
i
Example
a)
b)
c)
Skip 5 d)
j
e)
f)
g)
h)
i)
j)
Prefixes:
00001
00010
00011
001
0101
011
100
1010
1100
11110000
46
Lookup Performance Required
Line
Line Rate
Pktsize=40B
Pktsize=240B
T1
1.5Mbps
4.68 Kp/ps
0.78 Kp/ps
OC3
155Mbps
480 Kp/ps
80 Kp/ps
OC12
622Mbps
1.94 Mp/ps
323 Kp/ps
OC48
2.5Gbps
7.81 Mp/ps
1.3 Mp/ps
OC192
10 Gbps
31.25 Mp/ps
5.21 Mp/ps
47