CPSC 538a - Topics in Computer Systems (Winter 2005)

The official course webpage can be found here. Below Here is a list of the paper's that I presented in class.

A Case for End-System Multicast

Paper Details: Yang-hua Chu, Sanjay G. Rao, Srinivasan Seshan and Hui Zhang.   IEEE Journal on Selected Areas in Communication (JSAC), Special Issue on Networking Support for Multicast, Vol. 20, No. 8.

Presented on: January 31, 2005

Paper Summary: This paper presented a novel application-level multicast (ALM) architecture for End-System Multicast, with an implementation of the protocol called Narada. The authors present the key design criteria and issues for End-System Multicast and demonstrate how their implementation (Narada) addresses the issues. Narada is a self-organizing, fully distributed end-system multicast implementation that uses a mesh-based overlay for optimizing both application and network-level performance metrics. Peers (hosts) maintain a routing table for other peers in their group such that they can efficiently forward data with a minimal amount of redundancy and overhead. The authors also present one of the first extensive evaluations using both simulation and real-world Internet experiments. The overall results show the Narada has very low performance pentalties for small-to-medium sized groups, and as such the potential benefits of transferring multicast from routers to end-systems outweight the incurred performance penalties.

Some of the issues that were discussed focused on the issue of scalability. For instance, hosts keep a routing table for every other host in their group. Thus, storing and maintaing these routing tables requires actively updating the information and storing stats for individual hosts. The computationl resources required for processing and storage to maintain such routing tables scales with the group size, and thus there is considerable issues with regards to scaling to larger group sizes. The authors insist that less aggresive monitoring techniques (such as lightweight RTT bandwidth probing techniques) could be used to cut down on a major portion of the overhead; however, this remains an open research topic.

Class Discussion Summary: The main points that were addressed during class discussion was the fact that the simulation experiments were performed with relatively strong (and hence somewhat unrealistic) assumptions, such as steady-state network conditions and constant network delays. Moreover, these test models ignored bandwidth, queuing delay and packet loss. Another point was raised that although the performance metrics used are typical of interactive media applications (such as video conferencing) the authors do not attempt to qualify their application as being suited for such applications, and as such the test results were discussed in the content of non-interactive media applications, such as streaming media where factors such as delay are relatively insignificant (within a certain amount).

Download the presentation (PDF)

System Architecture Directions for Networked Sensors

Paper Details: Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, Kristofer Pister.  Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000)

Presented on: February 28, 2005

Paper Summary: This paper provides a requirements analysis and prototype implementation for state-of-the-art sensor networks. The main point of the paper is that sensor network architectures have significantly different requirements that other real-time OS’s and similar micro-controller OS’s. The study concludes that the main characteristics that need to be addresses are (1) small physical size and lower power consumption, (2) concurrency-intensive operation, (3) limited physical parallelism and controller hierarchy, (4) diversity in design and usage, and (5) robust operation. Each of these is addressed in a prototype implementation which resulted in a now popular choice of OS for sensor networks, TinyOS. A very careful event-based approach with complete static memory allocation enables the authors to develop a complete prototype sensor with contains the TinyOS, 3 LED’s, photo and temperature sensors and asynchronous radio transmitter – and all of this required just over 3kb of code and only 226 bytes of data. The authors then compare TinyOS to other similar OS’s and argue how, although they sufficient for their current purposes, such existing OS’s definitely do not meet the requirements they outlined in the beginning of the paper.

Class Discussion Summary:

• The authors argue that the event-driven architecture is the standard for high-performance computing, but our class discussion led us to believe this is somewhat of a contraversial topic, and that other approaches such as multi-threading and message passing type systems are sometimes preferred depending on the application under consideration.
• The cost of these sensors that they describe in the paper, even 5 years after it was written, are much too high for the average user or even for decently-sized academic research. For instance, a "mote" with only a LED and a basic photo sensor is about $200US. Then the acutal programming board is even more than that. The general consensus is that for these technologies to really take off ,they will have to be much more affordable than they are now...Even though every paper states that in the "future", sensors will be a dime-a-dozen, this is not currently the case the "practical future" does not hold any such promises as we can currently see.
• Even though the key point of this paper is for minimizing the size and resource requirements for the OS, some people believe that such limitations will actually be a disadvantage. For instance, there is almost no room for storing data, other than for temporary processing purposes. This contradicts other researcher's view on sensor networks where they envision nodes storing a certain amount of data for long periods of time (for instance see the paper below of multi-resolution storage)

Download the presentation (PDF)

An Evaluation of Multi-Resolution Storage for Sensor Networks

Paper Details: Deepak Ganesan, Ben Greenstein. Denis Perelyubskiy, Deborah Estrin and John Heidemann Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003)

Presented on: March 14, 2004

Paper Summary: This paper describes an approach for multi-resolution data storage in sensor networks using wavelets as a means to compress data at varying levels of granularity. A dense array of sensors is hierarchically partitioned into grids, and within each partition a “clusterhead” is nominated to receive data summaries (the compressed data) from the other nodes. Each clusterhead then re-compresses the data and forwards it up to the clusterhead of a higher “level”. This process is recursively repeated until the compressed data reaches the highest level, which corresponds to the most coarse (less accurate) summary. Using this hierarchical approach, users can perform drill-down queries that start at the highest level and proceed downwards to a desired level of accuracy. Data summaries at each level are stored locally for a specified amount of time before they are “aged”, and then they are dropped or recompressed into lower-quality data summaries. The method of determining the right parameters for the aging/dropping of the data summaries is cast into an optimization problem and solved using one of three methods: ominiscient (full a priori knowledge), semi-supervised training or an online greedy algorithm. The intent of the aging algorithm is to provide “graceful degradation queries” which essentially means queries on more recent data will be more accurate as opposed to queries on older data which will be less accurate.

Class Discussion Summary:

• A point was raised that the progressive aging strategy is similar to the progressive compression level approach in Buck’s QStream system.
• The user defined aging function Quser is often not trivial to derive, and largely depends on the specific problem at hand. Sometimes only a domain expert will be the only one who can provide an accurate approximation to this optimal aging function. And because the data generated from these sensors is often input into complex simulation models, the accuracy of the data becomes increasingly important.
• The use of wavelets as well as the training algorithms is rather computationally expensive, which somewhat contradicts many researcher’s opinions that per-sensor processing should be kept to a minimum. However, the assumption in this paper is that the main constraint is network resources, so minimal communication and overhead is prioritized over computational resources. Furthermore, the argument can be somewhat offset by the fact that many of these sensor nodes may only be performing these computations infrequently, i.e. on a hourly/daily/weekly basis.
• The use of wavelets is not given much of an argument in this paper, i.e. why they chose to use this method instead of some other less computationally-expensive process. The general feeling is that wavelets are somewhat of a standard for multi-resolution analysis and thus were a primary choice for this task (perhaps so de-facto that it didn’t need arguing support)

Download the presentation (PDF)

Human Pacman: A Mobile Entertainment System with Ubiquitous Computing and Tangible Interaction over a Wide Outdoor Area

Paper Details: Adrian David Cheok, Siew Wan Fong, Kok Hwee Goh, Xubo Yang, Wei Liu, Farzam Farzbiz In Proceedings of the Second Workshop on Network and System Support for Games (NetGames'2003)

Presented on: March 30, 2004

Paper Summary: This paper presents a new type of Pacman called Human Pacman, where, like the name suggests, human beings are the Pacmen and Ghosts. A prototype implementation is given that explores the feasibility of an interactive role-playing game that combines the physical and virtual worlds into one multi-sensory experience. The game is presented through both a virtual and augmented reality environment that incorporates various aspects of human society and explores frontiers on mobile gaming. The game setting is the physical outdoors, and physical objects are integrated in the game by implanting in each a Bluetooth-enabled devices that allow it to communicate with players and other objects.

Each Pacman and Ghost is equipped with a wearable computing, a head-mounted display, global positioning system (GPS), dead-reckoning device, fire-wire cameras, Inertia sensors and a hand-held keyboard and mouse. The wearable computer is also equipped with a Bluetooth device that communicates with a central server to keep game state and data in synch.

The main concept of the game is the same as the original, which is to collect all the cookies in the Pac-world without getting eaten by the Ghosts. New to the game is a "Helper", who is assigned to each Pacman or Ghost. Helpers communicate with their partners to provide extra information, such as location of nearby cookies or enemies.

Some issues with implementation were network connectivity and bandwidth limitations. To solve the network connectivity issues, the wearable computers could store a certain amount of data locally to allow the player to continue with the game even during disconnection from the network; then upon reconnection the data is upload and re-synchronized with the main server. Currently, bandwidth limitation is resolved by keeping network traffic to a minimum, i.e. sending text status messages instead of video streams.

Class Discussion Summary:

• With "physical interaction" as a part of the game, to what limits can this be used? For example, can physical domination be used to win games?
  The discussion here was basically that physical strengths and weaknesses are now constraints and limitations in the virtual world. As described in the paper, the life-span of your virtual pacman character is directly related to the agility of the human player. A player who is physically stronger and faster will win in this mixed-reality game - this is a contradiction to current video games where these types of abilities are not a factor (although other factors still play a role, like hand-eye coordination, etc). Also, what would happen if a Pacman player physically hurt a Ghost player in order to escape from being "eaten"? Is this allowed? Probably not, but to what extent can physical interaction be used? These types of issues seem to be the most important for this new breed of mixed-reality video games.
• Issues with outdoor environment:
  We also discussed some issues about having the game in a physical outdoor environment. For instance, the unpredictability of nature and the surrounding environment raises many questions. For instance, a sudden weather storm could cause loss of communication or more permanent damage to the electronics. For importantly, the unpredictability of the outdoors introduces dangers that were never a factor before. For example, what happens if a Pacman gets hit by a automobile while running away from the Ghost? Or what if some stranger walking down the street decided to steal one of the game objects (i.e. the sugar jar)? Sounds a bit funny, but these issues will arise if the game becomes more mainstream.

Download the presentation (PDF)