ABSTRACT
Title of dissertation: GLOBAL PHENOMENA
FROM LOCAL RULES:
PEER-TO-PEER NETWORKS
AND CRYSTAL STEPS
Amy Finkbiner, Doctor of Philosophy, 2007
Dissertation directed by: Professor James Yorke
Department of Mathematics
Department of Physics
Institute for Physical Science and Technology
Even simple, deterministic rules can generate interesting behavior in dynamical
systems. This dissertation examines some real world systems for which fairly simple,
locally defined rules yield useful or interesting properties in the system as a whole. In
particular, we study routing in peer-to-peer networks and the motion of crystal steps.
Peers can vary by three orders of magnitude in their capacities to process net-
work traffic. This heterogeneity inspires our use of ?proportionate load balancing,?
where each peer provides resources in proportion to its individual capacity. We pro-
vide an implementation that employs small, local adjustments to bring the entire
network into a global balance. Analytically and through simulations, we demon-
strate the effectiveness of proportionate load balancing on two routing methods for
de Bruijn graphs, introducing a new ?reversed? routing method which performs better
than standard forward routing in some cases.
The prevalence of peer-to-peer applications prompts companies to locate the
hosts participating in these networks. We explore the use of supervised machine
learning to identify peer-to-peer hosts, without using application-specific informa-
tion. We introduce a model for ?triples,? which exploits information about nearly
contemporaneous flows to give a statistical picture of a host?s activities. We find that
triples, together with measurements of inbound vs. outbound traffic, can capture
most of the behavior of peer-to-peer hosts.
An understanding of crystal surface evolution is important for the development
of modern nanoscale electronic devices. The most commonly studied surface features
are steps, which form at low temperatures when the crystal is cut close to a plane
of symmetry. Step bunching, when steps arrange into widely separated clusters of
tightly packed steps, is one important step phenomenon. We analyze a discrete model
for crystal steps, in which the motion of each step depends on the two steps on either
side of it. We find an time-dependence term for the motion that does not appear in
continuum models, and we determine an explicit dependence on step number.
GLOBAL PHENOMENA FROM LOCAL RULES:
PEER-TO-PEER NETWORKS AND CRYSTAL STEPS
by
Amy Finkbiner
Dissertation submitted to the Faculty of the Graduate School of the
University of Maryland, College Park in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
2007
Advisory Committee:
Professor James Yorke, Chair/Advisor
Professor Brian Hunt, Co-Advisor
Professor Dionisios Margetis, Co-Advisor
Professor Edward Ott
Professor Neil Spring
c?Copyright by
Amy Finkbiner
2007
Acknowledgements
I am indebted to many people for helping me through graduate school and my
dissertation.
My co-advisor, Jim Yorke, is a source for many great ideas, but he has also
always taken time to review my papers and presentations. Brian Hunt deserves just
as much credit for his ideas and availability. I am also grateful to Ed Ott and Eric
Harder for participating in the networks research group. I am thankful that Dio
Margetis was willing to give me a fascinating project at a very busy time in my life.
I am also grateful to Neil Spring for running an interesting class and serving on my
committee.
I would not have made it through the daily routine without my series of excellent
officemates, from Christian Zorn and Eric Errthum to Poorani Subramanian and
Russell Halper. Special thanks go to Russ for suggesting the title of this dissertation.
The NPSC and AFOSR provided my financial support, and the math and IPST
department staff were amazing in their ability to make that support run smoothly.
Finally, I would not be where I am today without my Swarthmore education
and my family, so I give them all my thanks.
ii
Table of Contents
List of Tables vi
List of Figures vii
1 Introduction 1
1.1 Overview of the dissertation . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Peer-to-peer networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Distributed hash tables . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Continuous-discrete definition . . . . . . . . . . . . . . . . . . 6
1.3.2 Data sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.3 Maintenance of the network . . . . . . . . . . . . . . . . . . . 8
1.4 Crystal surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Exploiting heterogeneity 11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 DHTs and proportionate load balancing . . . . . . . . . . . . 13
2.1.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Heterogeneous de Bruijn networks . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Forward and reversed de Bruijn networks . . . . . . . . . . . . 16
2.2.1.1 de Bruijn graphs (continuous model) . . . . . . . . . 16
2.2.1.2 de Bruijn networks (discrete model) . . . . . . . . . 17
2.2.2 Heterogeneity in de Bruijn networks . . . . . . . . . . . . . . . 21
2.2.2.1 Number of neighbors . . . . . . . . . . . . . . . . . . 21
2.2.2.2 Query path lengths . . . . . . . . . . . . . . . . . . . 23
2.2.2.3 Caching . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Proportionate load balancing . . . . . . . . . . . . . . . . . . . . . . 30
2.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.2.1 Arriving and departing peers (churn) . . . . . . . . . 31
2.3.2.2 Existing peers . . . . . . . . . . . . . . . . . . . . . . 33
2.3.3 Data and rewiring costs . . . . . . . . . . . . . . . . . . . . . 38
2.4 Simulation experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.2 Static networks . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.2.1 Uniform request rate . . . . . . . . . . . . . . . . . . 42
2.4.2.2 Varied request rate . . . . . . . . . . . . . . . . . . . 46
2.4.3 Dynamic networks . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4.4 Hierarchical DHTs . . . . . . . . . . . . . . . . . . . . . . . . 50
2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
iii
3 Identification of peer-to-peer hosts 56
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.1.2 Trace data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.1.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2 Feature set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2.1 Elementary features . . . . . . . . . . . . . . . . . . . . . . . 62
3.2.2 Triples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2.2.2 Counting triples . . . . . . . . . . . . . . . . . . . . 64
3.3 Classification results . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3.1 Determining the ?true? classes . . . . . . . . . . . . . . . . . . 67
3.3.2 Supervised learning techniques . . . . . . . . . . . . . . . . . . 69
3.3.2.1 Goals and definitions . . . . . . . . . . . . . . . . . . 70
3.3.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.3.4 Testing against the Memphis data set . . . . . . . . . . . . . . 73
3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4 Discrete analysis of crystal steps 78
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.1.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.2 Physical models of step motion . . . . . . . . . . . . . . . . . . . . . 82
4.2.1 Assumptions for the discrete model . . . . . . . . . . . . . . . 82
4.2.2 Discrete terrace equations . . . . . . . . . . . . . . . . . . . . 83
4.2.3 Discrete step boundary conditions . . . . . . . . . . . . . . . . 84
4.3 Step motion equation from the model . . . . . . . . . . . . . . . . . . 86
4.3.1 Adatom density and adatom current . . . . . . . . . . . . . . 86
4.3.2 Terrace width . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.4 Linearization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.4.1 Subordinate functions . . . . . . . . . . . . . . . . . . . . . . 89
4.4.2 Terrace width evolution . . . . . . . . . . . . . . . . . . . . . 90
4.4.3 Dependence on the physical parameters . . . . . . . . . . . . . 93
4.4.3.1 Non-interaction terms (O(1)) . . . . . . . . . . . . . 94
4.4.3.2 Step-step interaction terms (O(g)) . . . . . . . . . . 95
4.5 Solutions to linearized equation . . . . . . . . . . . . . . . . . . . . . 97
4.5.1 Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.5.2 Initial data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.5.3 Steepest descents . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.5.3.1 No step interactions (g = 0) . . . . . . . . . . . . . . 101
4.5.3.2 Step repulsions (g > 0) . . . . . . . . . . . . . . . . . 104
4.5.3.3 Relationship between the solutions (glessmuch1) . . . . . 108
4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
iv
A Addendum to Chapter 3 112
A.1 Standard ports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
B Addendum to Chapter 4 115
B.1 Parameters and variables of the crystal problem . . . . . . . . . . . . 115
Bibliography 116
Bibliography 121
v
List of Tables
2.1 Properties of the imposed capacity distribution . . . . . . . . . . . . 41
3.1 Traffic breakdown by port number . . . . . . . . . . . . . . . . . . . . 67
3.2 Counts of host types . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3 Success and false positive rates after 16 flows . . . . . . . . . . . . . . 75
3.4 Success and false positive rates after 64 seconds . . . . . . . . . . . . 76
A.1 Standard port usage for peer-to-peer applications . . . . . . . . . . . 112
A.2 Standard port usage for peer-to-peer applications (continued) . . . . 113
A.3 Standard port usage for client/server applications . . . . . . . . . . . 114
B.1 Parameters and variables of the crystal problem . . . . . . . . . . . . 115
vi
List of Figures
1.1 Cartoon diagrams of peer-to-peer systems . . . . . . . . . . . . . . . 4
1.2 Cartoon diagrams of crystal steps . . . . . . . . . . . . . . . . . . . . 10
2.1 Examples of reversed de Bruijn graphs . . . . . . . . . . . . . . . . . 17
2.2 Example of a reversed de Bruijn distributed hash table . . . . . . . . 18
2.3 Load distribution across a peer?s zone . . . . . . . . . . . . . . . . . . 34
2.4 Pseudocode for proportionate load balancing . . . . . . . . . . . . . . 36
2.5 Contracting and expanding zones . . . . . . . . . . . . . . . . . . . . 37
2.6 Static simulation results ? forward de Bruijn . . . . . . . . . . . . . 43
2.7 Static simulation results ? reversed de Bruijn . . . . . . . . . . . . . 44
2.8 Comparison of static simulation results . . . . . . . . . . . . . . . . . 45
2.9 Static simulation results for varied request rates . . . . . . . . . . . . 47
2.10 Dynamic simulation results . . . . . . . . . . . . . . . . . . . . . . . . 49
2.11 Hierarchical simulation results ? forward de Bruijn . . . . . . . . . . 51
2.12 Hierarchical simulation results ? reversed de Bruijn . . . . . . . . . . 52
3.1 Classification rates after a fixed number of flows/seconds . . . . . . . 74
4.1 Adatom motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.2 Integration contours (no step interaction) . . . . . . . . . . . . . . . . 101
4.3 Integration contours (positive step interaction) . . . . . . . . . . . . . 105
vii
Chapter 1
Introduction
1.1 Overview of the dissertation
Even simple, deterministic rules can generate interesting behavior in dynamical sys-
tems. For example, the logistic map exhibits chaos for certain parameter values. This
dissertation examines some real-world systems for which fairly simple, locally-defined
rules yield useful or interesting properties in the system as a whole.
The remaining sections of this chapter provide an introduction to modern peer-
to-peer networks and to crystal surfaces. We trace the history of peer-to-peer net-
works from completely centralized systems like Napster, to completely decentralized
systems like Gnutella, to hybrid systems like FastTrack, to alternative systems like
BitTorrent. We then give a detailed introduction to distributed hash tables, which are
decentralized but structured peer-to-peer systems. Finally, we discuss the motivation
behind the study of crystal steps and the step bunching phenomenon.
In Chapter 2, we address the issue of heterogeneity in peer-to-peer networks.
By heterogeneity, we refer to the fact that peers can vary by three orders of mag-
nitude in their capacities to process traffic. We define and analyze networks based
on two routing methods for de Bruijn graphs, introducing a new ?reversed? routing
method which performs better than standard forward routing in some cases. We
quantify how heterogeneity affects the average query path length under each routing
1
method, proving that the length decreases in most cases. We also provide an imple-
mentation of what we term ?proportionate load balancing,? which is applicable to
a range of peer-to-peer networks. Proportionate load balancing employs small local
adjustments to bring the entire network into a global balance, where each participant
provides resources in proportion to its capacity. We demonstrate the effectiveness of
proportionate load balancing on de Bruijn networks.
Chapter 3 explores the use of supervised machine learning to identify peer-
to-peer hosts, without using port numbers or other application-specific information.
Most studies in this area have attempted to classify TCP flows, rather than individual
users. We introduce a model for ?triples,? which capture the composite behavior
available when we study hosts rather than flows. Triples exploit information about
nearly-contemporaneous flows to give a statistical picture of a host as a whole. We
find that triples, together with measurements of inbound vs. outbound traffic, can
capture most of the behavior of peer-to-peer hosts, while maintaining acceptable
?false-positive? rates.
In Chapter 4, we analyze a discrete model for crystal steps. In this model, the
motion of each step depends on the two steps on either side of it. We evaluate the
effect of step-step interactions on the stability of the crystal surface, with a focus on
step bunching.
2
1.2 Peer-to-peer networks
Classical internet activity fits the client-server model, where powerful central comput-
ers (the servers) provide resources to lower-capacity end users (the clients). Some ex-
amples of servers include cnn.com, which disseminates news; microsoft.com, which
distributes Windows updates; yahoo.com, which provides forums for games and chat-
ting; or the machines that handle all umd.edu email.
Peer-to-peer (P2P) applications, on the other hand, represent a distributed type
of internet activity. A peer-to-peer network is a collection of machines that associate
with one another to share files or other resources. A P2P network may have servers
that facilitate these communications, but unlike in a client-server setup, the servers
do not provide all of the content.
1.2.1 Statistics
Up to 60% of worldwide Internet traffic is peer-to-peer [42]. Most peer-to-peer ap-
plications are used for file sharing ? sending files directly between end-users. By
volume, P2P traffic is [42]
? 61% video content,
? 11% audio content,
? 11% compressed files,
? 17% other.
3
(a) A centralized P2P system. (b) A decentralized P2P system.
Figure 1.1: Peer-to-peer applications may be divided broadly into two classes.
Centralized systems have a server that organizes file sharing for a large number
of subsidiary users; this server is a bottleneck and single point of failure for
the system. Decentralized systems lack a central authority, so they avoid the
weaknesses of centralized systems; however, searches can only follow a limited
number of paths, so such systems can be highly inefficient.
$2.3 billion in copyrighted movies were downloaded worldwide in 2005 [36]. Only 13%
of that loss came from users in the United States.
1.2.2 History
Broadly, there are two classes of peer-to-peer applications: centralized and decentral-
ized. See Figure 1.1.
Centralized systems (Napster, DirectConnect, BitTorrent) have a computer that
acts as a hub to organize file transmissions for a large number of client computers.
Napster had a single hub for all its users; DirectConnect has many disjoint sets of
clients and a hub; BitTorrent has a hub for every individual file. Despite their central-
4
ized organization, these systems are peer-to-peer because shared files are transmitted
directly between clients. The hubs act only as facilitators to help clients find other
users who possess the information they want, not as content servers. The hubs also
provide an obvious target for disabling the network; Napster was shut down by court
order in July 2001 [53].
Decentralized systems (Gnutella, FastTrack (Kazaa), distributed hash tables
(Kademilia)) have each peer connected to some small number of other peers, without
a central authority, so searches for files must be distributed through their networks.
Gnutella became popular with the demise of Napster. It employs flooding, where a
peer asks its connected peers if they have a certain file, whereupon they ask their
connected peers, etc. FastTrack automatically divides its peers into clients and su-
pernodes, with supernodes performing searches in a Gnutella-like fashion for their
connected clients. Distributed hash tables are structured to provide more efficient
searches in exhange for the overhead of maintaining the structure. In all cases, once
the requested file is located, it is transferred between the relevant clients.
Some systems (eDonkey2000) seem to lie between the two extremes. eDon-
key2000 originally acted like DirectConnect with disjoint hub networks, but it now
allows the hubs to pass searches among themselves.
5
1.3 Distributed hash tables
Distributed hash tables (DHTs) form completely decentralized P2P systems which,
due to an imposed structure, have reliable and efficient search methods. See [32] for
details on several popular protocols. Let P be the set of peers. In general, DHTs
have three structural components:
1. A keyspace K, with a publicly-known function f : {data items} ? K that
assigns keys to data items.
2. A rule for assigning a portion, or zone, of the keyspace to each peer i?P, such
that uniontexti?P zone(i) =K.
3. A set of application-level connections, assigned between peers based on the keys
in their zones.
In the following subsections, we formalize this definition, then briefly discuss
the operation and maintenance of DHTs.
1.3.1 Continuous-discrete definition
For definiteness, we describe Naor and Wieder?s continuous-discrete approach [37] to
defining DHTs. In this framework,
1. Kis a continuous space. There is a graph Gcont that hasKas its vertex set. (f
is unrestricted; it is often taken to be a uniform hash function.)
2. Kis decomposed into possibly-overlapping, connected zones, one per peer.
6
3. If Gcont has an edge from zone(i) to zone(j), then there may be an application-
level link from peer i to peer j. This yields a discrete graph Gdisc on the vertex
setP of peers.
In Chapter 2, we will define proportionate load balancing for DHTs that have
a one-dimensional keyspace K = [0,1) mod 1. With this type of DHT, peer zones
are simply intervals. Peer i has label id(i), and should keep track of (at least) its
immediate predecessor pred(i) and successor succ(i), which are the peers such that
id(j)?(id(pred(i)),id(succ(i))) ?? j = i. (1.1)
We use the following definitions in this paper.
? Zone: zone(i) = [id(i),id(succ(i))) mod 1
? Zone size: zi = id(succ(i))?id(i) mod 1
? Relative zone size: ri = nzi, the ratio of zi to the average zone size 1n
1.3.2 Data sharing
DHTs operate successfully because every peer knows to treat the location idx =
f(x) ?K as the authority on information about the data item x. Suppose idx ?
zone(i). Fundamentally, DHTs need to provide just one operation: lookup :K?P:
idx mapsto?i, which passes messages through the network to locate the peer in charge of
item x.
Data items (files) enter the network by having a peer elect to share them. If
peer o (the ?owner?) elects to share item x, it executes lookup(f(x)) to find the peer
7
i (the ?intermediary?) in charge of idx. Peer o then gives its contact information to
peer i.
When another peer s (the ?seeker?) wants to find item x, it also executes
lookup(f(x)) to find the peer i. Peer i reports peer o?s contact information to peer s,
so that s can obtain x from o. If no peer has elected to share the item x, peer i can
definitively alert peer s to this fact.
In a network of n peers, many (though not all) DHTs provide search times of
orderO(log2(n)) withO(log2(n)) connections per peer. In Chapter 2, we will explain
the lookup operation in detail for de Bruijn networks. These networks provide search
times of orderO(log2(n)) with onlyO(k) connections per peer.
1.3.3 Maintenance of the network
New peers join the network by a process known as bootstrapping. A new peer must
locate a peer already in the network, often via a list of IP addresses for computers
known to have been connected in the past. The new peer locates a target through
this intermediary, and consults with the target to divide that zone between them.
A peer can sign off of the network by transferring its zone to another peer with
a consecutive region of the keyspace. If, instead, the peer simply drops out of the
network without notifying any of its neighbors, a period of time is necessary for the
network to completely recover. Ensuring satisfactory performance during this period
is a subject of much study [44]. Typically, peers will re-advertise their available files
periodically in order to assist in the recovery.
8
1.4 Crystal surfaces
An understanding of crystal surface evolution is important for modern nanoscale
applications, such as nanowires and quantum dots [69]. A variety of surface features
[81] can occur. For sufficiently low temperatures, crystal steps are the dominant
feature on a crystal surface cut close to a plane of symmetry.
Specifically, a crystal lattice has certain planes of symmetry that depend on the
lattice structure. A cubic lattice has three perpendicular planes of symmetry. The
crystal can be cut at a ?vicinal angle? ? << 1 away from a plane of symmetry. At
high temperatures, the surface will be statistically rough, but at temperatures T less
than the ?roughening temperature? TR (which depends on the material), observable
steps form. See Figure 1.2. The terraces have an average length L?cot(?).
Step bunching is a widely studied surface phenomenon. In the one-dimensional
model, one equilibrium state is a train of uniformly-spaced steps. In contrast, under
the step bunching instability, steps arrange themselves into widely-separated clusters
of tightly-packed steps. This bunching has been observed in a variety of experimental
systems, most commonly as a result of electromigration due to an applied direct
current [70], but also as a result of material deposition onto the surface [65]. Such
experimental observations have motivated interest in a theoretical understanding of
the phenomenon.
9
(a) Crystal steps with curvature. (b) Straight crystal steps.
Figure 1.2: At sufficiently low temperatures, steps are observable on a crystal
surface cut close to a plane of symmetry. The steps are approximately one
lattice constant high, and the terraces are typically tens or hundreds of lattice
constants wide. Real crystal steps have kinks, islands, vacancies, and other
imperfections, but they can be effectively modeled by smooth curved steps as
in Figure 1.2(a). Under certain conditions, the steps can be considered to have
zero curvature, as in Figure 1.2(b). This allows one-dimensional modeling of
step positions.
10
Chapter 2
Exploiting heterogeneity
2.1 Introduction
Internet-enabled computers are heterogeneous, in that their capacities to process
traffic vary widely [46, 29]. In a peer-to-peer situation, it can be considered equitable
for the more capable peers to handle a larger fraction of the traffic [44]. We will
equalize the utilizations of the peers, where utilization is defined in Section 2.3.1 as
the fraction of a peer?s capacity that is used by the P2P application.
We refer to the operation of equalizing utilizations as proportionate load balanc-
ing (PLB). This name distinguishes it from typical notions of load balancing, where
the absolute amount of traffic to each peer is equalized. We will demonstrate analyt-
ically and through simulations that leveraging heterogeneity can improve the query
path length and congestion in a particular class of distributed hash tables, the de
Bruijn DHTs.
2.1.1 Related work
DHTs based on the de Bruijn architecture have been studied previously [16, 37, 25,
31, 17, 2]. We will present the basics of both forward and reversed de Bruijn net-
works. In particular, we offer an algorithm for routing in reversed de Bruijn networks
(?reversed routing?) that is novel for being provably correct, i.e., the destination is
11
always reached in absence of node failures. Broose [17] provided a reversed routing
algorithm where the probability of failing to reach the desired destination was nonzero
(but small under the assumption of homogeneous zone sizes). Distance Halving [37]
defined its underlying architecture in a reversed manner, but only provided routing
algorithms that relied (in whole or in part) on forward routing. D2B [16], Koorde
[25], and ODRI [31] worked exclusively with forward networks. All of these employed
an assumption of homogeneity in the partitioning of the keyspace.
Demand on the network?s peers can differ for several reasons: (i) nonuniform
numbers of data items may be assigned to the peers [21]; (ii) data items of varying
popularities may receive highly nonuniform numbers of requests [28]; and (iii) the net-
work structure may cause demand to vary inherently, as we will see in Section 2.3.2.2.
Some prior approaches to coping with peer heterogeneity have divided the peers into
a hierarchy of two or more levels based on their capacities [19]. Other approaches
have employed a varying number of ?virtual servers? [9, 22] for each peer. These
approaches essentially use (i) to address heterogeneous peer capacities, but lack the
real-time adaptability to deal with (ii) and (iii).
Our PLB implementation allows continuous variability in load distribution, and
keeps the simplicity of a single-level DHT structure. Unlike a recent implementation
[20], it allows continuous variability in peer capacities, and seeks to balance the ratio
of these capacities to the actual traffic load at each peer, not simply to the amount
of keyspace assigned to each peer. It also operates throughout the peers? lifetimes,
not just during the process of joining or leaving the network.
Initially, proportionate load balancing seems similar to load balancing in het-
12
erogeneous processor networks [14]. While our implementation of PLB is similar to
first-order diffusion schemes for processor networks, or the NbrAdjust operation for
parallel databases [18], the problem setting is different. In P2P networks, traffic load
is intimately tied to network structure. We modify the structure to balance queries
at all stages along the search path, not just in the final stage of actually serving the
response to a request.
2.1.2 DHTs and proportionate load balancing
As noted above, most protocols call for all peers to hold zones of approximately equal
size [54], so that absolute traffic levels are nearly equal. However, by assigning more
traffic to peers with higher capacity, PLB can balance their relative traffic levels.
We will demonstrate how this is possible in certain DHTs, where the number of
connections a peer has, and thus the amount of traffic it processes, depends on the
size of its zone.
All DHTs that use the continuous-discrete framework of Section 1.3.1 satisfy
the following assumption, which is critical for our implementation of proportionate
load balancing.
(A1) The expected number of routing paths that pass through a given peer in-
creases with the relative size of its zone.
Well-known examples where Assumption A1 holds include CAN [32] and ODRI [31].
The proofs in Section 2.2.2 will rely in part on the following assumption.
(A2) The peers occur in a random order in the keyspace, that is, P(j = succ(i)) =
13
1
n?1 for all jnegationslash= i.
2.1.3 Overview
The remainder of this chapter is structured as follows. In Section 2.2 we define two
classes of de Bruijn DHTs and analytically examine them under heterogeneous struc-
ture. In Section 2.3 we present a simple scheme for dynamically adapting DHTs (not
necessarily de Bruijn) to exploit heterogeneity. In Section 2.4 we present simulation
results.
14
2.2 Heterogeneous de Bruijn networks
Researchers have studied de Bruijn DHTs because they offer the potential for loga-
rithmic diameter logk(#peers) with constant degree k. We use them because they
have node degree intimately tied to zone size [54], making them good candidates for
proportionate load balancing.
Some arguments have been made against the practicality of de Bruijn DHTs [10].
First, heterogeneous partitioning of the keyspace prevents de Bruijn peers from having
constant degree [10]. We embrace this disparity by providing the larger zones to peers
with more capacity. Second, some peers in a DHT must have degree ?(log(#peers))
(unlike the peers in a classical de Bruijn network) if the network is to remain connected
when half the peers fail [25]. By allowing varying peer degrees (Section 2.2.2.1) and
using an average degree k > 2 ([10] footnote 1), we can achieve a balance between
fault-tolerance and maintenance costs. Third, the path between two peers may be
?(#peers) in the worst case. If the ordering of the peers in the keyspace is random,
the probability of this is low; furthermore, heterogeneity improves the expected query
path length (Section 2.2.2.2).
In this section, we will present the basics of both forward and reversed de Bruijn
networks. The authors of Koorde and D2B provided more complete P2P protocols
[25, 16] than we offer here. The authors of ODRI offered comparisons of de Bruijn with
other DHT structures, including discussions of diameter, routing, and fault tolerance
[31].
15
2.2.1 Forward and reversed de Bruijn networks
In this section, we first define continuous versions of forward and reversed de Bruijn
graphs. We then show how to discretize these systems to obtain de Bruijn distributed
hash tables.
2.2.1.1 de Bruijn graphs (continuous model)
The underlying space is the unit interval [0,1) mod 1. When considering graphs of
degree k (integer?2), we will represent the values in base k, i.e.,
a = .a1a2a3???=
?summationdisplay
i=1
ai
ki ?[0,1) (2.1)
where each ai?Zk ={0,1,...,k?1}. The value of k should be a reasonable number
of connections for each peer to maintain, e.g., k = 8 or k = 16.
2.2.1.1.1 Forward de Bruijn graphs Algebraically, each point a ? [0,1) has
one outgoing edge, to the point ka mod 1. Symbolically, this is represented as an
edge .a1a2a3????.a2a3a4???. We can thus refer to these as left-shifting graphs.
2.2.1.1.2 Reversed de Bruijn graphs Algebraically, each point a?[0,1) has
k outgoing edges, to the points (a + x)/k mod 1, for x ? Zk. Symbolically, these
are represented as edges .a1a2a3??? ? .xa1a2???. We can thus refer to these as
right-shifting graphs.
2.2.1.1.3 Comments The outgoing neighbors of a vertex in a reversed de Bruijn
graph are its incoming neighbors in the corresponding forward de Bruijn graph, and
16
.01 d47d47
d20d20
.00d82d82
d125d125d124d124d124
d124d124d124
d124d124d124
d124d124d124
d124d124d124
d124d124
.10
d84d84
d47d47 .11
d97d97d66d66d66
d66d66d66
d66d66d66
d66d66d66
d66d66d66
d66d66
d117d117
(a) k = D = 2
.010 d47d47
d18d18
.001
d35d35d71d71d71
d71d71d71d71
d71d71
d123d123d119d119d119d119
d119d119d119d119
d119d119d119d119
d119d119d119d119
d119d119d119d119
d119
.011
d53d53d107d107d107d107d107
d107d107d107d107d107d107
d107d107d107d107d107
d26d26d53d53
d53d53d53
d53d53d53
d53d53d53
d53d53d53
d53 .000d82d82
d115d115d103d103d103d103d103d103d103d103
d103d103d103d103d103d103d103d103
d103d103d103d103d103d103d103d103
d103d103
.100
d68d68d9d9
d9d9d9
d9d9d9
d9d9d9
d9d9d9
d9
d41d41d83d83d83d83d83
d83d83d83d83d83d83
d83d83d83d83d83 .111
d107d107d87d87d87d87d87d87d87d87
d87d87d87d87d87d87d87d87
d87d87d87d87d87d87d87d87
d87d87 d12d12
.101
d82d82
d47d47 .110
d99d99d71d71d71d71
d71d71d71d71
d71d71d71d71
d71d71d71d71
d71d71d71d71
d71
d59d59d119d119d119
d119d119d119d119
d119d119
(b) k = 2, D = 3
Figure 2.1: Two reversed de Bruijn graphs on finite spaces{.a1a2???aD : ai?
Zk}. Each graph has kD vertices; each vertex has in- and out-degree k = 2.
The diameter of each graph is observably D.
vice versa.
In some applications, the underlying space may be taken as a collection of
elements {.a1a2???aD : ai ?Zk} (D fixed) that is finite but still much larger (e.g.,
2128) than the set of peers might ever be. In this case, each vertex in the forward
graph has k outgoing edges: .a1a2???aD?1aD ?.a2a3???aDy, y?Zk. The diameter
(the maximum length of any shortest path between vertices) of the resultant forward
and reversed graphs is D. Fig. 2.1 shows two reversed de Bruijn graphs on small
underlying spaces.
2.2.1.2 de Bruijn networks (discrete model)
As in Section 1.3, to create a distributed hash table, we assign each peer i an iden-
tifier id(i) in accordance with Eq. (1.1). Peer i then controls the segment zone(i) =
[id(i),id(succ(i))), and has links to all peers in control of zones where some underlying
17
.00001
.01010
.01111
.10010
.10110 .11010
(a) Outgoing edges
.00001
.01010
.01111
.10010
.10110 .11010
(b) Incoming edges
Figure 2.2: Here k = 2. The six large dots are the ids chosen by six peers,
and the arcs depict the zone each peer is in charge of. Fig. 2.2(a) shows
the outgoing edges for the peer with key .01010?0, while Fig. 2.2(b) shows
the incoming edges for that same peer. The dashed lines are some of the
relevant edges in the underlying reversed de Bruijn graph. The peer will have
network-level connections to (or from) all zones matching at least one of these
de Bruijn edges ? the solid lines show these resulting connections in the P2P
network.
edge from zone(i) terminates. See Fig. 2.2.
We now describe algorithms for routing in de Bruijn DHTs, and verify their
correctness. We will suppose that peer i initiates a request for an item with key
b = .b1b2b3???, which lies in some other peer?s zone(j).
2.2.1.2.1 Forward routing Let d be such that k?d?zi. Then for any sequence
.b1b2b3???, there exist a1,a2,...,ad ? Zk such that .a1a2???adb1b2b3???? zone(i).
18
At most two values of (a1,a2,...,ad) are required, and peer i can calculate them.
Following the sequence
.a1a2???ad?1 ad b1 b2 ????
.a2a3??? ad b1 b2 b3 ????
...
.adb1???bd?2bd?1 bd bd+1????
.b1b2???bd?1 bd bd+1bd+2???= b
(2.2)
of underlying edges yields a valid path of peer links through the network, starting
at peer i and terminating at the appropriate peer j in d steps. The next hop is
computable locally by each peer involved.
2.2.1.2.2 Reversed routing Let d be such that (b?k?d,b + k?d)?zone(j).1
(Peer i cannot determine d under our assumption of heterogeneity; we will deal with
this difficulty soon.) Then any point .b1b2???bdc1c2c3??? lies in (b?k?d,b+k?d) and
thus is covered by zone(j). Following any sequence
.c1c2??? cd cd+1cd+2????
.bdc1???cd?1 cd cd+1????
...
.b2b3??? c1 c2 c3 ????
.b1b2??? bd c1 c2 ????zone(j)
(2.3)
1What happens if b = id(j)? In the continuous case, this happens with probability 0, but can
still be corrected by requiring peer j?1 to forward requests for b to peer j. In the case of a finite
underlying space{.a1a2???aD : ai?Zk}, we may take d = D.
19
of underlying edges yields a valid path of peer links, starting at an arbitrary point c
and terminating at the appropriate peer j in d steps.
Since the optimal value of d, dmin, cannot be determined a priori by the source
peer i, we must modify the procedure in Eq. (2.3). Peer i should perform exponential
polling until dmin is exceeded, trying values d = 1,2,4,8,16,.... The queries need
not be returned to i between failed attempts. That is, usinga59d to denote the d-step
procedure in Eq. (2.3), and starting at id(i) = a = .a1a2a3???, the sequence
a a591 .b1 a
.b1a a592 .b1b2 b1a
.b1b2b1a a594 .b1b2b3b4 b1b2b1a (2.4)
.b1b2b3b4b1b2b1a a598 .b1???b8 b1b2b3b4b1b2b1a
...
reaches zone(j) in finite time. Letting 2h?1 < dmin ? 2h, the total number of steps
is lscript = 1 + 2 + 4 +???+ 2h = 2h+1 ?1 ? [2dmin ?1,4dmin ?1). The next hop is
computable locally by each peer involved, as long as the current ?stage? (1, 2, 4, 8,
...) is included with the message header.
Alternatively, peer i can send out multiple messages simultaneously, aa591 .b1a,
aa592 .b1b2a, ..., aa592g .b1???b2ga. If no response is received, g should be increased.
The value of g can be based on prior experience. The number of messages is the same
as Eq. (2.4), but the response time is shorter because some are sent in parallel.
Of course, in either case, it is probably desirable to have a larger first attempt
aa592f .b1???b2fa, 2f > 1.
20
2.2.2 Heterogeneity in de Bruijn networks
We now offer analytical analyses of de Bruijn DHTs under heterogeneity. To our
knowledge, this is the first such analysis for either forward or reversed networks.
Section 2.2.2.1 shows that forward networks are much more liable to develop peers
with only one outgoing neighbor, which are susceptible to disconnection from the
graph. Section 2.2.2.2 demonstrates that high variance among zone sizes always
reduces the query path length of reversed networks under reasonable assumptions, but
that there are reasonable assumptions for forward networks that yield longer query
path lengths. Finally, Section 2.2.2.3 discusses the use of caching as a complementary
tool to PLB.
2.2.2.1 Number of neighbors
We begin with a simple property: node degree. If we were assuming homogeneity
and roughly equal zone sizes, all peers would have in-degree and out-degree very near
k [31]. However, as the zone sizes vary in our heterogeneous networks, the degrees
become non-uniform.
2.2.2.1.1 Forward and reversed neighbors
Theorem 2.1. Suppose peer i has relative zone size ri in either a forward or reversed
de Bruijn DHT with n peers.
? Averaging over forward de Bruijn DHTs, peer i expects to have kfwdi = 1 + kri
outgoing links to other peers.
21
? Averaging over reversed de Bruijn DHTs, peer i expects to have krevi = k + ri
outgoing links to other peers.
Note that kfwdi and krevi are independent of n.
Proof. We begin with a general fact: If a DHT has n arbitrarily-ordered peers, and
[a,b) is an interval in the keyspace [0,1), then the expected number of distinct peers
in charge of some or all of [a,b) is n(b?a) + 1. Since the n peers are arranged in
no particular order by Assumption A2, the expected number of peers that lie inside
(a,b) is n(b?a). Each of these peers is in charge of a portion of [a,b). Additionally,
there is another peer whose key either is a or immediately precedes a; this peer is in
charge of the first portion of [a,b).
Now recall that zone(i) = [id(i), id(succ(i))).
In the forward case, zone(i) maps to [kid(i), kid(succ(i))), an interval of length
kzi. Then peer i expects to connect to n?kzi + 1 = 1 + kri peers.
In the reversed case, zone(i) maps to k evenly-spaced intervals [id(i)k , id(succ(i))k )+
x
k, x?Zk. Each of these intervals has length
1
kzi. Then peer i expects to connect to
k(n? 1kzi + 1) = k +ri peers.
In the reversed case, even if ri is very small, krevi ?k. Therefore, even a very
weak peer will have alternative paths to route a query through if one of its neighbors
fails. In the forward case, if ri is very small, then kfwdi ? 1 and the peer will be
susceptible to disconnection from the graph ([54], Section 2).
The expected number of links for a peer with an average-sized zone (ri = 1) is
k+1, rather than k, which is the number of links in a uniform de Bruijn graph. This
22
is because the uniform graph is unstable with respect to all of its zone boundaries
lining up.
We note that the number of incoming links in a forward DHT is the number of
outgoing links in the corresponding reversed DHT, and vice versa. However, incoming
links do not directly help with routing around a failed neighbor.
2.2.2.1.2 Cost of PLB In Section 2.3.3, we will discuss the number of peers who
must be notified when peer i participates in our implementation of PLB. In the worst
case, all the in- and out-neighbors of either peer pred(i) or i must be notified of a
change in id(i).
By Theorem 2.1, we expect the number of neighbors that must be contacted (in
either the forward or reversed case) to be?kfwd+krev = (k+1)(max{ri,rpred(i)}+1).
2.2.2.2 Query path lengths
If we were assuming homogeneity, so all n peers had roughly equal zone sizes, then
we would have d?logk n for both the forward and reversed cases. Thus the number
of routing steps would be O(logk n), as in [37, 25, 16, 17, 31]. We note that linear
polling in the reversed case (trying values d = 1,2,3,4,5,...) would have resulted in
O((logk n)2) steps.
In this paper we assume heterogeneity of peers and zone sizes. The average
number of routing steps will depend on these quantities:
? r = (r1,...,rn), the relative zone sizes.
? ? = (?1,...,?n), the relative rates at which the peers request items. Reasonable
23
values: ? = 1 (uniform rates); ? = (cap(1),...,cap(n)), where cap(i) is the
capacity2 of the ith peer (faster peers make more queries).
? ? = (?1,...,?n), the relative rates at which the peers supply items. Reasonable
value: ? = r (number of data items controlled is proportional to zone size).
Hot spots (Section 2.2.2.3) may yield a ? that is essentially random if caching
is not employed.
We will employ the fact that the weighted geometric mean
wGm(r;?) =
parenleftbigg nproductdisplay
i=1
r?ii
parenrightbigg1/Pni=1 ?i
(2.5)
is always less than or equal to the weighted arithmetic mean
wAm(r;?) =
summationtextn
i=1 ?irisummationtextn
i=1 ?i
(2.6)
with equality iff all ri are equal. The proof is via Jensen?s inequality.
It will be useful to have an estimate of logkwGm(r;r). Let f(x) = xlogk x; f
is infinitely differentiable and concave up on the interval I = [rmin,rmax] ? (0,?).
Taylor?s Theorem says that for any points a,a + h?I and some point ?h between a
and a +h,
f(a +h) = f(a) +fprime(a)h + 12fprimeprime(?h)h2 (2.7)
= alogk a + logk(ea)h+ 12lnk??1h h2 (2.8)
?alogk a + logk(ea)h+ 12lnkr?1maxh2. (2.9)
2A peer?s capacity is the rate at which it can process P2P traffic; see Section 2.3.1.
24
The mean 1nsummationtextni=1 ri = 1, so let si = ri?1. Then summationtextni=1 si = 0. Finally,
logkwGm(r;r) = 1n
nsummationdisplay
i=1
ri logk ri (2.10)
= 1n
nsummationdisplay
i=1
f(1 +si) (2.11)
? 1n
parenleftbigg
0 + logk(e)si + 12lnkr?1maxs2i
parenrightbigg
(2.12)
= 12lnkr?1max 1ns2i (2.13)
= 12lnkr?1maxVar{ri}. (2.14)
2.2.2.2.1 Forward query path lengths
Theorem 2.2. Consider a forward de Bruijn DHT with n peers.
? The length of the path from peer i to any given destination is
lscriptfwdj =ceilingleftlogk n?logk riceilingright. (2.15)
? Taking a weighted average over all peers i in the network gives the the average
query path length
?lscriptfwd = logk n?logkwGm(r;?) +C (2.16)
for some 0 < C < 1.
Proof. From Section 2.2.1.2.1, the length of the path from i to any b is
di =ceilingleftlogkparenleftbigz?1i parenrightbigceilingright= logk n?logk ri +epsilon1i, (2.17)
for some 0?epsilon1i < 1. For the second part of the theorem, we have
?lscriptfwd =
parenleftBigg nsummationdisplay
i=1
?i(logk n?logk ri +epsilon1i)
parenrightBiggparenleftBigg nsummationdisplay
i=1
?i
parenrightBigg?1
(2.18)
= logk n?logkwGm(r;?) +wAm(epsilon1;?) (2.19)
25
yielding Eq. (2.16).
If all peers have the same request rate (? = 1), then
logkwGm(r;1)?logkwAm(r;1) = logk 1 = 0, (2.20)
so the average query path length is at least logk n. On the other hand, if peers with
larger zones also have larger ?i (e.g., ? = (cap(1),...,cap(n)) and some form of PLB
has been performed), thenwAm(r;?) > 1 and the average query path length can be
less than logk n.
2.2.2.2.2 Reversed query path lengths We begin with a lemma.
Lemma 2.1. Consider a peer j in a reversed de Bruijn DHT with n peers. If b?
zone(j), let db be minimal such that .b1b2???bdbc1c2????zone(j) for all c. Then the
expected value of db over zone(j) is
?dj = logk n?logk rj +C(j)k (2.21)
where 0 < C(j)k < 2 + 1log
2 k
+ 1k?1 ?4.
Proof. We will perform the computation assuming b is in the left half of zone(j);
the argument for the right half is symmetric. Recall from Section 2.2.1.2.2 that db is
minimal such that (b?k?db,b+k?db)?zone(j). Thus b?id(j)?[k?db,k?db+1).
Let m be such that id(j) + [k?m,k?m+1) contains the midpoint of zone(j); we
find m =ceilingleft?logk zj2ceilingright. Then db is a step function on its half of zone(j), given by
db =
?
???
?
???
?
d if d > m and b?id(j)?[k?d,k?d+1),
m if b?id(j)?[k?m, zj2 ].
(2.22)
26
The expected value of db is found by weighted average:
?dj =
bracketleftBigg ?summationdisplay
d=m+1
dparenleftbigk?d+1?k?dparenrightbig (2.23)
+m
parenleftBigzj
2 ?k
?m
parenrightBigbracketrightBig
/zj2 (2.24)
=
bracketleftbiggk?m+1
k?1 +m
zj
2
bracketrightbigg
/zj2 (2.25)
=ceilingleftlogk n?logk rj + logk 2ceilingright+ k
?m+1
(k?1)zj2 . (2.26)
We have used Gabriel?s truncated staircase,summationtext?i=m+1 iri = mrm+11?r + rm+1(1?r)2 for 0 < r < 1.
By definition of m, k?m+1 ? (zj2 ,kzj2 ]. Thus the final term satisfies k?m+1(k?1)zj
2
?
( 1k?1, kk?1]?(0,2], yielding Eq. (2.21).
We now proceed to the theorem that is the main result of this subsection.
Theorem 2.3. Consider a reversed de Bruijn DHT with n peers.
? Averaging over all destinations b chosen uniformly at random from zone(j), the
expected length of the path from any given peer to b is
lscriptrevi ???
parenleftBig
logk n?logk rj +C(j)k
parenrightBig
?1, (2.27)
where ??4.
? Taking a weighted average over all destination zones j in the network gives the
the average query path length
?lscriptrev ???(logk n?logkwGm(r;?) +Ck). (2.28)
Here C(j)k and Ck are positive values bounded by 2 + 1log
2 k
+ 1k?1 ?4.
27
Proof. In Section 2.2.1.2.2, we found that the number of steps ?lscriptjrev = 2ceilingleftlog2 ?djceilingright+1?1 <
4?dj?1, yielding the first part of the theorem with ? = 4.
For the second part of the theorem, we average over all destination zones j,
?lscriptrev =
parenleftBigg nsummationdisplay
j=1
?j ?lscriptjrev
parenrightBigg
/
nsummationdisplay
j=1
?j (2.29)
?
parenleftBigg nsummationdisplay
j=1
?j??(logk n?logk rj +C(j)k )
parenrightBiggparenleftBigg nsummationdisplay
j=1
?j
parenrightBigg?1
(2.30)
= ??parenleftbiglogk n?logkwGm(r;?) +wAm(C(k)r ;?)parenrightbig (2.31)
yielding Eq. (2.28).
In practice, ? will depend on the distribution of the ?dj. Letting hj =ceilingleftlog2 ?djceilingright,
we have ? = 2hj+1/?dj. If ?dj were uniformly distributed in (2hj?1,2hj], then E(?) =
4ln2?2.8. If ?dj were distributed as 1/x in (2hj?1,2hj] (such as by Benford?s Law),
then E(?) = 2/ln2?2.9.
If received requests are proportional to zone size (? = r), then logkwGm(r;r) >
0, and the average query path length will be less than logk n. In particular, we saw
above that logkwGm(r;r)? 12lnkr?1maxVar{ri}, so high variance among zone sizes has
a beneficial effect on the average query path length.
2.2.2.3 Caching
Dynamic cachingis animportanttoolforrelieving hot spots [28] ?items withextreme
popularity that cause acute congestion for the peers that host them. Caching is a
process for replicating such items at multiple nodes, to distribute the workload.
Caching is compatible with PLB and provides a complementary benefit. Since
28
PLB is based on the actual amount of traffic processed by each peer, it is able to deal
with hot spots to some degree, but caching can be faster and more effective. On the
other hand, caching is not designed to alter the structure of the network in order to
take advantage of heterogeneity.
2.2.2.3.1 Forward caching Forward de Bruijn DHTs permit a simple caching
scheme [17, 37]. A hot spot at location b ? [0,1) should be replicated at the k
predecessor locations b+xk = .xb1b2???, x ? Zk. Then a request for b will always
pass through one of these caches, each with equal probability. The replication can be
repeated as necessary.
2.2.2.3.2 Reversed caching The analogous scheme does not work for reversed
de Bruijn DHTs, since there is only one predecessor location kb mod 1 to the hot
spot b. A routing-independent caching scheme such as [28] could be used. Al-
ternatively, a peer that routes more than a certain number of requests for item b
can begin caching the item, until some set of peers together controlling the inter-
val .bcrit???b2hb1???b2h?1???b1b2b1c, for all c ? [0,1), distributes the workload to a
satisfactory level. (Here bcrit is the first value for which the workload is distributed
satisfactorily.)
29
2.3 Proportionate load balancing
In this section, we present an implementation of proportionate load balancing in the
context of continuous-discrete DHTs (Section 1.3), not necessarily de Bruijn. Using
only information about itself and the two peers adjacent to it in the keyspace [0,1),
each peer will increase or decrease its zone size. Assumption 1 indicates that, over
time, this should equalize all peers? utilizations. We stress that in simulations, we
will have all peers alter their zone sizes simultaneously on clock ticks, but in reality
a peer can alter its zone size more or less often depending on its individual needs.
2.3.1 Definitions
The capacity of a peer (cap(i)) is the rate at which it is able to process traffic for the
P2P application. Generally, the outbound traffic rate will be the limiting factor [29].
Plots of estimated bottleneck bandwidths for peers in the Napster and Gnutella [32]
networks are given in Section 3.1 of [46]; these plots show that there are frequently
orders of magnitude differences between peer capacities.
Capacity is difficult to measure from the outside, but a peer can keep track of
its own capacity with relative ease. To discourage under-reporting of capacity, peers
might limit the rate at which they transfer files to peer i to be some multiple of i?s
published capacity. This does not affect the implementation of PLB. Over-reporting is
a more complex issue, but not an insurmountable one. The predecessor and successor
of a newly joined peer can restrict the growth of its zone by modifying the algorithm
of Section 2.3.2.2. If a misbehaving peer does obtain a large zone and fails to pass on
30
all its messages, it can be treated like a failed peer as in Section 2.3.2.1.
The load of a peer (load(i)) is the rate at which the network asks it to pro-
cess P2P traffic. A peer can keep track of this value, perhaps as an exponentially
weighted moving average. Load is a dynamic quantity that can depend on relative
zone size (Theorem 2.1), global network structure (Fig. 2.3), and key popularity (Sec-
tion 2.2.2.3) in a complicated way.
The utilization of a peer (util(i)) is a dimensionless quantity equal to the ratio
of its load and capacity: util(i) = load(i)cap(i) . In order for a peer to keep up with its
requests, its utilization should remain below 1.
2.3.2 Implementation
In our implementation, peer i is only required to keep track of limited information:
For the DHT: Its zone zone(i) = [id(i),id(succ(i))) and the data items that
map to it. Links to its neighbors in the underlying graph, for routing. Links to peers
pred(i) and succ(i), for consistency.
For PLB: The capacity, load, and utilization of itself and peers pred(i) and
succ(i).
2.3.2.1 Arriving and departing peers (churn)
When a new peer wants to join a P2P network, typically it must know how to contact
some existing peer, who helps the new peer find its proper neighbors. Several methods
for assigning a zone to a new peer were analyzed in [54]. In single-point random-split,
31
a randomly chosen point in the keyspace becomes the new peer?s id. In single-point
center-split, the peer that controls a randomly chosen point gives exactly half of its
zone to the new peer. In multi-point center-split (random or semi-deterministic), a
fixed number of points are sampled; the one belonging to the largest zone becomes
the target of a center-split. As an example of the analyses, we have that under
single-point center-split the largest and smallest zones are ?(logn) times larger and
?
parenleftBig
2
?
2log2 n
parenrightBig
times smaller than average, with high probability.
The center-split methods are readily generalizable to proportional-split methods,
where the target zone is split, not in half, but in proportion to the capacities of the
new and existing peers3. The intent is to equalize utilizations rather than zone sizes.
In a multi-point method, the point belonging to the peer with the highest utilization
becomes the target.
In our simulations, we will use single-point proportional-split, which works as
follows: If the network has n?1 peers, then the nth peer chooses a random point
id ?K, which will lie in the zone of some existing peer i. Peer n then receives the
identifier id(n)?zone(i) such that znzi = cap(n)cap(i) . (Alternatively, id(n) could be chosen
based on the load distribution function gi(x) discussed in Section 2.3.2.2.2.)
When peer i leaves the P2P network, its adjacent peers pred(i) and succ(i)
should take control of its zone. If peer i announces its departure, the adjacent peers
can split zone(i) in proportion to their capacities, and take responsibility for the data
items previously managed by i. If peer i fails or simply drops out, some information
3More generally, it may be split in proportion to some function of the capacities of the new and
existing peers, depending on the nature of the relationship in Assumption 1.
32
may be temporarily lost. The Chord coping mechanism [49] is applicable to our
DHTs; an analysis of coping mechanisms is beyond the scope of this paper. Typically,
periodic re-publication of data items is required.
2.3.2.2 Existing peers
Proportional-split joining methods are insufficient to achieve balanced utilizations.
Part of this is due to the unpredictable nature of peer departures, but at least as
important is the fact that local DHT traffic load depends on the global structure of
the network. Fig. 2.3 shows the distribution of load across a particular peer?s zone
for an actual simulation, a reversed de Bruijn network in which the request rates ?
(Section 2.2.2.2) were all equal and destinations b ?K were chosen with uniform
probability.
The dependence of load on network structure means that it is not practical
(or perhaps even possible) to find an exact solution to the problem of utilization
balancing, even if the set of peers is held constant. This is in contrast to processor
networks or parallel databases, where an exact solution can be found as the result of a
global linear equation, and the challenge is to find locally-computable approximations
to this global solution.
Our implementation of PLB has similarities to the NbrAdjust operation of
[18] and the first-order diffusion schemes described in [14], but we also address the
non-uniformity depicted in Fig. 2.3, and we incorporate fail-safes to make sure that
zone sizes do not change too quickly. Pseudocode for the local implementation of
33
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10.00
0.05
0.10
0.15
0.20
10 regions
g i(x): Fraction of peer i?s traffic
in given region
Figure 2.3: Traffic load is not distributed uniformly within zones, even under
uniform selection of sources and destinations. This graph depicts the distri-
bution of load across a particular peer?s zone in a reversed de Bruijn network.
In the simulation, 19% of the traffic went through the second portion of the
zone, and only 6% through the fifth portion. Call this step function gi(x) for
peer i.
34
PLB is given in Fig. 2.4.
2.3.2.2.1 The Balance operation Lines 1 and 2 of Balance assign h to be
the peer with higher utilization, and lscript the peer with lower utilization. Line 3 tests
whether util(h) is sufficiently higher than util(lscript) for the GiveZone operation to be
performed in line 4.
PLB requires two tolerance values, tmin,tdiff?[0,1). Their meaning is as follows.
If util(lscript) = 0, we change id(i) if util(h)?util(lscript) ? tmin. On the other hand, if the
util(lscript) = 1, we change id(i) if util(h)?util(lscript) ? tmin + tdiff. For other values of
util(lscript), we interpolate linearly. Smaller values of tmin and tdiff cause the network to
take longer to settle down, but a more even distribution of utilizations is achieved.
2.3.2.2.2 The GiveZone operation Line 1 of GiveZone determines the frac-
tion of peer h?s load that should be transferred to peer lscript so that util(h)prime = util(lscript)prime.
Solving the equation load(lscript)+f?load(h)cap(lscript) = (1?f)?load(h)cap(h) for f yields f = 1?util(lscript)/util(h)1+cap(h)/cap(lscript). Be-
cause i communicates with both pred(i) and succ(i), zone(i) may be expanded or con-
tracted on both ends simultaneously, so we use the modified value loadfrac(h,lscript) = 12f.
Recall that the distribution of traffic load is nonuniform within zones. In line
2, peer h determines the fraction zonefrac(h,lscript) of its zone (adjacent to id(i)) that
corresponds to ??loadfrac(h,lscript) of its load. (The parameter ??(0,1] is tunable; we
use ? = 1.) In our simulations, we had each peer keep a histogram of the activity in
s = 10 equal sub-intervals of its zone, generating a step function gh like in Fig. 2.3.
If h = i, the integral is Gh,lscript(x) =integraltextx0 gh(t)dt. If h = pred(i), the integral is Gh,lscript(x) =
35
Balance (peer i)
1 Let h?argmax{util(i),util(pred(i))}
2 Let lscript?argmin{util(i),util(pred(i))}
3 IF util(h)?(1 +tdiff)util(lscript) +tmin THEN
4 GiveZone(h, lscript)
GiveZone (peer h, peer lscript)
1 Let loadfrac(h,lscript)? 12 ? 1?util(lscript)/util(h)1+cap(h)/cap(lscript)
2 Let zonefrac(h,lscript)?G?1h,lscript(?loadfrac(h,lscript))
3 Let ? ?min
braceleftBig
zonefrac(h,lscript), 12, zlscriptz
h
bracerightBig
4 Adjust id(i) by ??zh
Figure 2.4: Pseudocode for PLB (Section 2.3.2.2). Balance describes the
conditions under which PLB is performed. Here tmin,tdiff?[0,1). GiveZone
determines the new boundary id(i)prime between zone(i) and zone(pred(i)). In
simulations, we have all peers execute Balance simultaneously on clock ticks,
but in reality it can be executed at any time depending on each peer?s needs.
36
id(i?1) id(i) id(i+1)
Before:
? = fraction of zone(i)
id(i?1) id(i)? id(i+1)
After:
(a) Contracting zone(i)
id(i?1) id(i) id(i+1)
Before:
? = fraction of zone(i?1)
id(i?1) id(i)? id(i+1)
After:
(b) Expanding zone(i)
Figure 2.5: In Fig. 2.5(a), peer i contracts its zone by increasing id(i) to id(i)prime.
In Fig. 2.5(b), peer i expands its zone by decreasing id(i) to id(i)prime.
integraltext1
1?x gh(t)dt. Notice that G
?1
h,lscript is easy to calculate since gh is a step function.
Line 3 ensures that zprimeh = zh??zh ? 12zh and zprimelscript = zlscript + ?zh ?2zlscript, so the zone
sizes do not adjust too quickly. It is easy to repeat the Balance operation, but it is
difficult to recover from a suddenly over-utilized peer.
In line 4, id(i) is adjusted by the proper fraction of zh. It is increased if h = i,
and decreased if h = pred(i). See Fig. 2.5.
37
2.3.3 Data and rewiring costs
When peer i changes its id(i) based on PLB, the interval between the old id(i) and
the new id(i)prime changes ownership as discussed in the last section. The previous owner
is h (i or pred(i), the peer with higher utilization), while the new owner is the other
peer lscript. There is a data cost associated with moving information about data items
from h to lscript to maintain the proper definition of their zones. This cost is proportional
to the relative size of the interval, ?rh, that was transferred.
There is also a rewiring cost for adjusting neighbor connections maintain the
structure of the DHT. When id(i) is changed, links to/from peer h may be removed,
and links to/from peer lscript may be added. For each link involving h, we check whether
the link should be removed from h, and whether a corresponding link should be added
for lscript. (These are separate questions because both h and lscript may simultaneously link to
the same peer.) Any links not involving h will be unchanged. A special case arises if
h has a (virtual) link to itself; then we must check all four combinations of old and
new interval owners: h?h, lscript?h, h?lscript, and lscript?lscript.
We summarize these results in a theorem.
Theorem 2.4. Consider continuous-discrete DHTs as in Section 1.3. Suppose id(i)
is adjusted by ??zh in the GiveZone operation.
? Averaging over all distributions of data items, the expected data cost is
?zh
parenleftBigsummationdisplay
Dj
parenrightBig
= ?rh ?D. (2.32)
Here Dj is the number of data items stored by peer j, and ?D = 1nsummationtextnj=1 Dj is
the average number of stored (and thus of shared) data items per peer.
38
? The rewiring cost is at most 2(out-degree of h) + 2(in-degree of h) + 4.
39
2.4 Simulation experiments
We now use simulations to evaluate the performance of our proportionate load bal-
ancing implementation. These simulations are all of P2P networks based on various
types of de Bruijn DHTs.
One key feature of a network, which we will report on for each experiment, is its
maximum utilization. The maximum utilization is the greatest utilization experienced
by any peer in the network. A large maximum utilization (near 1) implies that some
peer is near capacity, and will start dropping queries if the request rates increase. A
small maximum utilization (near 0) implies that all peers are experiencing relatively
low load, and the request rate can be increased substantially without overloading the
network.
2.4.1 Setup
We perform iterations of PLB on static and dynamic networks of various sizes, ranging
from 64 to 8192 peers. During one iteration, all utilizations are computed, and then
each peer performs the Balance operation (Section 2.3.2.2) once.
The capacity of each peer is assumed to be constant during the simulation. Ca-
pacities are selected from a probability distribution that approximates the estimated
bottleneck upstream bandwidths of peers in the Gnutella network [46]. This distri-
bution is described in Table 2.1. Capacities selected from this distribution will be
highly variable, indicated by the standard deviation of F being larger than the mean.
The request rate ?i of each peer (Section 2.2.2.2) is also assumed to be constant
40
Table 2.1: Statistical properties of our capacity distribution.
Property Value
CDF F(x) = 12.3 log10 x25
Mean 940 Kbps
Standard deviation 1.5 Mbps
Median 350 Kbps
Range 25 Kbps?x < 5 Mbps
during the simulation. We test two reasonable values of ?: 1 and (cap(1),...,cap(n))
(Section 2.2.2.2). In the simulations presented here, the supply rate ?i of each peer
is taken to be proportional to its relative zone size ri.4
We estimate the utilization of each peer by tracing paths from random source
peers to random destination keys. The number of times a peer is traversed during
this process allows us to estimate its relative traffic load. An average of 100 paths per
source peer were traced; results were similar for different choices of the traced paths.
We tested various protocol parameters, and found no unpredictable results. The
parameters used herein are as follows. de Bruijn graphs: k = 8, D = 8. Balance
operation: tmin = 0.03, tdiff = 0.0?7.
2.4.2 Static networks
In our static simulations, no peers joined or left the system. We assigned capacities
to the n peers and fixed their order in the keyspace. We report on four stages of PLB.
In each we measured network features such as maximum utilization, mean utilization,
4Simulations with smooth but very nonuniform distributions of data items showed that PLB copes
well with different values of ?; space prohibits their presentation here. Caching can be employed to
level isolated hot spots, as described in Section 2.2.2.3.
41
and average query path length.
0. As a baseline, we tested the uniform network (all peers have zi = 1n).
1. We then rebuilt the network with the single-point proportional-split method of
Section 2.3.2.1.
2. We performed five iterations of PLB on this network (to evaluate realistic per-
formance).
3. We continued performing 500 iterations for some simulations (to evaluate lim-
iting behavior). The worst-case value of each feature between 450 and 500
iterations was used.
2.4.2.1 Uniform request rate
In these simulations, ??1. At each network size, 30 simulations were performed for
stages 1 and 2. Because of time considerations, only 6 simulations were continued to
stage 3.
Figs. 2.6 and 2.7 show how the maximum utilization drops under PLB. The
inverse of the maximum utilization determines how much traffic the network can
handle without any peer becoming over-utilized.
Relative to the corresponding uniform networks, forward de Bruijn DHTs saw
a greater decrease in maximum utilization in stages 1 and 2 than did reversed de
Bruijn DHTs. However, the starting values in stage 0 were about twice as great. The
limiting behavior of both cases was about the same, with the maximum utilization
42
128 256 512 1024 2048 40960
0.2
0.4
0.6
0.8
1
Ratio to max. util.
in forward uniform network
Number of peers (log scale)
Prop?l?split
PLB (5 iters)
Limit
Figure 2.6: Results of the static simulations in Section 2.4.2.1, with uniform
request rate ? = 1. The results for forward de Bruijn networks are depicted
here. Multiple simulations were performed. These plots show median values
connected by lines, with boxes delimiting the 25th and 75th percentiles, and
whiskers showing the full extent of the data. Figs. 2.6 and 2.7 show how
the maximum peer utilization decreases under PLB. All measurements are
relative to the maximum utilization in the corresponding uniform network
(peer capacities and ordering are the same as the original network, but all
zones are given equal size). The solid line shows networks built with single-
point proportional-split (Section 2.3.2.1). The dashed line shows the same
proportional-split networks after 5 iterations of Balance. The dotted line
shows the limiting behavior of PLB, after 450 iterations.
43
128 256 512 1024 2048 40960
0.2
0.4
0.6
0.8
1
Ratio to max. util.
in reverse uniform network
Number of peers (log scale)
Prop?l?split
PLB (5 iters)
Limit
Figure 2.7: Results of the static simulations in Section 2.4.2.1, for reversed de
Bruijn networks. This figure complements Figure 2.6, which shows the results
for forward de Bruijn networks.
44
Unif Prop  1   5  50 500 0
0.5
1
1.5
2
Number of iterations (log scale)
Max. util. with 
?=2.5 Kbps
Forward
Reverse
Figure 2.8: Sample result of the static simulations in Section 2.4.2.1. For a
fixed injection rate ?, we compare the maximum utilization for forward and
reversed de Bruijn DHTs as PLB is performed. The graph depicts the results
of one simulation of each, with 2048 peers. Local fluctuations are much higher
in the forward case.
being 5% to 10% of its original value.
As predicted in Section 2.2.2.2, query path lengths decreased (by 10%) for
reversed de Bruijn DHTs, and increased (by 10%) for forward de Bruijn DHTs. In
stage 0, the reversed query path lengths were about 70% longer than the forward
query path lengths.
45
2.4.2.1.1 Volatility Figure 2.8 compares the actual values of the maximum uti-
lization for forward and reversed de Bruijn DHTs. In the limit of a large number of
iterations, their best-case behavior is similar, but oscillations for the forward DHTs
yield a higher worst-case behavior.
The sudden spikes in utilization seen in Figure 2.8 most often occur when a
low-capacity peer becomes overwhelmed, usually for one of two reasons. (i) The peer
might expand its zone and acquire more traffic than expected, due to imbalances in the
keyspace. The imbalances are more profound in forward de Bruijn graphs, because of
their more primitive routing procedure. (ii) A different peer might change the size of
its zone, thus forcing it to connect to the peer in question. This is more problematic in
the forward case because a small peer is likely to have only one outgoing connection,
thus overwhelming its sole neighbor.
2.4.2.2 Varied request rate
In these simulations, ??(cap(1),...,cap(n)). At each network size, 30 simulations
were performed for stages 1 and 2. Of these, 6 were continued to stage 3. See
Figure 2.9.
Results for maximum utilization were very similar to the simultations with
uniform rerquest rate, as seen in Figure 2.9. Forward de Bruijn DHTs again saw a
greater decrease in maximum utilization in stages 1 and 2 than did reversed de Bruijn
DHTs. The starting values in stage 0 were again about twice as great. However, the
limiting behavior in forward DHTs was slightly better than reversed.
46
128 256 512 1024 2048 40960
0.2
0.4
0.6
0.8
1
Ratio to max. util.
in forward uniform network
Number of peers (log scale)
Prop?l?splitPLB (5 iters)
Limit
(a) Forward de Bruijn
128 256 512 1024 2048 40960
0.2
0.4
0.6
0.8
1
Ratio to max. util.
in reverse uniform network
Number of peers (log scale)
Prop?l?splitPLB (5 iters)
Limit
(b) Reversed de Bruijn
Figure 2.9: Results of the static simulations in Section 2.4.2.2, with capacity-
proportional request rate. See Figure 2.6 for an explanation.
47
Query path lengths again decreased for reversed de Bruijn DHTs. Forward de
Bruijn DHTs saw a very slight decrease. In stage 0, the reversed query path lengths
were about 65% longer than the forward query path lengths.
2.4.3 Dynamic networks
These simulations model networks that have reached a steady-state size, but with a
fluctuating (dynamic) population of peers. We start with the average network size
n = 512, and allow peers to join and leave the system according to the rules of
Section 2.3.2.1.
Fix a churn rate ?. Between each iteration of PLB, we independently allow
each peer to drop out of the network with probability ?, and we also insert 512? new
peers with capacities chosen from the distribution in Table 2.1. This process will tend
to keep the network size close to 512.5 How fast do peers come and go in reality?
A detailed study of churn rates ([50], Figure 6) reveals that in the real-world DHT
Kad, approximately 80% of the peers in the network at any given time have been
present for at least one hour, while approximately 95% have been present for at least
ten minutes. Therefore, only a small percentage of the peers will have changed if we
execute PLB every few minutes.
We executed 12 simulations of 500 iterations for forward and reversed networks
for values of ? = 2?15,2?14,...,2?3. The results for small ? were similar to Figure 2.8,
as expected. A representative example for larger ? appears in Figure 2.10.
5If the network size is ni after i iterations, then E (|ni+1?512||ni) =|(ni?ni?+512?)?512|=
(1??)|ni?512|<|ni?512|.
48
0 50 100 150 2000
0.2
0.4
0.6
0.8
1
Number of iterations
Util. relative to forwarduniform network
Maximum
99th %ile
Figure 2.10: Sample result of the dynamic simulations in Section 2.4.3 (for-
ward network pictured). The churn rate is ? = 2?5 ?3.1%. For clarity, only
200 iterations are displayed. Forward and reversed networks displayed statis-
tically similar reactions to churn rate. We see that the maximum utilization
is highly volatile, but the 99th percentile of utilizations is relatively stable,
indicating that the vast majority of peers in dynamic networks will benefit
from PLB.
49
For definiteness, we define a spike as an increase in one step by at least a factor
of two, and the spike recovery time as the number of steps to return to within 10%
of the pre-spike value. First consider the maximum peer utilization, as we have in
other experiments. As ? becomes large (we tested up to ? = 2?3 ? 13%), the
median distance between spikes and the median spike recovery time both approach
approximately 5 steps. Now consider the 99th percentile of the peer utilizations,
depicted by the bottom line in Figure 2.10. Ignoring a very few highly-affected peers
increases the median distance between spikes to approximately 75, without greatly
affecting the spike recovery time.
Note that we are assuming no correlation between session length and capacity.
It is plausible to think that in reality, peers with short session times also have low
capacities. Such behavior would reduce the fluctuations in maximum utilization, since
the removal of a peer with a small zone has less impact than the removal of one with
a large zone.
2.4.4 Hierarchical DHTs
Hierarchical P2P systems [19] divide their peers into two (or sometimes more) classes.
One class consists of superpeers, with high capacity and stability, and one consists
of regular, transient peers. We implemented a simple hierarchical system based on
reversed de Bruijn graphs, as follows.
Given a threshold capacity c, we label peer i a superpeer if cap(i) ? c, or a
regular peer otherwise. We form a de Bruijn DHT from the superpeers; then each of
50
128 256 512 1024 2048 40960
0.02
0.04
0.06
0.08
0.1
Ratio to max. util.
in forward uniform flat network
Number of peers (log scale)
Uniform hier.
PLB (5 iters) hier.
Figure 2.11: Results of the hierarchical simulations in Section 2.4.4. The
results for forward de Bruijn neigworks are depicted here; see Figure 2.12
for the results for reversed de Bruijn networks. Peers were grouped by the
threshold capacity cmean = 940 Kbps, and results are shown relative to the
corresponding flat uniform network (no hierarchy, all zones equal size). The
solid line depicts a hierarchical uniform graph, while the dashed line shows a
hierarchical graph to which PLB has been applied for 5 iterations.
51
128 256 512 1024 2048 40960
0.02
0.04
0.06
0.08
0.1
Ratio to max. util.
in reverse uniform flat network
Number of peers (log scale)
Uniform hier.
PLB (5 iters) hier.
Figure 2.12: Results of the hierarchical simulations in Section 2.4.4, for re-
versed de Bruijn networks. This figure complements Figure 2.11, which shows
the results for forward de Bruijn networks
.
52
the regular peers is assigned to a superpeer at random. All peers share data, but a
superpeer handles all of the routing of requests for its associated regular peers.
When building the network with the single-point proportional-split method
(Section 2.3.2.1), we split zones in proportion to the square roots of the capacities
of the new and existing superpeers. This is because the expected amount of traffic
through a superpeer depends both on its zone size, and on the number of regular
peers attached to it, which is proportional to its zone size. The Balance operation
was unchanged.
Figures 2.11 and 2.12 show results for uniform hierarchical networks and PLB-
iterated hierarchical networks, both compared to uniform non-hierarchical (flat) net-
works. We note two features of these plots. First, uniform hierarchical networks
have maximum utilizations that are about 3% (forward) to 6% (reversed) of the value
for a flat network, which is a large improvement. Second, executing PLB on these
hierarchical networks yields maximum utilizations that are as good as or better than
those for the uniform hierarchical networks.
53
2.5 Discussion
We have presented the mechanics of forward and reversed de Bruijn DHTs, under
the continuous-discrete framework. We analyzed the effect of relative zone size on
expected degree in each type of DHT. Furthermore, we investigated the effect of zone
size distribution on the average query path length. Theorems 2.1, 2.2, and 2.3 of
Section 2.2.2 describe the beneficial effect heterogeneity can have.
We have also presented a proportionate load balancing algorithm, which it-
eratively optimizes continuous-discrete DHTs by equalizing peer utilizations. After
analyzing the data and rewiring costs involved, we performed simulations of static,
dynamic, and hierarchical networks to verify the efficacy of PLB in reducing strain
on peers. We found that the maximum relative load on any peer dropped to approx-
imately 20% of the value for a uniformly-structured network after just five iterations
of PLB, and to less than 10% in the limit of 450-500 iterations. A more complete
practical algorithm could be a subject of future research.
Networks built with PLB offer a continuum of peer roles, from server-like to
client-like, so each peer can choose an appropriate role for itself depending on the
current makeup of the network. This differs from hierarchical schemes [19] which
treat some peers almost exclusively as servers and the others only as clients.
We found that forward de Bruijn DHTs are more volatile in their response to
PLB than reversed de Bruijn DHTs (Section 2.4.2.1.1). They also experienced larger
starting values of maximum utilization, by approximately a factor of two. Although
forward DHTs have shorter average query path length in uniformly-structured net-
54
works, under heterogeneity we have that the query path length may increase for
forward DHTs, while for reversed DHTs it decreases by ?2lnkr?1maxVar{ri}. This is
because in the forward case, a large zone size only benefits the owner, while in the re-
versed case, a large zone size benefits all the peers. We believe these features present
a strong case for the consideration of reversed de Bruijn DHTs.
55
Chapter 3
Identification of peer-to-peer hosts
3.1 Introduction
Universities and corporations have a particular interest in identifying peer-to-peer
traffic in their networks. Their concerns are twofold: bandwidth and security. With
regard to bandwidth, peers in peer-to-peer networks typically upload more than
clients in client-server systems [45], which puts strain on the networks they inhabit.
With regard to security, sharing pirated content can result in costly legal action, or
applications and content may contain viruses, spyware, or other malware [7].
Our focus on this chapter is on security concerns, so our goal is to identify the
offending/vulnerable hosts. In contrast, when the major concern is for bandwidth,
the goal is to identify individual traffic flows, or even packets. Higher accuracy can
be achieved when identifying hosts, because more information is available: we can
consider all the flows a host is involved in. Additionally, network monitoring is work-
intensive. We are able to achieve acceptable results with NetFlow-style [8] data,
while effective flow-identification schemes tend to require packet-level information
[3, 55, 35].
We will use behavioral commonalities to identify peer-to-peer applications. Our
data will be IP traffic passively observed at set monitoring locations. Examples of
observable behaviors are average flow size, or number of IP addresses communicated
56
with in a certain period of time. Message passing, measured in ?triples,? will be a
particularly important behavior. We will intentionally ignore other behaviors, such as
port information [34], or the specific timing of requests, because they are application-
specific. We will also attempt to make the identification as close to real-time as
possible, rather than performing extensive post-processing analysis of network struc-
ture.
3.1.1 Related work
Most of the literature on identifying peer-to-peer traffic has focused on labeling flows
(or IP pairs) rather than individual hosts. When applicable, payload examination can
be a very effective method of classifying particular P2P applications [47, 1]. However,
encryption and data volume are increasingly rendering payload methods inapplicable.
It is also possible to identify flows based only on features extracted from meta-
data. These features are typically processed by machine learning classification tech-
niques. Some studies have attempted to identify specific applications, such as Kazaa
or eDonkey. Two such studies achieved 80-90% accuracy, one [3] using only the sizes
of its first several data packets in the flow, and another [55] using a wider variety of
features, including packet interarrival times.
Other studies, which are more in line with our goals, have attempted to identify
the categories of traffic that a flow belongs to, such as P2P or email. One such
study [35] used features including packet interarrival times and TCP ports to achieve
up to 95% accuracy for certain application categories, though only up to 55% for
57
P2P. Another [26] used features including port counts to identify 99% of P2P flows
with a 10% false positive rate, but used a fixed algorithm rather than adaptable
machine learning techniques. Though these studies did not rely on prespecified port
information, the use of port numbers at all is increasingly unreliable, because it is
possible for users to employ random port numbers.
A smaller number of studies have discussed identification of individual hosts,
rather than flows. BLINC[27] used featuresincludingportcountstoclassifyhostsinto
application categories, then used that information to classify the corresponding flows,
achieving 95% accuracy on 80-90% of the flows. Some others focused on more narrow
subsets of P2P applications: one [48] primarily investigated eDonkey, while another
[52] discussed the identification of DHTs, without providing an implemenation, or
suggesting the ?triple? heuristic we discuss in Section 3.2.2. All these studies required
post-processing on the graph of host connections.
Other work of interest includes the identification of compromised ?stepping
stone? computers [56] and the identification of relay nodes in Skype [51], because
such hosts are qualitatively similar to the hosts in the middle of the ?triples? we
define in Section 3.2.2. The identification of email spamming machines by graph
theory techniques [11] may also be of interest.
One might think of a ?stepping stone? [56] as a host in the middle of a triple
(see Section 3.2.2), but stepping stone analysis requires the flows to be very similar
on the packet level. In the interest of general applicability, we only concern ourselves
with the existence of the flows, no with any of their measurable properties (other
than perhaps their overall size).
58
3.1.2 Trace data
We use publicly-available traces from the NLANR Passive Measurement and Anal-
ysis Project [38]. The PMA project provides packet header traces from a variety of
monitoring locations. Most traces have a duration of 90 seconds, but special traces
with durations of hours or days are also available.
Our main focus was on the Leipzig-I data set [39], a trace capturing all traffic
of the University of Leipzig between 8pm Thursday, November 21 and 2pm Tuesday,
November 26, 2002. This data was captured recently enough that peer-to-peer traffic
is common, but sufficiently long ago that many peers were still using fixed TCP and
UDP ports [34]. In addition to these advantages, the long time period of the trace
allows us to study the behavior of a host in more detail.
We can also compare to 90-second traces from the University of Memphis [40],
captured as recently as March 2006.
Because they each monitor the gateway to a university, both of these traces have
a definite ?inside? and ?outside.? For Leipzig-I, the inbound and outbound packets
are stored in separate files (whose labels were inadvertently switched [33]). We place
more focus on classifying the interior hosts, since the trace capture more information
about their communications. The interior hosts may also be of more interest to a
network administrator.
We may look at what happens when we use classifications of the exterior hosts
to adjust our judgements of the interior hosts.
59
3.1.3 Overview
The remainder of this chapter is structured as follows. In Section 3.2 we discuss
the measurable features of our data set, and derive a model for message passing. In
Section 3.3 we discuss the use of port numbers, provide an overview of supervised
learning techniques, and list the results of our classification experiments.
60
3.2 Feature set
The trace data we use provides packet-level records, but we convert them to NetFlow-
style data [8] befpre performing our analyses. In particular, we use the following
definition.
Definition 3.1. A flow is a sequence of packets sent back and forth between a pair
of hosts, identified by the 5-tuple
f = (S,s; D,d; P), (3.1)
where (S,s) are the source?s IP address and port number, (D,d) are the destination?s
IP address and port number, and P is the protocol number. The ?source? is the host
that sends the first observed packet in the flow. If there is a gap of more than 60
seconds between consecutive packets, we consider there to be two distinct flows.
In this work, we only consider flows corresponding to the TCP and UDP pro-
tocols. Most other protocols could easily be included, but for the triples discussed in
Section 3.2.2, it is important to ignore ICMP flows.
Using Definition 3.1, we divide packet traces into flows, keeping the following
information about each flow:
? The 5-tuple (S,s; D,d; P), with s = d = 0 for protocols without port numbers
? The timestamp of the first packet in the flow
? The timestamp of the last packet in the flow
? The number of packets sent from S to D
61
? The number of packets sent from D to S
? The number of bytes (header and payload) sent from S to D
? The number of bytes (header and payload) sent from D to S
? A flag identifying which IP address (S or D) is internal to the university
3.2.1 Elementary features
Whenever a new host X is observed, we create a database entry for it, noting the
timestamp of the first observation and whether the host is interior or exterior to
the university (if known). As X participates in more flows, we update the following
values: the most recent timestamp; a list of the distict IP addresses X interacts
with; the total number of flows initiated and accepted; the total number of packets
initiated and accepted; the total number of payload bytes initiated and accepted; the
total duration of individual flows; and counts of each protocol type.
From these values, we calculate nine acceptable features:
? The average number of new neighbors (IP addresses X interacts with) per sec-
ond
? The average number of flows per neighbor
? The average number of packets per flow
? The average number of payload bytes per packet
? The average flow duration
62
? The fraction of flows that were initiated by X
? The fraction of packets that were initiated by X
? The fraction of payload bytes that were initiated by X
? The fraction of flows that used the TCP protocol
These features can be calculated at a specified clock time, or after seeing a specified
amount of activity from host X.
3.2.2 Triples
We now present a feature that measures flow interactions.
3.2.2.1 Definition
For a decentralized peer-to-peer network to function, the peers must participate in
message-passing. Whether in older systems such as Gnutella or newer systems based
on distributed hash tables [32], the lack of a central authority implies that when a
peer wants a file, he must make a lookup query of one or more of his neighbors, who
must in turn make queries of one or more of their neighbors, until the file is located.
Therefore, peers in a decentralized peer-to-peer network will both initiate and
accept flows with other peers, and in quick succession if they are not willing to intro-
duce significant delay into the search process. This inspires the following definition,
where Time(f) is the timestamp of the first packet in flow f.
63
Definition 3.2. A triple for a host X is a pair of flows f1 = (A,a;X,x1;p1), f2 =
(X,x2;B,b;p2) such that Anegationslash= B and 0 < Time(f2)?Time(f1)??. The triple is
denoted A?X?B. The parameter ? is called the window parameter.
We use a window parameter of ? = 5 seconds.
Note that either flow f1 or f2 may be involved in more than one triple. In fact,
in the case of Gnutella, we would expect f1 to be in multiple triples, since Gnutella
lookup queries are passed to all neighbors.
3.2.2.2 Counting triples
Because we only observe traffic that takes place between a host inside the university
and a host outside the university, we will be artificially unlikely to see triples for
exterior hosts. We therefore focus on interior hosts. We will find that P2P hosts tend
to have more triples, even though we cannot see the peer activity that takes place
entirely within the university network. In the Leipzig-I dataset, we can easily limit
our analysis to interior hosts.
Consider observing a interior host X for a time period 0 ? t ? T. We keep
track of the following statistics:
? N1 = the number of flows X accepts
? N2 = the number of flows X initiates
? S1 = the number of accepted flows that are involved in a triple
? S2 = the number of initiated flows that are involved in a triple
64
? H = the number of distinct hosts X communicates with (may be omitted ?
see below)
The flows counted by N1 have the potential to be the first flow in a triple,
while those counted by N2 have the potential to be the second. We will model each
flow?s probability of being in a triple by assuming that the start times of the flows
are uniformly distributed in the interval [0,T], and then compare this expectation to
the observations Si.
We choose the uniform distribution for simplicity, and will find it to be effective.
We tried the Poisson distribution with similar results, but it has been known for years
[43] that Poisson models do not capture the burstiness in data networks. Non-Poisson
arrival models [41] could also be considered.
Let f1 be one of the N1 inbound flows, and let t1 = Time(f1). We define
p1 = P[f1 is in a triple] (3.2)
= P[a flow f2 to a different host occurs with Time(f2)?(t1,t1 +?]] (3.3)
= 1?
parenleftBig
1? ?T
parenrightBigH?1
H N2 (3.4)
where H?1H N2 is the average number of flows that X initiates to hosts, other than
the host involved in f1. Similarly, given an outbound flow f2, we can define the
probability
p2 = 1?
parenleftBig
1? ?T
parenrightBigH?1
H N1 (3.5)
that f2 is involved in a triple.
65
If H is deemed to be to expensive to keep track of, we can use the approximations
p1?1?
parenleftBig
1? ?T
parenrightBigN2
, p2?1?
parenleftBig
1? ?T
parenrightBigN1
(3.6)
because H?1H ?1 for large H.
For i = 1,2, we can now model the number of flows that are involved in a
triple using a Binomial(Ni,pi) distribution, if we assume each flow has an indepen-
dent, identically distributed probability of being involved in a triple. Recall that the
binomial distribution, which has probability mass function
Bi(n) =
parenleftbiggN
i
n
parenrightbigg
pni (1?pi)Ni?n, (3.7)
has mean ?i = Nipi and variance ?2i = Nipi(1?pi).
The Binomial(Ni,pi) distribution can be approximated by a Normal(?i,?2i ) dis-
tribution. Therefore, to compare Si to the expected ?i, we may use the z-score
zi = Si??i?
i
(3.8)
The z-score represents the difference between Si and the model mean, in units of the
model standard deviation. The z-scores z1 and z2 will be our metrics for measuring
triples.
66
3.3 Classification results
This section describes our testing methodology and results.
3.3.1 Determining the ?true? classes
Although TCP/UDP port numbers are not generally an effective method for identi-
fying peer-to-peer traffic [34], we can use them as a baseline measurement of truth
in the Leipzig-I data set because of its age. Table 3.1 summarizes how much P2P
traffic can be identified by port number; we see that port numbers cannot be used as
a reliable means of identification in the Memphis data set.
Table 3.1: The fraction of TCP/UDP traffic, by number of flows and by
amount of payload, that has known P2P port numbers.
Leipzig-Ia Memphisb
Application Flows Bytes Flows Bytes
eDonkey 2000 23.54% 12.38% 0.28% 0.01%
Soribada 1.52% 0.04% ? ?
WinMX 1.19% 3.58% ? ?
DirectConnect 1.05% 1.15% ? ?
KaZaA 1.04% 10.59% 0.04% 0.01%
Gnutella 0.48% 1.27% 0.75% 0.07%
Manolito 0.21% 0.01% 0.73% 0.01%
SoulSeek 0.10% 0.65% ? ?
Napster 0.04% 0.11% 0.08% 0.00%
iMesh 0.01% 0.01% ? ?
BitTorrent 0.00% 0.00% 0.10% 0.00%
Client/Server 48.51% 35.21% 50.94% 54.34%
Unknown 22.29% 34.99% 47.08% 45.55%
aFrom 20021121-200000.
bFrom MEM-1143763417-1.
Given an interior host X, we can assign one of four labels to each of its flows:
67
1. Peer-to-Peer: At least one port is known to be associated with a peer-to-peer
application (KaZaA, eDonkey 2000, etc.)
2. Server: At least one port associates the host with the server end of a specific
non-P2P application (HTTP, games, instant messaging, trojans, etc.).
3. Client: At least one port associates the host with the client end of a specific
non-P2P application.
4. Unknown: Neither port has a known association.
We use the port list in Appendix A.1, derived from a variety of online sources.
For example, if X uses port 80 (HTTP), we label the flow Server; if the other host
uses port 80, we label the flow Client.
If at least 75% of the flows that host X participates in are Unknown, then
we also assign X the label Unknown. Otherwise, we assign X one of the labels
Peer-to-Peer, Server, or Client by a simple plurality vote of the relevant flows.
Counts are shown in Table 3.2. Some time-of-day trends are apparent.
We conjecture that many of the Unknown flows are peer-to-peer, because
traditional client/server applications tend to use well-known ports. We also conjecture
that some flows taking place over port 80 are also P2P [26], since hosts may try to
hide their traffic to bypass firewalls or other security measures.
68
Table 3.2: The number of active hosts of each type, broken down by date and
time. An ?active? host is one that both sent and received one packet in the six-
hour file window. Not all hosts were used in the experiments (Section 3.3.3),
because the experiments employed a more limited time (or traffic volume)
window.
Time Date P2P Client Server Unk. Total
8pm Thu 189 2129 312 1120 3750
Fri 144 1492 316 513 2465
Sat 133 1205 312 301 1951
Sun 190 1880 363 344 2777
Mon 226 2364 324 454 3368
2am Fri 102 788 169 246 1305
Sat 100 415 256 309 1080
Sun 104 646 236 258 1244
Mon 93 768 780 98 1739
Tue 122 872 203 398 1595
8am Fri 167 3462 388 463 4480
Sat 123 1482 214 419 2238
Sun 131 1254 857 468 2710
Mon 172 3929 561 453 5115
Tue 171 3917 520 572 5180
2pm Fri 184 3103 388 432 4107
Sat 139 1683 400 352 2574
Sun 169 1866 439 220 2694
Mon 227 4326 437 535 5525
3.3.2 Supervised learning techniques
We will compare the results of a variety of supervised learning techniques. This
section provides an overview of such techniques. Since we are only using the tools,
not developing new techniques, we do not provide full details; see, e.g., [24] for more
information.
69
3.3.2.1 Goals and definitions
The goal of supervised learning is to construct a function, based on known examples,
that relates observable features to an outcome of interest. It can be used to answer
questions such as: What is the probability of a customer defaulting on their mortgage?
Will a patient?s cancer recur? Is a computer access malicious?
Each event (item in the sample space) has:
? a feature vector ??x = (x1,x2,...,xp)?Rp of observable variables1
? an outcome variable y?Y 2
There is a body of known training data (??x1,y1),...,(??xN,yN). Supervised learn-
ing techniques attempt to build a function f : Rp ? Y that is close to having
f(??xj) = yj for all 1?j?N, without overfitting. Building f may be time-consuming,
but once the setup process is complete, predicting the outcome y = f(??x ) for a new
observation??x is fast.
3.3.2.2 Examples
We begin with a very simple example. Assume there are only two possible outcomes,
y = 0 or y = 1. The training data divides into two classes, each with Ny members,
1It is possible to have categorical variables xi?Xi, where Xi is notR, nor even a metric space; for
example, Xi ={female,male}. Since none of our features are categorical, we use Xi = R throughout
to simplify the discussion.
2If |Y| is finite, building f is known as a ?classification problem?; if Y = R, it is known as a
?regression problem.? We focus on classification problems here.
70
and each with mean
???y = 1
Ny
Nysummationdisplay
j=1
??xj(y), (3.9)
and covariance matrix
?y = 1N
y?1
Nysummationdisplay
j=1
(??xj(y)????y)T(??xj(y)????y). (3.10)
If the true classes are normally distributed with equal covariances, then Fisher?s linear
discrminant [15] provides the Bayes optimal solution. This discriminant divides the
feature space Rp with a hyperplane perpendicular to
??w = ((N0?1)?0 + (N1?1)?1)?1(???0????1). (3.11)
That is, either
fc(??x ) =
??
???
????
0 if??w ???x ?c
1 if??w ???x < c,
or fc(??x ) =
??
???
????
1 if??w ???x ?c
0 if??w ???x < c,
(3.12)
for some constant c.
We now briefly describe some of the most important supervised learning tech-
niques. In a given problem, there may be more than two possible outcomes; these
techniques can be generalized to multi-class versions with varying amounts of diffi-
culty.
? Linear discriminant analysis [15]. The feature space is divided by a hyperplane.
The model assumes the classes have equal covariances.
? Quadratic discriminant analysis [13]. The feature space is divided by a quadric
surface. The model assumes the classes are normally distributed with unequal
covariances.
71
? Naive Bayes classification [12]. All features are assumed to be independent.
? k-nearest neighbor algorithm [13]. A new observation ??x is assigned the most
common y value of its k nearest neighbors xj1,...,xjk in the training set.
? Neural networks [30]. The function f is a compilaton of other functions, which
fit a given model and are tuned by the training data.
? Classification trees [6]. The feature space is hierarchically divided along one
variable at a time. At each point in the hierarchy, the split is chosen to reduce
the node impurity i = n0n1(n0+n1)2.
? Random forests [4]. A large number of classification trees are produced, each
using a small random subset of the features and a randomly chosen (with re-
placement) subset of the training data.
We use Breiman?s implementation for random forests [5], and LNKnet?s imple-
mentation for all other techniques [23]. In LNKnet, we performed a simple mean-0,
variance-1 normalization of the data; such normalization is unnecessary in random
forests.
3.3.3 Results
Since the makeup of a university?s active computer population varies over the course
of a day, we grouped the input files by local start time: 8pm, 2am, 8am, and 2pm.
For n = 4,16,64,256,1024, we observed the first n flows for each IP address. Again
for n = 4,16,64,256,1024, we observed the first n seconds of activity for each IP
72
address. The features described in Section 3.2 were computed, then run through var-
ious supervised learning algorithms. To account for imbalances in class distribution,
Peer-to-Peer hosts were given a weight five times as great as Client and Server
hosts in the training process.
We estimated the success rate (percent of Peer-to-Peer hosts classified cor-
rectly) and false positive rate (percent of non-Peer-to-Peer (Client and Server)
hosts classified as Peer-to-Peer) for each algorithm. With random forests, these
come from the out of bag (OOB) error estimate. With the other algorithms, these
come from 10-fold cross-validation (CV10).
A comparison of classification techniques is given in Tables 3.3 and 3.4. We
see that the random forests technique generally has the highest success rates. It also
gives larger false positive rates, but as discussed above, we believe many of these
?false positives? are true Peer-to-Peer hosts disguising their traffic as Client,
Server, or Unknown traffic.
The dependence on n (the number of flows or seconds) is depicted in Figure 3.1,
for random forests. We see that increasing the number of flows in the sample increases
the success rate (and the false positive rate), while increasing the time scale of the
sample has little effect.
3.3.4 Testing against the Memphis data set
We compare Memphis data collected just after midnight on Saturday, March 31,
2006 with a Leipzig trace collected at 2am on Saturday, November 23, 2002. Because
73
4 16 64 256 10240
20
40
60
80
100 RandomForest at 02:00
Number of flows
Percent
(a) Based on n flows, at 2am
4 16 64 256 10240
20
40
60
80
100 RandomForest at 14:00
Number of flows
Percent
(b) Based on n flows, at 2pm
4 16 64 256 10240
20
40
60
80
100 RandomForest at 02:00
Number of seconds
Percent
(c) Based on n seconds of data, at 2am
4 16 64 256 10240
20
40
60
80
100 RandomForest at 14:00
Number of seconds
Percent
(d) Based on n seconds of data, at 2pm
Figure 3.1: Sample of the results for the random forest classifier. Each line
represents a different date. The upper (black) lines are success rates. The
lower (blue) lines are false positive rates. The solid lines incorporate all fea-
tures. The dashed lines incorporate only z1, z2, and the fraction of traffic
initiated by the given host.
74
Table 3.3: The range of success and false positive rates, across different days,
for a variety of classifiers, based on the first 16 flows from each host. The
first line under each classifier is for the full feature set. The second line is for
the limited feature set consisting of z1, z2, and the inbound/outbound traffic
ratios.
8pm 2am 8am 2pm
Technique S% FP% S% FP% S% FP% S% FP%
Random forest 62-75 9-12 77-81 11-20 48-65 4-12 56-65 5-850-67 13-15 71-79 14-29 41-55 4-13 43-57 7-11
Neural 47-64 6-12 37-82 2-40 22-45 1-9 35-49 3-7
network 37-54 16-19 44-78 18-55 15-37 3-17 16-33 4-11
Classification 45-56 5-7 58-66 5-12 27-43 2-7 32-46 4-5
tree 30-37 7-8 47-56 8-18 16-34 3-8 26-28 4-8
Linear 42-52 8-9 37-69 4-23 8-34 0-5 24-43 2-7
discriminant 33-42 10-12 30-59 7-33 1-27 0-6 13-28 4-7
Nearest 35-40 5-7 45-64 4-13 22-34 2-5 26-41 3-5
neighbor 19-31 7-9 30-53 7-18 13-20 2-7 15-21 4-7
Naive Bayes 27-41 4-4 24-57 4-8 16-29 1-3 23-35 2-42-12 1-3 5-39 2-6 0-13 0-2 2-11 0-2
port number are not a reliable means of identification in the Memphis data set (see
Section 3.3.1), we use Leipzig as the training data.
Specifically, we build a random forest on the Leipzig data just as in Section 3.3.3,
then pass the Memphis data through the forest. We base the random forest on the
first 64 seconds of data from each host. Less than 2% of the Memphis hosts had 16
or more flows, so we skip that comparative analysis.
Using the full feature set, 3% of the Memphis hosts were classified as Peer-
to-Peer, 53% as Client, and 43% as Server.
Using the limited feature set consisting of z1, z2, and the inbound/outbound
traffic ratios, which we consider to be less application-specific, 15% of the Memphis
75
Table 3.4: The range of success and false positive rates, across different days,
for a variety of classifiers, based on the first 64 seconds of data from each host.
The first line under each classifier is for the full feature set. The second line
is for the limited feature set consisting of z1, z2, and the inbound/outbound
traffic ratios.
8pm 2am 8am 2pm
Technique S% FP% S% FP% S% FP% S% FP%
Random forest 67-78 11-13 81-89 14-25 64-79 6-16 69-72 8-1144-65 11-13 66-84 14-40 51-75 7-24 49-62 8-12
Neural 51-59 3-10 73-83 12-56 49-68 2-27 53-60 3-8
network 55-64 25-31 62-93 16-60 57-70 10-27 48-63 16-27
Classification 38-51 6-9 56-71 7-16 41-59 2-9 45-50 5-7
tree 26-31 6-9 43-63 7-36 32-56 3-18 26-34 5-10
Linear 35-50 7-15 50-83 15-42 36-63 4-22 34-43 6-9
discriminant 34-47 17-28 47-88 17-65 35-49 9-23 20-48 11-23
Nearest 29-53 5-8 51-68 7-16 38-54 2-10 30-45 4-7
neighbor 23-30 10-12 39-59 17-24 27-37 6-13 25-33 7-13
Naive Bayes 18-39 3-4 37-53 4-9 36-56 3-6 33-38 3-412-19 1-2 28-49 4-7 22-36 2-4 14-21 1-3
hosts were classified as Peer-to-Peer, 71% as Client, and 14% as Server.
We consider these results promising. The two data sets were collected more
than three years apart, and we restrict attention to only interior hosts in the Leipzig
data set, while this is not done in the Memphis data set. Nonetheless, a classifier
built from the Leipzig hosts is sufficiently sensitive to distinguish different behaviors
in the Memphis hosts, rather than classifying all Memphis hosts as, e.g., Clients.
76
3.4 Discussion
We have found that with minimal tweaking of the parameters, random forests can
identify 80% or more of P2P hosts. One study [35] added a variety of adjustments to
naive Bayes classifiers to improve performance from 65% to 95% on certain application
categories; if they had started with a more powerful classifier such as random forests,
their results might have been even greater.
Our success rates are comparable to those of related studies, given the limita-
tions on our data. We must estimate true classes from port numbers, since we lack
packet payloads. We also miss all peer activity taking place within the university; we
see only communcations between interior and exterior hosts.
77
Chapter 4
Discrete analysis of crystal steps
4.1 Introduction
In Section 1.4, we discussed the importance of understanding crystal surface evolution,
particularly the motion of steps. In this work, we develop an analytical description
of step motion under a discrete model of the underlying physics.
Under continuum models, the crystal surface height is treated as a continuous
function of horizontal position. Because physical steps have discrete heights, discrete
models offer a more natural description of step behavior. Discrete models are still
approximations, however, because the horizontal step positions are typically treated
as continuous variables. In our discrete model analysis, we find an extra time de-
pendence term (t?1/2) in addition to the exponential dependence that emerges in
continuum models.
We discuss the effect of the model?s physical parameters on the step motion,
and therefore the step bunching. Consider an equilibrium solution corresponding
to equally spaced steps. When terrace width deviations tend to decay towards this
solution, the behavior will remain stable. When the terrace widths exhibit growth
away from equilibrium instead, step bunching can occur.
78
4.1.1 Related work
A discrete model for crystal steps was first formulated in the early 1950?s [57], after
Burton, Cabrera, and Frank noted the growth of crystals in solutions that were much
less supersaturated than demanded by contemporary models. They concluded that
the crystal surface holding the solution must not be smooth at the nanoscale. Such
discrete models are now called ?BCF models.?
A variety of extensions to the original BCF model have been offered. Finite
attachment-detachment rates at step edges play a large role in step behavior [66].
Step-step interactions based on the surface free energy were considered early on [63]; a
variety of short- and long-range interactions have been considered since [67]. Modeling
the crystal as a stack of concentric circular discs allows the introduction of curvature
and step line tension [76]. Analyses of more general shapes have been limited to
single-layer islands [58].
An electric field can also bias the terrace diffusion [80] by applying a direct
current to the adatoms, which have a net charge due to their interactions with the
crystal surface. The inclusion of an electric field in a BCF model [79, 77] is particularly
important because application of a direct current is the most common method of
inducing step bunching experimentally.
Step bunching [68] can appear in systems limited by the step edge attachment-
detachment rates [66]. Experiments show that, under the application of a direct
current, behaviorofthebunchinginstabilitydependsinacomplexwayonthesystem?s
temperature and on the direction of the applied current [70, 82]. Step bunching can
79
also be induced by deposition from the surrounding vapor, as shown experimentally
[65] and numerically [72]. Finally, step curvature itself can also induce bunching in
the model [61, 62].
In this work, we seek to understand step bunching of straight steps via ana-
lytical examination of the natural discrete equations, rather than by a continuum
approximation [73] or numerically [72, 71, 78, 79]. We focus on the importance of the
applied electric field.
Partial differential equations have been used to study step behavior, for example
scaling laws for bunch widths. These PDEs can be derived directly from continuum
versions of surface free energy and chemical potential [75, 76], or they can be derived
as the continuum limit of discrete step equations [73]. The PDEs are highly nonlinear
andtendtobe offourthorder(e.g., equation (5)of[73]). Most analyses haveemployed
linearized versions [74] for tractability. The linearization is performed about the
solution corresponding to equally spaced steps (e.g., equation (6) of [62]). Growth of
step bunches due to electromigration has been studied in a nonlinear context (e.g.,
equation (31) of [77]).
4.1.2 Overview
The remainder of this chapter is structured as follows. In Section 4.2, we construct a
discrete model for the physics of step motion. In Section 4.3, we derive coupled equa-
tions for terrace widths based on this model. In Section 4.4, we find the linearization
of this step motion equation. Finally, in Section 4.5, we find approximate solutions
80
to this linearized equation. A table of relevant parameters and variables appears in
Appendix B.1.
81
4.2 Physical models of step motion
In this section, we derive a discrete model for step motion based on the underlying
physics. We will analyze the behavior of a set of coupled linear ODEs, providing a
contrast to the analyses of linear PDEs common in the literature.
4.2.1 Assumptions for the discrete model
We make the following assumptions about the geometry of our model:
(A3) The steps are straight (Figure 1.2(b))
(A4) The step sequence is monotone, downwards to the right
(A5) The step height a is constant
These assumptions permit a one-dimensional model of the crystal surface, with
the position of the jth step edge denoted xj(t). The jth terrace has width xj+1(t)?
xj(t), or normalized width uj(t) = xj+1(t)?xj(t)L , where L is the average terrace width.
We also make the following assumptions about the kinetics.
(A6) Surface diffusion is faster than attachment-detachment (ADL kinetics)
(A7) Step-step interactions have energy U ? 1/(terrace width)2 (e.g., entropic
or elastic interactions)
(A8) There are no thermal fluctuations (low temperature)
Step motion proceeds from the motion of adsorbed atoms (adatoms) on the
crystal surface. See Figure 4.1. Let cj(x,t) be the local concentration of adatoms on
82
Figure 4.1: The crystal substrate is composed of bonded atoms. Adsorbed
atoms (adatoms) interact with the surface, but move across it. If an adatom
attaches at a step edge (xn), the step edge advances by one lattice constant.
Similarly, an adatom can detach from a step edge, causing the edge to retreat.
the jth terrace, xj < x < xj+1. Also let Jj(x,t) be the adatom current on the jth
terrace.
4.2.2 Discrete terrace equations
The model we derive here is very similar to the straight-step model in [62].
The step velocity law comes from mass conservation of adatoms near the step
edge:
dxj
dt =
?
a
bracketleftbigg
?Jj(x+j ) +Jj?1(x?j )
bracketrightbigg
, (4.1)
where ? is the atomic volume and a is the step height.
The adatom current obeys Fick?s first law of diffusion and is also affected by
electric drift with speed v0:
Jj(x) =?D?cj?x +v0cj. (4.2)
The adatom density cj satisfies Fick?s second law and is also affected by the
83
desorption time ? and deposition rate R:
?cj
?t =?
?Jj
?x ?
1
?cj +R (4.3a)
= D?
2cj
?x2 ?v0
?cj
?x ?
1
?cj +R. (4.3b)
We will assume there is no deposition: R = 0.
For tractability, we make the quasi-steady approximation [57]
?cj
?t ?0. (4.4)
This approximation is not rigorous, but it agrees with physical observations. The
justification is that step velocities (which depend on attachment-detachment) are
much slower than terrace adatom diffusion, so the concentration cj relaxes to steady-
state between step adjustments.
4.2.3 Discrete step boundary conditions
We assume linear kinetics at both the left and right edges of the jth terrace, that is,
Jj(x+j ) =?k+parenleftbigcj(x+j )?Ceqj parenrightbig, (4.5a)
Jj(x?j+1) = k?parenleftbigcj(x?j+1)?Ceqj+1parenrightbig, (4.5b)
where k+ and k? are the attachment-detachment rate coefficients. If k+,k? are un-
equal, we say there is an ?Ehrlich-Schwoebel barrier? at the step edge [78].
The equilibrium adatom density is given by the Arrhenius equation,
Ceqj = c0e?j/kBT. (4.6)
Here ?j is the step chemical potential, which is the change in surface free energy when
an adatom attaches at the jth step edge. Positive values of ?j indicate a propensity
84
for a step edge to emit adatoms, while negative values indicate a propensity to accept
adatoms.
Because we are ignoring step curvature (Assumption A3), the chemical potential
depends only on step-step interactions. Assuming nearest-neighbor effects, we have
?j ? ddx
j
[U(xj,xj+1) +U(xj?1,xj)], (4.7)
where, from Assumption A7,
U(xj,xj+1)? 1(x
j+1?xj)2
. (4.8)
Then, subsuming the constants of proportionality into g, we have
?j
kBT = g
bracketleftBiggparenleftbigg
L
xj+1?xj
parenrightbigg3
?
parenleftbigg L
xj?xj?1
parenrightbigg3bracketrightBigg
. (4.9)
g is a dimensionless constant that describes the strength of the nearest-neighbor step-
step interactions.
85
4.3 Step motion equation from the model
Here we find an equation for dujdt that depends explicitly only on the terrace widths.
We will see that when steps interact, dujdt depends on the terraces two neighbors away,
but when step-step interactions are eliminated, dujdt depends only on the terraces one
neighbor away.
4.3.1 Adatom density and adatom current
Under the quasi-steady approximation, the PDE in equation (4.3) becomes an ODE:
D?
2cj
?x2 ?v0
?cj
?x ?
1
?cj = 0, (4.10)
which has solutions
cj(x) = B+j eR+(x?xj)/L +B?j eR?(x?xj)/L (4.11)
where B?j will be determined by boundary conditions, and
R? = Lv02D ?Lv02D
radicalbig
1 + 4?2, (4.12)
? =
?D?
v0? (4.13)
are dimensionless constants.
Substituting equation (4.11) into equation (4.2) gives
Jj(x) =?q+B+j eR+(x?xj)/L?q?B?j eR?(x?xj)/L, (4.14)
where
q? = DLR??v0 =?v02 ?v02
radicalbig
1 + 4?2. (4.15)
86
We will find it convenient to set
q+? = q? +k?, q?? = q??k+. (4.16)
Substituting into equation (4.5) from equations (4.14) and (4.11) gives
B+j q?+ +B?j q?? =?k+Ceqj , (4.17a)
B+j q++eR+uj +B?j q+?eR?uj = k?Ceqj+1, (4.17b)
where
uj = xj+1?xjL (4.18)
is the normalized width of step j. Now we can solve for B?j , finding
B?j =?d(uj)bracketleftbigk?q??Ceqj+1 +k+q+?eR?ujCeqj bracketrightbig, (4.19)
where
d(u) = 1q+
+q
?
?eR+u?q
?
+q
+
?eR?u
. (4.20)
Finally, from equation (4.6), we have
Ceqj = c0eg(u?3j ?u?3j?1) (4.21)
where glessmuch1 is the strength of step interactions.
4.3.2 Terrace width
Via equation (4.1), the normalized terrace width satisfies
?uj = ?xj+1? ?xjL (4.22a)
= ?La
bracketleftbigg
?Jj+1(xj+1) + (Jj(xj+1) +Jj(xj))?Jj?1(xj)
bracketrightbigg
(4.22b)
87
= ?La
bracketleftbigg
+q+B+j+1 +q?B?j+1
?q+B+j (1 +eR+uj)?q?B?j (1 +eR?uj)
+q+B+j?1eR+uj?1 +q?B?j?1eR?uj?1
bracketrightbigg
(4.22c)
= ?La
bracketleftbigg
+Ceqj+2bracketleftbigd(uj+1)k?(q+q???q?q?+)bracketrightbig
+Ceqj+1bracketleftbigd(uj+1)k+(q+q+?eR?uj+1?q?q++eR+uj+1)
?d(uj)k?(q+q??(1 +eR+uj)?q?q?+(1 +eR?uj))bracketrightbig
+Ceqj bracketleftbig?d(uj)k+(q+q+?eR?uj(1 +eR+uj)?q?q++eR+uj(1 +eR?uj))
+d(uj?1)k?(q+q??eR+uj?1?q?q?+eR?uj?1)bracketrightbig
+Ceqj?1bracketleftbigd(uj?1)k+(q+q+?eR?uj?1eR+uj?1?q?q++eR+uj?1eR?uj?1))bracketrightbig
bracketrightbigg
(4.22d)
= ?Lac0
bracketleftbigg
eg(u?3j+2?u?3j+1)[?d(uj+1)k+k?(q+?q?)]
+eg(u?3j+1?u?3j )bracketleftbig+d(uj+1)k+(?q?q++eR+uj+1 +q+q+?eR?uj+1)
?d(uj)k?(q+q??(1 +eR+uj)?q?q?+(1 +eR?uj))bracketrightbig
+eg(u?3j ?u?3j?1)bracketleftbig?d(uj)k+(k?(q+?q?)e(R++R?)uj
?q?q++eR+uj +q+q+?eR?uj)
+d(uj?1)k?(q+q??eR+uj?1?q?q?+eR?uj?1)bracketrightbig
+eg(u?3j?1?u?3j?2)bracketleftbig+d(uj?1)k+k?(q+?q?)e(R++R?)uj?1bracketrightbig
bracketrightbigg
. (4.22e)
Therefore, dujdt depends on the two terraces to either side: uj, uj+1,uj?1, and
uj+2,uj?2. However, the dependence on uj+2 and uj?2 is only through the step-step
interactions. If g = 0, dujdt depends only on uj+1,uj,uj?1.
88
4.4 Linearization
To make progress with the solution of equation 4.22e, we find the linearization. The
coefficients of uj+2 and uj?2 will be O(g), reflecting that the two-away neighbors
only affect the step motion through step-step interactions. We then investigate the
dependence of all the coefficients on the physical parameters, in the limiting cases of
very strong and very weak electric field.
4.4.1 Subordinate functions
We will linearize around the solution corresponding to equally spaced steps, that is,
uj = 1 for all j. We define the deviation
?uj = uj?1 (4.23)
so we may consider|?uj|lessmuch1. Several parts of equation (4.22e) must be linearized.
eKuj ?eK +KeK?uj +Oparenleftbig?u2jparenrightbig, (4.24)
u?3j ?u?3j?1?3?uj?1?3?uj +Oparenleftbig?u2j + ?u2j?1parenrightbig, (4.25)
d(uj)?d0 +d1?uj +Oparenleftbig?u2jparenrightbig, (4.26)
where
d0 = 1q+
+q
?
?eR+?q
?
+q
+
?eR?
, d1 = ?q
+
+q
?
?R+eR+ +q
?
+q
+
?R?eR?parenleftbig
q++q??eR+?q?+q+?eR?parenrightbig2
. (4.27)
We note that
d0R+ +d1 =?d20(R+?R?)q?+q+?eR?, (4.28a)
89
d0R? +d1 =?d20(R+?R?)q++q??eR+, (4.28b)
d0(R+ +R?) +d1 = +d20(q++q??R?eR+?q?+q+?R+eR?) (4.28c)
4.4.2 Terrace width evolution
We now find the linearization of ??uj = ?uj. We require each of|?uj|lessmuch1,|g?uj|lessmuch1, and
|R??uj|lessmuch1 for all j.
??uj ? ?
Lac0
bracketleftbigg
(1?3g?uj+2 + 3g?uj+1)[?(d0 +d1?uj+1)(k+k?(q+?q?))]
+ (1?3g?uj+1 + 3g?uj)bracketleftbig+(d0 +d1?uj+1)(k+(?q?q++eR+ +q+q+?eR?)
+k+(?q?q++R+eR+ +q+q+?R?eR?)?uj+1)
?(d0 +d1?uj)(k?(q+q??(1 +eR+)?q?q?+(1 +eR?))
+k?(q+q??R+eR+?q?q?+R?eR?)?uj)bracketrightbig
+ (1?3g?uj + 3g?uj?1)bracketleftbig?(d0 +d1?uj)(k+(k?(q+?q?)eR++R?
?q?q++eR+ +q+q+?eR?)
+k+(k?(R+ +R?)(q+?q?)eR++R?
?q?q++R+eR+ +q+q+?R?eR?)?uj)
+ (d0 +d1?uj?1)(k?(q+q??eR+?q?q?+eR?)
+k?(q+q??R+eR+?q?q?+R?eR?)?uj?1)bracketrightbig
+ (1?3g?uj?1 + 3g?uj?2)bracketleftbig+(d0 +d1?uj?1)(k+k?(q+?q?)eR++R?
+k+k?(R+ +R?)(q+?q?)eR++R??uj?1)bracketrightbig
bracketrightbigg
+Oparenleftbig?u2?parenrightbig (4.29a)
? ?Lac0
bracketleftbigg
(1?3g?uj+2 + 3g?uj+1)
90
bracketleftbig?d
0k+k?(q+?q?)
?d1k+k?(q+?q?)?uj+1bracketrightbig
+ (1?3g?uj+1 + 3g?uj)
bracketleftbig+d
0
parenleftbigk
+k?(q+?q?)
parenleftbig1 +eR
+ +eR?
parenrightbig
?(k+ +k?)q+q?parenleftbigeR+?eR?parenrightbigparenrightbig
+d20k2+(R+?R?)(q+?q?)q++q+?eR++R??uj+1
+k?(q+?q?)parenleftbigd20k?(R+?R?)q?+q??eR++R? +d1k+parenrightbig?ujbracketrightbig
+ (1?3g?uj + 3g?uj?1)
bracketleftbig?d
0
parenleftbigk
+k?(q+?q?)
parenleftbigeR
++R? +eR+ +eR?
parenrightbig
?(k+ +k?)q+q?parenleftbigeR+?eR?parenrightbigparenrightbig
?k+(q+?q?)parenleftbigd20k+(R+?R?)q++q+?
+k?(d0(R+ +R?) +d1))eR++R??uj
?d20k2?(R+?R?)(q+?q?)q?+q??eR++R??uj?1bracketrightbig
+ (1?3g?uj?1 + 3g?uj?2)
bracketleftbig+d
0k+k?(q+?q?)eR++R?
+ (d0(R+ +R?) +d1)k+k?(q+?q?)eR++R??uj?1bracketrightbig
bracketrightbigg
+Oparenleftbig?u2?parenrightbig
(4.29b)
? ?Lac0
bracketleftbigg
?uj+2bracketleftbig+3gd0k+k?(q+?q?)bracketrightbig
+ ?uj+1bracketleftbig(q+?q?)d20(k2+(R+?R?)q++q+?eR++R?
+k+k?(q++q??R+eR+?q?+q+?R?eR?))
91
?3gd0(k+k?(q+?q?)(eR+ +eR? + 2)
?(k+ +k?)q+q?(eR+?eR?))bracketrightbig
+ ?ujbracketleftbig(q+?q?)d20parenleftbig?(R+?R?)(k2+q++q+??k2?q?+q??)eR++R?
?k+k?((q++q??R?eR+?q?+q+?R+eR?)eR++R?
+ (q++q??R+eR+?q?+q+?R?eR?))parenrightbig
+ 3gd0(k+k?(q+?q?)(eR++R? + 2eR+ + 2eR? + 1)
?2(k+ +k?)q+q?(eR+?eR?))bracketrightbig
+ ?uj?1bracketleftbig(q+?q?)d20eR++R?(?k2?(R+?R?)q?+q??
+k+k?(q++q??R?eR+?q?+q+?R+eR?))
?3gd0(k+k?(q+?q?)(2eR++R? +eR+ +eR?)
?(k+ +k?)q+q?(eR+?eR?))bracketrightbig
+ ?uj?2bracketleftbig+3gd0k+k?(q+?q?)eR++R?bracketrightbig
bracketrightbigg
+Oparenleftbig?u2?parenrightbig. (4.29c)
Note that all affine terms have cancelled out.
We will typically use the more compact notation
??uj ?(g?2) ?uj+2 + (?1 +g?1) ?uj+1 + (?0 +g?0) ?uj
+ (??1 +g??1) ?uj?1 + (g??2) ?uj?2, (4.30)
where
?1 = ?c0La (q+?q?)d20(k2+(R+?R?)q++q+?eR++R?
+k+k?(q++q??R+eR+?q?+q+?R?eR?)), (4.31a)
??1 = ?c0La (q+?q?)d20eR++R?(?k2?(R+?R?)q?+q??
92
+k+k?(q++q??R?eR+?q?+q+?R+eR?)), (4.31b)
?0 =?(?1 +??1); (4.31c)
?2 = 3?c0La d0k+k?(q+?q?), (4.31d)
??2 = 3?c0La d0k+k?(q+?q?)eR++R?, (4.31e)
?1 =?3?c0La d0(k+k?(q+?q?)(eR+ +eR? + 2)
?(k+ +k?)q+q?(eR+?eR?)), (4.31f)
??1 =?3?c0La d0(k+k?(q+?q?)(2eR++R? +eR+ +eR?)
?(k+ +k?)q+q?(eR+?eR?)), (4.31g)
?0 =?(?2 +?1 +??1 +??2). (4.31h)
4.4.3 Dependence on the physical parameters
Here we examine the behavior of each of the coefficients ?n, ?n. A summary of the
physical parameters appears in Appendix B.1. We should always have
(A9) L > 0, a > 0, ? > 0, c0 > 0, ? > 0, D > 0, k+ > 0, k? > 0
We will also assume
(A10) v0 > 0, g?0
Then we have q+ > 0 > q? and R+ > 0 > R?.
From these assumptions, we first note that
d0 =bracketleftbigq++q??eR+?q?+q+?eR?bracketrightbig?1 (4.32a)
=bracketleftbig(q+q??k+q+ +k?q??k+k?)eR+
93
?(q+q? +k?q+?k+q??k+k?)eR?bracketrightbig?1 (4.32b)
=bracketleftbig(q+q??k+k?)parenleftbigeR+?eR?parenrightbig
?q+parenleftbigk+eR+ +k?eR?parenrightbig+q?parenleftbigk?eR+ +k+eR?parenrightbigbracketrightbig?1 (4.32c)
< 0. (4.32d)
Holding all the parameters L,a,?,c0,?,D,k+,k? constant, and letting v0 vary
in (0,?), we have
R+?
??
???
????
Lv0/D for v0greatermuch1
L/?D? for v0lessmuch1,
R??
?
????
???
?
?L/(v0?) for v0greatermuch1
?L/?D? for v0lessmuch1,
(4.33a)
q+?
??
???
????
D/(v0?) for v0greatermuch1
radicalbigD/? for v
0lessmuch1,
q??
??
???
????
?v0 for v0greatermuch1
?radicalbigD/? for v0lessmuch1.
(4.33b)
Further assuming that ? = L/?D? lessmuch1, we have
d0?
?
???
?
???
?
?bracketleftbigk?v0eLv0/Dbracketrightbig?1 for v0greatermuch1
?
bracketleftBig
2(k+ +k?)radicalbigD/?
bracketrightBig?1
+O(?) for v0lessmuch1.
(4.34)
4.4.3.1 Non-interaction terms (O(1))
From equation (4.31a), we can calculate
?1? ?c0La ?
?
????
???
?
?k+(k++k?)k? Lv0D e?Lv0/D for v0greatermuch1
??
radicalBig
D
?
k+
k++k? for v0lessmuch1.
(4.35)
94
From equation (4.31b), we can calculate
??1? ?c0La ?
?
???
?
???
?
k+ Lv0? for v0greatermuch1
?
radicalBig
D
?
k?
k++k? for v0lessmuch1.
(4.36)
When the electric field is very strong, ?1?0? and ??1?0+, with ?1 decaying
faster in v0 than ??1.
In the case where there is no Ehrlich-Schwoebel effect, that is, k+ = k?, then,
when the electric field is very weak, we have ?1????1, and ?0?0.
4.4.3.2 Step-step interaction terms (O(g))
From equation (4.31d), we know ?2 < 0 for all valid choices of the physical parameters.
We can calculate
?2? ?c0La ?
?
???
?
???
?
?3k+e?Lv0/D for v0greatermuch1
?3 k+k?k++k? for v0lessmuch1.
(4.37)
From equation (4.31e), we know it is also true that ??2 < 0 for all valid choices
of the physical parameters. We can calculate
??2? ?c0La ?
?
???
?
???
?
?3k+ for v0greatermuch1
?3 k+k?k++k? for v0lessmuch1.
(4.38)
From equation (4.31f), we know ?1 > 0 for all valid choices of the physical
parameters. We can calculate
?1? ?c0La ?
?
???
?
???
?
3k+ for v0greatermuch1
12 k+k?k++k? for v0lessmuch1.
(4.39)
95
From equation (4.31g), we know ??1 > 0 for all valid choices of the physical
parameters as well. We can calculate
??1? ?c0La ?
?
???
?
???
?
9k+ for v0greatermuch1
12 k+k?k++k? for v0lessmuch1.
(4.40)
When the electric field is very strong, we have ?2???2, while ??1?3?1.
When the electric field is very weak, we have ?2???2, and ?1???1.
96
4.5 Solutions to linearized equation
We transform the linearized step motion equation to simplify the coupling, thus find-
ing an integral expression for ?uj(t). We then use the method of steepest descents to
estimate this integral for long times t.
4.5.1 Transformation
Emulating the solution to a difference equation in [59], we assume that ?uj(t) takes
the form
?uj(t) =
integraldisplay
C(t)
eijzf(z,t)dz (4.41)
for all j,t, for some fixed function f(z,t) and contours C(t). Writing the endpoints of
C(t) as C0(t),C1(t), and assuming we may interchange integration and differentiation,
the Leibniz integral rule gives
??uj(t) =
integraldisplay
C(t)
eijz?f?t (z,t)dz +Cprime1(t)eijC1(t)f(C1(t),t)?Cprime0(t)eijC0(t)f(C0(t),t). (4.42)
To eliminate the last two terms, we require the endpoint contribution of the integrand
to vanish, so eijzf(z,t)?0 in measure as z?a(t), z?b(t).
For convenience, we define
h(z) = (g?2)e2iz +(?1+g?1)eiz +(?0+g?0)+(??1+g??1)e?iz +(g??2)e?2iz. (4.43)
Now, substituting equation (4.41) into equation (4.30) gives
integraldisplay
C(t)
eijz?f?t (z,t)dz?
integraldisplay
C(t)
eijzh(z)f(z,t)dz. (4.44)
For this equation to hold for all j, f(z,t) should satisfy the differential equation
?f
?t (z,t) = h(z)f(z,t), (4.45)
97
which has solutions
f(z,t) =U(z)eth(z). (4.46)
We will use the requirement U(x) ? 0 as x ??? to ensure the vanishing
endpoint contributions in equation 4.42. Then we can take C(t) = R for all t, so
that equation 4.41 is a simple Fourier transform. The other factors eijz and eth(z) are
oscillatory along this contour, confirming decay at the endpoints.
4.5.2 Initial data
U(z) can be determined by the initial data of the problem. We have ?uj(0) =
integraltext
R e
ijzf(z,0)dz =integraltext
R e
ijzU(z)dz. Treating j as a real (rather than integer) parameter,
we see thatU(z) is the inverse Fourier transform of ?uj(0):
U(z) = 12pi
integraldisplay
R
e?izj?uj(0)dj. (4.47)
To represent a valid physical system, ?uj(0) must be continuous in j, the average
of the ?uj(0) over all j?Z must equal 0, and we must have ?uj(0)??1 for all j. We
also restrict ourselves to ?uj(0) such thatU(z)?0 as z???in a neighborhood of
the real axis.
Later, we will need to use the fact that that U(?z) = U(z), which is easily
verified:
U(?z) = 12pi
integraldisplay
R
eijz?uj(0)dj (4.48a)
= 12pi
integraldisplay
R
e?ijz?uj(0)dj (4.48b)
= 12pi
integraldisplay
R
e?ijz?uj(0)dj (4.48c)
98
=U(z) (4.48d)
As a consequence,Umaps the imaginary axis to the real axis, sinceU(iy) =U(?iy) =
U(iy).
As an example, we might choose ?uj(0;epsilon1) = je?|j|/epsilon1, which yields U(z;epsilon1) =
?2ipi epsilon13z(1+(epsilon1z)2)2. Since ?uj(0;epsilon1) is an odd function of j, we are guaranteed that
1
2N + 1
Nsummationdisplay
j=?N
?uj(0;epsilon1) = 0 (4.49)
for all N, including N ??.
4.5.3 Steepest descents
From equations (4.41) and (4.46), we have
?uj(t) =
integraldisplay
R
U(z)eijzeth(z)dz, (4.50)
where U(z) is given by equation (4.47). In each case below, we will consider the
complex plane restricted to x?(?pi,pi] to determine the relevant critical point(s) and
contour of integration. This region should be repeated at intervals of 2npi (n?Z) to
deform the entire real line R. eijz and eth(z) are periodic in Real(z) with period 2pi,
so only the value ofU(z) will differ between regions.
We are interested in the long-term behavior of the terrace widths, so we assume
tgreatermuch1. We consider steps ?in the bulk? of the crystal, wherevextendsinglevextendsinglejtvextendsinglevextendsinglelessmuch1. To approximate
the above integral using Riemann?s method of steepest descents, we must locate the
critical points where hprime(z) = 0. From h(z) in equation (4.43), we have
hprime(z) = iparenleftbig2(g?2)e2iz + (?1 +g?1)eiz?(??1 +g??1)e?iz?2(g??2)e?2izparenrightbig. (4.51)
99
Letting w = eiz, we know that w cannot equal 0. Therefore, hprime(z) = 0 if and only if
w is a nonzero root of the polynomial
pg(w) = (2g?2)w4 + (?1 +g?1)w3?(??1 +g??1)w?(2g??2). (4.52)
Suppose we have determined a contour C passing through a unique maximum
critical point z0, where hprime(z0) = 0. We can approximate equation (4.50) by making
the change of variable
?2 = h(z0)?h(z)??12hprimeprime(z0)(z?z0)2 +Oparenleftbig(z?z0)3parenrightbig (4.53)
so that z ?z0 +bracketleftbig?12hprimeprime(z0)bracketrightbig?1/2 ? +O(?2) and dzd? ?bracketleftbig?12hprimeprime(z0)bracketrightbig?1/2 +O(?). (Here
we must fix a branch of the square root function. We choose it such that?z =?z
for all z not on the negative real axis.) Then
?uj(t) =
integraldisplay
C
U(z)eijzeth(z)dz (4.54a)
?
integraldisplay
R
U(z(?))eijz(?)et(h(z0)??2)dzd? d? (4.54b)
?U(z0)eijz0eth(z0)
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2integraldisplay
R
e?t?2d? (4.54c)
=U(z0)??pi
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
?(eiz0)j?eth(z0)t?1/2. (4.54d)
The factor t?1/2 is a departure from continuum estimations. It is the fastest decay
we could expect to see in an asymptotic expansion. If the first non-zero derivative of
h were of higher order (hprime(z0) = hprimeprime(z0) =???= h(m?1)(z0) = 0, h(m)(z0)negationslash= 0, m > 2),
the decay would be t?1/m.
100
-32-101234-202
4
(a) Both real
-32-101234-202
4
(b) Both complex
Figure 4.2: The case g = 0. Contours of constant imaginary part equal to the
imaginary part of a critical point, shown for x?(?pi,pi].
4.5.3.1 No step interactions (g = 0)
In this case, the polynomial (4.52) is simply
p0(w) = ?1w3???1w. (4.55)
We must ignore the root w = 0, because 0 = w = eiz has no solutions for finite z.
The other roots are?w0, where w0 =
radicalBig?
?1
?1 . Depending on the physical parameters,
w0 may be real, pure imaginary, or zero. w0 = 0 is a bifurcation point, so we analyze
the other two cases in depth. They are generically pictured in Figure 4.2.
The deformed integration path should be chosen so that Imag(h(z)) is constant
and Real(h(z)) reaches a maximum at a critical point. We have
Imag(h(x +iy)) = sin(x)parenleftbig?1e?y???1eyparenrightbig, (4.56a)
Real(h(x +iy)) = cos(x)parenleftbig?1e?y +??1eyparenrightbig+?0. (4.56b)
4.5.3.1.1 Real roots (sign(?1) = sign(??1)). When w0 is real, h(z0) is real as
well, so we must find the contours where Imag(h(z)) = 0. We immediately see that
101
Imag(h(x +iy)) = 0 if and only if x = npi (for some n?Z) or e?y =
radicalBig?
?1
?1 .
When x = 2npi, we have cos(x) = 1, so Real(h(x +iy))??? as y ???.
Similarly, when x = (2n + 1)pi, Real(h(x +iy))?+?. Therefore, along the hori-
zontal contour y = ?ln
radicalBig?
?1
?1 in Figure 4.2(a), we know that Real(h(z)) reaches a
maximum at the points zn = (2n + 1)pi?iln
radicalBig?
?1
?1 . We have z0 = pi?iln
radicalBig?
?1
?1 .
For the final calculation, note that
eiz0 =?w0 =?
radicalbigg?
?1
?1 < 0, (4.57a)
h(z0) =
parenleftBigradicalbig
|?1|+
radicalbig
|??1|
parenrightBig2
> 0, (4.57b)
hprimeprime(z0) =?2??1??1 < 0. (4.57c)
Also recall thatU(?z) =U(z). Now, by summing equation (4.54) over all adjacent
regions of width 2pi, we have
?uj(t)?
summationdisplay
n?Z
U(z0 + 2npi)??pi
bracketleftbigg
?12hprimeprime(z0 + 2npi)
bracketrightbigg?1/2
?(ei(z0+2npi))j?eth(z0+2npi)t?1/2
(4.58a)
=?pi
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
?(?w0)j?eth(z0)t?1/2?
summationdisplay
n?Z
U
parenleftbigg
(2n + 1)pi?iln
radicalbigg?
?1
?1
parenrightbigg
(4.58b)
=?pi(?1??1)?1/4?
parenleftbigg
?
radicalbigg?
?1
?1
parenrightbiggj
?et
??
|?1|+
?
|??1|
?2
t?1/2
?2
?summationdisplay
n=0
Real
parenleftbigg
U
parenleftbigg
(2n + 1)pi?iln
radicalbigg?
?1
?1
parenrightbiggparenrightbigg
. (4.58c)
4.5.3.1.2 Pure imaginary roots (sign(?1)negationslash= sign(??1)). Here w0 = i
radicalbiggvextendsingle
vextendsinglevextendsingle??1
?1
vextendsinglevextendsingle
vextendsingle,
so zn = (n + 12)pi?iln
radicalbiggvextendsingle
vextendsinglevextendsingle??1
?1
vextendsinglevextendsingle
vextendsingle for n?Z are all the critical points.
102
When w0 is imaginary, h(z0) is complex. Furthermore, we have the imagi-
nary part Imag(h(x +iy)) = 0 only when x = npi (n ? Z), and not along the
horizontal contour in Figure 4.2(a). Because the contours where Imag(h(x +iy)) =
Imag(h(z0)), a nonzero constant, may not cross the contours where Imag(h(z)) = 0,
they are restricted to regions where x?(npi,(n+1)pi), so we have y???. There-
fore, to keep Imag(h(x +iy)) from growing, we must have sin(x)?0 with exponen-
tial decay. This implies that the contours are asymptotic to x = npi (n?Z).
When x ? 2npi, we have cos(x) > 0, so Real(h(x +iy)) ? ?? as y ?
?? and Real(h(x +iy)) ? +? as y ? +?. Similarly, when x ? (2n + 1)pi,
Real(h(x +iy))?+?as y???and Real(h(x +iy))???as y?+?. There-
fore, along the contour joining (?pi,+?) to (0,??) to (pi,+?) in Figure 4.2(b),
Real(h(z)) reaches maxima at the critical points z0,?z0.
For the final calculation, note that
eiz0 = w0 = i
radicalBiggvextendsingle
vextendsinglevextendsingle
vextendsingle
??1
?1
vextendsinglevextendsingle
vextendsinglevextendsingle, (4.59a)
h(z0) =|?1|?|??1|?2i
radicalbig
|?1??1|, (4.59b)
hprimeprime(z0) = 2i
radicalbig
|?1??1|. (4.59c)
Also note that h(?z) = h(z) as well. Now we have
?uj(t)?
summationdisplay
n?Z
U(z0 + 2npi)??pi
bracketleftbigg
?12hprimeprime(z0 + 2npi)
bracketrightbigg?1/2
?(ei(z0+2npi))j?eth(z0+2npi)t?1/2
+
summationdisplay
n?Z
U(?z0?2npi)??pi
bracketleftbigg
?12hprimeprime(?z0?2npi)
bracketrightbigg?1/2
?(ei(?z0?2npi))j?eth(?z0?2npi)t?1/2 (4.60a)
103
=?pit?1/2
summationdisplay
n?Z
parenleftbigg
U(z0 + 2npi)?
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
wj0eth(z0)
+U(z0 + 2npi)?
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
w0jeth(z0)
parenrightbigg
(4.60b)
= 2?pit?1/2
summationdisplay
n?Z
Real
parenleftBigg
U(z0 + 2npi)?
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
wj0eth(z0)
parenrightBigg
(4.60c)
= 2?pit?1/2
?
?Real
?
?
parenleftBig
?i
radicalbig
|?1??1|
parenrightBig?1/2parenleftBigg
i
radicalBiggvextendsingle
vextendsinglevextendsingle
vextendsingle
??1
?1
vextendsinglevextendsingle
vextendsinglevextendsingle
parenrightBiggj
eth(z0)
?
?
?
summationdisplay
n?Z
Real(U(z0 + 2npi))
?Imag
?
?parenleftBig?iradicalbig|?1??1|parenrightBig?1/2
parenleftBigg
i
radicalBiggvextendsingle
vextendsinglevextendsingle
vextendsingle
??1
?1
vextendsinglevextendsingle
vextendsinglevextendsingle
parenrightBiggj
eth(z0)
?
?
?
summationdisplay
n?Z
Imag(U(z0 + 2npi))
bracketrightBigg
. (4.60d)
4.5.3.2 Step repulsions (g > 0)
In this case, pg(w) is given by the full equation (4.52). Note that pg(w) has real
coefficients, so if w0 is a root, then w0 is also a root. This implies that if z0 is a
critical point, then?z0 is also a critical point.
We know that ??2 are both negative. Therefore, pg(w) ??? as w ???,
and pg(0) > 0. The intermediate value theorem implies that pg(w) has at least two
real roots, one positive and one negative. Furthermore, if pg(w) has four real roots,
it is either the case that three are positive and one is negative, or one is positive and
three are negative. The cases are generically pictured in Figure 4.3.
It is possible to determine whether pg(w) has four real roots, or two real and
two complex roots, by finding the sign of the discriminant of pg(w) (positive in the
104
-32-101234-202
4
(a) Three positive
-32-101234-202
4
(b) Three negative
-32-101234-202
4
(c) One positive, one negative,
two complex conjugates
Figure 4.3: The case g > 0. Contours of constant imaginary part equal to the
imaginary part of a critical point, shown for x?(?pi,pi].
former case, negative in the latter).
4.5.3.2.1 Constant imaginary part. The deformed integration path should be
chosen so that Imag(h(z)) is constant. We have
Imag(h(x +iy)) = sin(x)parenleftbig2cos(x)bracketleftbig(g?2)e?2y?(g??2)e2ybracketrightbig
+bracketleftbig(?1 +g?1)e?y?(??1 +g??1)eybracketrightbigparenrightbig (4.61)
First, consider a real root w0 of pg(w). Since w0 is real, h(z0) is also real, so
we must find the contours where Imag(h(x +iy)) = 0. This equality holds when
sin(x) = 0, or when cos(x) = ?(?1+g?1)e?y+(??1+g??1)ey2((g?2)e?2y?(g??2)e2y) , which approaches 0 as y ?
??. Therefore, for all n?Z, the contours x = npi satisfy Imag(h(z)) = 0, and the
lines x = pi2 +npi are asymptotes of the remaining contours with Imag(h(z)) = 0.1
1It is not possible to choose, e.g., x = 0 as the deformed contour, because the deformation would
have to pass through regions of x-values where the integral does not converge.
105
Now, consider a possible complex root w0 of pg(w). We must find the contours
where Imag(h(x +iy)) = Imag(h(z0)), a nonzero constant. Since these may not
cross the contours where Imag(h(z)) = 0, they are restricted to regions where x ?
(npi,(n + 1)pi), so y ???. Since the term (g?2)e?2y ?(g??2)e2y dominates the
growth in y, we must have either sin(x) ? 0 or cos(x) ??(?1+g?1)e?y+(??1+g??1)ey2((g?2)e?2y?(g??2)e2y)
fast enough to keep Imag(h(z)) from growing. Once again, we find that the contours
are asymptotic to x = npi and x = pi2 +npi (n?Z).
4.5.3.2.2 Steepest descent paths. We will integrate over contours where the
real part Real(h(z)) reaches a maximum at one of the critical points. We have
Real(h(x +iy)) = cos(2x)bracketleftbig(g?2)e?2y + (g??2)e2ybracketrightbig
+ cos(x)bracketleftbig(?1 +g?1)e?y + (??1 +g??1)eybracketrightbig+ (?0 +g?0). (4.62)
Since e?2y dominate the growth of Real(h(z)) as y ???, and ??2 < 0, we have
Real(h(z))?+?along the lines x = pi2 +npi (n?Z), and Real(h(z))???along
the lines x = npi (n?Z). We now have three cases to consider.
In the first case, pg(w) has three positive roots and one negative root. Let w0 be
the middle positive root, and z0 =?iln(w0). The necessary contour in Figure 4.3(a)
joins z0 to the negative root and its reflection. By summing equation (4.54) over all
adjacent regions of width 2pi, we have
?uj(t)?
summationdisplay
n?Z
U(z0 + 2npi)??pi
bracketleftbigg
?12hprimeprime(z0 + 2npi)
bracketrightbigg?1/2
?w?j0 ?eth(z0+2npi)t?1/2 (4.63a)
=?pi
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
?w?j0 ?eth(z0)t?1/2?
summationdisplay
n?Z
U(iln(w0) + 2npi), (4.63b)
106
and, becauseU(?z) =U(z),
summationdisplay
n?Z
U(iln(w0) + 2npi) =U(iln(w0)) +
?summationdisplay
n=1
parenleftbigU(2npi +iln(w
0)) +U(?2npi +iln(w0))
parenrightbig
(4.64a)
=U(iln(w0)) + 2
?summationdisplay
n=1
Real(U(2npi +iln(w0)))?R. (4.64b)
In the second case, pg(w) has one positive root and three negative roots. Let
w0 be the middle negative root, and z0 = pi?iln|w0|. The necessary contour in
Figure 4.3(b) joins z0 and its reflection to the positive root. As above, we have
?uj(t)??pi
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
?w?j0 ?eth(z0)t?1/2?
summationdisplay
n?Z
U(iln|w0|+ (2n + 1)pi), (4.65)
and
summationdisplay
n?Z
U(iln|w0|+ (2n + 1)pi) =
?summationdisplay
n=0
parenleftbigU((2n + 1)pi +iln|w
0|)
+U(?(2n + 1)pi +iln|w0|)parenrightbig (4.66a)
= 2
?summationdisplay
n=0
Real(U((2n + 1)pi +iln|w0|))?R. (4.66b)
In the third case, pg(w) has one positive root, one negative root, and two com-
plex conjugate roots. Let w0 = eiz0 be the root with positive imaginary part, and
w0 = ei(?z0) the root with negative imaginary part. In Figure 4.3(c), the necessary
contour for z0 proceeds from the asymptote x = ?pi to the asympote x = 0, while
the contour for ?z0 proceeds from the asymptote x = 0 to the asympote x = +pi.
We have
?uj(t)?
summationdisplay
n?Z
U(z0 + 2npi)??pi
bracketleftbigg
?12hprimeprime(z0 + 2npi)
bracketrightbigg?1/2
?w?j0 ?eth(z0+2npi)t?1/2
107
+
summationdisplay
n?Z
U(?z0?2npi)??pi
bracketleftbigg
?12hprimeprime(?z0?2npi)
bracketrightbigg?1/2
?w0?j?eth(?z0?2npi)t?1/2 (4.67a)
=?pit?1/2
summationdisplay
n?Z
parenleftbigg
U(z0 + 2npi)?
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
w?j0 eth(z0)
+U(z0 + 2npi)?
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
w0?jeth(z0)
parenrightbigg
(4.67b)
= 2?pit?1/2
summationdisplay
n?Z
Real
parenleftBigg
U(z0 + 2npi)?
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
w?j0 eth(z0)
parenrightBigg
, (4.67c)
using the fact that h(?z) = h(z) as well.
4.5.3.3 Relationship between the solutions (glessmuch1)
Assume that a root w of pg(w) can be expanded as
w = w0 +g?w1 +g2?w2 +??? (4.68)
for some ?negationslash= 0.
First, assume that w0 = 0, and w?g?w1. Then
g4?+1(2?2w41)bracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright
1?
+g3?(?1w31)bracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright
2?
+g?(???1w1)bracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright
3?
+g1(?2??2)bracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright
4?
?0. (4.69)
The balance between 1?and 2?yields ? =?1, and thus w1 =??12?2. The balance
between 3?and 4?yields ? = 1, and thus w1 =?2??2??1 . So two of the roots are
w???12?
2
g?1 and w??2??2?
?1
g. (4.70)
Now, assume that w0negationslash= 0. Then
g1(2?2w40?2??2)bracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright
1?
+g0(?1w30???1w0)bracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright
2?
+g?(3?1w20w1???1w1)bracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright
3?
?0. (4.71)
108
TheO(1) term yields w0 =?
radicalBig?
?1
?1 . The balance between 1?and 3?yields ? = 1,
and thus w1 =?2 ?2w40???23?
1w20???1
= ??2?21??2?2?1?2
1??1
. So the other two roots are
w?
radicalbigg?
?1
?1 +gw1 and w??
radicalbigg?
?1
?1 +gw1. (4.72)
The O(1) roots correspond to the roots in the deformed contours we chose
for the integration ? they are either the two complex roots, or one is the middle
positive/negative root, since the remaining roots areO(g)?0 andO(g?1)???.
4.5.3.3.1 Dependence on time and step number. The step-step interaction
case can now be considered as a regular perturbation of the no-interaction case, for
steps in the bulk of the crystal.
When ?1 and ??1 have equal signs, which is possible for some intermediate
values of v0, we have equation (4.58c):
?uj(t)??pi(?1??1)?1/4?
parenleftbigg
?
radicalbigg?
?1
?1
parenrightbiggj
?et
??
|?1|+
?
|??1|
?2
t?1/2
?2
?summationdisplay
n=0
Real
parenleftbigg
U
parenleftbigg
(2n + 1)pi?iln
radicalbigg?
?1
?1
parenrightbiggparenrightbigg
The time dependence is proportional to et
??
|?1|+
?
|??1|
?2
t?1/2, which is exponential
growth with a polynomial decay term. The dependence on j is proportional to
parenleftBig
?
radicalBig?
?1
?1
parenrightBigj
, which is growth or decay depending on the sign of j. Note that the
sign of ?uj(t) alternates with odd and even values of j.
When ?1 and ??1 have opposite signs, which holds for very strong and very
weak electric fields, we have equation (4.60c):
?uj(t)?2?pit?1/2
summationdisplay
n?Z
Real
parenleftBigg
U(z0 + 2npi)?
bracketleftbigg
?12hprimeprime(z0)
bracketrightbigg?1/2
wj0eth(z0)
parenrightBigg
109
First consider the time dependence. Recall from equation (4.59) that Real(h(z0)) =
|?1|?|??1|. We found in Section 4.4.3 that ?1 decays to 0 faster than ??1 when
the electric field is very strong, implying that Real(h(z0)) < 0. Now consider the
dependence on step number. Recall that w0 = i
radicalbiggvextendsingle
vextendsinglevextendsingle??1
?1
vextendsinglevextendsingle
vextendsingle, so again we have growth or
decay depending on the sign of j.
110
4.6 Discussion
We have analyzed the motion of crystal steps as a discrete system of coupled linear
ODEs. Much of the literature has focused on continuum approximations of surface
height, which can provide reliable indications of the stability of uniform step trains;
step bunching is one form of instability. However, these continuum approximations
miss a time dependence term that appears in the discrete analysis, and they do not
give a full picture of the dependence on step number.
Recall our measure of the deviation of terrace width from the average value,
?uj(t) = xj+1(t)?xj(t)L ?1. We found that the time dependence of ?uj(t) is proportional
to eth(z0)t?1/2. The t?1/2 factor does not appear in continuum approximations, and is
the fastest decay we can expect from a first-order asymptotic analysis of the discrete
model. The h(z0) exponent depends on the physical parameters of the problem.
Stability is indicated when ?uj(t) decays with time, while instabilities such as step
bunching are possible when ?uj(t) grows with time.
We also found that the step number dependence of ?uj(t) is proportional to
(eiz0)j. Therefore, ?uj(t) grows or decays in j depending on the sign of j. We have
identified parameter regions where the base eiz0 is a negative real number, indicating
alternating signs of the terrace width deviation. Such alternation could lead to the
?double steps? that have been observed in silicon [60] and ruthenium [64].
111
Appendix A
Addendum to Chapter 3
A.1 Standard ports
In 2003, many peer-to-peer applications used constant port numbers. In addition,
many client-server applications use IANA-assigned ports, or other constant ports.
The following port values were used for determining the ?true? classes in Section 3.3.1.
Table A.1: Peer-to-peer ports, protocols, and their usages. Compiled from
various online sources.
Port Protocol Application
412 TCP/UDP DirectConnect
1214 TCP KaZaA
1412 TCP/UDP DirectConnect
2000 TCP eDonkey 2000
2004 UDP eDonkey 2000
2234 TCP SoulSeek
3415 TCP KaZaA
3531 TCP/UDP KaZaA
4329 TCP iMesh
4444 TCP Napster
4661 TCP eDonkey 2000
4662 TCP eDonkey 2000
4663 TCP eDonkey 2000
4665 UDP eDonkey 2000
4666 UDP eDonkey 2000
4670 TCP eDonkey 2000
112
Table A.2: Table A.1 continued.
Port Protocol Application
5498 TCP Hotline Connect
5499 UDP Hotline Connect
5500 TCP Hotline Connect
5501 TCP Hotline Connect
5502 TCP Hotline Connect
5503 TCP Hotline Connect
5534 TCP SoulSeek
5555 TCP Napster
6257 UDP WinMX
6346 TCP Gnutella
6347 UDP Gnutella
6348 TCP Gnutella
6662 TCP eDonkey 2000
6666 TCP Napster
6699 TCP WinMX
6700 TCP Napster
6701 TCP Napster
6881 TCP BitTorrent
7674 UDP Soribada
7675 TCP Soribada
7676 TCP Soribada
7677 TCP Soribada
7788 TCP/UDP BuddyShare
8311 TCP Scour
8875 TCP Napster
8888 TCP Napster
8889 TCP Napster
22321 TCP/UDP Soribada
22322 TCP Soribada
41170 TCP/UDP Blubster, Piolet, Manolito
113
Table A.3: Client/server ports, protocols, and their usages. Compiled from
various online sources.
Port Protocol Application
20 TCP FTP
21 TCP FTP
22 TCP SSH
23 TCP telnet
25 TCP SMTP
53 TCP/UDP DNS
80 TCP HTTP
110 TCP POP3
123 UDP network time protocol
143 TCP IMAP
389 TCP/UDP LDAP
443 TCP HTTPS
993 TCP IMAP over SSL
1024 TCP/UDP Windows browsing
1025 TCP/UDP Windows browsing
1026 TCP/UDP Windows browsing
1080 TCP proxy server
1490 TCP vocaltec videoconferencing
1755 UDP windows media streaming
1863 TCP/UDP msn messenger
2703 TCP/UDP SpamAssassin
4099 TCP AIM
5050 TCP Yahoo IM
5190 TCP aim
6277 TCP/UDP DCC anti-spam
6665 TCP IRC
6667 TCP IRC
6670 TCP vocaltec videoconferencing
7070 TCP/UDP realaudio
8000 TCP webserver
8080 TCP HTTP2
22555 UDP vocaltec videoconferencing
25793 TCP vocaltec videoconferencing
32768 TCP/UDP *nix browsing
32769 TCP/UDP *nix browsing
32770 TCP/UDP *nix browsing
114
Appendix B
Addendum to Chapter 4
B.1 Parameters and variables of the crystal problem
Table B.1: Overview of parameters and variables.
Symbol Dimensions Brief description
L length Typical terrace width
a length Step height
? length2 Atomic volume
xj(t) length Position of jth step edge at time t
uj(t) ? (xj+1(t)?xj(t))/L; normalized length of jth terrace
?uj(t) ? uj(t)?1; deviation from uniform terrace width
c0 1/length Adatom density at an isolated step
cj(x) 1/length Adatom density at position x on the jth terrace
Jj(x) 1/time Adatom current (flux) at position x on the jth terrace
? time Desorption time
D length2/time Terrace diffusivity
v0 length/time Down-step velocity due to electric field
k+,k? length/time Rate coefficients for attachment-detachment
g ? Strength of step interactions
? ? L/?D?
? ? ?D?/(v0?)
115
Bibliography: Peer-to-peer networks
[1] Abiola Abimbola, Qi Shi, and Madjid Merabti. Using intrusion detection to
detect malicious peer-to-peer network traffic. In PostGraduate Networking Con-
ference (PGNet), Manchester, UK, June 2003.
[2] Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, and
Elan Pavlov. A generic scheme for building overlay networks in adversarial sce-
narios. In International Parallel and Distributed Processing Symposium (IPDPS),
Nice, France, April 2003.
[3] Laurent Bernaille, Renata Teixeira, Ismael Akodkenou, Augustin Soule, and
Kave Salamatian. Traffic classification on the fly. ACM SIGCOMM Computer
Communication Review, 36(2):23?26, April 2006.
[4] Leo Breiman. Random forests. Machine Learning, 45(1):5?32, October 2001.
[5] Leo Breiman and Adele Cutler. Random forests (classification/clustering).
http://www.stat.berkeley.edu/?breiman/RandomForests, June 2004.
[6] Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone.
Classification and Regression Trees. Wadsworth, Inc., Belmont, California, USA,
1984.
[7] Multi-State Information Sharing & Analysis Center. Monthly cyber secu-
rity tips newsletter: Security concerns ? peer to peer (P2P) file sharing.
http://www.msisac.org/awareness/news/2007-04.cfm, April 2007.
[8] Cisco. Cisco IOS NetFlow version 9 flow-record format. http://www.cisco.com,
February 2007.
[9] Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica.
Wide-area cooperative storage with CFS. In ACM Symposium on Operating
Systems Principles (SOSP), Banff, Canada, October 2001.
[10] Anwitaman Datta, Sarunas Girdzijauskas, and Karl Aberer. On de Bruijn rout-
ing in distributed hash tables: There and back again. In IEEE International Con-
ference on Peer-to-Peer Computing (P2P), Zurich, Switzerland, August 2004.
[11] Prasanna Desikan and Jaideep Srivastava. Analyzing network traffic to detect
e-mail spamming machines. In ICDM Workshop on Privacy and Security Aspects
of Data Mining, Brighton, UK, November 2004.
[12] Pedro Domingos and Michael Pazzani. On the optimality of the simple Bayesian
classifier under zero-one loss. Machine Learning, 29(2):103?130, November 1997.
[13] Richard O. Duda and Peter E. Hart. Pattern Classification and Scene Analysis.
Wiley, New York, New York, USA, 1973.
116
[14] Robert Els?asser, Burkhard Monien, and Robert Preis. Diffusion schemes for load
balancing on heterogeneous networks. Theory of Computing Systems, 35(3):305?
320, May 2002.
[15] Ronald Aylmer Fisher. The use of multiple measures in taxonomic problems.
Annals of Eugenics, 7:179?188, September 1936.
[16] Pierre Fraigniaud and Philippe Gauron. D2B: A de Bruijn based content-
addressable network. Theoretical Computer Science, 355(1):65?79, April 2006.
[17] Anh-Tuan Gai and Laurent Viennot. Broose: A practical distributed hashtable
based on the de-Bruijn topology. In IEEE International Conference on Peer-to-
Peer Computing (P2P), Zurich, Switzerland, August 2004.
[18] Prasanna Ganesan, Mayank Bawa, and Hector Garcia-Molina. Online balanc-
ing of range-partitioned data with applications to peer-to-peer systems. In In-
ternational Conference on Very Large Data Bases (VLDB), Toronto, Canada,
September 2004.
[19] Luis Garc?es-Erice, Ernst W. Biersack, Keith W. Ross, Pascal Felber, and Guil-
laume Urvoy-Keller. Hierarchical peer-to-peer systems. Parallel Processing Let-
ters, 13(4):643?657, March 2003.
[20] George Giakkoupis and Vassos Hadzilacos. A scheme for load balancing in hetero-
geneous distributed hash tables. In ACM Symposium on Principles of Distributed
Computing (PODC), Las Vegas, Nevada, USA, July 2005.
[21] Sarunas Girdzijauskas, Anwitaman Datta, and Karl Aberer. On small world
graphs in non-uniformly distributed key spaces. In IEEE International Workshop
on Networking Meets Databases (NetDB), Tokyo, Japan, April 2005.
[22] P. Brighten Godfrey and Ion Stoica. Heterogeneity and load balance in dis-
tributed hash tables. In IEEE Conference on Computer Communications (IN-
FOCOM), Miami, Florida, USA, March 2005.
[23] MIT Lincoln Laboratory; Information Systems Technology Group. LNKnet.
http://www.ll.mit.edu/IST/lnknet, February 2004.
[24] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Sta-
tistical Learning: Data Mining, Inference, and Prediction. Springer Series in
Statistics. Springer, New York, New York, USA, 2001.
[25] M. Frans Kaashoek and David R. Karger. Koorde: A simple degree-optimal
distributed hash table. In International Workshop on Peer-to-Peer Systems
(IPTPS), Berkeley, California, USA, February 2003.
[26] Thomas Karagiannis, Andre Broido, Michalis Faloutsos, and Kc claffy. Transport
layer identification of P2P traffic. In ACM SIGCOMM Internet Measurement
Conference (IMC), Taormina, Sicily, Italy, October 2004.
117
[27] Thomas Karagiannis, Konstantina Papagiannaki, and Michalis Faloutsos. Blinc:
Multilevel traffic classification in the dark. ACM SIGCOMM Computer Com-
munication Review, 35(4):229?240, October 2005.
[28] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin,
and Rina Panigrahy. Consistent hashing and random trees: Distributed caching
protocols for relieving hot spots on the world wide web. In ACM Symposium on
Theory of Computing, El Paso, Texas, USA, May 1997.
[29] Karthik Lakshminarayanan and Venkata N. Padmanabhan. Some findings on
the network performance of broadband hosts. In ACM/USENIX Internet Mea-
surement Conference (IMC), Miami, Florida, USA, October 2003.
[30] Yuchun Lee. Classifiers: Adaptive modules in pattern recognition systems. Mas-
ter?s thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts,
USA, May 1989.
[31] Dmitri Loguinov, Anuj Kumar, Vivek Rai, and Sai Ganesh. Graph-theoretic
analysis of structured peer-to-peer systems: Routing distances and fault re-
silience. In ACM SIGCOMM Conference, Karlsruhe, Germany, August 2003.
[32] Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, and Steven Lim. A
survey and comparison of peer-to-peer overlay network schemes. IEEE Commu-
nication Surveys and Tutorials, 7(2):72?93, April 2005.
[33] Klaus Mochalski. Personal communication, December 2006.
[34] Andrew W. Moore and Konstantina Papagiannaki. Toward the accurate iden-
tification of network applications. In Passive and Active Network Measure-
ment, volume 3431 of Lecture Notes in Computer Science, pages 41?54. Springer
Berlin/Heidelberg, March 2005.
[35] Andrew W. Moore and Denis Zuev. Internet traffic classification using bayesian
analysis techniques. In ACM SIGMETRICS International Conference on Mea-
surement and Modeling of Computer Systems, Banff, Alberta, Canada, June
2005.
[36] Motion Picture Association and L.E.K. The cost of movie piracy.
http://www.mpaa.org/researchStatistics.asp, May 2006.
[37] Moni Naor and Udi Wieder. Novel architectures for P2P applications: The
continuous-discrete approach. In ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA), San Diego, California, June 2003.
[38] National laboratory for applied network research ? passive measurement and
analysis. http://pma.nlanr.net, 2006. Thanks to the National Science Foun-
dation cooperative agreement nos. ANI-0129677 (2002) and ANI-9807479 (1998).
118
[39] University of Leipzig internet access link. Leipzig-I data set.
http://pma.nlanr.net/Special/leip1.html, November 2002.
[40] University of Memphis internet access link. Memphis data set.
http://pma.nlanr.net/PMA/Sites/MEM.html, March 2006.
[41] Philippe Olivier and Nabil Benameur. Flow level IP traffic characterization. In
International Teletraffic Congress (ITC), Salvador da Bahia, Brazil, December
2001.
[42] Andrew Parker. P2P in 2005. http://www.cachelogic.com, August 2005.
[43] Vern Paxson and Sally Floyd. Wide area traffic: The failure of poisson modeling.
IEEE/ACM Transactions on Networking, 3(3):226?244, June 1995.
[44] Sylvia Ratnasamy, Scott Shenker, and Ion Stoica. Routing algorithms for DHTs:
Some open questions. In International Workshop on Peer-to-Peer Systems
(IPTPS), Cambridge, Massachusetts, USA, March 2002.
[45] Stefan Saroiu, Krishna P. Gummadi, Richard J. Dunn, Steven D. Gribble, and
Henry M. Levy. An analysis of internet content delivery systems. In Sympo-
sium on Operating Systems Design and Implementation (ODSI), Boston, Mas-
sachusetts, USA, December 2002.
[46] Stefan Saroiu, P. Krishna Gummadi, and Steven D. Gribble. A measurement
study of peer-to-peer file sharing systems. In Conference on Multimedia Com-
puting and Networking (MMCN), San Jose, California, USA, January 2002.
[47] Subhabrata Sen, Oliver Spatscheck, and Dongmei Wang. Accurate, scalable in-
networkidentificationofP2Ptrafficusingapplicationsignatures. InInternational
Conference on World Wide Web, New York, New York, USA, May 2004.
[48] Cyril Soldani. Peer-to-Peer Behaviour Detection by TCP Flows Analysis. PhD
thesis, University of Li`ege, Li?ege, Wallonia, Belgium, May 2004.
[49] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakr-
ishnan. Chord: A scalable peer-to-peer lookup service for internet applications.
In ACM SIGCOMM Conference, San Diego, California, USA, August 2001.
[50] Daniel Stutzbach and Reza Rejaie. Understanding churn in peer-to-peer net-
works. In ACM SIGCOMM Internet Measurement Conference (IMC), Rio de
Janeriro, Brazil, October 2006.
[51] Kyoungwon Suh, Daniel R. Figueiredo, Jim Kurose, and Don Towsley. Char-
acterizing and detecting relayed traffic: A case study using Skype. In IEEE
Conference on Computer Communications (INFOCOM), Barcelona, Catalun-
yaa, Spain, April 2006.
119
[52] Anssi Tauriainen. A self-learning system for P2P traffic classification. Semi-
nar on Internetworking, at the Telecommunications Software and Multimedia
Laboratory, Helsinki University of Technology, Otaniemi, Espoo, April 2005.
[53] United States District Court; Northern District of California. A&M Records, et
al. v. Napster, Inc., March 2001.
[54] Xiaoming Wang, Yueping Zhang, Xiafeng Li, and Dmitri Loguinov. On zone-
balancing of peer-to-peer networks: Analysis of random node join. In ACM
SIGMETRICS Conference, New York, New York, USA, June 2004.
[55] Sebastian Zander, Nigel Williams, and Grenville Armitage. Internet archeology:
Estimating individual application trends in incomplete historic traffic traces. In
Passive and Active Measurement Workshop (PAM), Adelaide, Australia, March
2006.
[56] Yin Zhang and Vern Paxson. Detecting stepping stones. In USENIX Security
Symposium, San Diego, California, USA, June 2000.
120
Bibliography: Crystal steps
[57] W.K. Burton, N. Cabrera, and F.C. Frank. The growth of crystals and the
equilibrium structure of their surfaces. Philosophical Transactions of the Royal
Society of London, Series A, 243(866):299?358, June 1951.
[58] Russel E. Caflisch and Bo Li. Analysis of island dynamics in epitaxial growth of
thin films. Multiscale Modeling and Simulation, 1(1):150?171, January 2003.
[59] George F. Carrier, Max Krook, and Carl E. Pearson. Functions of a Complex
Variable: Theory and Technique. McGraw-Hill, Inc., New York, St. Louis, San
Francisco, Toronto, London, Sydney, 1966.
[60] D. J. Chadi. Stabilities of single-layer and bilayer steps on Si(001) surfaces.
Physical Review Letters, 59(15):1691?1694, October 1987.
[61] Pak-Wing Fok. Simulations of Axisymmetric Stepped Surfaces with a Facet. PhD
thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA,
June 2007.
[62] Pak-Wing Fok, Rodolfo R. Rosales, and Dionisios Margetis. Unification of step
bunching phenomena on vicinal surfaces. Physical Review B, 76(3):033408, July
2007.
[63] E.E. Gruber and W.W. Mullins. On the theory of anisotropy of crystalline surface
tension. Journal of Physics and Chemistry of Solids, 28(5):875?887, May 1967.
[64] G. Held, S. Uremovi?c, and D. Menzel. Rearrangement of stepped Ru(001) sur-
faces upon oxygen adsorption. Physical Review Letters, 331?333(2):1122?1128,
July 1995.
[65] Wei Hong, Ho Nyung Lee, Mina Yoon, Hans M. Christen, Douglas H. Lowndes,
Zhigang Suo, and Zhenyu Zhang. Persistent step-flow growth of strained films
on vicinal substrates. Physical Review Letters, 95(9):095501, August 2005.
[66] Navot Israeli and Daniel Kandel. Profile of a decaying crystalline cone. Physical
Review B, 60(8):13707?13717, August 1999.
[67] C. Jayaprakash, Craig Rottman, and W. F. Saam. Simple model for crystal
shapes: Step-step interactions and facet edges. Physical Review B, 30(11):6549?
6554, December 1984.
[68] Daniel Kandel and John D. Weeks. Step bunching as a chaotic pattern formation
process. Physical Review Letters, 69(26):3758?3761, December 1992.
[69] Kavli Institute of Nanoscience; Delft University of Technology. Research in the
quantum transport group. http://qt.tn.tudelft.nl/research/.
121
[70] A.V. Latyshev, A.L. Aseev, A.B. Krasilnikov, and S.I. Stenin. Transforma-
tions on clean Si(111) stepped surface during sublimation. Surface Science,
213(1):157?169, 1989.
[71] Da-Jiang Liu and John D. Weeks. Quantitative theory of current-induced step
bunching on Si(111). Physical Review B, 57(23):14891?14900, June 1998.
[72] Feng Liu, J. Tersoff, and M.G. Lagally. Self-organization of steps in growth of
strained films on vicinal substrates. Physical Review Letters, 89(6):1268?1271,
February 1998.
[73] Dionisios Margetis, Michael J. Aziz, and Howard A. Stone. Continuum approach
to profile scaling in nanostructure decay. Physical Review B, 71(16):165432, April
2005.
[74] C. Misbah and O. Pierre-Louis. Pulses and disorder in a continuum version of
step-bunching dynamics. Physical Review E, 53(5):R4318, May 1996.
[75] William W. Mullins. Flattening of a nearly plane solid surface due to capillarity.
Journal of Applied Physics, 30(1):77?83, January 1959.
[76] A. Rettori and J. Villain. Flattening of grooves on a crystal surface: A method
of investigation of surface roughness. Journal de Physique (Paris, France),
49(2):257?267, 1988.
[77] Masahide Sato and Makio Uwaha. Growth of step bunches formed by the drift
of adatoms. Surface Science, 442(2):318?328, November 1999.
[78] Massahide Sato and Makio Uwaha. Growth law of step bunches induced by the
Ehrlich-Schwoebel effect in growth. Surface Science, 493(1):494?498, November
2001.
[79] S. Stoyanov and V. Tonchev. Properties and dynamic interaction of step density
waves at a crystal surface during electromigration affected sublimation. Physical
Review B, 58(3):1590?1600, July 1998.
[80] Stoyan Stoyanov. Electromigration induced step bunching on Si surfaces: How
does it depend on the temperature and heating current direction? Japanese
Journal of Applied Physics, 30(1):1?6, January 1991.
[81] Brian S. Swartzentruber. Scanning tunneling microscope / Atom-tracking lab.
http://www.sandia.gov/surface science/stm/, August 2002.
[82] Katsumichi Yagi, Hiroki Minoda, and Masashi Degawa. Step bunching, step
wandering and faceting: Self-organization at Si surfaces. Surface Science Reports,
43(2?4):45?126, July 2001.
122