Peering between Internet Service Providers (ISPs) is playing an increasingly critical role in Internet traffic exchange. As content delivery networks continue to expand, major content ISPs are increasingly opting for peering arrangements over transit services to facilitate faster exchange of traffic. The satisfaction of the ISP pair and the longevity of the peering arrangement depend on the stability and performance of these peering relationships. We introduce meta-peering, a term which refers to the set of tools needed to help and automate the ISP peering process – starting with identifying a list of ISPs that are likely to peer, writing router rules to establish BGP sessions with them, and extending the service to monitor all these sessions for notifying any major outages or peering agreement violations. In this paper, we first make a thorough analysis of recent trends in ISP peering and describe how meta-peering can be implemented by integrating some of the existing tools. We mainly focus on instrumenting the automation of the peer selection process with an aim to identifying potential peering partners and peering locations to exchange traffic. Using these direct peering links greatly reduces energy consumption as traffic takes much shorter paths to their destinations, going through reduced number of intermediary devices (e.g., routers, switches) compared to elongated transit routes, consequently reducing the environmental impact. Utilizing PeeringDB and CAIDA datasets to identify possible peering points for ISP pairs, we consider ISPs’ internal policies to generate a list of acceptable peering contracts (APCs). We design two methodologies to rank order each ISP in the APC list and offer guidance on which ones would be stable and beneficial for the potential peers. A study of more than 3,000 ISP pairs (mostly active in North America) shows that our peer selection methods can attain around 80% accuracy in predicting peering relations.

Multi-sensor IoT devices often rely on renewable energy and batteries to support diverse field deployments. A device’s sensors use significant energy, so careful energy management is needed to maximize its operating time while meeting application requirements. Model Predictive Control (MPC), a successful energy management technique for other application domains, requires significant computational resources usually not available in typical IoT sensing devices. We develop and evaluate a low-complexity approximation to MPC for IoT device operations powered by renewable (solar) energy, where the approximation is guided by the charging characteristics of real batteries. The complex MPC optimization problem is solved by decomposing it into a time-dependent energy allocation problem and a task-dependent sensor scheduling problem, each of which is solvable with cubic time complexity. We utilize a novel combination of an incremental max-min fair allocation method and a recursive dynamic programming-like procedure. This low-complexity predictive optimization step is integrated with a very simple parabola-based adaptive solar prediction to provide a full system solution, termed Predictive EneRgy Management for IoT (PERMIT) , that can be implemented in lightweight IoT devices. PERMIT is evaluated through experiments on a solar-powered Raspberry Pi device with multiple sensors. We also complement our evaluations with simulations based on real device data traces. Results show that PERMIT’s low-complexity algorithm approximates the exact MPC solution very closely. PERMIT also performs significantly better than Signpost, a comparable IoT energy management solution.

Deep neural networks (DNNs) have made significant strides in tackling challenging tasks in wireless systems, especially when an accurate wireless model is not available. However, when available data is limited, traditional DNNs often yield subpar results due to underfitting. At the same time, large language models (LLMs) exemplified by GPT-3, have remarkably showcased their capabilities across a broad range of natural language processing tasks.But whether and how LLMs can benefit challenging non-language tasks in wireless systems is unexplored.In this work, we propose to leverage the in-context learning ability (a.k.a. prompting) of LLMs to solve wireless tasks in the low data regime without any training or fine-tuning, unlike DNNs which require training. We further demonstrate that the performance of LLMs varies significantly when employed with different prompt templates. To solve this issue, we employ the latest LLM calibration methods. Our results reveal that using LLMs via ICL methods generally outperforms traditional DNNs on the symbol demodulation task and yields highly confident predictions when coupled with calibration techniques.

We analyze traffic exchange between Internet Service Providers (ISPs) at an Internet Exchange Point (IXP) as a non-cooperative game with ISPs as self-interested agents. Each ISP has the choice of exchanging traffic either using the shared IXP facilities, or outside the IXP – through their transit providers or private peering. We analyze the efficiency (social cost optimality) of the traffic exchange equilibrium at the IXP taking into consideration the congestion cost experienced by the ISPs at the IXP. To model both non-profit and for profit IXPs, we consider several cases, i) where the IXP does not charge any price to ISPs for the traffic exchanged (zero pricing), ii) when it charges a price that is proportional to the aggregate level of congestion at the IXP (proportional pricing), and iii) when it charges a constant price per unit traffic (constant pricing). Further, we also analyze the profit earned by the IXP under these pricing policies, under two different models of the congestion cost (delay) functions. Simulations conducted using data for actual IXPs obtained from PeeringDB demonstrate that the theoretical bounds derived for social cost and profit optimality at equilibrium (measured as the Price of Anarchy) are fairly tight, and correctly capture the performance trends against the variation of key model parameters. Further, the results show that for proportional pricing, there is an operating price range that attains near-optimal social cost and near-optimal IXP profitsimultaneously. We also demonstrate -through both theoretical analysis and simulations -that as compared to zero and constant pricing policies, proportional pricing attains better tradeoff between social cost and IXP profit, and also results in a performance that is more robust to price variations.

In this paper, we present FLASH, a framework which addresses for the first time the central AutoML problem of Combined Algorithm Selection and HyperParameter (HP) Optimization (CASH) in the context of Federated Learning (FL). To limit training cost, FLASH incrementally adapts the set of algorithms to train based on their projected loss rates, while supporting decentralized (federated) implementation of the embedded hyper-parameter optimization (HPO), model selection and loss calculation problems. We provide a theoretical analysis of the training and validation loss under FLASH, and their tradeoff with the training cost measured as the data wasted in training sub-optimal algorithms. The bounds depend on the degree of dissimilarity between the datasets of the clients, a result of FL restriction that client datasets remain private. Through extensive experimental investigation on several datasets, we evaluate three variants of FLASH, and show that FLASH performs close to centralized CASH methods.

The importance of peering in traffic exchange be-tween ISPs is rapidly increasing. With continuing growth in content delivery networks, large content ISPs are becoming increasingly inclined to exchange traffic through peering rela-tionships rather than using transit services. The stability and performance of these peering relationships dictate the satisfaction of the ISP pair and the durability of the peering. Quantification of various parameters that indicate the efficiency of peering contracts is however difficult. From the perspective of any ISP pair, there are two key decisions to be made: whether to peer or not, and at which location(s) to peer. We propose two metrics, peering willingness and peering stability, towards quantifying an ISP’s decision to peer at a location with another ISP, and the stability of that relationship. We compute these metrics using publicly available data to characterize peering relationships for different ISP pair types. We observe that peering between Content and Access ISP pairs results in the most stable and efficient relationship.

We consider a traffic peering game between Internet Service Providers (ISPs) at an Internet Exchange Point (IXP), where each ISP pair has a choice of exchanging traffic through a public IXP switch or sending the traffic through transit providers. We analyze the traffic flow efficiency (measured as social welfare) and the IXP revenue at the equilibrium of this game, as a function of the per-unit price charged by the IXP. We show that there exists a price point at which both social welfare and revenue are high, and the corresponding price-of-anarchy values can be expressed in terms of certain sublinearity measures of the inverse demand curves of the ISPs. Simulations carried out using models based on actual IXP data obtained from PeeringDB demonstrate that the theoretical bounds correctly capture the performance trends against the variation of price, and for a carefully chosen pricing point both social welfare and IXP revenue are within a factor of two of the corresponding optimal values.

We consider the problem of video caching across a set of 5G small-cell base stations (SBS) connected to each other over a high-capacity short-delay back-haul link, and linked to a remote server over a long-delay connection. Even though the problem of minimizing the overall video delivery delay is NP-hard, the Collaborative Caching Algorithm (CCA) that we present can efficiently compute a solution close to the optimal, where the degree of sub-optimality depends on the worst case video-to-cache size ratio. The algorithm is naturally amenable to distributed implementation that requires no explicit coordination between the SBSs, and runs in O(N + K log K) time, where N is the number of SBSs (caches) and K the maximum number of videos. We extend CCA to an online setting where the video popularities are not known a priori but are estimated over time through a limited amount of periodic information sharing between the SBSs. We demonstrate that our algorithm closely approaches the optimal integral caching solution as the cache size increases. Moreover, via simulations carried out on real video access traces, we show that our algorithm effectively uses the SBS caches to reduce the video delivery delay and conserve the remote server’s bandwidth, and that it outperforms two other reference caching methods adapted to our system setting.

Constrained Application Protocol (CoAP) and Message Queue Telemetry Transport (MQTT) are two IoT application layer protocols that are seeing increased attention and industry deployment. CoAP uses a request-response model and runs over UDP, while MQTT follows a publish-subscribe model running over TCP. For more constrained IoT devices, MQTTSensor Networks (MQTT-SN) provides a UDP-based transport between the sensor and an MQTT-SN gateway, while using TCP between that gateway and the MQTT broker. Quick UDP Internet Connections (QUIC) is a new protocol and although not originally designed for IoT devices, some design features such as reduced connection establishment time may be useful in an IoT environment. Each of these protocols seeks optimizations in features and implementation complexity based on application domains rather than having the full flexibility and adaptability of traditional transport protocols such as TCP. We investigate and analyze four protocols, namely, CoAP, MQTT, MQTT-SN and QUIC, to understand the overhead of obtaining data from an IoT device at a sink to potentially disseminate this data downstream. These constrained IoT devices often operate under challenging, varying network conditions, and it is important to understand the limitations of the protocols in such conditions. Thus, we evaluate the performance of these protocols under varying loss, delay and disruption conditions to identify the most effective environment for their operation and understand the limitations of their dynamic range. Results show that with non-confirmable CoAP a more adaptive wait timer is required; and a more streamlined QUIC protocol may be a potential alternative IoT protocol.

In this work we present a trust computation method, Direct Trust Computation, and utilize it to design a Reputation Routing Model (RRM) for MANETs. We utilize this routing framework to mitigate the effect of blackhole attacks in OLSR without altering the original protocol or increasing its overhead. Our solution can isolate bad nodes in the network and select the most trusted path to route packets. We evaluate the performance of our model by emulating network scenarios on Common Open Research Emulator (CORE) for static as well as dynamic topologies. From our findings, it is observed that RRM substantially outperforms the original OLSR protocol in terms of packet delivery rates in presence of a malicious node, unless the mobility rate is quite high. RRM is therefore useful in mitigating the effect of blackhole attacks in MANETs, particularly in low mobility scenarios.

Multiple description coding has been shown to provide flexible and distortion-rate optimal video streaming transmission over lossy links. In this paper, we provide an adaptive MD-FEC algorithm for point-to-multipoint video streaming that approximately minimizes the average distortion of the multicast video. Our new algorithm accomplishes this by adapting both the packet lengths and their number to fit heterogeneous link conditions.

In this work we present the design and evaluation of two high performance mass configuration protocols, focusing on efficiency and reliability, for wireless Mobile Ad-hoc Networks (MANETs) utilizing an Efficient Broadcast Module (EBM). MCONF, which was developed in an earlier work, enables mass configuration changes in a MANET using multiple modes of operation based on the underlying network scenario. However, MCONF relies on classic flooding approach to disseminate configuration changes and gather feedback information to/from nodes. In this paper we propose: S-MCONF - a Simple Mass Configuration protocol focusing on efficiency, and E-MCONF - an Efficient Mass Configuration protocol focusing on reliability. Both of these are developed based on MCONF while utilizing underlying efficient broadcasting framework that computes a Minimum Connected Dominating Set (MCDS) to forward messages in a MANET. Our proposed S-MCONF and E-MCONF protocols utilize three different relay selection algorithms, namely Essential Connecting Dominating Set (E-CDS), Source based MultiPoint Relay (S-MPR) and Non-source specific MultiPoint Relay (NS-MPR), to optimize performance. We evaluate the performance of our S-MCONF and E-MCONF protocols by emulating MANET on Common Open Research Emulator (CORE) for dynamic topologies based on mobility of nodes. Performance is measured in terms of reliability and packet redundancy. Based on our findings as part of the study, it is observed that S-MCONF is very well suited for low node mobility scenarios in the MANETs. On the other hand, E-MCONF provides reliability of packet delivery in MANETs even for high node mobility scenarios. Both S-MCONF and E-MCONF are able to improve their packet efficiency significantly at low mobility as compared to MCONF protocol.

Caching has been shown to enhance network performance. In this paper, we study fine-grain scalable video caching. We start from a single cache scenario by providing a solution to the caching allocation problem that optimizes the average expected video quality for the most popular video clips. Actual trace data is applied to verify the performance of our algorithm and compare its backhaul link bandwidth consumption relative to non-scalable video caching. In addition, we extend our analysis to collaborative caching and integrate network coding for further transmission efficiency. Our experimental results demonstrate considerable performance enhancement.

Buildings with shared spaces such as corporate office buildings, university dorms, etc., are occupied by multiple occupants who typically have different temperature preferences. Attaining a common temperature set-point that is agreeable to all users (occupants) in such a multi-occupant space is a challenging problem. Furthermore, the ideal temperature set-point should optimally trade off the building energy cost with the aggregate discomfort of all the occupants. However, the information on the comfort range (function) is held privately by each occupant. Using occupant-differentiated dynamically-adjusted penalty factor as feedback signals, we propose a distributed solution which ensures that a consensus is attained among all occupants upon convergence, irrespective of their ideal temperature preferences being in coherence or conflicting. Occupants are only assumed to be rational, in that they choose their own temperature set-points so as to minimize their individual energy cost plus discomfort. We establish the convergence of the proposed algorithm to the optimal temperature set-point vector that minimizes the sum of the energy cost and the aggregate discomfort of all occupants in a multizone building. Simulations with realistic parameter settings illustrate validation of our theoretical claims and provide insights on the dynamics of the system with a mobile user population.

In this paper, we formulate and study a capacity allocation game between a set of receivers (players) that are interested in receiving multicast data (video/multimedia) being streamed from a server through a multihop network. We consider fractional multicast streaming, where the multicast stream from the source (origin-server) to any particular receiver (end-user) can be split over multiple paths. The receivers are selfish and noncooperative, but must collaboratively purchase capacities of links in the network, as necessary for delivery of the multicast stream from the source to the individual receivers, assuming that the multicast stream is network-coded. For this multicast capacity allocation (network formation) game, we show that the Nash equilibrium is guaranteed to exist in general. For a 2-tier network model where the receivers must obtain the multicast data from the source through a set of relay nodes, we show that the price of stability is at most 2, and provide a polynomial-time algorithm that computes a Nash equilibrium whose social cost is within a factor of 2 of the socially optimum solution. For more general network models, we show that there exists a 2-approximate Nash equilibrium, whose cost is at most two times the social optimum. We also give a polynomial-time algorithm that computes a (2+∈)-approximate Nash equilibrium for any ∈ > 0, whose cost is at most two times the social optimum. Simulation studies show that our algorithms generate efficient Nash equilibrium allocation solutions for a vast majority of randomly generated network topologies.

We consider the contract-switching paradigm for studying the inter-domain traffic engineering problem. In the contract-switching paradigm, each ISP in the Internet is abstracted as a set of edge-to-edge contract links. We formulate the optimal routing problem for the contract-switching paradigm by considering three objectives, namely: 1) maximizing throughput, 2) minimizing delay, and 3) minimizing bandwidth usage. We solve the optimization problems on realistic network topologies and show that the routing solutions developed using the contract-switching paradigm provides significant improvement in performance compare to the BGP routing framework with respect to the three objectives. Moreover, our simulation study also reveals that the contract-switching paradigm performs close to the best performance that can be achieved in the Internet in the absence of any abstractions.

We address the question of strategic pricing of inter-domain traffic forwarding services provided by ISPs, which is also closely coupled with the question of how ISPs route their traffic towards their neighboring ISPs. Posing this question as a non-cooperative game between neighboring ISPs, we study the properties of this pricing game in terms of the existence and efficiency of the equilibrium. We observe that for "well-provisioned" ISPs, Nash equilibrium prices exist and they result in flows that maximize the overall network utility (generalized end-to-end throughput). For general ISP topologies, equilibrium prices may not exist; however, simulations on a large number of realistic topologies show that best-response based simple price update solutions converge to stable and efficient prices and flows for most topologies.

Multiple Description with Forward Error Correction (MD-FEC) coding provides the flexibility, easy adaptivity and distortion-rate optimality that are desirable for delivering streaming video in a network environment with time-varying bandwidth fluctuations and random packet losses. In this paper, we consider the issue of how diverse receivers of a video stream should be grouped - where each group receives a MD-FEC coded bitstream optimized for that group - so that the average video distortion is minimized across all receivers. We show that a sequential grouping solution is optimal for linear distortion-rate functions. For non-linear distortion-rate functions, while the optimal grouping structure may not be sequential in general, we observe that the approximation factor attained by the best sequential solution can be characterized in terms of the “degree of convexity” of the distortion-rate function. Numerical experiments with realistic distortion-rate functions reveal that the difference between the globally optimal grouping solution and the best sequential solution, is typically small. We provide a dynamic programming based polynomial-time algorithm to compute the best sequential solution.

Wireless networks (including wireless mesh networks) provide opportunities for using multiple paths. Multihoming of hosts, possibly using different technologies and providers, also makes it attractive for end-to-end transport connections to exploit multiple paths. In this paper, we propose a multipath transport protocol, based on a carefully crafted set of enhancements to TCP, that effectively utilizes the available bandwidth and diversity provided by heterogeneous, lossy wireless paths. Our Multi-Path LOss-Tolerant (MPLOT) transport protocol can be used to obtain significant goodput gains in wireless networks, subject to bursty, correlated losses with average loss rates as high as 50%. MPLOT is built around the principle of separability of reliability and congestion control functions in an end-to-end transport protocol. Congestion control is performed separately on individual paths, and the reliability mechanism works over the aggregate set of paths available for an end-to-end session. MPLOT distinguishes between congestion and link losses through Explicit Congestion Notification (ECN), and uses Forward Error Correction (FEC) coding to recover from data losses. MPLOT uses a dynamic packet mapping based on the current path characteristics to choose a path for a packet. Use of erasure codes and block-level recovery ensures that in MPLOT the receiving transport entity can recover all data as long as a necessary number of packets in the block are received, irrespective of which packets are lost. We present a theoretical analysis of the different design choices of MPLOT and show that MPLOT chooses its policies and parameters such that a desirable tradeoff between goodput with data recovery delay is attained. We evaluate MPLOT, through simulations, under a variety of test scenarios and demonstrate that it effectively exploits path diversity in addition to efficiently aggregating path bandwidths while remaining fair to a conventional TCP flow on each path.

We address the joint channel assignment and power allocation question in a multichannel wireless (access point) network where channel states differ across channels as well as users, and vary with time. Our goal is to obtain channel assignment and power allocation solutions that can dynamically adapt to changing channel conditions, and would maximize system throughput under per-user bandwidth (QoS) constraints, in a long-term sense. Using stochastic optimization techniques, we obtain an optimal scheduling policy that operates without knowledge of arrival rates and channel statistics (depending only on the instantaneous channel states and the queue lengths), and attains the overall system throughput that is arbitrarily close to the maximum achievable value with all per-user bandwidth constraints satisfied.

In this paper, we address the spectrum portfolio optimization (SPO) question in the context of secondary spectrum markets, where bandwidth (spectrum access rights) can be bought in the form of primary and secondary contracts. While a primary contract on a channel provides guaranteed access to the channel bandwidth (possibly at a higher per-unit price), the bandwidth available to use from a secondary contract (possibly at a discounted price) is typically uncertain/stochastic. The key problem for the buyer (service provider) in this market is to determine the amount of primary and secondary contract units needed to satisfy uncertain user demand. We initially consider a single-region problem in which the spectrum contracts are valid only in the single-region in which the buyer wishes to provide service. We formulate the problem as one of minimizing the cost of the spectrum portfolio subject to constraints on bandwidth shortage. Two different forms of bandwidth shortage constraints are considered, namely, the demand satisfaction rate constraint, and the demand satisfaction probability constraint. While the SPO problem under demand satisfaction rate constraint is shown to be convex for all density functions, the SPO problem under demand satisfaction probability constraint is not convex in general. We derive some sufficient conditions for convexity for this case. The SPO problems can therefore be solved efficiently using standard convex optimization techniques. Later, we extend the problem formulation and the convexity results to the multiple-region setting, where the buyer's portfolio is intended to serve a set of disjoint geographical locations, each having its own customer demand. Finally, we perform a thorough simulation-based study of the single-region and the multiple-region problems for different choices of the problem parameters, and provide key insights regarding the portfolio composition and demonstrate the convexity of the efficient frontier. We provide several insights about the scaling behavior of the unit prices of the secondary contracts, as the stochastic characterization of the bandwidth available from secondary contracts change.

We provide a formal model for the Change Management process for Enterprise IT systems, and develop change scheduling algorithms that seek to attain the "change capacity" of the system. The change management process handles critical updates in the system that often use overlapping sets of servers, resulting in scheduling conflicts between the corresponding change classes. Furthermore, applications are typically associated with certain permissible downtime windows, which impose constraints on the timing of the change executions. Scheduling of changes for such systems represent a complex dynamic optimization question. In a limiting fluid regime, where changes are assumed nonatomic, we develop a scheduling policy that provably attains the change capacity of the system. We then propose and evaluate an atomic approximation of the optimal fluid scheduling policy, which is well suited for application to a real change management system. Simulation results demonstrate that the expected change execution delay and the capacity attained by the approximate policy is close to the best attainable values, when unavoidable capacity losses due to fragmentation effects are taken into account and is significantly better than a randomized scheduling policy.

We consider the question of obtaining tight delay guarantees for throughout-optimal link scheduling in arbitrary topology wireless ad-hoc networks. We consider two classes of scheduling policies: 1) a maximum queue-length weighted independent set scheduling policy, and 2) a randomized independent set scheduling policy where the independent set scheduling probabilities are selected optimally. Both policies stabilize all queues for any set of feasible packet arrival rates, and are therefore throughput-optimal. For these policies and i.i.d. packet arrivals, we show that the average packet delay is bounded by a constant that depends on the chromatic number of the interference graph, and the overall load on the network. We also prove that this upper bound is asymptotically tight in the sense that there exist classes of topologies where the expected delay attained by any scheduling policy is lower bounded by the same constant. Through simulations we examine the scaling of the average packet delay with respect to the overall load on the network, and the chromatic number of the link interference graph.

Sensor networks have major applications in environmental monitoring, relief operations, surveillance, health-care and defense. Future sensor networks would comprise of sensing devices with energy harvesting capabilities from renewable energy sources such as solar power. Multiple sensor nodes deployed in the region of interest would collaborate to achieve a global objective, such as detection of application specific events. This paper focuses on the design of efficient algorithms for multi-sensor activation in order to optimize the overall event detection probability. The recharge-discharge dynamics of the individual rechargeable sensor nodes, along with temporally correlated nature of event occurrences makes the optimal multi-sensor event detection question very challenging. We formulate the dynamic multi-sensor event detection question in a stochastic optimization framework, and design efficient sensor activation algorithms. Particularly, we analyze certain classes of threshold activation policies and show that they achieve near-optimal performance when the threshold is chosen carefully. Specifically, we show that a time-invariant threshold policy, which attempts to maintain a fixed number (appropriately chosen) of sensors active at all times, is optimal in absence of temporal correlations. Moreover, the same energy-balancing time-invariant threshold policy approaches optimality in presence of temporal correlations as well, albeit under certain limiting assumptions. Through simulation studies, we compare the performance of this time-invariant policy with energy-balancing correlation-dependent policies, and observe that although the latter perform better, the performance difference is rather small.

We consider the joint scheduling and power allocation problem for uplink transmissions in a multichannel access point network, and develop solutions to achieve the maximum system throughput under QoS constraints for each user. In this frame-based multi-channel OFDM system, our goal is to determine when in the frame and on which channels each user should transmit, and how the power of each user should be split across the channels it uses. Our goal is to maximize the overall effective data rate in the network, taking into account variations in channel rates across channels as well as users, while satisfying minimum rate constraints for each user. Although this problem is in general a complex non-linear mixed-integer optimization question, we show that the optimal schedule and power allocation can be computed in polynomial time under a high SINR approximation. Finally we propose and evaluate several simple heuristics for this problem, and show that some of these attain a performance that is very close to the optimum, at fairly low computational cost.

We propose a novel transport protocol that effectively utilizes available bandwidth and diversity gains provided by heterogeneous, highly lossy paths. Our Multi-Path LOss-Tolerant (MPLOT) protocol can be used to provide significant gains in the goodput of wireless mesh networks, subject to bursty, correlated losses with average loss-rates as high as 50%, and random outage events. MPLOT makes intelligent use of erasure codes to guard against packets losses, and a Hybrid-ARQ/FEC scheme to reduce packet recovery latency, where the redundancy is adaptively provisioned into both proactive and reactive FECs. MPLOT uses dynamic packet mapping based on current path characteristics, and does not require packets to be delivered in sequence to ensure reliability. We present a theoretical analysis of the different design choices of MPLOT and show that MPLOT makes an optimal trade-off between goodput and delay constraints. We test MPLOT, through simulations, under a variety of test scenarios and show that it effectively exploits path diversity in addition to aggregating path bandwidths. We also show that MPLOT is fair to single-path protocols like TCP-SACK.

Despite the huge success of the Internet in providing basic communication services, the Internet architecture needs to be upgraded so as to provide end-to-end QoS services to its customers. Currently, a user or an enterprise that needs end-to-end bandwidth guarantees between two arbitrary points in the Internet for a short period of time has no way of expressing its needs. To allow these much needed basic QoS services, we propose a single-domain edge-to-edge (g2g) dynamic capacity contracting mechanism, where a network customer can enter into a bandwidth contract on a g2g path at a future time, at a predetermined price. For practical and economic viability, such forward contracts must involve a bailout option to account for bandwidth becoming unavailable at service delivery time, and must be priced appropriately to enable ISPs manage risks in their contracting and investments. Our design allows ISPs to advertise point-to-point different prices for each of their g2g paths instead of the current point-to-anywhere prices, allowing for better end-to-end paths, temporal flexibility and efficiency of bandwidth usage. We compute the risk-neutral prices for these g2g bailout forward contracts (BFCs), taking into account correlations between different contracts due to correlated demand patterns and overlapping paths. We implement this multiple g2g BFC framework on a realistic network model with Rocketfuel topologies, and evaluate our contract switching mechanism in terms of key network performance metrics like fraction of bailouts, revenue earned by the provider, and adaptability to link failures.

The question of providing throughput guarantees through distributed scheduling, which has remained an open problem for some time, is addressed in this paper. It is shown that a simple distributed scheduling strategy, maximal scheduling, attains a guaranteed fraction of the maximum throughput region in arbitrary wireless networks. The guaranteed fraction depends on the ldquointerference degreerdquo of the network, which is the maximum number of transmitter-receiver pairs that interfere with any given transmitter-receiver pair in the network and do not interfere with each other. Depending on the nature of communication, the transmission powers and the propagation models, the guaranteed fraction can be lower-bounded by the maximum link degrees in the underlying topology, or even by constants that are independent of the topology. The guarantees are tight in that they cannot be improved any further with maximal scheduling. The results can be generalized to end-to-end multihop sessions. Finally, enhancements to maximal scheduling that can guarantee fairness of rate allocation among different sessions, are discussed.

We address the problem of optimal node activation in a sensor network, where the optimization objective is represented as a global time-average utility function over the deployment area of the network. Each sensor node is rechargeable, and can hold up toKquanta of energy. When the recharge and/or discharge processes in the network are random, the problem of optimal sensor activation is a complex stochastic decision question. For the case of identical sensor coverages, we show the existence of a simplethreshold policywhich isasymptotically optimalwith respect to the energy bucket sizeK, that is, the performance of this threshold policy approaches the optimal performance asKbecomes large. We also show that the performance of the optimal threshold policy is robust to the degree of spatial correlation in the discharge and/or recharge processes. We then extend this approach to a general sensor network where coverage areas of different sensors could have complete, partial or no overlap with each other. We demonstrate through simulations that a local information based threshold policy, with an appropriately chosen threshold, achieves a performance which is very close to the global optimum.

We consider the problem of uplink/downlink scheduling in a multichannel wireless access point network where channel states differ across channels as well as users, vary with time, and can be measured only infrequently. We demonstrate that, unlike infrequent measurement of queue lengths, infrequent measurement of channel states reduce the maximum attainable throughput. We then prove that in frequency division multiplexed systems, a dynamic scheduling policy that depends on both the channel rates (averaged over the measurement interval) and the queue lengths, is throughput optimal. We also generalize the scheduling policy to solve the joint power allocation and scheduling problem. In addition, we provide simulation studies that demonstrate the impact of the frequency of channel and queue state measurements on the average delay and attained throughput.

A radio frequency identifier (RFID) system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. In this paper we, therefore, address this load balancing problem for readers - given a set of tags that are within range of each reader, which of these tags should each reader be responsible for such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. We show that a generalized variant of the load balancing problem is NP-hard and hence present a 2-approximation centralized algorithm. We next present an optimal centralized solution for a specialized variant. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.

We consider the problem of uplink/downlink scheduling in a multichannel wireless access point network where channel states differ across channels as well as users, vary with time, and can be measured only infrequently. We demonstrate that, unlike the infrequent measurement of queue lengths, infrequent measurement of channel states reduce the maximum attainable throughput. We then prove in frequency division multiplexing systems, a dynamic scheduling policy that depends on both the channel rates (averaged over the measurement interval) and the queue lengths, attains the maximum possible throughput. We also generalize the scheduling policy to solve the joint power allocation and scheduling problem in orthogonal frequency division multiplexing systems. In addition, we provide simulation studies that demonstrate the impact of the frequency of channel and queue state measurements on the average delay and attained throughput.

We consider the uplink channel assignment problem in a multi-channel access point wireless network, with the goal of attaining maximum system throughput. In this setup, a set of orthogonal channels must be assigned to a set of users, where each user splits its power optimally across the channels allocated to it. While the optimal power allocation solution has a "water-filling" type structure, the optimal channel assignment problem is very challenging due to the non-linear dependence of user throughput on the set of channels assigned to it. Since the optimal channel allocations is computationally intensive to obtain in general, we analyze the system in the two extremal SINR regimes (very high and very low SINR) and show how the optimal solutions can be obtained in these regimes in a computationally efficient manner. Finally, we demonstrate that the best of the optimal solutions obtained for the two extremes shows excellent (close to optimal) performance over the entire SINR range.

We investigate the fairness and throughput properties of a simple distributed scheduling policy, maximal scheduling, in the context of a general ad-hoc wireless network. We design a fully distributed algorithm that combines a token generation scheme with maximal scheduling policy so as to attain max-min fair rates within the feasible region of maximal scheduling. We next present throughput guarantees of maximal scheduling that quantify the performance loss of each session due to the use of local information based scheduling. We show that the performance loss for each session depends on the maximum “interference degree” in its neighborhood. We also demonstrate that the performance penalties can not be localized any further.

We analyze the delay performance of multi-channel MAC in point-to-multipoint wireless networks. We focus on contention based operation of nodes in such networks using a multi-channel MAC protocol adapted from Jungmin So et al., (2004). Our analysis can be extended to IEEE 802.11 DCF in PMP mode of operation and contention based IEEE 802.16 based networks. Using a slotted-time model, we derive expressions for the service time distribution of the packets, and approximate expressions for the queuing delay under Poisson traffic, when the contention window is of fixed size. We extend this analysis to incorporate exponential backoff of the contention window size. We conduct simulations for the multichannel MAC protocol in NS-2, and note that our analytical results match well with simulation results for moderate to high values of traffic intensity. Our analysis enables us to capture the imp act of various system parameters on queuing delay

In this paper, we address the rate control problem for layered multicast traffic, with the objective of solving a generalized throughput/fairness objective. Our approach is based on a combination of Lagrangian relaxation and dynamic programming. Unlike previously proposed dual-based approaches, the algorithm presented in this paper scales well as the number of multicast groups in the network increases. Moreover, unlike all existing approaches, our approach takes into account the discreteness of the receiver rates that is inherent to layered multicasting. We show analytically that our algorithm converges and yields rates that are approximately optimal. Simulations carried out in an asynchronous network environment demonstrate that our algorithm exhibits good convergence speed and minimal rate fluctuations

In this paper, we address the rate control problem in a multihop random access wireless network, with the objective of achieving proportional fairness amongst the end-to-end sessions. The problem is considered in the framework of nonlinear optimization. Compared with its counterpart in a wired network where link capacities are fixed, rate control in a multihop random access network is much more complex and requires joint optimization at both the transport and link layers. This is due to the fact that the attainable throughput on each link in the network is "elastic" and is typically a nonconvex and nonseparable function of the transmission attempt rates. Two cross-layer algorithms, a dual-based algorithm and a penalty-based algorithm, are proposed in this paper to solve the rate control problem in a multihop random access network. Both algorithms can be implemented in a distributed manner, and work at the link layer to adjust link attempt probabilities and at the transport layer to adjust session rates. We prove rigorously that the two proposed algorithms converge to the globally optimal solutions. Simulation results are provided in support of our conclusions.

We address the problem of adaptive dimensioning of bandwidth tunnels in a dynamic, real-time traffic environment. We consider a scenario where paths associated with the tunnels are fixed, but the associated bandwidth allocations can be adapted to variations in the incoming traffic. We present an approach for adjusting the tunnel bandwidths incrementally so as to maximize the system throughput. We show, through simulations, that our iterative algorithm converges to the optimal bandwidth allocation for stable traffic patterns. We also demonstrate that our dynamic bandwidth provisioning algorithm significantly outperforms the optimal static bandwidth provisioning policy. Although our policy is incremental in nature and is simple to implement, it yields a performance close to that of the optimal dynamic bandwidth provisioning policy.

In this paper, we address the problem of rate optimization in a multi-hop Aloha network, with the objective of achieving general utility-based fairness amongst the end-to-end flows. A general multi-hop wireless network is considered, where all nodes need not be within transmission range of each other. The rate optimization problem is considered within the framework of nonlinear programming and a cross-layer algorithm is proposed to solve the problem in a distributed manner. The algorithm works at both the link layer to adjust link attempt probabilities and at the transport layer to adjust flow rates. We prove that the algorithm converges to the local optimal solutions. Simulation results show that, when a logarithmic function is used as the utility function to achieve proportional fairness amongst the end-to-end flows, the proposed algorithm converges to the globally optimal solutions in various network scenarios.

We consider a network of rechargeable sensors, deployed redundantly in a random sensing environment, and address the problem of how sensor nodes should be activated dynamically so as to maximize a generalized system performance objective. The optimal sensor activation problem is a very difficult decision question, and under Markovian assumptions on the sensor discharge/recharge periods, it represents a complex semi-Markov decision problem. With the goal of developing a practical, distributed but efficient solution to this complex, global optimization problem, we first consider the activation question for a set of sensor nodes whose coverage areas overlap completely. For this scenario, we show analytically that there exists a simple threshold activation policy that achieves a performance within a factor of 3/4 of the optimum over all possible policies. We extend this threshold policy to a general network setting where the coverage areas of different sensors could have partial or no overlap with each other, and show by simulations that the performance of our policy is very close to that of the globally optimal policy. Our policy is fully distributed, and requires the sensor nodes to only keep track of the node activation states in its immediate neighborhood. We also consider the effects of spatial correlation on the performance of the threshold activation policy, and the choice of the optimal threshold.

In this paper, we consider the throughput modelling and fairness provisioning in CSMA/CA based ad-hoc networks. The main contributions are: firstly, a throughput model based on Markovian analysis is proposed for the CSMA/CA network with a general topology. Simulation investigations are presented to verify its performance. Secondly, fairness issues in CSMA/CA networks are discussed based on the throughput model. The origin of unfairness is explained and the trade-off between throughput and fairness is illustrated. Thirdly, throughput approximations based on local topology information are proposed and their performances are investigated. Fourthly, three different fairness metrics are presented and their distributed implementations, based on the throughput approximation, are proposed.

Tiny, low-cost sensor devices are expected to be failure-prone and hence in many realistic deployment scenarios for sensor networks these nodes are deployed in higher than necessary densities to meet operational goals. In this paper we address the question of how nodes should be managed in such dense sensor deployments so that the network topology formed by the active sensors is able to provide connected-coverage to the entire area of interest and at the same time increase the lifetime of the network. In particular, we propose and study distributed, low-coordination node wakeup schemes to efficiently construct multiple independent (node-disjoint) sensor network topologies to achieve good fault tolerance. We propose and evaluate different distributed, random and pattern-based wakeup policies for sensor nodes to construct connected-covered topologies. Through analysis and simulations we demonstrate that in dense sensor deployment scenarios, these policies can construct near-optimal topologies (within 2.7% of the optimal) with zero coordination between nodes, as long as location information is available at the individual sensor nodes.Based on these observations, we develop and evaluate a few simple distributed, wakeup based topology construction algorithms that can realize similar performance bounds in realistic sensor deployments, with varying node densities. These algorithms differ in terms of the required level of coordination and the use of sensor location information, and generate connected-covered topologies efficiently, with very low message-exchange overhead.

In this paper, we address the rate control problem in a multi-hop random access wireless network, with the objective of achieving proportional fairness amongst the end-to-end sessions. The problem is considered in the framework of nonlinear optimization. Compared to its counterpart in a wired network where link capacities are assumed to be fixed, rate control in a multi-hop random access network is much more complex and requires joint optimization at both the transport layer and the link layer. This is due to the fact that the attainable throughput on each link in the network is `elastic' and is typically a non-convex and non-separable function of the transmission attempt rates. Two cross-layer algorithms, a dual based algorithm and a primal based algorithm, are proposed in this paper to solve the rate control problem in a multi-hop random access network. Both algorithms can be implemented in a distributed manner, and work at the link layer to adjust link attempt probabilities and at the transport layer to adjust session rates. We prove rigorously that the two proposed algorithms converge to the globally optimal solutions. Simulation results are provided to support our conclusions.

This paper presents an overlay architecture where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs are organized into an overlay and act as application-layer multicast forwarding entities for a set of clients. We present a decentralized scheme that organizes the MSNs into an appropriate overlay structure that is particularly beneficial for real-time applications. We formulate our optimization criterion as a "degree-constrained minimum average-latency problem" which is known to be NP-hard. A key feature of this formulation is that it gives a dynamic priority to different MSNs based on the size of its service set. Our proposed approach iteratively modifies the overlay tree using localized transformations to adapt with changing distribution of MSNs, clients, as well as network conditions. We show that a centralized greedy approach to this problem does not perform quite as well, while our distributed iterative scheme efficiently converges to near-optimal solutions.

A new algorithm for routing of messages in ad-hoc networks where the nodes are energy-constrained is presented. The routing objective is to maximize the total number of messages that can be successfully sent over the network without knowing any information regarding future message arrivals or message generation rates. From a theoretical perspective, we show that if admission control of messages is permitted, then the worst-case performance of our algorithm is within a factor of O(log(network size)) of the best achievable solution. In other words, our algorithm achieves a logarithmic competitive ratio. Our approach provides sound theoretical backing for several observations that have been made by previous researchers. From a practical perspective, we show by extensive simulations that the performance of the algorithm is very good even in the absence of admission control (the admission control being necessary only to prove the competitive ratio result), and that it also performs better than previously proposed algorithms for other suggested metrics such as network lifetime maximization. Our algorithm uses a single shortest path computation, and is amenable to efficient implementation. We also evaluate by simulations the performance impact of inexact knowledge of residual battery energy, and the impact of energy drain due to dissemination of residual energy information.

Utilizing optical technologies to build packet fabrics for high-capacity switches and routers has several advantages in terms of scalability, power consumption, and cost. However, several technology related problems have to be overcome to be able to use such an approach. The reconfiguration times of optical crossbars are longer than those of electronic fabrics and end-to-end clock recovery in such systems add to the reconfiguration overheads. Both these problems can limit the efficiency of optical packet fabrics. In addition, existing work on input-buffered switches mostly assumes fixed size packets (referred as envelopes in this paper). When fixed size switching is used for Internet protocol networks where packets are of variable size, the incoming packets need to be fragmented to fit the fixed size envelopes. This fragmentation can lead to, possibly large loss of bandwidth and even instability. This paper addresses all of the above issues by presenting packetization and scheduling techniques that allow optical packet fabrics to be used within switches and routers. The proposed scheme aggregates multiple packets in a single envelope and when used in combination with proper scheduling algorithms, it can provide system stability as well as bandwidth and delay guarantees. As a result of the aggregation method, the reconfiguration frequency required from the optics is reduced, facilitating the use of optical technologies in implementing packet switch fabrics.

Routing with service restorability is of much importance in Multi-Protocol Label Switched (MPLS) networks, and is a necessity in optical networks. For restoration, each connection has an active path and a link-disjoint backup path. The backup path enables service restoration upon active path failure. For bandwidth efficiency, backups may be shared. This requires that at least the aggregate backup bandwidth used on each link be distributed to nodes performing route computations. If this information is not available, sharing is not possible. Also, one scheme in use for restorability in optical networks is for the sender to transmit simultaneously on the two disjoint paths and for the receiver to choose data from the path with stronger signal. This has the advantage of fast receiver-initiated recovery upon failure but it does not allow backup sharing. In this paper, we consider the problem of efficient dynamic routing of restorable connections when backup sharing is not allowed. Our objective is to be able to route as many connections as possible for one-at-a-time arrivals and no knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. We show that by using the minimum-interference ideas used for nonrestorable routing, we can develop efficient algorithms that outperform previously proposed algorithms for restorable routing such as routing with the min-hop like objective of finding two disjoint paths with minimum total hop-count. We present two new and efficient algorithms for restorable routing without sharing, and one of them requires only shortest path computations. We demonstrate that both algorithms perform very well in comparison to previously proposed algorithms.

Routing with service restorability is very important in multiprotocol label switched (MPLS) networks, and is a necessity in optical networks. For restoration, each connection has an active path and a disjoint backup path. The backup path enables service restoration upon active path failure. For bandwidth efficiency, backups may be shared. This requires that at least the aggregate backup bandwidth used on each link be distributed to nodes performing route computations. If this information is not available, sharing is not possible. Also, one scheme in use for restorability in optical networks is for the sender to transmit simultaneously on the two disjoint paths and for the receiver to choose data from the path with stronger signal. This has the advantage of fast receiver-initiated recovery upon failure but it does not allow backup sharing. We consider the problem of efficient dynamic routing of restorable connections when backup sharing is not allowed. Our objective is to be able to route as many connections as possible for one-at-a-time arrivals and no knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. We show that by using the minimum-interference ideas used for non-restorable routing, we can develop efficient algorithms that outperform previously proposed algorithms for restorable routing such as routing with the min-hop like objective of finding two disjoint paths with minimum total hop-count. We present two new and efficient algorithms for restorable routing without sharing, and one of them requires only shortest path computations. We demonstrate that both algorithms perform very well in comparison to previously proposed algorithms.

In multirate multicasting, different users (receivers) within the same multicast group can receive service at different rates, depending on the user requirements and the network congestion level. Compared with unirate multicasting, this provides more flexibility to the user and allows more efficient usage of the network resources. We address the rate control problem for multirate multicast sessions, with the objective of maximizing the total receiver utility. This aggregate utility maximization problem not only takes into account the heterogeneity in user requirements, but also provides a unified framework for diverse fairness objectives. We propose an algorithm for this problem and show, through analysis and simulation, that it converges to the optimal rates. In spite of the nonseparability of the problem, the solution that we develop is completely decentralized, scalable and does not require the network to know the receiver utilities. The algorithm requires very simple computations both for the user and the network, and also has a very low overhead of network congestion feedback.

Multirate multicasting, where the receivers of a multicast group can receive service at different rates, is an efficient mode of data delivery for many real-time applications. We address the problem of achieving rates that maximize the total receiver utility for multirate multicast sessions. This problem not only takes into account the heterogeneity in user requirements, but also provides a unified framework for diverse fairness objectives. We propose two algorithms and prove that they converge to the optimal rates for this problem. The algorithms are distributed and scalable, and do not require the network to know the receiver utilities. We discuss how these algorithms can be implemented in a real network, and also demonstrate their convergence through simulation experiments.

We consider the rate control problem with the objective of maximizing the total user utility. It takes into account the possible differences in user requirements, and also provides a framework for achieving a wide range of fairness objectives. We propose a simple algorithm for achieving the optimal rates for this problem. The algorithm can be implemented in a distributed way and does not require the network to know the user utility functions. In our algorithm, the network communicates to the user the number of congested links on the user's path, and the user (end-host) adjusts its rate accordingly, taking into account its utility function and the network congestion feedback. We show through analysis and experimentation that our algorithm converges to the optimum rates.

This paper presents new algorithms for dynamic routing of bandwidth guaranteed tunnels, where tunnel routing requests arrive one by one and there is no a priori knowledge regarding future requests. This problem is motivated by the service provider needs for fast deployment of bandwidth guaranteed services. Offline routing algorithms cannot be used since they require a priori knowledge of all tunnel requests that are to be rooted. Instead, on-line algorithms that handle requests arriving one by one and that satisfy as many potential future demands as possible are needed. The newly developed algorithms are on-line algorithms and are based on the idea that a newly routed tunnel must follow a route that does not "interfere too much" with a route that may he critical to satisfy a future demand. We show that this problem is NP-hard. We then develop path selection heuristics which are based on the idea of deferred loading of certain "critical" links. These critical links are identified by the algorithm as links that, if heavily loaded, would make it impossible to satisfy future demands between certain ingress-egress pairs. Like min-hop routing, the presented algorithm uses link-state information and some auxiliary capacity information for path selection. Unlike previous algorithms, the proposed algorithm exploits any available knowledge of the network ingress-egress points of potential future demands, even though the demands themselves are unknown. If all nodes are ingress-egress nodes, the algorithm can still be used, particularly to reduce the rejection rate of requests between a specified subset of important ingress-egress pairs. The algorithm performs well in comparison to previously proposed algorithms on several metrics like the number of rejected demands and successful rerouting of demands upon link failure.