Transcript Internetworking

Internetworking
4.1 Simple Internetworking (IP)
4.2 Routing
4.3 Global Internet
4.4 Multicast
1
4.1 Simple Internetworking (IP)
4.1.1 What is an Internework
4.1.2 Service Model
4.1.3 Global Address
4.1.4 Datagram Forwarding in IP
4.1.5 Address Translation (ARP)
4.1.6 Host Configuration (DHCP)
4.1.7 Error Reporting (ICMP)
4.1.8 Virtual Networks and Tunnels
2
4.1.1 What is an Internework
 Concatenation of networks
H1
H2
Netw ork 1 (Ethernet)
H7
H3
R3
H8
Netw ork 4
(point-to-point)
Netw ork 2 (Ethernet)
R1
R2
H4
Netw ork 3 (FDDI)
H5
H6
A simple internetwork. Hn =host, Rn = router
3
 An internetwork is a network of networks
 in the figure, we see Ethernets, an FDDI ring, and a
point-to-point link
 each of these is a single-technology network
 the nodes that interconnect the networks are called
routers (sometimes called gateways)
 The following figure shows how H1 and H8 are
logically connected by the internet, including
the protocol graph running on each node
4
 A simple internetwork of protocol stack
H1
H8
TCP
R1
IP
ETH
R2
IP
ETH
R3
IP
FDDI
FDDI
IP
PPP
PPP
TCP
IP
ETH
ETH
Protocol layers used to connect H1 to H8.
ETH: the protocol that runs over Ethernet.
5
4.1.2 Service Model
 A good place to start when you build an internetwork
is to define its service model
 A service model is the host-to-host services you want
to provide
 Service model for an internetwork
 a host-to-host service only if this service can
somehow be provided over each of the underlying
physical networks
6
4.1.2 Service Model
 IP service model has two parts
 addressing scheme
 provides a way to identify all hosts in the internetwork
 datagram (conectionless) model of data delivery
 This service model is sometimes called best effort
 although IP makes every effort to deliver datagrams, it makes
no guarantees
7
 Datagram
 a type of packet sent in a connectionless manner
over a network
 every datagram carry enough information to let
the network forward the packet to its correct
destination
 no need for any advance setup mechanism to tell
the network what to do when the packet arrives
8
 Best-effort delivery (unreliable service)
 if something goes wrong and has the following
situations




packets are lost
packets are delivered out of order
duplicate copies of a packet are delivered
packets can be delayed for a long time
 the network does not make any attempt to recover
from the failure
9
 Best-effort, connectionless service is about the
simplest service you could ask for from an
internetwork
 If you provide best-effort service over a
network that provides a reliable service, then
that’s fine
10
 If, on the other hand, you had a reliable service
model over an unreliable network, you would
have to put lots of extra functionality into the
routers
 Keeping the routers as simple as possible was
one of the original design goals of IP
11
 Datagram format
0
4
Version
8
HLen
16
TOS
31
Length
Ident
TTL
19
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Pad
(variable)
Data
12
 Datagram format
 a succession of 32-bit words
 Packet formats at the internetworking layer and above
are almost invariably designed to align on 32-bit
boundaries
 To simplify the task of processing them in software
0
4
Version
8
HLen
16
TOS
31
Length
Ident
TTL
19
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Pad
(variable)
Data
13
 Datagram format
 a succession of 32-bit words
 the top word is transmitted first
 the leftmost byte of each word is transmitted first
0
4
Version
8
HLen
16
TOS
31
Length
Ident
TTL
19
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Pad
(variable)
Data
14
 1st word of the header
 Version: the version of IP
 the current version of IP is 4 (IPv4)
 HLen: the length of the header in 32-bit words
 most of the time (when there are no options),
the header is 5 words (20 bytes) long
15
 TOS: the 8-bit type of service
 allow packets to be treated differently based
on application needs
 example, the TOS value might determine
whether or not a packet should be placed in a
special queue that receives low delay
16
 Length: 16 bits of the header
 contain the length of the datagram, including
the header
 the field counts bytes rather than words
 the maximum size of an IP datagram is
65,535 bytes
 the physical network over which IP is
running may not support such long packets
 IP supports a fragmentation and
reassembly process
17
 2nd word of the header contains information about
fragmentation
 Offset: 12-bit counts 8-byte chunk, not bytes
 the distance (number of chunks) between the
start of the original data and the start of the
current fragment
18
 3rd word of the header
 TTL: one-byte time to live
 a specific number of seconds that the packet
would be allowed to live
 routers along the path would decrement this
field until it reached 0
 By default: 64
 Protocol: one-byte demultiplexing key
 identifies the higher-level protocol to which
this IP packet should be passed
 values defined for TCP (6), UDP (17)
19
 Checksum:
 calculated by considering the entire IP header
as a sequence of 16-bit words
 adding them up using ones complement
arithmetic, and taking the ones complement
of the result
20
 the fourth word of the header: SourceAddr
 the fifth word of the header: DestinationAddr
 there may be a number of options at the end of the
header
 the presence or absence of options may be determined
by examining the header length (HLen) field
21
Fragmentation and Reassembly
 Each network technology tends to have its own idea
of how large a packet can be, example,
 Ethernet can accept packets up to 1,500 bytes long
 FDDI packets may be 4,500 bytes long
 Every network type has a maximum transmission
unit (MTU)
 the largest IP datagram that it can carry in a frame
 this value is smaller than the largest packet size on that
network because the IP datagram needs to fit in the payload
of the link-layer frame
22
 Fragmentation
 typically occurs when necessary (MTU < Datagram)
 to enable these fragments to be reassembled at the
receiving host, they all carry the same identifier in
the Ident field
 this identifier is chosen by the sending host and is
intended to be unique among all the datagrams that
might arrive at the destination from this source over
some reasonable time period
23
 since all fragments of the original datagram contain
this identifier, the reassembling host will be able to
recognize those fragments that go together
 should all the fragments not arrive at the receiving
host, the host gives up on the reassembly process
and discards the fragments that did arrive
 IP does not attempt to recover from missing
fragments
24
 example
 consider what happens when host Hl sends a datagram
to host H8
 assuming that the MTU is 1,500 bytes for the two
Ethernets, 4,500 bytes for the FDDI network, and 532
bytes for the point-to-point network
 a 1,420-byte datagram (20-byte IP header plus 1,400 bytes
of data) sent from H1 makes it across the first Ethernet and
the FDDI network without fragmentation but must be
fragmented into three datagrams at router R2
 these three fragments are then forwarded by router R3
across the second Ethernet to the destination host
25
26
H1
R1
R1
ETH IP (1400)
R2
R2
FDDI IP (1400)
H8
R3
R3
PPP IP (512)
ETH IP (512)
PPP IP (512)
ETH IP (512)
PPP IP (376)
ETH IP (376)
IP datagrams traversing the sequence of physical networks
27
 each fragment is itself a self-contained IP datagram
that is transmitted over a sequence of physical
networks, independent of the other fragments
 each IP datagram is reencapsulated for each
physical network over which it travels
28
(a)
(b)
Header fields used in IP fragmentation: (a) unfragmented packet; (b) fragmented packets.
29
 The unfragmented packet has 1,400 bytes of data and a
20-byte IP header
 when the packet arrives at router R2, which has an MTU of
532 bytes, it has to be fragmented
 a 532-byte MTU leaves 512 bytes for data after the 20-byte
IP header, so the first fragment contains 512 bytes of data
 the router sets the M bit as 1 in the Flags field, meaning that
there are more fragments to follow
 it sets the Offset to 0, since this fragment contains the first
part of the original datagram
30
 the data carried in the second fragment starts with
the 513th byte of the original data, so the field in
this header is set to 64 (= 512/8)
 the third fragment contains the last 376 bytes of
data, and the offset is now 2 × 512 / 8 = 128 (since
this is the last fragment, the M bit is not set)
31
4.1.3 Global Addresses
 One of the things that IP service model
provides is an addressing scheme
 If you want to be able to send data to any host
on any network, there needs to be a way of
identifying all the hosts
 Thus, we need a global addressing scheme–
one in which no two hosts have the same
address
32
4.1.3 Global Addresses
 Ethernet addresses are globally unique
 that alone does not suffice for an addressing
scheme in a large internetwork
 Ethernet addresses are also flat
 they have no structure and provide very few clues
to routing protocols
33
 IP addresses are hierarchical
 made up of two parts that correspond to some sort
of hierarchy in the internetwork
 network part
 identifies the network to which the host is
attached
 all hosts attached to the same network have the
same network part
 host part
 identifies each host uniquely on that particular
network
34
 example 1
 the addresses of the hosts on network 1 would all have the
same network part and different host parts
 example 2
 the routers are attached to two networks
 they need to have an address on each network, one for each
interface, e.g., router Rl
 has an IP address on the interface to network 2 that has the same
network part as the hosts on network 2
 has an IP address on the interface to network 3 that has the same
network part as the hosts on network 3
 it is more precise to think of IP addresses as belonging to
interfaces than to hosts
35
 IP addresses are divided into three different
classes
 each of the following figure defines different-sized
network and host parts
 there are also class D addresses specify a multicast
group, and class E addresses that are currently
unused
 in all cases, the address is 32 bits long
36
7
A:
0
24
Network
Host
14
B:
1
0
16
Network
Host
21
C:
1
1
0
Network
8
Host
IP addresses: (a) class A; (b) class B; (c) class C
37
 the class of an IP address is identified in the most
significant few bits
 if the first bit is 0, it is a class A address
 if the first bit is 1 and the second is 0, it is a class B
 if the first two bits are 1 and the third is 0, it is a class
C address
 of the approximately 4 billion (= 232)possible IP
addresses
 one-half are class A
 one-quarter are class B
 one-eighth are class C
38
 Class A addresses
 7 bits for the network part and 24 bits for the host
part
 126 (= 27-2) class A networks (0 and 127 are
reserved)
 each network can accommodate up to 224-2 (about 16
million) hosts (again, two are reserved values)
 Class B addresses
 14 bits for the network part and 16 bits for the host
part
 65,534 (= 216-2) hosts
39
 Class C addresses
 21 bits for the network part and 8 bits for the
host part
 2,097,152 (= 22l) class C networks
 254 hosts (host identifier 255 is reserved for
broadcast, and 0 is not a valid host number)
40
 IP addresses are written as four decimal integers
separated by dots
 each integer represents the decimal value contained in
1 byte (= 0~255) of the address, starting at the most
significant
 Example, 171.69.210.245
 Internet domain names (DNS)
 also hierarchical
 domain names tend to be ASCII strings separated by
dots, e.g., cs.princeton.edu
41
4.1.4 Datagram Forwarding in IP
 Forwarding
 the process of taking packet from an input and
sending it out on the appropriate output
 Routing
 the process of building up the tables that allow the
correct output for a packet to be determined
 The discussion here focus on forwarding
42
 Strategy
 every IP datagram contains destination’s address
 if connected to destination network
 then forward to host
 if not directly connected
 then forward to some router
 forwarding table maps network number
(NetworkNum) into next hop (NextHop)
 each host has a default router
 each router maintains a forwarding table
43
 Datagram forwarding algorithm
 if (NetworkNum of destination = NetworkNum of one
of my interfaces) then
deliver packet to destination over that interface
else
if (NetworkNum of destination is in my forwarding
table) then
deliver packet to NextHop route
else
deliver packet to default router
44
 For a host with only one interface and only a default router
in its forwarding table
 (simplified algorithm)
 if (NetworkNum of destination = my NetworkNum)
then
deliver packet to destination directly
else
deliver packet to default router
45
 Example1
 suppose H1 wants to send a datagram to H2
 since they are on the same physical network, H1
and H2 have the same network number in their IP
address
 H1 deduces that it can deliver the datagram directly
to H2 over the Ethernet
 the one that needs to be resolved is how Hl finds
out the correct Ethernet address for H2
46
 Example2
 suppose H1 wants to send a datagram to H8
 since they are on different physical networks
 H1 deduces that it needs to send the datagram to a
router
 Hl sends the datagram over the Ethernet to R1
 R1 knows that it cannot deliver a datagram directly
to H8 because neither of Rl’s interfaces is on the
same network as H8
47
 suppose R1’s default router is R2; R1 then sends
the datagram to R2 over the token ring network
 assume R2 has the forwarding table shown as
follows, it looks up H8’s network number (network
1) and forwards the datagram to R3
48
Network
Number
Next Hop
1
R3
2
R1
3
Interface 1
4
Interface 0
Forwarding table for router R2
49
 R3 forwards the datagram directly to H8
 it is possible to include the information about directly
connected networks in the forwarding table
 example, we could label the network interfaces of router R2
as interface 0 for the point-to-point link (network 4) and
interface l for the token ring (network 3)
50
4.1.5 Address Translation (ARP)
 Issue
 IP datagrams contain IP addresses, but the physical
interface hardware on the host or router to which you
want to send the datagram only understands the
addressing scheme of that particular network
51
 Resolution
 translate the IP address to a link-level address that
makes sense on this network (e.g., a 48-bit Ethernet
address)
 encapsulate the IP datagram inside a frame that contains
that link-1evel address and send it either to the ultimate
destination or to a router that promises to forward the
datagram toward the ultimate destination
frame
link-level
address
IP datagram
Encapsulation
52
Network part
Host part
(physical address)
 Simple way to map an IP address into a physical network
address
 encode a host’s physical address in the host part of its IP
address
 example, a host with physical address 00100001
01001001 (the decimal value 33 in the upper byte and
73 in the lower byte) might be given the IP address
128.96.33.73
 it is limited in that the network’s physical addresses can
be no more than 16 bits long in this example
53
 More general solution
 each host maintains a table of address pairs (map IP
addresses into physical addresses)
 Alternative solution：Address Resolution Protocol
(ARP)
 enable each host on a network to build up a table of
mappings between IP addresses and link-level addresses
 since these mappings may over time (e.g. because an
Ethernet card in a host breaks and is replaced by a new one
with a new address), the entries are timed out periodically
and removed
54
 this happens on the order of every 15 minutes
 the set of mappings currently stored in a host is known as the
ARP cache or ARP table
55
 The ARP packet contains
 HardwareType
 the type of physical network (e.g., Ethernet)
 ProtocolType
 the higher-layer protocol (e.g., IP)
 HLen (“hardware” address length) and PLen (“protocol”
address length)
 the length of the link-layer address and higher-layer
protocol address
56
 Operation
 specifies whether this is a request or a response
 Addresses




source hardware (Ethernet) address (6 bytes)
source protocol (IP) address (4 bytes)
target hardware (Ethernet) address (6 bytes)
target protocol (IP) address (4 bytes)
57
0
8
16
Hardware type = 1
HLen = 48
31
ProtocolType = 0x0800
PLen = 32
Operation
SourceHardwareAddr (bytes 0-3)
SourceHardwareAddr (bytes 4-5)
SourceProtocolAddr (bytes 0-1)
SourceProtocolAddr (bytes 2-3)
TargetHardwareAddr (bytes 0-1)
TargetHardwareAddr (bytes 2-5)
TargetProtocolAddr (bytes 0-3)
ARP Packet Format
58
4.1.6 Host Configuration (DHCP)
 Dynamic Host Configuration Protocol (DHCP)
 relies on the existence of a DHCP server that is responsible
for providing configuration information to hosts
 there is at least one DHCP server for an administrative
domain
 at the simplest level, the DHCP server can function just as
a centralized repository for host configuration information
 DHCP saves the network administrators from having to
walk around to every host in the company with a list of
addresses and network map in hand and configuring each
host manually
59
 a more sophisticated use of DHCP saves the network
administrator from even having to assign addresses to
individual hosts
 the DHCP server maintains a pool of available
addresses that it hands out to hosts on demand
 this considerably reduces the amount of configuration
an administrator must do by allocating a range of IP
addresses (all with the same network number) to each
network
60
 DHCP server discovery
 to contact a DHCP server, a newly booted or attached host
sends a DHCPDISCOVER message to a special IP
(broadcast) address (255.255.255.255)
 it will be received by all hosts and routers on that network
 in the simplest case, one of these nodes is the DHCP server
for the network
 the server would then reply to the host that generated the
discovery message (all the other nodes would ignore it)
61
 DHCP uses the concept of relay agent
 there is at least one relay agent on each network, and it is
configured with just one piece of information: the IP
address of the DHCP server
 when a relay agent receives a DHCPDISCOVER message,
it unicasts it to the DHCP server and awaits the response,
which it will then send back to the requesting client
62
Unicast to server
DHCP
relay
Other netw orks
DHCP
server
Broadcast
Host
A DHCP relay agent receives a broadcast DHCPDISCOVER message from a host and sends
a unicast DHCPDISCOVER to a remote DHCP Server.
63
Operation
HType
HLen
Hops
Xid
Secs
Flags
ciaddr
yiaddr
siaddr
giaddr
chaddr (16 bytes)
sname (64 bytes)
file (128 bytes)
options
DHCP packet format
64
65
Operation
HType
HLen
Hops
Xid
Secs
Flags
ciaddr
yiaddr
siaddr
giaddr
chaddr (16 bytes)
sname (64 bytes)
file (128 bytes)
options
 B (Broadcast): 1 bit





Client IP address (ciaddr): 32 bits
Your IP address (yiaddr): 32 bits
Server IP address (siaddr): 32 bits
Gateway IP address (giaddr): 32 bits
Client hardware address (chaddr): 16 bytes
66
4.1.7 Error Reporting (ICMP)
 Internet Control Message Protocol (ICMP)
 defines a collection of error messages that are sent
back to the source host whenever a router is unable
to process an IP datagram successfully
 ICMP segment structure
67
 ICMP header (starts at bit 160 of the IP header)
 Type
 ICMP type as specified above
 Code (see the following table)
 further specification of the ICMP type
 e.g. an ICMP Destination Unreachable might have this field
set to 1 through 15 each bearing different meaning
 Checksum
 contains error checking data calculated from the ICMP
header+data, with value 0 for this field
68
 ID
 contains an ID value, should be returned in case of
ECHO REPLY
 Sequence
 contains a sequence value, should be returned in case
of ECHO REPLY
69
List of permitted control messages
(incomplete list)
70
71
72
4.1.8 Virtual Networks and Tunnels
 Virtual Private Network (VPN)
 a more controlled connectivity
 corporations with many sites often build private networks by
leasing transmission lines from the phone companies and
using those lines to interconnect sites
 communication is restricted to take place only among the
sites of that corporation, which is often desirable for security
reasons
 to make a private network “virtual”, the leased transmission
lines - which are not shared with any other corporations would be replaced by some sort of shared network
73
C
Physical links
A
B
Corporation X private netw ork
K
L
M
Corporation Y private netw ork
(a)
K
C
L
Physical links
A
M
B
Virtual circuits
(b)
An example of virtual private networks: (a) two separate private networks;
(b) two virtual private networks sharing common switches.
 In the above figure
 Frame Relay or ATM network is used to provide the
controlled connectivity among sites
 limited connectivity of a real private network is
maintained
 IP Tunnel
 a virtual point-to-point link between a pair of nodes that
are actually separated by an arbitrary number of
networks
75
Netw ork 1
R1
Internetw ork
R2
Netw ork 2
10.0.0.1
IP header,
Destination = 2.x
IP header,
Destination = 10.0.0.1
IP header,
Destination = 2.x
IP payload
IP header,
Destination = 2.x
IP payload
IP payload
A tunnel through an internetwork (the change in encapsulation
of the packet as it moves across the network)
76
Netw ork 1
R1
Internetw ork
R2
Netw ork 2
10.0.0.1
IP header,
Destination = 2.x
IP header,
Destination = 10.0.0.1
IP header,
Destination = 2.x
IP payload
IP header,
Destination = 2.x
IP payload
IP payload
 A tunnel has been configured from R1 to R2
and assigned a virtual interface number 0
 The forwarding table in R1 might therefore
look like the following table
 R1 has two physical interfaces
 interface 0 connects to network 1
 interface 1 connects to a large internetwork and is
thus the default for all traffic that does not match
something more specific in the forwarding table
77
 R1 has a virtual interface, which is the interface to the tunnel
 suppose R1 receives a packet from network 1 that contains an
address in network 2
 the forwarding table says this packet should be sent out
virtual interface 0
 in order to send a packet out this interface, the router
takes the packet, adds an IP header addressed to R2, and
then proceeds to forward the packet as it had just been
received
 R2’s address is 10.0.0.1
 since the network number of this address is 10, not 1 or 2,
a packet destined for R2 will be forwarded out the default
interface into the internetwork
78
NetworkNum
NextHop
1
Interface 0
2
Virtual
interface 0
Default
Interface 1
Forwarding table for router R1
79