You can also search the papers by keyword.
This page lists all of our papers that are relevant to the D'Agents project. The papers are divided into several categories.
The last update to this paper list was on Sat Jul 21 21:20:56 EDT 2007.
Copyright © 2001 by the authors.
gzipped Postscript
(65K)
|
PDF
(92K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/aslam:position.ps.gz
Abstract: This paper surveys the architecture and properties of intelligent information agents. A number of issues arising in the future design of general, programmable agents are presented. Examples of agent applications are given with some implementations. A formal model for information agents is developed briefly.
Copyright © 1994 by the authors.
gzipped Postscript
(156K)
|
PDF
(2629K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:architecture.ps.gz
Abstract: In most working and proposed multiagent systems, the problem of identifying and locating agents that can provide specific services is a major problem of concern. A broker or matchmaker service is often proposed as a solution. These systems use keywords drawn from application domain ontologies to specify agent service, usually framed within some some sort of knowledge representation language . However, we believe that keywords and ontologies cannot be defined and interpreted precisely enough to make broking or matchmaking among agents sufficiently robust in a truly distributed, heterogeneous , multiagent computing environment. This creates matching conflicts between a client agents' requested functionality and a service agents' actual functionality . We propose a new form of interagent communication, called functional validation, specially designed to solve such matching conflicts. In this paper we introduce the functional validation concept, analyze the possible situations that can arise in validation problems and formalize the mathematical framework around which further work can be done.
Copyright © 1999 by AAAI Press.
gzipped Postscript
(856K)
|
PDF
(125K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:functional.ps.gz
Abstract: The development of the World Wide Web has changed the way that we think about information. Information on the web is distributed, updates are made asynchronously and resources come and go online without centralized control. Global networking will similarly change the way we think about and perform computation. Grid computing refers to computing in a distributed networked environment in which computing and data resources are located throughout a network. Grid computing is enabled by an infrastructure that allows users to locate computing resources and data products dynamically during a computation. In order to locate resources dynamically in a grid computation, a grid application program consults a broker or matchmaker agent that uses keywords and ontologies to specify grid services. However, we believe that keywords and ontologies cannot be defined or interpreted precisely enough to make brokering and matchmaking between agents sufficiently robust in a truly distributed, heterogeneous computing environment. To this end, we introduce the concept of functional validation. Functional validation goes beyond the symbolic negotiation level of brokering and matchmaking, to the level of validating actual functional performance of grid services. In this paper, we present the functional validation problem in grid computing and apply basic machine learning theory such as PAC learning and Chernoff bounds to solve the sample size problem that arises. Furthermore, in order to reduce network traffic and speedup the validation process, we describe the use of Dartmouth D'Agents technology to implement a general mobile functional validation agent system which can be integrated into a grid computing infrastructures as a standard grid service.
Copyright © 1999 by Allerton Conference.
gzipped Postscript
(132K)
|
PDF
(1361K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:grid.ps.gz
Copyright © 1999 by IFORS.
No online copy available.
Abstract: Mobile agents are programs that can migrate from machine to machine in a network of computers and have complete control over their movement. Since the performance space of mobile agents has not been characterized fully, assessing the effectiveness of using mobile agents over a traditional client/server approach currently requires implementing an agent system and running time-consuming experiments.
This report presents a simple mobile-agent simulation that can provide quick information on the performance and scalability of a generic information retrieval (IR) mobile-agent system under different network configurations. The simulation is built using the DaSSF and DaSSFNet frameworks, resulting in high performance and great configuration flexibility. This report also implements a real D'Agents mobile-agent IR system, measuring the performance of the system. A comparison of these real-world performance results and those given by the simulation suggest that the simulation has good accuracy in predicting the scalability of a mobile-agent system. Thus this report argues that simulation provides a good way to quickly assess the performance and scalability of an IR mobile-agent system under different network configurations.
Copyright © 2004 by the author.
PDF
(361K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2004-499/
Copyright © 1995 by Robert S. Gray.
gzipped Postscript
(56K)
|
PDF
(151K)
URL: http://agent.cs.dartmouth.edu/papers/gray:agenttcl.ps.gz
Copyright © 1995 by Robert S. Gray.
gzipped Postscript
(125K)
|
PDF
(518K)
URL: http://agent.cs.dartmouth.edu/manual/doc.1.1.ps.gz
Copyright © 1997 by Manning Publishing.
gzipped Postscript
(93K)
|
PDF
(237K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/gray:bookchap.ps.gz
Abstract: Mobile agents are programs that can move through a network under their own control, migrating from host to host and interacting with other agents and resources on each. We argue that these mobile, autonomous agents have the potential to provide a convenient, efficient and robust programming paradigm for distributed applications, particularly when partially connected computers are involved. Partially connected computers include mobile computers such as laptops and personal digital assistants as well as modem-connected home computers, all of which are often disconnected from the network. In this paper, we describe the design and implementation of our mobile-agent system, Agent Tcl, and the specific features that support mobile computers and disconnected operation. These features include network-sensing tools and a docking system that allows an agent to transparently move between mobile computers, regardless of when the computers connect to the network.
Copyright © 1997 by IEEE.
gzipped Postscript
(64K)
|
PDF
(295K)
URL: http://agent.cs.dartmouth.edu/papers/gray:mobile.ps.gz
Identical to gray:mobile-tr.
See also later version kotz:jmobile.
Abstract: Mobile agents are programs that can move through a network under their own control, migrating from host to host and interacting with other agents and resources on each. We argue that these mobile, autonomous agents have the potential to provide a convenient, efficient and robust programming paradigm for distributed applications, particularly when partially connected computers are involved. Partially connected computers include mobile computers such as laptops and personal digital assistants as well as modem-connected home computers, all of which are often disconnected from the network. In this paper, we describe the design and implementation of our mobile-agent system, Agent Tcl, and the specific features that support mobile computers and disconnected operation. These features include network-sensing tools and a docking system that allows an agent to transparently move between mobile computers, regardless of when the computers connect to the network.
Copyright © 1996 by the authors.
gzipped Postscript
(64K)
|
PDF
(216K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR96-285/
Identical to gray:mobile.
Abstract: A mobile agent is an executing program that can migrate, at times of its own choosing, from machine to machine in a heterogeneous network. On each machine, the agent interacts with stationary service agents and other resources to accomplish its task. In this chapter, we first make the case for mobile agents, discussing six strengths of mobile agents and the applications that benefit from these strengths. Although none of these strengths are unique to mobile agents, no competing technique shares all six. In other words, a mobile-agent system provides a single general framework in which a wide range of distributed applications can be implemented efficiently and easily. We then present a representative cross-section of current mobile-agent systems.
Copyright © 2002 by the authors.
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-365/
See also earlier version gray:motivation-tr.
Abstract: A mobile agent is an executing program that can migrate, at times of its own choosing, from machine to machine in a heterogeneous network. On each machine, the agent interacts with stationary service agents and other resources to accomplish its task. In this chapter, we first make the case for mobile agents, discussing six strengths of mobile agents and the applications that benefit from these strengths. Although none of these strengths are unique to mobile agents, no competing technique shares all six. In other words, a mobile-agent system provides a single general framework in which a wide range of distributed applications can be implemented efficiently and easily. We then present a representative cross-section of current mobile-agent systems.
Copyright © 2000 by the authors.
gzipped Postscript
(231K)
|
PDF
(405K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-365/
See also later version gray:motivation.
Abstract: Ideally soldiers in the field would have portable computing devices, which, connected with a wireless network, would provide access to military databases, terrain maps, and other soldiers. In this report and the associated invited talk, the author presents some routing and mobilecode technologies that have been developed to support soldiers in the field, as well as the highly intelligent network-sensing and planning agents that will be needed to fully solve the networking problems.
Copyright © 2000 by IEEE.
gzipped Postscript
(148K)
|
PDF
(711K)
URL: http://cmc.cs.dartmouth.edu/papers/gray:overview.ps.gz
Abstract: One of the paradigms that has been suggested for allowing efficient access to remote resources is transportable agents. A transportable agent is a named program that can migrate from machine to machine in a heterogeneous network. The program chooses when and where to migrate. It can suspend its execution at an arbitrary point, transport to another machine and resume execution on the new machine. Transportable agents have several advantages over the traditional client/server model. Transportable agents consume less network bandwidth and do not require a connection between communicating machines - this is attractive in all networks and particularly attractive in wireless networks. Transportable agents are a convenient paradigm for distributed computing since they hide the communication channels but not the location of the computation. Transportable agents allow clients and servers to program each other. However transportable agents pose numerous challenges such as security, privacy and efficiency. Existing transportable agent systems do not meet all of these challenges. In addition there has been no formal characterization of the performance of transportable agents. This thesis addresses these weakness. The thesis has two parts - (1) formally characterize the performance of transportable agents through mathematical analysis and network simulation and (2) implement a complete transportable agent system.
Copyright © 1995 by Robert S. Gray.
gzipped Postscript
(136K)
|
PDF
(373K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR95-261/
Abstract: Building applications with mobile agents often reduces the bandwidth required for the application, and improves performance. The cost is increased server workload. There are, however, few studies of the scalability of mobile-agent systems. We present scalability experiments that compare four mobile-agent platforms with a traditional client/server approach. The four mobile-agent platforms have similar behavior, but their absolute performance varies with underlying implementation choices. Our experiments demonstrate the complex interaction between environmental, application, and system parameters.
Copyright © 2001 by Springer-Verlag.
gzipped Postscript
(361K)
|
PDF
(315K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/gray:scalability.ps.gz
See also earlier version gray:scalability-tr.
Abstract: Mobile agents are programs that can jump from host to host in the network, at times and to places of their own choosing. Many groups have developed mobile-agent software platforms, and several mobile-agent applications. Experiments show that mobile agents can, among other things, lead to faster applications, reduced bandwidth demands, or less dependence on a reliable network connection. There are few if any studies of the scalability of mobile-agent servers, particularly as the number of clients grows. We present some recent performance and scalability experiments that compare three mobile-agent platforms with each other and with a traditional client/server approach. The experiments show that mobile agents often outperform client/server solutions, but also demonstrate the deep interaction between environmental and application parameters. The three mobile-agent platforms have similar behavior but their absolute performance varies with underlying implementation choices.
Copyright © 2001 by the authors.
gzipped Postscript
(812K)
|
PDF
(1179K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-386/
See also later version gray:scalability.
Copyright © 1996 by Robert S. Gray.
gzipped Postscript
(61K)
|
PDF
(164K)
URL: http://agent.cs.dartmouth.edu/papers/gray:security.ps.gz
See also later version gray:security2.
Abstract: D'Agents is a mobile-agent system that is used primarily for information-retrieval applications. In this paper, we first examine two such applications, where mobile agents greatly simplify the task of providing efficient but application-specific access to remote information resources. Then we describe the D'Agents system, which supports multiple languages, Tcl, Java and Scheme, and strong mobility for Tcl and Java. After considering the D'Agents implementation, we present some recent performance and scalability experiments that compare D'Agent mobile agents with traditional client/server approaches. The experiments show that mobile agents often outperform client/server solutions, but also demonstrate the deep interaction between environmental and application parameters. The mobile-agent performance space as a whole is complex, and significant additional experiments are needed to characterize it. Finally, after discussing current and future experiments, we explore the differences between D'Agents and other mobile-agent systems.
Copyright © 2002 by John Wiley \& Sons.
gzipped Postscript
(145K)
|
PDF
(480K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/gray:spe.ps.gz
Copyright © 1997 by Robert Gray.
gzipped Postscript
(811K)
|
PDF
(10709K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR98-327/
Abstract: Mobile agents are an increasingly popular paradigm, and in recent years there has been a proliferation of mobile-agent systems. These systems are, however, largely incompatible with each other. In particular, agents cannot migrate to a host that runs a different mobile-agent system. Prior approaches to interoperability have tried to force agents to use a common API, and so far none have succeeded. Our goal, summarized in the catch phrase ``Write Once, Move Anywhere,'' led to our efforts to develop mechanisms that support dynamic runtime interoperability of mobile-agent systems. This paper describes the Grid Mobile-Agent System, which allows agents to migrate to different mobile-agent systems.
Copyright © 2001 by the authors.
gzipped Postscript
(135K)
|
PDF
(218K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-411/
Abstract: In recent years, there has been an explosive growth in the amount of information available to our society. In particular, the amount of information available on-line through vast networks like the global Internet has been growing at a staggering rate. This growth rate has by far exceeded the rate of growth in network speeds, as has the number of individuals and organizations seeking access to this information. There is thus a motivation to find abstract methods of manipulating this on-line data in ways that both serve the needs of end users efficiently and use network resources intelligently. In lieu of a traditional client-server model of information processing, which is both inflexible and potentially very inefficient, a Transportable Intelligent Agent system has the potential to achieve a more efficient and flexible network system. An intelligent agent is a program that models the information space for a user, and allows the user to specify how the information is to be processed. A transportable agent can suspend its execution, transport itself to a new location on a network, and resume execution at the new location. This is a particularly attractive model for both wireless and dialup networks where a user might not be able to maintain a permanent network connection, as well as for situations where the amount of information to be processed is large relative to the network bandwidth. Preliminary work in the field has shown that such agent systems are possible and deserve further study. This thesis describes a prototype transportable intelligent agent system that extends work already done in the field. Agents are written in a modified version of the Tcl programming language and transported using TCP/IP connections. Several simple examples demonstrate the properties of the system.
Copyright © 1995 by Kenneth Harker.
gzipped Postscript
(31K)
|
PDF
(71K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR95-258/
Abstract: The Agent Tcl language is an extension of Tcl/Tk that supports distributed programming in the form of transportable agents. AGDB is a debugger for the Agent Tcl language. AGDB mixes of traditional and distributed debugging facilities. Traditional debugging features include breakpoints (line-specific, conditional, and once-only), watch conditions and variables, and interrupts. Distributed-debugging features address issues inherent in distributed programming such as migration and communication. These capabilities make debugging distributed programs difficult because they add complexities like race conditions to the set of problems a program can encounter. This paper discusses how AGDB uses distributed debugging features to debug agents.
Copyright © 1997 by the authors.
gzipped Postscript
(83K)
|
PDF
(209K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR97-306/
Abstract: As network information resources grow in size, it is often most efficient to process queries and updates at the site where the data is located. This processing can be accomplished by using a traditional client-server network interface, which constrains the client to the set of queries supported by the server, or requires the server to send all data to the client for processing. The former is inflexible; the latter is inefficient. Transportable agents, which support the movement of the client computation to the location of the remote resource, have the potential to be more flexible and more efficient. Transportable agents are capable of suspending their execution, transporting themselves to another host on a network, and resuming execution from the point at which they were suspended. Transportable agents consume fewer network resources and can support systems that do not have permanent network connections, such as mobile computers and personal digital assistants. We describe a prototype transportable-agent implementation that facilitates research in this area. Agents are written in a script language that supports agent relocation, and the language is processed at each host by an agent interpreter. Electronic mail is the current transport mechanism and we plan to explore others. We present a technical-report searching agent as a demonstration of the capabilities of our prototype implementation.
Copyright © 1994 by the authors.
gzipped Postscript
(31K)
|
PDF
(52K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/kotay:agents.ps.gz
Abstract: Worldwide applications exist in an environment that is inherently distributed, dynamic, heterogeneous, insecure, unreliable, and unpredictable. In particular, the latency and bandwidth of network connections varies tremendously from place to place and time to time, particularly when considering wireless networks, mobile devices, and satellite connections. Applications in this environment must be able to adapt to different and changing conditions. We believe that transportable autonomous agents provide an excellent mechanism for the construction of such applications. We describe our prototype transportable-agent system and several applications.
Copyright © 1996 by ACM.
gzipped Postscript
(46K)
|
PDF
(153K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/kotz:agents.ps.gz
Copyright © 1999 by IEEE.
HTML
Identical to kotz:jmobile.
Abstract: The field of mobile agents should shift its emphasis toward mobile code, in all its forms, rather than continue focusing on mobile agents. The development of modular components will help application designers take advantage of code mobility without having to rewrite their applications to fit in monolithic, mobile agent systems.
Copyright © 2002 by IEEE.
gzipped Postscript
(435K)
|
PDF
(488K)
|
HTML
See also earlier version kotz:dwta-tr.
Abstract: During a discussion in September 2000 the authors examined the future of research on mobile agents and mobile code. (A mobile agent is a running program that can move from host to host in network at times and to places of its own choosing.) In this paper we summarize and reflect on that discussion. It became clear that the field should shift its emphasis toward mobile code, in all its forms, rather than to continue its narrow focus on mobile agents. Furthermore, we encourage the development of modular components, so that application designers may take advantage of code mobility without needing to rewrite their application to fit in a monolithic mobile-agent system. There are many potential applications that may productively use mobile code, but there is no ``killer application'' for mobile agents. Finally, we note that although security is an important and challenging problem, there are many applications and environments with security requirements well within the capability of existing mobile-code and mobile-agent frameworks.
Copyright © 2002 by the authors.
gzipped Postscript
(1520K)
|
PDF
(205K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2002-415/
See also later version kotz:dwta.
Abstract: Use of the Internet has exploded in recent years with the appearance of the World-Wide Web. In this paper, we show how current technological trends necessarily lead to a system based substantially on mobile code, and in many cases, mobile agents. We discuss several technical and non-technical hurdles along the path to that eventuality. Finally, we predict that, within five years, nearly all major Internet sites will be capable of hosting and willing to host some form of mobile agents.
Copyright © 1999 by the authors.
gzipped Postscript
(113K)
|
PDF
(92K)
|
HTML
See also later version kotz:future2.
Abstract: Use of the Internet has exploded in recent years with the appearance of the World-Wide Web. In this paper, we show how current technological trends may lead to a system based substantially on mobile code, and in many cases, mobile agents. We discuss several technical and non-technical hurdles along the path to that eventuality. It seems likely that, within a few years, nearly all major Internet sites will be capable of hosting and willing to host some form of mobile code or mobile agents.
Copyright © 1999 by the authors.
gzipped Postscript
(109K)
|
PDF
(92K)
|
HTML
See also earlier version kotz:future.
Abstract: Mobile computers have become increasingly popular as users discover the benefits of having their electronic work available at all times. However, because network conditions vary from connection to connection, using Internet resources from a mobile platform is a major challenge. Mobile agents are one solution. A mobile agent is an autonomous program that can move from machine to machine in a heterogeneous network under its own control. It can suspend its execution at any point, transport itself to a new machine, and resume execution on the new machine from the point at which it left off. On each machine, it interacts with service agents and other resources to accomplish its task, returning to its home site with a final result when that task is finished.
Agent Tcl is a mobile-agent system whose agents can be written in Tcl, Java, and Scheme. Agent Tcl has extensive navigation and communication services, security mechanisms, and debugging and tracking tools. In this article we focus on Agent Tcl's architecture and security mechanisms, its RPC system, and its docking system, which lets an agent move transparently among mobile computers, regardless of when they are connected to the network.
Copyright © 1997 by IEEE.
gzipped Postscript
(2221K)
|
PDF
(709K)
|
HTML
Identical to kotz:bmobile.
See also earlier version gray:mobile.
Abstract: Wireless networks are an ideal environment for mobile agents, since their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources that they need to use. Furthermore, client-specific data transformations can be moved across the wireless link and run on a wired gateway server, reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents in a data-filtering application where numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and use parameters from filtering experiments conducted during a U.S. Navy Fleet Battle Experiment (FBE) to explore the model's implications.
Copyright © 2002 by Kluwer Academic Publishers.
gzipped Postscript
(281K)
|
PDF
(270K)
URL: http://doi.acm.org/10.1145/506882.506889
See also earlier version kotz:model-tr2.
Abstract: Wireless networks are an ideal environment for mobile agents, because their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources they need to use. Furthermore, client-specific data transformations can be moved across the wireless link, and run on a wired gateway server, with the goal of reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents to support a data-filtering application, in which numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and use parameters from our own experiments to explore the model's implications.
Copyright © 2000 by ACM.
gzipped Postscript
(91K)
|
PDF
(166K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/kotz:model.ps.gz
See also earlier version kotz:model-tr.
See also later version kotz:model-tr2.
Abstract: Wireless networks are an ideal environment for mobile agents, because their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources they need to use. Furthermore, client-specific data transformations can be moved across the wireless link, and run on a wired gateway server, with the goal of reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents to support a data-filtering application, in which numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and use parameters from our own experiments to explore the model's implications.
Copyright © 2000 by the authors.
gzipped Postscript
(309K)
|
PDF
(383K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-366/
See also later version kotz:model.
Abstract: Wireless networks are an ideal environment for mobile agents, since their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources that they need to use. Furthermore, client-specific data transformations can be moved across the wireless link and run on a wired gateway server, reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents in a data-filtering application where numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and use parameters from filtering experiments conducted during a U.S. Navy Fleet Battle Experiment (FBE) to explore the model's implications.
Copyright © 2000 by the authors.
gzipped Postscript
(102K)
|
PDF
(199K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-377/
See also earlier version kotz:model.
See also later version kotz:jmodel.
Abstract: This paper considers a sequencing problem which arises naturally in the scheduling of software agents. We are given n sites at which a certain task might be successfully performed. The probability of success is $p_i$ at the $i$th site and these probabilities are independent. Visiting site i and trying the task there requires time (or some other cost metric) $t_i$ whether successful or not. Latencies between sites $i$ and $j$ are $l_ij$, that is, the travel time between those two sites. Should the task be successfully completed at a site then any remaining sites do not need to be visited. The Travelling Agent Problem is to find the sequence which minimizes the expected time to complete the task. The general formulation of this problem is NP-Complete. However, if the latencies are constant we show that the problem can be solved in polynomial time by sorting the ratios $p_i/t_i$ according to decreasing value and visiting the sites in that order. This result then leads to an efficient algorithm when groups of sites form subnets in which latencies within a subnet are constant but can vary across subnets. We also study the case when there are deadlines for solving the problem in which case the goal is to maximize probability of success subject to satisfying the deadlines. Applications to mobile and intelligent agents are described.
Copyright © 2001 by Springer-Verlag.
gzipped Postscript
(71K)
|
PDF
(219K)
URL: http://agent.cs.dartmouth.edu/papers/moizumi:agent-plan.ps.gz
Abstract: Transportable agents are autonomous programs that migrate from machine to machine, performing complex processing at each step to satisfy client requests. As part of their duties agents often need to communicate with other agents. We propose to use remote procedure call (RPC) along with a flexible interface definition language (IDL), to add structure to inter-agent communication. The real power of our Agent RPC comes from a client-server binding mechanism based on flexible IDL matching and from support for multiple simultaneous bindings. Our agents are programmed in Agent Tcl; we describe how the Tcl implementation made RPC particularly easy to implement. Finally, although our RPC is designed for Agent Tcl programs, the concepts would also work for standard Tcl programs.
Copyright © 1996 by the authors.
gzipped Postscript
(67K)
|
PDF
(234K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR96-280/
Abstract: We present a centralized and a distributed algorithm for scheduling multi-task agents in a distributed system. Each agent consists of multiple tasks that can be executed on multiple machines which correspond to resources. The machines in the system have different speeds. There are different communication delays and data transfer delays. We optimize the overall completion time. Our centralized algorithm has an upper bound on the overall completion time and is used as a module in the distributed algorithm. We present extensive simulation results.
Copyright © 2001 by ACM.
PDF
(107K)
URL: http://cmc.cs.dartmouth.edu/papers/rus:scheduling.pdf
See also later version xie:scheduling.
Abstract: Developing code for the execution of a distributed, dynamic workflow requires significant effort and hence it becomes necessary to build tools that enable the creation and execution of such workflows. Compelling arguments have been made for the implementation of workflow management systems using mobile agents. Mobile agents are autonomous pieces of code that can migrate under their own control from one machine to another within a heterogeneous network. Mission-flow Constructor (MfC) is a workflow management system built on the D'Agents mobile agent system. Like its predecessor Mobile Agent Construction Environment (MACE), MfC uses the concept of visual languages and further abstracts the process of building a workflow. Agents generated by MfC are small and migrate only once. These agents hence make more optimal use of network resources than those generated by MACE. MfC generated agents also use improved communication means and incorporate some basic fault tolerance mechanisms. A set of primitive constructs that encapsulate commonly used topologies has been defined to make easier the process of workflow definition. A workflow specified using the GUI and associated annotation process is compiled to a set of D'Agents agents by making use of the visual depiction and the code fragments that define the individual modules. MfC then launches these agents to execute the various tasks associated with the workflow specified by the user.
Copyright © 2000 by Shankar Sundaram.
gzipped Postscript
(537K)
|
PDF
(11400K)
URL: http://agent.cs.dartmouth.edu/papers/sundaram:thesis.ps.gz
Abstract: Choosing a model for agent migration is a key decision in the design of a Java mobile agent system. Two major models have been proposed for implementing mobile agent migration: one which captures the entire execution state of a running agent, and one which captures only object state. In this paper we compare the two models from the perspective of both the system programmer and the application programmer, in the context of Agent Java, a part of the D'Agents system developed at Dartmouth College. From the system programmer's perspective, we consider such issues as difficulty and complexity of implementation, while from the application programmer's perspective we examine the level of convenience, naturalness and functionality each method provides. Ideally, we would also like to compare the two methods in terms of performance, but time constraints and technical difficulties have prevented us from obtaining accurate results. Nevertheless, we present the results we were able to gather.
Copyright © 1998 by D. Eric White.
No online copy available.
Abstract: We present a centralized and a distributed algorithm for scheduling multi-task agents in a distributed system with the objective of minimizing the overall application completion time. Each agent consists of multiple tasks that can be executed on multiple machines which correspond to resources. The machine speeds and link transfer rates are heterogeneous. Our centralized algorithm has an upper bound on the overall completion time and is used as a module in the distributed algorithm. Extensive simulations show promising results of the algorithms, especially for scheduling communication-intensive multi-task agents.
Copyright © 2001 by Springer-Verlag.
gzipped Postscript
(103K)
|
PDF
(260K)
URL: http://agent.cs.dartmouth.edu/papers/xie:scheduling.ps.gz
See also earlier version rus:scheduling.
Abstract: Mobile-agent systems must address three security issues: protecting an individual machine, protecting a group of machines, and protecting an agent. In this chapter, we discuss these three issues in the context of D'Agents, a mobile-agent system whose agents can be written in Tcl, Java and Scheme. (D'Agents was formerly known as Agent Tcl.) First we discuss mechanisms existing in D'Agents for protecting an individual machine: (1) cryptographic authentication of the agent's owner, (2) resource managers that make policy decisions based on the owner's identity, and (3) secure execution environments for each language that enforce the decisions of the resource managers. Then we discuss our planned market-based approach for protecting machine groups. Finally we consider several (partial) solutions for protecting an agent from a malicious machine.
Copyright © 1998 by Springer-Verlag.
gzipped Postscript
(267K)
|
PDF
(293K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/gray:security-book.ps.gz
See also earlier version gray:security.
Copyright © 1997 by CMP Media LLC.
URL: http://www.ddj.com/articles/1997/9703/
See also earlier version gray:security.
Abstract: Mobile agents are programs capable of migrating from one host machine to another. We propose that mobile agents purchase resource access rights from host machines thereby establishing a market for computational resources and giving agents a metric to evenly distribute themselves throughout the network. Market participation requires quantitative information about resource consumption to define demand and calculate utility.
We create a formal utility model to derive user-demand functions, allowing agents to efficiently plan expenditure and deal with price fluctuations. By quantifying demand and utility, resource owners can precisely set a value for a good. We simulate our model in a mobile agent scheduling environment and show how mobile agents may use server prices to distribute themselves evenly throughout a network.
Copyright © 1998 by the authors.
gzipped Postscript
(83K)
|
PDF
(480K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:demand.ps.gz
See also earlier version bredin:demand-tr.
Abstract: Mobile agents are programs capable of migrating from one host machine to another. We propose that mobile agents purchase resource access rights from host machines thereby establishing a market for computational resources and giving agents a metric to evenly distribute themselves throughout the network. Market participation requires quantitative information about resource consumption to define demand and calculate utility.
We create a formal utility model to derive user-demand functions, allowing agents to efficiently plan expenditure and deal with price fluctuations. By quantifying demand and utility, resource owners can precisely set a value for a good. We simulate our model in a mobile agent scheduling environment and show how mobile agents may use server prices to distribute themselves evenly throughout a network.
Copyright © 1998 by the authors.
gzipped Postscript
(101K)
|
PDF
(239K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR98-331/
See also later version bredin:demand.
Abstract: This paper considers resource allocation in a network with mobile agents competing for computational priority. We formulate this problem as a multi-agent game with the players being agents purchasing service from a common server. We show that there exists a computable Nash equilibrium when agents have perfect information into the future. From our game, we build a market-based CPU allocation policy and a strategy with which an agent may plan its expenditures for a multi-hop itinerary. We simulate a network of hosts and agents using our strategy to show that our resource-allocation mechanism effectively prioritizes agents according to their endowments and that our planning algorithm handles network delay gracefully.
Copyright © 2000 by ACM.
gzipped Postscript
(210K)
|
PDF
(259K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:game.ps.gz
See also earlier version bredin:game-tr.
Abstract: In traditional computational systems, resource owners have no incentive to subject themselves to additional risk and congestion associated with providing service to arbitrary agents, but there are applications that benefit from open environments. We argue for the use of markets to regulate agent systems. With market mechanisms, agents have the abilities to assess the cost of their actions, behave responsibly, and coordinate their resource usage both temporally and spatially.
We discuss our market structure and mechanisms we have developed to foster secure exchange between agents and hosts. Additionally, we believe that certain agent applications encourage repeated interactions that benefit both agents and hosts, giving further reason for hosts to fairly accommodate agents. We apply our ideas to create a resource-allocation policy for mobile-agent systems, from which we derive an algorithm for a mobile agent to plan its expenditure and travel. With perfect information, the algorithm guarantees the agent's optimal completion time.
We relax the assumptions underlying our algorithm design and simulate our planning algorithm and allocation policy to show that the policy prioritizes agents by endowment, handles bursty workloads, adapts to situations where network resources are overextended, and that delaying agents' actions does not catastrophically affect agents' performance.
Copyright © 2001 by Springer-Verlag.
gzipped Postscript
(127K)
|
PDF
(374K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:game-book.ps.gz
Abstract: This paper considers resource allocation in a network with mobile agents competing for computational priority. We formulate this problem as a multi-agent game with the players being agents purchasing service from a common server. We show that there exists a computable Nash equilibrium when agents have perfect information into the future. We simulate a network of hosts and agents using our strategy to show that our resource-allocation mechanism effectively prioritizes agents according to their endowments.
Copyright © 1999 by the authors.
gzipped Postscript
(215K)
|
PDF
(234K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR99-360/
See also later version bredin:game.
Copyright © 2001 by the authors.
gzipped Postscript
(118K)
|
PDF
(148K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:info.ps.gz
Abstract: Mobile-agent systems allow applications to distribute their resource consumption across the network. By prioritizing applications and publishing the cost of actions, it is possible for applications to achieve faster performance than in an environment where resources are evenly shared. We enforce the costs of actions through markets where user applications bid for computation from host machines.
We represent applications as collections of mobile agents and introduce a distributed mechanism for allocating general computational priority to mobile agents. We derive a bidding strategy for an agent that plans expenditures given a budget and a series of tasks to complete. We also show that a unique Nash equilibrium exists between the agents under our allocation policy. We present simulation results to show that the use of our resource-allocation mechanism and expenditure-planning algorithm results in shorter mean job completion times compared to traditional mobile-agent resource allocation. We also observe that our resource-allocation policy adapts favorably to allocate overloaded resources to higher priority agents, and that agents are able to effectively plan expenditures even when faced with network delay and job-size estimation error.
Copyright © 2003 by Kluwer Academic Publishers.
PDF
(324K)
HTML
See also earlier version bredin:game.
Abstract: We propose a method for increasing incentives for sites to host arbitrary mobile agents in which mobile agents purchase their computing needs from host sites. We present a scalable market-based CPU allocation policy and an on-line algorithm that plans a mobile agent's expenditure over a multihop ordered itinerary. The algorithm chooses a set of sites at which to execute and computational priorities at each site to minimize execution time while preserving a prespecified budget constraint. We present simulation results of our algorithm to show that our allocation policy and planning algorithm scale well as more agents are added to the system.
Copyright © 1999 by the authors.
No online copy available.
See also earlier version bredin:lottery-tr.
Abstract: We propose a method for increasing incentives for sites to host arbitrary mobile agents in which mobile agents purchase their computing needs from host sites. We present a scalable market-based CPU allocation policy and an on-line algorithm that plans a mobile agent's expenditure over a multihop ordered itinerary. The algorithm chooses a set of sites at which to execute and computational priorities at each site to minimize execution time while preserving a prespecified budget constraint. We present simulation results of our algorithm to show that our allocation policy and planning algorithm scale well as more agents are added to the system.
Copyright © 1999 by the authors.
gzipped Postscript
(223K)
|
PDF
(441K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR99-345/
See also later version bredin:lottery.
Abstract: Mobile agents are programs that can migrate from machine to machine in a heterogeneous, partially disconnected network. As mobile agents move across a network, they consume resources. We discuss a system for controlling the activities of mobile agents that uses electronic cash, a banking system, and a set of resource managers. We describe protocols for transactions between agents. We present fixed-pricing and dynamic-pricing policies for resources. We focus on and analyze the sealed-bid second-price auction as a mechanism for dynamic pricing.
Copyright © 1998 by ACM.
gzipped Postscript
(157K)
|
PDF
(149K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:market.ps.gz
See also earlier version bredin:market-tr.
Abstract: Mobile agents are programs that can migrate from machine to machine in a heterogeneous, partially disconnected network. As mobile agents move across a network, they consume resources. We discuss a system for controlling the activities of mobile agents that uses electronic cash, a banking system, and a set of resource managers. We describe protocols for transactions between agents. We present fixed-pricing and dynamic-pricing policies for resources. We focus on and analyze the sealed-bid second-price auction as a mechanism for dynamic pricing.
Copyright © 1997 by the authors.
gzipped Postscript
(95K)
|
PDF
(224K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR97-326/
See also later version bredin:market.
Abstract: Mobile-agent systems have gained popularity in use because they ease the application design process by giving software engineers greater flexibility. Although the value of any network is dependent on both the number of users and the number of sites participating in the network, there is little motivation for systems to donate resources to arbitrary agents. We propose to remedy the problem by imposing an economic market on mobile-agent systems where agents purchase resources from host sites and sell services to users and other agents. Host sites accumulate revenues, which are distributed to users to be used to launch more agents. We argue for the use of markets to regulate mobile-agent systems and discuss open issues in implementing market-based mobile-agent systems.
Copyright © 1999 by the authors.
gzipped Postscript
(76K)
|
PDF
(67K)
|
HTML
Abstract: Mobile-agent systems allow user programs to autonomously relocate from one host site to another. This autonomy provides a powerful, flexible architecture on which to build distributed applications. The asynchronous, decentralized nature of mobile-agent systems makes them flexible, but also hinders their deployment. We argue that a market-based approach where agents buy computational resources from their hosts solves many problems faced by mobile-agent systems.
In our earlier work, we propose a policy for allocating general computational priority among agents posed as a competitive game for which we derive a unique computable Nash equilibrium. Here we improve on our earlier approach by implementing resource guarantees where mobile-agent hosts issue call options on computational resources. Call options allow an agent to reserve and guarantee the cost and time necessary to complete its itinerary before the agent begins execution.
We present an algorithm based upon the binomial options-pricing model that estimates future congestion to allow hosts to evaluate call options; methods for agents to measure the risk associated with their performance and compare their expected utility of competing in the computational spot market with utilizing resource options; and test our theory with simulations to show that option trade reduces variance in agent completion times.
Copyright © 2000 by Kluwer.
gzipped Postscript
(86K)
|
PDF
(101K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:risk.ps.gz
Abstract: Modern distributed systems scatter sensors, storage, and computation throughout the environment. Ideally these devices communicate and share resources, but there is seldom motivation for a device's owner to yield control to another user. We establish markets for computational resources to motivate principals to share resources with arbitrary users, to enforce priority in distributed systems, to provide flexible and rational limitations on the potential of an application, and to provide a lightweight structure to balance the workload over time and between devices. As proof of concept, we implement a structure software agents can use to discover and negotiate access to networked resources. The structure separates discovery, authentication, and consumption enforcement as separate orthogonal issues to give system designers flexibility.
Mobile agents represent informational and computational flow. We develop mechanisms that distributively allocate computation among mobile agents in two settings. The first models a situation where users collectively own networked computing resources and require priority enforcement. We extend the allocation mechanism to allow resource reservation to mitigate utility volatility. The second, more general model relaxes the ownership assumption. We apply our computational market to an open setting where a principal's chief concern is revenue maximization.
Our simulations compare the performance of market-based allocation policies to traditional policies and relate the cost of ownership and consumption separation. We observe that our markets effectively prioritize applications' performance, can operate under uncertainty and network delay, provide metrics to balance network load, and allow measurement of market-participation risk versus reservation-based computation.
In addition to allocation problems, we investigate resource selection to optimize execution time. The problem is NP-complete if the costs and latencies are constant. Both metrics' dependence on the chosen set complicates matters. We study how a greedy approach, a novel heuristic, and a shortest-constrained-path strategy perform in mobile-agent applications.
Market-based computational-resource allocation fertilizes applications where previously there was a dearth of motive for or means of cooperation. The rationale behind mobile-agent performance optimization is also useful for resource allocation in general distributed systems where an application has a sequence of dependent tasks or when data collection is expensive.
Copyright © 2001 by Jonathan L. Bredin.
gzipped Postscript
(436K)
|
PDF
(1409K)
URL: http://cmc.cs.dartmouth.edu/papers/bredin:thesis.pdf
See also later version bredin:thesis-tr.
Abstract: Modern distributed systems scatter sensors, storage, and computation throughout the environment. Ideally these devices communicate and share resources, but there is seldom motivation for a device's owner to yield control to another user. We establish markets for computational resources to motivate principals to share resources with arbitrary users, to enforce priority in distributed systems, to provide flexible and rational limitations on the potential of an application, and to provide a lightweight structure to balance the workload over time and between devices. As proof of concept, we implement a structure software agents can use to discover and negotiate access to networked resources. The structure separates discovery, authentication, and consumption enforcement as separate orthogonal issues to give system designers flexibility.
Mobile agents represent informational and computational flow. We develop mechanisms that distributively allocate computation among mobile agents in two settings. The first models a situation where users collectively own networked computing resources and require priority enforcement. We extend the allocation mechanism to allow resource reservation to mitigate utility volatility. The second, more general model relaxes the ownership assumption. We apply our computational market to an open setting where a principal's chief concern is revenue maximization.
Our simulations compare the performance of market-based allocation policies to traditional policies and relate the cost of ownership and consumption separation. We observe that our markets effectively prioritize applications' performance, can operate under uncertainty and network delay, provide metrics to balance network load, and allow measurement of market-participation risk versus reservation-based computation.
In addition to allocation problems, we investigate resource selection to optimize execution time. The problem is NP-complete if the costs and latencies are constant. Both metrics' dependence on the chosen set complicates matters. We study how a greedy approach, a novel heuristic, and a shortest-constrained-path strategy perform in mobile-agent applications.
Market-based computational-resource allocation fertilizes applications where previously there was a dearth of motive for or means of cooperation. The rationale behind mobile-agent performance optimization is also useful for resource allocation in general distributed systems where an application has a sequence of dependent tasks or when data collection is expensive.
Copyright © 2001 by Jonathan L. Bredin.
PDF
(1002K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-408/
See also earlier version bredin:thesis.
Abstract: A usable and efficient resource-management system has been created for use with D'Agents. The software dynamically negotiates a price rate for CPU time, using the competitive bids of mobile agents that offer currency in return for fast computation. The system allows mobile agents to plan their expenditures across many hosts while minimizing the time needed for their tasks. The ability to price CPU time opens the door for service owners to be compensated for the computation consumed by agents and provides an incentive for servers to allow anonymous agents. We discuss the theoretical background which makes a CPU market system possible and the performance of the D'Agents market system.
Copyright © 2000 by the authors.
gzipped Postscript
(71K)
|
PDF
(228K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-375/
Wireless networks and sensor networks
Abstract: The advances in sensing devices and integrated circuit technology have allowed for the development of easily "reconfigurable smart sensor" products. Primarily utilizing commercial off-the-shelf (COTS) components, we have developed reconfigurable smart sensor, consisting of a microprocessor, GPS receiver, RF transceiver, and sensor. The standard serial control interface allows for ease of interchangeability for upgrades in RF transmission schemes as well as customizing the sensing device (i.e. temperature, video images, IR, motion, Ethernet) per application. The result is a flexible module capable of gathering sensor data, local processing, and forwarding compressed information to a central location via other module.
In this paper, we present our system infrastructure design and a cost function based geographical self-routing algorithm for networking reconfigurable smart sensors. The algorithm allows for the sensors to automatically negotiate in a geographical radial topology relative to a central location, utilizing other sensors as routes or hops for forwarding information to this central location. A number of these sensors are deployed in the field and performance measurements for routing times are analyzed and presented.
Copyright © 2000 by SPIE.
gzipped Postscript
(129K)
|
PDF
(354K)
URL: http://agent.cs.dartmouth.edu/papers/corr:reconfigurable.ps.gz
Abstract: Recent advances in sensing devices and integrated circuit technology have allowed for the development of easily "reconfigurable smart sensor" products for the application of Distributed Sensor Networks. Primarily utilizing commercial off-the-shelf (COTS) components, I have developed Reconfigurable smart sensors, consisting of a microprocessor, GPS receiver, RF transceiver, and temperature sensor. The result is a flexible module capable of gathering sensor data and forwarding compressed information to a central location via other modules.
In this Thesis, I will present a new paradigm with relaxed requirements for ad hoc sensor network routing protocols called Statistically Accurate Sensor Networks (SASN). Using the guidelines of a SASN, an innovative self-routing algorithm called Best Effort multi-Hop Geographical Routing (BEHGR), will be proposed for the purpose of networking wireless sensors. In BEHGR, geographical positioning information is utilized to dynamically route packets to a central location in a ``best effort" manner. Using the reconfigurable smart sensors as a real time test bed, I have deployed and tested the BEHGR protocol in the field. The infrastructure design for these sensor modules, as well as performance measurements for data throughput and data currentness of the BEHGR protocol are presented and analyzed.
Copyright © 2001 by Michael G. Corr.
gzipped Postscript
(759K)
|
PDF
(2073K)
URL: http://agent.cs.dartmouth.edu/papers/corr:thesis.ps.gz
Abstract: Interest in and development of mobile agent software systems has burgeoned in the past five years. Code mobility has many attractive attributes for performance and dynamic deployment of new distributed computing and information management applications. An active message is a datagram encapsulated as a mobile agent. The agent is persistent in the network, moving from node to node under its own internal routing logic and control at the application layer.
Active messages are particularly attractive in networks that have very unreliable links such as wireless networks in which the nodes are mobile. Such networks experience frequent link failures and other changes in topology. Active messages allow data to propagate between nodes that may never have viable TCP/IP type connections.
In spite of the growing implementation interest in mobile agents and active messaging, there are essentially no analytic models or results dealing with their performance. This paper presents a simple model for active messages in a network with frequent link failures. Using this model, we develop expressions for the expected delivery time of an active message along one path as well as expected delivery time for duplicated messages traversing disjoint paths between source and destination nodes.
Copyright © 1999 by Allerton Conference.
gzipped Postscript
(980K)
|
PDF
(209K)
URL: http://agent.cs.dartmouth.edu/papers/okino:active.ps.gz
Abstract: This paper deals with tracking based on natural language messages. Of particular interest are messages generated by multiple human observers over extended periods of time. The tracking problem is to associate messages that are about the same object or phenomenon, create the most probable tracks based on those associations and finally make inferences about the situation. A key technical innovation of this work is the use of mature radar signal processing tracking methods, originally used for correlating radar sensor reports, in the domain of natural language processing and understanding for tracking applications. We believe that our results can be useful in several applications that involve tracking and correlation of natural language reports based on text semantics. Such applications include: 1) military situation awareness using human observations (such as land vehicle tracking); 2) maintenance planning using text-based reports; 3) analysis of computer intrusion detection reports; 4) customer service monitoring and tracking.
In this paper we describe our present implementation, called TextTrack. It uses the multiple hypothesis tracking (MHT) paradigm developed for multiple object tracking. TextTrack has a simple natural language frontend which does rudimentary parsing and analysis of short messages or reports. Messages are then assembled into maximum likelihood tracks as computed by an MHT algorithm. These tracks can be analyzed to estimate, for example, an entity's identity. We develop both Bayesian maximum likelihood and fuzzy logic approaches to the problem. In addition to presenting the basic ideas behind our system, we also develop analytic convergence results for one tracking scenario under very weak assumptions.
Copyright © 1997 by the authors.
No online copy available.
Information retrieval and clustering
Abstract: Recent experiments and analysis suggest that there are about 800 million publicly-indexable web pages. However, unlike books in a traditional library, web pages continue to change even after they are initially published by their authors and indexed by search engines. This paper describes preliminary data on and statistical analysis of the frequency and nature of web page modifications. Using empirical models and a novel analytic metric of "up-to-dateness", we estimate the rate at which web search engines must re-index the web to remain current.
Copyright © 2000 by the authors.
gzipped Postscript
(314K)
|
PDF
(649K)
URL: http://agent.cs.dartmouth.edu/papers/brewington:dynamic.ps.gz
See also earlier version brewington:jdynamic.
Abstract: Because information depreciates over time, keeping Web pages current presents new design challenges. This article quantifies what "current" means for Web search engines and estimates how often they must reindex the Web to keep current with its changing pages and structure.
Most information-from a newspaper story to a temperature sensor measurement to a Web page-is dynamic. When monitoring an information source, when do our previous observations become stale and need refreshing? How can we schedule these refresh operations to satisfy a required level of currency without violating resource constraints-such as band-width or computing limitations on how much data can be observed in a given time?
The authors investigate the trade-offs involved in monitoring dynamic information sources and discuss the Web in detail, estimating how fast documents change and exploring what constitutes a "current" Web index. For a simple class of Web-monitoring systems-search engines-they combine their idea of currency with actual measured data to estimate revisit rates.
Copyright © 2000 by IEEE.
gzipped Postscript
(227K)
|
PDF
(417K)
|
HTML
Abstract: This thesis proposal deals with optimal observation of large collections of changing objects. These objects can change at random times, so we cannot know the state of objects for times at which they are unobserved. The goal of an observer is to maintain acceptably accurate state estimates while minimizing observational cost. In the thesis work, our goals are to (1) create models for this type of system, (2) show how these models can be empirically constructed by actually observing real systems, and (3) develop efficient algorithms for the optimal allocation of observation resources within this framework. An example of this type of optimization arises in the observation of World Wide Web (WWW) documents by web search engines and related web software applications. Our initial results include (1) developing statistical models for such systems; (2) collection of empirical data about how web documents change; and (3) development of finite-horizon algorithms for maximizing an index's accuracy. Although the algorithms presented are intended for optimizing the recency of document indices, they are general enough to be applied to any dynamic collection of objects. The work is important and novel in that it takes proper account of the cost of observing, a concept that is crucial to monitoring problems in many communications systems.
Copyright © 1998 by Brian Brewington.
gzipped Postscript
(137K)
|
PDF
(328K)
URL: http://agent.cs.dartmouth.edu/papers/brewington:observe.ps.gz
Abstract: Many modern information management tasks consist of an observer that must maintain current knowledge of a collection of changing information. The goal of this observer is to maintain acceptably accurate state estimates given limited observation resources, such as bandwidth, time, and storage. Good examples of such ``observation problems'' are found in any situation where bandwidth is limited and old observations become less useful over time. Two such examples are maintaining a search engine's index of the World Wide Web (WWW) and automated monitoring of multiple sensors. This thesis addresses the general observation problem by (1) devising a formal framework of what it means to be ``up-to-date'', (2) gathering empirical data about the web that allows us to apply this framework to an important setting, and (3) presenting algorithms for scheduling revisits to optimize formal performance measures. One year's worth of web page observations are analyzed to show how quickly and in what ways web pages change. The observations are used to estimate the distribution of web page change rates. Using this data as a model of the web we present and benchmark an algorithm for optimizing the observation of a set of web documents such that fewer changes go unnoticed. Our experiments on real search engines show that between 40 and 50% of results returned have been altered at least once since the search engine last observed them. Our algorithm can theoretically reduce these figures to between 36 and 44%, assuming that existing search engines currently use simple round-robin re-indexing strategies. These methods benefit the ``overworked'' observer much more than the one with ample bandwidth, and are general enough to be of use in a wide variety of monitoring tasks.
Copyright © 2000 by Brian Brewington.
gzipped Postscript
(2683K)
|
PDF
(6518K)
URL: http://actcomm.dartmouth.edu/papers/brewington:thesis.ps.gz
Abstract: Information push and information pull have recently emerged as useful concepts to describe the operation of distributed information resources. Information push, in particular, is becoming closely associated with intelligent agent functionality.
Loosely speaking, if a user requests and receives a very specific piece of information, this is information pull. If information is sent in anticipation of the user's need, or the agent's response includes information not directly solicited, then the situation is characterized as information push. Intuitively, junk mail (electronic or paper), television newscasts and wirefeeds are examples of information push. New web services such as Pointcast and Informant are examples of more selective push technologies. Web browsing, library searches, and telephone white pages are traditional examples of information pull.
Clearly, these categorizations can be ambiguous and are easily lost in semantics. The main goal of this paper is to formalize these concepts and describe a mathematical framework around which further work can be more precise. Specifically, we develop a stochastic framework based on Markov models to describe an ambient environment and an agent system. Depending on the relationships between the environment, the agent and the user's performance criterion, a continuum of possible information push and pull scenarios can be described. Some basic analytic results concerning the operation of a push/pull information system are derived.
Copyright © 1998 by Springer-Verlag.
gzipped Postscript
(65K)
|
PDF
(186K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:push.ps.gz
Mobile agents in information retrieval
Abstract: A mobile agent is an executing program that can migrate during execution from machine to machine in a heterogeneous network. On each machine, the agent interacts with stationary service agents and other resources to accomplish its task. Mobile agents are particularly attractive in distributed information-retrieval applications. By moving to the location of an information resource, the agent can search the resource locally, eliminating the transfer of intermediate results across the network and reducing end-to-end latency. In this chapter, we first discuss the strengths of mobile agents, and argue that although none of these strengths are unique to mobile agents, no competing technique shares all of them. Next, after surveying several representative mobile-agent systems, we examine one specific information-retrieval application, searching distributed collections of technical reports, and consider how mobile agents can be used to implement this application efficiently and easily. Then we spend the bulk of the chapter describing two planning services that allow mobile agents to deal with dynamic network environments and information resources: (1) planning algorithms that let an agent choose the best migration path through the network, given its current task and the current network conditions, and (2) planning algorithms that tell an agent how to observe a changing set of documents in a way that detects changes as soon as possible while minimizing overhead. Finally, we consider the types of errors that can occur when information from multiple sources is merged and filtered, and argue that the structure of a mobile-agent application determines the extent to which these errors affect the final result.
Copyright © 1999 by Springer-Verlag.
gzipped Postscript
(196K)
|
PDF
(419K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/brewington:IR.ps.gz
Abstract: Industry estimates show that aggressive reuse of existing inventory could reduce the delivered cost of large, complex manufactured systems by as much as 20\%. In most cases these savings are not captured, principally because the current technology to locate reusable designs and inventory, which uses taxonomies and other artificial indices, is too cumbersome. Furthermore, current systems do not address the design phase - where opportunities for reuse first arise. This paper describes a computer-based technology that will be an important step towards solving this problem.
For mechanical parts, the modern design phase starts with computer aided design (CAD) packages. Given a prototype design of a solid object, the design engineer should be able to determine whether the part under consideration is already designed or in manufacture. Our system does this by using physical shape as a direct index to existing designs and manufactured components, eliminating time-consuming and error-prone searches of the taxonomy. Other applications of this technology include identification of warehoused parts according to scanned shape and efficient management of 3-dimensional objects in computer animation and virtual reality systems.
Our system takes a standard digital representation of a solid object, such as in IGES form, and produces a surface triangular mesh representing the boundary of the object. The surface mesh allows a voxel approximation representation of the solid which is computed by flood filling. Zeroth, first and second order geometrical moments are used to normalize the orientation of the solid. Then a variety of volumetric invariants are computed and used as features. These features determine a hash function which maps similar shapes to closely related feature vectors. Nearby feature vectors identify a small subset of objects which are compared using symmetric differencing on a voxel by voxel basis. This voxel symmetric difference gives a rank ordering of similarity between 3-dimensional shapes in the database and the object under consideration. Using this small subset of like-shaped objects, the design engineer can browse a reasonable subset of parts from the complete database.
The described research has significant applications in industries which seek to reuse existing designs and inventory thereby reducing manufacturing costs. Applications in aerospace, automobile and machine tool industries are most promising and urgent. We expect that this research will lead to the commercial development of software that will enhance existing CAD and database systems.
gzipped Postscript (135K) | PDF (273K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:3dcad.ps.gz
Abstract: We have designed and implemented autonomous software agents. Autonomous software agents navigate independently through a heterogeneous network of computers. They can sense the state of the network, monitor software conditions, and interact with other agents. The network-sensing tools allow our agents to adapt to the network configuration and to navigate under the control of reactive plans. In this paper we illustrate the intelligent and adaptive behavior of autonomous agents in distributed information-gathering tasks.
Copyright © 1996 by AAAI Press.
gzipped Postscript
(117K)
|
PDF
(206K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/rus:autonomous.ps.gz
See also later version rus:autonomous2.
Abstract: Transportable agents are autonomous programs. They can move through a heterogeneous network of computers under their own control, migrating from host to host. They can sense the state of the network, monitor software conditions, and interact with other agents or resources. The network-sensing tools allow our agents to adapt to the network configuration and to navigate under the control of reactive plans. In this paper we describe the design and implementation of the navigation system that gives our agents autonomy. We also discuss the intelligent and adaptive behavior of autonomous agents in distributed information-gathering tasks.
Copyright © 1997 by ACM.
gzipped Postscript
(117K)
|
PDF
(193K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/rus:autonomous2.ps.gz
See also earlier version rus:autonomous.
See also later version rus:autonomous3.
Abstract: Transportable agents are autonomous programs. They can move through a heterogeneous network of computers under their own control, migrating from host to host. They can sense the state of the network, monitor software conditions, and interact with other agents or resources. The network-sensing tools allow our agents to adapt to the network configuration and to navigate under the control of reactive plans. In this paper we describe the design and implementation of the navigation system that gives our agents autonomy. We also discuss the intelligent and adaptive behavior of autonomous agents in distributed information-gathering tasks.
Copyright © 1997 by Kluwer Academic Publishers.
gzipped Postscript
(230K)
|
PDF
(245K)
URL: http://www.wkap.nl/oasis.htm/146930
Identical to rus:autonomous4.
See also earlier version rus:autonomous2.
Abstract: Transportable agents are autonomous programs. They can move through a heterogeneous network of computers under their own control, migrating from host to host. They can sense the state of the network, monitor software conditions, and interact with other agents or resources. The network-sensing tools allow our agents to adapt to the network configuration and to navigate under the control of reactive plans. In this paper we describe the design and implementation of the navigation system that gives our agents autonomy. We also discuss the intelligent and adaptive behavior of autonomous agents in distributed information-gathering tasks.
Copyright © 1997 by Morgan Kaufmann Publishers.
URL: http://www.elsevier.com/wps/find/bookdescription.cws_home/680784/description
Identical to rus:autonomous3.
Network sensing, learning and planning
Abstract: Most current computer applications are insensitive to changing conditions. With the growing demand for wireless. satellite, and other highly volatile computer communications networks, however, applications that are robust in the presence of network volatility must be designed and built. Network-robust applications are of great interest in military situations today, and we expect that interest to grow in industrial and eventually consumer environments as well. Mobile agents are one way to realize such applications, especially when used in a wireless environment. This article discusses issues and results related to the problem of making computer applications network-aware and reactive to changing network conditions. It contains a short overview of our work on mobile agents as well as a tutorial on network sensing from the agent perspective. Some prototypes of network-sensing systems and network aware mobile-agent applications are presented.
Copyright © 1998 by IEEE.
PDF
(1225K)
URL: http://cmc.cs.dartmouth.edu/papers/caripe:awareness.pdf
Abstract: Many memory-based methods for learning use some form of nearest neighbor inference. By memory-based, we mean methods that localize data in the training sample to make inferences about novel feature values. The conventional wisdom about nearest neighbor methods is that they are subject to various curses of dimensionality and so become infeasible in high dimensional feature spaces. However, recent results such as those by Barron and Jones suggest that these dimensionality problems can be overcome in the case of parametric models such as sigmoidal neural networks which are patently nonlocal. This creates a paradox because memory-based methods have been shown to perform well in a number of applications. They are often competative with parametric methods in terms of prediction error and actually superior in terms of training time. In this paper, we study the unreasonable effectiveness of memory-based methods. We analyze their performance in terms of new metrics that take into consideration ...
Copyright © 1997 by Springer-Verlag.
gzipped Postscript
(48K)
|
PDF
(198K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:effectiveness.ps.gz
Abstract: In the past decade, research in neurocomputing has been divided into two relatively well-defined tracks: one track dealing with cognition and the other with behavior. Cognition deals with organizing, classifying and recognizing sensory stimuli. Behavior is more dynamic, involving sequences of actions and changing interactions with an external environment. The mathematical techniques that apply to these areas, at least from the point of neurocomputing, appear to have been quite separate as well. The purpose of this paper is to give an overview of some recent powerful mathematical results in behavioral neurocomputing, specifically the concept of Q-learning due to C. Watkins, and some new extensions. Finally, we propose ways in which the mathematics of cognition and the mathematics of behavior can move closer to build more unified systems of information processing and action.
Copyright © 1997 by Kluwer Academic Publishers.
gzipped Postscript
(47K)
|
PDF
(133K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:qlearn.ps.gz
See also later version cybenko:q-learning.
Copyright © 1997 by the authors.
gzipped Postscript
(84K)
|
PDF
(199K)
URL: http://agent.cs.dartmouth.edu/papers/moizumi:uncertainty.ps.gz
Network routing and quality-of-service (QoS)
Abstract: This thesis presents some extensions to Mobile IP designed to better adapt this protocol to wireless networks. Specifically, the foreign-agent selection process is studied in depth and several selection criteria are proposed and implemented as extensions to an existing Mobile IP software package.
Wireless computer networks bring many advantages to those environments where network connectivity is required subject to constraints such as flexibility, affordability, and scalability. Wireless Local Area Networks (LANs) can be quickly installed in cases where traditional networks are not a feasible option for reasons like deployment time, cost, etc. Mobile IP is a protocol that provides support for roaming of computers between different networks. Each Mobile IP-enabled computer (mobile node) has a fixed home agent on its original network that keeps track of the mobile node's location at all times. The protocol specifies several different mechanisms for the mobile node to keep its home agent updated about its location every time it moves to another network. One of those mechanisms requires the mobile node to select a temporary gateway computer (foreign agent) at the visited network; this computer will serve as the mobile node's default router to the rest of the network and will forward location updates to the mobile node's home agent. In a wireless networking environment, mobile nodes will likely encounter situations in which there are several candidates from which to select a foreign agent. However, the Mobile IP protocol does not specify policies to use in such cases. The extensions developed in this thesis approach this problem. Performance measurements of Mobile IP-enabled wireless LANs using these extensions are also presented and analyzed. In terms of throughput for TCP bulk data transfer, compared to the throughput achieved from using the original Mobile IP implementation, these Mobile IP extensions led to a performance improvement of up to 20\% under certain scenarios.
Copyright © 1998 by Wilmer Caripe.
gzipped Postscript
(1288K)
|
PDF
(729K)
URL: http://agent.cs.dartmouth.edu/papers/caripe:mobileip.pdf