Transcript A(t)

An Introduction
to
Computer Networks
Lecture 2: Foundation
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
1
Outline






Objectives
Statistical Multiplexing
Inter-Process Communication
Network Architecture
Layering
Performance
Univ. of Tehran
Introduction to computer Network
2
Introduction

Building a network to support diverse
ranges of applications





Distributed computing.
Multimedia.
Telecommunication.
E-commerce, etc.
What kind of technology do we need?


Hardware.
Software.
Univ. of Tehran
Introduction to computer Network
3
First Step

What is computer Network?



Different views.
Differences from other networks, Its
generality.
What is requirements? Different
perspective:



Network provider
Network designer
Application programmer
Univ. of Tehran
Introduction to computer Network
4
Design goals



Connectivity
Scalability
Simplicity



Efficiency



For designers.
Most importantly for users.
cost
performance
Support for common user services.
Univ. of Tehran
Introduction to computer Network
5
An Ex. the mail system
Stanford
MIT
Nick
Dave
Admin
Admin
Univ. of Tehran
Introduction to computer Network
6
Characteristics of the mail system
 Each
envelope is individually routed.
 No time guarantee for delivery.
 No guarantee of delivery in sequence.
 No guarantee of delivery at all!
 Things
get lost
 How can we acknowledge delivery?
 Retransmission
 How
to determine when to retransmit? Timeout?
 Need local copies of contents of each envelope.
 How long to keep each copy.
 What if an acknowledgement is lost?
Univ. of Tehran
Introduction to computer Network
7
The mail system
Stanford
MIT
Application Layer
Nick
Dave
Transport Layer
Admin
Admin
Network Layer
Link Layer
Univ. of Tehran
Introduction to computer Network
8
The Internet
Leland.Stanford.edu
Athena.MIT.edu
Application Layer
Nick
Dave
Transport Layer
O.S.
Datagram
Data
Header
Data
Header
O.S.
Network Layer
Link Layer
Univ. of Tehran
Introduction to computer Network
9
Characteristics of the Internet
 Each
packet is individually routed.
 No time guarantee for delivery.
 No guarantee of delivery in sequence.
 No guarantee of delivery at all!
 Things
get lost
 Acknowledgements
 Retransmission
 How
to determine when to retransmit? Timeout?
 Need local copies of contents of each packet.
 How long to keep each copy?
 What if an acknowledgement is lost?
Univ. of Tehran
Introduction to computer Network
10
Characteristics of the Internet (2)
 No
guarantee of integrity of data.
 Packets can be fragmented.
 Packets may be duplicated.
Univ. of Tehran
Introduction to computer Network
11
An Introduction to the mail
system
Stanford
MIT
Application Layer
Nick
Dave
Transport Layer
Admin
Admin
Network Layer
Link Layer
Univ. of Tehran
Introduction to computer Network
12
Some questions about the mail
system
 How
many sorting offices are needed
and where should they be located?
 How much sorting capacity is needed?
 Should
 How
we allocate for Mother’s Day?
can we guarantee timely delivery?
 What
prevents delay guarantees?
 Or delay variation guarantees?
 How
do we protect against fraudulent
mail deliverers, or fraudulent senders?
Univ. of Tehran
Introduction to computer Network
13
More questions about the mail
system
 What
happens when a router fails?
 How can we prevent swamping the
routers with data too quickly?
 How can we prevent sending data too
slowly?
Univ. of Tehran
Introduction to computer Network
14
Building Blocks

Nodes: PC, special-purpose hardware…



hosts
switches, routers and gateways
Links: coax cable, optical fiber…

point-to-point

multiple access
Univ. of Tehran
Introduction to computer Network
…
15
Switched Networks
A network can be defined recursively as...

two or more nodes
connected by a link,
or
Univ. of Tehran
two or more networks
connected by two or
more nodes
Introduction to computer Network
16
Strategies

Circuit switching: carry bit streams




Packet switching: store-and-forward messages




Connection oriented.
original telephone network
Dedicated resource.
Connectionless (IP) or connection oriented (ATM)
Internet
Shared resource.
Packet switching is the focus of computer
Networks.
Univ. of Tehran
Introduction to computer Network
17
Circuit Switching
A
B
Source


Destination
It’s the method used by the telephone network.
A call has three phases:
1. Establish circuit from end-to-end (“dialing”),
2. Communicate,
3. Close circuit (“tear down”).


Originally, a circuit was an end-to-end physical wire.
Nowadays, a circuit is like a virtual private wire: each
call has its own private, guaranteed data rate from endto-end.
Univ. of Tehran
Introduction to computer Network
18
Circuit Switching
Telephone Network
Each phone call is allocated
64kb/s. So, a 2.5Gb/s trunk line
can carry about 39,000 calls.
Destination
“Callee”
Source
“Caller”
Central
Office
“C.O.”
Central
Office
“C.O.”
Trunk
Exchange
Univ. of Tehran
Introduction to computer Network
19
Packet Switching
A
Source
B
R2
R1
R3
Destination
R4





It’s the method used by the Internet.
Each packet is individually routed packet-by-packet,
using the router’s local routing table.
The routers maintain no per-flow state.
Different packets may take different paths.
Several packets may arrive for the same output link at
the same time, therefore a packet switch has buffers.
Univ. of Tehran
Introduction to computer Network
20
Packet Switching
Simple router model
“4” Link 1, ingress
Choose
Egress
Link 1, egress
Link 2, ingress
Choose
Egress
Link 2, egress
Link 3, ingress
Choose
Egress
Link 3, egress
Link 4, ingress
Choose
Egress
Link 4, egress
Link 2
Link 1
R1“4”
Link 3
Link 4
Univ. of Tehran
Introduction to computer Network
21
Addressing and Routing

Address: byte-string that identifies a node



usually unique
Routing: process of forwarding messages
to the destination node based on its
destination address
Types of addresses



unicast: node-specific
broadcast: all nodes on the network
multicast: some subset of nodes on the
network
Univ. of Tehran
Introduction to computer Network
22
Multiplexing (resource sharing)


Time-Division Multiplexing (TDM)
Frequency-Division Multiplexing (FDM)
L1
R1
L2
R2
L3
Univ. of Tehran
Switch 1
Switch 2
Introduction to computer Network
R3
23
Statistical Multiplexing



On-demand time-division
Schedule link on a per-packet basis
Packets from different sources interleaved on link




scheduling
fairness, quality of service
Buffer packets that are contending for the link
Buffer (queue) overflow is called congestion
…
Univ. of Tehran
Introduction to computer Network
24
Statistical Multiplexing
Basic idea
rate
One flow
rate
Two flows
Average
rate
time
rate
time
 Network traffic is bursty.
i.e. the rate changes frequently.
 Peaks from independent flows
generally occur at different times.
 Conclusion: The more flows we have,
the smoother the traffic.
Univ. of Tehran
Many flows
Introduction to computer Network
Average rates of:
1, 2, 10, 100,
1000 flows.
time
25
Packet Switching
Statistical Multiplexing
Packets for
one output
1
Data
Hdr
2
Data
Hdr
R
R
Queue Length
X(t)
X(t)
Link rate, R
Dropped packets
B
R
N
Data


Hdr
Packet
buffer
Time
Because the buffer absorbs temporary bursts, the egress link
need not operate at rate (NxR).
But the buffer has finite size, B, so losses will occur.
Univ. of Tehran
Introduction to computer Network
26
Statistical Multiplexing
Rate
A
C
A
C
B
C
time
Rate
B
C
time
Univ. of Tehran
Introduction to computer Network
27
Statistical Multiplexing Gain
Rate
A+B
2C
R < 2C
A
R
B
time
Statistical multiplexing gain = 2C/R
Other definitions of SMG: The ratio of rates that give rise to
a particular queue occupancy, or particular loss probability.
Univ. of Tehran
Introduction to computer Network
28
Why does the Internet use
packet switching?
Efficient use of expensive links:
1.



The links are assumed to be expensive and scarce.
Packet switching allows many, bursty flows to share the
same link efficiently.
“Circuit switching is rarely used for data networks, ...
because of very inefficient use of the links” - Gallager
Resilience to failure of links & routers:
2.

”For high reliability, ... [the Internet] was to be a datagram
subnet, so if some lines and [routers] were destroyed,
messages could be ... rerouted” - Tanenbaum
Univ. of Tehran
Introduction to computer Network
29
Some Definitions






Packet length, P, is the length of a packet in bits.
Link length, L, is the length of a link in meters.
Data rate, R, is the rate at which bits can be sent, in
bits/second, or b/s.1
Propagation delay, PROP, is the time for one bit to travel
along a link of length, L.
PROP = L/c.
Transmission time, TRANSP, is the time to transmit a
packet of length P.
TRANSP = P/R.
Latency is the time from when the first bit begins
transmission, until the last bit has been received. On a
link: 1. Note that a kilobit/second, kb/s, is 1000 bits/second, not 1024 bits/second.
Latency = PROP + TRANSP.
Univ. of Tehran
Introduction to computer Network
30
Packet Switching
A
B
R2
Source
R1
R3
Destination
R4
Host A
TRANSP1
“Store-and-Forward” at each Router
TRANSP2
R1
PROP1
TRANSP3
R2
PROP2
TRANSP4
R3
Host B
PROP3
PROP4
Minimum end to end latency   (TRANSPi  PROPi )
i
Univ. of Tehran
Introduction to computer Network
31
Packet Switching vs. Message
switching
M/R
M/R
Host A
Host A
R1
R1
R2
R2
R3
R3
Host B
Latency   ( PROPi  M / Ri )
Host B
Latency  M / Rmin   PROPi
i
i
Breaking message into packets allows parallel transmission
across all links, reducing end to end latency. It also prevents
a link from being “hogged” for a long time by one message.
Univ. of Tehran
Introduction to computer Network
32
Inter-Process Communication


Turn host-to-host connectivity into processto-process communication regardless where
the process are.
Give a unified view and fill gaps between
what applications expect and what the
underlying technology provides.
Host
Host
Host
Channel
Application
Host
Univ. of Tehran
Application
Host
Introduction to computer Network
33
IPC Abstractions

Common communication patterns.
Request/Reply (Client-server)
1.




distributed file systems (NFS)
digital libraries (web)
File Transfer (FTP)
Guarantee delivering data, and might
protect privacy and integrity also.
Univ. of Tehran
Introduction to computer Network
34
IPC Abstractions(Cont)
2. Stream-Based- sequence or stream of bits.

Video on demand: sequence of frames. Delay constrained,
but can be fetched before hand. For example, a Monitor with
352x240 pixels and 24 bit color.
(352 x 240 x 24)/8=247.5KB
Assuming 30 frame per second => 7500KBps = 60Mbps
 video Conferencing- tightly delay bounded. VIC From
Berkeley.
 Both application can tolerate packet loss.
Questions?
•What functionality each channel should provide?
•Where the functionality has to be implemented? In the end
points or in the network?
Univ. of Tehran
Introduction to computer Network
35
Reliability in the network?
What Goes Wrong in the Network?
 Bit-level errors (electrical interference), a
bit is corrupted or a burst error.
 Packet-level errors (congestion)




Messages are delayed
Messages are deliver out-of-order
Third parties eavesdrop, (lost packets)
Link and node failures
Univ. of Tehran
Introduction to computer Network
36
Layering



Use abstractions to hide complexity and
decompose to manageable components.
Abstraction naturally lead to layering
Alternative abstractions at each layer
Application programs
Request/Reply Message Stream
channel
channel
Host-to-host connectivity
Hardware
Univ. of Tehran
Introduction to computer Network
37
Layering

Advantages




Modularity – protocols are easier to manage
and maintain
Abstract functionality –lower layers can be
changed without affecting the upper layers
Reuse – upper layers can reuse the
functionality provided by lower layers
Disadvantages

Information hiding – inefficient
implementations
Univ. of Tehran
Introduction to computer Network
38
Protocols


Building blocks of a network architecture,
or layer abstraction.
Each protocol object has two different
interfaces



service interface: operations on this protocol
peer-to-peer interface: messages exchanged
with peer
Term “protocol” is overloaded


specification of peer-to-peer interface
module that implements this interface
Univ. of Tehran
Introduction to computer Network
39
Interfaces
Host 2
Host 1
High-level
object
Protocol
Univ. of Tehran
Service
interface
Peer-to-peer
interface
High-level
object
Protocol
Introduction to computer Network
40
Protocol Machinery

Protocol Graph



Nodes are protocols and edges are depend on.
most peer-to-peer communication is indirect
peer-to-peer is direct only at hardware level
Host 2
Host 1
File
application
Digital
Video
library
application application
MSP
RRP
HHP
Univ. of Tehran
File
application
Digital
Video
library
application
application
MSP
RRP
HHP
41
Protocol Machinery (cont)


Multiplexing and Demultiplexing (demux
key)
Encapsulation (header/body)
Host 2
Host 1
Application
program
Application
program
Data
Data
RRP
RRP
RRP Data
RRP Data
HHP
HHP
HHP RRP Data
Univ. of Tehran
42
ISO OSI Reference Model



ISO – International Standard Organization
OSI – Open System Interconnection
Started to 1978; first standard 1979


ARPANET started in 1969; TCP/IP protocols
ready by 1974
Goal: a general open standard

allow vendors to enter the market by using their
own implementation and protocols
Univ. of Tehran
Introduction to computer Network
43
ISO Architecture
End host
Telnet, FTP, TFTP
MSB, integer
Manage TCP streams
Message, P2P(process)
Packet, routing
Frame, CRC
Raw bit pipe
End host
Application
Application
Presentation
Presentation
Session
Session
Transport
Transport
Network
Network
Network
Network
Data link
Data link
Data link
Data link
Physical
Physical
Physical
Physical
One or more nodes
within the network
•The last 3 protocols are implemented in all elements in the
Network.
Univ. of Tehran
Introduction to computer Network
44
Encapsulation


A layer can use only the service provided by the
layer immediate below it
Each layer may change and add a header to data
packet
data
data
data
data
data
data
data
data
data
data
data
data
data
data
Univ. of Tehran
Introduction to computer Network
45
OSI Model Concepts



Service – says what a layer does
Interface – says how to access the
service
Protocol – Says how the communication
is done and how is the service
implemented

a set of rules and formats that govern the
communication between two peers
Univ. of Tehran
Introduction to computer Network
46
Physical Layer (1)




Service: move the information between
two systems connected by a physical link
Interface: specifies how to send a bit
Protocols: coding scheme used to
represent a bit, voltage levels, duration of
a bit
Examples: coaxial cable, optical fiber
links; transmitters, receivers
Univ. of Tehran
Introduction to computer Network
47
Datalink Layer (2)

Service:



framing, i.e., attach frame separators
send data frames between peers
others:





arbitrate the access to common physical media
ensure reliable transmission
provide flow control
Interface: send a data unit (packet) to a
machine connected to the same physical media
Protocols: layer addresses, implement Medium
Access Control (MAC) (e.g., CSMA/CD)…
Univ. of Tehran
Introduction to computer Network
48
Network Layer (3)

Service:



deliver a packet to specified destination
perform segmentation/reassemble
others:




packet scheduling
buffer management
Interface: send a packet to a specified
destination
Protocols: define global unique
addresses; construct routing tables
Univ. of Tehran
Introduction to computer Network
49
Transport Layer (4)

Services:






provide an error-free and flow-controlled end-to-end
connection
multiplex multiple transport connections to one
network connection
split one transport connection in multiple network
connections
Interface: send a packet to specify destination
Protocols: implement reliability and flow control
Examples: TCP and UDP
Univ. of Tehran
Introduction to computer Network
50
Session Layer (5)

Service:





full-duplex
access management, e.g., token control
synchronization, e.g., provide check points for long
transfers
Interface: depends on service
Protocols: token management; insert
checkpoints, implement roll-back functions
Univ. of Tehran
Introduction to computer Network
51
Presentation Layer (6)



Service: convert data between various
representations
Interface: depends on service
Protocol: define data formats, and rules
to convert from one format to another
Univ. of Tehran
Introduction to computer Network
52
Application Layer (7)

Service: any service provided to the end
user
Interface: depends on the application
Protocol: depends on the application

Examples: FTP, Telnet, WWW browser


Univ. of Tehran
Introduction to computer Network
53
Internet Architecture


Defined by Internet Engineering Task
Force (IETF). Developed in mid 60s in the
ARPANET project.
No assumption about the network tech.
FTP
HTTP
NV
TFTP
UDP
TCP
IP
NET 1
Univ. of Tehran
NET 2
…
Introduction to computer Network
NET n
54
Internet Architecture



Hourglass Design, IP is the focal point.
Delivery is separated from end-to-end
process channel.
No restrict layering
Application vs Application Protocol (FTP,
HTTP)
Application
TCP
UDP
IP
Network
Univ. of Tehran
Introduction to computer Network
55
OSI vs. TCP/IP


OSI: conceptually define services, interfaces,
protocols
Internet: provide a successful implementation
Application
Presentation
Session
Transport
Network
Datalink
Physical
OSI
Univ. of Tehran
Application
Transport
Internet
Host-tonetwork
Telnet
FTP DNS
TCP
UDP
IP
LAN
Packet
radio
TCP
Introduction to computer Network
56
Performance Metrics

Bandwidth (throughput)



data transmitted per time unit
link versus end-to-end
notation



KB = 210 bytes
Mbps = 106 bits per second
Latency (delay)



time to send message from point A to point B
one-way versus round-trip time (RTT)
components
Latency = Propagation + Transmit + Queue
Propagation = Distance / C (light speed)
Transmit = Size / Bandwidth
Univ. of Tehran
Introduction to computer Network
57
Bandwidth versus Latency

Relative importance



Latency bounded- sending 1-byte by client, 1ms vs 100ms
dominates sending a message on a 1Mbps or 100Mbps link
Bandwidth Bounded- sending 25MB image: 1Mbps vs
100Mbps dominates 1ms vs 100ms delayed channel.
Infinite bandwidth


RTT dominates
Throughput = TransferSize / TransferTime
TransferTime = RTT + 1/Bandwidth x TransferSize
1-MB file to 1-Gbps link the same as 1-KB packet to 1-Mbps
link.
Univ. of Tehran
Introduction to computer Network
58
Delay x Bandwidth Product


Amount of data “in flight” or “in the pipe”
Example: 100ms x 45Mbps = 560KB
Delay
Bandwidth
We are usually more interested in 2 times of this value
Since it take RTT to hear from receiver.
Univ. of Tehran
Introduction to computer Network
59
Latency (Queuing Delay)
The egress link might not be free, packets may be queued in a buffer. If
the network is busy, packets might have to wait a long time.
Host A
TRANSP1
Q2
R1
TRANSP2
PROP1
TRANSP3
R2
PROP2
R3
Host B
TRANSP4
How can we
determine the
queuing delay?
PROP3
PROP4
Actual end to end latency   (TRANSPi  PROPi  Qi )
i
Univ. of Tehran
Introduction to computer Network
60
Queues and Queuing Delay



To understand the performance of a packet switched network,
we can think of it as a series of queues interconnected by links.
For given link rates and lengths, the only variable is the
queuing delay.
If we can understand the queuing delay, we can understand
how the network performs.
Univ. of Tehran
Introduction to computer Network
61
Queues and Queuing Delay
Cross traffic causes
congestion and variable
queuing delay.
Univ. of Tehran
Introduction to computer Network
62
A router queue
Model of FIFO router queue
A(t), l
m
D(t)
Q(t)
A(t ) : The arrival process. The number of arrivals in interval [0, t ].
l : The average rate of new arrivals in packets/second.
D(t ) : The departure process. The number of departures in interval [0, t ].
1 : The average time to service each packet.
m
Q(t ): The number of packets in the queue at time t.
Univ. of Tehran
Introduction to computer Network
63
A simple deterministic model
Model of FIFO router queue
A(t), l
m
D(t)
Q(t)
Properties of A(t), D(t):
 A(t), D(t) are non-decreasing
 A(t) >= D(t)
Univ. of Tehran
Introduction to computer Network
64
A simple deterministic model
bytes or “fluid”
Cumulative number of bits
that arrived up until time t.
A(t)
A(t)
Cumulative
number of bits
D(t)
Q(t)
Service
process
m
m
time
D(t)
Cumulative number of
departed bits up until time t.
Univ. of Tehran
Properties of A(t), D(t):
 A(t), D(t) are non-decreasing
 A(t) >= D(t)
Introduction to computer Network
65
Simple deterministic model
Cumulative
number of bits
d(t)
A(t)
Q(t)
D(t)
time
•Queue occupancy: Q(t) = A(t) - D(t).
•Queuing delay, d(t), is the time spent in the queue by
a bit that arrived at time t, and if the queue is served
first-come-first-served (FCFS or FIFO)
Univ. of Tehran
Introduction to computer Network
66
Example
Cumulative
number of bits
Q(t)
d(t)
100
A(t)
D(t)
0.1s
0.2s
1.0s
Example: Every second, a train of
100 bits arrive
at rate 1000b/s. The maximum
departure rate is 500b/s.
What is the average queue
occupancy?
time
Solution: During each cycle, the queue fills at rate 500b/s for 0.1s,
then drains at rate 500b/s for 0.1s.The average queue occupancy when
the queue is non-empty is therefore: (Q (t ) Q(t )  0)  0.5  (0.1 500)  25 bits.
The queue is empty for 0.8s each cycle, and so: Q (t )  (0.2  25)  (0.8  0)  5 bits.
(You'll probably have to think about this for a while...).
Univ. of Tehran
Introduction to computer Network
67
Queues with Random Arrival
Processes
1.
2.
3.
Usually, arrival processes are
complicated, so we often model them as
random processes.
The study of queues with random arrival
processes is called Queueing Theory.
Queues with random arrival processes
have some interesting properties. We’ll
consider some here.
Univ. of Tehran
Introduction to computer Network
68
Properties of queues

Time evolution of queues.

Examples




Burstiness increases delay
Determinism minimizes delay
Little’s Result.
The M/M/1 queue.
Univ. of Tehran
Introduction to computer Network
69
Time evolution of a queue
Packets
Model of FIFO router queue
A(t), l
m
D(t)
Q(t)
Packet
Arrivals:
Departures:
time
1m
Q(t)
Univ. of Tehran
Introduction to computer Network
70
Burstiness increases delay

Example 1: Periodic arrivals




Example 2:





1 packet arrives every 1 second
1 packet can depart every 1 second
Depending on when we sample the queue, it will contain
0 or 1 packets.
N packets arrive together every N seconds (same rate)
1 packet departs every second
Queue might contain 0,1, …, N packets.
Both the average queue occupancy and the variance
have increased.
In general, burstiness increases queue occupancy
(which increases queuing delay).
Univ. of Tehran
Introduction to computer Network
71
Determinism minimizes delay

Example 3: Random arrivals




Packets arrive randomly; on average, 1 packet
arrives per second.
Exactly 1 packet can depart every 1 second.
Depending on when we sample the queue, it will
contain 0, 1, 2, … packets depending on the
distribution of the arrivals.
In general, determinism minimizes delay.
i.e. random arrival processes lead to larger
delay than simple periodic arrival processes.
Univ. of Tehran
Introduction to computer Network
72
Little’s Result
L  ld
Where:
L is the average number of customers in the system
(the number in the queue + the number in service),
l is the arrival rate, in customers per second, and
d is the average time that a customer waits in the
system (time in queue + time in service).
Result holds so long as no customers are lost/dropped.
Univ. of Tehran
Introduction to computer Network
73
The Poisson process
Poisson process is a simple arrival process in which:
1. Probability of k arrivals in an interval of t seconds is:
(l t ) k  l t
Pk (t ) 
e
k!
2. The expected number of arrivals in interval t is: lt.
3. Successive interarrival times are independent of each other
(i.e. arrivals are not bursty).
Univ. of Tehran
Introduction to computer Network
74
The Poisson process

Why use the Poisson process?


It is the continuous time equivalent of a series of coin
tosses.
It is known to model well systems in which a large number
of independent events are aggregated together. e.g.





Arrival of new phone calls to a telephone switch
Decay of nuclear particles
“Shot noise” in an electrical circuit
It makes the math easy.
Be warned



Network traffic is very bursty!
Packet arrivals are not Poisson.
Univ.it
of models
Tehran
computer Network
But
quite Introduction
well thetoarrival
of new flows.
75
An M/M/1 queue
Model of FIFO router queue
A(t), l

m
D(t)
If A(t) is a Poisson process with rate l, and the time to
serve each packet is exponentially distributed with rate
m, then:
Average delay, d 
Univ. of Tehran
1
l
; and so from Little's Result: L  l d 
m l
m l
Introduction to computer Network
76