Transcript 152-background - University of California, Santa Cruz

CMPE 150:
Introduction to
Computer Networks
J.J. Garcia-Luna-Aceves
Email: [email protected]
Phone: 94153
Office: E2, Room 317
CCRG Lab: E2, Room 315
http://www.cse.ucsc.edu/research/ccrg/CMPE150/FALL2004
July 15
UCSC
CMPE150
1
CMPE 150: Introduction
to Computer Networks
LECTURE 1:
Introduction and
Background
July 15
UCSC
CMPE150
2
Outline






What is a computer network?
Brief history and outlook of the Internet.
What are communication protocols and how do we
go about studying them?
Architectural structure of the Internet.
Issues of interest with transmission media as a
black box.
More about networks and links.
July 15
UCSC
CMPE150
3
What Is a Computer
Network?






A communication network is a set of nodes connected
by links and able to communicate with one another.
A computer network is a communication network
in which nodes are computers.
The purpose of the network is to serve users, which can be
humans or processes.
Network links can be point-to-point or multipoint and
implemented with several transmission media.
Information exchanged can be represented in multiple
media (audio, text, video, images, etc.)
Services provided to users can vary widely.
July 15
UCSC
CMPE150
4
Why Learn about Computer
Networks?

Computer networks started as a means for




The “web” and affordable hardware have changed
this!


Distributed processing
Communicating among people (electronic mail, conferencing)
Increasing system reliability
We are evolving into Internet-based enterprises, Internet-based
home services, and an Internet society
The network will be everywhere…

Computers will be used in almost everything we build (including
sensors, appliances, books, newspapers)
These computers need to be interconnected
NETWORKING = COMPUTING

July 15
UCSC
CMPE150
5
Why Learn about Computer
Networks?

Industry and research are wide open to innovation!


Today’s protocols are oriented to support “host-to-host” communication
and assume a client-server model for services and an “open door”
policy for the Internet community.
The continuing success of the Internet requires:




Person-to-person communication (voice and other media over the Internet)
Client-to-content services.
Security in the services, the infrastructure, and the clients of the Internet
Innovation required includes:




Mechanisms to “look-up” content, rather than addresses.
Protocols aimed at the new types of communication and services
Protocols that adhere to new principles of design.
Protocol stacks for nomadic users.
July 15
UCSC
CMPE150
6
Evolution of Computer Networks
1876:
1890s:
1897:
1940s:
1960:
1960s:
1961:
1962:
1965:
1968:
1969:
1970s:
July 15
Telephone by A. Graham Bell
Electromagnetic telephone switches
Cathode Ray Tube by K.F. Braun
Computers, error detection and retransmission
RS-232 physical layer interface (the “serial port”) and
modems
T-1 carrier system for telephone transmission
(1.5Mbps)
The Compatible Time Sharing System
Paul Baran at RAND proposes packet switching
Automatic equalization by Bob Lucky and others
Carterfone FCC decision that led to AT&T divestiture
in 1984.
DARPA funds project on packet switching
Computerized switches; work on ISDN starts
UCSC
CMPE150
7
Evolution of Computer Networks
1970s: ARPANET starts (UCLA, Utah, SRI, UCSB); its
technology evolved into today’s Internet
1970s: ALOHA system at U. of Hawaii; first protocol for
multiple access channels; leads to Ethernet
1970s: GUI, mouse, hypertext by Doug Engelbart at SRI
1974:
“A Protocol for Packet Network Interconnection,”
V. Cerf and R. Kahn, IEEE Trans. Comm (May).
1980s: OSI (open system interconnection) reference model
1982: TCP/IP is deployed in ARPANET/MILNET
1984: Host table evolves into DNS in ARPANET
1984: AT&T breaks up
1986: NSFNET is created; becomes Internet backbone
1992: WWW by Tim Berners-Lee (CERN) is released;
gives a GUI to the Internet
1990s: Caches and proxies helping clients access content
July 15
UCSC
CMPE150
8
Evolution of Computer Networks
1970s: CCITT publishes standards for public data networks
(X.25 standards)
1980s: Token ring LANs, FDDI emerge;
do not replace Ethernet
1990s: ATM evolves; does not replace IP
1990s: Internet: From 4 to 30M+ wired,
published nodes in two decades
1990s: SONET (synchronous optical network) and SDH
(synchronous digital hierarchy) evolve
1990s: Cellular phones, laptops, palmtops become popular
1999: Gigabit Ethernet starts, simplicity wins again.
July 15
UCSC
CMPE150
9
Evolution of Computer Networks
What will happen in the 2000s?:




Ad-hoc wireless networks; self-configuring nets
Networked sensors and appliances
System-area networks (“the network is [in] the
computer”)
Network-based computing: grid computing
(“the computer--processing and storage--is in the network”)



Internet-to-go; deeply networked systems
IP voice, IP devices
Content routing: ISPs start to be CDNs, allow clients to
obtain content based on its name from the best location
…. Networking
July 15
UCSC
= Computing
CMPE150
10
What Do We Study?





We will use the Internet as our running
example.
The Internet has computer hardware, software,
operating systems, transmission technology,
services defined over it... What is its glue?
Communication protocols implemented in
software or hardware transform otherwise isolated
machines into a society of computers.
Protocols specify how processes in different
machines can interact to provide a given service.
Distributed algorithms are the essence of what we
study.
July 15
UCSC
CMPE150
11
Communication Protocols


A set of rules governing the interaction of
concurrent processes in a system.
A protocol has five parts:





The service it provides.
The assumptions about the environment where it
executes, including the services it enjoys.
The vocabulary of messages used to implement it
The format of each message in the vocabulary.
The procedure rules (algorithms) guarding the
consistency of message exchanges and the integrity of
the service provided.
July 15
UCSC
CMPE150
12
What Do We Study Regarding
Protocols?

What is a good protocol design?


What are good and bad aspects in a protocol?



Judging by their survival, Ethernet and IP are good;
token ring protocols are not very good
TCP adapts to congestion, but it inherently assumes that
the Internet sends packets in order.
Use representative protocols to go over these
issues.
Discuss new directions in computer
communication.
July 15
UCSC
CMPE150
13
What Do We Study Regarding
Protocols?


We will take a quick look at the principles of
computer communication.
Our principles are:






July 15
The description of a protocol has no ambiguity.
A protocol does what it is supposed to do, all the time.
A protocol does not leave any communicating party
waiting forever for something to happen.
A protocol makes efficient use of available resources.
A protocol enables the use of resources fairly or
according to a predefined contract.
As with most engineering topics, simplicity is important.
UCSC
CMPE150
14
Principles of Computer
Communication






Protocol specification: The description of the
protocol is complete and accurate.
Safety: A protocol does what it is supposed to do,
all the time.
Liveness: A protocol does not leave any
deadlocks.
Efficiency: A protocol makes efficient use of
available resources.
Fairness: Fair or contractual use of resources
Simplicity is desirable, but not necessary.
July 15
UCSC
CMPE150
15
In The Beginning
There Was ARPANET
SRI
UTAH
IMP
IMP
UCSB IMP
IMP
UCLA
12/1/69
July 15
UCSC
CMPE150
16
The Beginnings of Protocol
Layering
Host-Host
HOST
IMP
HOST
IMP
IMP
IMP-IMP
application
Host-IMP
application
IMP
Routing within ARPANET is transparent to hosts
attaching to the ARPANET
July 15
UCSC
CMPE150
17
Characteristics of ARPANET
Architecture

Backbone-based:



A finite number of identifiers suffices to name the IMPs that
constitute the backbone.
The backbone provides a common packet-delivery service to the
backbone users.
Host-centric:



July 15
The users of the backbone are host computers.
The identifiers used to route packets to destinations are the names
of the attachment points of the hosts; these are unique identifiers
throughout the network.
A centralized host table can be used to map text-based host
names to the numeric names.
UCSC
CMPE150
18
Internet Model

Problem:


Need to maintain the details of how packets are
forwarded within and across heterogeneous
networks transparent to the users (hosts) of
the interconnect.
Approach:

July 15
Use a common end-to-end protocol spoken by
all gateways interconnecting networks, and also
by the hosts talking to gateways.
UCSC
CMPE150
19
Internet Model
3
A
A@3
NET
NET
G
IP
G
IP
G
G
B
NET
NET




Users of the interconnect are hosts.
A single address space is used to draw numeric names for
networks (“3”) and hosts (“A@3”).
An end-to-end protocol (the Internet Protocol or IP) is used
for delivering all user and control data, with a common
definition of services.
A table is used to map people-friendly names to numeric
names.
July 15
UCSC
CMPE150
20
Internet Model
R
R
G
R
R
R
G
G
G
How data are forwarded within each network is
transparent to IP, and IP is transparent to each
network
July 15
UCSC
CMPE150
21
Internet
R
R
R
R
R
R
R
R
R
R
NSFNET: Routers inside networks also use IP.
IP in every router; no need for network gateways.
Names of routers are “router@net”
July 15
UCSC
CMPE150
22
ARPANET Growth
(a) December 1969, (b) July 1970, (c) March 1971,
(d) April 1972, (e) September 1972.
July 15
UCSC
CMPE150
23
NSFNET Topology

July 15
The NSFNET backbone in 1988.
UCSC
CMPE150
24
Internet Elements
R
R
R
R
R
R
R
R
R
Hosts: The computers running user applications (clients, servers, proxies).
Routers/bridges/switches: Devices used to interconnect hosts and to
forward data from source to destination host.
Networks: Aggregations of hosts and routers.
Links between devices.
July 15
UCSC
CMPE150
25
What Is The Internet


protocols
Internet: “network of
networks”



router
server
workstation
mobile
local ISP
loosely hierarchical
public Internet versus
private intranet
regional ISP
Internet standards


July 15
RFC: Request for
comments
IETF: Internet
Engineering Task Force
UCSC
company
network
CMPE150
26
Internet Example
What does it take to get a page from the web?






Your client computer (client) and attached router have to be
configured.
Host and router communicate with each other through a LAN
or point-to-point link (PPP, CSMA/CD, 802.11, etc.).
Data is broken into “packets,” which are to be routed from
client to server and from server to client over a large number
of links, computers dedicated to routing, and networks
(IP, ARP, ICMP, OSPF, RIP, BGP).
Host obtains the IP address of remote server from a name
resolver (UDP, DNS) .
Client starts an end-to-end reliable connection with remote
server (TCP).
Client and server start exchanging messages (HTTP).
July 15
UCSC
CMPE150
27
Internet Example
P
P
R
R
R
R
R
R
R
R
R
R
One of many processes at one of many hosts in one of many networks
communicates with another process, which is one of many processes at
one of many hosts attached to one of many networks.
July 15
UCSC
CMPE150
28
Layering Model




Purpose is to divide and conquer complex software and
hardware needed to implement services
Partition services and functions needed in system into
layers
Each layer of service is provided by peer protocol entities
Communication can be point-to-point or multipoint
Layer N packets
NODE A
Layer-N
Protocol Entity
(virtual communication)
interface
NODE B
protocol
Layer-(N - 1)
Protocol Entity
July 15
Layer-N
Protocol Entity
Layer-(N - 1)
Protocol Entity
UCSC
CMPE150
29
The OSI Architecture


Proposed by the International Standards Organization
Specifies the functions at each layer, not the protocols that
implement them
APPLICATION
PRESENTATION
SESSION
TRANSPORT
NETWORK
LINK
PHYSICAL
July 15
End-user services (e.g., mail, file transfer)
Web access
Formatting, encryption, compression of data
Setup and management of end-to-end
dialogue
End-to-end delivery of messages to
processes
TCP
End-to-end transmissions of packets in net
IP
Transmissions of packets over a link
PPP, CSMA/CD
Transmission of bits over physical media
SONET
UCSC
CMPE150
30
Protocol Description





Specify the service to be provided by the
protocol
Specify assumptions about environment
Specify vocabulary (messages) needed in
the protocol
Specify the algorithms used to process and
exchange information in the protocol
Specify format of messages in vocabulary


We do this only in some cases
Our specifications are informal!
July 15
UCSC
CMPE150
31
Protocol Correctness


A protocol must be safe and live
Safety:


Liveness:


Protocol provides the desired service all the time
Protocol has no deadlocks (no process waits
forever for an event to occur)
Proving one may depend on the other
July 15
UCSC
CMPE150
32
Protocol Performance

Average delay


Throughput or capacity




Time between transmission of an information bit and
reception of the bit at the receiver
Number of information bits sent divided by the time
between transmission of first bit and delivery of the last
bit
Bottlenecks
Computations will make strong assumptions; in
most cases, results of analytical model provide only
a rough approximation
Most effective for comparative analysis
July 15
UCSC
CMPE150
33
Basic Network Services
S
1,2
1,2
D
All data flow
along same
path
Shared network resources
Connection-oriented service:



July 15
Reliable data transfer: In-order delivery, no
duplicates or missing data.
Flow control: Do not congest the receiver(s).
Congestion control: Do not congest the network(s).
UCSC
CMPE150
34
Basic Network Services
S
1,2
2
2
2
1
1,2
1
1
D
Data may
take different
paths to
destination
1
Shared network resources
Connection-oriented service:



July 15
Reliable data transfer: In-order delivery, no
duplicates or missing data.
Flow control: Do not congest the receiver(s).
Congestion control: Do not congest the network(s).
UCSC
CMPE150
35
Basic Network Services
S
1,2,3
2,1,2
D
Shared network resources
Connectionless service:
No delivery guarantees needed from the network.
 Any connection-oriented service to application is
provided by end-to-end protocol.

July 15
UCSC
CMPE150
36
Switching Methods
S
D
Shared network resources


Allocation of shared network resources
to the transport of user data.
Circuit switching and packet switching
are the two main types we will consider.
July 15
UCSC
CMPE150
37
Circuit Switching
S
D
call request
call accept
DATA
call termination
termination ack
Portion of physical resource is assigned to a single connection.
Delay and signaling overhead in establishing and ending connections.
July 15
UCSC
CMPE150
38
Multiplexing in Circuit
Switching


Share a given communication channel among
multiple connections.
Frequency division multiplexing (FDM):


Frequency spectrum of a link is partitioned into multiple
bands, and each band is assigned to zero or one
connection at any given time.
Time division multiplexing (TDM):

July 15
Time is divided into frames of fixed duration, and each
frame is divided into a fixed number of time slots. A
connection is assigned to a time slot, and occupies the
same time slot for multiple frames.
UCSC
CMPE150
39
FDM and TDM
Example:
FDM
4 users
frequency
time
TDM
frequency
July 15
UCSC
time
CMPE150
40
Message Switching
S
D
message
Message from sender is sent on a store-and-forward basis.
Message has a header used for forwarding.
Resources shared among different calls.
July 15
UCSC
CMPE150
41
Statistical Multiplexing

Share the same communication channel among
multiple connections without fixed allocations of
the resource to those connections.
S1
S2
m2
m1
m2
m2
m1
m1
m2
D1
m1
Link is shared based on
the statistics of each
connection or flow.
D2
Limitation:
Entire message must be received at a switch before it can be forwarded
July 15
UCSC
CMPE150
42
S
Packet Switching
D
packet 1
packet 2
packet 3
packet 4
Message from sender is broken into packets.
Each packet consists of a header and a payload.
Header information is used to forward packet to destination.
July 15
UCSC
CMPE150
43
S
Packet Switching
D
forward
store
A packet switch stores each packet it receives and determines
how to forward it based on the header information in the
packet.
July 15
UCSC
CMPE150
44
S
Packet Switching
D
packet 1
packet 2
packet 3
packet 4
Resources are shared among connections
Packets from the same connection can be processed concurrently
Connection setup delay can be avoided using datagrams
July 15
UCSC
CMPE150
45
Packet Switching vs
Message Switching
D
S
Processing message as packets in
store-and-forward mode saves time if propagation delays
are small!
July 15
UCSC
CMPE150
46
Packet Switching





Information is organized into packets
A packet consists of a header and a payload
Header specifies the control information needed
to transport the packet from origin to destination
Packets are forwarded from source to destination
using routing tables
There are two basic approaches to packet
switching:
datagrams
 virtual circuits

July 15
UCSC
CMPE150
47
Datagrams
2
e
6
a
7
5
1
b
c
3
4
c->d
To b
To d
To e
To 4
….


go to 2
go to 3
go to 2
go to 3
d
next
next
next
next
Routing table specifies next hop to each destination
Packets are forwarded based on the routing table
Each packet is routed independently

July 15
UCSC
CMPE150
48
Virtual Circuits
VC1
2
a
e
6
VC3
1
7
5
b
c
3


VC2
4
d
Virtual circuits are established and terminated
much like circuits in circuit switching.
Statistical multiplexing using packets, rather than
FDM or TDM is used to share links among
connections.
July 15
UCSC
CMPE150
49
Virtual Circuits
VC1
2
a
e
6
7
5
1
b
c
3
4
d
VC2
For VC1 use 2
For VC2 use 3
For VC3 use 3
...



Routing table specifies the next hop of an established VC.
Packet header specifies VC to be used for the packet.
All packets of the same VC are routed the same way.
July 15
UCSC
CMPE150
50
Virtual Circuits
VC1
2
a
e
6
7
5
1
b
c
VC5
3
4
d
VC2
VC4
For VC5 in, use 4 and label as VC2
For VC4 in, use 5 and label as VC3
...


Relative or global VC names can be used.
Relative VC names require “label swapping.”
July 15
UCSC
CMPE150
51
Packet Switching versus Circuit
Switching
Packet switching allows more users to use network!


1 Mbit link
Each user:



250 kbps when “active”
active 10% of time
Circuit-switching:


N users
4 users
Packet switching:


1 Mbps link
With 10 users, the probability
of having more than 4 active
users is 0.0016!
The average number of users
active on the link is one.
July 15
UCSC
Look at the probability of having up
to 10 active users.
Look at the arithmetic average.
CMPE150
52
Packet Switching versus Circuit
Switching




Works great in the average!
However, more than 4
users may be active at the
same time.
In that case, packets are
queued at the switch, and
congestion occurs.
Queuing delays are
important.
July 15
UCSC
N users
1 Mbps link
CMPE150
53
By Contrast: FDM and TDM
Example:
FDM
2 active users
frequency
time
TDM
frequency
July 15
UCSC
time
CMPE150
54
Packet Switching versus Circuit
Switching



Great for bursty data
 Resource sharing
 Simpler, no call setup (with datagrams!)
Excessive congestion: packet delay and loss
 Protocols needed for reliable data transfer,
congestion control, etc.
Q: How to provide circuit-like behavior?
 Bandwidth guarantees needed for audio/video
applications.
 Answer: Still a research problem.
July 15
UCSC
CMPE150
55
Transmission Media



We consider the physical layer as a “black box”
We are interested in the characteristics and
services provided by the transmission media that
impact the link layer and higher layers.
Parameters:






July 15
Bandwidth
Delay or latency: average and variance
Storage capacity (bandwidth-delay product)
Reliability and security
Order of delivery
Type of sharing or access
UCSC
CMPE150
56
Bandwidth



We can communicate information over transmission
media using energy, by varying some physical
property (e.g., voltage or current).
Problem: What the sender transmits is not exactly
what the receiver obtains from the communication
link.
Reasons: Link incurs some energy loss and delays,
and there are other interfering sources.
receiver
sender
July 15
UCSC
CMPE150
57
Bandwidth


We think of the bandwidth of a network or link as
the number of information bits that can be
transmitted over it in a certain period of time
(e.g., bits per second).
The bandwidth of a link is really the frequency range
tolerated by the channel without major attenuation.
Telephone line is 3000 Hz (300Hz to 3300 Hz)



Available bandwidth depends on the rate at which channel
can change stored energy.
We can model waveforms as sums of sine waves of different
frequencies.
Channel attenuates and delays each frequency component
differently, causing distortion.
July 15
UCSC
CMPE150
58
Bandwidth


Signals are run through a low-pass filter, and a signal can have V
discrete levels.
Maximum data rate of a noiseless channel of bandwidth B when V
discrete levels are used is
Data Rate = 2B log2 V bps (Nyquist, 1924).


Keep increasing V to achieve higher data rates with same B ?
Regardless of V, the maximum data rate (capacity) of a noisy channel
with bandwidth B and signal-to-noise ratio S/N is
C = B log2 (1+S/N) bps (Shannon, 1948)
S is the average signal power and N is the average noise power
Example: For a telephone line,
B is 3000 Hz, with a typical S/N ratio of 1000, so C is 30Kbps or so
We can achieve higher capacity only by increasing
S/N!
July 15
UCSC
CMPE150
59
Sources of Packet Delay
A
B
t1
t2
What contributes to the delay from the time the first
information bit is sent by the source (t1) to the time
when the last information bit is obtained by the receiver?
July 15
UCSC
CMPE150
60
Sources of Packet Delay
A
transmission time of packet
over each link
B
queueing
nodal
processing delay
nodal
queueing
processing delay
propagation delay
of each link
July 15
UCSC
CMPE150
61
Sources of Packet Delay

Nodal processing:



Queueing delay:



Time waiting at output link for transmission.
Depends on congestion level of router.
Transmission delay:


Checking for bit errors.
Determining output link.
Time to send bits into link: L/R, where
R = link bandwidth (bps) and L = packet length (bits)
Propagation delay:

July 15
Time for each bit to traverse a link: d/s, where
d = length of physical link and
s = propagation speed in medium (~2x108 m/sec)
UCSC
CMPE150
62
Packet Delay




Packet delay is the time elapsed between the instant when
the sender transmits the first bit of a obtains the last bit of
the packet.
Packet delay = Processing delay + Propagation delay +
Transmission delay + Queuing delay
Propagation delay = Distance / Speed of light
Speed of light = 3x108 meters/sec in the vacuum
~ 2x108 meters/sec in fiber
We can reduce processing, transmit, and queue
components using higher link speeds and faster processors,
but we cannot reduce the speed of light!
Long distances mean long latency!
July 15
UCSC
CMPE150
63
Nodal Delay
dnodal  dproc  dqueue  dtrans  dprop

dproc = processing delay


dqueue = queuing delay


depends on congestion
dtrans = transmission delay


typically a few microsecs or less
= L/R, significant for low-speed links
dprop = propagation delay

July 15
a few microsecs to hundreds of msecs
UCSC
CMPE150
64
Queueing delay (revisited)






R=link bandwidth
(bps)
L=packet length
(bits)
a=average packet
arrival rate
traffic intensity = La/R
La/R ~ 0: average queueing delay small
La/R -> 1: delays become large
La/R > 1: more “work” arriving than can
be serviced, average delay infinite!
July 15
UCSC
CMPE150
65
Packet Loss



Queue (i.e., the buffer) of each outgoing
link has finite capacity.
When packet arrives to a full queue,
packet is dropped (lost).
Lost packet may be retransmitted by
previous node, by source end system, or
not retransmitted at all.
July 15
UCSC
CMPE150
66
Bandwidth-Delay Product






The amount of data “stored” in the link.
Think of a link as a pipe; the latency is the length of the
pipe and the bandwidth is its diameter.
The BD product gives the volume of the pipe.
Example: A channel of 50 ms latency and just 45 Mbps
bandwidth can hold 2.25 million bits
(the same as the memory of a PC of early 80s!).
We are moving to Gigabit networks...
Big bandwidth and big distances require:



July 15
Big aggregation and big memories at hosts
New reliable transmission algorithms
Migration from client-server to client-content models.
UCSC
CMPE150
67
Bandwidth-Delay Product
Low-speed link
S
R
high-speed link


Links stretching long distances have large storage
capacity.
Problem: How do we provide feedback to senders?
TCP was originally designed for such applications
as telnet and ftp over paths with small BDP.
July 15
UCSC
CMPE150
68
Other Parameters




Reliability: We will assume that information is
transmitted correctly across a link or network with
a given likelihood.
Security: We will likely not cover this aspect in
much detail :(
Order of delivery: We will assume FIFO and nonFIFO delivery of packets or messages, depending
on the protocol and transmission media.
Access: We will consider point-to-point and
broadcast links.
July 15
UCSC
CMPE150
69
Internet Structure:
Network of Networks


Roughly hierarchical
At its center: “tier-1” ISPs
(e.g., UUNet, BBN/Genuity, Sprint, AT&T),
national/international coverage
 Treat each other as equals
Tier-1
providers
interconnect
(peer)
privately
July 15
Tier 1 ISP
Tier 1 ISP
UCSC
NAP
Tier-1 providers
also interconnect
at public network
access points
(NAPs)
Tier 1 ISP
CMPE150
70
Tier-1 ISP Example: Sprint
US Backbone Network
July 15
UCSC
CMPE150
71
Internet Structure


Each packet passes through many networks!
Limiting factor: Speed of light!
local
ISP
Tier 3
ISP
Tier-2 ISP
local
ISP
local
ISP
local
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
July 15
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
UCSC
CMPE150
Tier-2 ISP
local
ISP
72
Internet Structure

Why we need user-to-content rather than
client-server approach.
local
ISP
Tier 3
ISP
Tier-2 ISP
local
ISP
local
ISP
local
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
July 15
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
UCSC
CMPE150
Content comes
from nearest outlet
to client.
Content needs to
be routed to
nearest outlets.
Tier-2 ISP
local
ISP
proxy
73
END
July 15
UCSC
CMPE150
74
Internet Delays and Routes


What do “real” Internet delay and 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
router i will return packets to sender
sender times interval between transmission and reply.
3 probes
3 probes
3 probes
July 15
UCSC
CMPE150
75
Internet Delays and Routes
traceroute: gaia.cs.umass.edu to www.eurecom.fr
Three delay measements from
gaia.cs.umass.edu to cs-gw.cs.umass.edu
1 cs-gw (128.119.240.254) 1 ms 1 ms 2 ms
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
4 jn1-at1-0-0-19.wor.vbns.net (204.147.132.129) 16 ms 11 ms 13 ms
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
8 62.40.103.253 (62.40.103.253) 104 ms 109 ms 106 ms
link
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
12 nio-n2.cssi.renater.fr (193.51.206.13) 111 ms 114 ms 116 ms
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 * * *
* means no reponse (probe lost, router not replying)
18 * * *
19 fantasia.eurecom.fr (193.55.113.142) 132 ms 128 ms 136 ms
July 15
UCSC
CMPE150
76