Finding minimum node separators: A Markov chain Monte Carlo method

Lee, Joohyun,Kwak, Jaewook,Lee, Hyang-Won,Shroff, Ness B. Elsevier 2018 Reliability engineering & system safety Vol.178 No.-

<P><B>Abstract</B></P> <P>In networked systems such as communication networks or power grids, graph separation from node failures can damage the overall operation severely. One of the most important goals of network attackers is thus to separate nodes so that the sizes of connected components become small. In this work, we consider the problem of finding a minimum <I>α</I>-separator, that partitions the graph into connected components of sizes at most <I>αn</I>, where <I>n</I> is the number of nodes. To solve the <I>α</I>-separator problem, we develop a random walk algorithm based on Metropolis chain. We characterize the conditions for the first passage time (to find an optimal solution) of our algorithm. We also find an optimal cooling schedule, under which the random walk converges to an optimal solution almost surely. Furthermore, we generalize our algorithm to non-uniform node weights. We show through extensive simulations that the first passage time is less than <I>O</I>(<I>n</I> <SUP>3</SUP>), thereby validating our analysis. The solution found by our algorithm allows us to identify the weakest points in the network that need to be strengthened. Simulations in real topologies show that attacking a dense area is often not an efficient solution for partitioning a network into small components.</P>

Energy-Efficient Unified Routing Algorithm for Multi-Hop Wireless Networks

Sungoh Kwon,Shroff, Ness B. IEEE 2012 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS Vol.11 No.11

<P>In this paper, we develop an energy-efficient routing scheme that takes into account four key wireless system elements: transmission power; interference; residual energy; and energy replenishment. Since energy is a scarce resource, many energy-aware routing algorithms have been proposed to improve network performance. However, previous algorithms have been designed for a subset of these four main elements, which could limit their applicability. Thus, our contribution is here to develop a unified routing algorithm called the Energy-efficient Unified Routing (EURo) algorithm that accommodates any combination of these above key elements and adapts to varying wireless environments. We study the impact of key wireless elements on routing, and show via simulations that EURo outperforms the state-of-the-art.</P>

Local Greedy Approximation for Scheduling in Multihop Wireless Networks

Changhee Joo,Shroff, Ness B. IEEE 2012 IEEE TRANSACTIONS ON MOBILE COMPUTING Vol.11 No.3

<P>In recent years, there has been a significant amount of work done in developing low-complexity scheduling schemes to achieve high performance in multihop wireless networks. A centralized suboptimal scheduling policy, called Greedy Maximal Scheduling (GMS) is a good candidate because its empirically observed performance is close to optimal in a variety of network settings. However, its distributed realization requires high complexity, which becomes a major obstacle for practical implementation. In this paper, we develop simple distributed greedy algorithms for scheduling in multihop wireless networks. We reduce the complexity by relaxing the global ordering requirement of GMS, up to near zero. Simulation results show that the new algorithms approximate the performance of GMS, and outperform the state-of-the-art distributed scheduling policies.</P>

Towards Achieving the Maximum Capacity in Large Mobile Wireless Networks under Delay Constraints

Xiaojun Lin,Ness B. Shroff 한국통신학회 2004 Journal of communications and networks Vol.6 No.4

Opportunistic Scheduling: An Illustration of Cross Layer Design

Xin Liu,Ness B. Shroff,Edwin K. P. Chong 에스케이텔레콤 (주) 2004 Telecommunications Review Vol.14 No.6

Towards Achieving the Maximum Capacity in Large Mobile Wireless Networks under Delay Constraints

Lin, Xiaojun,Shroff, Ness B. The Korea Institute of Information and Commucation 2004 Journal of communications and networks Vol.6 No.4

In this paper, we study how to achieve the maximum capacity under delay constraints for large mobile wireless networks. We develop a systematic methodology for studying this problem in the asymptotic region when the number of nodes n in the network is large. We first identify a number of key parameters for a large class of scheduling schemes, and investigate the inherent tradeoffs among the capacity, the delay, and these scheduling parameters. Based on these inherent tradeoffs, we are able to compute the upper bound on the maximum per-node capacity of a large mobile wireless network under given delay constraints. Further, in the process of proving the upper bound, we are able to identify the optimal values of the key scheduling parameters. Knowing these optimal values, we can then develop scheduling schemes that achieve the upper bound up to some logarithmic factor, which suggests that our upper bound is fairly tight. We have applied this methodology to both the i.i.d. mobility model and the random way-point mobility model. In both cases, our methodology allows us to develop new scheduling schemes that can achieve larger capacity than previous proposals under the same delay constraints. In particular, for the i.i.d. mobility model, our scheme can achieve (n-1/3/log3/2 n) per-node capacity with constant delay. This demonstrates that, under the i.i.d. mobility model, mobility increases the capacity even with constant delays. Our methodology can also be extended to incorporate additional scheduling constraints.

Battle of Opinions Over Evolving Social Networks

Koprulu, Irem,Kim, Yoora,Shroff, Ness B. IEEE 2019 IEEE/ACM transactions on networking Vol.27 No.2

<P>Social networking environments provide major platforms for the discussion and formation of opinions in diverse areas, including, but not limited to, political discourse, market trends, news, and social movements. Often, these opinions are of a competing nature, e.g., radical vs. peaceful ideologies, correct information vs. misinformation, and one technology vs. another. We study the battles of such competing opinions over evolving social networks. The novelty of our model is that it captures the exposure and adoption dynamics of opinions that account for the preferential and random nature of exposure as well as the persuasion power and persistence of different opinions. We provide a complete characterization of the mean opinion dynamics over time as a function of the initial adoption, as well as the particular exposure, adoption, and persistence dynamics. Our analysis, supported by case studies, reveals the key metrics that govern the spread of opinions and establishes the means to engineer the desired impact of an opinion in the presence of other competing opinions.</P>

Analysis of Connectivity and Capacity in 1-D Vehicle-to-Vehicle Networks

Kwon, Sungoh,Kim, Yoora,Shroff, Ness B. IEEE 2016 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS Vol.15 No.12

<P>A vehicle-to-vehicle (V2V) network is one type of mobile ad hoc network. Due to mobility, the topology in a V2V network is time-varying, which complicates the analysis and evaluation of network performance. In this paper, we model the network as geometric elements of lines and points and analyze the connectivity and capacity of the network using geometric probability. Under the assumption that n vehicles randomly arrive with a Poisson distribution, our analysis shows that the spatial distribution of vehicles within a given distance D, is uniform and that the average number of vehicles to be fully connected is approximately (1/a)(log (1/a) + log log (1/a)) for a = R-T/D, where R-T is the maximum transmission range of a vehicle. When a random access scheme is adopted, only (1/2)(1 - e(-2)) n of links comprised of two adjacent nodes are simultaneously activated, on average, so the expected network capacity increases in a way linearly proportional to (1/2)(1 - e(-2)) as the number of vehicles increases. Through numerical studies and simulations, we verify the efficacy of our analytical results.</P>

Delay-Based Back-Pressure Scheduling in Multihop Wireless Networks

Bo Ji,Changhee Joo,Shroff, Ness B. IEEE 2013 IEEE/ACM transactions on networking Vol.21 No.5

<P>Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop.) In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric and show that the proposed scheme achieves optimal throughput performance. Furthermore, we conduct simulations to support our analytical results and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.</P>

On Stochastic Confidence of Information Spread in Opportunistic Networks

Kim, Yoora,Lee, Kyunghan,Shroff, Ness B. IEEE 2016 IEEE TRANSACTIONS ON MOBILE COMPUTING Vol.15 No.4

<P>Predicting spreading patterns of information or virus has been a popular research topic for which various mathematical tools have been developed. These tools have mainly focused on estimating the average time of spread to a fraction (e.g., alpha) of the agents, i.e., so-called average alpha-completion time E(T-alpha). We claim that understanding stochastic confidence on the time T-alpha rather than only its average gives more comprehensive knowledge on the spread behavior and wider engineering choices. Obviously, the knowledge also enables us to effectively accelerate or decelerate a spread. To demonstrate the benefits of understanding the distribution of spread time, we introduce a new metric G(alpha,beta) that denotes the time required to guarantee alpha completion (i.e., penetration) with probability beta. Also, we develop a new framework characterizing G(alpha,beta) for various spread parameters such as number of seeders, contact rates between agents, and heterogeneity in contact rates. We apply our technique to a large-scale experimental vehicular trace and show that it is possible to allocate resources for acceleration of spread in a far more elaborated way compared to conventional average-based mathematical tools.</P>