Large Language Models (LLMs) based on autoregressive, decoder-only Transformers generate text one token at a time, where a token represents a discrete unit of text. As each newly produced token is appended to the partial output sequence, the length grows and so does the memory and compute load, due to the expanding key-value (K/V) caches-which store intermediate representations of all previously generated tokens-in the multi-head attention (MHA) layer. As this iterative process steadily increases memory and compute demands, layer-based partitioning in resource-constrained edge environments often results in memory overload or high inference latency. To address this, aiming to reduce inference latency, we propose a resource-aware Transformer architecture partitioning algorithm, where the partitioning decision is updated at regular intervals during token generation. The approach is a myopic algorithm in the sense that it is based on instantaneously available information about device resources availability and network link bandwidths. When the algorithm is first executed, it generates a placement of blocks on devices, and in each consecutive time it is executed, it migrates these blocks among devices so that the sum of migration delay and inference delay remains low. Our approach partitions the decoder at the attention head-level, co-locating each attention head with its K/V cache and allowing dynamic migrations whenever resources become tight. By allocating different attention heads to different devices, we exploit parallel execution of attention heads and thus allow for substantial reductions in inference delays. Our experiments show that in small-scale settings (3-5 devices), the proposed method achieves within 15-20% of an exact optimal solver's latency, while in larger-scale tests it achieves notable improvements in inference speed and memory usage compared to state-of-the-art layer-based partitioning approaches.

The emergence of network function virtualization has enabled network function chaining as a flexible approach for building complex network services. However, the high degree of flexibility envisioned for orchestrating network function chains introduces several challenges to support dynamism in workloads and the environment necessary for their realization. Existing works mostly consider supporting dynamism by re-adjusting provisioning of network function instances, incurring reaction times that are prohibitively high in practice. Existing solutions to dynamic packet scheduling rely on centralized schedulers and a priori knowledge of traffic characteristics, and cannot handle changes in the environment like link failures.We fill this gap by presenting FUMES, a reinforcement learning based distributed agent design for the runtime scheduling problem of assigning packets undergoing treatment by network function chains to network function instances. Our design consists of multiple distributed agents that cooperatively work on the scheduling problem. A key design choice enables agents, once trained, to be applicable for unknown chains and traffic patterns including branching, and different environments including link failures. The paper presents the system design and shows its suitability for realistic deployments. We empirically compare FUMES with state-of-the-art runtime scheduling solutions showing improved scheduling decisions at lower server capacity.

The Intelligent Transportation System (ITS) environment is known to be dynamic and distributed, where participants (vehicle users, operators, etc.) have multiple, changing and possibly conflicting objectives. Although Reinforcement Learning (RL) algorithms are commonly applied to optimize ITS applications such as resource management and offloading, most RL algorithms focus on single objectives. In many situations, converting a multi-objective problem into a single-objective one is impossible, intractable or insufficient, making such RL algorithms inapplicable. We propose a multi-objective, multi-agent reinforcement learning (MARL) algorithm with high learning efficiency and low computational requirements, which automatically triggers adaptive few-shot learning in a dynamic, distributed and noisy environment with sparse and delayed reward. We test our algorithm in an ITS environment with edge cloud computing. Empirical results show that the algorithm is quick to adapt to new environments and performs better in all individual and system metrics compared to the state-of-the-art benchmark. Our algorithm also addresses various practical concerns with its modularized and asynchronous online training method. In addition to the cloud simulation, we test our algorithm on a single-board computer and show that it can make inference in 6 milliseconds.

Macrodiversity is a key technique to increase the capacity of mobile networks. It can be realized using coordinated multipoint (CoMP), simultaneously connecting users to multiple overlapping cells. Selecting which users to serve by how many and which cells is NP-hard but needs to happen continuously in real time as users move and channel state changes. Existing approaches often require strict assumptions about or perfect knowledge of the underlying radio system, its resource allocation scheme, or user movements, none of which is readily available in practice. Instead, we propose three novel self-learning and self-adapting approaches using model-free deep reinforcement learning (DRL): DeepCoMP, DD-CoMP, and D3-CoMP. DeepCoMP leverages central control and observations of all users to select cells almost optimally. DD-CoMP and D3-CoMP use multi-agent DRL, which allows distributed, robust, and highly scalable coordination. All three approaches learn from experience and self-adapt to varying scenarios, reaching 2x higher Quality of Experience than other approaches. They have very few built-in assumptions and do not need prior system knowledge, making them more robust to change and better applicable in practice than existing approaches.

Federated learning (FL) is usually performed on resource-constrained edge devices, e.g., with limited memory for the computation. If the required memory to train a model exceeds this limit, the device will be excluded from the training. This can lead to a lower accuracy as valuable data and computation resources are excluded from training, also causing bias and unfairness. The FL training process should be adjusted to such constraints. The state-of-the-art techniques propose training subsets of the FL model at constrained devices, reducing their resource requirements for training. However, these techniques largely limit the co-adaptation among parameters of the model and are highly inefficient, as we show: it is actually better to train a smaller (less accurate) model by the system where all the devices can train the model end-to-end than applying such techniques. We propose a new method that enables successive freezing and training of the parameters of the FL model at devices, reducing the training’s resource requirements at the devices while still allowing enough co-adaptation between parameters. We show through extensive experimental evaluation that our technique greatly improves the accuracy of the trained model (by 52.4 p.p. ) compared with the state of the art, efficiently aggregating the computation capacity available on distributed devices.

Federated Learning (FL) has emerged as a decentralized technique, where contrary to traditional centralized approaches, devices perform a model training in a collaborative manner, while preserving data privacy. Despite the existing efforts made in FL, its environmental impact is still under investigation, since several critical challenges regarding its applicability to wireless networks have been identified. Towards mitigating the carbon footprint of FL, the current work proposes a Genetic Algorithm (GA) approach, targeting the minimization of both the overall energy consumption of an FL process and any unnecessary resource utilization, by orchestrating the computational and communication resources of the involved devices, while guaranteeing a certain FL model performance target. A penalty function is introduced in the offline phase of the GA that penalizes the strategies that violate the constraints of the environment, ensuring a safe GA process. Evaluation results show the effectiveness of the proposed scheme compared to two state-of-the-art baseline solutions, achieving a decrease of up to 83% in the total energy consumption.

We study the problem of distributed training of neural networks (NNs) on devices with heterogeneous, limited, and time-varying availability of computational resources. We present an adaptive, resource-aware, on-device learning mechanism, DISTREAL, which is able to fully and efficiently utilize the available resources on devices in a distributed manner, increasing the convergence speed. This is achieved with a dropout mechanism that dynamically adjusts the computational complexity of training an NN by randomly dropping filters of convolutional layers of the model. Our main contribution is the introduction of a design space exploration (DSE) technique, which finds Pareto-optimal per-layer dropout vectors with respect to resource requirements and convergence speed of the training. Applying this technique, each device is able to dynamically select the dropout vector that fits its available resource without requiring any assistance from the server. We implement our solution in a federated learning (FL) system, where the availability of computational resources varies both between devices and over time, and show through extensive evaluation that we are able to significantly increase the convergence speed over the state of the art without compromising on the final accuracy.

We formulate computation offloading as a decentralized decision-making problem with autonomous agents. We design an interaction mechanism that incentivizes agents to align private and system goals by balancing between competition and cooperation. The mechanism provably has Nash equilibria with optimal resource allocation in the static case. For a dynamic environment, we propose a novel multi-agent online learning algorithm that learns with partial, delayed and noisy state information, and a reward signal that reduces information need to a great extent. Empirical results confirm that through learning, agents significantly improve both system and individual performance, e.g., 40% offloading failure rate reduction, 32% communication overhead reduction, up to 38% computation resource savings in low contention, 18% utilization increase with reduced load variation in high contention, and improvement in fairness. Results also confirm the algorithm’s good convergence and generalization property in significantly different environments.

Recent reinforcement learning approaches for continuous control in wireless mobile networks have shown impressive results. But due to the lack of open and compatible simulators, authors typically create their own simulation environments for training and evaluation. This is cumbersome and time-consuming for authors and limits reproducibility and comparability, ultimately impeding progress in the field.To this end, we propose mobile-env, a simple and open platform for training, evaluating, and comparing reinforcement learning and conventional approaches for continuous control in mobile wireless networks. mobile-env is lightweight and implements the common OpenAI Gym interface and additional wrappers, which allows connecting virtually any single-agent or multi-agent reinforcement learning framework to the environment. While mobile-env provides sensible default values and can be used out of the box, it also has many configuration options and is easy to extend. We therefore believe mobile-env to be a valuable platform for driving meaningful progress in autonomous coordination of wireless mobile networks.

Beyond 5G networks bring a new era in system automation, by introducing new and demanding, in terms of Quality of Service (QoS), use cases and applications. Predicting the QoS for end users in a timely manner and enabling service adaptation methods to react in advance in case of QoS degradation is of high importance, especially for safety-critical applications such as in vehicular communications. Current state-of-the-art approaches propose solutions towards the identification of potential QoS deterioration in a centralized manner. However, centralized solutions may raise privacy issues, since sensitive user information may need to be transmitted to communication network entities for processing and analysis. Other practical limitations of centralized solutions may also arise, such as the computational bottleneck and the fast increase of signaling overhead with number of end users. This study proposes a distributed QoS prediction scheme based on the well-known Long Short-Term Memory (LSTM) architecture to account for the natural high correlation of samples closely located in time. The primary target of the proposed scheme is to provide accurate QoS predictions up to several seconds, while preserving data privacy and reducing signaling overheads related to the exchange of information between the involved nodes. The evaluation of the proposed scheme indicates its potential gains and effectiveness compared to centralized state-of-the-art OoS prediction solutions.

Cellular networks enable high reliability of vehicle-to-vehicle (V2V) communications thanks to centralized, efficient coordination of radio resources. Collision-free transmissions are possible, where base stations could allocate orthogonal resources to the vehicles. However, in case of limited resources in relation to the data traffic load, the resource allocation task becomes a challenge. Current solutions propose heuristic algorithms that focus on resource reuse, often based on the location of the vehicles. Such schedulers are mainly designed assuming ideal network coverage conditions and are prone to performance degradation in case of coverage loss. Further, they typically rely on frequent scheduling updates, which increases the dependency on coverage. In this paper, we propose a reinforcement learning-based approach to scheduling V2V communications. Our solution, called iVRLS, delivers higher reliability than an enhanced version of a state-of-the-art benchmark algorithm in case of intermittent coverage conditions, while requiring less frequent scheduling. Following this approach, we enable a unified scheduler deployment irrespective of coverage, which offers graceful performance behavior across varying coverage conditions, thus making iVRLS a robust alternative to existing schedulers.

Modern services consist of interconnected components, e.g., microservices in a service mesh or machine learning functions in a pipeline. These services can scale and run across multiple network nodes on demand. To process incoming traffic, service components have to be instantiated and traffic assigned to these instances, taking capacities, changing demands, and Quality of Service (QoS) requirements into account. This challenge is usually solved with custom approaches designed by experts. While this typically works well for the considered scenario, the models often rely on unrealistic assumptions or on knowledge that is not available in practice (e.g., a priori knowledge). We propose DeepCoord, a novel deep reinforcement learning approach that learns how to best coordinate services and is geared towards realistic assumptions. It interacts with the network and relies on available, possibly delayed monitoring information. Rather than defining a complex model or an algorithm on how to achieve an objective, our model-free approach adapts to various objectives and traffic patterns. An agent is trained offline without expert knowledge and then applied online with minimal overhead. Compared to a state-of-the-art heuristic, DeepCoord significantly improves flow throughput (up to 76%) and overall network utility (more than 2x) on real-world network topologies and traffic traces. It also supports optimizing multiple, possibly competing objectives, learns to respect QoS requirements, generalizes to scenarios with unseen, stochastic traffic, and scales to large real-world networks. For reproducibility and reuse, our code is publicly available.

Modern services comprise interconnected components, e.g., microservices in a service mesh, that can scale and run on multiple nodes across the network on demand. To process incoming traffic, service components have to be instantiated and traffic assigned to these instances, taking capacities and changing demands into account. This challenge is usually solved with custom approaches designed by experts. While this typically works well for the considered scenario, the models often rely on unrealistic assumptions or on knowledge that is not available in practice (e.g., a priori knowledge). We propose a novel deep reinforcement learning approach that learns how to best coordinate services and is geared towards realistic assumptions. It interacts with the network and relies on available, possibly delayed monitoring information. Rather than defining a complex model or an algorithm how to achieve an objective, our model-free approach adapts to various objectives and traffic patterns. An agent is trained offline without expert knowledge and then applied online with minimal overhead. Compared to a state-of-the-art heuristic, it significantly improves flow throughput and overall network utility on real-world network topologies and traffic traces. It also learns to optimize different objectives, generalizes to scenarios with unseen, stochastic traffic patterns, and scales to large real-world networks.

Network function virtualization has introduced a high degree of flexibility for orchestrating service functions. The provisioning of chains of service functions requires making decisions on both (1) placement of service functions and (2) scheduling of traffic through them. The placement problem (1) can be tackled during the planning phase, by exploiting coarse-grained traffic information, and has been studied extensively. However, runtime traffic scheduling (2) for optimizing system utilization and service quality, as required for future edge cloud and mobile carrier scenarios, has not been addressed so far.We fill this gap by presenting a queuing-based system model to characterize the runtime traffic scheduling problem for service function chaining. We propose a throughput-optimal scheduling policy, called integer allocation maximum pressure policy (IA-MPP). To ensure practicality in large distributed settings, we propose multi-site cooperative IA-MPP (STEAM), fulfilling runtime requirements while achieving near-optimal performance. We examine our policies in various settings representing real-world scenarios. STEAM closely matches IA-MPP in terms of throughput, and significantly outperforms (possible adaptations of) existing static or coarse-grained dynamic solutions, requiring 30%-60% less server capacity for similar service quality. Our STEAM prototype shows feasibility running on a standard server.

In software-defined networking, the typical switch-controller cycle, from generating a network event notification at the controller until the flow rules are installed at the switches, is not an instantaneous activity. Our measurement results show that this has serious implications on the performance of flow setup procedure, specifically for larger networks: we observe that, even with software switches, the flow setup latency for networks of around 500 switches is in the order of 50 ms, with 99th percentile exhibiting 10× higher latencies. To reduce both the latency and the variance of the flow setup, we propose path aggregation strategies, which turn the network into a set of pre-configured pipes that connect any pair of nodes. Our approach radically simplifies the flow setup procedure by minimizing the set of switches to be updated for new user-initiated flows to a constant number. We implement our solution in our testbed and study its performance through measurements. The results show that in similar settings, it reduces the median and 99-percentile latencies to 5.9 and 7 ms, respectively, significantly improving the performance, especially in the tail.

While bringing many advantages, Software-Defined Networking (SDN) is accompanied by potential scalability issues that should be considered in the design of SDN-based networks. Specifically, SDN hardware switches based on Ternary Content-Addressable Memory (TCAM) can only store a few thousands of rules, imposing thus severe limits on the number of flows they can serve/process. Current proposals to deal with this problem mainly focus on optimal placement of flows that complies with the given constraints on TCAM size. We argue in this paper that flow routing not only should be but also can be independent of TCAM size constraints. We introduce two flow rule aggregation algorithms: One performs the "per-outport'' aggregation of the paths between access nodes in the network. It is optimal in that it holds the flow table sizes at the minimum, but has a drawback that it produces long identifiers of the path endpoints (access nodes), which cannot fit the IP address size. The other algorithm is its approximation under the constraint that the generated identifiers fit the limit imposed by the addressing scheme (e.g., IPv4). We study the performance of our algorithms analytically and through a set of experiments. While the optimal solution always keeps the flow table sizes at the minimum, we show that the approximate algorithm reduces the flow table sizes by a factor of 2 to 10 compared to the state of the art solution, under a reasonable constraint on the address length (e.g., 32 bits in case of IPv4).

Software Defined Networking (SDN) is considered one of the major driving factors to bring radical changes on Mobile Core Networks (MCN) design. There are many proposals on how to advocate SDN methodology, however, most of them stop at “vision” level without providing details about key performance contributors. In this paper, we tackle this gap and present a study of latency in SDN based MCN. We identify the major factors and elements in an SDN MCN that contribute to the overall latency. Two types of latency are considered: the processing delay inside the SDN control plane and the transmission delay of SDN control messages between controller and the managed switches. We use a realistic system setup with implementations of SDN controller and SDN application, as well as in-band transfer of control messages among switches and controller. We compare the latency obtained from SDN based MCN with the Evolved Packet Core (EPC). The observed overall latency in our experiments for SDN based MCN is within the EPC requirements. The direct comparison of the SDN versus EPC based MCN in the proposed scenarios show the first can reduce the overall latency. We also identified that the calls to controller APIs can be the major key contributors to the overall latency in SDN MCN, but the act of transmitting more control messages from the controller to the switches to setup longer flowpaths is not a key contributor for the overall latency.

Telco operators started to apply the SDN technologies also in the design of Mobile Core Networks (MCNs). In this change towards SDNized Mobile Core Network, it is crucial to understand how conventional interfaces among different mobile network entities should evolve. The issues derived from this change have not been tackled by current research approaches. This paper presents the first initiative to close this research gap. We tackle the key problem of how to identify which mobile SDN applications (APPs) should be invoked once a PACKET_IN (the OpenFlow message that transport information from the data plane to the control plane) is received at the control level. We propose data structures, a model, and detailed examples of three important PACKET_IN context interpretation for MCNs. Initial experiments, based on Floodlight controller and Mininet emulation environment were carried out. The results indicate that it is feasible to use our proposed approach to dispatch PACKET_INs to the right SDN APP. The delay introduced due to invocation of such mechanism to interpret the context of the PACKET_IN and activate the appropriate mobile SDN APPs is only in the order of microseconds. Our proposal can be used to simplify current Mobile Core Network interface design by exploiting the SDN mechanisms. We believe, this work helps to pave the way towards fully SDNized Mobile Core Networks.

Current solutions to evolve mobility management in Mobile Core Networks (MCN) based on SDN have showed the gain in flexibility and how to reduce control signaling. However, these works neglect the problems of describing the design choices of SDN Mobility Management Applications (MMA) and identifying where and what are the critical processing latency contributors for such design. Our paper addresses these problems. We study the internal mechanisms and interactions of MMA and controller, to determine the contributors to the overall processing latency. We implemented two MMA solutions (based on reactive and proactive designs) as modules of Floodlight, and we run experiments using Mininet and OpenFlow. The proactive MMA design can guarantee that the overall processing latency in the 95th percentile can be kept near the median value, given available CPU capacity at the SDN controller. One key lesson learned with our study is that only optimizing control signaling of MMA is not enough to provide better overall processing latency.

Online video streaming through mobile devices has become extremely popular nowadays. YouTube, for example, reported that the percentage of its traffic streaming to mobile devices has soared from 6% to more than 40% over the past two years. Moreover, people are constantly seeking to stream high-quality videos for better experience while often suffering from limited bandwidth. With the rapid deployment of content delivery networks, popular videos are now replicated at different sites, and users can stream over-the-top videos from close-by sources with low latency. Aggregating bandwidth for high definition video streaming has become possible as mobile devices, nowadays, are equipped with multiple wireless interfaces (e.g., WiFi and 3G/4G). We propose a client-based video streaming solution, MSPlayer, that takes advantage of multiple video sources and leverages multiple network paths through different interfaces. MSPlayer reduces start-up latency and provides robust data transport with high video quality in mobile scenarios. We experimentally demonstrate our solution on a test bed and through the YouTube video service.

Online video streaming through mobile devices has become extremely popular nowadays. YouTube, for example, reported that the percentage of its traffic streaming to mobile devices has soared from 6% to more than 40% over the past two years. Moreover, people are constantly seeking to stream high quality video for better experience while often suffering from limited bandwidth. Thanks to the rapid deployment of content delivery networks (CDNs), popular videos are now replicated at different sites, and users can stream videos from close-by locations with low latencies. As mobile devices nowadays are equipped with multiple wireless interfaces (e.g., WiFi and 3G/4G), aggregating bandwidth for high definition video streaming has become possible.

In asymptotic regimes, both in time and space (network size), the derivation of network capacity results is grossly simplified by brushing aside queueing behavior in nonJackson networks. This simplifying double-limit model, however, lends itself to conservative numerical results in finite regimes. To properly account for queueing behavior beyond a simple calculus based on average rates, we advocate a system theoretic methodology for the capacity problem in finite time and space regimes. This methodology also accounts for spatial correlations arising in networks with CSMA/CA scheduling and it delivers rigorous closed-form capacity results in terms of probability distributions. Unlike numerous existing asymptotic results, subject to anecdotal practical concerns, our transient results can be used in practical settings, e.g., to compute the time scales at which multi-hop routing is more advantageous than single-hop routing.

Today, most devices have multiple network interfaces. Coupled with wide-spread replication of popular content at multiple locations, this provides substantial path diversity in the Internet. We propose Multi-source Multipath HTTP, mHTTP, which takes advantage of all existing types of path diversity in the Internet. mHTTP needs only client-side but not server-side or network modifications as it is a receiver-oriented mechanism. Moreover, the modifications are restricted to the socket interface. Thus, no changes are needed to the applications or to the kernel.

Many scientific disciplines rely on "Experimental Design" to study various types of systems. Experimental design refers to a planned approach to experimentation that tries to provide statistical evidence to the outcome of experiments. The networking community rarely relies on such approaches, especially for real protocol implementations. Many improvements to protocols like TCP, including the recently proposed Multipath TCP, have been evaluated by considering a relatively limited set of simulations or experiments. Multipath TCP increases the goodput of a data transfer by simultaneously using multiple interfaces. It also improves load balancing thanks to dedicated congestion control. By applying experimental design, we conduct a large set of measurements inside Mininet with the Linux kernel Multipath TCP implementation, to measure its bandwidth aggregation and load balancing. Thanks to the experimental design approach, we are able to highlight several limitations of this implementation. We identify heuristics that lead to lower than expected performance and propose improvements.

In today's Internet, almost all end devices have multiple interfaces built in. This enables users to seamlessly switch between different access networks or even use them simultaneously; to better use the resources available to them and to better satisfy their needs. This is referred to as mobile data offloading and has received lots of attention recently in both the research community and in the industry. However, all the proposed data solutions either rely on static configuration policies or are reactive rather than proactive with regards to the application needs.

With the popularity of mobile devices and the pervasive use of cellular technology, there is widespread interest in hybrid networks and on how to achieve robustness and good performance from them. As most smart phones and mobile devices are equipped with dual interfaces (WiFi and 3G/4G), a promising approach is through the use of multi-path TCP, which leverages path diversity to improve performance and provide robust data transfers. In this paper we explore the performance of multi-path TCP in the wild, focusing on simple 2-path multi-path TCP scenarios. We seek to answer the following questions: How much can a user benefit from using multi-path TCP over cellular and WiFi relative to using the either interface alone? What is the impact of flow size on average latency? What is the effect of the rate/route control algorithm on performance? We are especially interested in understanding how application level performance is affected when path characteristics (e.g., round trip times and loss rates) are diverse. We address these questions by conducting measurements using one commercial Internet service provider and three major cellular carriers in the US.

Multipath TCP (MPTCP) has been proposed recently as a mechanism for transparently supporting multiple connections to the application layer. It is under discussion at the IETF. We nevertheless demonstrate that the current MPTCP suffers from two problems: P1) Upgrading some TCP users to MPTCP can reduce the throughput of others without any benefit to the upgraded users, which is a symptom of not being Pareto-optimal; and P2) MPTCP users could be excessively aggressive toward TCP users. We attribute these problems to the linked-increases algorithm (LIA) of MPTCP and, more specifically, to an excessive amount of traffic transmitted over congested paths. The design of LIA forces a tradeoff between optimal resource pooling and responsiveness. We revisit the problem and show that it is possible to provide these two properties simultaneously. We implement the resulting algorithm, called the opportunistic linked-increases algorithm (OLIA), in the Linux kernel, and we study its performance over our testbed by simulations and by theoretical analysis. We prove that OLIA is Pareto-optimal and satisfies the design goals of MPTCP. Hence, it can avoid the problems P1 and P2. Our measurements and simulations indicate that MPTCP with OLIA is as responsive and nonflappy as MPTCP with LIA and that it solves problems P1 and P2.

MPTCP has been proposed recently as a mechanism for supporting transparently multiple connections to the application layer. It is under discussion at the IETF. We show, however, that the current MPTCP suffers from two problems: (P1) Upgrading some TCP users to MPTCP can reduce the throughput of others without any benefit to the upgraded users, which is a symptom of not being Pareto-optimal; and (P2) MPTCP users could be excessively aggressive towards TCP users. We attribute these problems to the linked-increases algorithm (LIA) of MPTCP and, more specifically, to an excessive amount of traffic transmitted over congested paths.

Neighbor discovery is essential for the process of self-organization of a wireless network, where almost all routing and medium access protocols need knowledge of one-hop neighbors. In this paper we study the problem of neighbor discovery in a static and synchronous network, where time is divided into slots, each of duration equal to the time required to transmit a hello message, and potentially, some sort of feedback message. Our main contributions lie in detailing the physical layer mechanism for how nodes in receive mode detect the channel status, describing algorithms at higher layers that exploit such a knowledge, and characterizing the significant gain obtained. In particular, we describe one possible physical layer architecture that allows receivers to detect collisions, and then introduce a feedback mechanism that makes the collision information available to the transmitters. This allows nodes to stop transmitting packets as soon as they learn about the successful reception of their discovery messages by the other nodes in the network. Hence, the number of nodes that need to transmit packets decreases over time. These nodes transmit with a probability that is inversely proportional to the number of active nodes in their neighborhood, which is estimated using the collision information available at the nodes. We show through analysis and simulations that our algorithm allows nodes to discover their neighbors in a significantly smaller amount of time compared to the case where reception status feedback is not available to the transmitters.

Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical {\em Coupon Collector's Problem}. Consequently, we show that each node discovers all its $n$ neighbors in an expected time equal to $ne (\ln n + c)$, for some constant $c$. When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a $\ln n$ improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing $n$ results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase.

In many wired and wireless networks, nodes process input traffic to satisfy a network constraint (e.g., a capacity constraint) and to increase the utility of data in the output flows given these constraints. In this paper we focus on the special case in which data processing is applied to satisfy capacity constraints. This occurs when the sum of the rate of the input traffic at a node exceeds the sum of the capacity of its output links, or in a more general case, when the sum of the input rates is larger than any cut capacity in the network. In this case, nodes process data to decrease the output flow rate. This decrease from input rate to output rate distorts the transmitted data, which we characterize by a distortion metric. We show that the distortion cost of distributively processing input traffic in a network can be written as the sum of the distortion at individual nodes.. We present a distributed algorithm for a data-gathering network with many sources and a data sink that routes traffic and performs in-network data processing to minimize the distortion cost. In this algorithm, each node determines its routing table based on gradient information from neighboring nodes.

Many sensing systems remotely monitor/measure an environment at several sites, and then report these observations to a central site. We propose and investigate several practical algorithms for joint routing and compression of data files as they are forward from remote nodes to a central site, with the goal of minimizing the communication cost incurred. Our algorithms are practical in that they do not assume that nodes have a priori information about the correlation structure (and resulting compression gains) of the individual measurements at a given sensor or among multiple sensors. Instead, this correlation structure is learned as pieces of the files are routed and jointly compressed on their way to the sink, and routes are adaptively changed as the nodes learn more about the correlation structure of the data.

In this paper our recent results in the capacity of single relay erasure channels are used to derive a new and tighter cut-set bound. We initially present a simple and intuitive approach to derive the classical cut-set bound in general multi-terminal erasure channels. This derivation shows that attaining the bound supposes that a full level of collaboration exists between nodes in the channel. However under some scenarios the full collaboration is not possible. We thereafter use a bounding technique based on reducing every cut-set in a general multi-terminal erasure channel to a single relay super-channel consisting of super nodes. We show that if a rate setting is not achievable over the single relay super-channel it could not then achieved over the general multi-terminal erasure channel. This led us to a tighter cut-set type of bound for general multi-terminal erasure channel

We consider here a single sender-destination multi-relay channel. The links connecting the nodes are supposed to be erasure where symbols are received correctly without any error, or lost. We consider that the nodes are not able to use any interference cancellation mechanism. The interference might be suppressed through using separated physical channel or thought a time-sharing mechanism. This model is realistic for many practical scenarios in the context of wireless networks. In previous works, the capacity region of broadcast erasure channels as well as the capacity of the single-sender relay channel (under degraded and non-degraded hypothesis) has been derived. This paper extends the previous results to the more general case of multi-relay channels. We derive the cut-set bound for a general (stationary ergodic) multi-relay erasure channel, and we show that it can be reached through a practical linear coding scheme based on MDS codes.

Wireless networks consist of senders, receivers, and intermediate nodes collaborating (more or less) to establish the communication paths. Most of the researches in the domain of wireless network have focused on routing based approaches. In such an approach, wireless network is reduced to a dynamic graph, and a minimum cost routing mechanism is applied. These approaches have led to several routing mechanisms as OLSR and AODV. However, the fundamental nature of wireless network is the broadcast. In the wireless network, all the tuned receivers potentially receive every transmission. This basic property is not well captured by graph-based approaches where packets follow a single path from sender to receiver. In this paper we propose a relaying scheme for wireless multi-hop networks. It is based on collaboration of intermediate relays at network layer to forward useful side information in place of forwarding packets. In our scheme we assume that the nodes are not able to benefit from any interference cancellation mechanism. The channels from sender to relay nodes and from sender to receiver are logically separated through a temporal scheduling. This model is realistic for many practical scenarios in the context of wireless networks. We show in this paper the information theoretic bounds and show that they are achievable using practical codes. The proposed coding scheme is simulated in realistic scenarios. The obtained results show a remarkable improvement in throughput, relay load and reliability compared to network using classical routing approach.