15 research outputs found
Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision
No full textWe study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is NP-complete to decide whether the classical value of a non-local game is 1 or 1- epsilon, promised that one of the two is the case. Furthermore, as long as epsilon is small enough, this result does not depend on the gap epsilon. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap epsilon decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of MIP^{co}(2,1,1,s) (proofs with two provers, one round, completeness probability 1, soundness probability s, and commuting-operator strategies) can increase without bound as the gap 1-s gets arbitrarily small.
Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class PZK-MIP^{co}_{delta}(2,1,1,s) of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap 1-s gets arbitrarily small. While we do not know any computable time upper bound on the class MIP^{co}, a result of the first author and Vidick shows that for s = 1-1/poly(f(n)) and delta = 1/poly(f(n)), the class MIP^{co}_delta(2,1,1,s), with constant communication from the provers, is contained in TIME(exp(poly(f(n)))). We give a lower bound of coNTIME(f(n)) (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis
mptcpanalyzer: Zenodo release
No full text<p>This release provides one plot mechanism and the possitibility to load plugins.</p>
Novel approaches for multipath communications
No full textThe criticity of the Internet keeps increasing with a very high number of services depending on its infrastructure. The Internet is expected to support services with an increasing tangible impact on the physical world such as the Internet of Things (IoT) or autonomous vehicles. It is thus important to address the current infrastructure shortcomings in terms of scalability, confidentiality and reliability. Multipath communications are one possible solution to address this challenge. The transition towards multipath technologies is not obvious, there are several challenges ahead. Some network devices block unknown protocols, thus preventing the emergence of new technologies, which plays a part in what is often referred to as the ossification of the Internet. Moreover, due to technical reasons, there are cases for which multipath technologies perform worse than their single path counterpart. In this thesis, we are interested in addressing some of these cases and limit their impact, so that multipath communications perform better than single path communications as often as possible. More specifically, we propose enhancements to Multipath TCP (MPTCP). After a detailed survey of multipath communications across all layers, we propose an answer as to the question of how many paths to use and how to ensure proper forwarding. Moreover, motivated by the intuition that packet arrival disorder can be mitigated by the knowledge of one way latencies, we propose a latency estimator with sender-side modifications only. Furthermore, as throughput maximization is in general solved regardless of the interface cost or user preferences, we elaborate a framework capable of presenting more complex strategies if for instance the user wants to enforce throughput even on less efficient paths. Finally, we develop and present a complete simulation model of MPTCP.La dépendance des différentes infrastructures vis-à-vis du réseau Internet va croissant. D’abord la convergence des médias mais bientôt l’Internet des objets ou les véhicules autonomes peut-être vont contribuer à augmenter la criticité d’Internet. Il est donc important de résoudre les problèmes liés à l’infrastructure actuelle, en terme de passage à l’échelle, de confidentialité ou bien de fiabilité. Les communications multichemins font partie des possibilités pour attaquer ce défi. Pour autant la transition vers ces technologies n’est pas sans difficulté. En effet certains équipements bloquent les protocoles inconnus, empêchant ainsi l’émergence de nouvelles technologies. C’est un phénomène en partie responsable de l’ossification d’internet. D’autres considérations techniques limitent l’intérêt de recourir à des technologies multichemins dans certains cas, puisque celles-ci peuvent alors présenter des performances moindres que les technologies monochemins. Dans le cadre de cette thèse, nous proposons des réponses à certains de ces cas afin de maximiser le spectre d’application des technologies multichemins, en particulier du protocole Multipath TCP (MPTCP). Plus précisémement, après une revue détaillée du domaine des communications multichemins, nous proposons une réponse au problème de découverte des chemins. De plus, motivés par l’intuition que les ordonnanceurs peuvent s’appuyer sur les latences unidirectionelles, afin de lutter contre l’arrivé de paquets dans le désordre, nous proposons une technique qui ne modifie que l’envoyeur de données pour estimer cette métrique. En outre, nous proposons un outil qui maximise le débit tout en prenant en compte des politiques utilisateur par exemple pour forcer l’envoi d’une partie du trafic sur un chemin peu performant mais qui va coûter moins cher à l’utilisateur. Finalement, nous développons et évaluons un modèle de MPTCP
An implementation of Multipath TCP in ns3
No full textInternational audienceThe Multipath Transport Control Protocol (MPTCP) is undergoing a rapid deployment after a recent and quick standardization. MPTCP allows a network node to use multiple network interfaces and IP paths concurrently, which can lead to several advantages for the user in terms of performance and reliability. In this paper, we describe an MPTCP implementation in the Network Simulator 3 (ns3), comparing it with both the Linux implementation and previous ns3 implementations. We show that it is compatible with the Linux implementation and that it has a desirable similar behavior in traffic handling. Our goal is to allow researchers develop and evaluate new features of MPTCP using our simulator in a much faster way than they would with a kernel implementation, hence boosting MPTCP research
Boosting cloud communications through a crosslayer multipath protocol architecture
No full textInternational audienceExternal reliability in data-center networking is today commonly reached via forms of provider multihoming, so as to guarantee higher service availability rates. In parallel, Cloud users also resort to multihoming via different device access interfaces (Wi-fi, 3G, Wired). Both practices add path diversity between Cloud users and servers, unusable with legacy communication protocols. To overcome this void, we present a holistic multipath communication architecture for Cloud access and inter-Cloud communications, and defend its possible implementation using three promising recent protocols functionally acting at three different communication layers: MPTCP, LISP and TRILL
Differentiated Pacing on Multiple Paths to Improve One Way Delay Estimations
No full textInternational audienceSeveral works in the literature show that accurate estimations of the actual One-Way Delays (OWD) could improve the performance of various network protocol, such as Transport Control Protocol (TCP) throughput. With the emergence of multipath transport protocols like Multipath TCP or the Stream Control Transport Protocol (SCTP), the potential impact can be even higher. Indeed, as multipath transport protocols send data concurrently on heterogeneous paths, the knowledge of corresponding OWDs can greatly help mitigating packet arrival disorder. Theoretically, clock synchronization protocols between endpoints could ensure OWD knowledge, but their efficiency at the Internet scale is debatable. In practice, TCP uses the Round Trip Time (RTT) to take into account congestion or to compute retransmission timeouts, and the OWD is assumed to be half the RTT. However, numerous studies show that a majority of Internet connections experience latency asymmetry. In this paper, we propose a technique based on differential pacing over multiple paths to obtain an estimation of the difference in OWDs between the different paths, motivated by its strong utility for multipath transport protocols such as MPTCP and SCTP. Simulations show which are the interesting scenarios of application
Enhancing Buffer Dimensioning for MPTCP
No full textInternational audienceMultipath transport communication solutions gain traction in the communication networks industry. In particular, Multipath Transport Control Protocol (MPTCP) emerges as a viable transport protocol, as it is conceived as a TCP extension, incrementally deployable in the legacy Internet. MPTCP might improve throughput provided that the TCP buffers are big enough, otherwise the opposite may happen. When facing a situation with many paths available, it might be efficient for MPTCP not to use all of them to prevent throughput degradation because of head-of-line blocking. How many paths should be used remains an open question. Depending on the use case, it may be important to keep a path alive for confidentiality reasons or because of the financial cost associated with transmitting over the other paths. We document the MPTCP-NUMERICS tool we developed to manage MPTCP buffers. MPTCP-NUMERICS tries to take into account the MPTCP flow control constraints as well as policy-based constraints in order to answer such questions
Augmented multipath TCP communications
No full textInternational audienceCloud networking imposes new requirements in terms of connection resiliency and throughput among virtual machines, hypervisors and users. A promising direction is to resort to multipath communications, yet existing protocols still struggle to take advantage of the path diversity offered by IP networks. Multipath TCP (MPTCP) can create several TCP subflows on different interfaces and concurrently forward data on these subflows. Current MPTCP implementations create a full mesh of subflows between IP endhosts, which may be suboptimal according to the topology. We propose to rely on topology information brought by an external protocol in order to improve the MPTCP subflow management; we resort to the Locator/Identifier Separation Protocol (LISP) to retrieve IP path diversity information, to then accordingly create MPTCP subflows. We report noticeable benefits obtained using a large-scale Cloud access test bed, and we describe further work we are conducting in this sense
Internet Acceleration with LISP Traffic Engineering and Multipath TCP
No full textInternational audience—We present different design options to implement Augmented Multipath Transmission Control Protocol (A-MPTCP) communications via a Locator/Identifier Separation Protocol (LISP) Traffic Engineering (TE) overlay network. MPTCP allows a TCP connection using multiple subflows to maximize resource usage. LISP is a routing and addressing architecture that provides new semantics for IP communications, by separating the device identity (endpoint identifier) from its location (routing locator) using two different numbering spaces. Our proposition is to adopt a LISP overlay network with traffic engineering capabilities to steer MPTCP subflows across wide-area Internet networks. The resulting augmentation consists of a subflow forwarding that can reach edge bottleneck capacity and surround inter-domain transit bottlenecks and inefficient paths. It can be particularly useful for cases where, even if endpoints are single-homed, inter-domain path diversity can be grasped by the LISP-TE network overlay. We specify the different modes at which this augmentation can take place, from stateless and light modes with very limited management in the network, to stateful and advanced modes implementable by a network provider desiring a higher control on the network. Based on extensive experimentation on the worldwide LISP testbed, we show that the achievable gains up 25% in throughput, while identifying required further improvements
