Transcript Taxonomy of communication networks

A Taxonomy of Communication
Networks
Y. Richard Yang
1/16/2008
1
Outline
 Recap
 A taxonomy of communication networks
 Summary
2
Recap
 A protocol defines the format and the order of
messages exchanged between two or more
communicating entities, as well as the actions taken
on the transmission or receipt of a message or other
events.
 Some implications of the past:



ARPANET is sponsored by ARPA 
design should survive failures
The initial IMPs (routers) were made by a small
company  keep the network simple
Many networks 
internetworking: need a network to connect networks

Commercialization 
architecture supporting distributed, autonomous systems
3
Recap: Current Internet Physical
Infrastructure
Residential access




Cable
Fiber
DSL
Wireless
ISP
Backbone ISP
ISP
 The Internet is a network
Campus access,
e.g.,


Ethernet
Wireless
of networks
 Each individually
administrated network is
called an Autonomous
System (AS)
4
Northern CrossRoads (NoX)
Aggregation Point (AP)
http://www.nox.org/NoXAPConfig3-01.jpg
5
Abilene I2 Backbone
http://weathermap.grnoc.iu.edu/abilene_jpg.html
6
http://www.qwest.com/largebusiness/enterprisesolutions/networkMaps/preloader.swf
Qwest Backbone Map
7
ATT Global Backbone IP Network
From http://www.business.att.com
8
AT&T USA Backbone Map
From AT&T web site.
9
Commercial Internet ISP
Connectivity
 Roughly hierarchical


Divided into tiers
Tier-1 ISPs are also called
backbone providers, e.g.,
AT&T, Verizon, Sprint,
Level 3, Qwest
 An ISP runs (private)
Points of Presence (PoP)
where its customers and
other ISPs connect to it
 ISPs also connect at
(public) Network Access
Point (NAP)

called public peering
10
Network Access Point
 Interconnect multiple ISP’s
Example: Chicago NAP (http://www.aads.net/main.html)
11
Outline
 Admin. and recap
 A taxonomy of communication networks
 Summary
12
A Taxonomy of Communication Networks
 So far we have looked at only the topology and
physical connectivity of the Internet: a mesh of
computers interconnected via various physical
media
 The fundamental question: how is data (the bits)
transferred through a communication network?
13
Broadcast vs. Switched
Communication Networks
communication
networks
switched
networks
broadcast
networks
 Broadcast networks
 nodes share a common channel; information transmitted
by a node is received by all other nodes in the network
 examples: TV, radio
 Switched networks
 information is transmitted to a small sub-set (usually only
one) of the nodes
14
A Taxonomy of Switched Networks
communication
networks
switched
networks
circuit-switching
networks
(e.g. telephone,
GSM)
broadcast
networks
packet-switching
networks
(e.g. Internet)
 Circuit switching: dedicated circuit per call/session:

e.g., telephone, GSM High-Speed Circuit-Switched Data (HSCSD),
Integrated Services Digital Networks (ISDN)
 Packet switching: data sent thru network in discrete “chunks”

e.g., Internet, General Packet Radio Service (GPRS)
15
Outline
 Admin. and review
 A taxonomy of communication networks
 circuit switching networks
packet switching networks
 circuit switching vs. packet switching
 datagram switching vs. virtual circuit switching

 Summary
16
Circuit Switching
 Each link has a number
of “circuits”

sometime we refer to a
“circuit” as a channel or
a line
 An end-to-end
connection reserves
one “circuit” at each
link
First commercial telephone switchboard was opened in 1878 to serve the 21
telephone customers in New Haven, Connecticut
17
Circuit Switching: Resources/Circuits
(Frequency, Time and others)
 Divide link resource
into “circuits”
 frequency
division
multiplexing
(FDM)
 time division
multiplexing
(TDM)
 others such as
code division
multiplexing
(CDM),
color/lambda
division
18
Circuit Switching: The Process
 Three phases
1.
2.
3.
circuit establishment
data transfer
circuit termination
19
Timing Diagram of Circuit Switching
Host A
Node 1
Node 2
processing delay at Node 1
circuit
establishment
data
transmission
Host B
propagation delay
from A to Node 1
propagation delay
from B To A
DATA
circuit
termination
20
Delay Calculation in Circuit Switched Networks
 Propagation delay: delay for the first
d/s
bit to go from a source to a destination
 Transmission delay: time to pump
DATA
L/R
data onto link at reserved rate
Propagation delay:
 d = length of physical link
 s = propagation speed in
medium (~2x105 km/sec)
 propagation delay = d/s
Transmission delay:
 R = reserved bandwidth
(bps)
 L = message length (bits)
 time to send a packet
into link = L/R
21
An Example
 Propagation delay
 suppose the distance between A and B is 4000 km, then
one-way propagation delay is:
4000km
200, 000km / s
 20ms
 Transmission delay
 suppose we reserve a one slot HSCSD channel
• a frame can transmit about 115 kbps
• A frame is divided into 8 slots
• each reserved one slot HSCSD has a bandwidth of about 14
Kbps (=115/8)

then the transmission delay of a message of 1 Kbits:
1kbits
14 kbps
 70ms
22
An Example (cont.)
 Suppose the setup message is very small, and the total setup
processing delay is 200 ms
 Then the delay to transfer a message of 1 Kbits from A to B
(from the beginning until host receives last bit) is:
20  200  20  20  70  330ms
20 + 200
20
20
DATA
70
23
Outline
 Admin. and review
 A taxonomy of communication networks
 circuit switching networks
 packet switching networks
 circuit switching vs. packet switching
 Summary
24
Packet Switching
Each end-to-end data flow (i.e., a sender-receiver pair)
divided into packets
 Packets have the following structure:
Header
Data
Trailer
• header and trailer carry control information (e.g., destination
address, check sum)
• where is the control information for circuit switching?
• any analogy in life?
 At each node the entire packet is received,
processed (e.g., routing), stored briefly, and then
forwarded to the next node; thus packet-switched
networks are also called store-and-forward
networks
25
Packet Switching
26
Inside a Packet Switching Router
An output queueing switch
incoming links
node
outgoing links
Memory
27
Packet Switching: Resources
 Resources used as needed
 On its turn, a packet uses full link bandwidth
28
Outline
 Admin. and review
 A taxonomy of communication networks
 circuit switching networks
 packet switching networks
 circuit switching vs. packet switching
 Summary
29
Packet Switching vs. Circuit Switching

The early history of the Internet was a
heated debate between Packet Switching
and Circuit Switching
the telephone network was the
dominant network
 Need to compare packet switching with
circuit switching
30
Circuit Switching vs. Packet Switching
circuit
switching
packet
switching
resource
partitioned
not partitioned
when using
resource
use a single partition
bandwidth
use whole link
bandwidth
reservation/ need reservation
setup
(setup delay)
no reservation
resource
contention
busy signal
(session loss)
congestion (long delay
and packet losses)
header
no header
per packet header
processing
fast
per packet processing
31
Key Issue to be Settled
 All the other comparisons are easy to
understand, a key debating issue was
whether resource partition would be
inefficient.
 Tool used to analyze the issue: queueing
theory
32
Analysis of Circuit-Switching
Blocking (Busy) Time
 Assume N circuits
 Session arrival:  per second
 Session service rate:  per second
 What is the percentage of time that a new
session is blocked?
For a demo of M/M/1, see:
http://www.dcs.ed.ac.uk/home/jeh/Simjava/queueing/mm1_q/mm1_q.html
33
Analysis of Delay at a Link
 Four types of delay at each hop
 nodal processing delay: check errors & routing
 queueing: time waiting for its turn at output link
 transmission delay: time to pump packet onto a link at link speed
 propagation delay: router to router propagation
 The focus is on transmission delay and propagation delay
34
The Key Case: To Partition or
not to Partition?
Assume:
R = link bandwidth (bps)
L = average packet length (bits)
a = average packet arrival rate (pkt/sec)
R/L = packet service rate (pkt/sec)
Setup: n streams; each stream has an arrival rate of a/n
Comparison: each stream reserves 1/n bandwidth or not
 Case 1 (not reserve):
all arrivals into a single
link with rate R, what
is the queueing delay +
transmission delay?
 Case 2 (reserve): the
arrivals are divided
into n links with rate
R/n each, what is the
queueing delay +
transmission delay?
35
Analysis of Queueing +
Transmission Time
 Consider a single queue
 Packet arrival rate:  per second
 Packet service rate:  per second
 What is the queueing + transmission time
of each packet?
36
Delay: M/M/1 Model
Assume:
R = link bandwidth (bps)
L = average packet length (bits)
a = average packet arrival rate (pkt/sec)
R/L = packet service rate (pkt/sec)
a
La
utilizatio n :  

R/L R
L 
average queueing delay : w 
R 1 
L 1
queueing  trans 
R 1 
37
Queueing Delay as A Function of Utilization
Assume:
R = link bandwidth (bps)
L = packet length (bits)
a = average packet arrival rate (pkt/sec)
R/L = packet service rate (pkt/sec)
a
La
utilizatio n :  

R/L R
  ~ 0: average queueing delay
small
  -> 1: delay becomes large
  > 1: more “work” arriving than
can be serviced, average delay
infinite !

38
Statistical Multiplexing Gain
Assume:
R = link bandwidth (bps)
L = average packet length (bits)
a = average packet arrival rate (pkt/sec)
R/L = packet service rate (pkt/sec)
Setup: n streams; each stream has an arrival rate of a/n
Comparison: each stream reserves 1/n bandwidth or not
 Case 1 (not reserve):
all arrivals into a single
link with rate R
queueing  trans 
L 1
R 1 
 Case 2 (reserve): the
arrivals are divided
into n links with rate
R/n each
nL 1
queueing  trans 
any analogy in life?
R 1 
39
Packet Switching vs. Circuit Switching
 One of the major issues facing the Internet: How to
provide circuit-like behavior (in terms of quality of
service)?
 virtual circuit switching is originally mainly for
routing efficiency

bandwidth guarantees needed for audio/video apps

still an unsolved problem
40
Outline
 Admin. and review
 A taxonomy of communication networks
 circuit switching networks
 packet switching networks
 circuit switching vs. packet switching
 routing in packet switching networks
 Summary
41
A Taxonomy of Packet-Switched
Networks According to Routing
 Goal: move packets among routers from source to
destination

we’ll study routing algorithms later in the course
 Two types of packet switching
 datagram network
• each packet of a flow is switched independently

virtual circuit network:
• all packets from one flow are sent along a pre-established path
(= virtual circuit)
42
Datagram Packet Switching
 Example: IP networks
 Each packet is independently switched
 each packet header contains complete destination
address
 receiving a packet, a router looks at the packet’s
destination address and searches its current routing
table to determine the possible next hops, and pick one
 Discussions:
 an example of datagram-style communication in daily life?
 advantages of datagram switching?
 potential problems of packet switching?
43
Datagram Packet Switching
Host C
Host D
Host A
Node 1
Node 2
Node 3
Node 5
Host B
Node 6
Node 7
Host E
Node 4
44
Timing Diagram of Datagram Switching
Host A
transmission
time of Packet 1
at Host A
Node 1
Packet 1
Host
B
Node 2
propagation
delay from
Host A to
Node 1
Packet 2
Packet 1
processing
and
queueing
delay of
Packet 1 at
Node 2
Packet 3
Packet 2
Packet 3
Packet 1
Packet 2
Packet 3
45
Virtual-Circuit Packet Switching
 Example: Asynchornous Transfer Mode (ATM)
networks; Multiple Label Packet Switching (MPLS) in
IP networks
 Hybrid of circuit switching and datagram switching



each packet carries a short
tag (virtual-circuit (VC) #);
tag determines next hop
fixed path determined at
Virtual Circuit setup time,
remains fixed thru flow
routers maintain per-flow
state
Incoming
Interface
Incoming
VC#
Outgoing
Interface
Outgoing
VC#
1
12
2
22
1
16
3
1
2
12
3
22
…
• what state do routers
maintain for datagram switching?
46
Virtual-Circuit Switching
Host C
Host D
Host A
Node 1
Node 2
Node 3
Node 5
Host B
Node 6
Node 7
Host E
Node 4
47
Virtual-Circuit Packet Switching
 Three phases
1.
2.
3.
VC establishment
Data transfer
VC disconnect
48
Timing Diagram of Virtual-Circuit Switching
Host 1
Node 1
Host 2
Node 2
propagation delay
between Host 1
and Node 1
VC
establishment
Packet 1
Packet 2
Packet 1
data
transfer
Packet 3
Packet 2
Packet 3
Packet 1
Packet 2
Packet 3
VC
termination
49
Discussion: Datagram Switching vs. Virtual
Circuit Switching
 What are the benefits of datagram
switching over virtual circuit switching?
 What are the benefits of virtual circuit
switching over datagram switching?
50
Summary of the Taxonomy
of Communication Networks
communication
network
switched
network
circuit-switched
network
datagram
network
broadcast
communication
packet-switched
network
virtual circuit
network
51
Backup Slides
52
Packet Switching
Packet-switching:
store and forward behavior
53
Connection-Oriented Service
Goal: data transfer
between end sys.
 handshaking: setup
(prepare for) data
transfer ahead of time


Hello, hello back human
protocol
set up “state” in two
communicating hosts
 TCP - Transmission
Control Protocol

Internet’s connectionoriented service
TCP service [RFC 793]
 reliable, in-order byte-
stream data transfer

loss: acknowledgements
and retransmissions
 flow control:
 sender won’t overwhelm
receiver
 congestion control:
 senders “slow down sending
rate” when network
congested
54
Connectionless Service
Goal: data transfer
between end systems

same as before!
 UDP - User Datagram
Protocol [RFC 768]:
Internet’s
connectionless service
 unreliable data
transfer
 no flow control
 no congestion control
App’s using TCP:
 HTTP (WWW), FTP
(file transfer), Telnet
(remote login), SMTP
(email)
App’s using UDP:
 streaming media,
teleconferencing,
Internet telephony
55
Relationship Between Switching Techniques
and End Host Services
 End hosts determine end host services:
connection-oriented or connectionless

what an application wants
 Network service providers determine
network services: circuit-switching, packet
switching, datagram switching, or virtual
circuit switching

how the ISP builds their networks
56
Packet Switching: Resources
 Resources used as needed
 On its turn, a packet uses full link bandwidth
 Aggregated resource demand can exceed amount
available


congestion: packets queue, wait for link use
buffer overflow: packet losses
Bandwidth division into “pieces”
Resource reservation
57
Packet Switching vs. Circuit Switching
The early history of the Internet was a heated debate
between Packet Switching and Circuit Switching
 Advantages of packet switching over circuit switching




most important advantage of packet-switching over circuit switching
is statistical multiplexing, and therefore efficient bandwidth usage
no call setup (for datagram switching only)
no per-flow state information (for datagram switching only)
simple to implement
 Disadvantages of packet switching



potential congestion: packet delay and high loss
• protocols needed for reliable data transfer, congestion control
packet header overhead
per packet processing overhead
 Questions: why does the current Internet use datagram?
58
Statistical Multiplexing
Assume:
R = link bandwidth (bps)
L = average packet length (bits)
a = average packet arrival rate (pkt/sec)
R/L = packet service rate (pkt/sec)
L 
w
R 1 
Setup: N flows; each flow has an arrival rate of a/n
Comparison: each flow reserves 1/n bandwidth or not
 Case 1 (not reserve):
all arrivals into a single
link with rate R, what
is the queueing delay +
transmission delay?
 Case 2 (reserve): the
arrivals are divided
into n links with rate
R/n each, what is the
queueing delay +
transmission delay?
59
Queueing Delay: Kendall Notation
 Arrival/Service/NumberServers
 E.g., M/M/1, M/D/1
 Arrival process: the inter-arrival time
 D: fixed/deterministic inter-arrival time
 M: Markov, i.e., in each  unit of time, where  small, the
probability of exactly one arrival is , where  is called
arrival rate
 Service process: the service time
 D: fixed/deterministic service time
 M: Markov, i.e., in each  unit of time, where  small, the
probability of finish serving is , where  is called
service rate
For a demo of M/M/1, see:
http://www.dcs.ed.ac.uk/home/jeh/Simjava/queueing/mm1_q/mm1_q.html
60
Queueing Delay: M/M/1 Model
Assume:
R = link bandwidth (bps)
L = average packet length (bits)
a = average packet arrival rate (pkt/sec)
R/L = packet service rate (pkt/sec)
L 
average queueing delay : w 
R 1 
A more realistic model of
modern routers: M/D/1
1L 
average queueing delay : w 
2 R 1 
61