ABSTRACT This article proposes an implicit enumeration approach to solve the maximum ratio ‐plex and the maximum ratio ‐defective clique problems. The approach is inspired by the classical Bron‐Kerbosch algorithm for enumerating all maximal cliques in a graph, which is extended to enumerating structures that are hereditary on induced subgraphs. Such structures include ‐plexes and ‐defective cliques, among many others. The performance of the proposed approach is compared with that of the methods based on mixed integer linear programming (MILP), binary search, and Newton's iteration through numerical experiments on randomly generated and real‐life network instances.

Abstract This article introduces and studies two clique relaxation models with fractional objectives: the maximum ratio ‐plex problem and the maximum ratio ‐defective clique problem. The decision version of each problem is shown to be strongly ‐complete; we also discuss some related computational complexity issues. The base optimization models are single‐ratio fractional 0‐1 problems. We describe two general types of solution methods: the first one is based on mixed‐integer linear programs (MILPs) obtained by linearizing the original nonlinear 0‐1 models; the other one exploits parametric methods (namely, a binary search and Newton's method) that solve MILPs in an iterative manner. For the proposed MILPs, we derive valid inequalities that are shown to substantially improve the performance of an off‐the‐shelf MILP solver. Finally, the considered solution approaches are compared via extensive numerical experiments using a set of artificially generated and real‐life network instances.

In this paper, the problem of mining complex temporal patterns in the context of multivariate time series is considered. A new method called the Fast Temporal Pattern Mining with Extended Vertical Lists is introduced. The method is based on an extension of the level-wise property, which requires a more complex pattern to start at positions within a record where all of the subpatterns of the pattern start. The approach is built around a novel data structure called the Extended Vertical List that tracks positions of the first state of the pattern inside records and links them to appropriate positions of a specific subpattern of the pattern called the prefix. Extensive computational results indicate that the new method performs significantly faster than the previous version of the algorithm for Temporal Pattern Mining; however, the increase in speed comes at the expense of increased memory usage.

Consider a large wireless ad hoc network that facilitates communication between random pairs of network nodes. This paper investigates the size of routing tables as the number of nodes in the network increases. A routing protocol in a flat-label network is information-efficient if the amount of information at individual nodes required to route packets does not increase with the network size. It is shown that the shortest-path and straight-line routing algorithms are not information-efficient, i.e., these protocols can be implemented only when nodes' memory increases with the network size. On the other hand, it is established that there exists an information-efficient algorithm that routes packets correctly even if each node in the network is capable of storing information on a fixed number of destinations only.

The effectiveness of application-layer coding in a system with a large number of users is considered. The end users encode data packets before transmitting them. The effect of additional packets on the system performance is twofold: (i) additional packets increase offered load, which results in higher drop probability, and (ii) some of dropped packets can be recovered at the receivers after decoding. It is argued that the space of all systems can be partitioned into two regions where coding is beneficial and detrimental, respectively. In particular, the paper establishes an asymptotic regime that contains the boundary between these two regions. On the boundary, systems with and without coding have the same performance. Informally, our results indicate that application-layer coding improves the performance only in systems with low loss probabilities (without coding), and employing such coding in systems with high loss probabilities only degrades the performance.

The effectiveness of application-layer coding in a system with a large number of users is considered. The end users encode data packets before transmitting them. The effect of additional packets on the system performance is twofold: (i) additional packets increase the offered load, which results in higher drop probability, and (ii) some of dropped packets can be recovered at the receivers after decoding. The paper establishes an asymptotic regime in which systems with and without coding have the same performance. The space of all systems is partitioned into two regions where coding is beneficial and detrimental, respectively. Informally, it is argued that application-layer coding improves the performance only in systems with low loss probabilities (without coding), and employing such coding in systems with high loss probabilities only degrades the performance.

This paper investigates fundamental properties of throughput and energy cost in large wireless linear networks with very limited local resources that do not grow with the size of the network. The maximum throughput of the network is derived and the arrival process that maximizes throughput, given a fixed arrival rate, is established. An asymptotically critical loading regime is identified such that the probability of an arbitrary packet being lost is strictly within (0, 1) as the network size increases. Such a regime delivers throughput comparable to the maximum at a reasonable energy cost.

Consider a large wireless ad hoc network that facilitates communication between random pairs of network nodes. The paper investigates the size of routing tables as the number of nodes in the network increases. A routing protocol is information-efficient if the amount of information at individual nodes required to route packets does not increases with the network size. It is shown that the shortest-path and straight-line routing algorithms are not information-efficient, i.e., these protocols can be implemented only when nodes' memory increases with the network size. On the other hand, it is established that there exists an information-efficient routing algorithm -routing is feasible even if each node in the network is capable of storing information on a fixed number of destinations.

Abstract—This paper investigates the existence of scalable protocols that can achieve the capacity limit of per source-destination pair in a large wireless network of nodes when the buffer space of each node does not grow with the size of the network. It is shown that there is no end-to-end protocol capable of carrying out the limiting throughput of with nodes that have constant buffer space. In other words, this limit is achievable only with devices whose buffers grow with the size of the network. On the other hand, the paper establishes that there exists a protocol which realizes a slightly smaller throughput of log when devices have constant buffer space. Furthermore, it is shown that the required buffer space can be very small, capable of storing just a few packets. This is particularly important for wireless sensor networks where devices have limited resources. Finally, from a mathematical perspective, the paper furthers our understanding of the difficult problem of analyzing large queueing networks with finite buffers for which, in general, no explicit solutions are available. Index Terms—Ad hoc wireless networks, finite-buffer queueing networks, large-scale networks, local cooperation, scaling laws, wireless sensor networks. I.

We investigate the distribution of the waiting time V in an M/G/1 processor sharing queue with traffic intensity /spl rho/x] = P[B > (1 - /spl rho/)x](1 + o(1)) Furthermore, we demonstrate that the preceding relationship does not hold if the job distribution has a lighter tail than e/sup -/spl radic/x/. This result provides a new tool for analyzing network congestion points with moderately heavy-tailed characteristics, e.g. log normal distributions, that have been recently empirically discovered in Web traffic. The accuracy of our approximation is confirmed with simulation experiments.

Consider a network multiplexer with a finite buffer fed by a superposition of independent heterogeneous on-off sources. An on-off source consists of a sequence of alternating independent activity and silence periods. During its activity period a source produces fluid with constant rate. For this system, under the assumption that the residual activity periods are intermediately regularly varying, we derive explicit and asymptotically exact formulas for approximating the stationary overflow probability and loss rate. The derived asymptotic formulas, in addition to their analytical tractability, exhibit excellent quantitative accuracy, which is illustrated by a number of simulation experiments. We demonstrate through examples how these results can be used for efficient computation of capacity regions for network switching elements. Furthermore, the results provide important insight into qualitative tradeoffs between the overflow probability, offered traffic load, available capacity, and buffer space. Overall, they provide a new set of tools for designing and provisioning of networks with heavy-tailed traffic streams.