DARPA/NIST Invitational Smart Spaces Workshop, July 30-31, 1998, Gaithersburg, MA
Adaptable Protocols for Smart Spaces
Mitchell Tsai, Mark Yarvis, Peter Reiher, Gerald Popek
Computer Science Department
University of California, Los Angeles
Los Angeles, CA 90095
http://fmg-www.cs.ucla.edu/
3
DARPA/NIST Invitational Smart Spaces Workshop, July 30-31, 1998, Gaithersburg, MA
ABSTRACT
Human languages have an adaptability and resilience far surpassing current electronic protocols. Techniques based on human dialogue can assist in solving protocol creation, translation, and update problems for long-lived smart space devices. Devices will probably exist within environments which are similar to human communities, where communications are often facilitated by third parties, regulatory committees, and information repositories, but where external mediation is sometimes unavailable. Rather than relying solely on pre-tested protocols and secure transmission, smart devices can internally test protocols for faults, borrowing techniques from existing hardware and software simulation languages and from Artificial Life simulation environments.
- ADAPTIVE COMMUNICATION
Adaptive communication between electronic devices must recognize and respond to dynamically changing relationships among a wide variety of devices. For systems which can exist and function over decades, communication protocols should be able to automatically upgrade, even handling devices which do not yet exist. Also, we would like to minimize the massive maintenance and upgrade costs of current-day computer software.
One innovative approach is creating adaptable protocols which automatically discover and learn by trading agents which operate in internally simulated environments within each device. When no common protocols exist which are powerful enough for the desired communications, these agents try to establish communication within simulated environments, trading meta-information directly when possible, and communicating final results back to the original device.
Current communication protocols suffer from many limitations which do not exist in human languages. Consider modem communication. There are some limited negotiations when two modems communicate to adjust bandwidth and compression, but the protocols are preloaded onto modems and suffer the following problems:
· Incompatibility - When two different protocols are used, the result is usually complete miscommunication. Switching protocols may be possible, but only if they are preloaded. Even with the same protocol, many parameter settings must be correctly aligned beforehand, or communication will fail.
· Upgrade problem - Devices can not discover incremental changes in protocols. Instead, protocols must be completely replaced through software or hardware upgrades.
· Centralized protocol creation - Protocols are created off-line by humans. There are no means for individual devices to negotiate and create new protocols when current ones fail. When standards for new communication speeds are still being negotiated, manufacturers produce modems which must be upgraded when final standards are set. If two devices meet and one requires IR communication but the other requires wireless radio, successful communication may require third-party negotiation and the creation of hybrid protocols.
· Internal faults - There is no means for correcting a protocol which is inherently faulty or lacks the necessary capability to communicate with a new device which can not be described by the current device interface standard.
Human language systems have strong learning capabilities. New words are discovered and learned. New meanings can be learned for old words. When two people who speak different languages encounter each other, they can shift to a common language. If no common language exists, they create a pidgin language for temporary communication. If people continue using the pidgin language, it begins to take on the full power of a permanent language, developing into a creole.
In contrast, device languages and computer standards tend to be pre-designed, fairly limited, and overly long-lived (e.g. IPv4 to IPv6).
A typical approach is for a "far-seeing" company or committee to design a communication standard, with some means for exporting device interfaces. An attempt is made to anticipate all possibilities, incorporating the reasonable ones into the standard. The communication protocol is completely analyzed beforehand, so that it satisfies efficiency, correctness, and fairness requirements for the target environment. The decided standard is often used longer than desired, since the cost of switching to new standards is often very high.
Object-oriented languages and component-based communication systems provide some adaptability [1, 2], but "The current general way to describe interoperability information is to provide the component's interface definition and some additional informal documentation. This level of information is obviously not detailed enough to manage interoperability issues on a reasonable level... At the moment, a general established technique for the complete description of semantic interoperability of components does not exist."[3]
"Systems such as CORBA, OLE, and SOM define the interfaces they provide to other components, but not the interfaces they require from other components."[4] They also don't provide a mechanism for creating new interfaces and updating old interfaces. Interfaces may need to be established in a two-way process. Dynamic linking is just a start towards fully dynamic communication [5, 6].
- POSSIBLE APPLICATIONS
AND BENEFITS
Communication is simulated environments can occur much faster than real world communication, so protocol discovery can occur without tying up real-world bandwidth.
With adaptable protocols, groups can independently develop mobile computers and intelligent objects before worldwide standards are established. Two-way definition of interface languages provide extended flexibility for future environments.
- MAJOR TECHNICAL OBSTACLES
We want introspection, inspection, and communication methods which can establish initial communication with foreign devices, as well as trade the meta-information necessary for full communication. Our adaptable protocol system should be robust enough to redesign itself in all major areas, while maintaining self-check mechanisms and safety fallbacks to survive crashes and problems.
- PLAUSIBLE APPROACHES
4.1. Initial Communication
Some basic signals should be semi-reserved for "SOS" and "Query" commands, but these can also be flexible. For example, human languages don't even have the same words for "help", "yes", and "no." There is no a priori need for computer languages to have identical ones either. Devices can help each other learn the basic communication frequencies, encodings, signals, and words through Artificial Life techniques [7] and pattern detection algorithms.
A knowledge exploration system (using decision trees, Bayesian networks, expert systems, parallel simulated search etc...) can guide devices through the proper questions to ask when learning the details of a new protocol, or when learning modifications to an existing protocol.
4.2. Protocol Learning in Simulated Environments
Protocol learning and adaptation can be done through the trading of agents, rather than communicating over electrical or electromagnetic space, especially in insecure or noisy environments. The communication is simulated environments can take place much faster than real-world communication.
After initial communications are established, agents can be traded between devices. The agents can behave like the originating devices, learning and adapting protocols in simulated environments (which each device maintains), communicating the final results afterwards.
Some simulated environments can be very basic, others very complex. The protocol learning may occur in stages for very complicated languages, as communication may not just be "turn on the light", but may involve migrating InterJava 9.4 code. Initially a simple agent maybe sent for simulation environment A-1, but after one pass of negotiations, a more complex agent may be sent for simulation environment B-5.
4.3. Redesigning Communication Languages
Computer communication languages must develop the open-ended queries which are possible in human languages (and allow for their great adaptability). We can model the creation of new and hybrid protocols on human language discovery, rather than use fill-in-the-blank models of object properties and methods. Developing fill-in-the-blank templates are great, but we need methods to overcome their limitations, as well as methods to create templates when they don't already exist.
Open-ended and specific queries should be an integral part of the communication languages. "What does X mean?" "I am speaking a local version a7 of XYZ 1.32. Which version of XYZ 1.32 are you using?" "What are the differences between our versions of XYZ 1.32?" "Help!" "What are you doing?"
Languages should have response systems that detect attempts to communicate, distinguishing them from actual communication using known protocols. Basically, meta-questions and meta-answers.
4.4. Third-party (Network) Assisted Communication
Version control and replication systems [8, 9, 10] are needed to maintain and spread knowledge of multiple communication protocols. Individual devices do not need to know all protocols, but they should keep knowledge of the ones they are most likely to encounter.
Also, they may need to contact central repositories or other devices to learn (or relearn) protocols [11]. "I have contacted some device speaking a WX-type language, but have deleted my WX languages and can not figure out how to communicate with the WX device. Can you send me the latest WX negotiation protocol? I am having trouble with the encoding scheme."
"Device X has a 'verify' operation which I do not recognize. What is it? Can I reproduce it using my 'read' and 'write' operations?"
4.5. Internal Protocol Testing
Individual smart devices can test protocols for faults in internal simulations, borrowing techniques from hardware and software simulation languages (i.e. Maisie) [12] and Artificial Life [13] simulations. Rather than relying solely on pre-tested protocols and secure transmission, devices gain the flexibility to do partial or total internal protocol design with some protection, when communication might be impossible with existing well-tested protocols.
Secure codes will still be useful for transmitting worldwide or large-area updates to major communication protocols, and trusted repositories and other devices will use various levels of security methods in ordinary communication.
References
1. Bosch J., "Language Support for Component Communication in LayOM", 10th Annual European Conference on Object-Oriented Programming (ECOOP '96), July 1996.
2. Weck W., "Independently Extensible Component Frameworks," 10th Annual European Conference on Object-Oriented Programming (ECOOP '96), July 1996.
3. Murer T., Scherer D., Wurtz A., "Improving Component Interoperability", 10th Annual European Conference on Object-Oriented Programming (ECOOP '96), July 1996.
4. Olafsson A., and Bryan D., "On the Need for 'Required Interfaces' of Components", 10th Annual European Conference on Object-Oriented Programming (ECOOP '96), July 1996.
5. Diniz P. and Rinard M., "Dynamic Feedback: An Effective Technique for Adaptive Computing," Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '97), Las Vegas, NV, June 1997.
6. Fisher J., "Walk-Time Techniques: Catalyst for Architectural Change," Computer, September 1997, pp. 40-42.
7. Dyer M., "Grounding Language in Perception," Artificial Intelligence and Neural Networks: Steps toward Principled Integration, eds. V. Honavar and L. Uhr, Academic Press, NY, 1994, pp. 455-482.
8. Ratner D., "Roam: A Scalable Replication System for Mobile and Distributed Computing," UCLA Computer Science Department Ph.D. Dissertation, UCLA Technical Report CSD-970044, 1998.
9. Reiher P., Page T., Popek G., Cook J., and Crocker S., "Truffles -- A Secure Service for Widespread File Sharing," Proceedings of the Privacy and Security Research Group Workshop on Network and Distributed System Security, February 1993.
10. Reiher P., Popek G., Gunter M., Salomone J., and Ratner D., "Peer-to-Peer Reconciliation-Based Replication for Mobile Computers," ECOOP '96 Second Workshop on Mobility and Replication, July 1996.
11. Alwan A., Bagrodia R., Bambos N., Gerla M., Kleinrock L., Short J., and Villasensor J., "Adaptive Mobile Multimedia Networks," IEEE Personal Communications, April 1996, pp. 7-22.
12. Liu W., Chiang C., Wu H., Gerla M., Jha V., and Bagrodia R., "Parallel Simulation Environment for Mobile Wireless Networks," Proceedings of the 1996 Winter Simulation Conference WSC '96, eds. J. Charnes and D. J. Morrice, Coronado, CA, 1996.
13. Werner G. M. and Dyer M. G., “Bioland: A Massively Parallel Simulation Environment for Evolving Distributed Forms of Intelligent Behavior," in Massively Parallel Artificial Intelligence, eds. H. Kitano & J. Hendler, AAAI Press / MIT Press, Menlo Park, CA, Chapter 10, 1994, pp. 317-349.
3