IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
Graphs of Edge-Intersecting Non-splitting Paths in a Tree: Towards Hole Representations
Get PDFPublished as part of the book Book "Graph-Theoretic Concepts in Computer Science, 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers"
DOI: 10.1007/978-3-642-45043-3_11Given a tree and a set P of non-trivial simple paths on it, Vpt( P ) is the VPT graph (i.e. the vertex intersection graph) of P , and Ept( P ) is the EPT graph (i.e. the edge intersection graph) of the paths P of the tree T. These graphs have been extensively studied in the literature. Given two (edge) intersecting paths in a graph, their split vertices is the set of vertices having degree at least 3 in their union. A pair of (edge) intersecting paths is termed non-splitting if they do not have split vertices (namely if their union is a path). In this work, we define the graph Enpt( P ) of edge intersecting non-splitting paths of a tree, termed the ENPT graph, as the (edge) graph having a vertex for each path in P , and an edge between every pair of paths that are both edge-intersecting and non-splitting. A graph G is an ENPT graph if there is a tree T and a set of paths P of T such that G = Ept P , and we say that 〈T, , P 〉 is a representation of G. We show that trees, cycles and complete graphs are ENPT graphs. We characterize the representations of chordless ENPT cycles that satisfy a certain assumption. Unlike chordless EPT cycles which have a unique representation, these representations turn out to be multiple and have a more complex structure. Therefore, in order to give this characterization, we assume the EPT graph induced by the vertices of a chordless ENPT cycle is given, and we provide an algorithm that returns the unique representation of this EPT, ENPT pair of graphs. These representations turn out to have a more complex structure than chordless EPT cycles.TRUEpu
Is the Network Turing-Complete? EPFL Technical Report 187131
Get PDFEnsuring correct network behavior is hard. This is the case even for simple networks, and adding middleboxes only complicates this task. In this paper, we demonstrate a fundamental property of networks. Namely, we show a way of using a network to emulate the Rule 110 cellular automaton. We do so using just a set of network devices with simple features such as packet matching, header rewriting and round-robin loadbalancing. Therefore, we show that a network can emulate any Turing machine. This ultimately means that analyzing dynamic network behavior can be as hard as analyzing an arbitrary program. Analyzing a network containing middleboxes is already understood to be hard. Our result shows that using even only statically configured switches can make the problem intractable.pu
On Weather and Internet Traffic Demand
Get PDFThe weather is known to have a major impact on demand of utilities such as electricity or gas. Given that the Internet usage is strongly tied with human activity, one could guess the existence of similar correlation between its traffic demand and weather conditions. In this paper, we empirically quantify such effects. We find that the influence of precipitation depends on both time of the day as well as time of the year, and is maximal in the late afternoon over summer months.TRUEpu
Performance Bounds in Coupled Processor Systems
Get PDFWe consider queuing systems with coupled processors, where the service rate at each queue depends on the set of active queues in the system. The coupled-processors model arises naturally in the study of systems where a resource is shared by several classes of customers. For instance, its application has been suggested to model the complex interdependence that is present in wireless scenarios.
In general, the queue lengths of such systems, that we call Coupled Processor Systems (CPSs), are modelled through complex Markov Chains whose steady state distributions are known only for two-queue systems. In this paper we propose a new approach for the study of the performance of the CPSs, based on worst case analysis. Our method exploits Network Calculus results over a set of networks whose stability implies the stability of the CPS, and allows to derive sufficient conditions for the stability of a CPS,
as well as to compute bounds to queue size and packet delay. We also apply the CPS model to an ad-hoc IEEE 802:11 scenario, where we present a method to derive practical results, and where we show numerically that considering the characteristics of the incoming flows at the nodes improves substantially the resource allocation in the system.Telematics EngineeringUniversidad Carlos III de Madrid, Spainpu
Performance Evaluation of the IEEE 802.11aa Multicast Mechanisms for Video Streaming
Get PDFVideo traffic is foreseen to account for the majority of the Internet traffic in the near future. While the demand of video transmission keeps growing, the vast majority of wireless equipment deployed in the home environment, based on IEEE 802.11, cannot satisfy the amount of bandwidth that the video applications require. In order to cope with the increasing demand of multimedia traffic, the IEEE 802.11aa Task Group has recently standardized new mechanisms to allow efficient and robust transmission of multicast flows in Wireless LAN. However, the standard leaves open the choice of which one to use for a given scenario. In this paper, we explore the new mechanisms introduced by the 802.11aa Task Group, providing insights of the new choices for handling group addressed frames, by carrying out extensive simulations. Our results highlight the various trade-offs each mechanism has in terms of robustness, resource consumption and complexity, and provide a set of recommended guidelines for their use.TRUEpu
Sub-carrier Switch Off in OFDM-Based Wireless Local Area Networks
Get PDFAbstract—OFDM based wireless communication systems split the available frequency band into so-called sub-carriers, and data is transmitted on each of these sub-carriers in parallel. With frequency selective fading, sub-carriers may experience different channel qualities. Thus, choosing a different modulation and coding scheme (MCS) per sub-carrier improves performance. However, this comes at an increase in transceiver complexity and no current wireless system adapts the MCS at such a fine granularity. Some OFDMA based systems such as LTE allow to adapt the MCS per user, whereas wireless local area networks as specified by IEEE 802.11 use the same MCS on every sub-carrier. The performance of such wireless systems that use a single MCS in a frequency selective fading channel can be significantly improved through Sub-Carrier Switch Off (SSO), a simple but powerful alternative to adaptive MCS. SSO deactivates weak sub-carriers that excessively raise the error probability to improve the overall throughput. In this paper, we implement and test SSO in a software-defined radio testbed based on the Wireless Open Access Research Platform (WARP). We present a novel light-weight method for selecting the sub-carriers to be switched off based on the per-sub-carrier channel quality. The results we obtain from our measurements indicate that throughput increases of up to 250% are possible and thus SSO is a highly promising and very low complexity mechanism for future wireless local area networks.TRUEpu
Online Parallel Scheduling of Non-uniform Tasks: Trading Failures for Energy
Get PDFConsider a system in which tasks of different execution times arrive continuously and have to be executed by a set of processors that are prone to crashes and restarts. In this paper we model and study the impact of parallelism and failures on the competitiveness of such an online system. In a fault-free environment, a simple Longest-in-System scheduling policy, enhanced by a redundancy-avoidance mechanism, guarantees optimality in a long-term execution. In the presence of failures though, scheduling becomes a much more challenging task. In particular, no parallel deterministic algorithm can be competitive against an offline optimal solution, even with one single processor and tasks of only two different execution times. We find that when additional energy is provided to the system in the form of processor speedup, the situation changes. Specifically, we identify thresholds on the speedup under which such competitiveness cannot be achieved by any deterministic algorithm, and above which competitive algorithms exist. Finally, we propose algorithms that achieve small bounded competitive ratios when the speedup is over the threshold.TRUEpu
CSI Feedback in OFDMA Wireless Networks with Multiple Sender-Receiver Pairs
Get PDFIn wired or wireless distribution systems, as well as wireless mesh networks, multiple senders often need to deliver data to multiple receivers in the same interference domain. OFDMA enables interference avoidance by assigning disjoint sets of subcarriers to each sender. However, optimal subcarrier allocation requires CSI feedback to the transmitters, thus in-curring overhead. We evaluate an allocation mechanism inspired in subcarrier switching techniques, which allows nodes to locally decide which subcarriers they prefer. Hence, feedback is minimal, as only preference values need to be shared. We implement this approach on software defined radios and compare it to standard CSI feedback mechanisms. Despite our approach only requires local information, the results show that it performs close to an ideal solution based on full CSI knowledge.TRUEpu
