Transcript InternetworkingIntrox

Internetworking
Fall 2010
CMSC 150
1
Assumptions
• Data pipe from every machine to every other
machine.
– Need not be single link (and in most cases will
involve several links and several networks).
– Pipe can lose or corrupt data (think postal system
analogy – vast majority of time it arrives, but not
always).
– We transmit data in discrete chunks called “packets”
• So what info do we need to build a single
“logical” network (either reliable or
unreliable)?
Fall 2010
CMSC 150
2
Issues
• Getting various technologies to work with one
another (I.e. creating a single “network” from
many heterogeneous systems).
– Problem magnified since packet may need to
traverse several different networks (and network
technologies), each with their own addressing
schemes, service models, media access protocols,
etc.
• Scale: It’s the big issue
– How can you find an efficient path through a network
with millions (and perhaps billions eventually) of
nodes?
– How do you provide addressing for a network with
this many nodes?
Fall 2010
CMSC 150
3
Internetwork:
• Arbitrary collection of possibly heterogeneous
networks interconnected to provide host-tohost packet delivery service.
• Network: Directly connected or switched
network that uses a single technology (i.e.
ATM, 802.5, Ethernet).
– Could be many physical networks creating a single
logical network.
– E.g. several Ethernet networks connected on a
university campus
Fall 2010
CMSC 150
4
Internetwork
• Internet—THE internetwork.
– Runs the Internet Protocol (Kahn-Cerf)
– Interesting because it has faced the problems of
scale
• internet—abstract internetwork
Fall 2010
CMSC 150
5
IP is a big deal
White House News & Policies photo
• Vint Cerf and Bob Kahn with Pres. Bush at
2006 ceremony where they received the
Presidential Medal of Freedom for their work
on IP.
Fall 2010
CMSC 150
6
IP Internet
• Concatenation of Networks
Fall 2010
CMSC 150
Note Hn denotes host,
Rn denotes router.
7
IP Internet
• Protocol Stack
H1
H8
TCP
R1
IP
IP
ETH
Fall 2010
R2
ETH
R3
IP
FDDI
FDDI
IP
PPP
CMSC 150
PPP
TCP
IP
ETH
ETH
8
The Internet
Outline
Best Effort Service Model
Global Addressing Scheme
Fall 2010
CMSC 150
9
Service Model
• Connectionless (datagram-based)
– So each packet must be “self-contained”
• Best-effort delivery (unreliable
service)
– packets are lost
– packets are delivered out of order
– duplicate copies of a packet are
delivered (?!)
– packets can be delayed for a long time
Fall 2010
CMSC 150
10
Why?!
• Best Effort service model is as simple a model
as you can design, and this is a strong point!
– If you provide best effort service over a network
technology that provides reliable delivery, you’re fine
– If you provide reliable delivery over a network
technology that is unreliable, then you’ve got a
problem: you need lots of extra functionality in the
routers to handle the network deficiencies, and
keeping the routers as simple as possible was
an IP design goal. (Why?)
• Note: IP today runs over many technologies
that were not in existence when IP was
invented!
Fall 2010
CMSC 150
11
Note: fields
aligned on
32 bit
boundaries 0
IP Datagram Format
In 32 bit words
In bytes
4
V ersion
8
HLen
16
TOS
31
Length
Ident
TTL
19
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Pad
(variable)
Options (variable)
Data
Fall 2010
CMSC 150
12
Fields
• Version: note placement at front of packet
(why?)
• Header Length: in 32 bit words (20 bytes
when no options)
• Type of service: later
• Length: of entire packet in bytes (note max of
65,535 bytes because of 16 bit length field)
• Ident, flags, offset all deal with fragmentation
• Time to live: first seconds, but evolved to be
hop count
Fall 2010
CMSC 150
13
Fields
• Protocol: demux key specifying higher level
protocol that gets datagram
• Checksum: take IP header as sequence of 16
bit words, add them using ones complement,
take ones complement of result.
– Relatively easy to calculate in software
– Not as strong error detection as CRC
– Bad packets discarded
• Src, dest address: pretty clear (and these are
unique!)
• Options: rare, but complete IP implementation
must handle them all! Presence determined
by header length field
Fall 2010
CMSC 150
14
Fragmentation and Reassembly
• Each network has some MTU (why?)
– Why not some uniform standard?
– What is a reasonable choice for a given host?
• Strategy
–
–
–
–
–
–
fragment when necessary (MTU < Datagram length)
try to avoid fragmentation at source host
re-fragmentation is possible
fragments are self-contained datagrams
delay reassembly until destination host
do not recover from lost fragments
Fall 2010
CMSC 150
15
Fragmentation and Reassembly
• Ident field: chosen by sending host, intended
to be unique among all datagrams that might
be received at this dest from this source over
reasonable time period.
– All fragments keep this same ident value
• Offset: specifies 8 bytes chunk of data (why?)
• Flags: M is “more” flag
Fall 2010
CMSC 150
16
Example
Start of header
Ident= x
0
Offset= 0
Rest of header
1400 data bytes
MTU 532 bytes
Start of header
Ident= x
H1
R1
R2
R3
H8
1
Offset= 0
Rest of header
512 data bytes
Start of header
ETH IP (1400)
FDDI IP (1400)
PPP IP (512)
ETH IP (512)
PPP IP (512)
ETH IP (512)
Rest of header
PPP IP (376)
ETH IP (376)
512 data bytes
Ident= x
1 Offset= 512
Start of header
Ident= x
Note: fragmentation can occur
at multiple hops!
Fall 2010
0 Offset= 1024
Rest of header
376 data bytes
CMSC 150
17
Global Addresses
• Properties
– globally unique (don’t want anyone with my phone
#)
• Why not just use Ethernet address?!
– hierarchical: network + host (really interface)
• Dot Notation
– 10.3.2.4
– 128.96.33.81
– 192.12.69.77
A:
B:
C:
Fall 2010
0
7
24
Network
Host
1 0
1 1 0
CMSC 150
14
16
Network
Host
21
8
Network
Host
18
IP Internet
Note Hn denotes host,
Rn denotes router.
Routers need two
IP addresses.
All hosts on same
network have same
network part of
IP address
Fall 2010
CMSC 150
19
Terminology
•
•
Routing Mechanism: How a router selects
the link over which to forward a packet
Routing Protocol: Policies that determine
what is placed in the routing tables.
These are not the same thing!
Fall 2010
CMSC 150
20
Datagram Forwarding
• Strategy
– every datagram contains destination’s address
– if directly connected to destination network, then
forward to host
– if not directly connected to destination network, then
forward to some router
– forwarding table maps network number into next hop
– each host has a default router
– each router maintains a forwarding table
• Example (R2)
Network Number
Next Hop
1
R3
2
R1
3
interface 1
4
interface 0
Fall 2010
CMSC 150
21
Recall:
Network 1 (Ethernet)
H7
H2
H1
R3
H8
H3
Network 4
(point-to-point)
Network 2 (Ethernet)
R1
R2
H4
Network 3 (FDDI)
H5
Fall 2010
H6
CMSC 150
22
Pseudocode
if (networknum dest = networknum my
interface)
deliver packet over that interface
else
if (networknum in my routing table)
deliver packet to next hop router
else
deliver packet to default router
Fall 2010
CMSC 150
23