IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
Routing and Scheduling for Energy and Delay Minimization in the Powerdown Model
Get PDFEnergy conservation is drawing increasing attention in data networking. As networks are designed for peak traffic, network elements typically operate at full speed and consume maximum power even when carrying low traffic. One school of thought believes that a dominant amount of power saving comes from turning off network elements. The difficulty is that transitioning between the active and sleeping modes consumes considerable energy and time. This results in an obvious trade-off between saving energy and provisioning performance guarantees such as end-to-end delays. We study the following routing and scheduling problem in a network in which each network element either operates in the full- rate active mode or the zero-rate sleeping mode. For a given network and traffic matrix, routing determines the path that each traffic stream traverses. For frame- based periodic scheduling, a schedule determines the active period per element within each frame and prioritizes packets within each active period. For a line topology, we present a schedule with close-to-minimum delay for a minimum active period per element. For an arbitrary topology, we partition the network into a collection of lines and use the near-optimal schedule along each line. Additional delay is incurred only when a path switches from one line to another. By minimizing the number of switchings via routing, we show a logarithmic approximation for both power consumption and end- to-end delays. If routing is given as input, we present two schedules one of which has active period proportional to the traffic load per network element, and the other has active period proportional to the maximum load over all elements. The end-to-end delay of the latter is much improved compared to the delay for the former. This demonstrates the trade-off between power and delay. Finally, we provide simulation results to validate our algorithmic approaches.pu
Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies
Get PDFIn this paper we explore the problem of achieving efficient packet transmission over unreliable links with worst case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric for measuring the efficiency of scheduling strategies in such a setting. To this end, we propose a relative throughput metric which corresponds to the long term competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous error feedback with deferred error feedback, that requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The relative throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the relative throughput of the algorithms and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using
instantaneous feedback to improve the performance of communication systems in adverse environments.TRUEpu
Energy consumption savings with 3G offload
Get PDFDOI: http://dx.doi.org/10.1109/VTCFall.2013.6692182Current trends on mobile traffic show an exponential grow of the traffic consumed by users from smartphones and other portable devices. The explosion of traffic in cellular networks has forced operators to start deploying solutions to alleviate the congestion on their capacity-limited and expensive radio access networks. One of the solutions being discussed is the so called 3G offload that enables the terminals to use other technologies such as WiFi to offload some of the traffic. IP flow mobility is one mechanism providing 3G offload, by enabling selected flows to be moved among network interfaces. Although this is a very promising technology, it is not clear yet how it will affect the protocols currently in use to provide IP mobility in cellular networks, e.g., Proxy Mobile IPv6. The use of 3G offloading does not only benefits the operators, but also the final user, as it might extend the battery lifetime of its terminal. In this paper we first describe some network-based IP flow mobility extensions, highlighting important design choices. Secondly, we focus on providing experimental measurements showing how the use of this technology can result in an extended battery life for the case of 3G and WiFi enabled terminals.TRUEpu
Practical challenges of network optimized stored video delivery
Get PDFThe scope of this thesis is to investigate the challenges and their possible solutions of applying a theoretical model of optimized stored video delivery to an LTE network. Recent paradigm shifts in content consumption, caused by the ever increasing popularity of online social networks, have allowed researchers to predict future content requests. In addition, models that predict user mobility as well as user activity can be used to infer the capacity that users of radio access networks will have in the future. Our work tries to combine the above, in order to optimize the delivery of video content that is predicted to be consumed by a user, whose future channel capacity is perfectly known, in a way that is transparent to him and require as few radio resources as possible. Thus, both increasing the number of users that can be served in a cell and the quality of service that they enjoy. The simulations have shown that our solution achieves a good balance between robustness and low channel utilization, while significantly reducing the cost compared to the benchmark application.TelematicsUniversidad Carlos III de Madrid, Spainpu
Advanced Technologies for Extremely Dense and Heterogeneous Wireless Networks (CROWD project)
No full textFALSEpu
Reputation-based Mechanisms for Evolutionary Master-Worker Computing
Get PDFWe consider Internet-based Master-Worker task computing systems,such as SETI@home, where a master sends tasks to potentially unreliable workers, and the workers execute and report back the result. We model such computations using evolutionary dynamics and consider three type of workers: altruistic,malicious and rational. Altruistic workers always compute and return the correct result, malicious workers always return an incorrect result, and rational(selfish)workers decide to be truthful or to cheat, based on the strategy that increases their benefit. The goal of the master is to reach eventual correctness, that is, reach a state of the computation that always receives the correct results. To this respect, we propose a mechanism that uses reinforcement learning to induce a correct behavior to rational workers; to cope with malice we employ reputation schemes.We analyze our reputation-based mechanism modeling it as a Markov chain and we give provable guarantees under which truthful behavior can be ensured. Simulation results, obtained using parameter values that are likely to occur in practice, reveal interesting trade-offs between various metrics, parameters and reputation types, affecting cost, time of convergence to a truthful behavior and tolerance to cheaters.TRUEpu
Social - Content Revolution. A Vision for the Future Social Oriented Networking
Get PDFhttp://www.w3.org/2013/socialweb/Content distribution services are booming and they will be responsible for the majority of future Internet traffic. In parallel, Online Social Networks (OSNs) have become today's most popular Internet applications. The widespread adoption of OSNs has drastically changed the way content is consumed in the Internet, as the popularity of a given content is most often dictated by its "social" success. This calls for novel social-aware network architectures that exploit these social-content interdependencies to improve the efficiency of content distribution services and the Quality of Experience for the end user. This paper presents a set of targeted use cases to introduce the underlining requirements and standardization opportunities within W3C.TRUEpu
Scaling Next Generation Mobile Video Delivery
Get PDFDemo (MEDIEVAL - Multimedia Transport for Mobile Video Applications - project).FALSEpu
Quid Pro Quo: Mecanismos para la asignación de tareas en entornos distribuidos
Get PDFEn este trabajo proponemos una solución para la asignación de tareas en un entorno distribuido complejo y auto-organizado (sería el caso de las redes entre iguales o ́ P2P). Estamos interesados en las tareas que son comunes a todos los participantes o nodos del sistema. Cada uno de los nodos puede ejecutar estas tareas y, además, está interesado en que éstas se ejecuten. Cada nodo dispone de capacidad para la ejecución de cada una de las tareas. El coste para cada nodo es una información que no puede ser auditada y que es únicamente conocido por el nodo en cuestión. Suponemos que los nodos pueden mentir sobre su coste si eso les supone un beneficio; por ejemplo, por el ahorro que implicaría verse libre de ejecutar las tareas.
La presente tesis se enfrenta al problema de diseñar un sistema que permita la asignación de tareas entre nodos de forma que podamos garantizar un mínimo en el coste de ejecución, con la dificultad añadida de que los nodos son considerados egoístas y que, por lo tanto, tienen incentivos para mentir sobre el valor declarado. A estas dificultades, podemos añadir una serie de requisitos que consideramos oportunos si queremos que el sistema funcione en redes descentralizadas y anárquicas. Nos referimos a: la ausencia de nodos centrales que actúen de árbitros o controladores, la no utilización de sistemas de pago monetarios, nodos limitados total o parcialmente en su racionalidad, reparto justo de trabajo, limitada degradación del rendimiento ante agentes egoístas, el aprendizaje de los nodos sobre el comportamiento de los demás no debe aportar ventajas estratégicas, los nodos deben buscar la máxima agregación y no deben tener interés en crear grupos separados de trabajo y, finalmente, que la complejidad del algoritmo sea abordable desde un punto práctico.
En nuestro trabajo proponemos un modelo matemático y un conjunto de soluciones que resuelven el problema de la asignación de tareas de forma óptima sin necesidad de pagos entre nodos y que responde a los requisitos expuestos. Se proponen varios algoritmos que son analizados con las herramientas matemáticas de la “teoría de juegos” y, en concreto, del “diseño de mecanismos”. A estas soluciones las hemos denominados mecanismos “Quid Pro Quo” (QPQ). Esta expresión se suele utilizar cuando alguien realiza un trabajo o favor y espera en compensación un trabajo o favor equivalente. Presentamos varios mecanismos, correspondiendo cada una de ellos a un determinado nivel de correlación entre las valoraciones de los jugadores o a una diferente noción de justicia.
El primer mecanismo, denominado QPQ Básico, aporta una solución al caso en el que los jugadores tienen valoraciones de coste independientes. En la presente tesis se demuestra que este primer mecanismo tiene todas las propiedades buscadas. Además, se han realizado simulaciones que comprueban la aplicación de estas propiedades en diferentes escenarios.
La segunda familia de mecanismos se denomina QPQ Correlados, ya que el modelo previsto supone que los jugadores pueden tener cierta correlación en las distribuciones de los valores declarados. De nuevo se demuestra que la mayor parte de las propiedades se siguen manteniendo vigentes, aunque algunos conceptos han tenido que ser redefinidos (tales como justicia o eficiencia).
Finalmente, se aporta un esquema para la construcción de mecanismos QPQ basados en mecanismos de Groves. Nuestra propuesta incluye el estudio de las relaciones que pueden existir entre los mecanismos tradicionales de pagos y los mecanismos QPQ. Hemos denominado QPQ VCG o de Groves a este tipo de mecanismos. Aun- que en realidad es un caso particular de los modelos anteriores, creemos que tiene especial interés por su relación con los mecanismos de pago.Departamento de Sistemas Telemáticos y Computación (GSYC)Universidad Rey Juan Carlos, Madrid, Spainpu
Implementing the weakest failure detector for solving the consensus problem
No full textThe concept of unreliable failure detector was introduced by Chandra and Toueg as a mechanism that provides information about process failures. This mechanism has been used to solve several agreement problems, such as the consensus problem. In this paper, algorithms that implement failure detectors in partially synchronous systems are presented. First two simple algorithms of the weakest class to solve the consensus problem, namely the Eventually Strong class (S), are presented. While the first algorithm is wait-free, the second algorithm is f-resilient, where f is a known upper bound on the number of faulty processes. Both algorithms guarantee that, eventually, all the correct processes agree permanently on a common correct process, i.e. they also implement a failure detector of the class Omega (Ω). They are also shown to be optimal in terms of the number of communication links used forever. Additionally, a wait-free algorithm that implements a failure detector of the Eventually Perfect class (P) is presented. This algorithm is shown to be optimal in terms of the number of bidirectional links used forever.pu