Applications such as collaborative mapping motivate a need for network-wide broadcasting in Mobile Ad Hoc Networks (MANET) with low-rate long-range links. Existing MANET protocols are inadequate in such low-capacity regimes due to their high use of control packets. We present a novel protocol called ECHO that constructs and maintains a broadcast backbone without using any control packets. Instead, using a field in the data packet header, a node transmits and listens for an “echo” of the specific packet to determine its membership in the backbone. ECHO is deterministic, source-independent, fully distributed, accommodates mobility, and balances battery consumption across nodes. We prove ECHO’s correctness and show that its communication complexity is lower than that of Multi-Point Relay (MPR) and Flooding, and comparable to that of Opportunistic Announcement (OA). Simulations over random mobile low-capacity networks show that ECHO provides at least a 30 percent better delivery ratio than Flooding, MPR, and OA for 50-node networks and dramatically reduces the communication load. Experiments on a 12-node testbed of goTenna mobile mesh networking devices show that ECHO reduces transmissions by about 3x and increases battery life by more than 50 percent over Flooding. ECHO’s performance advantages are crucial for scalable broadcast in low-power, low-capacity wireless networks.

Most Software-Defined Networking (SDN) based centralized architectures for mobile multi-hop wireless networks propose using one or more of the following: infrastructure for hosting stationary SDNC, out-of-band single-hop (direct) communication links, location-tracking, or existing IP connectivity. Such architectures are inadequate for infrastructure-less networks having low-capacity links and susceptibility to high interference, packet losses, and collisions. We describe a novel centralized opportunistic reactive routing protocol called CORR that allows a mobile SDN Controller (SDNC) to establish connectivity by identifying a subset of nodes in the network and making them the network backbone for forwarding packets. The SDNC learns the network topology via the backbone nodes, reducing the network load and improving the scalability. We evaluate CORR for a wide range of network sizes, densities, and traffic rates. Our ns3 simulation results indicate that CORR provides up to 10% better packet delivery ratio than AODV while incurring at least 1.5x lower network load and 3x lower delay, making it energy efficient and suitable for time-sensitive applications.

Decentralized off-grid short-burst communications for public safety and other applications require mobile wireless networks that can be inexpensively and instantly deployed to cover a large area. Maximizing coverage often necessitates trading bit-rate for range. The resulting capacity is insufficient to support existing mesh networking protocols due to their excessive control overhead, and motivates a fresh approach. We present the networking architecture of goTenna - a long-range lightweight device for mobile mesh networking. Our protocol uses a novel zero-control-packet approach for broadcasting and unicasting that builds state by observing packet header information. We describe its experimental evaluation using ns3, and on a goTenna testbed, concluding with some research challenges.

Quality of information (QoI) provides a context-dependent measure of the utility that a network delivers to its users by incorporating non-traditional information attributes. Quickly and easily predicting performance and limitations of a network using QoI metrics is a valuable tool for network design. Even more useful is an understanding of how network components like topology, bandwidth, and protocols, impact these limitations. In this paper, we develop a QoI-based framework that can provide accurate estimates for limitations on network size and achievable QoI requirements, focusing on completeness and timeliness. We extend this framework to model competing flows and data loads as random variables to capture the stochastic nature of real networks. We show that our framework can provide a characterization of delays for satisfied queries to further analyze performance when some late arrivals are acceptable. Analysis shows that the large tradeoffs exist between network parameters, such as QoI requirements, topology, and network size. Simulation results also provide evidence that the developed framework can estimate network limits and delays with high accuracy. Finally, this paper also introduces scalably feasible QoI regions, which provide upper bounds on QoI requirements that can be supported for certain network applications.

We consider the network-wide broadcast problem in multihop wireless networks with reliable multicast at the Medium Access Control (MAC) layer, where the cost of transmitting to downstream nodes at each branch point in the broadcast tree depends on the number$k$of recipients, specifically$1+A k^b$in our model (for some$b \geq 0$,$A \geq 0$). This allows us to capture a wide array of MAC-layer approaches and their costs, simply by varying the value of$b$(relative to$A$), in a problem formulation subsuming the Connected Dominating Set and Spanning Tree problems. We give a systematic analysis of this problem, including positive and negative results. In particular, we show the problem is: approximable by a factor varying from$2H_{\Delta}+2$down to 2 as$b$varies from 0 to 1 (where$\Delta$is the maximum degree of the network graph and$H_\Delta$is the$\Delta$th harmonic number); approximable by a factor varying from 2 to 1 (i.e., optimal) as$b$varies from 1 to$\log _2 (\frac{1}{A}+2)$; and optimally solvable thereafter. Finally, we present numerical results comparing the two algorithms above with other natural heuristics. We find there is an advantage in algorithms taking into consideration the value$b$, even if$b$can only be roughly estimated.

User information sharing is an important behavior in online social networks. Understanding such behavior could help in various applications such as user modeling, information cascade analysis, viral marketing, etc. In this paper, we aim to understand the strategies users employ to make retweet decision. We are interested in investigating whether these strategies in online social network contain significant information about users and can be used to further characterize users. We propose a flexible model that captures a number of behavior signals affecting user's retweet decision. Our empirical results show that the inferred strategies can help increase the performance of retweet prediction.

Self-driving cars typically rely on a set of radars for mapping the environment to avoid obstacles and operate safely. Currently, the radar parameters are uncoordinated and can interfere with each other. This results in inefficient use of the spectrum and, more importantly, in dangerous blinding of the radars especially in dense urban settings, posing a barrier to widespread deployment of self-driving cars. We present RadarMAC - the first system architecture and dynamic radar parameter assignment algorithms for radar interference mitigation in self-driving cars. We characterize the degrees of freedom for vehicular radar parameters, and model the channel parameter assignment problem as one of dynamically coloring the corresponding time-varying interference graph. RadarMAC guarantees interference-free radar operations within a defined capacity region. Using extensive simulations, we demonstrate that RadarMAC significantly outperforms the state-of-the-art random assignment scheme commonly used today with off-the-shelf radars in terms of safety and spectrum efficiency metrics in both dense and sparse settings. Finally, we identify a set of research challenges in medium access control for vehicular radars.

Quality of Information (QoI) provides a context-dependent measure of the utility that a network delivers to its users by incorporating non-traditional information attributes. Quickly and easily predicting performance and limitations of a network using QoI metrics is a valuable tool for network design. Even more useful is an understanding of how network components like topology, bandwidth, protocols, etc. impact these limitations. In this paper, we develop a QoI-based framework that can provide this understanding of limitations and impact by modeling the various contributors to delay in the network, including channel rate and contention, competing traffic flows, and multi-hop propagation effects, and relating them to QoI requirements, especially completeness and timeliness. Analysis shows that large tradeoffs exist between network parameters, such as QoI requirements, topology, and network size. Simulation results also provide evidence that the developed framework can estimate network limits with high accuracy. Finally, this work also introduces scalably feasible QoI regions, which provide upper bounds on QoI requirements that can be supported for certain network applications.

A hypergraph is a set V of vertices and a set of nonempty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph. We analyze the time complexity of the proposed algorithms and perform simulation experiments for random geometric hypergraphs, energy efficient routing in multichannel multiradio networks, and the Enron email data set. The experiment with the Enron email data set illustrates the application of the proposed algorithms in social networks for identifying the most important actor and the latent social relationship based on the closeness centrality metric.

In many deployments of wireless sensor networks (WSNs), the primary goal is to collect and deliver data from many nodes to a data sink. This goal must be met while considering limited resources, such as battery life, in the wireless nodes. In this work, we propose considering the content of generated data to make intelligent data and node selection decisions. We formally present the problem of maximizing coverage of this collected data while restricting individual node costs to remain within a given budget and provide an algorithm that provides the optimal solution. Next we consider the related problem of finding the optimal long-term average coverage subject to average cost constraints and give its solution, which uses Lyapunov Optimization techniques. For real world implementations, we also provide computationally feasible approximation algorithms of both problems along with proven bounds on their performance, including a novel technique that uses virtual queues for the average maximum coverage problem. Finally, we provide simulation results of all proposed algorithms. These results not only demonstrate the benefits of considering data content in scheduling, but also show the advantages from using the long-term average solution and the near-optimal performance of our greedy virtual queue approximation algorithm.

Team science is a collaborative approach to research, typically with researchers drawn from different disciplines. Team science networks have certain unique characteristics in their conception and intent that set them apart from other commonly studied social and collaboration networks. We study the structural properties, and present metrics for collaborative performance assessment in two real-world team science networks initiated by the Army Research Lab. We model a team using a higher-order generalization of an edge called a simplex. A simplex captures group relationships distinct from the union of pairwise relationships. Our evaluation using a rigorous methodology reveals that the distributions of vertex and facet degrees (the number of maximal groups that a vertex belongs to) follow a power law, but with exponential cut-off at the tail in most cases. We propose metrics for quantitatively assessing the extent of intra-team and extra-team collaborations, and compare their effectiveness vis-a-vis our intuitive notions. Our work can be used as the basis for generative models, and for evaluating the collaborative performance of team science networks.

We investigate optimal channel assignment algorithms that maximize per node throughput in dense multi-channel multi-radio (MC-MR) wireless networks. Specifically, we consider an MC-MR network where all nodes are within the transmission range of each other. This situation is encountered in many real-life settings such as students in a lecture hall, delegates attending a conference, or soldiers in a battlefield. In this scenario, we show that intelligent assignment of the available channels results in a significantly higher per node throughput. We first propose a class of channel assignment algorithms, parameterized by T (the number of transceivers per node), that can achieve Θ(1/N1/T) per node throughput using Θ(TN1-1/T) channels. In view of practical constraints on T, we then propose another algorithm that can achieve Θ((1/log2n)2) per node throughput using only two transceivers per node. Finally, we identify a fundamental relationship between the achievable per node throughput, the total number of channels used, and the network size under any strategy. Using analysis and simulations, we show that our algorithms achieve close to optimal performance at different operating points on this curve. Our work has several interesting implications on the optimal network design for dense MC-MR wireless networks.

We model the problem of channel assignment in mobile networks as one of temporal coloring (T-coloring), that is, coloring a time-varying graph. In order to capture the impact of channel re-assignments due to mobility, we model the cost of coloring as C + αA, where C is the total number of colors used and A is the total number of color changes, and α is a user-selectable parameter reflecting the relative penalty of channel usage and re-assignments.

Our editorial board continues to perform outstanding service to the mobile computing community, and for this we are very grateful. The board has evolved this year, and we take this opportunity to welcome several new Associate Editors: Prithwish Basu, Carla Fabiana-Chiasserini, Ahmed Helmy, Vana Kalogeraki, Richard J. La, Xiang-Yang Li, Cecilia Mascolo, Tommaso Melodia, Guevara Noubir, Andrea Richa, Lakshminarayanan Subramanian, Karthikeyan Sundaresan, Xinbing Wang, Edmund Yeh, Yanyong Zhang, and Lin Zhong. Biographies are provided. They collectively strengthen our expertise in disruption-tolerant networking, vehicular networks, mobile computing systems, wireless security, mobile social networks, wireless network optimization, game theory, cognitive radios, and information theory. We are excited to have them on board and thank them for agreeing to serve. Finally, we'd also like to acknowledge several Associate Editors whose terms recently expired: Tajana Simunic-Rosing, Sajal Das, Paolo Santi, Terry Todd, Wade Trappe, Nalini Venkatasubramanian, Mary Ann Ingram, Ekram Hossain, Chiara Petrioli, Alex Snoeren, Prasant Mohapatra, and Yunhao Liu. This very distinguished group of researchers has contributed greatly to increasing the journal's quality and reputation, and they will be missed! We wish them the best in their future endeavors.

Two constituencies form the backbone of a journal and act as stewards of its quality. One is the Editorial Board, whose judgments on the quality of manuscripts shape a journal signifi cantly and set the tone for its direction. Equally important, but perhaps not as externally visible, is the body of external reviewers who are called upon to review manuscripts. The IEEE Transactions on Mobile Computing (TMC) is very fortunate to have more than 1,200 dedicated reviewers whose service to the journal is one of the major factors that contributes to TMC's standing as an academic publication. These reviewers collectively completed nearly 1,800 reviews in 2012 alone, and their thoroughness in reviewing manuscripts has been exemplary. The IEEE has recently initiated a Reviewer Appreciation Program for its publications to highlight reviewers who have gone beyond the call of duty, both in contributing signifi cant amounts of their time to reviewing manuscripts for TMC and also in the quality of their reviews. It is our great pleasure to recognize the individuals listed as distinguished reviewers for TMC for the year 2012.

O N behalf of our Associate Editors, the TMC Steering Committee, and the TMC

TDMA MAC protocols suffer from two draw-backs that have reduced its practical appeal, especially for infrastructure-less wireless networks: the need for time synchronization, and the use of Jrames. While there has been extensive research towards achieving the required time synchronization, the frames are assumed to be inherent in TDMA. In this paper we present a framework for frameless TDMA based on a new concept we refer to as a slot chain. A slot chain is a series of slots with a starting slot and inter-slot period that is chosen to match a given capacity request. The key challenge in using slot chains instead of frames is ensuring that slot chains representing arbitrary capacity requests are conflict free. We present an algorithm for interleaving slot chains in a conflict-free manner. The algorithm is optimal for a class of requests called geometric and is z-approximate for general requests, where z can be made arbitrarily small. We show that any TDMA MAC protocol can readily replace using frames with using slot chains. Our simulation analysis shows that using slot chains results in much better capacity utilization when traffic is heterogeneous - as much as 100% in some cases.

We consider the broadcasting problem in multi-radio multi-channel ad hoc networks. The objective is to minimize the total broadcast cost, where the cost can be of any form that is summable over all the transmissions (e.g., the transmission and reception energy, the price for accessing a specific channel). Our technical approach is based on a simplicial complex model that allows us to capture the broadcast nature of the wireless medium and the heterogeneity across radios and channels. Specifically, we show that broadcasting in multi-radio multi-channel ad hoc networks can be formulated as a minimum spanning problem in simplicial complexes. We establish the NP-completeness of the minimum spanning problem and propose two approximation algorithms with order-optimal performance guarantee. These two algorithms offer tradeoffs between performance and time complexity. In a broader context, this work appears to be the first that studies the minimum spanning problem in simplicial complexes and weighted minimum connected set cover problem.

We investigate the possibility of using directional antennas for medium access control in wireless ad hoc networks. Previous research in ad hoc networks typically assumes the use of omnidirectional antennas at all nodes. With omnidirectional antennas, while two nodes are communicating using a given channel, MAC protocols such as IEEE 802.11 require all other nodes in the vicinity to remain silent. With directional antennas, two pairs of nodes located in each other's vicinity may potentially communicate simultaneously, increasing spatial reuse of the wireless channel. Range extension due to higher gain of directional antennas can also be useful in discovering fewer hop routes. However, new problems arise when using directional beams that simple modifications to 802.11 may not be able to mitigate. This paper identifies these problems and evaluates the tradeoffs associated with them. We also design a directional MAC protocol (MMAC) that uses multihop RTSs to establish links between distant nodes and then transmits CTS, DATA, and ACK over a single hop. While MMAC does not address all the problems identified with directional communication, it is an attempt to exploit the primary benefits of beamforming in the presence of some of these problems. Results show that MMAC can perform better than IEEE 802.11, although we find that the performance is dependent on the topology and flow patterns in the system.

Despite decades of research and development, mobile ad hoc networks (MANETs) continue to lag behind wireline networks in terms of latency, capacity and robustness. We contend that a key reason for this is the way MANETs are thought about and architected today. We propose a radically new architecture that we believe will elevate MANETs to a performance plane on par with wireline networks. Our design concept for next generation MANETs is based on several revolutionary ideas - 1) a relay-oriented physical layer that selectively switches incoming packets on-the-fly without the intervention of the MAC or network layers, 2) a path-centric medium access mechanism that acquires the floor for not just the next, but several hops toward the destination, 3) cooperative transport of packets in stages using diversity combining. Our vision is to enable emerging and future very-low-latency, very-high-bandwidth applications to work seamlessly over large MANETs. Realizing our vision requires solving a number of challenging problems. We enumerate and briefly discuss these exciting new research areas.

Directional antennas offer tremendous potential for improving the performance of ad hoc networks. Harnessing this potential, however, requires new mechanisms at the medium access and network layers for intelligently and adaptively exploiting the antenna system. While recent years have seen a surge of research into such mechanisms, the problem of developing a complete ad hoc networking system, including the unique challenge of real-life prototype development and experimentation has not been addressed. In this paper, we present utilizing directional antennas for ad hoc networking (UDAAN). UDAAN is an interacting suite of modular network- and medium access control (MAC)-layer mechanisms for adaptive control of steered or switched antenna systems in an ad hoc network. UDAAN consists of several new mechanisms-a directional power-controlled MAC, neighbor discovery with beamforming, link characterization for directional antennas, proactive routing and forwarding-all working cohesively to provide the first complete systems solution. We also describe the development of a real-life ad hoc network testbed using UDAAN with switched directional antennas, and we discuss the lessons learned during field trials. High fidelity simulation results, using the same networking code as in the prototype, are also presented both for a specific scenario and using random mobility models. For the range of parameters studied, our results show that UDAAN can produce a very significant improvement in throughput over omnidirectional communications.

In this paper, we present UDAAN ("utilizing directional antennas for ad hoc networking"), which is an interacting suite of modular network- and MAC-layer mechanisms for adaptive control of steered or switched antenna systems in an ad hoc network. UDAAN consists of several new mechanisms - a directional power-controlled MAC, neighbor discovery with beamforming, link characterization with directional antennas, proactive routing and forwarding all working cohesively to provide the first complete systems solution. We describe the development of a real-life ad hoc network testbed using UDAAN with switched directional antennas, and we discuss the lessons learned during field trials. High fidelity simulation results, using the same networking code as in the prototype, are also presented. For the range of parameters studied, our results show that UDAAN can produce up to a factor-of-10 improvement in throughput over omni-directional communications.

A novel framework is presented for the study of scalability in ad hoc networks. Using this framework, the first asymptotic analysis is provided with respect to network size, mobility, and traffic for each fundamental class of ad hoc routing algorithms. Protocols studied include the following: plain flooding (PF), standard link state (SLS), dynamic source routing (DSR), hierarchical link state (HierLS), zone routing protocol (ZRP), and hazy sighted link state (HSLS). It is shown that PF and ZRP scale better with mobility, SIJS and ZRP scale better with respect to traffic, and HSLS scales better with respect to network size. The analysis provides deeper understanding of the limits and trade-offs inherent in mobile ad hoc network routing. Our analysis is complemented with a simulation experiment comparing HSLS and HierLS. An important contribution of this paper is that HSLS is an scalable, easy-to-implement, alternative to hierarchical approaches for large ad hoc networks.

Previous research in wireless ad hoc networks typically assumes the use of omnidirectional antennas at all nodes. With omnidirectional antennas, while two nodes are communicating using a given channel, MAC protocols such as IEEE 802.11 require all other nodes in the vicinity to stay silent. With directional antennas, two pairs of nodes located in each other's vicinity may potentially communicate simultaneously, depending on the directions of transmission. This can increase spatial reuse of the wireless channel. In addition, the higher gain of directional antennas allows a node to communicate with other nodes located far away, implying that messages could be delivered to the destination in fewer hops. In this paper, we propose a MAC protocol that exploits the characteristics of directional antennas. Our design focuses on using multi-hop RTSs to establish links between distant nodes, and then transmit CTS, DATA and ACK over a single hop. Results show that our directional MAC protocol can perform better than IEEE 802.11, although we find that the performance is dependent on the topology configuration and the flow patterns in the system.

Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called textbf monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be bf NP -complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.

Beamforming antennas have the potential to provide a fundamental breakthrough in ad hoc network capacity. We present a broad-based examination of this potential, focusing on exploiting the longer ranges as well as the reduced interference that beamforming antennas can provide. We consider a number of enhancements to a convectional ad hoc network system, and evaluation the impact of each enhancement using simulation. Such enhancements include "aggressive" and "conservative" channel access models for beamforming antennas, link power control, and directional neighbor discovery. Our simulations are based on detailed modeling on detailed modeling of steered as well as swiched beams using antenna patterns of varying gains, and a realistic radio and propagation model. For the scenarios studied, our results show that beamforming can yield a 28% to 118% (depending upon the density) improvement in throughput, and up to a factor-of-28 reduction in delay. Our study also tells us which mechanisms are likely to be more effective and under what conditions, which in turn identifies areas where future research is neede

In this paper, we introduce a class of approaches that attempt to scale link-state routing by limiting the scope of link state update dissemination in space and over time. We present the first fundamental analysis of this generic class, which we call "Fuzzy Sighted Link State routing". Using a novel perspective on the "overhead"of a protocol that includes not only the overhead due to control messages but also due to route sub-optimality, we formulate an analytical model whose solution automatically leads to the best algorithm in this class. This algorithm is shown to have nearly the best possible asymptotic overhead for any routing algorithm -proactive or reactive. Simulation results are presented that compare the performance or several algorithms in this class

We consider the problem of adjusting the transmit powers of nodes in a multihop wireless network (also called an ad hoc network) to create a desired topology. We formulate it as a constrained optimization problem with two constraints-connectivity and biconnectivity, and one optimization objective-maximum power used. We present two centralized algorithms for use in static networks, and prove their optimality. For mobile networks, we present two distributed heuristics that adaptively adjust node transmit powers in response to topological changes and attempt to maintain a connected topology using minimum power. We analyze the throughput, delay, and power consumption of our algorithms using a prototype software implementation, an emulation of a power-controllable radio, and a detailed channel model. Our results show that the performance of multihop wireless networks in practice can be substantially increased with topology control.

We describe the construction of, and our experimental experience with, an ad hoc wireless testbed developed as part of the DARPA Global Mobile Information Systems (GloMo) sponsored MMWN and DAWN projects. The goal of the MMWN/DAWN system is the network-layer support for real-time QoS in large, dense, mobile ad hoc networks. The testbed consists of MMWN/DAWN switches-a single box with an embedded processor, and a commercial radio transceiver, and endpoints-laptops running voice and data applications. We have conducted a number of real-life experiments with this testbed, and report on our experiences and results.

As networks grow in scale and heterogeneity, hierarchical organization is inevitable. We present the case for optimal self-organization of network hierarchies. We provide a graph partitioning formulation relevant to networking but different from extant graph partitioning literature. In particular, we require that the resultant partitions be connected, a constraint that changes the character of the problem significantly. We devise a solution that consists of distinct phases for initial partitioning, refinement and post-processing, propose efficient heuristics for each phase, and evaluate them extensively on internetwork-like graphs through simulation. The results suggest that vertex trading techniques, in vogue for a number of decades in graph partitioning, are highly applicable, but multilevel techniques favored by conventional graph partitioning research may be of limited value for internetwork-like graphs. This solution can be implemented in practical networks to automatically generate Internet OSPF areas or ATM PNNI clusters.

Channel assignment problems in the time, frequency and code domains have thus far been studied separately. Exploiting the similarity of "constraints" that characterize assignments within and across these domains, we introduce the first unified framework for the study of assignment problems. Our framework identifies eleven atomic constraints underlying most current and potential assignment problems, and characterizes a problem as a combination of these constraints. Based on this framework, we present a unified algorithm for efficient (T/F/C)DMA channel assignments to nodes or to inter-nodal links in a (multihop) wireless network. The algorithm is parametrized to allow for tradeoff-selectable use as three different variants called random (RAND) ordering, minimum neighbors first (MNF), and progressive minimum neighbors first (PMNF). Using theoretical analysis, we show that the worst-case performance guarantee of PMNF is an order of magnitude better than that of the traditional RAND and MNF for most networks. We also experimentally study the relative performance for one node and one link assignment problem. We observe that PMNF performs the best, and that a larger fraction of unidirectional links degrades the performance in general.

We formulate the problem of multicast tree generation in asymmetric networks as one of computing a directed Steiner tree of minimal cost. We present a new polynomial-time algorithm that provides for trade-off selection, using a single parameter /spl kappa/, between the tree-cost (Steiner cost) and the runtime efficiency. Using theoretical analysis, we (1) show that it is highly unlikely that there exists a polynomial-time algorithm with a performance guarantee of constant times optimum cost, (2) introduce metrics for measuring the asymmetry of graphs, and (3) show that the worst-case cost of the tree produced by our algorithm is bounded in proportion to the graph asymmetry for two of the metrics. For a class of graphs whose asymmetry is upper bounded by a constant, this gives constant times optimum performance guarantee and is significant in light of (1). We also show that three well-known algorithms for (undirected) Steiner trees are but particular cases of our algorithm. Our experimental study shows that operating at a low /spl kappa/ gives nearly best possible average tree cost while maintaining acceptable runtime efficiency.

We formulate the problem of multicast tree generation as one of computing a directed Steiner tree of minimal cost. In this context, we present a polynomial-time algorithm that provides for trade-off selection, using a single parameter /spl kappa/, between the tree-cost (Steiner cost) and the run time efficiency. Further, the same algorithm may be used for delay optimization or tree-cost minimization simply by configuring the value of /spl kappa/ appropriately. We present theoretical and experimental analysis characterizing the problem and the performance of our algorithm. Theoretically, we show that it is highly unlikely that there exists a polynomial-time algorithm with a performance guarantee of constant times optimum cost, introduce metrics for measuring the asymmetry of graphs, and show that the worst-case cost of the tree produced by our algorithm is, at most, twice the optimum cost times the asymmetry, for two of these asymmetry metrics. For graphs with bounded asymmetry, this gives constant times optimum performance guarantee. We also show that three well-known algorithms for (undirected) Steiner trees are but particular cases of our algorithm. Our experimental study shows that operating at a low /spl kappa/ gives nearly best possible expected tree cost while maintaining acceptable run-time efficiency.