Online multiplayer gaming has emerged as a popular form of entertainment. During these games, the players' main focus is usually placed on achieving the objectives that must be completed to win the game. While these tasks may be of the primary interest to the players, over the course of the game their interactions may result in interesting narratives that go unnoticed. This may be due to the imperfect information that a player has access to or as a result of their attention being directed towards accomplishing the goals of the game. This thesis presents Afterthought, a system that will allow players to view these emergent narratives after completing their gameplay session. The tool accomplishes this through logging the actions that occur during the play of the game, analyzing the log and retrieving interesting narratives, generating the cinematic discourse for visualization, rendering the videos of the narratives, and finally uploading the videos to a video sharing site so that they are easily viewable by all participants. This thesis concludes with preliminary human subjects evaluation of the system's effectiveness.

As the science of robotics advances, robots are interacting with people more frequently. Robots are appearing in our houses and places of work acting as assistants in many capacities. One aspect of this interaction is determining spatial relationships between objects. People and robots simply can not communicate effectively without references to the physical world and how those objects relate to each other. In this research fuzzy logic is used to help determine the spatial relationships between objects as fuzzy logic lends itself to the inherent imprecision of spatial relationships. Objects are rarely absolutely in front of or to the right of another, especially when dealing with multiple objects. This research compares three methods of fuzzy logic, the angle aggregation method, the centroid method and the histogram of angles â composition method. First we use a robot to gather real world data on the geometries between objects, and then we adapt the fuzzy logic techniques for the geometry between objects from the robot's perspective which is then used on the generated robot data. Last we perform an in depth analysis comparing the three techniques with the human survey data to determine which may predict spatial relationships most accurately under these conditions as a human would. Previous research mainly focused on determining spatial relationships from an allocentric, or bird's eye view, where here we apply some of the same techniques to determine spatial relationships from an egocentric, or observer's point of view.

Mobile devices are hand held devices used to deliver time sensitive and locale specific information to the users. In multi-user environments with limited resources, agents running on mobile devices as assistants to their users improve the social welfare in the presence of tradable reservations. The purpose of this research is to show the benefits of planning in such an environment. By conducting various experiments we study the effects, when complex plans are generated to satisfy the user specified constraints and environment enforced constraints. We observe that with tradable reservations the social welfare increases with increase in planning horizon. We also observe that tradable reservations and clairvoyance help the users satisfy their preferences and constraints imposed by environment without loss in social welfare.

Group communication is the most important mode of communication in ad hoc networks, because of the collaborative nature of mobile ad hoc applications. In this light, an efficient and light weight multicast routing protocol is necessary. Presently the multicast routing is either done entirely at the network layer, or at the application layer as stateless overlay mulitcasting. Owing to the dynamic nature of ad hoc networks, the first method incurs a large signaling overhead due to frequent modification of routing tables and exchanging of session state information. The latter approach uses the underlying unicast routing to build multicast data distribution trees without maintaining session state information thereby trading efficiency for minimal messaging overhead. For small groups with constant bound on the number of multicast group members, the overlay schemes, apart from having a trivial signaling overhead, are also known to be far more efficient than the network layer schemes. But the existing overlay schemes do not completely exploit the `knowledge' possessed by the network layer; they just use the unicast routing at the network layer. We believe that, even for larger groups, the overlay schemes can function with reasonable efficiency along with trivial signaling overhead if they intelligently use the network layer information.<br><br>In this thesis, we propose a network assisted multicast routing scheme, NAMO NAMAHA, which primarily operates as an overlay while getting assistance from the network layer unicast routing protocol, CEDAR. The overlay algorithms dynamically build an approximate Steiner data distribution tree, adopting the (CHINS)_T (Cheapest Insertion Heuristic with Table) algorithm for the distributed implementation of the well known Takahashi-Matsuyama heuristic. The Steiner trees are incrementally built over a subgraph of core nodes, which form the approximate Minimum Dominating Set (MDS) over the network nodes. The core nodes get computed by a network layer heuristic using local data at that layer, and they provide useful information for the NAMO NAMAHA tree computation algorithms at the overlay layer. The main idea in this thesis is that if the construction of overlays is aided by some minimal but useful information from the network layer that is almost invariant, local and that which would incur constant memory overhead, efficient overlays can be constructed.<br><br>This thesis presents the algorithms for the protocol NAMO NAMAHA, offers proof of correctness for the protocol and shows that the time and memory complexity of the algorithms in the protocol are either constant, or linear with the number of graph edges or nodes. We compare our work with the MCEDAR protocol in terms of the cost of the multicast data distribution trees, the number of messages exchanged in building them and the time and memory complexity of the algorithms involved. We choose MCEDAR since other multicast protocols for ad hoc networks are either network based which does not scale for large nubmer of nodes, or function as overlays designed only for small groups. When compared to MCEDAR, NAMO NAMAHA has a simpler join protocol implemented by our unique Unicast Trap algorithm that does not make use of acknowledgements. Unlike MCEDAR, the sender discovery messages are not propagated all over the network; they are restricted to regions where it is absolutely necessary. In NAMO NAMAHA, at any given time, a path exists between any multicast subscriber and the sender (which is approximately the best path possible) with very high probability. Such a guarantee cannot be given in MCEDAR. Furthermore because of the incremental Steiner tree construction, the resulting multicast data distribution tree has nearly the least total cost. Cost is not minimized in MCEDAR. These advantages are obtained in NAMO NAMAHA just by using extra messages during tree construction, whose number is well below the actual number of nodes in the multicast group. The time and memory complexity of the NAMO NAMAHA algorithms are in the same order as that in MCEDAR.

Scalability has become a major issue within the field of visualization as data gathering methodologies and display technologies diversify. To compensate for large data sets and display limitations, perceptual visualization techniques aim to optimize graphical data representations with human vision in mind. The following outlines the principles, motivations, and development behind the Telescope multivariate visualization framework. Telescope provides mechanisms for generating and manipulating visualizations in which the visual angle and display resolution of individual elements are of chief concern. This software utilizes ongoing research towards the development of comprehensive perceptual feature guidelines to provide a means of dynamically mapping several common visual features to a given data set. Specific element mappings may be disabled or enabled when the size or display resolution of the displayed data elements crosses a defined threshold. Visualization features of interest are: hue, density, direction, flicker, luminance, orientation, regularity, size, and velocity. The system also allows for the simulation of various viewing environments with concern to display size, resolution, viewing distance, and visual angle. Support is provided for the input of a common data format and the easy manipulation of system parameters by means of a rule system. The end result is a system which lays the foundation for the implementation of a comprehensive perceptual visualization hierarchy.

Layered graphs find use in many applications today, including flow charts, business processes, and genealogical diagrams. Traditional means of depicting this data are similar to depictions of unlayered node-link graphs, with each layer's nodes grouped into a line. This type of diagram becomes increasingly difficult to use as the number of nodes and links increases, presenting a scalability issue. We suggest quilted graphs as a better scaling alternative to traditional depictions. Quilted graphs draw on the strengths of matrix-style depictions already in use for unlayered graphs to reduce the impact of graph size on graph legibility. By combining positional encoding from matrix-style depictions with other means of link encoding, they can also be made more compact than matrix depictions. We have developed prototype software to create these graphs, and interactive behavior has been added to enhance their usability. Several applications of quilted graphs are suggested and demonstrated in place of existing diagrams including SAS's activity-based management (ABM) data, online analytical processing (OLAP) hierarchies, and genealogical diagrams.

<p>Many applications and telecommunications services in futurehigh-speed networks will require some form of multipointcommunication. The problems associated with providing network support formultipoint communication have been widely studied within anumber of different networking contexts.As current network technologies evolve to an all-optical, largely passive infrastructure, these problems takeon new significance and raise a number of challenging issuesthat require novel solutions.<p>We consider the problem of supporting multipoint communication at the media access control (MAC) layer of broadcast-and-select Wavelength Division Multiplexed (WDM) networks.In this environment, bandwidth consumption and channel utilization arise as two conflicting objectives in the design of scheduling algorithms for multicast traffic.We present a new technique for the transmission of multicast packets which is based on the concept of a virtual receiver. This is a set of physical receivers which behave identically in terms of tuning.We focus on the problem of optimally selecting the virtual receivers, and prove that it is NP-complete.We then present four heuristics of varying degrees of complexity for obtaining virtual receivers that provide a good balance between the two conflicting objectives.<p>The dynamic nature of multicast traffic could affect the balance obtained with the virtual receivers when the network conditions change.We study the sensitivity to changes of the virtual receiver sets and the cost associated with handling the changes.Also, the cost of three different approaches to handling the changes is analyzed.Finally, we study the performance of various strategies for scheduling a combined load of unicast and multicast traffic in a broadcast WDM network.Three different scheduling strategies are presented, namely: separate scheduling of unicast and multicast traffic, treating multicast traffic as a number of unicast messages, and treating unicast traffic as multicasts of size one.Performance is measured in terms of schedule length which directly affects both aggregate network throughput and average packet delay.<P>

<p>In this research we study the problems associated with dynamic reconfiguration of broadcast WDM networks.Adaptability to the changing traffic conditions is viewed as one of the key features of multiwavelength optical networks, and this is the first comprehensive in-depth study of this problem area.Our contribution consists of identifying the three main questions related to network reconfiguration: a) how to balance the load across multiple wavelengths; b) deciding when it is best to reconfigure the network and c) performing the actual reconfiguration in an efficient manner, that minimizes cell losses.We provide novel solutions to each of these problems.Our solutions consist of an algorithm we call GLPT, which balances the cell load across wavelengths, an optimal reconfiguration policy, derived from representing the problem as a Markovian Decision Process, and a class of retuning strategies that allow us to reconfigure the system.In addition, we perform a simulated comparison of static and dynamically reconfigurable networks in order to verify the validity of our approach.The simulation also provides us with valuable insights into the behavior of an adaptable optical network.<P>

<p>We study a class of circuit switched wavelength routing networks with fixed or alternate routing, with or without converts, and with various wavelength allocation policies.We first construct an exact Markov process and an approximate Markovprocess which has a closed-form solution for a single path. We alsodevelop an iterative decomposition algorithm to analyze long paths with orwithout wavelength converters effectively. Based on this algorithm, we thenpresent an iterative path decomposition algorithm to evaluate the blocking performance of mesh topology networks with fixed and alternate routing accurately and efficiently.The decomposition approach can naturally capture the correlation of both link loads and link blocking events, giving accurate results for a wide range of loads and network topologies.Our model also allows non-uniform traffic, i.e., call request arrival rates that can vary with the source-destination pair, and it can be used when the location of converters is fixed but arbitrary.Our algorithm represents a simple and computationally efficient solution to the difficult problem of computing call blocking probabilities in wavelength routing networks. Finally we show through numericaland simulation results that the blocking probabilities for the randomwavelength allocation and the circuit-switched case provide upper and lowerbounds on the blocking probabilities for two wavelength allocation policiesthat are most likely to be use in practice, namely most-used and first-fitallocation. Furthermore, we demonstrate that using these two policieshas an effect on call blocking probabilities that is equivalent toemploying converters at a number of nodes in the network.<P>

<p>Sophisticated computing environments support many of the complex tasks whicharise in modern enterprises. An enterprise environment is a collective ofthe organization's software, hardware, networking, and data systems.Typically, many user workstations communicate with shared servers, balancingcomputer processing throughout the organization. In a ``secure" modernenterprise issues of authentication, private communication, and protected,shared data space must be addressed. In this thesis we present a generalmodel for adding security to the currently popular enterprise architecture:the World Wide Web (WWW).<P>The results of our investigation into adding security to the generalWWW architecture are reported in this document. We focus onauthenticating users (Kerberos), establishing a secure communicationlink for private data exchange (SSL), protected space to store shareddata (AFS filesystem), and an enhanced server (Apache) to integrate thesecomponents. After presenting our secure model, we describe a prototypeapplication, built using our approach, which addresses a common problemof secure online submission of homework assignments in a universityenvironment.<P>