Posts Tagged ‘ad-hoc

Mobile DTN Routers: Data Mules

The concept of a mobile router has been discussed among researchers of ad-hoc and mobile Internet networks for some time. When operating in the context of Internet-style protocols, mobile routers generally present challenges with respect to node addressing and routing performance when the topology or link performance changes. These challenges have their analogues in DTN, but with a some what different set of constraints. Once again, while we can learn from the approaches considered for ad-hoc routing and Mobile IP, the applicabilityof these approaches are limited because generally speaking the network model for these efforts is the traditional (static) network where the nodes are fully connected.

In the context of DTN, a mobile router is a device capable of store-and-forward operations, and thus represents more of a data carrying entity instead of a conventional router that may happen to be moving among. These data carrying “routers” have been called Data Mules. This term has emerged to describe situations where some entity (the mule) provides storage for messages that is physically moved from point to point to provide transit connectivity. This method of message transport is not purely academic fantasy: the DakNet project connects hard-to-reach villages via limited range RF transmissions from a portable computer ona commuter bus that performs store-and-forward data transfers (via smtp). In another example, the Wizzy Digital Courier project in South Africa transfers e-mail messages and Web searches on a USB key that is carried by a bicycle or motorcycle rider between schools. Finally,the postal system has been been proposed as a viable message carrying entity, and entire computers are sometimes shipped in order to move very large quantities of data. The benefit of data mules is essentially the possibility of extremely high capacity and throughput in exchange for large delivery delays.

While the DTN architecture embraces the concept of data mules, it appears to suggest abstracting them as edges in the DTN network multigraph. This may seem most appropriate, as the mule intuitively appears to be a communication link with a particularly high delay (and possibly high capacity). However, a mule generally has finite storage which is unequal to its bandwidth-delay product. We therefore consider the following question: Should the Data Mule be modeled as a node or a link ?

A network link (graph edge) is generally characterized by its delay and throughput and the vertices it interconnects.These edges are directional, so that different performance characteristics can be captured for asymmetric bidirectional links. Links are typically considered to be passive in that they execute neither a path selection nor scheduling decision process. Nodes, conversely, tend to be thought of as active entities (with finite storage) that make forwarding decisions about the messages transiting through them.

Using the active/passive characterization of nodes and edges, it then seems natural to represent a mule as a node instead of an edge, given its activity with respect to message routing. If we apply the same reasoning to passive entities (e.g. USB drives or DVDs), then we naturallyconclude they should be characterized as edges. However, as we shall now explore, this method of partitioning may reveal a false dichotomy.

To make effective forwarding decisions, nodes should maintain state about their communication contacts andact on this state as necessary. This is straight forwardly implemented for an active device (bus with computer aboard), but less clear for a passive device. Taking aUSB drive as an example, it is fairly simple to arrange for the drive to store state representing, at a minimum,the set of nodes that it has (and/or will likely) encounter.With this in mind, there is little fundamental distinction between a USB drive (passive, storage only) and a router equipped bus (active, storage and processing) both can be considered mules. One could easily imagine a software architecture wherein inserting a USB drive into ahost machine causes that host to automatically make aset of forwarding decisions based on state stored on the drive itself. In this way, the USB drive (in conjunction with its host) resembles a message router that employs check pointing to persistent storage. In other words, the USB drive is a node that remains dormant until “activated” by a host.

Thus, while the DTN architecture embraces the concept of mobile nodes and data mules, it does not fully specify how they should be included in the network model. Through the careful consideration of mobility and mules, we have refined the DTN architectural description in order to provide a basis for the design of our implementation.

Tags : , , , , , , , , , , , , , , , ,

Mixing Batch and OLTP Queries

Tandem and Teradata have demonstrated that the same architecture can be used successfully to process transaction-processing workloads as well as ad-hoc queries. Running a mix of both types of queries concurrently, however, presents a number of unresolved problems. The problem is that ad-hoc relational queries tend to acquire a large number of locks (at least from a logical viewpoint) and tend to hold them for a relatively long period of time, (at least from the viewpoint of a competing debit-credit style query). The solution currently offered is “Browse mode” locking for ad-hoc queries that do not update the database. While such a “dirty_read” solution is acceptable for some applications, it is not universally acceptable. The solution advocated by XPRS, is to use a versioning mechanism to enable readers to read a consistent version of the database without setting any locks.While this approach is intuitively appealing, the associated performance implications need further exploration. Other, perhaps better, solutions for this problem may also exist.

A related issue is priority scheduling in a shared-nothing architecture. Even in centralized systems, batch jobs have a tendency to monopolize the processor, flood the memory cache, and make large demands on the I/O subsystem. It is up to the underlying operating system to quantizeand limit the resources used by such batch jobs in order to insure short response times and low variance in response times for short transactions. A particularly difficult problem, is the priority inversion problem, in which a low-priority client makes a request to a high priority server. The server must run at high priority because it is managing critical resources. Given this, the work ofthe low priority client is effectively promoted to high priority when the low priority request is serviced by the high-priority server. There have been several ad-hoc attempts at solving this problem, but considerably more work is needed.

Tags : , , , , , , , , , ,