From liuhz@CS.Cornell.EDU Mon Oct 21 23:06:37 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9M36bh13030 for ; Mon, 21 Oct 2002 23:06:37 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615 PAPER 40 Date: Mon, 21 Oct 2002 23:06:37 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE67D@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 40 Thread-Index: AcJ5eAjae5fnQaqLQCaWr7+b24iYzw== From: "Hongzhou Liu" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g9M36bh13030 This paper introduces the design and implementation of a single system image operating systme(MagnetOS) for sensor networks. The implementation of MagnetOs includes two steps. First, a monolithic application is partitioned into distributed components automatically at some border nodes. The MagnetOS runtime creates instances and migrate them dynamically at the start of each epoch. Two online algorithms, namely NetCenter and NetPull are present in this paper to automatically determine the power-optimizing placement for objects. NetPull collects information about the communication patterns at the physical link layer and migrates objects only one hop each epoch toward the node that communicates with them most, while NetCenter maintains information at the network layer and migrates objects directly to the node communicating with them most in one epoch. Both algorithms require only local info- rmation that is readily available and thus are easy to implement. MagnetOS selects epoch length dynamically to improve system longevity. The goal of the selection algorithm is that a well-placed component should get equal numbers of packets from all directions within an epoch. The paper presents detailed simulation result to demonstrate the performance of two object -placement algorithms and the effect of different selection of epoch length on the performance. The result demonstrate that MagnetOS can conserve power and achieve a factor of four to five improvement in system longevity. A problem here that I can not understand is in Figure 10, random algorithm achieves better system longevity than NetPull, which conflicts with results in other figures. I think the paper should spend some efforts here to explain this anomaly. From hs247@cornell.edu Mon Oct 21 23:57:23 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-0.nyroc.rr.com [24.92.226.125]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9M3vNh22462 for ; Mon, 21 Oct 2002 23:57:23 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g9M3vLL22501 for ; Mon, 21 Oct 2002 23:57:21 -0400 (EDT) Message-Id: <5.1.0.14.2.20021021235719.00b8e650@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Mon, 21 Oct 2002 23:57:39 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 40 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper introduces MagnetOS, a distributed operating system designed for sensor networks. Sensor networks differ from regular wired distributed systems in that they are resource limited, especially in power. It has been identified that most power consumptions is due to communication. MagnetOS tries to extend a system's lifetime by moving objects where communication is kept to a minimum. MagnetOS is implemented as a distributed java virtual machine. A java application is partitioned into the granularity of object instances. At the partitioning phase, each class is translated into a remote object. Like Java RMI, there are stubs (MagentPole), an interface (Magnet Interface), and the instance of the object Magnet. Because static methods, are also needed, static methods of a class are encapsulated in their own class (MagnetStatic) and is handled like another object. Objects can now move around in the network and it is the job of the Magnet Pole to track them down. Application partitioning takes place at the binary level and is therefore transparent to the user. However, the system does provide an interface where a developer can specify components to bind to specific nodes. Two movement object models were looked at: NetPull and NetCenter. They were compared to Static (objects were statically assigned to nodes) and Random (objects are randomly assigned to nodes). Both NetPull and Netcentre decide where to move an object based on communication information collected during a certain time interval (epoch) at each node. At the end of each epoch, NetPull moves an object instance one hop closer to where most messages are coming from and sent to. NetCentre moves an object directly to the node where there is the most activity pertaining to that object instance. In both cases, the idea is to lessen the communication overhead (and therefore power consumption). Obviously the length of an epoch is very important. As one that is too short might make an object move around unnecessarily, while a long one may cause the system to waste energy in communication. In the simulation, it was shown that NetPull and NetCentre outperformed Static and Random techniques by extending the systems lifetime by 4 or 5 times. One issue that this paper didn't address was failure. What happens if a node with an object instance dies? Perhaps when a node knows that its lifetime is becoming short, it can start to replicate the instance to other nodes. Some questions that can be asked are: Which node becomes the owner of the instance next? How many replications of the object instance is necessary? How do you replicate the object instance data to make sure it is consistent? From ag75@cornell.edu Tue Oct 22 01:13:28 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9M5DRh06872 for ; Tue, 22 Oct 2002 01:13:27 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id BAA17292 for ; Tue, 22 Oct 2002 01:13:25 -0400 (EDT) Date: Tue, 22 Oct 2002 01:13:25 -0400 (EDT) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 40 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII In this paper we are presented with MagnetOS, an operating system designed for wireless multi-hop networks, where utilizing power effectively and maximizing system longevity is more important than traditional application performance. MagnetOS tries to maximize system longevity by bringing application components closer to the data sources. In order to do this the authors use two object placement algorithms: NetPull and NetCenter. Both of these operate on the principle that shortening the the mean path length of data packets by automatically moving communicating objects closer together will reduce the total distance packets travel, and thereby reduce the overall power consumption. One of the important points is that the object placement is done automatically. This way all applications are forced to behave cooperatively. Before this can be done, however, the system needs to convert the given monolithic applications into a distributed application. MagnetOS does this for Java, but there doesn't seem to be a way to do it for applications written in other languages. In addition, the authors have found that most nontrivial, stateful applications will require some amount of failure recovery in all but the most densely connected and static networks, which means that the applications will have to be modified. The authors say that 2 MB of RAM is needed to run MagnetOS, which makes it unusable for older sensor networks. However, for newer sensor networks MagnetOS looks promising because it scales well (3600 nodes in simulation) and the improvement is system longetivity (4 - 5 times) is impressive. From mvp9@cornell.edu Tue Oct 22 01:53:50 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9M5roh13167 for ; Tue, 22 Oct 2002 01:53:50 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id BAA25084 for ; Tue, 22 Oct 2002 01:53:47 -0400 (EDT) Date: Tue, 22 Oct 2002 01:53:47 -0400 (EDT) From: mvp9@cornell.edu X-Sender: mvp9@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 40 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII network, MagnetOS, that aims to minimize power consumption and extend lifetime of the system. The contributions are two-fold - a program to separate a java program into components (on class level) that can be sent to different nodes, and an algorithm that manages the location of these components, and does so quite well. Both of these innovations are incorporated into a modified JVM that is to run on each sensor node. Specifically, two methods are introduced to decide on location of components - NetPull and NetCenter. Both function by monitoring traffic to a component and then, if deemed necessary, either moving it up-stream with respect to the traffic, or directly to its source. Finally, the longevity of the nodes using this approach, the performance of the code decomposition, and the epoch lengths (used by NetPull and NetCenter) are evaluated. The strengths of the system are also its potential weaknesses. The modification of java code to work over separate nodes without access to source code is impressive. Despite the descpription of how various java services are adapted to this distributed form, its hard to believe that all the exception handling, garbage collection, message passage, multi-threading, etc provided by java are fully handled. What is the program used to demonstrate the longevity of MagnetOS - how intensive is this SensorNet? As has been noted before - be wary of the benchmarks developed by the application programmer. Further, the numbers in the Java RMI vs MagnetOS comparison are strange - how can an automatic decomposition perform 3-6 times better than a manual one, unless either the manual one is very poor, or the benchmark targets its unfairly. The component distribution mechanism intuitively makes sense, if it is lying on top of the rest of MagnetOS structure. Perhaps even better models can be developed for component placing, for example, by noticing patterns and acting preemptively, although this would require considerable state and processing. Also, how long are the epochs? How long, in terms of time, do the tested nodes survive, and is that reasonable? Finally, sensor networks are often quite immobile, and manually writing a static (but efficient) partitioning, with good load-balancing, may be very successful, possibly on the level of Net* algorithms. From shafat@CS.Cornell.EDU Tue Oct 22 03:32:31 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9M7WVh00720 for ; Tue, 22 Oct 2002 03:32:31 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615 PAPER 40 Date: Tue, 22 Oct 2002 03:32:31 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134FB1@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 40 Thread-Index: AcJ47NpVO55CXKdKSa+dFdDW1hQcQA== From: "Syed Shafat Zaman" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g9M7WVh00720 This paper presents an outline of MagnetOS, a single system image Java operating system for sensor ad hoc networks. The main design goals of MagnetOS are described as efficient, adaptive, general purpose and platform independent. It provides an abstraction of a single JVM over an ad hoc network of heterogeneous nodes that is capable of moving around application components among nodes for load-balancing and reducing energy consumption. The application partition granularity in MagnetOS is done at the class level. This essentially allows instances of a class object to move around freely in the network. Remote stubs known as MagnetPoles are used for tracking the current location of the corresponding Magnet in the network, and also for invoking procedure calls on the Magnet. For the explicit purpose of component migration in the network, the paper introduces two algorithms that work at different layers in the network. NetPull operates at the physical layer and migrates components to the one hop neighbor with the greatest communication pattern with the reference node. On the other hand, NetCenter operates at the network layer, and migrates component to neighbors multi-hops away based on the same criterion. The main goals for using these algorithms are to extend system longevity, balance load more effectively, and avoid hot spots in the network. While the paper does specify a minimum threshold of probability on which the migration decision is based upon at each epoch, I think adding another parameter to this model might lead to improved performance. It is implicitly assumed that the energy cost associated withcommunications far exceeds the cost involved in processing at each node. However, it may be the case that the nature of the component granularity does not allow for any further partitions in this "expensive" component being processed, and migrating it to other nodes would only add extra communication cost to the system. The simulation results however show impressive improvements over more traditional algorithms like "static" and "random". Another minor problem that I personally had was figuring out exactly where the MagnetPoles reside during the execution phase. It seems that they remain resident on the node where the object instance is first created - although this assumption could be wrong. Future work could involve adding more fall-back mechanisms in the system. What happens if a node dies along with the components that were residing on it at that particular instance? What if a node with an active component move out of range of the MagnetPoles? From mr228@cornell.edu Tue Oct 22 03:33:48 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9M7Xlh00834 for ; Tue, 22 Oct 2002 03:33:47 -0400 (EDT) Received: from cornell.edu (pptp-039.cs.cornell.edu [128.84.227.39]) by cornell.edu (8.9.3/8.9.3) with ESMTP id DAA05443 for ; Tue, 22 Oct 2002 03:33:47 -0400 (EDT) Message-ID: <3DB4FFA4.AD10DC3D@cornell.edu> Date: Tue, 22 Oct 2002 03:35:00 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 40 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper present MagentOS, a system designed to provide transparent code mobility for applications designed for sensor networks. The primary contribution is to provide a system that moves code around the network so as to optimize power-consumption and is at the same time completely transparent to application programmers. The system is a modified JVM that can split any application into chunks and move chunks around the network to optimize some performance metric. MagnetOS chunks can be a fine-grained as a single object. MagnetOS rewrites byte code thus not requiring access to source; this rewriting allows the MagnetOS runtime to catch certain events. The primary "event" is object instantiation. Everytime an object is to be instantiated, the MagnetOS runtime chooses a suitable node (initially always the current local node in this implementation) and places the object there. Objects can then move around and leave pointers behind indicating where the actual object has been moved to. A stub is left in place of the object and when the stub is accessed, the MagnetOS runtime uses an AODV routing layer to make the appropriate RPC calls to the remote node containing the object instance. The two interesting relocation heuristics used are NetPull and NetCenter. NetPull uses physical layer traffic analysis and relocates objects to the neighbor with which it had the most transactions during the past epoch (an epoch being some fixed amount of time) NetCenter is similar in spirit, but uses network layer AODV statistics and relocates objects to the node (any node, not just a neighbor) with which the object interacted with the most during the previous epoch. One thing that is unclear is how the "long chains of forward pointers" are collapsed without destorying needed paths/links. Also, how is node failure dealt with? Is there some method of instance re-discovery? Future work might consider classes of applications that might be run on top of this framework. Some applications might have one large class doing most of the computation and many very short lived objects and thus benefit less from this system, and others might be just the converse and be a perfect fit for this. From ashieh@CS.Cornell.EDU Tue Oct 22 03:34:44 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9M7Yhh01561 for ; Tue, 22 Oct 2002 03:34:44 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g9M7YhC27064 for ; Tue, 22 Oct 2002 03:34:43 -0400 (EDT) Date: Tue, 22 Oct 2002 03:34:43 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 40 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ** Contributions This paper presents a system for dynamically partitioning computations in an ad hoc network. Computation hotspots may potentially form in ad hoc networks, much in the same way that routing hotspots may occur. In MagnetOS, applications binaries are in JVM byte code, and objects are the units of relocation. Infrastructure for supporting code motion is added through binary rewriting; the overhead of the MagnetOS approach comes from this RPC glue and the cost of moving object state around in the network. One of the NetPull and NetCenter algorithms is used for placing objects in the network. In the NetPush algorithm, objects are moved one hop at a time, along the local peer through which most traffic is routed. In the NetCenter algorithm, objects are moved to the RPC peer that is communicated with the most. An epoch detection algorithm is used to determine when object movement decisions should be made; it triggers object motion when communications patterns prefer one peer over the others. Both code motion approaches were found to increase network longevity, with NetCenter having the best performance, especially when the dynamics of the sensed environment changes drastically (see section 4.6). NetPull seems to fail to converge in these stressful situations, performing worse than a random allocation. ** Shortcomings There appears to be an implicit unfairness of the heuristics. For instance NetCenter only uses the relative ordering between link usage the layout decision. This implies that when the top three links are each heavily used, with the peers objects communicating in a way such that they are not relocated (for instance, heavily communicating with other objects assigned to the same node), and there are a number of other low usage object peers, relocations could oscillate; for good reason, too, since none of these nodes are likely a good place for the object. A better algorithm might attempt to place the object in the "middle". This analysis assumes some degree of degeneracy in the communications patterns, which may not arise in practice. A big unstated assumption is that local placement decisions don't lead to global instability that can cause worse performance, and so the heuristics do not deal directly with the dynamics of multiple objects. There may be a cluster of communicating objects, of which the relocation of one would trigger the relocation of the others. Suppose there is a linear chain of such objects, then a linear number of epochs is required to migrate the entire cluster. This assumes that the cluster is even moved. If the communications within the cluster dominates communications outside the cluster, then no object within the cluster would ever be moved. In general, one object movement may trigger a cascade of other movements, which is potentially cyclic. These cases seem to beg for a movement algorithm that considers objects en masse. Such situations could potentially be solved with programmer intervention, perhaps by annotating objects as a group, or combining multiple classes. The latter likely imposes a larger programming and maintainence burden. It would be nice to have a definition of "best-case layout" against which to compare these placement algorithms, for limits analysis. Perhaps a layout system that operates with global knowledge and reacts instantly. The paper does not discuss the convergence properties/conditions of NetPull and NetCenter. NetCenter can potentially exhibit oscillations and suboptimal placement; NetPull potentially places the object in the "center" when there are multiple competing high-utilization paths. NetCenter seems to have better convergence properties in general, based on Figure 10, but this is not explained in the paper. ** Future directions - Allow the user to specify affinity between objects, not just affinity of objects for nodes. - The migration algorithm forms a feedback loop with an epoch detection algorithm. This implies a potential instability in the system, depending on the choice of algorithms for both. - Explore how to use both NetPull and NetCenter at the same time, and quantify the advantage of doing so. - Tighter integration between routing and object placement For instance: Link-state routing required considerable space overhead. However, it seems that having a global view of the routing graph would be useful for object placement, since one could then directly place a relocated object in the "center" of a bunch of communicating nodes, rather than having to commit to one particular node. In this case, the overhead of the link-state is amortized over two clients, and can potentially be supplied to the application layer as well to amortize the cost still more. We could reactively construct those parts of the graph that are relevant to the active links of each object placed at a particular node to save space. So long as network degree/density remains constant as technology improves and network size increases, link-state techniques are scalable. - It may be nice to communicate an imminent epoch change on an object to the other peers of that object, which would trigger nodes to determine how to reallocate other objects, and potentially shoot down the proposal if the cost of rearranging other computation is expensive. This would perhaps alleviate some of the cascading pull effects. - What is the relative performance of the routing algorithms that we have discussed in the presence of primarily on-off topology changes? How can we exploit this restriction in a routing algorithm? From mp98@cornell.edu Tue Oct 22 08:21:57 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MCLvh26711 for ; Tue, 22 Oct 2002 08:21:57 -0400 (EDT) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id IAA16075 for ; Tue, 22 Oct 2002 08:21:56 -0400 (EDT) From: mp98@cornell.edu Date: Tue, 22 Oct 2002 08:21:58 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: CS 615 Paper 40 To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: X-Mailer: Apple Mail (2.546) This paper describes Magnetos, a system whose separation of data filtering nodes from data acquisition and consumption nodes is somewhat reminiscent of the earlier paper in this course on directed diffusion; Magnetos is distinguished, however, by its ability to migrate tasks based on dynamic conditions in the network (the directed diffusion paper had static filters in place). The goals of Magnetos are to be efficient in terms of power, adaptive, general purpose, and platform independent. A MagnetOS system acts as a single Java Virtual Machine. When code is injected into the network, it is partitioned into components (once partitioned the break-up is static) at the object level, which are distributed throughout the network. An object in the network is a Magnet, a reference to that object is a MagnetPole, and knowledge of the object's API is a MagnetInterface. Static variables are implemented with MagnetStatic. The methods of a Magnet are executed through a MagnetPole which will either send the request to the local interface (if it resides on the local host) or to a remote node using AODV routing. Offtopic, but having talked to both John and Dan about their work, the description of MagnetOS RMI versus Java RMI should be stronger in order to explain table 1 of the paper on the cost of remote calls. After initial distribution, components will be migrated around to minimize power consumption. Although some components may be hardcoded to certain nodes, most will be free to move around. The goal of migration in general is to minimize the amount of forwarding required for RMI in MagnetOS. The two techniques of object migration are NetPull, which pulls objects towards their optimal location by forwarding them at the end of an epoch to the neighboring node with the most communication to it, and NetCenter, which moves objects directly to the source of the most communication. There are some problems here, obviously: it might be optimal to move an object to some midpoint in the network, for example the branch of the fork in Figure 2 of the paper. But NetCenter only moves towards sources. NetPull could work in this situation, however, it would require that an object be allowed to remain at its current location which so far as I can tell is not specified in the paper. Also perhaps I am confused, but I think the system as it stands now will not necessarily stabilize. Say we have a NetCenter system with components A and B on two nodes and another component C that they both communicate a lot with. It seems that from epoch to epoch C could move from one node to the other and back to the first on the following epoch, over and over again, possibly expensively. In terms of simulation, this paper also commits one of the great sins of papers we have read: It develops its own simulation environment. While I can understand why (having experience a night of rough, abusive, masochistic love making with ns2 myself) and some of the motivation (not wanting to release the code until published), still: One should plan to allow access to it at the time of the conference. What this paper needs most is a re-evaluation of the NetPull and NetCenter operations. The rest of the paper is very strong, but these algorithms seem doubtful to a reader: Why do components *always* move? Why just count the number of messages without some scaling according to latency (for example, if a component is getting messages from both A and B and B is sending slightly more messages, but A's messages come from many more hops away, perhaps it makes sense to NetCenter at A instead of B)? From smw17@cornell.edu Tue Oct 22 09:41:01 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MDf1h12367 for ; Tue, 22 Oct 2002 09:41:01 -0400 (EDT) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id JAA12522 for ; Tue, 22 Oct 2002 09:41:00 -0400 (EDT) Message-ID: <3DB402F8.9040604@cornell.edu> Date: Mon, 21 Oct 2002 09:36:56 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0.1) Gecko/20020823 Netscape/7.0 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 40 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Single System Image Java Operating System The target for the system described in this work is a network of sensor nodes communicating data results to a single concentrator node that bridges between the sensor network and the standard network. Each node is assumed to have moderate processing power and local storage, and the power consumption of the wireless transmission is assumed to be the dominant factor in overall power consumption. One consequence of this design assumption is that there is a definite benefit in data aggregation and processing within the network, trading local processing for network bandwidth. The goal of the system presented in this work is to dynamically allocate the data processing throughout the network in order to minimize the total energy required and preserve the lifetime of the network. Given the assumptions stated above, achieving this goal becomes a matter of minimizing the size and frequency of network transmissions. The authors propose to do this with a dynamic Java-based system that constructs a single JVM from the entire network. The sensing applications run on top of this virtual machine, with the OS handling the dynamic distribution. Applications are decomposed from Java byte code at the object/class level, and standard access primitives are redirected at the OS level to break the class into a Magnet instance, a remote stub (MagnetPole), an interace (MagnetInterface), and a class object (MagnetStatic). By decomposing the original class in this manner, it is possible to make the class itself a dynamic entity in a relatively transparent fashion - the only major impact of accessing a remote object is the increased latency and power involved in the transaction. This rewriting is done at the byte code level at code injection points, after which the application code is distributed across the entire network in its re-written form. The system runs over the routing layer, permitting a variety of ad-hoc routing algorithms to be chosen. A custom RPC package was implemented to overcome limitations in Sun's RMI. The heart of this system is the energy-minimization procedure. The energy minimiation procedure seeks to distribute the mobile class structures in such a manner that the network energy use is reduced by profiling the connection behavior for each object, and relocating those objects based on this information. Two mechanisms are presented for implementing this relocation. The first, NetPull, works with profiling information collected at the physical layer for each object. At the end of each epoch (one unit of time for the relocation algorithm), the object is migrated one hop in the direction of the link with the greatest communication. NetCenter operates at a higher level, permitting multiple hop migrations in each epoch. NetCenter considers the source and destination addresses, and for each epoch migrates objects to the node most frequently accessed. An epoch is ideally matched to the event frequency of the sensors for best performance. An adaptive epoch selection mechanism is presented. The system was simulated in a custom simulator designed to handle large networks. Results from the simulation are promising, showing a significant benefit to the proposed scheme over more simple scenarios. Simulation results suggest that distributing the processing across the network can significantly improve the lifetime of sensor networks by shifting much of the load off of the critical nodes around the gateway node. Indeed, this system appears to have a much more graceful failure mode than the naive static implementation, achieving 55-70% of power consumed usefully, as compared to the 5-30% demonstrated by the naive static implementation. I would, however, be interested in seeing a comparison with a more intelligent static or pseudo- static implementation, rather than the almost hopelessly naive static scheme presented. I would also be interested in seeing more information on the network traffic patterns and object/class mobility, to get a better picture of exactly how mobile these classes are in practice. Finally, Figure 7 is the wrong graph, exactly the same as Figure 6. From tmroeder@CS.Cornell.EDU Tue Oct 22 09:51:01 2002 Received: from dhcp98-88.cs.cornell.edu (dhcp98-88.cs.cornell.edu [128.84.98.88]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MDp0h14506 for ; Tue, 22 Oct 2002 09:51:00 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp98-88.cs.cornell.edu (8.11.6/8.11.6) id g9MDnEL09275; Tue, 22 Oct 2002 09:49:14 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15797.22362.74846.53429@dhcp98-88.cs.cornell.edu> Date: Tue, 22 Oct 2002 09:49:14 -0400 To: Emin Gun Sirer Subject: 615 PAPER #40 X-Mailer: VM 7.07 under Emacs 21.2.1 (I note that Gun hasn't given us any helpful hints in red ink here about what to look for in his paper :-) MagnetOS seeks to be a single system image operating system for ad hoc wireless sensor networks, and, in particular, this paper addresses the issue of code movement to preserve overall energy consumption in the network. They present two algorithms, NetCenter and NetPull, and describe an adaptive epoch-choosing algorithm which further optimizes the actions of NetCenter and NetPull. They carefully avoid some of the traps of RPC, such as cyclic object references (which would be deadly to power consumption in an ad hoc power constrained setting) by using a lease-based garbage collection scheme for objects in the network. The evaluation is on a custom simulator, which claims to represent well the physical and hardware universes they depend on. I have some concerns about issues to do with this setup. The first and foremost is that the Net* algorithms, while having been demonstrated to work well for whatever this benchmark actually comprises (which may be sufficient to quell my concern), have not been demonstrated here to work well for all types of applications. What if, for example, the sensor network only comes into contact with a collection agent infrequently? (ie. we don't have a central data processing node, but rather a collector which comes by infrequently to pick up data?) What if the motion of the code tends to follow a particular path through the network, because a certain node is sending out lots of data. In this case, nodes along that path would have to transfer many of the objects in the network, which might be more packets than they would have had to send if the objects had just stayed put. In general, in fact, the question of the viability of *particular* nodes is not addressed. I would like to be able to have a notion of the worth of a node, which might, for instance, change adaptively on the power remaining at that node along with the importance of the data it can sense. Especially as one of the main issues here is losing connectivity in the network, it seems valuable to consider ways in which one can preserve that connectivity to key sensors for as long as possible, even if this means losing other parts of the network. In the current setup, applications can decide it for themselves, but this adaptability is exactly the problem MagnetOS was designed to address. Future algorithms might use some of these metrics by, for instance, having a way of judging the cost of sending a particular object versus continuing to receive packets (it might not be possible to go this in general, since packet sending is continuous, and moving an object only happens once. The only time it might matter is if moving the object will cause a failure along the path, or if we know that we'll be communicating for a fixed length of time). Another possible metric would be to consider preserving nodes which sense important data. Some idea of coverage could be applied here. From bd39@cornell.edu Tue Oct 22 10:05:43 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9ME5hh18247 for ; Tue, 22 Oct 2002 10:05:43 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id KAA00964 for ; Tue, 22 Oct 2002 10:05:40 -0400 (EDT) Message-Id: <5.1.0.14.2.20021022100237.00b96ba8@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 22 Oct 2002 10:03:24 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 40 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Paper 40 - MAGNETOS Magnetos is a distributed operating system whose is target platform is a large sensor network. The goal of magnetos is to provide an operating system which can run general purpose sensor applications in a power aware manner. Magnetos seeks to be transparent to the end application that runs on top of it and be adaptive to changes in network conditions. Features: 1 Operating system runs as a unified java virtual machine 2 Code is distributed in the system by a static partitioning system. These objects form the units which Magnetos moves from node to node in the system to reduce power consumption. - code is partitioned by classes. Method calls to object instances in the system are replaced by a stub into RPC calls, which allow instance objects to move to different nodes in the network. A java class is split into the instance, redirection layer, interface and class/static data. (magnet, magnet pole, magnet interface and magnet static) - Object code is migrated by saving the state of a magnet and sending it to the target node. magnet poles are updated to redirect to the destination. 3 Running code is migrated according to two schemes NetPull and NetCenter - Magnetos keeps track of all network traffic between components per epoch. At the end of the epoch: - NetPull migrates code in the direction of the most network traffic - NetCenter places code at the source of the most network traffic. - Spurious movement is prevented by calculating a threshold for migration. Evaluation: Custom written simulator simulated the effect of NetPull and NetCenter on a sensor field. The sensor field consisted of static sensors (sources), movable condensors (sinks) and events that move through the sensor field. NetPull and NetCenter perform quite well in extending sensor field longevity, 4 to 5 over static placement. Questions: Train effect of programs following each other? Suppose there was an event that moved through the sensor network. In NetPull, could there be a case where the components chased each other, one after the other for the event. Evaluation does not show the effects of partitioning. Condensors are single instance of an object. What about running a more complex application which has been split into multiple pieces? How does NetPull, NetCenter perform in different traffic models, other than locality based events? What is the advantage of partitioning anyway? Given that the capability of sensor nodes is to increase, why partition an application and incur more communication traffic? There is no evaluation as to the benefits of partitioning a system. Ease of porting. How extensive were the changes needed to ensure proper error handling for post partitioned programs? Failure of nodes results in a lot of problems for applications, especially when instances of objects suddenly disappear from the network. How are these failure modes addressed? Dynamic replication and merging of condensers due to traffic? (ClayOS) Misc: Figure 7 seems to be the wrong graph. From kwalsh@CS.Cornell.EDU Tue Oct 22 10:14:49 2002 Received: from duke.cs.duke.edu (duke.cs.duke.edu [152.3.140.1]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MEEnh20412 for ; Tue, 22 Oct 2002 10:14:49 -0400 (EDT) Received: from localhost (moe.cs.duke.edu [152.3.140.74]) by duke.cs.duke.edu (8.9.3/8.9.3) with ESMTP id KAA00550 for ; Tue, 22 Oct 2002 10:14:48 -0400 (EDT) From: kwalsh@CS.Cornell.EDU Received: from 132.236.29.71 ( [132.236.29.71]) as user walsh@imap.cs.duke.edu by login.cs.duke.edu with HTTP; Tue, 22 Oct 2002 10:14:48 -0400 Message-ID: <1035296088.3db55d58bb0a4@login.cs.duke.edu> Date: Tue, 22 Oct 2002 10:14:48 -0400 To: egs@CS.Cornell.EDU Subject: 615 PAPER 40 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.0 X-Originating-IP: 132.236.29.71 A single system image java operating system for sensor networks (aka: MagnetOS). This paper introduces MagnetOS, a system designed to mask the complexity of programming sensor networks behind a single-machine abstraction. The high-level goal is to extend system lifetime, which is primarily impacted by the high power draw of sending packets in the network. The central insight is that network hotspots (which lead to premature system failure) can be mitigated by code placement, or more specifically by code mobility. The system input is a standard Java program. In an off-line stage, the program is statically partitioned into distributable components along class boundaries via bytecode rewriting. The system is then free to position components independently within the sensor network (i.e. at sensor nodes, intermediate nodes, or base stations). Two adaptive algorithms are presented to obtain a good placement. Both repeatedly reposition components for a better fit after some epoch duration. The intuition is that packet flows in the network should act as “magnets”, pulling components closer to the sources of packets, and thereby minimizing total network traffic. The two algorithms differ only in the granularity of movement: NetPull repositions components at most one physical hop per epoch, in the direction of greatest packet flow. NetCenter repositions components many hops per epoch, directly to the greatest source of packets. Finally, an algorithm is presented to adaptively choose epochs. Here, the motivation is that a simple statistical test is sufficient to determine if the accumulated “magnetic pull” of packets seen so far is statistically significant. If so, the epoch is declared finished (locally). Some simulations show that the algorithms seem to work in at least one scenario. What is lacking, I feel, is good motivation and justification on several points. Why should partitioning only be done along classes boundaries (other than the ease of implementation)? Is this a good or natural choice? Are all classes modularized (including String, Integer, etc.)? Also neglected is the impact of code size stored on individual nodes. It could be argued that this impact is unimportant, but then why would the paper carefully state that only the code for constructors be placed unilaterally across nodes. The obvious answer is that full replication of code is too expensive in terms of space and network bandwidth. So these factors obviously are important, and should be addressed. Also missing is justification for why these algorithms should (1) approximate a good placement, and (2) converge to something reasonable. Simple examples show both algorithms achieving sub-optimal placements, or actually moving away from optimal placements to less optimal placements. I find especially disturbing figure 10, a graph of the number of epochs to failure versus epoch length. (I assume the y axis is actually time to failure, and not number of epochs to failure, otherwise static placement would show a hyperbola). Intuitively, it seems as if a 5-second epoch length, matching exactly the duration of event intervals, could be disastrous due to the phase offset between events and mobility. This would be the common case, even. Perhaps error bars would show this problem, or perhaps I misunderstand the graph or algorithm. From nbs24@cornell.edu Tue Oct 22 11:17:46 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MFHkh06248 for ; Tue, 22 Oct 2002 11:17:46 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA04483; Tue, 22 Oct 2002 11:17:44 -0400 (EDT) Date: Tue, 22 Oct 2002 11:17:44 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200210221517.LAA04483@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: nbs24@cornell.edu X-Originating-IP: 132.236.71.82 Subject: 615 PAPER 40 The paper describes the design and implementation of a distributed operating system (MagnetOS) for sensor networks, whose primary limitation is energy consumption. MagnetOS is implemented as a distributed JVM. It partitions a java program into different components that can be sent to different nodes. The authors introduce two automatic object migration algorithms; NetPull and NetCenter. The goal of these algorithms is to reduce overall energy consumption by automatically moving communicating objects closer in proximity and thus shortening the travel distance of data packets. The performance of NetPull and NetCenter are compared to static and random object migration algorithms and the authors find that their contribution extends the system lifetime by 4 to 5 times. The major weakness is the authors’ development of their own benchmark, SensorNet. It does not give credibility to their performance numbers, especially since the underlying simulation framework is not verified by anyone else. And what happened to Figure 7 (it looks like Figure 5 to me)? How do the 2 algorithms behave in different traffic scenarios? How about the effect of node failure? How well do these algorithms converge? Are the static and random algorithms the best algorithms out there for comparison purposes? Future work could include using a widely accepted set of benchmarks and then submitting SensorNet separately as a new benchmark. Also the authors may want to consider node failure and convergence in future evaluations. Nana B. Sam From pj39@CS.Cornell.EDU Tue Oct 22 11:22:28 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MFMSh07609 for ; Tue, 22 Oct 2002 11:22:28 -0400 (EDT) Received: from pj39.cornell.edu (syr-24-59-67-50.twcny.rr.com [24.59.67.50]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA00443 for ; Tue, 22 Oct 2002 11:22:26 -0400 (EDT) Message-Id: <5.1.0.14.2.20021022110920.01e078d8@postoffice2.mail.cornell.edu> X-Sender: pj39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 22 Oct 2002 11:22:28 -0400 To: egs@CS.Cornell.EDU From: Piyoosh Jalan Subject: 615 PAPER 40 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed A Single System Image Java Operating System for Sensor Networks This paper introduces MagnetOS a Java based distributed operating systems which enables power-aware, adaptive and efficient applications for ad hoc networks. According to the paper developing applications to run efficiently requires components that collaborate to be optimally placed in the network (reducing the mean path length). MagnetOS achieves this by statically partitioning the code and by providing a local runtime that supports partitioned applications.The code partitioning is done at the Java bytecode level and is performed by partitioning different classes and placing them at different nodes. Object creation thus involves call to the local runtime which selects the appropriate node and creates an instance of the class (object) at that node. Method invocations take place through the Java RMI (remote method invocation) mechanism. The decision of moving the statically partitioned objects is based on two online algorithms NetPull and NetCenter. NetPull operates at the physical link level and migrates components one hop at a time whereas NetCenter operates at the network layer and migrates components directly towards the host with which the object communicates most. This moving of objects closer to the hosts where they are used most increases system longetivity (less power consumption), less network bandwidth utilization etc. The resulting network is also platform independent as because the static code partitioning takes place at the Java bytecode level and the system provides a single system image of a Java virtual machine to applications over a collection of heterogeneous nodes. The main goals of MagnetOS is summarized below - Employs static code partitioning at the Java bytecode level and places these objects nearer to its highest usage to ensure optimal resource usage. This reduces energy consumption thus increases system longetivity. - Provides single Java virtual machine (JVM) image to network applications. - It is adaptive as the communication pattern changes the objects are moved around accordingly. - It is scalable due to the movement and optimal allocation of resources among the nodes. - It is platform independent and hence applications can be run in a network with heterogeneous nodes and also consisting of both fixed and mobile nodes. - Uses NetPull and NetCenter for placing objects nearer to its greatest communication host thus reducing the mean path length of data packets and hence conserving energy in the long time. Future work could be directed towards optimizing MagnetOS for networks which has a mix of static and mobile nodes(wired and wireless nodes). Since energy is not a constraint for static nodes so the partitioned objects could be moved and/or replicated at the static nodes (as static nodes usually has more memory too), hence mobile nodes closer to the static nodes could be served by creating instances of objects and remote method invocation at these static nodes thus further increasing the longetivity of the system. Moreover the paper is based on the assumption that there are certain communicating hosts which instantiates and invokes certain object more than other. However there is no mention on the basis for this claim. What if use of resource is evenly distributed among nodes over time. In this scenario the NetPull and NetCenter algorithms used here might try to move the partitioned objects closer to the communicating hosts which might end up consuming more energy than other wise keeping the object static at one node. From vivi@CS.Cornell.EDU Tue Oct 22 11:45:41 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MFjeh15642 for ; Tue, 22 Oct 2002 11:45:41 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615paper40 Date: Tue, 22 Oct 2002 11:45:40 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF92@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper40 Thread-Index: AcJ54hDqgiRJE6rBRJ+pX6G46k+AOQ== From: "Vivek Vishnumurthy" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g9MFjeh15642 This paper describes MagnetOS, an operating system for sensor networks. Sensor networks are resource-constrained, and communication between nodes is the biggest energy consumer (according to the paper). MagnetOS tries to extend system lifetime by dynamically migrating applications close to where they are needed, and thus saving the amount of power used in communication. Applications are split into components, and the migration decisions corresponding to each component are independently taken, based on the incoming and outgoing communication packets corresponding to that component. The system uses one of two algorithms for object migration: Netpull (operates at the physical link level) migrates objects one hop at a time along the link that had the most communication, and NetCenter (operates at the network level) migrates objects directly to the node that communicates the most with the object. Contributions: The paper is based on a novel concept : move applications to where they are needed the most. Simulation results show that the concept works. The system is also highly adaptive. Migration decisions are dynamically made, thus making the system applicable in typical sensor networks where the pattern of communication varies widely. Weaknesses: -- The migration decision does not consider nodes' remaining capacities. Thus the decision to migrate an application to a node that is already low in reserve power might worsen the system lifetime. The system could be made more robust by assigning some weightage to the reserve power at a node. -- The worst case O(n^2) space requirement. -- Repeated fluctuations of communication patterns could lead to thrashing: migration of components back and forth. Possible improvements -- The logic behind the equation used to decide if there is a definite gradient in the communication is not very clear; this could be clarified further. Also, the equation assigns equal weightage to all nodes. It makes sense to assign higher weightage to the communication between the component and the node that it resides at, because this communication incurs effectively zero cost. (It is also very likely that the amount of this communication is significant, as the migration algorithm at the previous epoch had decided to move the component to this node.) From mtp22@cornell.edu Tue Oct 22 11:57:01 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MFv1h20654 for ; Tue, 22 Oct 2002 11:57:01 -0400 (EDT) Received: from narnia (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA07389 for ; Tue, 22 Oct 2002 11:56:59 -0400 (EDT) Content-Type: text/plain; charset="iso-8859-1" From: Matt Piotrowski Reply-To: mtp22@cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 40 Date: Tue, 22 Oct 2002 11:57:33 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <0210221157330I.00645@narnia> Content-Transfer-Encoding: 8bit The main contribution of this paper is a distributed operating system for sensor networks whose goal is to maximize the lifetime of the network. The motivation behind this is analyses that have shown that power consumption is the biggest concern in sensor networks, and that it costs a lot more to send data than to compute data; so if we can somehow be smarter with where we put the processing, we may be able to achieve a much longer network lifetime while achieving the same functionality. MagnetOS offers a way to break up an application and ways to distribute the pieces dynamically based on the state of the network. The two main algorithms behind MagnetOS are NetPull and NetCenter, which move the processing of data closer to the source on a step-by-step physical level and a larger network level, respectively. I think a weakness of this paper is the emphasis on the automatic and transparent partitioning of an application. The paper talks about how legacy applications can be run on a MagnetOS system. However--and this is discussed a little in the paper--if an application doesn't specify what to do in the event of a component failure, it is very hard to guess what should be done. An exception framework is added to deal with this, but then the partitioning is no longer transparent. That is, an application will have to know where MagnetOS may partition it in order to react properly to the exceptions. An extension of this paper could be re-running the simulations in this experiment using different underlying ad hoc routing protocols and comparing the results. Particularly interesting would be the effect of incorporating an algorithm such as PARO. From vrg3@cornell.edu Tue Oct 22 11:58:45 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MFwjh20860 for ; Tue, 22 Oct 2002 11:58:45 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA06285; Tue, 22 Oct 2002 11:58:42 -0400 (EDT) Date: Tue, 22 Oct 2002 11:58:42 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 40 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents MagnetOS, an operating system for wireless power-limited sensor networks. It implements a distributed Java Virtual Machine which separates the objects in a Java application so they can be implemented on different nodes of the network. These objects are positioned at various nodes in an attempt to minimize power usage by the nodes' radios. During each epoch, the amount of network traffic between nodes is remembered. Then, this information is used by a migration method. Two migration methods are presented, NetPull (which allows network traffic to "magnetically attract" objects) and NetCenter (which moves objects straight to the source of the traffic). Inside nodes can be condensers, which process data passing through, aggregating and/or filtering it. It would be interesting to add some awareness of remaining power to this system. This way you could have a heterogeneous mix of high- and low-power nodes (even base stations). From adam@graphics.cornell.edu Tue Oct 22 12:02:18 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MG2Ih21991 for ; Tue, 22 Oct 2002 12:02:18 -0400 (EDT) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id g9MG2C0k077148 for ; Tue, 22 Oct 2002 12:02:13 -0400 (EDT) Date: Tue, 22 Oct 2002 12:01:55 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 paper 40 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII A single system image jave operating system for sensor networks This paper's main contributions are that it builds a single operating system (java based) out of an entire group of sensor nodes that have different processing abilities, life and usage availability. It uses adaptive processing to try and balance the load amongst the nodes. It further implements the descrived ideas and shows how this system works to achieve its goals. The basic idea behind the Magnet OS is to partition the work of a java program by making each class "portable" and assigning in to an available (and able) node to process. Each time a cross class call or instantiation is made there are JVM rewrites to hook into the OS find the appropriate node, ship the data to it and continue processing. There are two different adaptation algorithms that were provided NetCenter and NetPull. Both are epoch based algs. The overall idea is to migrate classes, and information closer to each other based on how much inter-exchange of data goes on between them. Netpull does this by observing link level activity and moving one hop at a time in the direction which greatest communication (indicating activity) was. Netcenter is a network based alg and moves things multiple hops, netcenter examines the whole network level activity and then adjusts the network accordingly at the end of the epoch. This paper presents some great new ideas. The distributed JVM in an adaptive environment is especially attractive. I think that it exploits the advantage the each node has some processing power and that all nodes can do some work. There is also the notion that this can be used to limit replication of work. MagnetOS could be easily extended to try and minimize duplicate calculations from different sensor nodes through caching or broadcasting results. I further think that both netPull and netCenter as adaption algorithms (based on minimizing path length) provide impressive results over using static processing in a network. One of the downsides to MagnetOS which was obvious to me, but maybe not to the designers was the lack of modifications to the underlying routing alg. AODV (or any alg) could have been modified to help provide some sort of usage, power and availability data about each node assuming a netCenter alg scenario. This could have been weighed into the calculations of the algorithm and cost-benefit could have been done w/ relation to killing a node off (due to moving the class to it) or saving it to simply collect data and pass it off the work to other nodes. The idea of a "node hierarchy" in which nodes have multiple importances (like how much "unique" area they sense coupled w/ how much battery life and processing power they have) could easily be worked in. This could hopefully easily be implemented into further versions of this work. I think a next step for testing would be to actually deploy this into the real world. The Defrees Hydrology Lab (basement of Hollister) has sensor networks on lake ontario and on cayuga lake, it would be interesting to see how this system works in an actual uncontrolled situation. From sc329@cornell.edu Tue Oct 22 14:00:46 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MHi5h17412 for ; Tue, 22 Oct 2002 13:44:05 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id NAA03167 for ; Tue, 22 Oct 2002 13:43:57 -0400 (EDT) Message-Id: <5.1.0.14.2.20021022133920.0281fbb8@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 22 Oct 2002 13:44:07 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 40 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth CHandrakumar This paper describes the design and implementation of power-aware adaptive distributed operating systems for sensor networks. Adapting to dynamically changing conditions by changing the distribution of components across a network is critical for many distributed applications. Static assignment of components to nodes are fragile and energy inefficient. Also locally optimised policies to share a common network may lead to globally unstable system behaviour. This system consists of the following components: MagnetOS implements a single system image operating system . It partitions a single monolithic operatic system and distributes it across the ad hoc networks. The partitioning of applications is done at a class granularity. The transformation is done at the byte-code level. This partitioning can be done offline since it need to be done only at the time of code injection. For each class , MAgnetOS creats an instance, a remote stub, an interface and a class object. The remote stub is used to make procedure calls to objects residing in other nodes. Apart from these components, a MagnetStaic object is also created, which contains the static field members, which are shared between all instances. MagentOS Runtime provide the dynamic services that facilitate the distributed execution of componentized applications across an ad hoc network. It does inter-compoenet communications, object migration, garbage collection, naming and object discovery. All objects are initially created locally, and then migrated to various nodes over time. Migration is done by serialization. The run time also assists in collecting the information on the amount of data it exchanges with other components. Migration algorithms : NetPull and Netcenter.Basically they both shorten the mean path length of data packets by automatically moving communicating objects closer together.Netpull collects information about the communication pattern of the application at the physical level , and migrates components ove physical links one hop at a time. NetCenter operates at the network level, and migrates components multiple hops at at time. Netcenter finds the host with which a given object communicates the most and migrates the object directly to that host. Both the algorithms are epoch based, so the duration of an epoch should be calculated judiciously. This a very very interesting proposal that implements a java virtual machine interface on top of a collection of sensor nodes. The simulation results show impressive performance of this model compared to other static and random approaches. Thought the paper mentions about object discovery and lookup, it doenst explain how these things implemented. It doesnt talk about any object repositories, from which a remote client can find out and invoke procedures on remote objects. From ks238@cornell.edu Tue Oct 22 14:52:13 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MIqDh08922 for ; Tue, 22 Oct 2002 14:52:13 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id OAA12142; Tue, 22 Oct 2002 14:52:09 -0400 (EDT) Date: Tue, 22 Oct 2002 14:52:09 -0400 (EDT) From: ks238@cornell.edu Message-Id: <200210221852.OAA12142@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: ks238@cornell.edu Reply-To: ks238@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: ks238@cornell.edu X-Originating-IP: 128.84.99.98 Subject: 615 Paper #40 In this paper, we once again examine extremely resource starved sensor networks. Hence, the idea of memory, bandwidth and processing space is extremely limited and its conservation is of central importance. The paper presents a distributed operating system, MagnetOS, which is designed for sensor networks and has design goals of being efficient, adaptive, general purpose (i.e. supporting multiple applications), and platform independent. The paper proposes MagnetOS to be an abstraction of a single JVM across the entire network available for applications (i.e. hence making it a single system image). A key feature to this distributed OS is the use of static application partitioning. With this mechanism JAVA applications are broken into components and based on a partitioning which conserves energy, the components are migrated to different areas in the network. Runtime mechanisms facilitate component creation, migration, communication, collection, naming and other important functionalities for independent components. In order to account for mobility, nodes interact with each other through a special RPC package which allows for the reorganization of communication endpoints as components move in the network. These algorithms (NetCenter and NetPull) are all employed in order to allow component migration so as conserve energy and increase system longevity. This is done with the use of epochs at each node that calculate the amount of energy consumed by a certain objects and chooses a correct algorithm accordingly. This is key contribution of the paper. This algorithm prevents one node or a cluster of nodes from being excessively exhausted and exploited due to its central location. I would be interested in learning more about networks which scale more and with higher degrees of mobility, although this may not be true for sensor networks. I think that another area of research is the application of such distributed OS (i.e. single system images) to non-sensor networks. From linga@CS.Cornell.EDU Tue Oct 22 15:00:43 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9MJ0gh11962 for ; Tue, 22 Oct 2002 15:00:43 -0400 (EDT) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g9MJ0fF15178 for ; Tue, 22 Oct 2002 15:00:41 -0400 (EDT) Date: Tue, 22 Oct 2002 15:00:41 -0400 (EDT) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 40 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII MagnetOS -------- This paper talks about design and implementation of MagnetOS, a distributed OS for sensor networks. Main design goal is to reduce energy consumption and increase system longevity. The way they achieve this is dynamic placement of components (of applications) i.e. where and when to place the components in a sensor network. Design goals of an OS for energy-constrained sensor network environment: efficient (less power consumption and longer system life), adaptive (adapt to changes in network topology, communication patterns etc automatically), portable (platform independent) and general purpose (backward compatability with centralized applications and also supports a host of new applications). Main idea to achieve these goals is to provide the abstraction of a single unified JVM. The challenge here is to provide this abstraction over an network of heterogenous, potentially mobile, physically separate nodes. This is done using a two-step process. First step involves statically partitioning the application into components. These components are distributed and executed at different hosts in the adhoc network but the application semantics are still preserved. Unit of mobility is a class object because partitioning is done at class granularity. The second step involves co-ordination and migration of these components to maintain application semantics (so the distributed version is similar to running the application on a single machine). MagnetOS runtime provides dynamic services necessary to achieve this. Some of the services provided by MagnetOS runtime are: component creation, inter-component communication, object migration, garbage collection etc. Standard routing protocols were used to provide multi-hop routing. Migration of objects in the dynamic environment of adhoc networks is not well-supported by standard RMI. So authors developed their own RPC package. Two algorithms (NetPull and NetCenter) have been proposed which could be used to migrate components using the information gathered by run-time to increase system life. Main idea is to move communicating objects closer to reduce overhead and delay. Simulation results presented show that this OS helps conserve power and achieves a factor of 4 to 5 improvement in system longevity. Pros&Cons: A new distributed OS which improves system longevity has been proposed in this paper. Concept is interesting and works quite well for small number of nodes in some scenarios. Scalability and other issues still need to be addressed. From egs@CS.Cornell.EDU Thu Oct 24 19:02:51 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g9ON2ph02208 for ; Thu, 24 Oct 2002 19:02:51 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id g9ON2ok04574 for egs; Thu, 24 Oct 2002 19:02:50 -0400 (EDT) Date: Thu, 24 Oct 2002 19:02:50 -0400 (EDT) Message-Id: <200210242302.g9ON2ok04574@zinger.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 Paper 40 >Date: Mon, 21 Oct 2002 23:53:22 -0400 >To: egs@cs.cornell.edu >From: Hubert Sun >Cc: 615 Paper 40 > >This paper introduces MagnetOS, a distributed operating system designed >for sensor networks. Sensor networks differ from regular wired >distributed systems in that they are resource limited, especially in >power. It has been identified that most power consumptions is due to >communication. MagnetOS tries to extend a system's lifetime by moving >objects where communication is kept to a minimum. > >MagnetOS is implemented as a distributed java virtual machine. A java >application is partitioned into the granularity of object instances. At >the partitioning phase, each class is translated into a remote >object. Like Java RMI, there are stubs (MagentPole), an interface (Magnet >Interface), and the instance of the object Magnet. Because static >methods, are also needed, static methods of a class are encapsulated in >their own class (MagnetStatic) and is handled like another >object. Objects can now move around in the network and it is the job of >the Magnet Pole to track them down. Application partitioning takes place >at the binary level and is therefore transparent to the user. However, >the system does provide an interface where a developer can specify >components to bind to specific nodes. > >Two movement object models were looked at: NetPull and NetCenter. They >were compared to Static (objects were statically assigned to nodes) and >Random (objects are randomly assigned to nodes). Both NetPull and >Netcentre decide where to move an object based on communication >information collected during a certain time interval (epoch) at each >node. At the end of each epoch, NetPull moves an object instance one hop >closer to where most messages are coming from and sent to. NetCentre >moves an object directly to the node where there is the most activity >pertaining to that object instance. In both cases, the idea is to lessen >the communication overhead (and therefore power consumption). Obviously >the length of an epoch is very important. As one that is too short might >make an object move around unnecessarily, while a long one may cause the >system to waste energy in communication. In the simulation, it was shown >that NetPull and NetCentre outperformed Static and Random techniques by >extending the systems lifetime by 4 or 5 times. > >One issue that this paper didn't address was failure. What happens if a >node with an object instance dies? Perhaps when a node knows that its >lifetime is becoming short, it can start to replicate the instance to >other nodes. Some questions that can be asked are: Which node becomes the >owner of the instance next? How many replications of the object instance >is necessary? How do you replicate the object instance data to make sure >it is consistent?