Introduction

A note on the use of these PowerPoint slides:

We’re making these slides freely available to all (faculty, students,
readers). They’re in PowerPoint form so you see the animations; and
can add, modify, and delete slides (including this one) and slide
content to suit your needs. They obviously represent a lot of work
on our part. In return for use, we only ask the following:

 If you use these slides (e.g., in a class) that you mention their
source (after all, we’d like people to use our book!)
 If you post any slides on a www site, that you note that they are
adapted from (or perhaps identical to) our slides, and note our
copyright of this material.
Computer
For a revision history, see the slide note for this page.
Networking: A Top-
Thanks and enjoy! JFK/KWR
Down Approach
All material copyright 1996-2020 8th edition
J.F Kurose and K.W. Ross, All Rights Reserved
Jim Kurose, Keith Ross
Pearson, 2020
Introduction: 1-1
Alternative to packet switching: circuit switching
end-end resources allocated to,
reserved for “call” between
source and destination
 in diagram, each link has four
circuits.
• call gets 2nd circuit in top link
and 1st circuit in right link.
 dedicated resources: no sharing
• circuit-like (guaranteed)
performance
 circuit segment idle if not used by
call (no sharing)
 commonly used in traditional
telephone networks
Introduction: 1-52
 Circuit switching: FDM and TDM
Frequency Division Multiplexing (FDM)
 optical, electromagnetic frequencies 4 users

frequency
divided into (narrow) frequency
bands
 each call allocated its own band, can
transmit at max rate of that narrow
band
time
Time Division Multiplexing (TDM)

frequency
 time divided into slots
 each call allocated periodic
slot(s), can transmit at maximum
rate of (wider) frequency band,
but only during its time slot(s) time
Introduction: 1-53
Numerical example
 How long does it take to send a file of 640,000 bits from host A
to host B over a circuit-switched network?
 All links are 536 Mbps
 Each link uses TDM with 24 slots/sec
 500 msec to establish end-to-end circuit

Let’s work it out!

In TDM: each host gets same slot in revolving TDM frame.

1-54
An Early History Of Thee Internet
by LEONARD KLEINROCK:
 «Circuit switching is problematic because data
communications is bursty, that is, it is typically dominated
by short bursts of activity with long periods of inactivity. I
realized that any static assignment of network resources, as
is the case with circuit switching, would be extremely
wasteful of those resources, whereas dynamic assignment (I
refer to this as “dynamic resource sharing” or “demand
access”) would be highly efficcient».
Principios fundamentales packet
switching

 Demand access
 Distributed control
Packet switching vs circuit switching
packet switching allows more users to use network ?

Example:
 1 Gb/s link
 each user:

…..
N
• 100 Mb/s when “active” users 1 Gbps link
• active 10% of time

 circuit-switching: 10 users
Q: how did we get value 0.0004?
 packet switching: with 35
users, probability > 10 active Q: what happens if > 35 users ?
at same time is less
than .0004 *
* Check out the online interactive exercises for more examples: h ttp://gaia.cs.umass.edu/kurose_ross/interactive
Introduction: 1-57
Recordemos la distribución binomial
 n usuarios activo no activo

A=
(1-p) (1-p) p (1-p) p p p (1-p) p p

35−6 6
P ( A)=(1− p) p

35 35−6 6
P ( seis activos)=
6 ( )
(1− p) p

P ( k⩽10 activos)= P (0)+ P (1)+ P (2)+...+ P (10)

Packet Switching Versus Circuit Switching
• packet switching:
– with 35 users, probability > 10 active at same time is less than .0004 *

Probabilidad de > 10 usuarios

activos a la vez


1 - CDF[BinomialDistribution[35, 0.1], 10]

0.000424298
Q: how did we get value 0.0004?
Q: what happens if > 35 users ?
* Check out the online interactive exercises for more examples: tttp://gaia.cs.umass.edu/kurose_ross/interactive /
Blocking probability
 35 users, 10 channels
Packet switching versus circuit switching
Is packet switching a “slam dunk winner”?
 great for “bursty” data – sometimes has data to send, but at
other times not
• resource sharing
• simpler, no call setup
 excessive congestion possible: packet delay and loss due to
buffer overflow
• protocols needed for reliable data transfer, congestion control
 Q: How to provide circuit-like behavior?
• bandwidth guarantees traditionally used for audio/video
applications
Q: human analogies of reserved resources (circuit switching) versus
on-demand allocation (packet switching)?
Introduction: 1-61
Is packet Switching that beautiful?
 El cubrimiento de la banda ancha residencial y móvil es cada vez
mayor.
 El acceso banda ancha sirve no solo para el servicio de Internet si
no de otros servicios como TV (IPTV) y voz (VoIP).
 Packet switching brinda flexibilidad para llevar estos servicios
sobre la misma red
 ¿Qué ocurre si muchas fuentes a la vez demandan los recursos de
tx simultáneamente?
 ¿Cómo resolver este problema?
Priorization principle
AF = Assured forwarding
BE = Best effort

Figura tomada de Rec. ITU-T

G.114 con carácter
educativo.
Timing of events in (a)circuit switching, (b)packet switching.
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall , 2011
 Item Circuit switched Packet switched
Call setup Required Not needed
Dedicated physical path Yes No
Each packet follows the same route Yes No
Packets arrive in order Yes No
Is a switch crash fatal Yes No
Bandwidth available Fixed Dynamic
Time of possible congestion At setup time On every packet
Potentially wasted bandwidth Yes No
Store-and-forward transmission No Yes
Charging Per minute Per packet

A comparison of circuit-switched and packet-switched networks.

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall , 2011

How do packet loss and delay occur?
packets queue in router buffers
 packets queue, wait for turn
 arrival rate to link (temporarily) exceeds output link
capacity: packet loss
packet being transmitted (transmission delay)

B
packets in buffers (queueing delay)
free (available) buffers: arriving packets
dropped (loss) if no free buffers
Introduction: 1-66
 Packet delay: four sources
transmission
A propagation

B
nodal
processing queueing

dnodal = dproc + dqueue + dtrans + dprop

dproc: nodal processing dqueue: queueing delay

 check bit errors  time waiting at output link for
 determine output link transmission
 typically < msec  depends on congestion level of
router
Introduction: 1-67
Packet delay: four sources
transmission
A propagation

B
nodal
processing queueing

dnodal = dproc + dqueue + dtrans + dprop

dtrans: transmission delay: dprop: propagation delay:
 L: packet length (bits)  d: length of physical link
 R: link transmission rate  s: propagation speed (~2x108
(bps) m/sec)
 dtrans = L/R dtrans and dprop  dprop = d/s * Check out the online interactive
exercises:
http://gaia.cs.umass.edu/kurose_ross
very different Introduction: 1-68
Caravan analogy
100 100
km km
ten-car caravan toll booth toll booth
(aka 10-bit (aka router)
packet)
 time to “push” entire
 cars “propagate” at 100 km/hr caravan through toll booth
 toll booth takes 12 sec to onto highway = 12*10 =
120 sec
service car (bit transmission
time)  time for last car to
 car ~ bit; caravan ~ packet propagate from 1st to 2nd
toll both: 100km/(100km/hr)
 Q: How long until caravan is = 1 hr
lined up before 2nd toll booth?
 A: 62 minutes
Introduction: 1-69
 Caravan analogy
100 100
km km
ten-car toll booth toll booth
caravan (aka router)
(aka 10-bit
packet)
 suppose cars now “propagate” at 1000 km/hr
 and suppose toll booth now takes one min to service a car
 Q: Will cars arrive to 2nd booth before all cars serviced at first
booth?
A: Yes! after 7 min, first car arrives at second booth;
three cars still at first booth

Time for a car to propagate from 1st to 2nd toll both: 100km/(1000km/hr) = 6 min

Time to “push” entire caravan through toll booth onto highway = 60*10 = 600 sec=10 min
Introduction: 1-70
Packet queueing delay (revisited)

average queueing
delay
 R: link bandwidth (bps)
 L: packet length (bits)
 a: average packet arrival rate

traffic intensity = La/R 1

 La/R ~ 0: avg. queueing delay small
La/R ~ 0
 La/R -> 1: avg. queueing delay large
 La/R > 1: more “work” arriving is
more than can be serviced -
average delay infinite!
La/R -> 1
Introduction: 1-71
On packet congestion
Connecting Computers With Robert E. Kahn, By Alexander B.
Magoun, Proceedings of the IEEE, Vol. 102, No. 12, December
2014:
 «One of the problems Kahn faced in building the IMPs
was others’ conficdence that message packet congestion
would not be a problem[..] I knew that could happen
in the net, but I couldn’t convince anybody. When we
went to do the ficrst test of the system out in the ficeld,
the very ficrst thing that I did was to make it lock up».
“Real” Internet delays and routes
 what do “real” Internet delay & loss look like?
 traceroute program: provides delay measurement
from source to router along end-end Internet path
towards destination. For all i:
• sends three packets that will reach router i on path towards
destination (with time-to-live field value of i)
• router i will return packets to sender
• sender measures time interval between transmission and reply

3 probes 3 probes

3 probes

Introduction: 1-73
Real Internet delays and routes
traceroute: gaia.cs.umass.edu to
www.eurecom.fr 3 delay measurements from
gaia.cs.umass.edu to cs-gw.cs.umass.edu
1 cs-gw (128.119.240.254) 1 ms 1 ms 2 ms 3 delay measurements
2 border1-rt-fa5-1-0.gw.umass.edu (128.119.3.145) 1 ms 1 ms 2 ms
3 cht-vbns.gw.umass.edu (128.119.3.130) 6 ms 5 ms 5 ms to border1-rt-fa5-1-
4 jn1-at1-0-0-19.wor.vbns.net (204.147.132.129) 16 ms 11 ms 13 ms 0.gw.umass.edu
5 jn1-so7-0-0-0.wae.vbns.net (204.147.136.136) 21 ms 18 ms 18 ms
6 abilene-vbns.abilene.ucaid.edu (198.32.11.9) 22 ms 18 ms 22 ms
7 nycm-wash.abilene.ucaid.edu (198.32.8.46) 22 ms 22 ms 22 ms trans-oceanic link
8 62.40.103.253 (62.40.103.253) 104 ms 109 ms 106 ms
9 de2-1.de1.de.geant.net (62.40.96.129) 109 ms 102 ms 104 ms
10 de.fr1.fr.geant.net (62.40.96.50) 113 ms 121 ms 114 ms
11 renater-gw.fr1.fr.geant.net (62.40.103.54) 112 ms 114 ms 112 ms looks like delays
12 nio-n2.cssi.renater.fr (193.51.206.13) 111 ms 114 ms 116 ms decrease! Why?
13 nice.cssi.renater.fr (195.220.98.102) 123 ms 125 ms 124 ms
14 r3t2-nice.cssi.renater.fr (195.220.98.110) 126 ms 126 ms 124 ms
15 eurecom-valbonne.r3t2.ft.net (193.48.50.54) 135 ms 128 ms 133 ms
16 194.214.211.25 (194.214.211.25) 126 ms 128 ms 126 ms
17 * * *
18 * * * * means no response (probe lost, router not replying)
19 fantasia.eurecom.fr (193.55.113.142) 132 ms 128 ms 136 ms

* Do some traceroutes from exotic countries at www.traceroute.org

Introduction: 1-74
traceroute from 134.79.197.214 (www.slac.stanford.edu) to 45.5.165.36 (10-
36.dyn.univalle.edu.co) for 45.5.165.36
Tue Jun 4 14:05:01 2019: executing exec(traceroute -m 30 -q 1 -w 1 -A 45.5.165.36
140)
traceroute to 45.5.165.36 (45.5.165.36), 30 hops max, 140 byte packets
1 134.79.197.131 (134.79.197.131) [AS3671] 0.617 ms
2 rtr-core2-p2p-serv01-01.slac.stanford.edu (134.79.254.65) [AS3671] 0.602 ms
3 rtr-fwcore1-trust-p2p-core1.slac.stanford.edu (134.79.254.134) [AS3671] 1.026 ms
4 rtr-core1-p2p-fwcore1-untrust.slac.stanford.edu (134.79.254.137) [AS3671] 1.383
ms
5 rtr-border2-7k-core1.slac.stanford.edu (134.79.252.181) [AS3671] 1.389 ms
6 sunncr5-ip-c-slac.slac.stanford.edu (192.68.191.233) [AS3671] 1.880 ms
7 eqxsjcr5-ip-b-sunncr5.es.net (134.55.222.110) [AS293] 2.273 ms
8 v214.core1.sjc2.he.net (66.220.6.249) [AS6939] 2.257 ms
9 level3-as3356.ethernet10-15.core1.sjc2.he.net (64.71.128.254) [AS6939] 2.540 ms
10 *
11 EMPRESAS-MU.ear4.Miami2.Level3.net (4.15.158.50) [AS3356] 124.625 ms
12 *
...
29 *
30 *
traceroute -m 30 -q 1 -w 1 -A 45.5.165.36 140 took 5secs. Total script traceroute.pl
time=5secs,
 Packet loss
 queue (aka buffer) preceding link in buffer has finite capacity
 packet arriving to full queue dropped (aka lost)
 lost packet may be retransmitted by previous node,
by source end system, or not at all
buffer
(waiting area) packet being transmitted
A

B
packet arriving to
full buffer is lost

* Check out the Java applet for an interactive animation on queuing and loss
Introduction: 1-76
 Throughput
 throughput: rate (bits/time unit) at which bits are being
sent from sender to receiver
• instantaneous: rate at given point in time
• average: rate over longer period of time

link capacity
pipe that can link
pipecapacity
that can carry
server sends R carry
bits/sec
server, with fluid at rate
s Rc fluid at rate
bits/sec
bits
file of F bits (Rc bits/sec)
(fluid) client (Rs bits/sec)
intotopipe
to send
Introduction: 1-77
Alcance mediciones ISP

Fuente: Rec. ITU‑T Y.1540 (07/2016). Uso educativo

Throughput
Rs < Rc What is average end-end throughput?

Rs bits/sec Rc bits/sec

Rs > Rc What is average end-end throughput?

Rs bits/sec Rc bits/sec

bottleneck link
link on end-end path that constrains end-end
throughput
Introduction: 1-79
Throughput: network scenario
 per-connection
Rs end-end
Rs Rs throughput:
min(Rc,Rs,R/10)
R  in practice: Rc or Rs
Rc Rc
is often bottleneck
Rc
* Check out the online interactive exercises for more
examples: http://gaia.cs.umass.edu/kurose_ross/

10 connections (fairly) share

backbone bottleneck link R
bits/sec Introduction: 1-80
Internet structure: a “network of networks”

 Hosts connect to Internet via access Internet

Service Providers (ISPs)
• residential, enterprise (company, university,
commercial) ISPs
 Access ISPs in turn must be interconnected
• so that any two hosts can send packets to each other
 Resulting network of networks is very complex
• evolution was driven by economics and national
policies
 Let’s take a stepwise approach to describe
current Internet structure
Introduction: 1-81
Internet structure: a “network of networks”
Question: given millions of access ISPs, how to connect them together?

access
… access
net
access
net …
net
access
access net
net
access
access net
net
…

…
access access
net net

access
net
access
net

access
net
access
… net
access access …
net access net
net

Introduction: 1-82
Internet structure: a “network of networks”
Question: given millions of access ISPs, how to connect them together?

access
… access
net
access
net …
net
access
access
net
… … net

access
access net
net

connecting each access

…

…
ISP to each other directly

…
access
access
doesn’t scale: O(N2)
…

net net

access
connections.
net
access
net

access
net
access
…

… net
access access …
net access net
net

Introduction: 1-83
Internet structure: a “network of networks”
Option: connect each access ISP to one global
transit ISP?
Customer and provider ISPs have economic
agreement. access
access
…access
net net …
net
access
access net
net
access
access net
net
…

…
global
access
net
ISP access
net

access
net
access
net

access
net
access
… net
access access …
net access net
net

Introduction: 1-84
Internet structure: a “network of networks”
But if one global ISP is viable business, there will be
competitors ….

access
… access
net
access
net …
net
access
access net
net
access
access net
net
ISP A
…

…
access
net ISP B access
net

access
net
ISP C
access
net

access
net
access
… net
access access …
net access net
net

Introduction: 1-85
Internet structure: a “network of networks”
But if one global ISP is viable business, there will be
competitors …. who will want to be connected
Internet exchange point
access
access
…
access
net net …
net
access
access net
net
IXP access
access net
net
ISP A
…

…
access
net
IXP ISP B access
net

access
net
ISP C
access
net

access
net
peering link
access
… net
access access …
net access net
net

Introduction: 1-86
Internet structure: a “network of networks”
… and regional networks may arise to connect
access nets to ISPs
… …
access
access
net
access
net

net
access
access net
net
IXP access
access net
net
ISP A
…

…
access
net
IXP ISP B access
net

access
net
ISP C
access
net

access
net
regional ISP access
… net
access access …
net access net
net

Introduction: 1-87
Internet structure: a “network of networks”
… and content provider networks (e.g., Google, Microsoft,
Akamai) may run their own network, to bring services,
content close to end
… users … access
net
access
net
access
net
access
access net
net
IXP access
access net
net
ISP A
…

…
Content provider network
access
net
IXP ISP B access
net

access
net
ISP C
access
net

access
net
regional ISP access
… net
access access …
net access net
net

Introduction: 1-88
Basic network topologies

Fuente: Wikipedia.org
The Internet is an interconnected collection of many
networks

Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
 Internet2

Canet4
Geant

Ejemplos redes
académicas

Figura propiedad de IEEE Communications Magazine 
1-92
Ejemplo red óptica
Architecture of the Internet

Overview of the Internet architecture


Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
 Internet structure: a “network of networks”

Tier 1 ISP Tier 1 ISP Google

IXP IXP IXP

Regional ISP Regional ISP

access access access access access access access access

ISP ISP ISP ISP ISP ISP ISP ISP

At “center”: small # of well-connected large networks

 “tier-1” commercial ISPs (e.g., Level 3, Sprint, AT&T, NTT), national &
international coverage
 content provider networks (e.g., Google, Facebook): private network that
connects its data centers to Internet, often bypassing tier-1, regional ISPs1-95
Introduction:
Internet exchange point (IXP)
Rec. ITU-T D.52
 «An Internet exchange point (IXP) is a single physical
network infrastructure operated by a single entity with
the purpose to facilitate the exchange of Internet
traffic. It acts as a centralized hub enabling local traffic
to be routed locally and save international bandwidth
which has the effect to reduce the overall costs of
international internet connectivity.»
Tier-1 ISP Network map: Sprint (2019)

POP: point-of-presence
to/from other Sprint PoPS
links to
peering
networks

…
… … …
links to/from Sprint customer networ

Introduction: 1-97
Los cuatro grandes actores de Internet:

1) End users
2) Broadband providers
3) Backbone networks (long-haul firber-optic links
and high-speed routers)
4) Edge providers (provide content, services, and
applications over the Internet.)