OpenRaiser/Intern-Atlas huggingface dataset:
The Effect of ISP Traffic Shaping on User-Perceived Performances in Broadband Shared Access Networks
Venue: arXiv cs.NI 2014
Year: 2014

Recent studies on the practice of shaping subscribers' traffic by ISPs give a new insight into the actual performance of broadband access networks at a packet level. Unlike metro and backbone networks, however, access networks directly interface with end-users, so it is important to base the study and design of access networks on the behaviors of and the actual performance perceived by end-users. In this paper we study the effect of ISP traffic shaping using traffic models based on user behaviors and application/session-layer metrics providing quantifiable measures of user-perceived performance for HTTP, FTP, and streaming video traffic. To compare the user-perceived performance of shaped traffic flows with those of unshaped ones in an integrated way, we use a multivariate non-inferiority testing procedure. We first investigate the effect of the token generation rate and the token bucket size of a token bucket filter on user-perceived performance at a subscriber level with a single subscriber. Then we investigate their effect at an access level where shaped traffic flows from multiple subscribers interact with one another in a common shared access network. The simulation results show that for a given token generation rate, a larger token bucket provides better user-perceived performance at both subscriber and access levels. It is also shown that the loose burst control resulting from the large token bucket --- up to 100 MB for access line rate of 100 Mbit/s --- does not negatively affect user-perceived performance with multiple subscribers even in the presence of non-conformant subscribers; with a much larger token bucket, however, the negative effect of non-conformant subscribers on the user-perceived performance of conformant subscribers becomes clearly visible because the impact of token bucket size and that of token generation rate are virtually indistinguishable in this case.
A Comparison of Hybridized and Standard DG Methods for Target-Based hp-Adaptive Simulation of Compressible Flow
Venue: arXiv cs.CE 2014
Year: 2014

We present a comparison between hybridized and non-hybridized discontinuous Galerkin methods in the context of target-based hp-adaptation for compressible flow problems. The aim is to provide a critical assessment of the computational efficiency of hybridized DG methods. Hybridization of finite element discretizations has the main advantage, that the resulting set of algebraic equations has globally coupled degrees of freedom only on the skeleton of the computational mesh. Consequently, solving for these degrees of freedom involves the solution of a potentially much smaller system. This not only reduces storage requirements, but also allows for a faster solution with iterative solvers. Using a discrete-adjoint approach, sensitivities with respect to output functionals are computed to drive the adaptation. From the error distribution given by the adjoint-based error estimator, h- or p-refinement is chosen based on the smoothness of the solution which can be quantified by properly-chosen smoothness indicators. Numerical results are shown for subsonic, transonic, and supersonic flow around the NACA0012 airfoil. hp-adaptation proves to be superior to pure h-adaptation if discontinuous or singular flow features are involved. In all cases, a higher polynomial degree turns out to be beneficial. We show that for polynomial degree of approximation p=2 and higher, and for a broad range of test cases, HDG performs better than DG in terms of runtime and memory requirements.
Payoff Performance of Fictitious Play
Venue: arXiv cs.GT 2014
Year: 2014

We investigate how well continuous-time fictitious play in two-player games performs in terms of average payoff, particularly compared to Nash equilibrium payoff. We show that in many games, fictitious play outperforms Nash equilibrium on average or even at all times, and moreover that any game is linearly equivalent to one in which this is the case. Conversely, we provide conditions under which Nash equilibrium payoff dominates fictitious play payoff. A key step in our analysis is to show that fictitious play dynamics asymptotically converges the set of coarse correlated equilibria (a fact which is implicit in the literature).
The Hospitals / Residents Problem with Couples: Complexity and Integer Programming Models
Venue: arXiv cs.DS 2014
Year: 2014

The Hospitals / Residents problem with Couples (HRC) is a generalisation of the classical Hospitals / Resident problem (HR) that is important in practical applications because it models the case where couples submit joint preference lists over pairs of (typically geographically close) hospitals. In this paper we give a new NP-completeness result for the problem of deciding whether a stable matching exists, in highly restricted instances of HRC. Further, we present an Integer Programming (IP) model for HRC and extend it the case where preference lists can include ties. Also, we describe an empirical study of an IP model or HRC and its extension to the case where preference lists can include ties. This model was applied to randomly generated instances and also real-world instances arising from previous matching runs of the Scottish Foundation Allocation Scheme, used to allocate junior doctors to hospitals in Scotland.
Multipath Matching Pursuit
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose an algorithm referred to as multipath matching pursuit that investigates multiple promising candidates to recover sparse signals from compressed measurements. Our method is inspired by the fact that the problem to find the candidate that minimizes the residual is readily modeled as a combinatoric tree search problem and the greedy search strategy is a good fit for solving this problem. In the empirical results as well as the restricted isometry property (RIP) based performance guarantee, we show that the proposed MMP algorithm is effective in reconstructing original sparse signals for both noiseless and noisy scenarios.
A Multilayered Approach to Estimate Business Performance
Venue: arXiv cs.CY 2014
Year: 2014

The performance of a business is chiefly determined by the business model adopted and its environment of operation. This paper emphasizes on the integration of Web 2.0 services like social networking to your existing business, which helps in the progressive sustainability of the business organization. The usage of Web 2.0 tools, such as Wikipedia, blogs and social networking services such as Facebook, LinkedIn, Orkut by individuals in all societies, has been pervasive and very successful in proliferating their use at the professional or business levels. This paper puts forth the discussion which helps in better understanding of what social networking encompasses for present day business. It also aims to educate business decision makers about the benefits and risks associated in incorporating business model with social networking. Thus, the paper focuses on the implementation of social networking platforms in business operations and discusses the different attributes of business performance and gives an overview in choosing a social networking platform for its business purposes.
Automated Verification of Interactive Rule-Based Configuration Systems (Additional Material)
Venue: arXiv cs.LO 2014
Year: 2014

Additional material for the original paper "Automated Verification of Interactive Rule-Based Configuration Systems".
Delay Minimization for Instantly Decodable Network Coding in Persistent Channels with Feedback Intermittence
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the problem of minimizing the multicast decoding delay of generalized instantly decodable network coding (G-IDNC) over persistent forward and feedback erasure channels with feedback intermittence. In such an environment, the sender does not always receive acknowledgement from the receivers after each transmission. Moreover, both the forward and feedback channels are subject to persistent erasures, which can be modelled by a two state (good and bad states) Markov chain known as Gilbert-Elliott channel (GEC). Due to such feedback imperfections, the sender is unable to determine subsequent instantly decodable packets combination for all receivers. Given this harsh channel and feedback model, we first derive expressions for the probability distributions of decoding delay increments and then employ these expressions in formulating the minimum decoding problem in such environment as a maximum weight clique problem in the G-IDNC graph. We also show that the problem formulations in simpler channel and feedback models are special cases of our generalized formulation. Since this problem is NP-hard, we design a greedy algorithm to solve it and compare it to blind approaches proposed in literature. Through extensive simulations, our adaptive algorithm is shown to outperform the blind approaches in all situations and to achieve significant improvement in the decoding delay, especially when the channel is highly persistent
Relative Comparison Kernel Learning with Auxiliary Kernels
Venue: arXiv cs.LG 2014
Year: 2014

In this work we consider the problem of learning a positive semidefinite kernel matrix from relative comparisons of the form: "object A is more similar to object B than it is to C", where comparisons are given by humans. Existing solutions to this problem assume many comparisons are provided to learn a high quality kernel. However, this can be considered unrealistic for many real-world tasks since relative assessments require human input, which is often costly or difficult to obtain. Because of this, only a limited number of these comparisons may be provided. In this work, we explore methods for aiding the process of learning a kernel with the help of auxiliary kernels built from more easily extractable information regarding the relationships among objects. We propose a new kernel learning approach in which the target kernel is defined as a conic combination of auxiliary kernels and a kernel whose elements are learned directly. We formulate a convex optimization to solve for this target kernel that adds only minor overhead to methods that use no auxiliary information. Empirical results show that in the presence of few training relative comparisons, our method can learn kernels that generalize to more out-of-sample comparisons than methods that do not utilize auxiliary information, as well as similar methods that learn metrics over objects.
Decentralized Rigidity Maintenance Control with Range Measurements for Multi-Robot Systems
Venue: arXiv cs.SY 2014
Year: 2014

This work proposes a fully decentralized strategy for maintaining the formation rigidity of a multi-robot system using only range measurements, while still allowing the graph topology to change freely over time. In this direction, a first contribution of this work is an extension of rigidity theory to weighted frameworks and the rigidity eigenvalue, which when positive ensures the infinitesimal rigidity of the framework. We then propose a distributed algorithm for estimating a common relative position reference frame amongst a team of robots with only range measurements in addition to one agent endowed with the capability of measuring the bearing to two other agents. This first estimation step is embedded into a subsequent distributed algorithm for estimating the rigidity eigenvalue associated with the weighted framework. The estimate of the rigidity eigenvalue is finally used to generate a local control action for each agent that both maintains the rigidity property and enforces additional con- straints such as collision avoidance and sensing/communication range limits and occlusions. As an additional feature of our approach, the communication and sensing links among the robots are also left free to change over time while preserving rigidity of the whole framework. The proposed scheme is then experimentally validated with a robotic testbed consisting of 6 quadrotor UAVs operating in a cluttered environment.
Enhanced Precision Through Multiple Reads for LDPC Decoding in Flash Memories
Venue: arXiv cs.IT 2014
Year: 2014

Multiple reads of the same Flash memory cell with distinct word-line voltages provide enhanced precision for LDPC decoding. In this paper, the word-line voltages are optimized by maximizing the mutual information (MI) of the quantized channel. The enhanced precision from a few additional reads allows FER performance to approach that of full-precision soft information and enables an LDPC code to significantly outperform a BCH code. A constant-ratio constraint provides a significant simplification in the optimization with no noticeable loss in performance. For a well-designed LDPC code, the quantization that maximizes the mutual information also minimizes the frame error rate in our simulations. However, for an example LDPC code with a high error floor caused by small absorbing sets, the MMI quantization does not provide the lowest frame error rate. The best quantization in this case introduces more erasures than would be optimal for the channel MI in order to mitigate the absorbing sets of the poorly designed code. The paper also identifies a trade-off in LDPC code design when decoding is performed with multiple precision levels; the best code at one level of precision will typically not be the best code at a different level of precision.
Information Filtering via Collaborative User Clustering Modeling
Venue: arXiv cs.IR 2014
Year: 2014

The past few years have witnessed the great success of recommender systems, which can significantly help users find out personalized items for them from the information era. One of the most widely applied recommendation methods is the Matrix Factorization (MF). However, most of researches on this topic have focused on mining the direct relationships between users and items. In this paper, we optimize the standard MF by integrating the user clustering regularization term. Our model considers not only the user-item rating information, but also takes into account the user interest. We compared the proposed model with three typical other methods: User-Mean (UM), Item-Mean (IM) and standard MF. Experimental results on a real-world dataset, \emph{MovieLens}, show that our method performs much better than other three methods in the accuracy of recommendation.
Linear Degrees of Freedom of the X-Channel with Delayed CSIT
Venue: arXiv cs.IT 2014
Year: 2014

We establish the degrees of freedom of the two-user X-channel with delayed channel knowledge at transmitters (i.e., delayed CSIT), assuming linear coding strategies at the transmitters. We derive a new upper bound and characterize the linear degrees of freedom of this network to be 6/5. The converse builds upon our development of a general lemma that shows that, if two distributed transmitters employ linear strategies, the ratio of the dimensions of received linear subspaces at the two receivers cannot exceed 3/2, due to delayed CSIT. As a byproduct, we also apply this general lemma to the three-user interference channel with delayed CSIT, thereby deriving a new upper bound of 9/7 on its linear degrees of freedom. This is the first bound that captures the impact of delayed CSIT on the degrees of freedom of this network, under the assumption of linear encoding strategies.
Source Broadcasting to the Masses: Separation has a Bounded Loss
Venue: arXiv cs.IT 2014
Year: 2014

This work discusses the source broadcasting problem, i.e. transmitting a source to many receivers via a broadcast channel. The optimal rate-distortion region for this problem is unknown. The separation approach divides the problem into two complementary problems: source successive refinement and broadcast channel transmission. We provide bounds on the loss incorporated by applying time-sharing and separation in source broadcasting. If the broadcast channel is degraded, it turns out that separation-based time-sharing achieves at least a factor of the joint source-channel optimal rate, and this factor has a positive limit even if the number of receivers increases to infinity. For the AWGN broadcast channel a better bound is introduced, implying that all achievable joint source-channel schemes have a rate within one bit of the separation-based achievable rate region for two receivers, or within $\log_2 T$ bits for $T$ receivers.
A Practical Distributed Universal Construction with Unknown Participants
Venue: arXiv cs.DC 2014
Year: 2014

Modern distributed systems employ atomic read-modify-write primitives to coordinate concurrent operations. Such primitives are typically built on top of a central server, or rely on an agreement protocol. Both approaches provide a universal construction, that is, a general mechanism to construct atomic and responsive objects. These two techniques are however known to be inherently costly. As a consequence, they may result in bottlenecks in applications using them for coordination. In this paper, we investigate another direction to implement a universal construction. Our idea is to delegate the implementation of the universal construction to the clients, and solely implement a distributed shared atomic memory at the servers side. The construction we propose is obstruction-free. It can be implemented in a purely asynchronous manner, and it does not assume the knowledge of the participants. It is built on top of grafarius and racing objects, two novel shared abstractions that we introduce in detail. To assess the benefits of our approach, we present a prototype implementation on top of the Cassandra data store, and compare it empirically to the Zookeeper coordination service.
Exploiting Interference for Efficient Distributed Computation in Cluster-based Wireless Sensor Networks
Venue: arXiv cs.DC 2014
Year: 2014

This invited paper presents some novel ideas on how to enhance the performance of consensus algorithms in distributed wireless sensor networks, when communication costs are considered. Of particular interest are consensus algorithms that exploit the broadcast property of the wireless channel to boost the performance in terms of convergence speeds. To this end, we propose a novel clustering based consensus algorithm that exploits interference for computation, while reducing the energy consumption in the network. The resulting optimization problem is a semidefinite program, which can be solved offline prior to system startup.
Distributed Estimation and Control of Algebraic Connectivity over Random Graphs
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we propose a distributed algorithm for the estimation and control of the connectivity of ad-hoc networks in the presence of a random topology. First, given a generic random graph, we introduce a novel stochastic power iteration method that allows each node to estimate and track the algebraic connectivity of the underlying expected graph. Using results from stochastic approximation theory, we prove that the proposed method converges almost surely (a.s.) to the desired value of connectivity even in the presence of imperfect communication scenarios. The estimation strategy is then used as a basic tool to adapt the power transmitted by each node of a wireless network, in order to maximize the network connectivity in the presence of realistic Medium Access Control (MAC) protocols or simply to drive the connectivity toward a desired target value. Numerical results corroborate our theoretical findings, thus illustrating the main features of the algorithm and its robustness to fluctuations of the network graph due to the presence of random link failures.
Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
Venue: arXiv cs.SI 2014
Year: 2014

Graphs are used to model interactions in a variety of contexts, and there is a growing need to quickly assess the structure of such graphs. Some of the most useful graph metrics are based on triangles, such as those measuring social cohesion. Algorithms to compute them can be extremely expensive, even for moderately-sized graphs with only millions of edges. Previous work has considered node and edge sampling; in contrast, we consider wedge sampling, which provides faster and more accurate approximations than competing techniques. Additionally, wedge sampling enables estimation local clustering coefficients, degree-wise clustering coefficients, uniform triangle sampling, and directed triangle counts. Our methods come with provable and practical probabilistic error estimates for all computations. We provide extensive results that show our methods are both more accurate and faster than state-of-the-art alternatives.
Simulating e-Commerce Client-Server Interaction for Capacity Planning
Venue: arXiv cs.CY 2014
Year: 2014

Contemporary ways of doing business are heavily dependent on the e-Commerce/e-Business paradigm. The highest priority of an e-Commerce Web site's management is to assure pertinent Quality-of-Service (QoS) levels of their Web services continually, in order to keep the potential e-Customers satisfied. Otherwise, it faces an immense possibility of losing both e-Customers and revenues, along with a big possibility of gaining bad reputation due to either poor performance or unavailability of the e-Commerce Web site. In order to avoid numerous unpleasant consequences, by designing and implementing e-Commerce Web sites that will always meet e-Customer's high expectations, a relevant performance models have to be utilized to obtain appropriate performance metrics. A continuous assessment of current performances and especially predicting future needs are the subjects of capacity planning methodologies. Within this paper, such a predictive model has been described and evaluated by using discrete-event simulation of both the client-side and server-side processes involved. In addition, the paper discusses the performance metrics obtained as a function of the intensity and quality of the workload parameters.
Resource Optimization in Device-to-Device Cellular Systems Using Time-Frequency Hopping
Venue: arXiv cs.IT 2014
Year: 2014

We develop a flexible and accurate framework for device-to-device (D2D) communication in the context of a conventional cellular network, which allows for time-frequency resources to be either shared or orthogonally partitioned between the two networks. Using stochastic geometry, we provide accurate expressions for SINR distributions and average rates, under an assumption of interference randomization via time and/or frequency hopping, for both dedicated and shared spectrum approaches. We obtain analytical results in closed or semi-closed form in high SNR regime, that allow us to easily explore the impact of key parameters (e.g., the load and hopping probabilities) on the network performance. In particular, unlike other models, the expressions we obtain are tractable, i.e., they can be efficiently optimized without extensive simulation. Using these, we optimize the hopping probabilities for the D2D links, i.e., how often they should request a time or frequency slot. This can be viewed as an optimized lower bound to other more sophisticated scheduling schemes. We also investigate the optimal resource partitions between D2D and cellular networks when they use orthogonal resources.