<p>This thesis presents a formal model of checking sequencegeneration for finite state specifications, based on the machine identificationproblem. The machine identification problem is concerned with drawingconclusions about the internals of an unknown machine by performing experimentson it. Using this approach, the properties of checking sequences are describedin the context of abstract experiments. This formal model is used toprove fault coverage properties of some of the existing checkingsequence generation methods. The same model is alsoused to develop two new checking sequence generation methods, one usingUIO sequences and the other using a distinguishing sequence together withUIO sequences. These two new methods do not use the reset feature.Empirical results indicate that these new methods have advantages overexisting methods for checking sequence generation.<P>

<p>WENTAO MO. A Referral-Based Recommender System for E-Commerce (Under the direction of Dr. Munindar P. Singh).The thesis is intended to develop the technology and infrastructure to allow people to share knowledge with and learn from each other. A special kind of multiagent system, called multiagent referral system (MARS), is proposed. In MARS, each user is assigned a software agent, and software agents help automate the process of expertise location by a series of ?referral chains.? Unlike most previous approaches, our architecture is totally distributed and preserves the privacy and autonomy of their users. These agents learn models of each other in terms of expertise (ability to produce correct domain answers), and sociability (ability to produce accurate referrals). <P>

<p>HUANG, YI-AN. Anomaly Detection for Wireless Ad-Hoc Routing Protocols.(Under the direction of Wenke Lee.)<BR><BR>Mobile Ad-hoc networking (MANET) is an important emergingtechnology. As recent several security incidents remind us, noopen computer system is immune from intrusions. The routing protocolsin ad-hoc networks are key components yet vulnerable and presentspecial challenges to intrusion detection.<BR><BR>In this thesis, we propose an anomaly detection scheme for existingad-hoc routing protocols. Our approach relies on information from localrouting data and other reliable local sources. Our approach models thetemporal/sequential characteristics of observations and uses entropyanalysis for feature selection. Classification algorithms are used tocompute anomaly detection models. We present case studies on DSR andDSDV protocols using the ns-2 simulator. The overall results thusfar are very encouraging. We discuss how the available information from arouting protocol influences anomaly detection performance and attemptto provide guidelines on what features we need for anomaly detection.<BR><BR>Finally, we also discuss several challenging issues and propose ourfuture work.<P>

<p>The explosive growth in worldwide communication via the Internet has increased the reliance oforganizations and individuals on the electronically transmitted information, which consequentlycreated rising demands to protect data from information leakage, corruption or alteration duringtransmission. Various security service requirements are demanded among different applications andcustomers with consideration of respective data sensitivity level, performance requirement andmonetary investment. It becomes important to provide end-to-end security service commitment tosatisfy the diverse customers needs. We expect the Quality of Protection (QoP) to fulfill end-to-endsecurity service commitment to be integrated within the emerging QoS networks to support secure QoSInternet service. For clarity, we call both of QoP and QoS ?Quality of Network Services? (QoNS).The security issues surrounding the QoNS (QoP and QoS) provisioning have been studied in my PhDresearch. The thesis is composed of two main parts, i.e. QoP security and QoS security. First, thepolicy issues of QoP security service are analyzed and automatic policy generation algorithms arepresented. Furthermore, a signaling protocol is designed to provide end-to-end security service forQoP. The protocol is designed to be secure to protect messages against possible forgery andmodification attacks. Second, the threats to the QoS signaling protocol RSVP are analyzed andcountermeasures are proposed. In addition, the intrusion detection methods for QoS attacks directly ondata flow are investigated and experimented.<P>

<p>TCP Emulation at Receivers (TEAR) is a TCP-friendly protocol that has been proposed for real-time multimedia flow control. Most best-effort traffic on the Internet is well-served by TCP, the dominant transport protocol. However, many applications with real-time constraints, such as multimedia streaming find TCP's response to congestion quite severe and too drastic to deliver acceptable end-user quality. TEAR was designed in order to provide smoothly varying rate changes for such applications while being friendly to competing TCP flows. In this thesis, weevaluate and verify TEAR's performance over the Internet. We verify TEAR's fairness to TCP, the smoothness of its rate fluctuations and its stability in the presence of network perturbations. We then adapt TEAR to run over wireless networks and consider using round-trip delay instead of packet loss as a congestion indication for wireless networks. We present the results of our experiments with TEAR over commercially deployed wireless networks in South Korea. We recount our experiences with the loss-delay characteristics of these networks. We analyze how TEAR competes with TCP, which is known to suffer from severe degradations in environments where the underlying network is unreliable. We then study TEAR's rate variations and the increased longer-term predictability it provides over wireless networks. Finally, we compare the performance of a reliable protocol we built over TEAR with TCP.<P>

<p><p>We consider the problem of scheduling a differentiated mix of (IP DiffServtype) traffic in a broadcast single hop WDM network. Tunability isprovided only at one end, namely at the transmitter. Our objective is todesign transmission schedules to schedule a mix of guaranteed service andbest-effort traffic, by allocating the excess bandwidth to best-efforttraffic in a manner. We consider scheduling algorithms forboth systems with negligible transceiver tuning latency and systems withnon-negligible transceiver tuning latency. We map the optimal preemptive scheduling algorithm to schedule packets in a system withnegligible transceiver tuning latency and use the nonpreemtive scheduling algorithm for systems with non-negligible transceiver tuninglatency. We propose mechanisms for the allocation of slots to best efforttraffic for the preemptive and non-preemptive scheduling algorithms. Wepresent the results of extensive simulation study that evaluate theperformance of the best effort allocation schemes in terms of channelthroughput and schedule lengths. We identify the effect of schedulelengths and percentage reservations for guaranteed traffic on schedulingdelay, and develop heuristics that effectively decouple the effect ofschedule lengths on scheduling delay. We then present the architecture ofthe highly extensible WDM simulator component we implemented over .The component can be used to study the performance of collision-freescheduling algorithms and queuing mechanisms on a TT-FR broadcast singlehop WDM network. Finally, we use this simulator component to study theeffects of different system parameters, such as slot demands andreservations on scheduling delay, and delay jitter.<P>

<p>Wavelength division multiplexing (WDM) in optical fiber networks iswidely viewed as the technology with the potential to satisfy theever-increasing bandwidth needs of network users effectively and on asustained basis.In WDM networks, nodes are equipped with optical cross-connects(OXCs)</em>, devices which can optically switch a signal on any givenwavelength from any input port to any output port.This makes it possible to establish lightpaths</em> between any pair of network nodes.A lightpath is a clear channel in which the signal remainsin optical form throughout the physical path between the two endnodes.The set of lightpaths established over the fiberlinks defines a .Consequently, the problem arises of designing virtual topologies tooptimize a performance measure of interest for a set of trafficdemands.<p>With the deployment of commercial WDM systems, it has become apparentthat the cost of network components, especially line terminatingequipment (LTE) is the dominant cost in building optical networks, andis a more meaningful metric to optimize than, say, the number ofwavelengths.Furthermore, since the data rates at which each individual wavelengthoperates continue to increase (to OC-192 and beyond), it becomes clearthat a number of independent traffic components must be multiplexed inorder to efficiently utilize the wavelength capacity.These observations give rise to the concept of ,which refers to the techniques used to combine lower speed componentsonto available wavelengths in order to meet network design goals suchas cost minimization. Traffic grooming is a hard problem in generalwhich remains computationally intractable even for simple networks.<p>We consider the problem of traffic grooming in ring, star andtree topologies. We provide theoretical results regarding achievabilitybounds for these networks as well as practical frameworks to obtainincreasingly better feasible solutions with the expenditure of morecomputational power.<P>

<p><p>Films and novels effectively convey intriguing stories, powerful emotions, and meaningful messages to their audiences. Telling interactive stories in a virtual environment seems a natural progression of the narrative. Users find virtual environments more engaging when they perceive that they have agency within those environments. The greater the sense of freedom they have over choosing and executing their own actions, the greater their sense of agency will be. However, in order to maintain the coherence of their stories, current attempts at interactive narrative environments often limit a users sense of agency by restricting his ability to affect critical elements of the story. The process of mediation is designed to give users as great a sense of agency in an unfolding narrative as possible while still maintaining the narrative's coherence and goals. This is accomplished by making the system, user, and author collaborators in the production of the storyline. This collaboration takes the form of a mediation system constantly rewriting the narrative within the confines of the author's goals as the user interacts with characters and objects in the virtual environment.</p><p>Mediation assumes that an effective narrative storyline can be modeled by a fully ordered series of actions (know as a plan) performed by one or more virtual characters in a virtual environment. A mediation system is composed of three primary components: a speculative planner, a decision cache data structure, and an execution monitor. The speculative planner is constantly analyzing the storyline to determine what actions a user could perform that would prevent the storyline from reaching its end. For each such action it utilizes a narrative planner to determine if the storyline can be rewritten around the action or if the action must be prevented. One way of realistically preventing an action is modeled by failure modes. Failure modes are alternative actions that can be substituted by the system when necessary for user-attempted actions.</p><p>The decisions of the speculative planner are stored in the decision cache data structure that is used by the execution monitor. The execution monitor observes users in the virtual environment and the actions they perform. If any user attempts an action in the decision cache, the execution monitor alerts the speculative planner and takes preventive action if necessary.</p><p>Mediation is a prime candidate for use in narrative environments that require a great deal of user interaction and freedom. Most notable are entertainment and educational systems. More generally, mediation concepts can be applied to many varying collaborative application environments, such as on-screen agents that advise or assist users in the achievement of goals. Mediation frees users from the limitations of a system's author's ability to predict all combinations of actions a user may wish to perform in a virtual environment.</p><p>In this work we describe a prototype of the execution monitor component of mediation that has been implemented in Mimesis, a virtual environment architecture designed for interactive narrative [37].</p><P>

<p>Recent advances in technology have led to the widespread deployment of computational resources and network-enabled end-devices. This poses new challenges to network engineers: how to locate a particular service or device out of hundreds of thousands of accessible services and devices. One of the major issues involved is the efficient storage, retrieval and dissemination of information about available services. Well known relational database techniques are not very efficient in these situations because our primary concern is the determination of availability of a service, not the retrieval of data. Also, database techniques involve additional overhead for indexing and query processing. We propose a novel scheme for efficient determination of the availability of services called SRDP(SummaryRepresentation for service Discovery Protocols). SRDP makes use of a sub-string search algorithm based on hashing techniques. For this purpose, service descriptions are treated as strings and queries are treated as sub-strings. Information about each service and its attributes is stored as a 128 bit signature in a hash table. To exploit all bits of the signature, a signature creation scheme using the characteristics of the distribution of characters in English language is employed. For the hash table, a Fibonacci hash based scheme and a CRC hash based scheme using primitive polynomials are tested for their effectiveness as hash functions. Results are presented from tests performed using actual URL data obtained from the Internet. Finally we compare the performance and memory requirements of our scheme with a Bloom-filter based approach. Results show that SRDP executes twice as fast, consumes 80% less memory and still provides false drop probabilities comparable to a Bloom filter based approach.<P>

<p>Elhaddad, Mahmoud Shawky. Adaptive Multipath Traffic Allocation in TCP/IP Networks.(Under the direction of Dr. Injong Rhee and Dr. Munindar Singh)Balancing network traffic among multiple paths connecting ingress-egress pairspromises better utilization of network links and improved servicequality for user-flows.Research into optimized adaptive traffic allocation yielded techniquesthat tradeoff convergence speed to stability and/or fail to incorporate knowledgeabout the behavior of congestion control mechanisms, making their evaluationa difficult, if possible task -- both analytically and experimentally.In this thesis, we consider load balancing in multipath IP networks where thenumber of flows between ingress-egress pairs is a slow-changing process andTCP-friendliness is adopted-by or imposed-on all flows. Provided that packetordering is preserved, we present an analytical characterization of the throughput-optimalfractional allocations of flow packets in terms of the TCP-fair share alongeach candidate path; and show that optimally splitting all network flows resultsin efficient and globally fair sharing of network resources. For the estimationof the fair share along network paths, we demonstrate that TCP-fairness in sharingbottleneck bandwidth can be modeled as weighted max-min, where the weight vectorcorresponds to the Bulk Transfer Capacity (BTC) of the bottlenecked path. Policingat the ingress routers limits connections to their computed fair rates, therebyeliminating TCP bias against connections passing through multiple bottlenecksand minimizing packet losses at internal routers. Given minimal loss rate andsmall bounded delay skew among alternative paths, packet resequencing at theegress routers can be applied effectively.We also introduce AMTA -- a centralized traffic allocation service for MPLSnetworks based on the optimality and fairness results described above, and extendedto handle flows with limited throughput demand. The robustness of AMTA underrelevant scenarios is demonstrated through simulations.<P>