Data link layer | EPFL Graph Search

The data link layer, or layer 2, is the second layer of the seven-layer OSI model of computer networking. This layer is the protocol layer that transfers data between nodes on a network segment across the physical layer. The data link layer provides the functional and procedural means to transfer data between network entities and may also provide the means to detect and possibly correct errors that can occur in the physical layer. The data link layer is concerned with local delivery of frames between nodes on the same level of the network. Data-link frames, as these protocol data units are called, do not cross the boundaries of a local area network. Inter-network routing and global addressing are higher-layer functions, allowing data-link protocols to focus on local delivery, addressing, and media arbitration. In this way, the data link layer is analogous to a neighborhood traffic cop; it endeavors to arbitrate between parties contending for access to a medium, without concern fo

Energy Saving and Capacity Gain of Micro Sites in Regular LTE Networks: Downlink Traffic Layer Analysis

Ramin Khalili, Jean-Yves Le Boudec, Teklemariam Tsegay Tesfay

We study the impact of deployment of low cost, low power micro base stations along with macro base stations on energy consumption and capacity of downlink LTE. We add three important elements to the existing studies: a traffic layer analysis that take both the physical and traffic layer specifications of LTE downlink into account; a threshold-based policy to associate users to base stations; and an allocation scheme to allocate the frequency band to macro and micro sites. We investigate all combinations of these elements through numerical evaluation. We observe that 1. there are important differences between traffic layer and physical layer analysis, 2. threshold-based user association policy improve the capacity of the network by up to 33% without affecting the energy profile of the network, and 3. considerable energy saving and capacity gain can be achieved thought an optimal allocation of the frequency band to macro and micro sites. Finally, we show that up to 46% saving in energy can be achieved by a careful network deployment as compared to the case that no micro sites are deployed in the network.

2010

Anypath routing

Henri Julien Dubois-Ferrière

In many networks, it is less costly to transmit a packet to any node in a set of neighbors than to one specific neighbor. A well-known instance is with unreliable wireless links, where the probability that at least one node out ofnreceives a packet increases with n. This observation was previously exploited, by modifying single-path routing to assign to each node group of candidate next-hops for a particular destination. However, single-path metrics not do reflect the cost of forwarding when a sender has multiple candidate relays, and they result in routing decisions that are in many cases suboptimal. This dissertation addresses the shortest anypath routing problem: how to assign a set of candidate relays at each node for a given destination, such that the cost of forwarding a packet to the destination is minimized. The key is the following tradeoff: on the one hand, increasing the number of candidate relays decreases the forwarding cost, but on the other, this increases the likelihood of "veering" away from the most direct trajectory. Solving the shortest anypath problem requires us first to formalize the notions of anycast link cost and remaining path cost, that generalize the link cost and path cost of single-path routing. Unlike with single-path routing, a packet can travel across an anypath route in many different ways; the cost of this route is naturally defined as the expected cost of all possible traversals. We introduce an algorithm that provably computes the shortest anypath route between each node and a destination. It is based on the Bellman-Ford algorithm and so is amenable to implementation in a distributed setting. This algorithm works for all physical cost metrics; we show that there exist certain "non-physical" cost metrics under which the shortest anypath route may contain cycles. We also explore the interaction between the relay selection policy, that is, the way in which the effective relay is chosen among many receivers, and the cost of optimal routes. We also explore the robustness of anypath routes, and find that they are significantly more stable in the face of topology changes and imperfect information than are single-path and multipath routes. The principles of anypath routing are general and can be applied in many settings. Our application focus in this dissertation is on low-power, low-rate wireless communication in embedded wireless networks. We introduce novel ways in which low-power link-layers can take advantage of anycast forwarding to reduce transmission energy or latency. We describe the design and implementation of a complete anypath routing protocol; evaluation on a 50-node wireless testbed demonstrates that anypath routing is robust, stable, and increases energy efficiency of low-power nodes by a significant factor over the equivalent system using single-path routing. Finally, we describe a novel error-correctionmechanism for multi-hop wireless communication based on packet combining. Packet combining allows to exploit corrupt packets received at different nodes by jointly decoding independent, noisy versions of an original packet.

EPFL2006

Interference management in impulse-radio ultra-wide band networks

Ruben Merz

We consider networks of impulse-radio ultra-wide band (IR-UWB) devices. We are interested in the architecture, design, and performance evaluation of these networks in a low data-rate, self-organized, and multi-hop setting. IR-UWB is a potential physical layer for sensor networks and emerging pervasive wireless networks. These networks are likely to have no particular infrastructure, might have nodes embedded in everyday life objects and have a size ranging from a few dozen nodes to large-scale networks composed of hundreds of nodes. Their average data-rate is low, on the order of a few megabits per second. IR-UWB physical layers are attractive for these networks because they potentially combine low-power consumption, robustness to multipath fading and to interference, and location/ranging capability. The features of an IR-UWB physical layer greatly differ from the features of the narrow-band physical layers used in existing wireless networks. First, the bandwidth of an IR-UWB physical layer is at least 500 MHz, which is easily two orders of magnitude larger than the bandwidth used by a typical narrow-band physical layer. Second, this large bandwidth implies stringent radio spectrum regulations because UWB systems might occupy a portion of the spectrum that is already in use. Consequently, UWB systems exhibit extremely low power spectral densities. Finally IR-UWB physical layers offer multi-channel capabilities for multiple and concurrent access to the physical layer. Hence, the architecture and design of IR-UWB networks are likely to differ significantly from narrow-band wireless networks. For the network to operate efficiently, it must be designed and implemented to take into account the features of IR-UWB and to take advantage of them. In this thesis, we focus on both the medium access control (MAC) layer and the physical layer. Our main objectives are to understand and determine (1) the architecture and design principles of IR-UWB networks, and (2) how to implement them in practical schemes. In the first part of this thesis, we explore the design space of IR-UWB networks and analyze the fundamental design choices. We show that interference from concurrent transmissions should not be prevented as in protocols that use mutual exclusion (for instance, IEEE 802.11). Instead, interference must be managed with rate adaptation, and an interference mitigation scheme should be used at the physical layer. Power control is useless. Based on these findings, we develop a practical PHY-aware MAC protocol that takes into account the specific nature of IR-UWB and that is able to adapt its rate to interference. We evaluate the performance obtained with this design: It clearly outperforms traditional designs that, instead, use mutual exclusion or power control. One crucial aspect of IR-UWB networks is packet detection and timing acquisition. In this context, a network design choice is whether to use a common or private acquisition preamble for timing acquisition. Therefore, we evaluate how this network design issue affects the network throughput. Our analysis shows that a private acquisition preamble yields a tremendous increase in throughput, compared with a common acquisition preamble. In addition, simulations on multi-hop topologies with TCP flows demonstrate that a network using private acquisition preambles has a stable throughput. On the contrary, using a common acquisition preamble exhibits an effect similar to exposed terminal issues in 802.11 networks: the throughput is severely degraded and flow starvation might occur. In the second part of this thesis, we are interested in IEEE 802.15.4a, a standard for low data-rate, low complexity networks that employs an IR-UWB physical layer. Due to its low complexity, energy detection is appealing for the implementation of practical receivers. But it is less robust to multi-user interference (MUI) than a coherent receiver. Hence, we evaluate the performance of an IEEE 802.15.4a physical layer with an energy detection receiver to find out whether a satisfactory performance is still obtained. Our results show that MUI severely degrades the performance in this case. The energy detection receiver significantly diminishes one of the most appealing benefits of UWB, specifically its robustness to MUI and thus the possibility of allowing for parallel transmissions. This performance analysis leads to the development of an IR-UWB receiver architecture, based on energy detection, that is robust to MUI and adapted to the peculiarities of IEEE 802.15.4a. This architecture greatly improves the performance and entails only a moderate increase in complexity. Finally, we present the architecture of an IR-UWB physical layer implementation in ns-2, a well-known network simulator. This architecture is generic and allows for the simulation of several multiple-access physical layers. In addition, it comprises a model of packet detection and timing acquisition. Network simulators also need to have efficient algorithms to accurately compute bit or packet error rates. Hence, we present a fast algorithm to compute the bit error rate of an IR-UWB physical layer in a network setting with MUI. It is based on a novel combination of large deviation theory and importance sampling.

EPFL2008