Transcript chapter1

Chapter 1 - Foundation
Outline
Basic building blocks of a Network
Statistical Multiplexing
Inter-Process Communication
Performance Metrics
Network Architecture
1
Computer Network
• A computer network is a network of computers for
exchanging data (bits) among themselves over a
single medium
• Information access (global) – almost immediate
access to information
• Interaction among cooperative application
programs – distributed processing/client-server
programming
• Resource sharing – sharing hardware and software
resources
2
Popular Applications





E-mail
File transfer/access (ftp)
Web browsing (http, html)
Remote login/execution (telnet)
The Internet (global access to information)
3
Building Blocks of a Network
• Nodes: PC, special-purpose hardware…
– hosts
– switches
• Links: coax cable, optical fiber…
point-to-point
(a)
multiple access
(b)
4
Switched Networks
• A network can be defined recursively as...
– two or more nodes
connected by a link, or
Switch
– two or more networks
connected by two or
more nodes
Router/Gateway
5
Why Switched Network?
• Multiple-access links are limited in size; cannot
support large geographical area (except satellites)
• Multiple-access links cannot support large number
of nodes
• Connecting all nodes directly to each other using
point-to-point links is unmanageable and very
expensive for large number of nodes covering a
large geographic area
• A switched network solves all preceding problems
6
Switching Strategies
• Circuit switching: carry bit streams
– Example: original telephone network
– A dedicated circuit (or channel) is established across a
sequence of links.
– Source node sends a stream of bits across the circuit
• Packet switching: store-and-forward messages
(packets)
– Example: Internet
– Each intermediate node receives and stores a complete
packet and then forwards to the next node
7
What is a packet?
• A discrete block of data
• Part of a piece of an email, an html page, or an
image
8
Identifying Nodes
• How to identify a packet’s sender?
• How to identify a packet’s receiver?
• How to determine to which link a packet should
be forwarded in a switched network?
9
Addressing and Routing
• Address: byte string that identifies a node
– usually unique
– sender and receiver addresses are always included in a
packet
• Routing: process of forwarding messages/packets
to the destination node based on its address
– Routing is done by a device called a router or a gateway
– A router connects two or more networks
• Address Types
– unicast: node-specific
– broadcast: all nodes on the network
– multicast: some subset of nodes on the network
10
Resource Sharing
• How do all the hosts that want to communicate
share the same network?
• How do several hosts share the same link when
they all want to use it at the same time?
11
Cost-Effective Resource Sharing:
Multiplexing
• Time-Division Multiplexing (TDM)
• Frequency-Division Multiplexing (FDM)
L1
R1
L2
R2
Sw itch 1
L3
Sw itch 2
R3
12
STDM and FDM
• Synchronous time-division multiplexing (STDM)
– Each host is allowed to transmit during a designated
slot of time in round-robin fashion.
– Disadvantage:
• Inefficient if not all hosts have anything to transmit
• Frequency-division multiplexing (FDM)
– Different frequencies (channels) are used for transmit
each data flow
– Same as the way TV programs are transmitted over the
same cable or medium
– Inefficient if not all channels are busy all the time
• Both STDM and FDM are static methods
13
Statistical Multiplexing
• On-demand time-division
• Schedule link on a per-packet basis
• Packets from different sources interleaved on
link
• Buffer packets that are contending for the link
• Buffer (queue) overflow is called congestion
■■■
14
Support for Common Services
• Hiding complexity of the network from the
application
• Providing logical channels over which
application processes on different hosts can
communicate with each other
15
Inter-Process Communication
• Turn host-to-host connectivity into process-to-process
communication.
• Fill gap between what applications expect and what the
underlying technology provides.
Host
Host
Application
Channel
Host
Application
Host
Host
16
Common Communication Patterns:
IPC Abstractions
• Request/Reply
– distributed file systems
– digital libraries (web)
• Stream-Based
– video: sequence of frames
• 1/4 NTSC = 352x240 pixels
• (352 x 240 x 24)/8=247.5KB
• 30 fps = 7500KBps = 60Mbps
– video applications
• on-demand video
• video conferencing
17
Request/Reply & Stream-Based
• Request/Reply Characteristics
–
–
–
–
Small amount of data sent as request
Large amount of data sent as reply
Not very time sensitive
Very error sensitive
• Stream-Based Charecteristics
– Time or delay sensitive
– Can tolerate errors to some extent
18
Reliability
• What Goes Wrong in the Network?
–
–
–
–
–
–
Bit-level errors (electrical interference)
Packet-level errors (congestion)
Link and node failures
Messages are delayed
Messages are delivered out-of-order
Third parties eavesdrop
19
Network Architecture
• Requirements for good network design
– Must provide general, cost-effective, fair, robust, and
high-performance connectivity among a large number
of computers
– Must evolve to accommodate future changes and
growths
• Two important widely referenced architectures
– OSI architecture and Internet architecture
20
Layering
• Use abstractions to hide complexity
• Abstractions naturally lead to layering
Application programs
Process-to-process channels
Host-to-host connectivity
Hardware
•Alternative abstractions at each layer
Application programs
Request/reply Message stream
channel
channel
Host-to-host connectivity
Hardware
21
Protocol
•
•
•
•
A set of rules for communications
Implemented in software and hardware
Building blocks of a network architecture
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
22
Interfaces
Host 1
High-level
object
Protocol
Host 2
Service
interface
Peer-to-peer
interface
High-level
object
Protocol
23
Protocol Machinery
• Protocol Graph
– most peer-to-peer communication is indirect
– peer-to-peer is direct only at hardware level
Host 1
File
application
Digital
library
application
Video
application
Host 2
File
application
Digital
library
application
Video
application
RRP: Request/Reply Protocol
MSP: Message Stream Protocol
HHP: Host to Host Protocol
24
Protocol Machinery (contd..)
• Multiplexing and Demultiplexing (demux key)
• Encapsulation (header/body)
Host
Host
Application
Application
program
program
Application
Application
program
program
Data
Data
RRP
RRP
RRP
Data
RRP
HHP
Data
HHP
HHP
RRP
Data
25
OSI Architecture
End host
End host
Application
Application
Presentation
Presentation
Session
Session
Transport
Transport
Netw ork
Data link
Physical
Netw ork
Netw ork
Data link
Data link
Physical
Physical
Netw ork
Data link
Physical
One or more nodes
w ithin the netw ork
26
OSI Architecture (contd..)
• Application – supports user applications e.g., email, ftp
• Presentation – supports formatting or transformation data
needed by an application
• Session – supports dialog and managing connections
between cooperating applications
• Transport – supports reliable end-to-end transmission of
data
• Network – address assignment; routing
• Data Link – supports frame construction, flow control,
error detection and correction
• Physical – deals with mechanical, electrical, functional,
and procedural characteristics of the physical medium
27
Internet Architecture
• Defined by Internet Engineering Task Force (IETF)
• Hourglass Design
• Application vs Application Protocol (FTP, HTTP)
FTP
HTTP
NV
TFTP
UDP
TCP
IP
NET 1
NET 2
■■■
NET n
• NET1, NET2, . . ., NETn are
network protocols, usually
implemented by a combination
of hardware (e.g., a network
adapter) and software (e.g., a
device driver).
28
Alternative View of Internet
Architecture
Application
TCP UDP
IP
Network
29
Performance
Metrics:Communication Bandwidth
• Number of bits that can be transmitted over the
network in a certain period of time
• Generally means the available bandwidth or the
link bandwidth
• Effective bit transfer rate is always less than the
available bandwidth (commonly referred as
throughput or end-to-end bandwidth)
• Notation
• bps, Kbps, Mbps, Gbps
30
Performance Metrics: Latency
• The time taken for a message to travel from one
end of a network to the other
• Also called delay
• Components
Latency = Propagation + Transmit + Queue
Propagation = Distance / speed
Transmit = Size / Bandwidth
31
Performance Metrics (contd..)
• Propagation Speed
– 3.0 x 108 meters/second in a vacuum
– 2.3 x 108 meters/second in a cable
– 2.0 x 108 meters/second in a fiber
• Notes
–
–
–
–
no queuing delays in direct link
bandwidth not relevant if Size = 1 bit
process-to-process latency includes software overhead
software overhead can dominate when Distance is small
32
Round-Trip Time (RTT)
• Time it takes to send a message from one end of a
network to the other and back
33
Bandwidth versus Latency
• Relative importance
– 1-byte: 1ms vs 100ms dominates 1Mbps vs 100Mbps
– 25MB: 1Mbps vs 100Mbps dominates 1ms vs 100ms
• Infinite bandwidth
– RTT dominates
• Throughput = TransferSize / TransferTime
• TransferTime = RTT + 1/Bandwidth x TransferSize
– 1-MB file to 1-Gbps link as 1-KB packet to 1-Mbps link
34
Delay x Bandwidth Product
• Amount of data “in flight” or “in the pipe”
• Example: 100ms x 45Mbps = 4.5Mbits=562KB
Delay
Bandw idth
35