Transcript ppt

Introduction to Computer
Networks
CMPE 150
Fall 2005
Lecture 24
CMPE 150- Introduction to Computer Networks
1
Announcements
• Homework 4 due on Wed.,11.23.05.
• No class on Friday, 11.25.05.
• We will have a “real” lab this week.
– Routing with RIP.
– Print lab description before going to your lab
session.
• Midterm statistics:
– Average: 54.07
– Std. deviation: 18.21
CMPE 150- Introduction to Computer Networks
2
Last Class…
• Finished routing.
• Internetworking.
–
–
–
–
–
Interconnecting networks.
Heterogeneity.
Different approaches to internetworking.
Translating versus gluing.
Tunneling.
CMPE 150- Introduction to Computer Networks
3
Today
• Internetworking (cont’d).
• IP.
CMPE 150- Introduction to Computer Networks
4
Internetworking
CMPE 150- Introduction to Computer Networks
5
Internetwork Routing
• Inherently hierarchical.
– Routing within each network: interior gateway
protocol (IGP).
– Routing between networks: exterior gateway
protocol (EGP).
• Within each network, different routing
algorithms can be used.
• Each network is autonomously managed
and independent of others: autonomous
system (AS).
CMPE 150- Introduction to Computer Networks
6
Internetwork Routing: Example
• (a) An internetwork. (b) A graph of the internetwork.
CMPE 150- Introduction to Computer Networks
7
Internetwork Routing (Cont’d)
• Typically, packet starts in its LAN. Gateway
receives it (broadcast on LAN to “unknown”
destination).
• Gateway sends packet to gateway on the
destination network using its routing table. If it
can use the packet’s native protocol, sends
packet directly. Otherwise, tunnels it.
CMPE 150- Introduction to Computer Networks
8
Fragmentation
• Happens when internetworking.
• Network-specific maximum packet size.
– Width of TDM slot.
– OS buffer limitations.
– Protocol (number of bits in packet length field).
• Maximum payloads range from 48 bytes (ATM
cells) to 64Kbytes (IP packets).
CMPE 150- Introduction to Computer Networks
9
Problem
• What happens when large packet wants to
travel through network with smaller
maximum packet size? Fragmentation.
• Gateways break packets into fragments;
each sent as separate packet.
• Gateway on the other side have to
reassemble fragments into original packet.
• 2 kinds of fragmentation: transparent and
non-transparent.
CMPE 150- Introduction to Computer Networks
10
Types of Fragmentation
• (a) Transparent fragmentation. (b)
Nontransparent fragmentation.
Transparent Fragmentation
Non-Transparent Fragmentation
CMPE 150- Introduction to Computer Networks
11
Transparent Fragmentation
• Small-packet network transparent to other
subsequent networks.
• Fragments of a packet addressed to the
same exit gateway, where packet is
reassembled.
– OK for concatenated VC internetworking.
• Subsequent networks are not aware
fragmentation occurred.
• ATM networks (through special hardware)
provide transparent fragmentation.
CMPE 150- Introduction to Computer Networks
12
Problems with Transparent
Fragmentation
• Exit gateway must know when it received
all the pieces.
– Fragment counter or “end of packet” bit.
• Some performance penalty but requiring
all fragments to go through same gateway.
• May have to repeatedly fragment and
reassemble through series of small-packet
networks.
CMPE 150- Introduction to Computer Networks
13
Non-Transparent
Fragmentation
• Only reassemble at destination host.
– Each fragment becomes a separate packet.
– Thus routed independently.
• Problems:
– Hosts must reassemble.
– Every fragment must carry header until it reaches
destination host.
CMPE 150- Introduction to Computer Networks
14
Keeping Track of Fragments
•
•
Fragments must be numbered so that
original data stream can be
reconstructed.
Tree-structured numbering scheme:
–
–
–
–
Packet 0 generates fragments 0.0, 0.1, 0.2, …
If these fragments need to be fragmented later
on, then 0.0.0, 0.0.1, …, 0.1.0, 0.1.1, …
But, too much overhead in terms of number of
fields needed.
Also, if fragments are lost, retransmissions can
take alternate routes and get fragmented
differently.
CMPE 150- Introduction to Computer Networks
15
Keeping Track of Fragments
(Cont’d)
• Another way is to define elementary
fragment size that can pass through every
network.
• When packet fragmented, all pieces equal
to elementary fragment size, except last
one (may be smaller).
• Packet may contain several fragments.
CMPE 150- Introduction to Computer Networks
16
Keeping Track of Fragments
• Header contains packet number, number of first
fragment in the packet, and last-fragment bit.
Last-fragment bit
E F G H I
27 0 1 A B C D
Number of
first fragment
Packet number
27 0
0 A B
C D
E
F
G
H
1 byte
J
(a) Original packet
with 10 data bytes.
27 8
1 I
J
(b) Fragments after passing through network
with maximum packet size = 8 bytes.
CMPE 150- Introduction to Computer Networks
17
The Internet
CMPE 150- Introduction to Computer Networks
18
Design Principles for Internet
•
•
•
•
•
•
•
Keep it simple.
Exploit modularity.
Expect heterogeneity.
Think robustness.
Avoid static options and parameters.
Think about scalability.
Consider performance and cost.
CMPE 150- Introduction to Computer Networks
19
Internet as Collection of
Subnetworks
CMPE 150- Introduction to Computer Networks
20
IP (Internet Protocol)
• Glues Internet together.
• Common network-layer protocol spoken
by all Internet participating networks.
• Best effort datagram service:
– No reliability guarantees.
– No ordering guarantees.
CMPE 150- Introduction to Computer Networks
21
IP
• Transport layer breaks data streams into
datagrams; fragments transmitted over Internet,
possibly being fragmented.
• When all packet fragments arrive at destination,
reassembled by network layer and delivered to
transport layer at destination host.
CMPE 150- Introduction to Computer Networks
22
IP Versions
• IPv4: IP version 4.
– Current, predominant version.
– 32-bit long addresses.
• IPv6: IP version 6 (aka, IPng).
– Evolution of IPv4.
– Longer addresses (16-byte long).
CMPE 150- Introduction to Computer Networks
23
IP Datagram Format
• IP datagram consists of header and data (or
payload).
• Header:
– 20-byte fixed (mandatory) part.
– Variable length optional part.
CMPE 150- Introduction to Computer Networks
24
The IP v4 Header
CMPE 150- Introduction to Computer Networks
25
IP Options
5-54
CMPE 150- Introduction to Computer Networks
26
IP Addresses
• IP address formats.
CMPE 150- Introduction to Computer Networks
27
IP Addresses (Cont’d)
• Class A: 128 networks with 16M hosts each.
• Class B: 16,384 networks with 64K hosts
each.
• Class C: 2M networks with 256 hosts each.
• More than 500K networks connected to the
Internet.
• Network numbers centrally administered by
ICANN.
CMPE 150- Introduction to Computer Networks
28
IP Addresses (Cont’d)
• Special IP addresses.
CMPE 150- Introduction to Computer Networks
29
Scalability of IP Addresses
• Problem: a single A, B, or C address refers to
a single network.
• As organizations grow, what happens?
CMPE 150- Introduction to Computer Networks
30
Example: A Campus Network
CMPE 150- Introduction to Computer Networks
31
Solution
• Subnetting: divide the organization’s address
space into multiple “subnets”.
• How? Use part of the host number bits as the
“subnet number”.
• Example: Consider a university with 35
departments.
– With a class B IP address, use 6-bit subnet
number and 10-bit host number.
– This allows for up to 64 subnets each with
1024 hosts.
CMPE 150- Introduction to Computer Networks
32
Subnets
• A class B network subnetted into 64 subnets.
CMPE 150- Introduction to Computer Networks
33
Subnet Mask
• Indicates the split between network and subnet
number + host number.
Subnet Mask: 255.255.252.0 or
/22 (network + subnet part)
CMPE 150- Introduction to Computer Networks
34
Subnetting: Observations
• Subnets are not visible to the outside world.
• Thus, subnetting (and how) is a decision
made by local network admin.
CMPE 150- Introduction to Computer Networks
35
Subnet: Example
• Subnet 1: 10000010 00110010 000001|00 00000001
– 130.50.4.1
• Subnet 2: 10000010 00110010 000010|00 00000001
– 130.50.8.1
• Subnet 3: 10000010 00110010 000011|00 00000001
– 130.50.12.1
CMPE 150- Introduction to Computer Networks
36