CS 8803 E – Pervasive Computing with Distributed Sensors

Final Take Home Exam Solution (15% of your course grade)

Due: May 1, 2002 (before 5 PM), NO EXCEPTIONS!

NOTES:

1. The exam has to be done individually.

2. No consultation with fellow students beyond looking at the scribe notes on the web.

3. No one should post anything that can be deemed as potential solutions to the following questions on the web.

4. The completed answers can be submitted by e-mail before the due date and time.

5. Hard copies will also be accepted.

6. Enjoy doing the exam!

1. For pervasive computing to become a reality, it is desirable to provide network identity for every device. IPv4 has its limitations, which are apparently solved by IPv6.

(a) First explain the limitations and how IPv6 solves them.

(b) Second explain if these limitations of IPv4 absolutely warrant the introduction of IPv6. If not, why not? If yes, justify why the proposed workarounds for these limitations in IPv4 are insufficient?

(courtesy: Lenin Singaravelu)

1a) Limitations of IPv4

·Address space limitations: 32 bits => around 4 billion addresses and current population of earth - around 6 billion. So even with one device per person, we wont be able to assign unique addresses to everyone.

·Lack of support for QoS- To support multimedia services on the web, the network must provide us with a guarantee about the quality of service. At preset the Internet supports Best effort delivery only.

·Multicast communication is not very practical - As multimedia services become more popular, it will become impractical to provide each user with a separate multimedia stream in all cases. This calls for some form of multicast to optimize network usage.

·Security concerns- Most of the traffic on the web is not encrypted. Also, present day Internet is vulnerable to intrusions, connection hijacking, Denial of Service attacks etc.

·Routing table problems- Since a large number of C class addresses are being issued, routing tables are getting bigger.

·No support for mobility.

o How IPv6 solves them

·128 bit addressing: 64 * 10^36 addresses - This should solve the address space problem.

·Extension Headers to support QOS, security - Again, it is not a default feature, but there is support for QoS and security. For QoS, IPv6 enabled routers will have added responsibilities.

·Supports auto configuration, which simplifies Mobile IP. It eliminates the need for a node to advertise and distribute IP addresses in a foreign network.

·Since authentication is an integral feature of IPv6, source routing can be used. Which means that mobility can be managed transparently.

Workarounds in IPv4 and issues with each one of them.

i. NAT and CIDR for address space problem

Installing NAT means that the interior is not visible to the nodes outside. While this may provide some security and firewall type capability, Internet transparency is lost. There will be restrictions on connections, which may not encourage the growth of Internet.

NAT interferes with encryption- Encrypted TCP headers are not permitted in NAT. In some applications, which transfer IP address information in the data field (e.g. Kerberos), NAT will not work.

CIDR leads to inefficient processing at the routers. This is because routers now have to look up the whole routing table to determine the longest prefix match. IPv6 does not eliminate this problem as it also uses a CIDR type lookup and 128 bit addresses mean that space occupied at the routers and the lookup time will considerably increase. But
with faster processors and memory this is close to becoming a non-issue.

ii. Many multicast methods (PIM, DVMRP, Overcast) some of which incorporate QoS.

At present, most of the routers have support for multicast, but the multicast techniques are not efficient. Either they send packets all over the Internet (dense mode) or the path from the source to the sink is not optimal (sparse mode). IPv6 does not promise any solution to this, but it has the advantage of being designed with Internet-wide multicast in mind.

iii. IPsec for security.

Most of the connections in IPv4 do not use secure communication, which is the reason for many spoofed packets. IPSec hasn't really caught on with the majority of traffic. In the case of IPv6, with the use of the authentication header, this problem can be simplified.

iv. Mobility Support via Mobile IP.

Mobile IP provides support. But doesn't work well with NAT/ ingress filtering. IPv6 provides auto configuration which means there is no need configure a node as an agent to distribute addresses. Also IPv6 has better security, which means that source routing is now a viable option. This will greatly improve Mobility support.

Conclusion:

IPv6 does not provide solutions to all the problems in the current setup. With minor modification like making SSL connections mandatory, designating some well-known port numbers in NAT, one can improve IPv4, so that it works fine for some more years. But a compelling argument for the use of IPv6 is that it has been designed with the future in mind. When IPv4 was designed, many factors like size of the Internet, multimedia over the net, etc? weren't thought of, so all the solutions we have are hacks. This would mean that IPv6 would be able to outperform IPv4 in almost every area. My view would be to start upgrading to IPv6.

2. What is source routing in IPv4, and how is it used? What are some of the problems with source routing in IPv4 that limit its use for mobile IP? Do these problems apply to IPv6?

(courtesy: Bikash Agarwalla)

2. Source Routing

Source routing is a routing approach that doesn’t require an intermediate node to maintain a routing table. Before the source can send a packet, it has to know the complete route to the destination host. The source includes the routing information in the header of the packet. The routing information contains sequence of nodes to traverse. It gives intermediate nodes sufficient information to forward the packet. Source routing works in datagram or virtual circuit packet switching.

Problems with source routing in IPv4:

• IPv4 source routing option requires the receiver of the packet to follow the reverse path to sender along the indicated intermediate nodes. This means that malicious nodes using source routes from remote locations could impersonate other nodes.

Example : A is the source, C is the destination, M is the malicious node.

A ( A- B- C) ---------B-----------M--------(A-B-M-C) ----------C

M intercepted a packet and changed the source route. Now, all the responses from C will go through M. M can then drop those packets and send new packets with new sequence numbers to A. It will be able to impersonate C.

• Existing routers have very bad performance when using source routing.

These limit its use in Mobile IP. IPv6 solves these problems. IPv6 eliminates the need for source route reversal and let routers ignore options that don’t need attention. So, correspondent nodes can use routing headers without penalty. This allows the mobile node to easily determine when a correspondent node doesn’t have the correct care of address. Packets delivered by encapsulation instead of by source routing means that the correspondent node needs binding updates from the mobile node. In contrast to IPv4, in IPv6 mobile nodes send the binding updates to the correspondent node instead of the home agent. This allows for key management between the two nodes.

Since routers now can ignore some of the options, this improves the performance.

(a) Compare and contrast the design points targeted by Infopad, Itsy, and Compaq Backpaq.

(b) Discuss how the choice of the design point may have influenced the architectural decisions in each of these devices.

(c) If you were designing an embedded computing platform to serve as a data aggregator for sensors in pervasive computing framework, what design choices would you incorporate in your architecture?

(courtesy: Matt Wolenetz/Hasnain Mandviwala)

(a) Compare and contrast the design points targeted by Infopad, Itsy, and Compaq Backpaq.

Infopad is the instantiation of one extreme: limit computing power on the device to that required only to communicate and support I/O interfaces. Major design goals were to reduce the weight and power consumption, while incorporating wireless connectivity, usability in remote information access applications, and flexibility for research purposes. "Computing and storage resources are removed from the portable device and are placed on a shared, high-speed backbone network of servers that provide mass storage, general purpose computation, and execution of system- and user-level applications. No provision is made for local application execution and storage -- laptops, palmtops, PDAs and PIMs fundamentally differ from the InfoPad in this respect." (From "The InfoPad Multimedia Terminal: A Portable Device for Wireless Information Access"). Although the design goal implies the elimination of microprocessors from the InfoPad implementation, they actually included one to handle ONLY start-up initialization of the device, packet scheduling for transmission over the wireless radio link, and support for different link and media access protocols (including mobility support). Essentially, the InfoPad, although an extreme, is still a research platform, and the ability to rapidly prototype different protocol support provided by the use of a microprocessor outweighed their energy consumption concerns.

Itsy was designed to explore new applications and user-interface modalities enabled by advances in energy-conserving microprocessors in the domain of a mobile hand-held device. It was built as a research prototype, incorporating flexibility as a major design goal. In contrast to the InfoPad, Itsy runs a full operating system (can run Linux) locally. Complex, compute and memory-intensive applications such as speech recognizers, a JVM, and real-time MPEG-1 movie decoding can run on Itsy. InfoPad, while also a research prototype, targets support for such applications on a remote server backbone, significantly limiting the processor, memory, and power requirements of the handheld device. Although Itsy incorporates more computational power, many extensions were relegated to daughtercards to keep the Itsy core simple and small (only 70% larger than it would be if it contained only the battery and display).

The Compaq BackPAQ (prototyping platform for CRL's Mercury Project) builds on previous Itsy work and the Compaq iPAQ core handheld device. The BackPAQ unit itself provides extended I/O and memory capabilities to the iPAQ, including a CMOS camera, 32MB additional Flash memory, and additional expansion connector, 2 PC Card slots, an accelerometer, and incorporates an audio codec along with a headset connector. The driving goal of the Mercury Project is to extend the boundaries of pervasive wireless computing. To that end, the BackPAQ device, when coupled with PC Card(s) providing wireless support and the iPAQ core handheld device, is a full-fledged flexible hand-held device that has compute and interactive capabilities rivalling those of desktop machines of a few years ago. The Mercury Project pursues its goal in software as well by building on top of the Linux OS and including IPv6 capability for IPv6 mobility.

All three of these devices are platforms developed to explore the boundaries of mobile computing: the InfoPad seeks to minimize power and processing requirements on the hand-held device while using a wireless radio link to access remotely-accessed information (application displays, etc.). Itsy seeks to explore different user interfaces, keeping a flexible, powerful underlying core to facilitate local processing, application flexibility, and research software (including mobility support). BackPAQ extends the Itsy idea by coupling greater flexibility with mobility.

(b) Discuss how the choice of the design point may have influenced the

architectural decisions in each of these devices.

First of all, for the InfoPad, the goal of reducing complexity on the

mobile device perhaps influenced the artituctural design the most. As a

result, most of the processing functionality was transferred to servers

that communicated with the InfoPad as an I/O device for and input (speech

data/pen storkes) and output (display pixels). Almost all of the

processing occured at these backend servers. In turn, this led to the

reduced need for onboard powerful processors and only dedicated

peripherals were used to impove performance and energy consumption. The

PPU, as mentioned in (a), was used in place of a CPU not to process

information, but only to manage the various I/O peripheral devices. Since

communication between the InfoPad and its respective basestation was

simple I/O, class-based communication protocols were intorduced that were

configured to handle a "heterogenous mix" of I/O data. For example, the

protocols are aware of data-sensive packets that contained pen movement

information and also about error-resistant pixel packets that have a

lesser effect on performace if corrupted. There are also multiple level of

error controls (highest reliability geing a type-1 Hybrid ARQ protocol)

with "various level encoding schemes allowing bandwidth-intensive data to

be minimally encoded, while latency or content-critical data to be

maximally encoded." Furthermore, Infopad kept minimal stae information as

most software state was stored on the backend servers that hosted the

applications. This is turn allowed simpler harware requirements and

greater performance in term of power consumption.

The Itsy being a standalone device required a much powerful processor (a

StrongArm SA-100, 32-bit processor). The 32-bit processes allowed for

higher performance for number crunching applications like mpeg decoding.

However, since power was a primary concern, the Itsy architecture adopted

some unique power technique mechanisms. First of all, the StrongArm

processor could be run on a lower voltage (1.23V) but a limited clock

speed giving a 30% power saving for the overall computation. If

computational speed is not a major need (which is true most of the time,

except when running applications like vide decoders etc.), this is a very

useful hardware feature. The Itsy also has various sleep modes, ranging

from "deep sleep" where only the watchdog clock is awake, to turning off

specific peripherals that are not being currently used. It also has a

1-bit per pixel memory that is used to display a monochrome image on the

display when other subsystems like the processor are asleep. For

flexibility, the Itsy allows for addition of daughter cards that can add

functionality to existing featureset.

The iPAQ does not have many power saving features but instead focus most

on adding functionality. For easy of upgrade, the iPAQ has two PCMCIA type

II slots that allow is expansion to a large variety of peripheral devices

ranging from cd-burners to wireless connectivity. The Backpack is just

such an extension that adds a camera which can be used for video

conferencing. To add to the feature rich base, an accelerometer allows the

rotation of the windows in the display giving the added freedom for the

user to hold the device in whatever axis that he/she may find comfortable.

(c) If you were designing an embedded computing platform to serve as a data aggregator for sensors in pervasive computing framework, what design choices would you incorporate in your architecture?

The notion of a data aggregator is somewhat distinct from that of a handheld device. Although a handheld device can aggregate data, its primary function is to interact directly with users, providing information access and real-time interaction capabilities. A data aggregator is simply that: a collector/router of information. In the pervasive computing framework, a data aggregator could be simply an intermediate network router that performs data fusion, for example (although a Compaq BackPAQ would qualify as a data aggregator and a hand-held device at the same time). If I were designing a data aggregator for use in a pervasive computing framework, I would include the following design choices in my architecture:

-I would be sure to keep energy consumption minimization a high priority, unless the unit were to be deployed in a wired environment.

-I would be sure to keep communication flexibility as a primary design priority. Providing the ability to support different modes of wireless communication in a single unit would increase the utility of the aggregator by allowing it to directly support a broader range of remote, wireless sensors and uplinks.

-From the example the skiffs have shown, and from the growing complexity of embedded software, I would probably choose to have the aggregator run a well-known general purpose OS (such as Linux) to simplify systems-programming aspects while enabling more direct and local manipulation of sensor data. Such programs would most likely be components in distributed programs across more than one aggregator and possibly higher level entities, requiring robust development support provided by such an OS.

-From the examples provided by InfoPad's radio module flexibility and Itsy and BackPAQ's expansion flexibility, I would probably want to incorporate similar modular design and extensibility via PC Card/daughtercards to enable future adaptations of the core aggregator hardware to increase its utility and, hopefully, effectiveness.

(a) What are the key research issues in embedded software? Why are these new? What makes them interesting and/or hard research problems? Justify with real-life examples.

(b) If we have Java everywhere together with middleware such as CORBA, are the issues you identified in (a) still relevant? Why or why not?

(courtesy: Hasnain Mandviwala)

(a) Before beginning the discussion on research issues on embedded

software, we must first understand the underlying embedded hardware

requirements that exist at present. Embedded hardware is largely a set of

devices that are catered to a specific task and are required to perform

that task in a manner that is as efficient as possible. The task of

performing individual specific tasks alone makes embedded hardware range

in complexity and size from small sensors that measure temperature to

military surveillance satellites that perform image processing in real-time

(of coarse in hardware!). Each device talks to its recognizable set of

embedded devices in a specific manner. (For the temperature sensor, it

follows a certain I/O protocol to a SPI [serial peripheral interface]

device, while a satellite has its own way of communicating to other

satellites and/or military command receivers). To control these devices is

therefore a task that range significantly from device to device. This

setup brings out a resounding problem: dealing with heterogeneity. To make

embedded devices work together, one has to deal with different platforms

at one point. Inter-operability therefore becomes a key issue for embedded

software design that has recently come up as a major cause for concern in

the embedded world.

Linked with inter-operability is another concern; flexibility. Embedded

software interfaces should be generic enough as to allow the flexibility

for communication with other embedded software "components". For example,

if a piece of software driving some sensors (temperature/humidity)

conforms to a certain generic transport protocol, but is restricted to

communicate with only a predefined set of devices (namely the temp./humd.

sensors), then it would require a re-write of the embedded software to

make the infrastructure encapsulate other sensors (such as infra-red

radiation detectors).

Such flexibility usually requires some dynamic properties to be inherent

in the software design. For example, dynamic discovery should be an

active ingredient in the design of embedded software. Embedded devices are

largely plentiful, expendable and mobile, and as a result appear and

disappear in a given environment. When they appear in an environment, they

should be recognized by other sensors around them. Embedded software should

then adapt to this changed environment to the benefit of the device they

control. For example, if a user carrying a PDA crosses a sensors that has

data to send but not enough power to send it, the sensor should simply

transmit its data to the PDA in an attempt to use the PDA's higher TX

ability to get the message across. (something like a harmless parasite.

An analogy would be those fish that hitch a ride on sharks to get leftover

food).

Moreover, embedded software controllers should be smart enough to perform

tasks like data fusion, where it could merge its own data with data

received from neighbors to save on total transmission.

Reusability, which has relatively been an older issue is still a concern

with embedded software. With constantly improving hardware, embedded

software should be modular enough as to be able to evolve without need for

much revision. However, reusability of software has largely been addressed

only on higher paradigm levels. When the embedded software design comes in

contact with the hardware, little can be done to keep design goals to be

similar. However, this should lead to an effort for keeping the hardware

interfaces to be similar such that the overlaying software controllers have

the flexibility to be generic.

Security is yet another key issue which is relatively new as such small

devices have become abundant. For the example given above of sensors

sending data with a host PDA, it is important that the PDA is trust

worthy, and that there is some form of guarantee for the sensors that the

data would eventually reach its destination (the data aggregator).

Security leads to the question of privacy. Embedded software may become

generic enough such that all devices conform to one API, but if some of

the devices do not wish to share their information, that such flexibility

should most certainly be provided. One example I can think of is a passive

locator system, that wishes only to locate itself without letting other

sensors to know where it is.

These issues are more linked with the hardware but permeate all the way

through to the software layer:

1) Performance: Issues-issues, QoS

2) Power savings

(b) If we have Java everywhere together with middleware such as CORBA,

are the issues you identified in (a) still relevant? Why or why not?

Java everywhere would certainly ease the heterogeneity problem and CORBA

may even provide a certain level of dynamic resource discovery and

communication abilities between embedded devices but all the problems are

not overcome with the combination of there two. One must remember that

technologies like CORBA and Java that do provide inter-operability and

flexibility, come at high cost of efficiency. QoS properties such as

soft-real-time guarantees are sometimes required by embedded machines and

therefore they demand such resources from the embedded software that

control it. Security and reusability are also well addressed in CORBA and

Java (respectively) but they encompass only a small set of current

existing and common devices (cell phones etc.). All said, privacy still

remains a largely untouched issue and perhaps the most challenging of all

problems in embedded software design.

5. Once upon a time (and perhaps still!) CPU was the precious resource in a computer system. Hence the entire OS was designed around ensuring fair use of this precious resource. Fast forward to the year 2010. Energy is the precious resource. With this in mind sketch the design of an adaptive OS for a Personal Mobile Digital Assistant (PMDA) whose primary goal is to optimize energy use while making forward progress on a set of ubiquitous computing applications.

In answering this question,

(a) State your assumptions about this futuristic PMDA (architectural features, power requirements, etc.).

(b) State your assumptions about applications you envision running on the PMDA.

(c) State your assumptions about the QoS requirements you envision in these applications.

Your answer will be evaluated by its (a) originality, (b) creativity, and (c)

attention to OS details.

Due to the open ended nature of this question I am providing below some of the

answers I liked.

Answer 1: (courtesy: Bolot Kerimbaev)

Question 5: Personal Mobile Digital Assistant

Once upon a time (and perhaps still!) CPU was the precious resource in a computer system. Hence the entire OS was designed around ensuring fair use of this precious resource. Fast forward to year 2010. Energy is the precious resource. With this in mind sketch the design of an adaptive OS for a Personal Mobile Digital Assistant (PMDA) whose primary goal is to optimize energy use while making forward progress on a set of ubiquitous computing applications.

a) State your assumptions about this futuristic PMDA (architectural features, power requirements, etc.)

The PMDA design will be informed by the experiences in designing, building, and using Itsy, Mercury (BackPAQ), InfoPad, Apple iPod, Pocket PC devices, etc.

InfoPad demonstrated how far a mobile system could get without having any general-purpose computational resources of its own. However, its use is constrained to highly instrumented environments, with high-bandwidth wireless networking. Thus, PMDA will benefit from having its own computing power. On the other hand, the cyber foraging concept would allow the PMDA to take advantage of resources if they are available in the environment, further reducing its power usage. In Odyssey experiments, for example, delegating speech recognition to a remote host resulted in about 30-40% power savings. Such dual approach could make it possible to switch between using its own processor and delegating functionality entirely to the surrogates (or taking something in between). This could enable the PMDA to cover a wider range of applications.

If development of mobile chips continues per Moore’s law, we may expect performance of the StrongARM-like chip to reach the equivalent of the most powerful desktops of today. However, a more realistic estimate (because Moore’s law limits may be reached or because it may not be possible to maintain power consumption at the same level with increased performance) is to aim for performance sufficient for real-time speech recognition, i.e., at least 3 times faster than Itsy version 2.

The PMDA will have a high-speed networking support, to enable information access and to permit cyber foraging (when applicable).

Paralleling the Mercury (BackPAQ) project hypothesis, the PMDA will include a large capacity hard drive. Advances in hard-drive technology allow for energy saving and small form factor. For example, Apple iPod MP3 player has a 5 GB hard drive and a batter life of up to 11 hours, depending on use. This is achieved primarily due to aggressive power management. Another example, IBM’s MicroDrive packs 1 GB of storage into a CompactFlash II card form-factor. High capacity storage could be used for improving user experience (lower latency, higher quality information), power consumption trade-offs (under certain scenarios, e.g., repeated playback of a video), resilience to network availability (prefetch data), etc.

Itsy demonstrated that it is useful to be informed about actual power usage to make better decisions with respect to power management policies. Thus, the PMDA will support both power management and power monitoring. All components will be enabled for power regulation and monitoring, with known trade-offs. For example, hard-drive may be used for secondary (or tertiary) storage and not needed at all times (the main secondary storage may be the flash memory). Thus, it could be turned off most of the time. Furthermore, it can provide spin-down modes for accessing low-bandwidth data.

Odyssey and Itsy demonstrated value of combining various power saving techniques, termed “composable”. Thus, the Operating System support is critical for energy saving, since it will take advantage of and control the power management capabilities of components. The OS is the only one that knows about the various components in the system. Thus, it can make better decisions about the overall power profile, by selectively powering down individual components and re-enabling others. Characteristics of applications also play an important role in the effectiveness of power management decisions made by the OS. For example, if it is known that an email client only uses text-based terminal for display and interaction and communication for retrieving mostly small size messages, the system can be configured accordingly, only leaving the black-and-white text display and low-bandwidth communication option. While learning about a black-box application’s exact behavior is intractable, certain information can be inferred from the application code. For example, imported libraries may indicate that an application can use a certain piece of functionality.

Itsy’s session support allows viewing groups of applications together. Foreground sessions receive user input and can use output, whereas ones in background don’t get input and their output is suppressed. Thus, a simple screensaver (blank screen session) can provide power savings with low wake-up time (cost of switching to the previously active session). Changing the semantics of background applications, further savings could result, e.g., by putting them to sleep mode.

Breaking down abstractions may be yet another way to improve power savings and performance. Itsy, for example, uses a modified Linux ext2 file system, which provides additional information to the lower level device block driver, which enables better performance for the flash memory based file system. An interesting question is possible savings from the display technology. If an image on the display doesn’t change, it doesn’t need to update from the video memory (but it could be a minor power saving).

Programming idioms and paradigms may benefit applications designed for the PMDA. Aspect-Oriented Programming with support for the appropriate concepts may allow the application programmer to more directly encode trade-offs when various components are available and under different conditions. High level patterns may also aid in this. For example, a given function may be performed either in “terminal” mode (InfoPad style), or in fully self-sufficient manner (Itsy style). In addition to alternatives for various configurations, alternatives for various fidelities also need to be supported, since these result in significant savings, too (average of 36% savings in Odyssey experiments). However, since various applications have different savings based on fidelity reduction, it is necessary to know exact resulting savings to control the selection of the overall configuration (which devices are turned on/off, what power mode they are in, what algorithms are used in applications, and what fidelity is supported).

As the Palm and Pocket PC platforms demonstrated, the hand-held form factor of the PMDA will necessitate use of non-desktop interaction metaphors. Thus, additional burden will be placed on the infrastructure for supporting such modalities. Perhaps, some of these could be integrated into the OS specifically designed for mobile devices. Support for speech and gesture recognition is essential. However, other modalities are possible. Non-speech interaction techniques may be warranted because they are better suited for privacy (e.g., interacting with the device in a crowded environment). Thus, it is likely the PDMA will sport a rudimentary keyboard, smaller than the full qwerty, something on par with cell-phones or gameboy.

b) State your assumptions about applications you envision running on the PMDA.

In addition to the “usual suspects”, personal information management and communications suite, the PMDA of 2010 will undoubtedly cover more territory. Software that adapts, perceives, and predicts user intent. Prediction in general could be used to improve user experience and energy characteristics, especially through use of cyber foraging.

For example, the PMDA makes a prediction that a user will be accessing a remote database in the near future. It formulates the request and asks surrogates to prefetch data and perform initial computation on it. When the user actually goes to use that database (prediction was correct), the data is already available in the local surrogates, which decreases latency and reduces time necessary for the device to remain in idle loop (which, while providing power saving, still consumes more power than deep sleep).

The PMDA may be used for entertainment, such as video playback and gaming. These require either high bandwidth networking or large capacity storage. However, these highly engaging (attention and/or interaction) and long-duration activities go counter to the typical usage scenario for hand-helds.

Communications uses range from videophone to email. Both of these could support speech-based interface, but videophone would retain audio signal as is, whereas the email application would use speech recognition to convert speech into text (this conversion could take place on a remote host).

c) State your assumptions about the QoS requirements you envision in these applications.

The primary goal of the PMDA is user experience. Thus, more appropriate metrics for user experience need to be developed. These will be combined with the power requirements of individual components (both in hardware and software).

Admission control will ensure that only applications (tasks) that conform to these requirements will be accepted. For example, it is known that the device needs to remain operational for the next 1 hour, and the current load is low enough to allow that. Now, a new task is attempted. However, this task will cut the battery life to less than 1 hour. Thus, this task is not admitted. Alternatively, the currently running tasks may have specified the QoS variability they can tolerate. Then, they can adapt to allow for the new task to run and for the whole system to remain within the constraints.

Answer 2: (courtesy: Yavor Angelov)

Q5. Once upon a time (and perhaps still!) CPU was the precious resource in a computer

system. Hence the entire OS was designed around ensuring fair use of this precious

resource. Fast forward to the year 2010. Energy is the precious resource. With this in

mind sketch the design of an adaptive OS for a Personal Mobile Digital Assistant

(PMDA) whose primary goal is to optimize energy use while making forward progress

on a set of ubiquitous computing applications.

In answering this question, (a) State your assumptions about this futuristic PMDA

(architectural features, power requirements, etc.). (b) State your assumptions about

applications you envision running on the PMDA. (c) State your assumptions about the

QoS requirements you envision in these applications.

Sketch - a classic OS design (e.g. Linux) will serve the requirements, provided end-to-end

energy management is introduced.

Applications, the OS itself and drivers needs to be energy aware. This means there are

APIs for the apps and the drivers to give as much information as possible to everybody to

solve the global optimization problem of maximizing energy efficiency.

On the top, the applications define tasks. Energy is accounted for the tasks ultimately

receiving the services – be it services from other tasks or the OS or a device. API should

allow (as well as a general purpose interface in the OS) users to specify requirements

with respect to the execution plans of the tasks which could be such as:

- time-bound deadline (by 5pm Wednesday)

- flexible deadline (before battery runs out)

and for QoS-aware tasks also:

- recurrence schedule – (e.g. certain timeslot on the CPU every N milliseconds,

certain amount of bytes on the network interface every second etc.). these

schedules are collaboratively computed between the app and devices involved in

servicing the app using certain primary QoS attributes such as frame rate and

image size and continuously adjusted with actual statistics from the devices

- service degradation profiles - how do gracefully degrade performance for the

primary QoS attributes, re-negotiate the schedules. The profiles also specify

minimal acceptable values.

The OS periodically runs a optimization process (similar to the query optimization of

databases) which generates/modifies a schedule for the scheduler to follow.

Device drivers are important in that they export the power-related capabilities of the

devices – different power states (e.g. CPU clock rate, disk spin rate, etc.) and allocation

statistics (e.g. what banks of memory are currently used so to use them as fully as

possible before moving to other banks). Strategies for reducing power consumptions of

various devices are given here [1] and [2].

Of course the problem space for the optimizer is huge. Certain heuristic rules can be

applied to limit the options(e.g. power down hard drives after 5 seconds of inactivity.)

Still, the important idea is that the energy consumption of the entire system should be

partitioned in terms of user-recognizable tasks. All resource budgeting will be done in

terms of this consumption – a well-behaved application will give the OS a graph of

subtasks and subtasks involved in completing the major task (printing a file requires

subtasks 1. read the file, 2. render, 3. send to the spooler); each subtask will receive have

predicted power consumption and resource usage (in resource-specific units, such as CPU

cycles or packets) and all subtasks will be aggregated – this graph will be dynamic

following changes of intent from the user. The predictions will be adjusted with a

measurement infrastructure in the OS and input from the application in terms of what

remains to be done using the resource. In the worst case where the application is energy unaware,

the OS will time the application and measure the consumption of various

resources then the user will specify a goal of how long he wants the application to run the

given task and the OS will come up with a prediction. The user can, then, in the worst

case, observe predictions for each tasks in terms of total energy consumption until

completion and manually turn off certain tasks, or order the tasks in priority groups

(analog to CPU priorities). Then, the optimizer builds execution schedules by ensuring

that all tasks with a given priority will meet their goals before scheduling tasks with a

lower priority.

Several practical suggestions: - vary the time slice based on the QoS requirements. Make

it more granular if possible to avoid cache flushes. In the case of interactive applications,

compute automatic QoS requirements based on the types of user interfaces served – a

word processor requires refresh N times per second since the typing speed of a user has

some limitations. Don’t run user applications more frequently than necessary, to avoid

idle looping in the applications and save it for the OS which can then decide to power

down certain various devices.

- use more strong-typed languages and component frameworks; perform more aggressive

compile-time verification. general purpose protection mechanisms (e.g. memory

protection) can be avoided on PDAs that run small set of programs that can be well tested

beforehand.

- drivers to support external devices (such as a ‘nfs-client’ device) which can complement

or substitute for local devices (local hard disk) or an external device with more powerful

antenna to use to relay the network traffic for our PDA. These options can lead to more

options for the optimizer but as long as a general framework for a device exporting costs

and scenarios to the optimizer exists, a general-purpose optimization algorithm can

produce good enough (although not guaranteed optimal) schedules. Most likely it will do

better job than the user manually deciding which network interface to use, where to read

the file from etc. particularly because the schedules will be constantly updated.

Assumptions: the futuristic PDA will be an extended version of the Ipaq. It will have

many sensors integrated – GPS, camera, microphone. A lot of user interfaces will be

supported – voice recognition, face recognition (including for provision of feedback and

user intent – i.e. if the user is angry his facial expression will cause the scheduler to boost

the priority of the active task) and these will be implemented using custom chips.

Programming support will allow general purpose software to either use the hardware

acceleration provided by these custom chips (for example the voice recognition chip) or

use the general purpose CPU.

The applications will be variants of Microsoft Outlook (email, calendar-task planner),

NetMeeting (videoconferencing), Word, Excel, Project (project management), SQL

server (databases). Depending on the interface mode used (e.g. stylus vs. voice), a more

traditional interface to the application (similar to the desktop computer) or a more highlevel

interface (questions and answers with intelligent suggestions from the PDA) will be

supported (“do you want me to contact all your colleagues and rearrange the meetings on

“Wednesday”).

The QoS requirements of these applications depend on the interfaces they would use. If

they use the voice recognizer they automatically inherit the QoS parameters of the

recognizer – sampling rate of audio, CPU usage given a dictionary size, etc - which

depend on the degradation profile. The video-conferencing application will have similar

requirements but with a larger set of parameters.

References:

[1] D. Lee. Energy Management Issues for Computer Systems.

http://citeseer.nj.nec.com/434764.html

[2] J. Lorch and A.J.Smith. Software Strategies for Portable Computer Energy

Management. IEEE Personal Communications Magazine, 5(3):60-73, June 1998.

Answer 3: (courtesy: Jake Auxier)

The design requirements of a PMDA would be something akin to the design requirements of the Itsy. It would also need to have the ability of adding on other components like arrays of sensors similar to the BackPAQ. Thus, it would require a rather powerful processor to handle computations of large amounts of data. Also, it would require wireless networking capability, and a nice color display. These features would require a rather large amount of power. One can envision running any application on the PMDA. You may want to run anything from a simple electronic address book to a video player. Since one of its goals is to make forward progress on ubiquitous computing applications, it should have the capability of providing data such as location information to various applications in an environment. QoS requirements will vary on the application that you are using. The requirements should be degraded gracefully in the face of network or energy hardships. For instance, the video viewer may decrease the resolution and quality of the images as power gets low or network bandwidth gets low (if you are getting the video from an external source.)

An adaptive OS must be able to monitor all aspects of the hardware's environment that it is running on. It must be able to detect decreases in bandwidth as well as energy. It must also be aware the various operations it can do to deal with these decreases. Not only should it come with a set of standard techniques, but also applications should be able to provide their own set of techniques that they deem appropriate. The OS, though, should be able to supercede the application's techniques if it realizes the application's techniques will not suit the current energy state and use. The OS should provide the means for a user to specify the type of energy saving techniques he or she sees as appropriate. The user's requirements will always supercede the OS's requirements.

It is possible the user will exhibit patterns over time that the OS can learn and use to its advantage. For example, the OS knows that the user only uses low-energy, non-performance requiring applications in a certain block of time. The OS can then slow the processor during this time in order to save energy. Of course, if the user does something differently during this time that requires more processor speed (and thus falls outside what the OS has learned), the OS should adapt and provide the necessary speed. But, the OS should not erase what it has learned except to adjust what it has learned in some graceful manner. The OS may also be able to do prediction based on information it gets from outside sensors. If the OS knows the location of the user, it may be able to figure out that user will soon be using a power-hungry application and save energy before hand. The user's interaction with both the environment and the PMDA should be key in the OS's energy saving strategies.

Answer 4: (courtesy: Agathe Battisteni)

(a)

The device of the future is a handheld-size device, equipped with a touch screen but also a wearing screen/microphone/speaker/video camera module that will be set on the head. The main advantage is that the device may be quickly accessible (as today’s handhelds) by just awaking the screen, but for applications that are more usable when shown on bigger screen, the eye-screen (connected by a special optical fiber cable) is used. Moreover, the eye-screen is less power-consuming.

Some advances will have been made to augment batteries life, but the usability and mobility of the devices rely on the infrastructure: on campus, at work, in airports, at home, in banks, in specialized stores... where the connectivity had to be ensured by the Internet access and services providers to really get ubiquitous devices into the main market. When the device is not connected, enhanced optimization managers help saving power.

The device is for general-purpose applications, use a non-restrictive OS (linux, or maybe later an open PocketPC or WindowsCE or something equivalent), may integrate a JVM and a middleware such as Corba or Jini that allows the discovery of services, and also bluetooth or IrDa for device to device communications. Thanks to big enhancements for security and privacy concerns, people may use it in their everyday life to make payments, to consult their bank accounts, do phone calls, listen to music, send video, and play networked games.

To bypass the power and bandwidth limitations, the device works in two main modes:

• Autonomous, wireless, optimized power management (batteries) mode, reduced CPU frequency.
• Wireline/powerline connection: the device is directly connected to the network (for communication and power). The device batteries are recharged, and all power- and computation-consuming application may run without limitations. (conferencing, downloading of required modules, storage management...)

(b)

Applications:

• Making payments: credit/debit or a limited account. This feature is available in wireless mode, but the security is better when it is done in connected mode.
• Multimedia applications: music, video, movies (a DVD module may be attached to the device to play the movie on the eye-screen)
• Communication-oriented application: surfing, chat, emails
• Playing games
• Accessing secured services: consulting banks accounts
• Locating oneself (within a map), other (its family, or to meet people- i.e. at the airport), and services (stores, entertainment...)

(c)

The OS adaptivity is modeled with Intelligent Artificial techniques such as statistical algorithms (machine learning, Bayesian network or neural network) and a frame-based representation of the device.

The goal is on one hand to have the most accurate understanding of the energy consumption: this is made possible by getting low-level indications of the energy consumption about each particular piece of hardware (CPU, display, memory, external communication, internal communications...). This requires the addition of sensors or captors to get all relevant measures.

On the other hand, a comprehensible model of the energy consumption must be presented to applications.

The machine learning part aims at updating the models of energy consumption of the hardware. The model is a frame-based representation that gives several views of the energy consumption:

§ Per piece of hardware:

o Display (s)

o CPU

o Memory

o External communication (wireless card, wireline card...)

o Internal communication (to memory, to peripherals equipment...)

§ Per application/process

o OS main processes (file system, virtual memory management...)

o Communications processes

o Every running application

§ Per operation (relevant operations or presented as indices)

o To display 1k of data

o To send 1k of data, in wireless/wireline mode

o 1 hour of idle mode

o ...

It would be a burden to ask each application to manage its energy consumption, thus this is done by energy-aware managers on their behalf. An application starts a manager and parameterizes with a kind of policy file.

The model also includes a rate of remaining consumable energy. An energy coin defines the basic amount of energy that can be granted by the OS to the managers. Depending on how much energy the applications needs, they ask for a certain amount of energy. Because the OS and the applications may access the model of consumption, the energy is fairly distributed, because it is up to the OS to negotiate with the managers the amount of energy granted.

The managers must be trusted and implement themselves a certain policy to avoid the problems of unfair management. This way, managers implement a trusted code, that cannot unfairly act on the OS, but work for the applications sake.

We can imagine several types of managers that work differently depending on the connectivity mode (wireless/wireline). We can also imagine that managers may observe each other so that each manager may anticipate what other applications will request.

§ Guarantees an application to run at least a certain time.

§ Guarantees to execute an operation in a minimum amount of time.

§ Triggers the execution to maximize the efficiency of the resource utilization.

§ ...

More than presenting precise model of energy policy, this framework tries to distribute the energy-awareness among the different layers so that each party may access the information in the most appropriate form (low-level for hardware, lot of information for the OS, high-level for applications).

Answer 5: (courtesy: Lenin Singaravelu)

PDMA for the future:

Assumptions about the architecture:

Crusoe type processor that is very energy efficient, though performance-wise it may be a bit slower. e.g. features - Dynamic voltage switching, turning off functional units not in use etc?

Since the device is expected to be small, common bus should not consume energy. Again, there can be optimizations here so that an unused bus could be switched off or consume very low power.

Memory should be banked. And each of the banks could be switched off temporarily or move to a low power state.

All the controllers should be integrated with the processor to give a "computer on a chip" to minimize energy usage.

A HDD, that implements some form of energy saving mechanism like spin down.

Communication devices will mostly be RF based and there should be two types of RF cards on each system- a low range one and a high range one. Another option the Ultra wide band which could solve both problems at once as it consumes very low power and at the same it has better range.

The software:

OS: The OS will be micro-kernel based and as small as possible. It should contain a fair-share battery scheduler and a memory manager.

For this to happen, the application program should be divided into quanta by the compiler. This can be done by inserting special instructions in the code or using a bit in the Instruction Set of the architecture. Each quanta should contain at most one RF receive of transmit instruction or one block of read/write from the HDD. All packets have to be of fixed size. The energy consumed instructions in a quanta should be a proper fraction of the energy of a transmit operation. In short the energy consumed in a quanta can be at any one of the 3 levels

Normal Instructions

Peripheral read/write instructions

TX/RX instruction

And the instruction at the beginning to each quanta should contain information about what type of quanta it is.

The scheduler:

Each process on entry should register itself with the scheduler and inform it about the average number of quanta per second and the average energy that will be consumed. The scheduler should try to balance out the energy consumed in next cycle by considering the energy consumed in the previous cycle. There should be some from of priority support so that there can be some QoS guarantees. For e.g. in cellphone mode, the PMDA should provide the highest priority to the tx/rx application. The presence of quanta markings help the scheduler to switch it out of the run queue.

The scheduler must also have information about remaining battery life. Then using a goal oriented model, wherein the user specifies the amount of time he wants the device to keep running, the scheduler could deny permission to a low priority process that is already running, downsize CPU voltage or ask the memory manager to enforce stricter bank controls.

Memory Manager:

A program on starting up must provide information about its data set size. This will allow the MM to allocate memory such that fewer banks are used. This way when that process is running, it can power down other banks. Another option would be to use static RAM. An aggressive scheme would be transfer blocks from one memory bank to another so that some banks can be switched off. This would mean considerable overheads, but when just one process is going to run for a long time, this approach could save considerable amount of energy.

The banks could also be both horizontally and vertically split. This way one can power down larger portions of memory.

Communication Module:

Since it is a mobile device, it must contain some form of communication. The lowest power consuming one would be IR. But, given the unidirectionality and inability to use it outdoors, it would be tough to make a case for IR. So RF is a viable option. Within 10 years, Ultra Wide Band could become a reality. UWB consumes very less power. So may be the quantas described earlier could be the same. Still, the protocol stack has to be very lightweight, the number of copies has to be minimized. Routing in adhoc networks has to be energy aware. Each device must advertise its energy capability in the route advertisement packets. This way the end nodes could select the path that consumes the least energy, at the same time not using up too much energy at the intermediate nodes. This will work only in a cooperative environment. The other approach would be to place enough wired access points so that interdependence is greatly reduced.

Security: User access will be based on some form of biometric security system. Communication must be based on exchanging symmetric keys using a Public key encryption algorithm and then using symmetric key to communicate. All this should happen at the h/w level to reduce s/w overheads.

As seen above there should be extensive support from the compiler for this system to work. There are some QoS parameters that can be specified by the application but these are limited to specifying number of quantas that can be executed and the priority level. So all that can be guaranteed is that if the process priority is high enough, 'n' quantas will be executed. What is not specified is the voltage level at which it will run. So the application has to assume the worst case behavior (at least 2.5 V means use 2.5 V in all calculations even when 5 V's may be available) while calculating its quanta needs to achieve QoS.

Answer 6: (courtesy: Arnab Paul)

Futuristic OS for a PMDA

------------------------

Prelude :

---------

Energy consumption is most intimately related to the Hardware.

Low level mechanisms lie in hardware. However, higher level

policies can potentially make a lot of difference in the

energy consumption. Hence the need for a new OS.

Low power circuit design has long been a holy grail for

hardware engineers. And it has been observed ( an

obvious observation though )that reducing the dissipative elements

in the circuitry (such as resistance) causes less energy be wasted.

Given that all the dissipative elements are removed from

the circuit, the hardware becomes one that is reversible, i.e.,

the physical state can toggle back and forth without any

additional energy. An analogy is a no-damping spring that can

oscillate for ever without any boosting.

Given that no dissipation circuits are available, a further

ubiquitous source of energy dissipation is the way we write

programs. Landauer observed that whenever a bit is irreversibly

erased, i.e., the previous value is no longer known, a certain

amount of energy is bound to be dissipated. This is called logical

irreversibility. Bennett showed that it is possible to write

computer programs in a logically reversible way, where no information

is ever destroyed. Theoretically such computers (built on

a non-dissipative hardware ) will be the most power efficient ones.

Assumption

----------

Stretching the imagination for 2010, we assume that

quasi-non-dissipative hardware are in place. Which means

amount of energy spent for processing bits is negligibly small.

However, memory cannot be infinite, hence, not all information

can be stored for ever. However, electromechanical devices,

such as disks are bound

to dissipate energy. We cannot do much with display devices either.

Multiple processors can be bundled in a single PMDA.

Also, it will be really nice to have enough registers

to hold a kernel stack at least.

OS structure

-------------

Process Manager -

It should manage the threads/process so that

movement of data is minimized. Because bit processing eats less

power than data movement. Interprocess communications should

be done through registers sitting at close proximity to

the processors whenever possible. This will avoid memory

instructions.

Take help of cyber-foraging in power critical situation

if it is energy-economic to migrate a computation to

a backbone machine.

Voltage Scheduler Unit -

Depending on the cpu usage, a voltage/clock scheduler unit

can control the clock speed and the operating voltage, that

can optimize some power.

Hardware Monitoring Unit -

Like the voltage scheduler, this unit monitors different parts

of the hardware and turning them into different power modes

whenever necessary. This has to be done in both transparent and

on-demand way. Such as sleep modes for CPUs or memory banks etc.

Memory Manager -

Should adopt power aware memory allocation policy.

This is where the "reversible erasure" of information may

play a significant role. Instead of overwriting computational

states every time, if new memory is allocated till available,

this would push back the irreversible erasure - and hence

energy loss - as far as possible into the future. When the

system is really running low on battery, some critical tasks

might still be accomplished by optimizing power in this way.

Messaging Layer -

Can adapt different transmission policies.

For example, while sending data on wireless, the network

layer may selectively deliver more or less energy

depending on the distance the bits have to travel through.

Energy efficient routing optimizations are also expected

to help the overall power requirements.

.

.

.

.