Entrepreneurship has become a defining force in the technology sector, with startups and unicorns largely fueled by computer science skills. However, most undergraduate computer science programs focus on technical competencies while outsourcing entrepreneurial education to business schools, where curricula are often generic and disconnected from the realities of CS-driven ventures. In addition, existing capstone and software engineering courses emphasize the technical details of development rather than entrepreneurial processes. This paper presents a curriculum that explicitly integrates artificial intelligence (AI) tools into entrepreneurship learning for computer science students. The program is designed to help students move beyond the notion that entrepreneurship is accidental or sudden and instead develop sustained exposure to ideation, customer discovery, prototyping, and pitching. Our project-based, one-year program equips students with entrepreneurial skills while leveraging AI for brainstorming, market validation, prototyping, and storytelling. We argue that, particularly in tight labor markets where evidence suggests graduates increasingly turn to entrepreneurship, there is an urgent need to embed CS-centered entrepreneurial education into undergraduate programs.

The explosive growth of data-intensive applications and Generative AI (GAI) workloads has led to unprecedented demands on computing resources. Virtual Machine (VM) migration is pivotal in dynamically adjusting resource distribution across workloads. However, traditional reactive approaches often fall short in adapting to network changes and dynamic workloads. This paper presents a Digital Twin (DT) framework integrated with a data center to enhance resource utilization. The framework combines real-time monitoring, time-series forecasting, and Mixed-Integer Linear Programming (MILP) optimization to predict future bandwidth demands, CPU utilization, and memory usage, thereby determining optimal VM migration and placement strategies. Our analysis reveals that integrating forecasting with optimization reduces CPU load variance across servers by up to 50%. Compared to prior reactive or heuristic-based methods, our forecast-aware optimization framework achieves significantly more uniform resource distribution. Furthermore, capping server CPU load at 50% of capacity nearly eliminates variance, underscoring the effectiveness of the proposed model in stabilizing data center workloads.

Packet classification plays a crucial role in numerous network services, including Quality of Service (QoS), Firewalls, and data streaming. In our research, we introduce a cutting-edge method for packet classification utilizing a modified multi-dimensional range tree, which enables effective rule storage and swift querying. This method provides a comprehensive solution for packet classification across various rulesets. Our use of the multi-dimensional tree structure significantly enhances the efficiency of packet classification, leading to better overall performance. The worst-case time complexity for our method is$O(\log^{d}n)$, with$n$representing the number of rules and$d$the number of dimensions/fields. Our method surpasses PartitionSort, which has a worst-case time complexity of$O(n^{1/d})$, underscoring the improved efficiency of our technique. Our approach includes two types of classifiers: one that identifies the first applicable rule (Classify First), and another that finds the most specific rule (Classify Specific) for a given packet. To assess the effectiveness of our method, we performed empirical tests using the Classbench dataset to simulate real-world conditions. We created standard 5-tuple rulesets of various sizes and seeds and compared our method with other techniques such as PartitionSort, Priority Tuple Space Search (TSS), HyperSplit and HyperCuts. Our findings show that our first rule classifier surpasses other techniques in all ruleset sizes, being 600% faster than PartitionSort for 64k rulesets. The specific rule classifier also shows increased efficiency, nearly matching PartitionSort for smaller rule sets and exceeding it by 30% for 64k size rulesets. Furthermore, our Classify First approach is shown to be empirically faster than other well-studied techniques such as SmartSplit, HyperSplit, HyperCuts, TSS, and others.

Buffer capacities at routers are ever-increasing to accommodate the extreme-scale increase in the volume of incoming traffic. Sophisticated packet classification is being adopted to address challenges in meeting application demands. With the number of rules for classification and packets arriving at routers per second reaching 100's of thousands to millions, special hardware is also being built for packet classification to increase throughput at routers. Sorting packets (based on various conditions) in the buffers offers a significant advantage for the packet classification process. The sorting step is a time-consuming step given the large volume of packets in the incoming buffers. We propose a technique to approximately sort the packets by capping the maximum number of comparisons that can be made. We show that the performance of well-known decision tree-based packet classification methods such as HyperCuts, EffiCuts, and SmartSplits can be improved by more than 32% with approximate sorting for when the number of packets is less than 10K at any given time. If the number of packets in the arriving buffer is greater than 10K, we can divide them into smaller portions to achieve similar gains.

Time-evolving web and social network graphs are modeled as a set of pages/individuals (nodes) and their arcs (links/relationships) that change over time. Due to their popularity, they have become increasingly massive in terms of their number of nodes, arcs, and lifetimes. However, these graphs are extremely sparse throughout their lifetimes. For example, it is estimated that Facebook has over a billion vertices, yet at any point in time, it has far less than 0.001% of all possible relationships. The space required to store these large sparse graphs may not fit in most main memories using underlying representations such as a series of adjacency matrices or adjacency lists. We propose building a compressed data structure that has a compressed binary tree corresponding to each row of each adjacency matrix of the time-evolving graph. We do not explicitly construct the adjacency matrix, and our algorithms take the time-evolving arc list representation as input for its construction. Our compressed structure allows for directed and undirected graphs, faster arc and neighborhood queries, as well as the ability for arcs and frames to be added and removed directly from the compressed structure (streaming operations). We use publicly available network data sets such as Flickr, Yahoo!, and Wikipedia in our experiments and show that our new technique performs as well or better than our benchmarks on all datasets in terms of compression size and other vital metrics.

Matrix multiplication is an essential operation in the field of mathematics and computer science. Many critical computations, such as matrix factorization and graph computations, cast the bulk of their computation in terms of this operation. Thus, it is crucial that this operation is tuned to the data being computed on. In the case of sparse domains, this translates to minimizing the traffic between the CPU and main memory as the amount of work is not necessarily sufficient to amortize the code of the data movement. The amount of memory required to store a nonnegative valued matrix of n rows and m columns requires (n × m) × log2(n) bits. When these dimensions are converted to real world scenarios, for example, a one billion by one billion matrix will require 1000 petabytes of memory, which is impractical. This hinders the ability to perform any operations on the matrix.In this paper, we propose techniques for performing Matrix-Matrix multiplication directly on compressed data stored in two different compression data structures. The structures we consider are the well-known compressed sparse matrix and the Compressed Binary Trees [1]. We test our algorithm on extremely large matrices, in the order of 100s of millions with various levels of sparsity. We show for matrices of order 100 million with 10 million nonzero elements, the space required to store the matrices using the CBT representation is about 6.4MB and requires 13.52s to complete the multiplication using the sequential algorithms provided in this paper.

Time-evolving graphs are structures that encapsulate how a graph changes over time. Thus, we not only have to deal with large graphs consisting of nodes and edges in the billions, but we must also keep track of when these edges activate and deactivate over long lifetimes. In this age of big historical data, we must make use of efficient time-evolving graph compressions, or we will find ourselves quickly out of main memory. These time-evolving graph compressions must not only be space efficient, but must also facilitate fast querying directly on the compressed graph. In this paper, define several novel time-evolving graph problems and develop algorithms to solve them directly on various, massive, synthetic and real-world time-evolving graphs compressed using our technique. Our experiments provide details of the compressed graph sizes, algorithm run times, and other metrics.

Time-evolving graphs represent a set of individuals (nodes) and their edges (relationships) over time. How these graphs are represented in data structures determines what information is easy to obtain from them. Now that we have such massive social networks with dynamic lifetimes, even basic data structures are too large to fit into main memory. Clearly, this poses a problem to areas such as time-evolving graph pattern analysis. Therefore, it is an interesting field of study to design time-evolving graph compressions that can efficiently answer certain queries about the graph at any given point in time.If a single snapshot of a graph at a moment in time can be considered a 2D matrix, then can we visualize these time-evolving graphs as 3D matrices and then use a novel technique to compress the entire graph over time. Our technique is based on our previous work using compressed binary trees. In this work, we adapt our strategy to compress time-evolving graphs, rather than static ones. We manage to maintain our minimal main memory overhead by not requiring an intermediate structure (e.g. adjacency list) to compress. This compression is queryable, meaning that the data can be read without decompression. It is also streaming, meaning that the data can be changed without decompression. This includes adding/removing edges in individual frames. We test our algorithms on public, anonymized, massive, time-evolving graphs such as Flickr, Yahoo!, and Wikipedia. Our empirical evaluation is based on several parameters including time to compress, size of compressed graph, and time to execute queries. Our compression rates are highly competitive, as we achieve the smallest representation of 4.9GB on our largest dataset which only spans three days yet occupies 21.5GB of space.

In this era of social networks, we find ourselves with a collection of massive, changing graphs. Each of these graphs contain a set of nodes (individuals) and a set of edges among the nodes (relationships). How a graph is represented in a data structure determines what information is easy to obtain from it. However, many graphs are so large that even basic data structure representations (e.g. adjacency lists) do not fit in main memory. Therefore, it is an interesting field of study to design compressed data structures that facilitate certain query functions. Since we are dealing with social networks, our structure will also be able to stream edges directly into the compressed graph. We introduce our social network compressed data structure as an indexed array of compressed binary trees. We further minimize memory overhead by directly constructing the graph without any intermediate structure. We also provide fast access methods for edge existence (does an edge exist between two nodes?), neighbor queries (list a node's neighbors), and streaming operations (add/remove nodes/edges). We test our algorithms on public, anonymized, massive graphs such as Friendster, Live-Journal, Pokec, Twitter, and others. Our empirical evaluation is based on several parameters including time to compress, memory required by the compression algorithm, size of compressed graph, and time to execute queries.

Aggregating common-path network flows (in the network interior) helps in improving the applications delivery performance. From the network edge perspective, the sender and receiver-ends of the respective applications need to have a typical one-to-one mapping. An aggregation framework in the network therefore needs an effective forking to maintain the one-to-one mapping of the flows. In this demo, we show a working prototype of TCP-based join and fork framework that we have developed and implemented using SDN. Moreover, our framework is implemented in such a way that the aggregation and splitting of flows are performed seamlessly without intervention from the end-user applications. We believe such transparency in the framework would attract existing (unmodified) applications to easily adapt and benefit from our implementation.

Fog computing is a promising technology that enables users to perform time-sensitive IoT analytics at locations near the clients. Recent studies have shown the improved delivery performance of fog networks by comparing them with traditional cloud-based architectures. In this paper, we focus on further improving the delivery performance of a fog network. We first show that the performance of fog networks in their native form suffers from unfairness among the IoT clients, which results in causing heterogeneous delivery delays. As a consequence, the fog node (which performs analytics) would need to wait for a prolonged time, until all IoT clients send their data. In this paper, we address this critical fairness issue from the network point of view, and propose a framework to achieve fair delivery of clients' data to the fog node. To this end, we identify the transport layer aspects that contribute to the unfairness, and appropriately augment the transport layer in order to enable fairness among the IoT clients. We also develop an experimental prototype of MQTT-based IoT nodes using Raspberry Pi devices, and extensively study the network performance, as well as demonstrate the efficacy of the proposed framework.

Latest research in smart grid communications has advocated the aggregation of multiple traffic flows in order to achieve an improved throughput. While aggregation improves the overall throughput, the individual flows still suffer from unfair throughput performance. As a result, the enablers for time sensitive smart grid services such as load-shedding that require a timely report of data are the most affected. In this paper, we propose a novel SDN-based framework to provide fairness among smart-meters, through flow aggregation and scheduling. By exploring the SDN's flow-level manageability features, for the first time in this paper, we present an implementation-based architecture to perform effective aggregation-and-scheduling of traffic flows. The proposed framework ensures fairness (among the smart-meters), as well as improve the throughput performance. Our extensive experiment results validate the efficacy of our proposed framework.

Social networks are constantly changing as new members join, existing members leave, and `followers' or `friends' are formed and disappear. The model that captures this constantly changing graph is the streaming graph model. Given a massive graph data stream wherein the number of nodes is in the order of millions and the number of edges is the tens of millions, we propose a simple algorithm to compress this graph without having read in the entire graph into the main memory. Our algorithm uses the quadtree data structure that is implicitly constructed to produce the compressed graph output. As a result of this implicit construction, our algorithm allows for node and edge additions/deletions that directly modifies the output compressed graph. We further develop algorithms to solve edge queries (is there any between two nodes?) and node queries (for a given node, list all its neighbors) that directly operates on the compressed graph. We have performed extensive empirical evaluations of our algorithms using publicly available, large social networks such as LiveJournal, Pokec, Twitter, and others. Our empirical evaluation is based on several parameters including time to compress, memory required by the compression algorithm, size of compressed graph, and time and memory size required to execute queries. We have also presented extensions to the compression algorithm that we have developed.

Studying the properties of Online Social Networks (OSNs) and other real world graphs have gained importance due to the large amount of information available from them. These large graphs contain data that can be analyzed and effectively used in advertising, security and improving the overall experience of the users of these networks. However, the analysis of these graphs for studying specific properties requires combinatorially explosive number of computations. Compute Unified Device Architecture (CUDA) is a programming model available from Nvidia for solving general-purpose problems using the massively parallel and highly multi-threaded Graphics Processing Units (GPUs). Therefore, using GPUs to solve these types of problems is appropriate. In addition, due to the properties of real-world data, the graphs being considered are sparse and have irregular data dependencies. Hence, using efficient techniques to store the graph data for initial preprocessing and final computation by taking advantage of heterogeneous CPU-GPU systems can address these issues. In this paper, we are interested in studying different properties of these real-world entities that transform into the following graph problems: a) identifying a missing edge, which when added would result in maximum increase in the number of triangles, b) identifying an existing edge whose removal would result in the maximum decrease in the number of triangles, c) identifying an existing edge whose removal would increase the number of connected components in the graph. In this paper, we develop and implement algorithms to solve the above problems using both CPU and GPU. Specifically, given a graph G = (V, E), we provide algorithms for the following: a) find (vi, Vj) ∉ E, such that Δf- Δcis maximized, where Δfand Δcare the number of triangles in Gm= (V, E ∪(vi, Vj)) and G, respectively, b) find a (vi, Vj) ϵ E, such that Δc- Δfis maximized, where Δfand Δcare the number of triangles in Gm= (V, E \ (vi, Vj)) and G = (V, E), respectively, c) find a (vi, Vj) ϵ E, such that Φc> Φc, where Φcand Φcare the number of connected components in Gm= (V, E \ (vi, Vj)) and G = (V, E), respectively. We implement the algorithms using a GPU and achieve a 10 × speedup as compared to a sequential implementation. Thereafter, we design a heuristic for finding an edge whose existence would result in the maximum increase in the number of triangles. The heuristic is implemented and the results are reported and compared to those of the regular algorithm on the GPU.

Radio Frequency IDentification (RFID) system is a highly sought-after technology prominently used in the automation, logistics, and supply-chain industries. EPC Gen-2 is the current standard RFID air-interface protocol in the industry. Underlying this standard is the Q-adaptive MAC protocol, which is used to identify and read the tags, by stochastically arranging them over time. The Q-adaptive protocol's performance is sensitive to the number of tags placed under the vicinity of the reader. With the current era of ‘item-level tagging’ witnessing an increased number of tags in a given area; mathematically understanding the performance of the protocol in these large-scale RFID systems becomes essential. Recent works have established the importance of the Q-adaptive protocol, by analyzing its performance with the help of Markov-chain models. However, these analyses suffer from the common ‘state-space explosion’ problem, as the state-space increases quadratically with an increasing number of participating tags. Hence it is essential to come up with a scalable analysis, whose computation model is insensitive to the number of tags. To this end, in this paper, we propose a scalable bound-based solution to study the delay performance of Q-adaptive protocol. We derive the delay bound by exploiting the fact that, in the large number of tags regime, the Q-adaptive protocol rapidly reaches to theoretical maximum performance and stays reasonably close in that optimal region for most of the time. Our extensive simulation results validate our bound-based solution with reasonable accuracy.

Sink trees such as Breadth-First Search (BFS) or Shortest-Path Tree (SPT) are essential in Wireless Sensor Networks (WSNs) for various purposes such as data gathering, aggregation, clustering, and synchronization. These trees minimize the path-lengths reachable from root node to any other node in the network. With the energy-bound sensor nodes, it is vital to construct such trees in an effective manner, by minimizing the number of message exchanges. By exploiting the broadcast nature of the underlying wireless medium, we present distributed energy-efficient algorithms for constructing BFS and SPT sink trees in WSNs. To mitigate collisions, we propose a simple distributed collision avoidance mechanism that enables efficient functioning of our tree construction algorithms. Extensive simulation study is performed for different networks by varying the size, degree, and depth. Our promiscuous learning based algorithm outperformed by incurring up to 66% less (message) exchanges than the state-of-the-art tree construction algorithm.

Reducing collisions caused by the concurrent transmissions of RFID chips (tags) is a crucial research topic in designing efficient air-interface protocols in passive-tag RFID systems. Different anti-collision protocols are proposed to improve the tag reading efficiency, by ordering the tags' participation over a period of time, by stochastic or deterministic manner. All existing anti-collision protocols follow a `single line of thought'; wherein the onus for mitigating collisions is always on the reader, with no active role being played by the tags. We propose a fundamentally different strategy of enabling communications among the tags, especially to assist the reader in further resolving collisions. Overthrowing the conventional wisdom of limited RFID communication allowed only between the reader and tags, recent experimental studies have shown the possibility of Tag-to-Tag (T2T) communication, in industry popular UHF RFID systems. Two tags within the Near-Field (NF) of each other, can electromagnetically couple with and therefore communicate, as long as they are receiving energy from the reader. A critical property of NF communication systems is their small reading range, about 30mm for a 900MHZ UHF RFID system. This provides a two spheres of communication, and enables concurrent T2T communications to happen within the long-range (around 6m) of a UHF RFID system. In this NF UHF passive tag RFID system, a tag can promiscuously listen to its NF neighboring tags' collided-transmissions, and give them a second chance for identification. In this paper, we will augment two different variants of frame-slotted ALOHA protocols to support promiscuous learning of NF tags, and study the change in reading efficiency in terms of delay and energy costs. Our detailed performance evaluation study will demonstrate the efficacy of our proposed augmented protocols, both in terms of delay and energy costs.

Multicasting is an efficient way to deliver multimedia content (streaming, for instance) to different locations in the network. While end-to-end real-time constraints are important for interactive applications, sustained availability of bandwidth is more important to the destinations for multimedia streaming. In this research, we address the problem of multi-stream multi-source multicast routing problem (MMMRP) where each data stream could have multiple sources that will serve it and each source can serve multiple data streams in a sustained manner. The goal of MMMRP is to construct a routing forest for each of the data streams and the destinations while maximizing the residual bandwidth. The residual bandwidth is the available bandwidth after all destinations have been served with their desired streams. Our problem is shown to be NP-hard and we provide an Integer Programming formulation together with an efficient heuristic algorithm (MMForests) based on widest-path algorithm. Our empirical evaluations show that our algorithm MMForests can construct the multicast routing trees both quickly and keeping the residual bandwidth close to the optimal.

Data gathering is a typical operation in wireless sensor networks where data flow through a data gathering tree towards a sink node. Plenty of work had been done on constructing energy-efficient data gathering trees at the routing layer. However, data generation in wireless sensor networks could be bursty as it is driven by the events of interest. Without any sleep scheme, the sensor nodes will stay idle for most of the time. Therefore energy-efficient data gathering trees alone are not enough for energy saving. We propose a routing layer data gathering sleep scheme (DGSS) which could be incorporated into existing data gathering tree formation algorithms to save unnecessary energy consumption due to idle listening and meanwhile adapts to bursty traffic condition. We compare DGSS with DMAC, a popular energy efficient MAC protocol for data gathering, through simulations and show that DGSS can perform better than DMAC for bursty traffic at relatively high data rates.

DMAC is a popular data gathering MAC protocol for wireless sensor networks. It employs staggered sleep-awake schedules to enable continuous data forwarding along a data gathering tree, resulting in reduced end-to-end delays and energy consumption. In this paper we present a generalized model for the DMAC protocol and for this generalized model we have analyzed end-to-end delay and energy consumption with respect to the source node for both constant bit rate traffic and stochastic traffic following a Poisson process. The stochastic traffic scenario is modeled as a discrete time Markov chain and expressions for state transition probabilities, average delay and average energy consumption are developed and it is shown that these can be evaluated numerically. Simulations are carried out with various parameters and the results are in line with the analytical results. Both analysis and simulations indicate that DMAC is more suitable for constant bit rate traffic than stochastic traffic.

Virtual world and other collaborative applications are increasingly becoming popular among Internet users. In such applications, users interact with each other through digital entities or avatars. In order to preserve the user experience, it is important that certain Quality of Service (QoS) requirements (e.g., delay and bandwidth) are satisfied by the interactions. These QoS requirements are usually defined by the application designer. When applications with such QoS requirements are being deployed on a network of servers, an appropriate set of servers capable of satisfying the QoS constraints of the interactions must be identified. This identification process is nothing, but the subgraph homeomorphism problem. In this paper, we present polynomial-time solutions for a special case of this problem viz. subtree homeomorphism problem, wherein the guest and the host graphs are both trees. We also discuss generalizations of the subtree homeomorphism problem and present polynomial-time solutions.

While in-network aggregation and query processing are the common forms of collecting data in a typical wireless sensor network, continuous monitoring allows for more complex querying of the data collected. The process of collecting this data subject to constraints on the network resources is termed adaptive sampling. In this paper we present a simple quantitative scheme for adaptive sampling by using a vector of suitably defined parameters. The adaptive sampling vector (ASV) specifies the baseline of the data which needs to be collected to meet information quality needs.

Consider a wireless sensor network where each node has K radios r1,r2, ⋯ , rKsuch that the one hop reachability distance (resp. energy expended) of (resp. by) radio riis greater than that of rj1 ≤ j <; i ≤ K. Given such a network, the problem of energy efficient radio activation is to minimize the total energy spent by the active radios across all nodes in order to maintain a connected network. We show that this problem is NP-Hard. We initially pay attention to the case of K = 2 and discuss a basic version of the radio activation problem in such networks. We propose approximation methodologies for solving this problem. Our analytical and experimental studies reveal that the greedy algorithm and the minimum spanning tree solution have the best worst case performance while the greedy algorithm has the best average case performance. To the best of our knowledge, this is one of the first few works to focus on optimal radio activation in generic multi-radio wireless networks.

Wireless Sensor Networks (WSNs) open up wide range of possibilities for new applications such as monitoring and surveillance applications due to their low-cost and easy deployability. However, the limitations in terms of limited CPU processing power, memory, and battery, bring in a great deal of challenge to provide adequate security for on-board data storage and communication. While many works on secure key establishment exist, most of them assume that sensor nodes are either in fixed location or move within a single WSN. As WSN technology develops, there are more applications coming up which require a sensor node to roam across multiple WSNs. This paper presents a roaming protocol that provides security for the on-board sensory data (in terms of data access) while allowing a sensor node to move across multiple WSNs.

Data generation in wireless sensor networks could be bursty as it is dictated by the presence or absence of events of interest that generate these data. While conventional sensor nodes possessed only one radio interface, next generation sensor nodes are expected to have two (possibly more) radio int

We can improve the end-to-end throughput between a sender and receiver in a wireless network using multiple paths which do not interfere with each other. Given finding such paths is computationally hard, we present a heuristic that is amenable to distributed implementation. This heuristic allows for the possibility of interfering links but schedules the transmission in ways to achieve the maximum possible throughput. One can characterize interfering links as either destructive or non-destructive, the latter of which does not affect the throughput, if transmission is properly scheduled. We present a distributed algorithm which exploits this knowledge to find multiple s-t paths such that high throughputs could be achieved despite the interference. On a wireless network with n nodes, our distributed algorithm has a time and message complexity of O(n2).

Currently, workflow systems are either XML based or component based. Both paradigms have usability deficiencies. XML is not designed for procedural programming. Legacy code is difficult to adapt to component based systems. We propose a new paradigm by adding workflow keywords to an existing high-level language. This approach, called GroupSpeak, uses a procedural style of programming and allows for easy introduction of workflow patterns to legacy code. The programmer can leverage their existing knowledge of the high-level language to easily add workflow capabilities to their applications.

We can improve the end-to-end throughput between a sender and receiver in a wireless network using multiple paths which do not interfere with each other. Given that the problem of finding such paths is computationally hard, the paper focuses on finding multiple paths which may have interference between them, but still are able to obtain the maximum possible throughput. It is achieved by observing that the pattern of interference is more important than the number of interfering links. The nature of path sets with non-destructive interference is discussed and based on these observations, combinatorial techniques for finding interference aware disjoint paths in a wireless network are presented. Simulation results indicate that the proposed solutions achieve throughputs that are significantly higher than the established theoretical results.

Collaborative multimedia applications (CMAs) on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include networked games and collaborative design and simulation. An important challenge in realizing CMAs is obtaining floor control, a problem in which the end-users compete among themselves to gain exclusive access to a shared resource. In this paper, we present deterministic and randomized distributed mechanisms for solving the floor control problem. In particular, we adapt the well-known MAC protocols viz. distributed queue dual bus (DQDB), ALOHA, and carrier sense multiple access (CSMA) as solutions for the floor control problem. Central to our adaptation is an algorithmic methodology that efficiently virtualizes the underlying network connecting the CMA participants so as to enhance the proposed solutions' performance. We present analytical and experimental studies on the performance of the proposed floor control protocols that bring out their essential characteristics.

Online energy aware routing in wireless networks is the problem of finding energy efficient routes that maximize the network lifetime without the knowledge of future message flows. To maximize network lifetime, the paths for message flows are chosen in such a way that the total energy consumed along the path is minimized while avoiding energy depleted nodes. Finding paths which consume minimum energy and finding paths which do not use energy depleted nodes lead to conflicting objectives. In this paper, we propose a two-phased energy-aware routing strategy that balances these two conflicting objectives by transforming the routing problem into a multi-metric widest path problem. We find that the proposed approach outperforms the best known algorithm in literature. We also demonstrate a simple but insightful relationship between the total energy required along a path and the minimum remaining energy of a node along the path.

In this paper, we introduce a framework termed Accelerated Frame Slotted Aloha (AFSA) for reducing the average reading time of passive RFID tags in dense environments. The proposed framework can be used in conjunction with almost all tag reading protocols that are based on frame slotted Aloha. AFSA reduces the tag reading time by decreasing the time wasted due to collisions and idle slots. We also discuss extensions of AFSA to read passive tags in a mobile setting. Simulation results show that AFSA can significantly reduce the average tag reading time with respect to the base protocol under both static and mobile settings.

Computer supported collaborative applications on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include video-conferencing, distributed database replication, and online games. This type of application requires a multicasting subnetwork, using which messages should arrive at the destinations within a specified delay bound. These applications also require that destinations receive the message from the source at approximately the same time. The problem of finding a multicasting subnetwork with delay and delay-variation bound has been proved to be an NP complete problem in the literature and heuristics have been proposed for this problem. In this paper, we provide an efficient heuristic to obtain a multicast subnetwork on an overlay network, given a source and a set of destinations that is within a specified maximum delay and a specified maximum variation in the delays from a source to the destinations. The time-complexity of our algorithm is O(|E|+nk log(|E|/n)+m2k), where n and |E| are the number of nodes and edges in the network, respectively, k is the number of shortest paths determined, and m is the number of destinations. We have shown that our algorithm is significantly better in terms of time-complexity than existing algorithms for the same problem. Our extensive empirical studies indicate that our heuristic uses significantly less runtime in comparison with the best-known heuristics while achieving the tightest delay variation for a given end-to-end delay bound

Computer supported collaborative applications on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include video-conferencing, collaborative design and simulation, distance learning, and online games. One of the important issues in collaborative applications is floor control wherein the end-users coordinate among themselves to gain exclusive access to the communication channel. An end-user who wins the floor, sends message to all other participating end-users. In this paper, to solve the floor control problem we present an implementation and evaluation of ALOHA and distributed queue dual bus (DQDB) distributed MAC (medium access control) protocols on overlay networks. As an initial step in the implementation of these MAC protocols, we propose an algorithm to construct an efficient communication channel among the Network Service Nodes (NSNs) in the overlay network. We also show that our implementation scheme (first one among decentralized floor control protocols) preserves the causal ordering of messages. We compare the efficiencies of the proposed implementation of floor control protocols using an analytical model that is verified using extensive simulation experiments.

There has been a constant barrage of worms over the Internet during the recent past. Besides threatening network security, these worms cause an enormous economic burden in terms of loss of productivity at the victim hosts. In addition, these worms create unnecessary network data traffic that causes network congestion, thereby hurting all users. To develop appropriate tools for thwarting quick spread of worms, researchers are trying to understand the behavior of the worm propagation with the aid of epidemiological models. In this study, we apply the classical SIS model and a modification of SIR model to simulate worm propagation in two different network topologies. Whereas in the SIR model once a node is cured after infection it becomes permanently immune, our modification allows this immunity to be temporary, since the cured nodes may again become infected, maybe with a different strain of the same worm. The simulation study also shows that time to infect a large portion of the network vary significantly depending on where the infection begins. This information could be usefully employed to choose hosts for quarantine to delay worm propagation to the rest of the network.

We present an asynchronous distributed algorithm to determine an ear decomposition of an arbitrary, connected, bidirectional network containing n-nodes and m-links which uses O(m) messages and which can be completed in O(n) time. Using the ear decomposition, we obtain the following results for a distributed network: 1) The distributed ear decomposition algorithm can be used to test biconnectivity, determine biconnected components, find cutpoints and bridges using O(m) messages in O(n) time. 2) The distributed ear decomposition algorithm can be used to test if a biconnected network is outerplanar using O(n) messages in O(n) time, and if the network is outerplanar, the embedding is also given using the same message and time complexity.

We develop and evaluate several heuristics for the construction of a multicast tree to transmit a given message of size r from a source to a set of destinations with guarantees on the end-to-end delay over a computer network. Different multicast trees can be constructed for various values of r. We consider delay sources on links to be from propagation and bandwidth availability. The heuristics that we have developed try to minimize the end-to-end delay of the multicast tree taking into consideration various switching architectures that range from pipeline to store-and-forward. Our evaluations of these heuristics consider various network generation models including locality, Waxman I and II, and transit-stub. We have evaluated multicast tree generation heuristics based on both shortest path and Steiner tree heuristics. A novel heuristic called grow-tree is proposed in this paper and it is based on both Kruskal's and Prim's minimum spanning tree algorithm. This heuristic performs admirably well in many network environments.

A dynamic ad hoc network consists of a collection of mobile hosts with frequently changing network topology. We propose a distributed algorithm that adapts to the topology by utilizing spanning trees in the regions where the topology is stable, and resorting to an intelligent flooding-like approach in highly dynamic regions of the network. Routing is performed using the spanning trees based on a hold-and-forward or shuttling method. We introduce the notion of connectivity-through-time and holding time to quantify the performance of the routing algorithms for various network connectivity scenarios. Using simulation, we study the throughput, reachability and message-reachability ratio of the proposed network under various connection/reconnection rates and holding times.

We present a distributed algorithm for rerouting to accommodate unlimited movement of mobile hosts in a mobile-mobile connection. The algorithm is source initiated-that is the source base station is responsible for the rerouting. The algorithm ensures that the establishment of non-optimal and incorrect paths is avoided and that no packets in the session are lost as there is always a path between the base stations in charge of the source and the destination. The design of this distributed algorithm ensures that the processing at the mobile hosts is kept to a minimum. In addition, the proposed framework for rerouting in mobile-mobile communications is independent of the type of rerouting scheme.

This paper describes the use of a new, multiple use laboratory facility in DSP education at the University of Oklahoma. The facility, funded by a combination of NSF grant money, industrial donations and university funds supports the teaching of signal and image processing, telecommunications and multimedia courses. This unique combination of related areas has fostered significant faculty and department interaction to support the strong telecommunications industry in the region. In fact, the laboratory was chosen as the model laboratory for the joint OU/OSU program in Telecomputing.

In recent years researchers have become increasingly convinced that the performance of information retrieval systems can be greatly enhanced by the use of key phrases for automatic conceptual document indexing and retrieval. In this article we describe two programs, INDEX and INDEXD, which locate repeated phrases in a document, gather statistical information about them, and rank them according to their value as index phrases. The programs show promise as the basis for a sophisticated conceptual indexing system. The simpler program, INDEX, ranks phrases in such a way that frequently occurring phrases which contain several frequently occurring words are given a high ranking. INDEXD is an extension of INDEX which incorporates a dictionary for stemming, weighting of words and validation of syntax of output phrases. Sample output of both programs is included, and we discuss plans to combine INDEXD with linguistic and artificial intelligence techniques to provide a general conceptual phrase-indexing system that can incorporate expert knowledge about a given application area. © 1990 John Wiley & Sons, Inc.