  A great deal of effort has been spent measuring topological features of the
Internet. However, it was recently argued that sampling based on taking paths
or traceroutes through the network from a small number of sources introduces a
fundamental bias in the observed degree distribution. We examine this bias
analytically and experimentally. For Erdos-Renyi random graphs with mean degree
c, we show analytically that traceroute sampling gives an observed degree
distribution P(k) ~ 1/k for k < c, even though the underlying degree
distribution is Poisson. For graphs whose degree distributions have power-law
tails P(k) ~ k^-alpha, traceroute sampling from a small number of sources can
significantly underestimate the value of \alpha when the graph has a large
excess (i.e., many more edges than vertices). We find that in order to obtain a
good estimate of alpha it is necessary to use a number of sources which grows
linearly in the average degree of the underlying graph. Based on these
observations we comment on the accuracy of the published values of alpha for
the Internet.
