Transcript Introduction - Ilam university

Introduction to
Computer Networks
Internetworking
Ilam University
By: Dr. Mozafar Bag-Mohammadi
1
Internetworking


Communication between networks.
Problems:



Different Networking technologies (Heterogeneity).
So many Networks (Scaling).
Some terminologies:



“internetworking” refer to an arbitrary collection of
connected networks.
“Internet” the global internetwork.
“Network” either directly connected or switched
network using any LAN technology such as
Ethernet, Token ring, ATM, etc.
2
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
H6
3
IP Internet (cont)

Protocol Stack
H1
H8
TCP
R1
IP
IP
ETH

ETH
R2
R3
IP
FDDI
FDDI
IP
PPP
PPP
TCP
IP
ETH
ETH
Everything is running on top IP
4
Source Routing
0 Switch 1
3
0
1
2 Switch 2
2
3 0 1
3
3
1
1
2
1 3 0
0
Host A
0 1 3
1
0 Switch 3
3
2
Host B
• All routing information is provided by the source.
•The address can be implemented by a linked list in the packet header.
5
Networking Technologies
Circuit Based
(constant rate)
Packet Based
(variable rate, store-and-forward)
TDM Telephony
SONET/SDH
DWDM
Virtual Circuits
Frame Relay
ATM
X.25
Connection Oriented
Connectionless
CLNP (ISO)
SNA (IBM)
Appletalk
IPX (Novell)
IP
6
Virtual Circuit Switching

Problems with source routing:



The source must know the whole topology of
network.
The number of switches (header) is variable.
2nd solution: use the telephone model or virtual
circuits.



Explicit connection setup (and tear-down) phase. This
is called signaling.
Each flow is identified by a Virtual Circuits Identifier
(VCI).
Switch needs to maintains a VC table.
7
Virtual Circuit Switching (cont)




Subsequence packets follow the same circuit
Sometimes called connection-oriented model.
VCIs is swapped in the switches.
Example: Lookup table.
In-port
0
3
In-VCI
Out-port
Out-VCI
2
5
1
11
3
11
0
7
Switch 1
1
2
2
5
3
11
Switch 2
1
0
Host A
7
0
1
Switch 3
3
4
2
Host B
8
Virtual Circuit Model

Typically wait full RTT for connection setup
before sending first data packet.

While the connection request contains the full
address for destination, each data packet
contains only a small identifier, making the perpacket header overhead small.

If a switch or a link on the path fails, the
connection is broken and a new one needs to be
established.

Connection setup provides an opportunity to
reserve resources.
9
Datagram Switching




No connection setup phase since it is costly.
Each packet forwarded independently
Sometimes called connectionless model
Analogy:
postal system
Host D
0
3
Host C

Each switch
maintains a
forwarding
(routing) table
Host E
Switch 1
1
2
2
3
Host F
Switch
2
1
0
Host A
Host 1G
0 Switch 3 Host B
3
2
Host H
10
Datagram Model

There is no round trip time delay waiting for connection
setup; a host can send data as soon as it is ready.

Source host has no way of knowing if the network is
capable of delivering a packet or if the destination host
is even up.

Since packets are treated independently, it is possible
to route around link and node failures.

Since every packet must carry the full address of the
destination, the overhead per packet is higher.
11
Connection Oriented vs.
Connectionless
Connection Oriented
• Connection set up. Signaling reserves resources along
the end-to-end path
• Traffic flows
• Connection torn down and resources freed
Connectionless
•Best-effort delivery (Send and Pray)
•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
12
Encapsulation Example
Ethernet Header
IP Header
TCP Header
HTTP Header
….
An Ethernet
segment
transmitting
HTTP data.
HTTP Data
….
13
IP 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.
0
8
4
Version
HLen
16
TOS
Ident
TTL
19
31
Length
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Data
Pad
(variable)
14
Packet Headers
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.
15
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.
16
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”
17
Fragmentation and Reassembly
0
7|0
Identification
 Flags
 DF: Don’t Fragment
 MF: More Fragment coming
7|0
4
7|0
Flags
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.
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.
18
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
 delay reassembly until destination host
 do not recover from lost fragments
19
Example
• Packet delivery from host H1 to host H8
H1
ETH IP (1400)
R1
R2
FDDI IP (1400)
R3
H8
PPP IP (512)
ETH IP (512)
PPP IP (512)
ETH IP (512)
PPP IP (376)
ETH IP (376)
20
Example (cont)
Start of header
The packets are fragmented as:
Ident = x
1
Offset = 0
Rest of header
512 data bytes
Start of header
Ident = x
0
Start of header
Offset = 0
Rest of header
1400 data bytes
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
21
Addressing

Each host in the network is identified by an address
having the following property.


globally unique
hierarchical: network + host
11111111 00010001 10000111 00000000
Network Number
Host Number
22
IPv4 Implementation of Addresses
Thirty Two Bits:
0
8
16
24
11111111 00010001 10000111 00000000
255
17
135
0
255.17.135.0
Dotted Quad notation for “human readability”
23
Classful Addresses
Class A
0nnnnnnn hhhhhhhh hhhhhhhh hhhhhhhh
Class B
10nnnnnn nnnnnnnn hhhhhhhh hhhhhhhh
Class C
110nnnnn nnnnnnnn nnnnnnnn hhhhhhhh
n = network address bit
h = host identifier bit
24
The Classful Address Space
Class
Networks Hosts
Share of IP
address space
16,777,214 1/2
A
127
B
C
16,384
65,534
2,097,152 254
1/4
1/8
Leads to very inefficient allocation of addresses …
25
IP Addresses
Example:
Class “A” address
Class “B” address
www.mit.edu
18.181.0.31
(18<128 => Class A)
mekong.stanford.edu
171.64.74.155
(128<171<128+64 => Class B)
26
Classless Addressing
CIDR
Class-based:
A
B
C
D
232-1
0
Classless:
128.9.0.0
65/8
0
142.12/19
128.9/16
232-1
216
128.9.16.14
27
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”
28
Forwarding Datagrams

“Network ID” uniquely identifies a physical
network.



All hosts and routers sharing a Network ID share
same physical network.
Every datagram contains a destination
address.
Is the datagram for a host on directly
attached network?


If no, consult forwarding table to find next-hop.
If only one next-hop, can use default routing.
29
Forwarding Datagrams
128.17.20.1
R2
1
R1 2
3
R3
R4
128.17.16.1
e.g. 128.9.16.14 => Port 2
Prefix
65/8
128.17.14.1
128.9/16
128.9.16/20
128.9.19/24
128.9.25/24
128.9.176/20
142.12/19
Next-hop
Port
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
30
Default Routing
R1
Default
Routing
R2
R3
Requires
Routing
Table
R4
R5
Default
Routing
31
Address Translation

Map IP addresses into physical addresses



destination host
next hop router
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
32
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
33
ARP Packet Format
0
8
16
Hardware type = 1
HLen = 48
31
ProtocolT ype = 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)
34
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
35
Inside a Router
1.
Forwarding
Table
2.
3.
Output
Scheduling
Interconnect
Forwarding
Decision
Forwarding
Table
Forwarding
Decision
Forwarding
Table
Forwarding
Decision
36
IP Forwarding Process
1. Remove a packet
from an input
queue
2. Check for sanity,
decrement TTL
field
4. Place packet on
correct output
queue
Forwarding Process
If queues
get full, just
drop packets!
3. Match packet’s
destination to
a table entry
If queues
get full, just
drop packets!
IP Forwarding Table
Router
37