OpenRaiser/Intern-Atlas huggingface dataset:
Analytical Study of Adversarial Strategies in Cluster-based Overlays
Venue: arXiv cs.GT 2009
Year: 2009

Scheideler has shown that peer-to-peer overlays networks can only survive Byzantine attacks if malicious nodes are not able to predict what is going to be the topology of the network for a given sequence of join and leave operations. In this paper we investigate adversarial strategies by following specific games. Our analysis demonstrates first that an adversary can very quickly subvert DHT-based overlays by simply never triggering leave operations. We then show that when all nodes (honest and malicious ones) are imposed on a limited lifetime, the system eventually reaches a stationary regime where the ratio of polluted clusters is bounded, independently from the initial amount of corruption in the system.
Scheduling Heterogeneous Real-Time Traffic over Fading Wireless Channels
Venue: arXiv cs.NI 2009
Year: 2009

We develop a general approach for designing scheduling policies for real-time traffic over wireless channels. We extend prior work, which characterizes a real-time flow by its traffic pattern, delay bound, timely-throughput requirement, and channel reliability, to allow time-varying channels, allow clients to have different deadlines, and allow for the optional employment of rate adaptation. Thus, our model allow the treatment of more realistic fading channels as well as scenarios with mobile nodes, and the usage of more general transmission strategies. We derive a sufficient condition for a scheduling policy to be feasibility optimal, and thereby establish a class of feasibility optimal policies. We demonstrate the utility of the identified class by deriving a feasibility optimal policy for the scenario with rate adaptation, time-varying channels, and heterogeneous delay bounds. When rate adaptation is not available, we also derive a feasibility optimal policy for time-varying channels. For the scenario where rate adaptation is not available but clients have different delay bounds, we describe a heuristic. Simulation results are also presented which indicate the usefulness of the scheduling policies for more realistic and complex scenarios.
Outage Capacity of Incremental Relaying at Low Signal-to-Noise Ratios
Venue: arXiv cs.IT 2009
Year: 2009

We present the ε-outage capacity of incremental relaying at low signal-to-noise ratios (SNR) in a wireless cooperative network with slow Rayleigh fading channels. The relay performs decode-and-forward and repetition coding is employed in the network, which is optimal in the low SNR regime. We derive an expression on the optimal relay location that maximizes the ε-outage capacity. It is shown that this location is independent of the outage probability and SNR but only depends on the channel conditions represented by a path-loss factor. We compare our results to the ε-outage capacity of the cut-set bound and demonstrate that the ratio between the ε-outage capacity of incremental relaying and the cut-set bound lies within 1/\sqrt{2} and 1. Furthermore, we derive lower bounds on the ε-outage capacity for the case of K relays.
Deterministic Formulization of SNR for Wireless Multiuser DS-CDMA Networks
Venue: arXiv cs.NI 2009
Year: 2009

Wireless Multiuser receivers suffer from their relatively higher computational complexity that prevents widespread use of this technique. In addition, one of the main characteristics of multi-channel communications that can severely degrade the performance is the inconsistent and low values of SNR that result in high BER and poor channel capacity. It has been shown that the computational complexity of a multiuser receiver can be reduced by using the transformation matrix (TM) algorithm [4]. In this paper, we provide quantification of SNR based on the computational complexity of TM algorithm. We show that the reduction of complexity results high and consistent values of SNR that can consequently be used to achieve a desirable BER performance. In addition, our simulation results suggest that the high and consistent values of SNR can be achieved for a desirable BER performance. The performance measure adopted in this paper is the consistent values of SNR.
Recent Applications of Optical Parametric Amplifiers in Hybrid WDM TDM Local Area Optical Networks
Venue: arXiv cs.NI 2009
Year: 2009

In the present paper, the recent applications of optical parametric amplifiers (OPAs) in hybrid wavelength division multiplexing (WDM)/time division multiplexing (TDM) local area passive optical networks have been modeled and parametrically investigated over wide range of the affecting parameters. Moreover, we have analyzed the ability of the hybrid WDM/TDM Passive optical networks to handle a triple play solution, offering voice, video, and data services to the multiple users. Finally, we have investigated the maximum time division multiplexing (MTDM) bit rates for optical network units (ONUs) for maximum number of supported users with optical parametric amplifier technique across the single mode fiber (SMF) or highly nonlinear fiber (HNLF) cables to achieve both maximum network reach and quality of service (QOS).
Joint Source-Channel Coding over a Fading Multiple Access Channel with Partial Channel State Information
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we address the problem of transmission of correlated sources over a fast fading multiple access channel (MAC) with partial channel state information available at both the encoders and the decoder. We provide sufficient conditions for transmission with given distortions. Next these conditions are specialized to a Gaussian MAC (GMAC). We provide the optimal power allocation strategy and compare the strategy with various levels of channel state information. Keywords: Fading MAC, Power allocation, Partial channel state information, Correlated sources.
Generalized Analysis of a Distributed Energy Efficient Algorithm for Change Detection
Venue: arXiv cs.IT 2009
Year: 2009

An energy efficient distributed Change Detection scheme based on Page's CUSUM algorithm was presented in \cite{icassp}. In this paper we consider a nonparametric version of this algorithm. In the algorithm in \cite{icassp}, each sensor runs CUSUM and transmits only when the CUSUM is above some threshold. The transmissions from the sensors are fused at the physical layer. The channel is modeled as a Multiple Access Channel (MAC) corrupted with noise. The fusion center performs another CUSUM to detect the change. In this paper, we generalize the algorithm to also include nonparametric CUSUM and provide a unified analysis.
Distance priority based multicast routing in WDM networks considering sparse light splitting
Venue: arXiv cs.NI 2009
Year: 2009

As we know, the member-only algorithm in provides the best links stress and wavelength usage for the construction of multicast light-trees in WDM networks with sparse splitting. However, the diameter of tree is too big and the average delay is also too large, which are intolerant for QoS required multimedia applications. In this paper, a distance priority based algorithm is proposed to build light-trees for multicast routing, where the Candidate Destinations and the Candidate Connectors are introduced. Simulations show the proposed algorithm is able to greatly reduce the diameter and average delay of the multicast tree (up to 51% and 50% respectively), while keep the same or get a slightly better link stress as well as the wavelength usage than the famous Member-Only algorithm.
Contraction of Timetable Networks with Realistic Transfers
Venue: arXiv cs.DS 2009
Year: 2009

We successfully contract timetable networks with realistic transfer times. Contraction gradually removes nodes from the graph and adds shortcuts to preserve shortest paths. This reduces query times to 1 ms with preprocessing times around 6 minutes on all tested instances. We achieve this by an improved contraction algorithm and by using a station graph model. Every node in our graph has a one-to-one correspondence to a station and every edge has an assigned collection of connections. Our graph model does not need parallel edges. The query algorithm does not compute a single earliest arrival time at a station but a set of arriving connections that allow best transfer opportunities.
Interfacing network coding with TCP: an implementation
Venue: arXiv cs.NI 2009
Year: 2009

In previous work (`Network coding meets TCP') we proposed a new protocol that interfaces network coding with TCP by means of a coding layer between TCP and IP. Unlike the usual batch-based coding schemes, the protocol uses a TCP-compatible sliding window code in combination with new rules for acknowledging bytes to TCP that take into account the network coding operations in the lower layer. The protocol was presented in a theoretical framework and considered only in conjunction with TCP Vegas. In this paper we present a real-world implementation of this protocol that addresses several important practical aspects of incorporating network coding and decoding with TCP's window management mechanism. Further, we work with the more widespread and practical TCP Reno. Our implementation significantly advances the goal of designing a deployable, general, TCP-compatible protocol that provides the benefits of network coding.
On P vs. NP, Geometric Complexity Theory, and the Riemann Hypothesis
Venue: arXiv cs.CC 2009
Year: 2009

Geometric complexity theory (GCT) is an approach to the $P$ vs. $NP$ and related problems. A high level overview of this research plan and the results obtained so far was presented in a series of three lectures in the Institute of Advanced study, Princeton, Feb 9-11, 2009. This article contains the material covered in those lectures after some revision, and gives a mathematical overview of GCT. No background in algebraic geometry, representation theory or quantum groups is assumed.
View-based Propagator Derivation
Venue: arXiv cs.AI 2009
Year: 2009

When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear constraints both with unit and non-unit coefficients? Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance than resorting to constraint decomposition. This paper shows how to use views to derive perfect propagator variants. A model for views and derived propagators is introduced. Derived propagators are proved to be indeed perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators such as transformation, generalization, specialization, and type conversion are developed. The paper introduces an implementation architecture for views that is independent of the underlying constraint programming system. A detailed evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Without views, Gecode would either require 180 000 rather than 40 000 lines of propagator code, or would lack many efficient propagator variants. Compared to 8 000 lines of code for views, the reduction in code for propagators yields a 1750% return on investment.
Multiuser Modulation Classification Based on Cumulants in AWGN Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper the negative impacts of interference transmitters on automatic modulation classification (AMC) have been discussed. We proposed two approaches for AMC in the presence of interference: single user modulation classification (SUMC) and multiuser modulation classification (MUMC). When the received power of one transmitter is larger than the other transmitters, SUMC approach recognizes the modulation type of that transmitter and other transmitters are treated as interferences. Alternatively when the received powers of all transmitters are close to each other we propose MUMC method to recognize the modulation type of all of the transmitted signals. The features being used to recognize the modulation types of transmitters for both approaches, SUMC and MUMC are higher order cumulants. The super-position property of cumulants for independent random variables is utilized for SUMC and MUMC. We investigated the robustness of our classifier with respect to different powers of the received signals via analytical and simulation results and we have shown the analytical results will be confirmed by simulations. Also we studied the effect of signal synchroni-zation error via simulation results in the both condition for MUMC and SUMC.
Real Interference Alignment: Exploiting the Potential of Single Antenna Systems
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, the available spatial Degrees-Of-Freedoms (DOF) in single antenna systems is exploited. A new coding scheme is proposed in which several data streams having fractional multiplexing gains are sent by transmitters and interfering streams are aligned at receivers. Viewed as a field over rational numbers, a received signal has infinite fractional DOFs, allowing simultaneous interference alignment of any finite number of signals at any finite number of receivers. The coding scheme is backed up by a recent result in the field of Diophantine approximation, which states that the convergence part of the Khintchine-Groshev theorem holds for points on non-degenerate manifolds. The proposed coding scheme is proved to be optimal for three communication channels, namely the Gaussian Interference Channel (GIC), the uplink channel in cellular systems, and the $X$ channel. It is proved that the total DOF of the $K$-user GIC is $\frac{K}{2}$ almost surely, i.e. each user enjoys half of its maximum DOF. Having $K$ cells and $M$ users within each cell in a cellular system, the total DOF of the uplink channel is proved to be $\frac{KM}{M+1}$. Finally, the total DOF of the $X$ channel with $K$ transmitters and $M$ receivers is shown to be $\frac{KM}{K+M-1}$.
Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves
Venue: arXiv cs.CG 2009
Year: 2009

We consider the theoretical model of Crystalline robots, which have been introduced and prototyped by the robotics community. These robots consist of independently manipulable unit-square atoms that can extend/contract arms on each side and attach/detach from neighbors. These operations suffice to reconfigure between any two given (connected) shapes. The worst-case number of sequential moves required to transform one connected configuration to another is known to be Theta(n). However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only O(log n) parallel steps, although the total number of operations increases slightly to Theta(nlogn). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.
Stability and Distributed Power Control in MANETs with Outages and Retransmissions
Venue: arXiv cs.NI 2009
Year: 2009

In the current work the effects of hop-by-hop packet loss and retransmissions via ARQ protocols are investigated within a Mobile Ad-hoc NET-work (MANET). Errors occur due to outages and a success probability function is related to each link, which can be controlled by power and rate allocation. We first derive the expression for the network's capacity region, where the success function plays a critical role. Properties of the latter as well as the related maximum goodput function are presented and proved. A Network Utility Maximization problem (NUM) with stability constraints is further formulated which decomposes into (a) the input rate control problem and (b) the scheduling problem. Under certain assumptions problem (b) is relaxed to a weighted sum maximization problem with number of summants equal to the number of nodes. This further allows the formulation of a non-cooperative game where each node decides independently over its transmitting power through a chosen link. Use of supermodular game theory suggests a price based algorithm that converges to a power allocation satisfying the necessary optimality conditions of (b). Implementation issues are considered so that minimum information exchange between interfering nodes is required. Simulations illustrate that the suggested algorithm brings near optimal results.
Wild Card Queries for Searching Resources on the Web
Venue: arXiv cs.DB 2009
Year: 2009

We propose a domain-independent framework for searching and retrieving facts and relationships within natural language text sources. In this framework, an extraction task over a text collection is expressed as a query that combines text fragments with wild cards, and the query result is a set of facts in the form of unary, binary and general $n$-ary tuples. A significance of our querying mechanism is that, despite being both simple and declarative, it can be applied to a wide range of extraction tasks. A problem in querying natural language text though is that a user-specified query may not retrieve enough exact matches. Unlike term queries which can be relaxed by removing some of the terms (as is done in search engines), removing terms from a wild card query without ruining its meaning is more challenging. Also, any query expansion has the potential to introduce false positives. In this paper, we address the problem of query expansion, and also analyze a few ranking alternatives to score the results and to remove false positives. We conduct experiments and report an evaluation of the effectiveness of our querying and scoring functions.
Data structure for representing a graph: combination of linked list and hash table
Venue: arXiv cs.DS 2009
Year: 2009

In this article we discuss a data structure, which combines advantages of two different ways for representing graphs: adjacency matrix and collection of adjacency lists. This data structure can fast add and search edges (advantages of adjacency matrix), use linear amount of memory, let to obtain adjacency list for certain vertex (advantages of collection of adjacency lists). Basic knowledge of linked lists and hash tables is required to understand this article. The article contains examples of implementation on Java.
Overlapped Chunked Network Coding
Venue: arXiv cs.IT 2009
Year: 2009

Network coding is known to improve the throughput and the resilience to losses in most network scenarios. In a practical network scenario, however, the accurate modeling of the traffic is often too complex and/or infeasible. The goal is thus to design codes that perform close to the capacity of any network (with arbitrary traffic) efficiently. In this context, random linear network codes are known to be capacity-achieving while requiring a decoding complexity quadratic in the message length. Chunked Codes (CC) were proposed by Maymounkov et al. to improve the computational efficiency of random codes by partitioning the message into a number of non-overlapping chunks. CC can also be capacity-achieving but have a lower encoding/decoding complexity at the expense of slower convergence to the capacity. In this paper, we propose and analyze a generalized version of CC called Overlapped Chunked Codes (OCC) in which chunks are allowed to overlap. Our theoretical analysis and simulation results show that compared to CC, OCC can achieve the capacity with a faster speed while maintaining almost the same advantage in computational efficiency.
A Stable On-line Algorithm for Energy Efficient Multi-user Scheduling
Venue: arXiv cs.NI 2009
Year: 2009

In this paper, we consider the problem of energy efficient uplink scheduling with delay constraint for a multi-user wireless system. We address this problem within the framework of constrained Markov decision processes (CMDPs) wherein one seeks to minimize one cost (average power) subject to a hard constraint on another (average delay). We do not assume the arrival and channel statistics to be known. To handle state space explosion and informational constraints, we split the problem into individual CMDPs for the users, coupled through their Lagrange multipliers; and a user selection problem at the base station. To address the issue of unknown channel and arrival statistics, we propose a reinforcement learning algorithm. The users use this learning algorithm to determine the rate at which they wish to transmit in a slot and communicate this to the base station. The base station then schedules the user with the highest rate in a slot. We analyze convergence, stability and optimality properties of the algorithm. We also demonstrate the efficacy of the algorithm through simulations within IEEE 802.16 system.
On the Relationship between Trading Network and WWW Network: A Preferential Attachment Perspective
Venue: arXiv cs.IR 2009
Year: 2009

This paper describes the relationship between trading network and WWW network from preferential attachment mechanism perspective. This mechanism is known to be the underlying principle in the network evolution and has been incorporated to formulate two famous web pages ranking algorithms, PageRank and HITS. We point out the differences between trading network and WWW network in this mechanism, derive the formulation of HITS-based ranking algorithm for trading network as a direct consequence of the differences, and apply the same framework when deriving the formulation back to the HITS formulation that turns to become a technique to accelerate its convergences.
Predictability of Fixed-Job Priority Schedulers on Heterogeneous Multiprocessor Real-Time Systems
Venue: arXiv cs.OS 2009
Year: 2009

The multiprocessor Fixed-Job Priority (FJP) scheduling of real-time systems is studied. An important property for the schedulability analysis, the predictability (regardless to the execution times), is studied for heterogeneous multiprocessor platforms. Our main contribution is to show that any FJP schedulers are predictable on unrelated platforms. A convenient consequence is the fact that any FJP schedulers are predictable on uniform multiprocessors.
Level Crossing Rate and Average Fade Duration of the Multihop Rayleigh Fading Channel
Venue: arXiv cs.IT 2009
Year: 2009

We present a novel analytical framework for the evaluation of important second order statistical parameters, as the level crossing rate (LCR) and the average fade duration (AFD) of the amplify-and-forward multihop Rayleigh fading channel. More specifically, motivated by the fact that this channel is a cascaded one, which can be modelled as the product of N fading amplitudes, we derive novel analytical expressions for the average LCR and AFD of the product of N Rayleigh fading envelopes, or of the recently so-called N*Rayleigh channel. Furthermore, we derive simple and efficient closed-form approximations to the aforementioned parameters, using the multivariate Laplace approximation theorem. It is shown that our general results reduce to the specific dual-hop case, previously published. Numerical and computer simulation examples verify the accuracy of the presented mathematical analysis and show the tightness of the proposed approximations.
On Continuous Weighted Finite Automata
Venue: arXiv cs.FL 2009
Year: 2009

We investigate the continuity of the ω-functions and real functions defined by weighted finite automata (WFA). We concentrate on the case of average preserving WFA. We show that every continuous ω-function definable by some WFA can be defined by an average preserving WFA and then characterize minimal average preserving WFA whose ω-function or ω-function and real function are continuous. We obtain several algorithmic reductions for WFA-related decision problems. In particular, we show that deciding whether the ω-function and real function of an average preserving WFA are both continuous is computationally equivalent to deciding stability of a set of matrices. We also present a method for constructing WFA that compute continuous real functions.