Transcript An Introduction to Computer Networks

An Introduction
to
Computer Networks
Lecture 8: Internetworking
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
Univ. of Tehran
Introduction to Computer Network
1
Outline





Internetworking
Best Effort Service Model
Segmentation and Reassembly (SAR)
Global Addressing Scheme
Packet forwarding.
Univ. of Tehran
Introduction to Computer Network
2
Internetworking


Communication between networks, either directly
connected or switched
Problems:






Different Networking technologies (Heterogeneity).
So many Networks (Scaling).
Surviving in case of failure.
Different services
etc.,
Some terminologies:


“internetworking” refer to an arbitrary collection of
connected networks.
“Internet” the global internetwork.
Univ. of Tehran
Introduction to Computer Network
3
Goals of the DARPA project
0
Connect existing networks

1.
Survivability
-
2.
3.
4.
5.
6.
initially ARPANET and ARPA packet radio network
ensure communication service even in the
presence of network and router failures
Support multiple types of services
Must accommodate a variety of networks
Allow distributed management
Allow host attachment with a low level of effort
Univ. of
Tehran
Introduction to Computer Network
Allow
resource
accountability
4
IP Internet


Concatenation of Networks or
“networks of Networks”.
“R” is routers and “H” is hosts.
Network 1 (Ethernet)
H7
H2
H1
R3
H8
H3
Network 4
(point-to-point)
Network 2 (Ethernet)
R1
R2
H4
Network 3 (FDDI)
H5
Univ. of Tehran
H6
Introduction to Computer Network
5
IP Internet (cont)

Protocol Stack
H1
H8
TCP
IP
IP
ETH

R2
R1
ETH
FDDI
R3
IP
FDDI
IP
PPP
PPP
TCP
IP
ETH
ETH
Everything is running on top of IP, “IP
over everything”
Univ. of Tehran
Introduction to Computer Network
6
Service Model


Connectionless (datagram-based)
Best-effort delivery (unreliable service)





packets are lost. No recover from lost.
packets are delivered out of order
duplicate copies of a packet are delivered
packets can be delayed for a long time
Datagram format
0
8
4
Version HLen
16
TOS
Ident
•Contains all information
for routing of a packet.
TTL
19
Length
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Data
Univ. of Tehran
31
Introduction to Computer Network
Pad
(variable)
7
Packet Headers
The current Version is 4 or IPv4.
 HLen- the Header Length: from 5-15 in 32-bit
words.
 Length- the total length of the packet including
headers. Max length is 64K.
TTL: Time To Live is expressed in second. It is to
prevent packet from permanently circulating in a
loop.
 Protocol: specify the packet application ex. 1 for
ICMP. It is for demultiplexing to higher layer
protocols.
 Checksum: is a 1-complement error checksum for
the header only.
Univ. of Tehran
Introduction to Computer Network
8
Packet Headers (Cont)

TOS: type of Service

Precedence
Specify the priority

Type of Services
0
2 | 3
Precedence
7
Type of service
D
T
R
C
Specify routing, for instance cheapest, fastest and
more reliable

D for Delay

T for Throughput

R for Reliability

C for low cost.

Note: Precedence is only for inside
channel queuing.
Univ. of Tehran
Introduction to Computer Network
9
Packet Headers (Cont)

Options
C
Class
Number
If C set, the option will copied to all fragments.
Otherwise, only to the first one.

Class 0 for control

Class 2 for debugging and measurement.
Options are rarely used in today except for
‘loose’ and ‘strict’ source routing parameters.
‘loose’ and ‘strict’ source option sometimes, is
used for IP encapsulation in another IP or
“Tunneling”
Univ. of Tehran
Introduction to Computer Network
10
Fragmentation and Reassembly
0
7|0
7|0
Identification
4
7|0
Flags
 Flags
 DF: Don’t Fragment
 MF: More Fragment coming
7
Fragment Offset
0
1
2
0
DF
MF
In fragmentation, IP copy the original header and only modify
The length, which is the new length, and offset.
Offset is used for reassembly.
 Note: Fragmentation may degrade the network performance.
That is why the IP packet should be the same of TCP packets
Modern TCP implement “Path MTU discovery”.
It start with large packet and with DF set flag, if it passed
TCP keeps the same packet size, otherwise, it reduces it.
Univ. of Tehran
Introduction to Computer Network
11
Fragmentation and Reassembly
(cont)


Each network has a Maximum Transfer Unit size,
MTU
Strategy
 fragment when necessary (MTU < Datagram)
 try to avoid fragmentation at source host
 re-fragmentation is possible
 fragments are self-contained datagrams
 use CS-PDU (not cells) for ATM
 delay reassembly until destination host
 do not recover from lost fragments
Univ. of Tehran
Introduction to Computer Network
12
Example
• Packet delivery from host H1 to host H8
H1
R1
ETH IP(1400)
Univ. of Tehran
R2
FDDIIP(1400)
R3
H8
PPP IP(512)
ETH IP(512)
PPP IP(512)
ETH IP(512)
PPP IP(376)
ETH IP(376)
Introduction to Computer Network
13
Example (cont)
The packets are fragmented as:
Start of header
Ident = x
1
Offset = 0
Rest of header
Start of header
Ident = x
0
512 data bytes
Offset = 0
Rest of header
1400 data bytes
Start of header
Ident= x
1 Offset= 512
Rest of header
512 data bytes
Start of header
Ident = x
0 Offset= 1024
Rest of header
376 data bytes
Univ. of Tehran
Introduction to Computer Network
14
Addressing

Each host in the network is identified by an
address having the following property.



globally unique
hierarchical: network + host
Address Classes


Class D for Multicasting
Class E for experiments
A:
B:
7
24
0 Network
1 0
Host
14
16
Network
Host
21

Address Notation



C:
1 1 0
Network
8
Host
10.3.2.4
128.96.33.81
192.12.69.77
Univ. of Tehran
Introduction to Computer Network
15
IP Addresses
Example:
Class “A” address
www.mit.edu
18.181.0.31
(18<128 => Class A)
Class “B” address
Class C)
Univ. of Tehran
mekong.stanford.edu
171.64.74.155
(128<171<128+64 =>
www.ece.ut.ac.ir
194.225.
Introduction to Computer Network
16
Addressing in IP




IP addresses are names of interfaces
Domain Name System (DNS) names are
names of hosts
DNS binds host names to interfaces
Routing binds interface names to paths
Univ. of Tehran
Introduction to Computer Network
17
How to assign IP Addresses?

Manually



Uniqueness
Too much and tedious job
Dynamically: use DHCP: Dynamic Host
Configuration Protocol.
Univ. of Tehran
Introduction to Computer Network
18
Making a Forwarding Decision
IP Address Space
Class A
Class B
Class A
212.17.9.4
Class B
Class C
Univ. of Tehran
Class C
D
Routing Table:
Exact
Match
212.17.9.0
Introduction to Computer Network
212.17.9.0 Port 4
19
Forwarding Datagrams



Every datagram contains a destination
address.
“Network ID” uniquely identifies a
physical network.
All hosts and routers sharing a Network
ID share same physical network.
Univ. of Tehran
Introduction to Computer Network
20
Forwarding 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 the outgoing interface.
• Transmit packet onto link.
Univ. of Tehran
Introduction to Computer Network
21
Address Translation

Map IP addresses into physical addresses



Techniques



destination host
next hop router
encode physical address in host part of IP address
table-based
ARP




table of IP to physical address bindings
broadcast request if IP address not in table
target machine responds with its physical address
table entries are discarded if not refreshed
Univ. of Tehran
Introduction to Computer Network
22
ARP Details

Request Format






HardwareType: type of physical network (e.g., Ethernet)
ProtocolType: type of higher layer protocol (e.g., IP)
HLEN & PLEN: length of physical and protocol addresses
Operation: request or response
Source/Target-Physical/Protocol addresses
Notes




table entries timeout in about 10 minutes
update table with source when you are the target
update table if already have an entry
do not refresh table entries upon reference
Univ. of Tehran
Introduction to Computer Network
23
ARP Packet Format
0
8
16
Hardware type = 1
HLen = 48
31
ProtocolType = 0x0800
PLen = 32
Operation
SourceHardwareAddr (bytes 0 – 3)
SourceHardwareAddr (bytes 4
SourceProtocolAddr (bytes 2
– 5) SourceProtocolAddr (bytes 0
– 3)
– 1)
TargetHardwareAddr (bytes 0 – 1)
TargetHardwareAddr (bytes 2
TargetProtocolAddr (bytes 0
– 5)
– 3)
•HLen = Hardware Address Length
•PLen = Protocol Address Length
Univ. of Tehran
Introduction to Computer Network
24
Internet Control Message
Protocol (ICMP)







Echo (ping)
Redirect (from router to source host)
Destination unreachable (protocol, port,
or host)
TTL exceeded (so datagrams don’t cycle
forever)
Checksum failed
Reassembly failed
Cannot fragment
Univ. of Tehran
Introduction to Computer Network
25
Tunneling


Big companies having different networks want to
connect them together.
Virtual Private Network (VPN)


Use leased line to connect networks.
Use Internet (Shared line).
Network 1

Sloution

R1
Internet
R2
Network 2
Virtual line
Encapsulate packets in R1 in IP packets for destination
R2.
Univ. of Tehran
Introduction to Computer Network
26
IP Address Problem (1991)

Inefficient use of Hierarchical Address Space



class C with 2 hosts (2/255 = 0.78% efficient)
class B with 256 hosts (256/65535 = 0.39%
efficient)
Address space depletion




In danger of running out of classes A and B
Class C too small for most domains
Very few class A – IANA (Internet Assigned
Numbers Authority) very careful about giving
Class B – greatest problem
Univ. of Tehran
Introduction to Computer Network
27
Solutions for IP Address

Better utilize address space




Subnetting
Supperneting
Locally use unofficial IP addresses (NATing)
Use wider IP addresses

New version of IP, IPv6.
Univ. of Tehran
Introduction to Computer Network
28
Subnetting

Add another level to address/routing hierarchy:

subnet
Subnet masks define variable partition of host part

Subnets visible only within site
Network number
Host number
Class B address
1111111111111111111
0000000000000000
Subnet mask (255.255.0.0)
Network number
Univ. of Tehran
Subnet ID
Subnetted address
Host ID
Introduction to Computer Network
29
Subnet Example
Subnet
Net
host
Subnet mask: 255.255.255.128.
Subnet number: 128.96.34.0
128.96.34.15
H1
111….1.0xxx….x
128.96.34.1
R1
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.128
128.96.34.130
128.96.34.139
128.96.34.129
H3
128.96.33.14
H2
R2
128.96.33.1 Forwarding
Subnet mask: 255.255.255.0
Subnet number: 128.96.33.0
Univ. of Tehran
table at router R1
Subnet #
128.96.34.0
128.96.34.128
128.96.33.0
Subnet Mask
255.255.255.128
255.255.255.128
255.255.255.0
Introduction to Computer Network
Next Hop
interface 0
interface 1
R2
30
Forwarding Algorithm
D = destination IP address
for each entry (SubnetNum, SubnetMask, NextHop)
D1 = SubnetMask & D
if D1 = SubnetNum
if NextHop is an interface
deliver datagram directly to D
else
deliver datagram to NextHop




Use a default router if nothing matches
Not necessary for all 1s in subnet mask to be
contiguous
Can put multiple subnets on one physical network
Subnets
not visible
fromtothe
rest
of the Internet 31
Univ. of Tehran
Introduction
Computer
Network
Supernetting



Assign block of contiguous network numbers to
nearby networks
Called CIDR: Classless Inter-Domain Routing
Represent blocks with a single pair
(first_network_address, count)



Restrict block sizes to powers of 2
Use a bit mask (CIDR mask) to identify block size
All routers must understand CIDR addressing
Univ. of Tehran
Introduction to Computer Network
32
IP Address Utilization (‘98)
http://www.caida.org/outreach/resources/learn/ipv4space/
Univ. of Tehran
Introduction to Computer Network
33
Classless Addressing
CIDR
Class-based:
A
0
Classless:
B
128.9.0.0
65/8
0
C
D
232-1
142.12/19
128.9/16
216
232-1
128.9.16.14
Univ. of Tehran
Introduction to Computer Network
34
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”
Univ. of Tehran
Introduction to Computer Network
35
Forwarding Datagrams
128.17.20.1
R2
1
R1 2
3
R3
R4
128.17.16.1
Univ. of Tehran
e.g. 128.9.16.14 => Port 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
1
7
2
1
3
Introduction to Computer Network
36
Default Routing
R1
Default
Routing
R2
Univ. of Tehran
R3
Requires
Routing
Table
R4
Introduction to Computer Network
R5
Default
Routing
37
Inside a Router
1.
Forwarding
Table
2.
3.
Output
Scheduling
Interconnect
Forwarding
Decision
Forwarding
Table
Forwarding
Decision
Forwarding
Table
Forwarding
Decision
Univ. of Tehran
Introduction to Computer Network
38
NAT: Network Address Translation

IP addresses need to be unique when we are going
outside of our network.

We can use whatever IP address as long as we are
functioning inside our own network.
Univ. of Tehran
Introduction to Computer Network
39
IP Version 6

Features








128-bit addresses (classless)
multicast
real-time service
authentication and security
autoconfiguration
Any cast address
protocol extensions
Header


40-byte “base” header
extension headers (fixed order, mostly fixed length)




No fragmentation
source routing
authentication and security
other options
Univ. of Tehran
Introduction to Computer Network
40
IPV6: Packet format
0
4
Version
12
16
24
31
FlowLabel
TrafficClass
PayloadLen
NextHeader
HopLimit
…
SourceAddr (16 bytes)
…
DestinationAddr (16 bytes)
Next header/ Data

Next header: IP option and protocol fields in IPv4. If options
(i.e. fragmentation) indicated by this field, otherwise, it is
protocol fields.
Univ. of Tehran
Introduction to Computer Network
41