Minimum-cost multicast over coded packet networks

We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e., packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved.     

On the scalability of ad hoc networks

We investigate the inherent scalability problem of ad hoc networks originated from the nature of multihop networks. First, the expected packet traffic at the center of a network is analyzed. The result shows that the expected packet traffic at the center of a network is linearly related with the network size, that is, the expected packet traffic at the center of a network is O(k), where k is the radius of a network. From the result, the upper bound of the diameter of a network D=2k, that guarantees the network is scalable, is obtained. The upper bound is given by C/r-1, where C is the channel capacity available to each node and r is the packet arrival rate at each node.     

Optimal segments for forwarding table size minimization in segment-routed SDNs

Segment routing (SR) is a source routing paradigm where packet forwarding is based on a sequence of instructions known as segments identified using segment IDs (SIDs). An ordered list of SIDs identifies the source route and is carried in the packet headers. Switches in such networks use the SIDs to look up their forwarding tables and forward packets along the segments. Since various flows can share the segments, SR is a mechanism to avoid per-flow state thereby minimizing the forwarding table size (FTS) of the switches. Software-defined networks (SDNs) are suitable for SR since the source routing can be accomplished by a centralized controller. Typically, the segment list is limited to a maximum segment list depth (SLD). It can be shown that FTS varies inversely as the SLD. This paper studies the problem of minimizing the FTS given the set of flows and the SLD limitation, which is shown to be NP-complete. An ILP formulation of the problem is used to solve the problem in relatively small networks. Two different heuristic solutions, BFH and CCH, are presented to solve this problem in large-scale networks with up to 30,000 nodes and 250,000 flows and for three different network topologies (ring-of-rings, fat-tree, and mesh). The heuristics are shown to perform up to 50% better than an existing FTS minimization technique. Further, CCH is shown to perform better in networks with a high prevalence of equal cost multipaths (ECMPs), while BFH performs better when ECMPs are few in number.     

A control theoretical approach to congestion control in packet networks

In this paper, we introduce a control theoretical analysis of the closed-loop congestion control problem in packet networks. The control theoretical approach is used in a proportional rate controller, where packets are admitted into the network in accordance with network buffer occupancy. A Smith Predictor is used to deal with large propagation delays, common to high speed backbone networks. The analytical approach leads to accurate predictions regarding both transients as well as steady-state behavior of buffers and input rates. Moreover, it exposes tradeoffs regarding buffer dimensioning, packet loss, and throughput.     

Models and Approximation Algorithms for Channel Assignment in Radio Networks

We consider the frequency assignment (broadcast scheduling) problem for packet radio networks. Such networks are naturally modeled by graphs with a certain geometric structure. The problem of broadcast scheduling can be cast as a variant of the vertex coloring problem (called the distance-2 coloring problem) on the graph that models a given packet radio network. We present efficient approximation algorithms for the distance-2 coloring problem for various geometric graphs including those that naturally model a large class of packet radio networks. The class of graphs considered include (r,s)-civilized graphs, planar graphs, graphs with bounded genus, etc.     

Rate-distortion optimized hybrid error control for real-time packetized video transmission.

The problem of application-layer error control for real-time video transmission over packet lossy networks is commonly addressed via joint source-channel coding (JSCC), where source coding and forward error correction (FEC) are jointly designed to compensate for packet losses. In this paper, we consider hybrid application-layer error correction consisting of FEC and retransmissions. The study is carried out in an integrated joint source-channel coding (IJSCC) framework, where error resilient source coding, channel coding, and error concealment are jointly considered in order to achieve the best video delivery quality. We first show the advantage of the proposed IJSCC framework as compared to a sequential JSCC approach, where error resilient source coding and channel coding are not fully integrated. In the USCC framework, we also study the performance of different error control scenarios, such as pure FEC, pure retransmission, and their combination. Pure FEC and application layer retransmissions are shown to each achieve optimal results depending on the packet loss rates and the round-trip time. A hybrid of FEC and retransmissions is shown to outperform each component individually due to its greater flexibility.     

An energy efficiency model for adaptive and custom error control schemes in Bluetooth sensor networks

This paper analyzes the effect of custom error control schemes on the energy efficiency in Bluetooth sensor networks. An analytical model is presented to evaluate the energy efficiency metric, which considers in just one parameter the energy and reliability constraints of wireless sensor networks. New packet types are introduced using some error control strategies in the AUX1 packet, where custom coding can be implemented. Two adaptive techniques are proposed that change the error control strategy based on the number of hops traversed by a packet through the network. A packet selection strategy based on channel state is proposed for sensor networks with different channel conditions. Performance results are obtained through analysis and simulation in Nakagami-m fading channels for networks with different number of hops and channel conditions.     

Commercial, legal, and international aspects of packet communications

Packet switching technology emerged rapidly in the 1970's as another viable mode of communications switching, along with circuit and message switching. Since packet switching offers economical and versatile data communication capabilities in a multiuser environment, it is particularly well suited for furnishing public data communication network services. Public packet networks are now established or being developed in most industrialized countries, and the introduction of these networks has raised policy issues relating to the structure and regulation of the national networks, and the interconnection of national networks into an international packet switching system. This paper reviews these issues and concludes that public packet switching network services will continue to be regulated in all cases; that competitive packet networks will coexist in the U.S. and in Canada, but that only one national packet network will exist in each of most other countries; that packet networks will aggravate the problem of distinguishing nonregulated data processing services from regulated data communication services; that international interconnection of public packet networks based upon CCITT standanh will occur rapidly over the next several years; and that a unified international packet switching system will eventually emerge similar to today's international telephone and telex systems.     

Joint Delay-Power Multiple Packet Capture Scheme for Spread-Spectrum Slotted ALOHA Packet Radio Networks

In this paper, a joint delay-power multiple packet capture scheme, that can collect multiple packets simultaneously from different terminals with both delay and power captures, is presented. The corresponding joint delay-power capture probabilities for a spread-spectrum slotted ALOHA packet radio networks where all terminals use a common spreading code under Rayleigh fading with power control are derived. Throughput and delay performance of the spread-spectrum slotted ALOHA packet radio networks with the joint delay-power multiple packet capture effect are shown by our simulation results to be significantly improved compared with the existing schemes.     

Efficient Broadcasting Using Network Coding

We consider the problem of broadcasting in an ad hoc wireless network, where all nodes of the network are sources that want to transmit information to all other nodes. Our figure of merit is energy efficiency, a critical design parameter for wireless networks since it directly affects battery life and thus network lifetime. We prove that applying ideas from network coding allows to realize significant benefits in terms of energy efficiency for the problem of broadcasting, and propose very simple algorithms that allow to realize these benefits in practice. In particular, our theoretical analysis shows that network coding improves performance by a constant factor in fixed networks. We calculate this factor exactly for some canonical configurations. We then show that in networks where the topology dynamically changes, for example due to mobility, and where operations are restricted to simple distributed algorithms, network coding can offer improvements of a factor of , where is the number of nodes in the network. We use the insights gained from the theoretical analysis to propose low-complexity distributed algorithms for realistic wireless ad hoc scenarios, discuss a number of practical considerations, and evaluate our algorithms through packet level simulation.     

Optimal Rate–Delay Tradeoffs and Delay Mitigating Codes for Multipath Routed and Network Coded Networks

Via multiterminal information theory, a framework is presented for deriving fundamental rate–delay tradeoffs that delay mitigating codes must have when utilized over multipath routed and random linear network coded networks. The rate–delay tradeoff is formulated as a calculus problem on a capacity region of a related abstracted broadcast channel. Given this general framework for studying such rate–delay tradeoffs, the extreme case of uniform networks, in which each possible received packet arrival order is equally likely, is considered. For these networks, the rate–delay calculus problem is simplified to an integer programming problem, which for small numbers of packets may be solved explicitly, or for larger numbers of packets, may be accurately approximated through the calculus of variations by appropriate relaxation of an integer constraint. Explicit expressions for the rate–delay tradeoff in uniform networks are presented in the special cases of i) constant packet inter-arrival times, and ii) exponential independent and identically distributed (i.i.d.) packet arrival times. Finally, the delay mitigating codes achieving these rate–delay tradeoffs are discussed.      

Maximizing multicast lifetime in unreliable wireless ad hoc network

Multicast is an efficient method for transmitting the same packets to a group of destinations. In energy-constrained wireless ad hoc networks where nodes are powered by batteries, one of the challenging issues is how to prolong the multicast lifetime. Most of existing work mainly focuses on multicast lifetime maximization problem in wireless packet loss-free networks. However, this may not be the case in reality. In this paper, we are concerned with the multicast lifetime maximization problem in unreliable wireless ad hoc networks. To solve this problem, we first define the multicast lifetime as the number of packets transmitted along the multicast tree successfully. Then we develop a novel lifetime maximization genetic algorithm to construct the multicast tree consisting of high reliability links subject to the source and destination nodes. Simulation results demonstrate the efficiency and effectiveness of the proposed algorithm.     

Minimising the size of voids in optical packet switching using a novel packet scheduling algorithm

In this paper, we propose a new packet scheduling algorithm to minimise the size of voids in optical packet switching. The effects of excess load, output utilisation, and packet loss probability are closely studied. Other contributing factors to the packet loss probability, which include the buffer depth and the numbers of wavelength channels, are also investigated. The proposed algorithm is of importance to next generation networks where broadband capabilities with end-to-end quality of service over all-IP optical networks is envisaged.     

Feedback control of congestion in packet switching networks: thecase of a single congested node

Addresses a rate-based feedback approach to congestion control in packet switching networks where sources adjust their transmission rate in response to feedback information from the network nodes. Specifically, a controller structure and system architecture are introduced and the analysis of the resulting closed loop system is presented. Conditions for asymptotic stability are derived. A design technique for the controller gains is developed and an illustrative example is considered. The results show that, under appropriately selected control gains, a stable (nonoscillatory) operation of store-and-forward packet switching networks with feedback congestion control is possible     

Novel Fastest Retransmission and Rate Control Schemes for Improving TCP Performance in Wireless Ad Hoc Networks

A number of different authors have considered the problem of performance degradation of transmission control protocol (TCP) in wireless ad hoc networks. We herein show that pauses in packet transmission due to packet losses are the fundamental cause of performance degradation of TCP in wireless ad hoc networks. To minimize the duration of packet transmission pauses, we propose a fast retransmission scheme for improving TCP performance in consideration of the inter-operability of previously deployed TCPs in wireless ad hoc networks. We also propose an additional rate control scheme for TCPs to reduce the probability of packet contention. Using OPNET and NS2 simulations, we show that our proposed schemes can provide a much better performance than conventional TCPs.     

Jointly optimized bit-rate/delay control policy for wireless packetnetworks with fading channels

We consider the downlink rate control problem in a wireless channel. A dynamic programming optimization method is introduced to obtain the optimal bit-rate/delay control policy in the downlink for packet transmission in wireless networks with fading channels. We assume that the base station is capable of transmitting data packets in the downlink with different bit rates, R₀1<···M-1 . It is assumed that the symbol rate is fixed in the system, and different bit rates are achieved by choosing the transmitted symbols from the appropriate signal constellation (adaptive modulation). The derived optimal rate control policy, in each time slot, selects the highest possible bit rate which minimizes the delay and at the same time minimizes the number of rate switchings in the network. The optimal bit-rate control problem is an important issue, especially in packet data networks, where we need to guarantee a quality of service (QoS) in the network. Our analytical as well as simulation results confirm that there is an optimal threshold policy to switch between different rates     

Congestion control for multimedia services

The problem of congestion control in high-speed networks for multimedia traffic, such as voice and video, is considered. It is shown that the performance requirements of high-speed networks involve delay, delay-jitter, and packet loss. A framing congestion control strategy based on a packet admission policy at the edges of the network and on a service discipline called stop-and-go queuing at the switching nodes is described. This strategy provides bounded end-to-end delay and a small and controllable delay-jitter. The strategy is applicable to packet switching networks in general, including fixed cell length asynchronous transfer mode (ATM), as well as networks with variable-size packets     

The Square Root Multipliers Algorithm for Discrete Capacity and Buffer Assignment problems in Elastic Traffic Networks

This paper discusses a novel approach for the dimensioning of packet networks, under the constraints of end-to-end Quality-of-Service (QoS) requirements. The network modeling also considers the dynamic behavior of today's networks traffic. In particular, the proposed approach considers multilink networks where discrete capacities are the decision variables. This Discrete Capacity Assignment (DCA) problem can be classified as a constrained combinatorial optimization problem and therefore it is NP-complete. In order to solve the problem, we propose the Square Root Multipliers Algorithm (SRMA) followed by a Randomized Rounding (RR) method. We also enforce loss probability constraints by properly choosing buffer sizes, therefore facing the Buffer Assignment (BA) problem. To evaluate the performance of our approach, SRMA/RR results are compared with the optimal solutions found by an exhaustive search (ES) procedure. Analytical results for a variety of problem instances are reported, and a verification is performed based on simulations conducted with the software NS-2. The results suggest that the proposed approach provides a quite efficient method to obtain near-optimal solutions with small computational effort.     

Hop count optimal position-based packet routing algorithms for ad hoc wireless networks with a realistic physical Layer

Existing routing and broadcasting protocols for ad hoc networks assume an ideal physical layer model. We apply the log-normal shadow fading model to represent a realistic physical layer and use the probability p(x) for receiving a packet successfully as a function of distance x between two nodes. We define the transmission radius R as the distance at which p(R)=0.5. We propose a medium access control layer protocol, where receiver node acknowledges packet to sender node u times, where u*p(x)/spl ap/1. We derived an approximation for p(x) to reduce computation time. It can be used as the weight in the optimal shortest hop count routing scheme. We then study the optimal packet forwarding distance to minimize the hop count, and show that it is approximately 0.73R (for power attenuation degree 2). A hop count optimal, greedy, localized routing algorithm [referred as ideal hop count routing (IHCR)] for ad hoc wireless networks is then presented. We present another algorithm called expected progress routing with acknowledgment (referred as aEPR) for ad hoc wireless networks. Two variants of aEPR algorithm, namely, aEPR-1 and aEPR-u are also presented. Next, we propose projection progress scheme, and its two variants, 1-Projection and u-Projection. Iterative versions of aEPR and projection progress attempt to improve their performance. We then propose tR-greedy routing scheme, where packet is forwarded to neighbor closest to destination, among neighbors that are within distance tR. All described schemes are implemented, and their performances are evaluated and compared.