location of each hop, for example that areas where not much actual distance vices can be accessed. It resembles
atla.net.internet2.edu was in Georgia, is traveled. Other possible sources of input/output, supporting a read/write
that hous.net.internet2.edu was in delay include slower routers (the CRS-1 style of interface. The impact of the IPC
Texas, and losa.net.internet2.edu was is a very high performance router) and software on a single message’s latency
in California. other intervening appliances (such as is typically low; ping measurements of
There are 17 hops reported. Our firewalls) and slow links. Nonetheless, a local loopback interface on klondike.
analysis of an unobstructed fiber did it is impressive that the IP routing in- cis.upenn.edu show times of about 20
not account for these routers, nor for frastructure is only about a factor of microseconds of latency. The largest
the possibility that packets did not two “slower” than the speed of light in cause of propagation delays in IPC is
travel “as the crow flies” between the fiber: 88ms vs. 38ms. protocols.
source and destination. The total prop- This observation of the difference Protocols are rules for communicat-
agation delay through this network, between pencil and paper and mea- ing intended to provide desired proper-
then, is equal to the sum of the propa- sured results leads to the definition of ties, such as high application through-
gation time across each subnet, plus the throughput of a system, which is put, reliability, or ordering. Reliable
the time required to pass through the how many bits per second you can send message delivery is a common applica-
routers. This time includes both the after taking all the real-world limita- tion requirement and usually requires
time to switch from an input subnet tions—propagationdelays, bandwidth, confirmation from the receiver to the
to an output subnet and the additional latency, and hops—into account. sender, thus implying a round-trip.
time spent waiting in queues of pack- Communications requiring more data
ets held in memory associated with interprocess Communication than a single packet must use multiple
line cards. If these queues are filled and Protocols packets, implying multiple round-trip
with packets because an output sub- In a distributed system, processes that times. To see the impact of the phys-
netistoobusy, congestionoccurs, and need to communicate do so via one ics on a naïve protocol, imagine an
packets that cannot be buffered are or more schemes for IPC.3 Example IPC system that uses 10Kbit packets
dropped. schemes include messages, reliable and must move 100Kbits (10-packets
Modern routers such as the Cisco streams, and remote procedure calls. worth of data) across the U.S., which
CRS-1 exhibit average latencies of It is easiest to think of IPC in terms as we have seen (for a single transcon-
about 100 microseconds1 when there of messages, sometimes called appli- tinental piece of fiber) should require
is no queuing. Our Philadelphia–Palo cation data units (ADUs), as they are about 19ms. If a new packet is sent
Alto example would include approxi- the building blocks on which other only when a previous one has been ac-
mately 30 of them in the round-trip IPC mechanisms, including reliable knowledged, one packet will be sent
path, making the total switching time bytestreams, are built. Messages may every 38ms, and the communication
latency about 3ms. The other causes require multiple IP packets. The socket will require 380ms, or almost one half
of delay are more difficult to measure, API is one example of a way in which second, independent of the bandwidth
but we can see that hop 8 (Atlanta) to message and reliable bytestream ser- of the network. Yet, it’s clear that with
hop 9 (Houston) takes about 23.5ms
and is about 1129km. To estimate the
Table 2: Traceroute results from home network (in n.J.) to cs.stanford.edu.
speed, we calculate 1129000 / .0235,
which is 48042553m/sec or about 16%
hop
Time 1 (ms)
Time 2 (ms)
Time 3 (ms)
of the speed of light. Hop 9 (Houston)
1
1.835
0.594
0.461
to hop 10 (Los Angeles) takes about
2
5.336
3.634
5.076
35.5ms to travel 2211km, which works
3
5.043
4.093
4.975
out to a little less than 21% of the speed
4
10.043
9.408
9.656
of light. So each hop is slowing things
5
14.687
14.319
14.902
down quite a bit. An additional factor
6
15.025
14.309
18.432
is routing, and the possibility of poor
7
14.004
14.254
15.001
route selection. Routers attempt to op-
8
14.914
13.945
14.916
timize a path between two points, but
9
14.985
14.031
16.568
that may be difficult, so in addition to
10
19.003
18.738
18.890
the delay through the routers we can
11
19.986
39.004
41.033
expect a certain delay caused by path
selections that deviate from a straight
12
59.984
58.776
58.969
line. An example of this can be found
13
41.168
90.035
88.657
in Table 2, where hop 9 is in New York,
14
60.013
89.862
88.904
hop 10 is in Massachusetts (Boston)
15
89.992
89.749
91.322
and hop 11 (the one that takes 19ms) is
16
90.302
97.151
96.555
in Rhode Island (Providence). Table 2
17
92.022
is interesting also in that it shows that
about 15ms is lost in the NJ/NY area
and 10ms in the California area, both
18
*
97.272
98.329
*
99.830
state
NJ
NJ
NJ
NJ
NY
NY
NY
NY
NY
MA
RI
?
IL?
CA?
CA
CA
CA
CA
JULY 2009 | VOL. 52 | NO. 7 | CoMMuniCATions of The ACM
63
