Search

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 79-81)., As more of the world moves towards online technologies, users are exposed to the increasing threat of cyberattacks. Studies show that most of these attacks begin with a phishing attack. Phishing emails and websites may compromise user credentials or download unsolicited and malicious software. This thesis presents the design and implementation of Quboid, a workstation for safer web interaction. Quboid helps users better defend against phishing attacks by providing several security mechanisms. The design of Quboid is based on the principle of isolation and restricted communication. The system enforces isolation by using virtualization to restrict browser instances to show dierent websites in separate virtual machines. For example, Quboid isolates a user's bank website and social networking website in separate VMs. It uses deep-packet inspection to implement a HTTP/HTTPS proxy filter to ensure virtual machines only communicate with specfic web servers. It also provides users with a secure interface and provides cues to help them recognize phishing attacks., by Amol M. Bhave., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 47-48)., In this thesis, I evaluated the theoretical and practical performance of a Geiger mode avalanche photodiode (GM-APD, or Geiger mode APD) array for use in optical communications systems. I designed and implemented a test pattern generator, capable of producing waveforms with OOK and PPM modulations at a variety of symbol rates and duty cycles. Using this pattern generator, I tested the receiver properties over a wide range of data rates and illumination levels, and was able to demonstrate the capability for error-free communications in both modulation formats, up to 78.8 Mbps at a sensitivity of 1.8 photons per bit for OOK, and 34.9 Mbps at 2 photons per bit for PPM., by Benjamin William Horkley., M. Eng.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Cataloged from PDF version of thesis., Includes bibliographical references (pages 109-114)., This dissertation addresses two challenges relating to in-memory storage systems. The first challenge is storing and retrieving data at a rate close to the capabilities of the underlying memory system, particularly in the face of parallel accesses from multiple cores. We present Masstree, a high performance in-memory key-value store that runs on a single multi-core server. Masstree is derived from a concurrent B+tree. It provides lock-free reads for good multi-core performance, which requires special care to avoid writes interfering with concurrent reads. To reduce time spent waiting for memory for workloads with long common key prefixes, Masstree arranges a set of B+trees into a Trie. Masstree uses software prefetch to further hide DRAM latency. Several optimizations improve concurrency. Masstree achieves millions of queries per second on a 16-core server, which is more than 30x as fast as MongoDB [6] or VoltDB [17]. The second challenge is replicating storage for fault-tolerance without being limited by slow writes to stable disk storage. Lazy VSR is a quorum-based replication protocol that is fast and can recover from simultaneous crashes of all the replicas as long as a majority revive with intact disks. The main idea is to acknowledge requests after recording them in memory, and to write updates to disk in the background, allowing large batched writes and thus good performance. A simultaneous crash of all replicas may leave the replicas with significantly different on-disk states; much of the design of Lazy VSR is concerned with reconciling these states efficiently during recovery. Lazy VSR's client-visible semantics are unusual in that the service may discard recent acknowledged updates if a majority of replicas crash. To demonstrate that clients can nevertheless make good use of Lazy VSR, we built a file system backend on it. Evaluation shows that Lazy VSR achieves much better performance than a version of itself with traditional group commit. Lazy VSR achiev, by Yandong Mao., Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Cataloged from PDF version of thesis., Includes bibliographical references (pages 109-114)., This dissertation addresses two challenges relating to in-memory storage systems. The first challenge is storing and retrieving data at a rate close to the capabilities of the underlying memory system, particularly in the face of parallel accesses from multiple cores. We present Masstree, a high performance in-memory key-value store that runs on a single multi-core server. Masstree is derived from a concurrent B+tree. It provides lock-free reads for good multi-core performance, which requires special care to avoid writes interfering with concurrent reads. To reduce time spent waiting for memory for workloads with long common key prefixes, Masstree arranges a set of B+trees into a Trie. Masstree uses software prefetch to further hide DRAM latency. Several optimizations improve concurrency. Masstree achieves millions of queries per second on a 16-core server, which is more than 30x as fast as MongoDB [6] or VoltDB [17]. The second challenge is replicating storage for fault-tolerance without being limited by slow writes to stable disk storage. Lazy VSR is a quorum-based replication protocol that is fast and can recover from simultaneous crashes of all the replicas as long as a majority revive with intact disks. The main idea is to acknowledge requests after recording them in memory, and to write updates to disk in the background, allowing large batched writes and thus good performance. A simultaneous crash of all replicas may leave the replicas with significantly different on-disk states; much of the design of Lazy VSR is concerned with reconciling these states efficiently during recovery. Lazy VSR's client-visible semantics are unusual in that the service may discard recent acknowledged updates if a majority of replicas crash. To demonstrate that clients can nevertheless make good use of Lazy VSR, we built a file system backend on it. Evaluation shows that Lazy VSR achieves much better performance than a version of itself with traditional group commit. Lazy VSR achiev, by Yandong Mao., Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 75-79)., Multicore main-memory databases only obtain parallel performance when transactions do not conflict. Conflicting transactions are executed one at a time in order to ensure that they have serializable effects. Sequential execution on contended data leaves cores idle and reduces throughput. In other parallel programming contexts---not serializable transactions--techniques have been developed that can reduce contention on shared variables using per-core state. This thesis asks the question, can these techniques apply to a general serializable database? This work introduces a new concurrency control technique, phase reconciliation, that uses per-core state to greatly reduce contention on popular database records for many important workloads. Phase reconciliation uses the idea of synchronized phases to amortize the cost of combining per-core data and to extract parallelism. Doppel, our phase reconciliation database, repeatedly cycles through joined and split phases. Joined phases use traditional concurrency control and allow any transaction to execute. When workload contention causes unnecessary sequential execution, Doppel switches to a split phase. During a split phase, commutative operations on popular records act on per-core state, and thus proceed in parallel on different cores. By explicitly using phases, phase reconciliation realizes two important performance benefits: First, it amortizes the potentially high costs of aggregating per-core state over many transactions. Second, it can dynamically split data or not based on observed contention, handling challenging, varying workloads. Doppel achieves higher performance because it parallelizes transactions on popular data that would be run sequentially by conventional concurrency control. Phase reconciliation helps most when there are many updates to a few popular database records. On an 80-core machine, its throughput is up to 38x higher than conventional concurrency control protocols on microbenchmarks, and up to 3x, by Neha Narula., Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 75-79)., Multicore main-memory databases only obtain parallel performance when transactions do not conflict. Conflicting transactions are executed one at a time in order to ensure that they have serializable effects. Sequential execution on contended data leaves cores idle and reduces throughput. In other parallel programming contexts---not serializable transactions--techniques have been developed that can reduce contention on shared variables using per-core state. This thesis asks the question, can these techniques apply to a general serializable database? This work introduces a new concurrency control technique, phase reconciliation, that uses per-core state to greatly reduce contention on popular database records for many important workloads. Phase reconciliation uses the idea of synchronized phases to amortize the cost of combining per-core data and to extract parallelism. Doppel, our phase reconciliation database, repeatedly cycles through joined and split phases. Joined phases use traditional concurrency control and allow any transaction to execute. When workload contention causes unnecessary sequential execution, Doppel switches to a split phase. During a split phase, commutative operations on popular records act on per-core state, and thus proceed in parallel on different cores. By explicitly using phases, phase reconciliation realizes two important performance benefits: First, it amortizes the potentially high costs of aggregating per-core state over many transactions. Second, it can dynamically split data or not based on observed contention, handling challenging, varying workloads. Doppel achieves higher performance because it parallelizes transactions on popular data that would be run sequentially by conventional concurrency control. Phase reconciliation helps most when there are many updates to a few popular database records. On an 80-core machine, its throughput is up to 38x higher than conventional concurrency control protocols on microbenchmarks, and up to 3x, by Neha Narula., Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 75-79)., Multicore main-memory databases only obtain parallel performance when transactions do not conflict. Conflicting transactions are executed one at a time in order to ensure that they have serializable effects. Sequential execution on contended data leaves cores idle and reduces throughput. In other parallel programming contexts---not serializable transactions--techniques have been developed that can reduce contention on shared variables using per-core state. This thesis asks the question, can these techniques apply to a general serializable database? This work introduces a new concurrency control technique, phase reconciliation, that uses per-core state to greatly reduce contention on popular database records for many important workloads. Phase reconciliation uses the idea of synchronized phases to amortize the cost of combining per-core data and to extract parallelism. Doppel, our phase reconciliation database, repeatedly cycles through joined and split phases. Joined phases use traditional concurrency control and allow any transaction to execute. When workload contention causes unnecessary sequential execution, Doppel switches to a split phase. During a split phase, commutative operations on popular records act on per-core state, and thus proceed in parallel on different cores. By explicitly using phases, phase reconciliation realizes two important performance benefits: First, it amortizes the potentially high costs of aggregating per-core state over many transactions. Second, it can dynamically split data or not based on observed contention, handling challenging, varying workloads. Doppel achieves higher performance because it parallelizes transactions on popular data that would be run sequentially by conventional concurrency control. Phase reconciliation helps most when there are many updates to a few popular database records. On an 80-core machine, its throughput is up to 38x higher than conventional concurrency control protocols on microbenchmarks, and up to 3x, by Neha Narula., Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Cataloged from PDF version of thesis., Includes bibliographical references (pages 109-114)., This dissertation addresses two challenges relating to in-memory storage systems. The first challenge is storing and retrieving data at a rate close to the capabilities of the underlying memory system, particularly in the face of parallel accesses from multiple cores. We present Masstree, a high performance in-memory key-value store that runs on a single multi-core server. Masstree is derived from a concurrent B+tree. It provides lock-free reads for good multi-core performance, which requires special care to avoid writes interfering with concurrent reads. To reduce time spent waiting for memory for workloads with long common key prefixes, Masstree arranges a set of B+trees into a Trie. Masstree uses software prefetch to further hide DRAM latency. Several optimizations improve concurrency. Masstree achieves millions of queries per second on a 16-core server, which is more than 30x as fast as MongoDB [6] or VoltDB [17]. The second challenge is replicating storage for fault-tolerance without being limited by slow writes to stable disk storage. Lazy VSR is a quorum-based replication protocol that is fast and can recover from simultaneous crashes of all the replicas as long as a majority revive with intact disks. The main idea is to acknowledge requests after recording them in memory, and to write updates to disk in the background, allowing large batched writes and thus good performance. A simultaneous crash of all replicas may leave the replicas with significantly different on-disk states; much of the design of Lazy VSR is concerned with reconciling these states efficiently during recovery. Lazy VSR's client-visible semantics are unusual in that the service may discard recent acknowledged updates if a majority of replicas crash. To demonstrate that clients can nevertheless make good use of Lazy VSR, we built a file system backend on it. Evaluation shows that Lazy VSR achieves much better performance than a version of itself with traditional group commit. Lazy VSR achiev, by Yandong Mao., Ph. D.

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002., Includes bibliographical references (leaves 54-56)., by Jacob A. Strauss., M.Eng.

Thesis (S.B. and M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000., Includes bibliographical references (leaves 67-69)., by David Matthew Simmons., S.B.and M.Eng.

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001., Includes bibliographical references (p. 53-55)., by Frank Dabek., M.Eng.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001., Includes bibliographical references (p. 64-66)., by Peilei Fan., S.M.

Thesis (S.B. and M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000., Includes bibliographical references (leaves 67-69)., by David Matthew Simmons., S.B.and M.Eng.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001., Includes bibliographical references (p. 64-66)., by Peilei Fan., S.M.

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002., Includes bibliographical references (leaves 54-56)., by Jacob A. Strauss., M.Eng.

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002., Includes bibliographical references (leaves 51-53)., by Michale J. Freedman., M.Eng.

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002., Includes bibliographical references (leaves 54-56)., by Jacob A. Strauss., M.Eng.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001., Includes bibliographical references (p. 64-66)., by Peilei Fan., S.M.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012., Cataloged from PDF version of thesis., Includes bibliographical references (p. 59-60)., This thesis describes an algorithm developed to aid in solving the problem of performance diagnosis, by automatically identifying the specific component in a multicomponent application system responsible for a performance problem. The algorithm monitors the system, collecting load and latency information from each component, searches the data for patterns indicative of performance saturation using statistical methods, and uses a machine learning classifier to interpret those results. The algorithm was tested with two test applications in several configurations, with different performance problems synthetically introduced. The algorithm correctly located these problems as much as 90% of the time, indicating that this is a good approach to the problem of automatic performance problem location. Also, the experimentation demonstrated that the algorithm can locate performance problems in environments different from those for which it was designed and from that on which it was trained., by Michael R. Stunes., M.Eng.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012., Cataloged from PDF version of thesis., Includes bibliographical references (p. 59-60)., This thesis describes an algorithm developed to aid in solving the problem of performance diagnosis, by automatically identifying the specific component in a multicomponent application system responsible for a performance problem. The algorithm monitors the system, collecting load and latency information from each component, searches the data for patterns indicative of performance saturation using statistical methods, and uses a machine learning classifier to interpret those results. The algorithm was tested with two test applications in several configurations, with different performance problems synthetically introduced. The algorithm correctly located these problems as much as 90% of the time, indicating that this is a good approach to the problem of automatic performance problem location. Also, the experimentation demonstrated that the algorithm can locate performance problems in environments different from those for which it was designed and from that on which it was trained., by Michael R. Stunes., M.Eng.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012., Cataloged from PDF version of thesis., Includes bibliographical references (p. 113-116)., Flooding in wireless mesh networks involves distributing some data from one node to rest of the nodes in the network. This dissertation proposes UFlood, a flooding protocol for wireless mesh networks that targets large file transfers, such as software updates, where achieving high throughput (minimizing the time to complete the flood to all nodes) and low airtime (lower the time each node spends in transmitting packets, and thus lower the impact on other wireless traffic) are both important. The central challenge in good flooding performance is the choice of senders for each transmission opportunity. At each time during a flood, some parts of the network will have received more data than others. The set of best sending nodes lies along the boundaries between these regions, and evolves with time in ways that are difficult to predict. UFlood's key new idea is a distributed heuristic to dynamically choose the senders likely to lead to all nodes receiving the flooded data in the least time. The mechanism takes into account which data nearby receivers already have as well as inter-node channel quality. The mechanism includes a novel bit-rate selection algorithm that trades off the speed of high bit-rates against the larger number of nodes likely to receive low bit-rates. Unusually, UFlood uses both random network coding to increase the usefulness of each transmission and detailed feedback about what data each receiver already has; the feedback is critical in deciding which node's coded transmission will have the most benefit to receivers. The required feedback is potentially voluminous, but UFlood includes novel techniques to reduce its cost. The dissertation concludes that careful choice of senders allows UFlood to achieve 150% higher throughput than MORE, a known high-throughput flooding protocol, using 65% less time transmitting. UFlood uses 54% lower airtime than MNP, an existing flooding protocol to minimize airtime, and achieves 300% higher throughput., by Jayashree Subramanian., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012., Cataloged from PDF version of thesis., Includes bibliographical references (p. 113-116)., Flooding in wireless mesh networks involves distributing some data from one node to rest of the nodes in the network. This dissertation proposes UFlood, a flooding protocol for wireless mesh networks that targets large file transfers, such as software updates, where achieving high throughput (minimizing the time to complete the flood to all nodes) and low airtime (lower the time each node spends in transmitting packets, and thus lower the impact on other wireless traffic) are both important. The central challenge in good flooding performance is the choice of senders for each transmission opportunity. At each time during a flood, some parts of the network will have received more data than others. The set of best sending nodes lies along the boundaries between these regions, and evolves with time in ways that are difficult to predict. UFlood's key new idea is a distributed heuristic to dynamically choose the senders likely to lead to all nodes receiving the flooded data in the least time. The mechanism takes into account which data nearby receivers already have as well as inter-node channel quality. The mechanism includes a novel bit-rate selection algorithm that trades off the speed of high bit-rates against the larger number of nodes likely to receive low bit-rates. Unusually, UFlood uses both random network coding to increase the usefulness of each transmission and detailed feedback about what data each receiver already has; the feedback is critical in deciding which node's coded transmission will have the most benefit to receivers. The required feedback is potentially voluminous, but UFlood includes novel techniques to reduce its cost. The dissertation concludes that careful choice of senders allows UFlood to achieve 150% higher throughput than MORE, a known high-throughput flooding protocol, using 65% less time transmitting. UFlood uses 54% lower airtime than MNP, an existing flooding protocol to minimize airtime, and achieves 300% higher throughput., by Jayashree Subramanian., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012., Cataloged from PDF version of thesis., Includes bibliographical references (p. 113-116)., Flooding in wireless mesh networks involves distributing some data from one node to rest of the nodes in the network. This dissertation proposes UFlood, a flooding protocol for wireless mesh networks that targets large file transfers, such as software updates, where achieving high throughput (minimizing the time to complete the flood to all nodes) and low airtime (lower the time each node spends in transmitting packets, and thus lower the impact on other wireless traffic) are both important. The central challenge in good flooding performance is the choice of senders for each transmission opportunity. At each time during a flood, some parts of the network will have received more data than others. The set of best sending nodes lies along the boundaries between these regions, and evolves with time in ways that are difficult to predict. UFlood's key new idea is a distributed heuristic to dynamically choose the senders likely to lead to all nodes receiving the flooded data in the least time. The mechanism takes into account which data nearby receivers already have as well as inter-node channel quality. The mechanism includes a novel bit-rate selection algorithm that trades off the speed of high bit-rates against the larger number of nodes likely to receive low bit-rates. Unusually, UFlood uses both random network coding to increase the usefulness of each transmission and detailed feedback about what data each receiver already has; the feedback is critical in deciding which node's coded transmission will have the most benefit to receivers. The required feedback is potentially voluminous, but UFlood includes novel techniques to reduce its cost. The dissertation concludes that careful choice of senders allows UFlood to achieve 150% higher throughput than MORE, a known high-throughput flooding protocol, using 65% less time transmitting. UFlood uses 54% lower airtime than MNP, an existing flooding protocol to minimize airtime, and achieves 300% higher throughput., by Jayashree Subramanian., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012., Cataloged from PDF version of thesis., Includes bibliographical references (p. 113-116)., Flooding in wireless mesh networks involves distributing some data from one node to rest of the nodes in the network. This dissertation proposes UFlood, a flooding protocol for wireless mesh networks that targets large file transfers, such as software updates, where achieving high throughput (minimizing the time to complete the flood to all nodes) and low airtime (lower the time each node spends in transmitting packets, and thus lower the impact on other wireless traffic) are both important. The central challenge in good flooding performance is the choice of senders for each transmission opportunity. At each time during a flood, some parts of the network will have received more data than others. The set of best sending nodes lies along the boundaries between these regions, and evolves with time in ways that are difficult to predict. UFlood's key new idea is a distributed heuristic to dynamically choose the senders likely to lead to all nodes receiving the flooded data in the least time. The mechanism takes into account which data nearby receivers already have as well as inter-node channel quality. The mechanism includes a novel bit-rate selection algorithm that trades off the speed of high bit-rates against the larger number of nodes likely to receive low bit-rates. Unusually, UFlood uses both random network coding to increase the usefulness of each transmission and detailed feedback about what data each receiver already has; the feedback is critical in deciding which node's coded transmission will have the most benefit to receivers. The required feedback is potentially voluminous, but UFlood includes novel techniques to reduce its cost. The dissertation concludes that careful choice of senders allows UFlood to achieve 150% higher throughput than MORE, a known high-throughput flooding protocol, using 65% less time transmitting. UFlood uses 54% lower airtime than MNP, an existing flooding protocol to minimize airtime, and achieves 300% higher throughput., by Jayashree Subramanian., Ph.D.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student submitted PDF version of thesis., Includes bibliographical references (p. 61-62)., As storage capacity requirements grow, storage systems are becoming distributed, and that distribution poses a challenge for space savings processes. In this thesis, I design and implement a mechanism for storing only a single instance of duplicated data within a distributed storage system which selectively performs deduplication across each of the independent computers, known as nodes, used for storage. This involves analyzing the contents of each node for objects with characteristics more likely to have duplicates elsewhere, particularly using duplication within a node as the indicative property - an object duplicated many times in a dataset will likely be duplicated at least once in some node. An inter-node system is responsible for efficiently collecting and distributing the information of these potential duplicates. A test implementation was built and run on several data sets characteristic of common storage workloads where deduplication is important, while distributing across 128 nodes. The efficiency of this implementation was analyzed and compared against the savings when distributed across 128 nodes with deduplication performed only between duplicate objects within each node, without inter-node deduplication. The inter-node deduplication was found to increase the space saved by a factor of four to six times. This represented in one case, a file storage server, only a quarter of potential savings due to the majority of potential savings being in files with only a few duplicates. This left a low probability of locating duplication within a single node. However in another case, a collection of over 100 virtual machine images, nearly all potential duplicates were found due to the high number of duplicates for each object, providing an example of where this inter-node mechanism can be most useful., by Matthew Goldstein., M.Eng.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Cataloged from PDF version of thesis., Includes bibliographical references (p. 83-87)., Users increasingly store data collections such as digital photographs on multiple personal devices, each of which typically presents the user with a storage management interface isolated from the contents of all other devices. The result is that collections easily become disorganized and drift out of sync. This thesis presents Eyo, a novel personal storage system that provides device transparency: a user can think in terms of "file X", rather than "file X on device Y", and will see the same set of files on all personal devices. Eyo allows a user to view and manage the entire collection of objects from any of their devices, even from disconnected devices and devices with too little storage to hold all the object content. Eyo separates metadata (application-specific attributes of objects) from the content of objects, allowing even storage-limited devices to store all metadata and thus provide device transparency. Fully replicated metadata allows any set of Eyo devices to efficiently synchronize updates. Applications can specify flexible placement rules to guide Eyo's partial replication of object contents across devices. Eyo's application interface provides first-class access to object version history. If multiple disconnected devices update an object concurrently, Eyo preserves each resulting divergent version of that object. Applications can then examine the history and either coalesce the conflicting versions without user direction, or incorporate these versions naturally into their existing user interfaces. Experiments using Eyo for storage in several example applications-media players, a photo editor, podcast manager, and an email interface-show that device transparency can be had with minor application changes, and within the storage and bandwidth capabilities of typical portable devices., by Jacob Alo Strauss., Ph.D.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student submitted PDF version of thesis., Includes bibliographical references (p. 61-62)., As storage capacity requirements grow, storage systems are becoming distributed, and that distribution poses a challenge for space savings processes. In this thesis, I design and implement a mechanism for storing only a single instance of duplicated data within a distributed storage system which selectively performs deduplication across each of the independent computers, known as nodes, used for storage. This involves analyzing the contents of each node for objects with characteristics more likely to have duplicates elsewhere, particularly using duplication within a node as the indicative property - an object duplicated many times in a dataset will likely be duplicated at least once in some node. An inter-node system is responsible for efficiently collecting and distributing the information of these potential duplicates. A test implementation was built and run on several data sets characteristic of common storage workloads where deduplication is important, while distributing across 128 nodes. The efficiency of this implementation was analyzed and compared against the savings when distributed across 128 nodes with deduplication performed only between duplicate objects within each node, without inter-node deduplication. The inter-node deduplication was found to increase the space saved by a factor of four to six times. This represented in one case, a file storage server, only a quarter of potential savings due to the majority of potential savings being in files with only a few duplicates. This left a low probability of locating duplication within a single node. However in another case, a collection of over 100 virtual machine images, nearly all potential duplicates were found due to the high number of duplicates for each object, providing an example of where this inter-node mechanism can be most useful., by Matthew Goldstein., M.Eng.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student submitted PDF version of thesis., Includes bibliographical references (p. 61-62)., As storage capacity requirements grow, storage systems are becoming distributed, and that distribution poses a challenge for space savings processes. In this thesis, I design and implement a mechanism for storing only a single instance of duplicated data within a distributed storage system which selectively performs deduplication across each of the independent computers, known as nodes, used for storage. This involves analyzing the contents of each node for objects with characteristics more likely to have duplicates elsewhere, particularly using duplication within a node as the indicative property - an object duplicated many times in a dataset will likely be duplicated at least once in some node. An inter-node system is responsible for efficiently collecting and distributing the information of these potential duplicates. A test implementation was built and run on several data sets characteristic of common storage workloads where deduplication is important, while distributing across 128 nodes. The efficiency of this implementation was analyzed and compared against the savings when distributed across 128 nodes with deduplication performed only between duplicate objects within each node, without inter-node deduplication. The inter-node deduplication was found to increase the space saved by a factor of four to six times. This represented in one case, a file storage server, only a quarter of potential savings due to the majority of potential savings being in files with only a few duplicates. This left a low probability of locating duplication within a single node. However in another case, a collection of over 100 virtual machine images, nearly all potential duplicates were found due to the high number of duplicates for each object, providing an example of where this inter-node mechanism can be most useful., by Matthew Goldstein., M.Eng.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Cataloged from PDF version of thesis., Includes bibliographical references (p. 83-87)., Users increasingly store data collections such as digital photographs on multiple personal devices, each of which typically presents the user with a storage management interface isolated from the contents of all other devices. The result is that collections easily become disorganized and drift out of sync. This thesis presents Eyo, a novel personal storage system that provides device transparency: a user can think in terms of "file X", rather than "file X on device Y", and will see the same set of files on all personal devices. Eyo allows a user to view and manage the entire collection of objects from any of their devices, even from disconnected devices and devices with too little storage to hold all the object content. Eyo separates metadata (application-specific attributes of objects) from the content of objects, allowing even storage-limited devices to store all metadata and thus provide device transparency. Fully replicated metadata allows any set of Eyo devices to efficiently synchronize updates. Applications can specify flexible placement rules to guide Eyo's partial replication of object contents across devices. Eyo's application interface provides first-class access to object version history. If multiple disconnected devices update an object concurrently, Eyo preserves each resulting divergent version of that object. Applications can then examine the history and either coalesce the conflicting versions without user direction, or incorporate these versions naturally into their existing user interfaces. Experiments using Eyo for storage in several example applications-media players, a photo editor, podcast manager, and an email interface-show that device transparency can be had with minor application changes, and within the storage and bandwidth capabilities of typical portable devices., by Jacob Alo Strauss., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Cataloged from PDF version of thesis., Includes bibliographical references (p. 83-87)., Users increasingly store data collections such as digital photographs on multiple personal devices, each of which typically presents the user with a storage management interface isolated from the contents of all other devices. The result is that collections easily become disorganized and drift out of sync. This thesis presents Eyo, a novel personal storage system that provides device transparency: a user can think in terms of "file X", rather than "file X on device Y", and will see the same set of files on all personal devices. Eyo allows a user to view and manage the entire collection of objects from any of their devices, even from disconnected devices and devices with too little storage to hold all the object content. Eyo separates metadata (application-specific attributes of objects) from the content of objects, allowing even storage-limited devices to store all metadata and thus provide device transparency. Fully replicated metadata allows any set of Eyo devices to efficiently synchronize updates. Applications can specify flexible placement rules to guide Eyo's partial replication of object contents across devices. Eyo's application interface provides first-class access to object version history. If multiple disconnected devices update an object concurrently, Eyo preserves each resulting divergent version of that object. Applications can then examine the history and either coalesce the conflicting versions without user direction, or incorporate these versions naturally into their existing user interfaces. Experiments using Eyo for storage in several example applications-media players, a photo editor, podcast manager, and an email interface-show that device transparency can be had with minor application changes, and within the storage and bandwidth capabilities of typical portable devices., by Jacob Alo Strauss., Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Cataloged from PDF version of thesis., Includes bibliographical references (p. 47-48)., Effective use of CPU data caches is critical to good performance, but poor cache use patterns are often hard to spot using existing execution profiling tools. Typical profilers attribute costs to specific code locations. The costs due to frequent cache misses on a given piece of data, however, may be spread over instructions throughout the application. The resulting individually small costs at a large number of instructions can easily appear insignificant in a code profiler's output. DProf helps programmers understand cache miss costs by attributing misses to data types instead of code. Associating cache misses with data helps programmers locate data structures that experience misses in many places in the application's code. DProf introduces a number of new views of cache miss data, including a data profile, which reports the data types with the most cache misses, and a data flow graph, which summarizes how objects of a given type are accessed throughout their lifetime, and which accesses incur expensive cross-CPU cache loads. We present two case studies of using DProf to find and fix cache performance bottlenecks in Linux. The improvements provide a 16-57% throughput improvement on a range of memcached and Apache workloads., by Aleksey Pesterev., S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009., Cataloged from PDF version of thesis., Includes bibliographical references (p. 91-98)., This dissertation describes two systems, RESIN and BFLow, whose goal is to help Web developers build more secure Web sites. RESIN and BFLOW use data flow management to help reduce the security risks of using buggy or malicious code. RESIN provides programmers with language-level mechanisms to track and manage the flow of data within the server. These mechanisms make it easy for programmers to catch server-side data flow bugs that result in security vulnerabilities, and prevent these bugs from being exploited. BFLow is a system that adds information flow control, a restrictive form of data flow management, both to the Web browser and to the interface between a browser and a server. BFLOW makes it possible for a Web site to combine confidential data with untrusted JavaScript in its Web pages, without risking leaks of that data. This work makes a number of contributions. RESIN introduces the idea of a data flow assertion and demonstrates how to build them using three language-level mechanisms, policy objects, data tracking, and filter objects. We built prototype implementations of RESIN in both the PHP and Python runtimes. We adapt seven real off-the-shelf applications and implement 11 different security policies in RESIN which thwart at least 27 real security vulnerabilities. BFLow introduces an information flow control model that fits the JavaScript communication mechanisms, and a system that maps that model to JavaScript's existing isolation system., (cont.) Together, these techniques allow untrusted JavaScript to read, compute with, and display confidential data without the risk of leaking that data, yet requires only minor changes to existing software. We built a prototype of the BFLow system and three different applications including a social networking application, a novel shared-data Web platform, and BFlogger, a third-party JavaScript platform similar to that of Blogger.com. We ported several untrusted JavaScript extensions from Blogger.com to BFlogger, and show that the extensions cannot leak data as they can in Blogger.com., by Alexander Siumann Yip., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009., Cataloged from PDF version of thesis., Includes bibliographical references (p. 91-98)., This dissertation describes two systems, RESIN and BFLow, whose goal is to help Web developers build more secure Web sites. RESIN and BFLOW use data flow management to help reduce the security risks of using buggy or malicious code. RESIN provides programmers with language-level mechanisms to track and manage the flow of data within the server. These mechanisms make it easy for programmers to catch server-side data flow bugs that result in security vulnerabilities, and prevent these bugs from being exploited. BFLow is a system that adds information flow control, a restrictive form of data flow management, both to the Web browser and to the interface between a browser and a server. BFLOW makes it possible for a Web site to combine confidential data with untrusted JavaScript in its Web pages, without risking leaks of that data. This work makes a number of contributions. RESIN introduces the idea of a data flow assertion and demonstrates how to build them using three language-level mechanisms, policy objects, data tracking, and filter objects. We built prototype implementations of RESIN in both the PHP and Python runtimes. We adapt seven real off-the-shelf applications and implement 11 different security policies in RESIN which thwart at least 27 real security vulnerabilities. BFLow introduces an information flow control model that fits the JavaScript communication mechanisms, and a system that maps that model to JavaScript's existing isolation system., (cont.) Together, these techniques allow untrusted JavaScript to read, compute with, and display confidential data without the risk of leaking that data, yet requires only minor changes to existing software. We built a prototype of the BFLow system and three different applications including a social networking application, a novel shared-data Web platform, and BFlogger, a third-party JavaScript platform similar to that of Blogger.com. We ported several untrusted JavaScript extensions from Blogger.com to BFlogger, and show that the extensions cannot leak data as they can in Blogger.com., by Alexander Siumann Yip., Ph.D.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009., Includes bibliographical references (p. 95)., The goal of this project is to enhance performance of virtual machines and simplify the design of the virtual machine monitor by running 32-bit x86 operating systems in x86-64 mode. In order to do so, 32-bit operating system binary code is translated into x86-64 binary code via "widening binary translation"; x86-32 code is "widened" into x86-64 code. The main challenge of widening BT is emulating x86-32 legacy segmentation in x86-64 mode. Widening BT's solution is to emulate segmentation in software. Most of the overhead for software segmentation can be optimized away. The main contribution of widening BT is simplification of the VMM, which reduces the human cost of maintaining a complicated VMM. Widening BT also improves performance of 32-bit guest operating systems running in virtual machines and demonstrates the independence of virtual machines from physical hardware. With widening BT, legacy hardware mechanisms like segmentation can be dropped. Therefore widening BT reduces hardware's burden of backwards-compatibility, encouraging software/hardware co-design., by Yu-hsin Chen., M.Eng.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008., Includes bibliographical references (p. 91-96)., This thesis presents a virtual disk cluster called END, the Expandable Network Disk. END aggregates storage on a cluster of servers into a single virtual disk. END's main goals are to offer good performance during normal operation, and efficiently handle changes in the cluster membership. END achieves these goals using a two-layer design, in which storage "bricks," servers that consist of CPU, memory, and hard disks, hold two kinds of information. The lower layer stores replicated immutable chunks of data, each indexed by a unique key. The upper layer maps each block address to the key of its current data chunk; each mapping is held on two bricks using primary-backup replication. This separation allows END flexibility in where it stores chunks and thus efficiency: it writes new chunks to bricks chosen for speed; it moves only address mappings (not data) when bricks fail and recover, which results in fast recovery; it fully replicates new writes during temporary brick failures; and it uses chunks on a recovered brick without risk of staleness. The END prototype's write throughput on a cluster of 16 PC-based bricks is 150 megabytes/s with 2x replication. END continues after a single brick failure, re-incorporates a rebooting brick, and expands to include a new brick after a few seconds of reduced performance during each change. The results show that END's two-layer design maintains good performance, resumes operation quickly after changes in the cluster, and maintains full replication of new writes even during a brick failure., by Athicha Muthitacharoen., Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Includes bibliographical references., Carrier sense, or clear channel assessment (CCA), is widely used in wireless medium access control (MAC) protocols as the means to arbitrate access and regulate concurrency, striking a balance between interference protection and spatial reuse. Criticized widely in the literature, carrier sense has been subject to many replacement attempts with sophisticated and complex alternatives, yet it remains extremely popular. Is the search for a superior alternative justified? In this thesis, we develop a physically motivated theoretical model for average case carrier sense behavior in the two-sender case, based upon radio propagation theory and Shannon capacity. We argue from our model that common notions about carrier sense, such as the hidden and exposed terminal phenomena, are inherently misleading in the context of adaptive bitrate, casting in black and white terms effects that often cause only mild reduction in throughput. The frequency of severe misbehavior is low. We also demonstrate that it is possible to choose a fixed sense threshold which performs well across a wide range of scenarios, in large part due to the role of the noise floor. The noise floor has a significant effect on fairness as well. Using our model, we show that, when implemented well, average-case carrier sense performance is surprisingly close to optimal. We conclude with experimental results from our indoor 802.11 testbed, which corroborate these claims., by Micah, Z. Brodsky., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Includes bibliographical references., Carrier sense, or clear channel assessment (CCA), is widely used in wireless medium access control (MAC) protocols as the means to arbitrate access and regulate concurrency, striking a balance between interference protection and spatial reuse. Criticized widely in the literature, carrier sense has been subject to many replacement attempts with sophisticated and complex alternatives, yet it remains extremely popular. Is the search for a superior alternative justified? In this thesis, we develop a physically motivated theoretical model for average case carrier sense behavior in the two-sender case, based upon radio propagation theory and Shannon capacity. We argue from our model that common notions about carrier sense, such as the hidden and exposed terminal phenomena, are inherently misleading in the context of adaptive bitrate, casting in black and white terms effects that often cause only mild reduction in throughput. The frequency of severe misbehavior is low. We also demonstrate that it is possible to choose a fixed sense threshold which performs well across a wide range of scenarios, in large part due to the role of the noise floor. The noise floor has a significant effect on fairness as well. Using our model, we show that, when implemented well, average-case carrier sense performance is surprisingly close to optimal. We conclude with experimental results from our indoor 802.11 testbed, which corroborate these claims., by Micah, Z. Brodsky., S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008., Includes bibliographical references (p. 83-90)., Distributed hash tables (DHTs) have been proposed as a generic, robust storage infrastructure for simplifying the construction of large-scale, wide-area applications. For example, UsenetDHT is a new design for Usenet News developed in this thesis that uses a DHT to cooperatively deliver Usenet articles: the DHT allows a set of N hosts to share storage of Usenet articles, reducing their combined storage requirements by a factor of O(N). Usenet generates a continuous stream of writes that exceeds 1 Tbyte/day in volume, comprising over ten million writes. Supporting this and the associated read workload requires a DHT engineered for durability and efficiency. Recovering from network and machine failures efficiently poses a challenge for DHT replication maintenance algorithms that provide durability. To avoid losing the last replica, replica maintenance must create additional replicas when failures are detected. However, creating replicas after every failure stresses network and storage resources unnecessarily. Tracking the location of every replica of every object would allow a replica maintenance algorithm to create replicas only when necessary, but when storing terabytes of data, such tracking is difficult to perform accurately and efficiently. This thesis describes a new algorithm, Passing Tone, that maintains durability efficiently, in a completely decentralized manner, despite transient and permanent failures. Passing Tone nodes make replication decisions with just basic DHT routing state, without maintaining state about the number or location of extant replicas and without responding to every transient failure with a new replica. Passing Tone is implemented in a revised version of DHash, optimized for both disk and network performance., (cont.) A sample 12 node deployment of Passing Tone and UsenetDHT supports a partial Usenet feed of 2.5 Mbyte/s (processing over 80 Tbyte of data per year), while providing 30 Mbyte/s of read throughput, limited currently by disk seeks. This deployment is the first public DHT to store terabytes of data. These results indicate that DHT-based designs can successfully simplify the construction of large-scale, wide-area systems., by Emil Sit., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008., Includes bibliographical references (p. 91-96)., This thesis presents a virtual disk cluster called END, the Expandable Network Disk. END aggregates storage on a cluster of servers into a single virtual disk. END's main goals are to offer good performance during normal operation, and efficiently handle changes in the cluster membership. END achieves these goals using a two-layer design, in which storage "bricks," servers that consist of CPU, memory, and hard disks, hold two kinds of information. The lower layer stores replicated immutable chunks of data, each indexed by a unique key. The upper layer maps each block address to the key of its current data chunk; each mapping is held on two bricks using primary-backup replication. This separation allows END flexibility in where it stores chunks and thus efficiency: it writes new chunks to bricks chosen for speed; it moves only address mappings (not data) when bricks fail and recover, which results in fast recovery; it fully replicates new writes during temporary brick failures; and it uses chunks on a recovered brick without risk of staleness. The END prototype's write throughput on a cluster of 16 PC-based bricks is 150 megabytes/s with 2x replication. END continues after a single brick failure, re-incorporates a rebooting brick, and expands to include a new brick after a few seconds of reduced performance during each change. The results show that END's two-layer design maintains good performance, resumes operation quickly after changes in the cluster, and maintains full replication of new writes even during a brick failure., by Athicha Muthitacharoen., Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Includes bibliographical references., Carrier sense, or clear channel assessment (CCA), is widely used in wireless medium access control (MAC) protocols as the means to arbitrate access and regulate concurrency, striking a balance between interference protection and spatial reuse. Criticized widely in the literature, carrier sense has been subject to many replacement attempts with sophisticated and complex alternatives, yet it remains extremely popular. Is the search for a superior alternative justified? In this thesis, we develop a physically motivated theoretical model for average case carrier sense behavior in the two-sender case, based upon radio propagation theory and Shannon capacity. We argue from our model that common notions about carrier sense, such as the hidden and exposed terminal phenomena, are inherently misleading in the context of adaptive bitrate, casting in black and white terms effects that often cause only mild reduction in throughput. The frequency of severe misbehavior is low. We also demonstrate that it is possible to choose a fixed sense threshold which performs well across a wide range of scenarios, in large part due to the role of the noise floor. The noise floor has a significant effect on fairness as well. Using our model, we show that, when implemented well, average-case carrier sense performance is surprisingly close to optimal. We conclude with experimental results from our indoor 802.11 testbed, which corroborate these claims., by Micah, Z. Brodsky., S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008., Includes bibliographical references (p. 91-96)., This thesis presents a virtual disk cluster called END, the Expandable Network Disk. END aggregates storage on a cluster of servers into a single virtual disk. END's main goals are to offer good performance during normal operation, and efficiently handle changes in the cluster membership. END achieves these goals using a two-layer design, in which storage "bricks," servers that consist of CPU, memory, and hard disks, hold two kinds of information. The lower layer stores replicated immutable chunks of data, each indexed by a unique key. The upper layer maps each block address to the key of its current data chunk; each mapping is held on two bricks using primary-backup replication. This separation allows END flexibility in where it stores chunks and thus efficiency: it writes new chunks to bricks chosen for speed; it moves only address mappings (not data) when bricks fail and recover, which results in fast recovery; it fully replicates new writes during temporary brick failures; and it uses chunks on a recovered brick without risk of staleness. The END prototype's write throughput on a cluster of 16 PC-based bricks is 150 megabytes/s with 2x replication. END continues after a single brick failure, re-incorporates a rebooting brick, and expands to include a new brick after a few seconds of reduced performance during each change. The results show that END's two-layer design maintains good performance, resumes operation quickly after changes in the cluster, and maintains full replication of new writes even during a brick failure., by Athicha Muthitacharoen., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008., Includes bibliographical references (p. 83-90)., Distributed hash tables (DHTs) have been proposed as a generic, robust storage infrastructure for simplifying the construction of large-scale, wide-area applications. For example, UsenetDHT is a new design for Usenet News developed in this thesis that uses a DHT to cooperatively deliver Usenet articles: the DHT allows a set of N hosts to share storage of Usenet articles, reducing their combined storage requirements by a factor of O(N). Usenet generates a continuous stream of writes that exceeds 1 Tbyte/day in volume, comprising over ten million writes. Supporting this and the associated read workload requires a DHT engineered for durability and efficiency. Recovering from network and machine failures efficiently poses a challenge for DHT replication maintenance algorithms that provide durability. To avoid losing the last replica, replica maintenance must create additional replicas when failures are detected. However, creating replicas after every failure stresses network and storage resources unnecessarily. Tracking the location of every replica of every object would allow a replica maintenance algorithm to create replicas only when necessary, but when storing terabytes of data, such tracking is difficult to perform accurately and efficiently. This thesis describes a new algorithm, Passing Tone, that maintains durability efficiently, in a completely decentralized manner, despite transient and permanent failures. Passing Tone nodes make replication decisions with just basic DHT routing state, without maintaining state about the number or location of extant replicas and without responding to every transient failure with a new replica. Passing Tone is implemented in a revised version of DHash, optimized for both disk and network performance., (cont.) A sample 12 node deployment of Passing Tone and UsenetDHT supports a partial Usenet feed of 2.5 Mbyte/s (processing over 80 Tbyte of data per year), while providing 30 Mbyte/s of read throughput, limited currently by disk seeks. This deployment is the first public DHT to store terabytes of data. These results indicate that DHT-based designs can successfully simplify the construction of large-scale, wide-area systems., by Emil Sit., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2006., Includes bibliographical references (p. 123-132) and index., DHash is a new system that harnesses the storage and network resources of computers distributed across the Internet by providing a wide-area storage service, DHash. DHash frees applications from re-implementing mechanisms common to any system that stores data on a collection of machines: it maintains a mapping of objects to servers, replicates data for durability, and balances load across participating servers. Applications access data stored in DHash through a familiar hash-table interface: put stores data in the system under a key; get retrieves the data. DHash has proven useful to a number of application builders and has been used to build a content-distribution system [31], a Usenet replacement [115], and new Internet naming architectures [130, 129]. These applications demand low-latency, high-throughput access to durable data. Meeting this demand is challenging in the wide-area environment. The geographic distribution of nodes means that latencies between nodes are likely to be high: to provide a low-latency get operation the system must locate a nearby copy of the data without traversing high-latency links., (cont.) Also, wide-area network links are likely to be less reliable and have lower capacities than local-area network links: to provide durability efficiently the system must minimize the number of copies of data items it sends over these limited capacity links in response to node failure. This thesis describes the design and implementation of the DHash distributed hash table and presents algorithms and techniques that address these challenges. DHash provides low-latency operations by using a synthetic network coordinate system (Vivaldi) to find nearby copies of data without sending messages over high-latency links. A network transport (STP), designed for applications that contact a large number of nodes, lets DHash provide high throughput by striping a download across many servers without causing high packet loss or exhausting local resources. Sostenuto, a data maintenance algorithm, lets DHash maintain data durability while minimizing the number of copies of data that the system sends over limited-capacity links., by Frank Dabek., Ph.D.

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006., Includes bibliographical references (p. 75-78)., This thesis presents the design and implementation of a port of the Asbestos operating system to the ARM processor. The port to the ARM allows Asbestos to run on mobile devices such as cell phones and personal digital assistants. These mobile, wireless-enabled devices are at risk for data attacks because they store private data but often roam in public networks. The Asbestos operating system is designed to prevent disclosure of such data. The port includes a file system and a network driver, which together enable future development of Asbestos applications on the ARM platform. This thesis evaluates the port with a performance comparison between Asbestos running on an HP iPAQ hand held computer and the original x86 Asbestos., by Martijn Stevenson., M.Eng.

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002., Includes bibliographical references (p. 51-53)., This thesis presents NATRON, a system in which an overlay network of nodes cooperates to improve unicast routing to non-participating hosts. Previous overlay systems have used overlay routing to improve communication between participating hosts; they were unable to exploit overlay routing to non-participating hosts. NATRON uses a combination of IP tunneling and network address translation to allow members of the overlay to communicate with hosts outside the overlay network via other overlay members. In order to estimate the potential performance improvement a system like NATRON might provide, we performed an exhaustive test on a multi-site Internet testbed. Our results show that a system that always guesses the best intermediate node could reduce the average HTTP transfer time by 18% and reduce the number of downloads lasting longer than 30 seconds by 16%. We implemented a working NATRON and a heuristic for choosing intermediate overlay nodes, but we find that our heuristic can only exploit 22% of the potential performance gains. We conclude that overlay routing to oblivious hosts has good potential for performance enhancement but further work is needed to develop a path choice heuristic., by Alexander Siumann Yip., M.Eng.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005., Includes bibliographical references (p. 49-50)., This thesis evaluates bit-rate selection techniques to maximize throughput over wireless links that are capable of multiple bit-rates. The key challenges in bit-rate selection are determining which bit-rate provides the most throughput and knowing when to switch to another bit-rate that would provide more throughput. This thesis presents the SampleRate bit-rate selection algorithm. SampleRate sends most data packets at the bit-rate it believes will provide the highest throughput. SampleRate periodically sends a data packet at some other bit-rate in order to update a record of that bit-rate's loss rate. SampleRate switches to a different bit-rate if the throughput estimate based on the other bit-rate's recorded loss rate is higher than the current bit-rate's throughput. Measuring the loss rate of each supported bit-rate would be inefficient because sending packets at lower bit-rates could waste transmission time, and because successive unicast losses are time-consuming for bit-rates that do not work. SampleRate addresses this problem by only sampling at bit-rates whose lossless throughput is better than the current bit-rate's throughput. SampleRate also stops probing at a bit-rate if it experiences several successive losses. This thesis presents measurements from indoor and outdoor wireless networks that demonstrate that SampleRate performs as well or better than other bit-rate selection algorithms., (cont.) SampleRate performs better than other algorithms on links where all bit-rates suffer from significant loss., by John C. Bicket., S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004., Includes bibliographical references (leaves 99-102)., This thesis describes Pastwatch, a distributed version control system. Pastwatch maintains versions of users' shared files. Each version is immutable: to make changes, a user checks out a version onto the user's computer, edits the files locally, then commits the changes to create a new version. The motivation behind Pastwatch is to support wide-area read/write file sharing. An example of this type of sharing is when loosely affiliated programmers from different parts of the world collaborate to work on open-source software projects. To support such users, Pastwatch offers three properties. First, it allows users who travel frequently or whose network connections fail from time to time to access historical versions of the shared files or make new versions while disconnected. Second, Pastwatch makes the current and historical versions of the shared files highly available. For example, even when their office building experiences a power failure, users can still create new versions and retrieve other users' changes from other locations. Supporting disconnected operation is not adequate by itself in these cases; users also want to see others' changes. Third, Pastwatch avoids using dedicated servers. Running a dedicated server requires high administrative costs, expertise, and expensive equipment. Pastwatch achieves its goals using two interacting approaches. First, it maintains a local branch tree of versions on each user's computer. A user can check out versions from the local tree and commit changes into the local tree. Second, Pastwatch uses a shared branch tree in a DHT to publish users' new versions. It contacts the tree to keep a user's local branch tree up-to-date., by Benjie Chen., Ph.D.

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, June 2002., "May 2002.", Includes bibliographical references (p. 63-64)., In this thesis, we present the design and implementation of Herodotus, a peer-to-peer web archival system. Like the Wayback Machine, a website that currently offers a web archive, Herodotus periodically crawls the world wide web and stores copies of all downloaded web content. Unlike the Wayback Machine, Herodotus does not rely on a centralized server farm. Instead, many individual nodes spread out across the Internet collaboratively perform the task of crawling and storing the content. This allows a large group of people to contribute idle computer resources to jointly achieve the goal of creating an Internet archive. Herodotus uses replication to ensure the persistence of data as nodes join and leave. Herodotus is implemented on top of Chord, a distributed peer-to-peer lookup service. It is written in C++ on FreeBSD. Our analysis based on an estimated size of the World Wide Web shows that a set of 20,000 nodes would be required to archive the entire web, assuming that each node has a typical home broadband Internet connection and contributes 100 GB of storage., by Timo Burkard., M.Eng.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004., Vita., Includes bibliographical references (leaves 111-118)., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., The expected transmission count (ETX) metric is a new route metric for finding high-throughput paths in multi-hop wireless networks. The ETX of a path is the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet along that path. For practical networks, paths with the minimum ETX have the highest throughput. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. Busy networks that use the ETX route metric will also maximize total network throughput. We describe the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which make them work well with ETX. Measurements taken from a 29-node 802.11b test-bed show that using ETX improves performance significantly over the widely-used minimum hop-count metric. For long paths the throughput increase is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer. We also present a simple model for predicting how packet delivery ratio varies with packet size, and detailed measurements which characterize the test-bed's distribution of link delivery ratios and route throughputs., by Douglas S.J. Couto., Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004., Includes bibliographical references (leaves 99-102)., This thesis describes Pastwatch, a distributed version control system. Pastwatch maintains versions of users' shared files. Each version is immutable: to make changes, a user checks out a version onto the user's computer, edits the files locally, then commits the changes to create a new version. The motivation behind Pastwatch is to support wide-area read/write file sharing. An example of this type of sharing is when loosely affiliated programmers from different parts of the world collaborate to work on open-source software projects. To support such users, Pastwatch offers three properties. First, it allows users who travel frequently or whose network connections fail from time to time to access historical versions of the shared files or make new versions while disconnected. Second, Pastwatch makes the current and historical versions of the shared files highly available. For example, even when their office building experiences a power failure, users can still create new versions and retrieve other users' changes from other locations. Supporting disconnected operation is not adequate by itself in these cases; users also want to see others' changes. Third, Pastwatch avoids using dedicated servers. Running a dedicated server requires high administrative costs, expertise, and expensive equipment. Pastwatch achieves its goals using two interacting approaches. First, it maintains a local branch tree of versions on each user's computer. A user can check out versions from the local tree and commit changes into the local tree. Second, Pastwatch uses a shared branch tree in a DHT to publish users' new versions. It contacts the tree to keep a user's local branch tree up-to-date., by Benjie Chen., Ph.D.