Network coding (NC) and multipacket reception with successive interference cancellation (SIC) have been shown to improve the performance of multihop wireless networks (MWNs). However, previous work emphasized maximization of network throughput without considering quality of service (QoS) requirements, which may lead to high packet delays in the network. The objective of this work is minimization of packet delay in a TDMA-based MWN that is jointly utilizing NC and SIC techniques for a given traffic demand matrix. We assume conflict-free scheduling and allow multipath routing. We formulate a cross-layer optimization that assigns time slots to links in a way that the average packet delay is minimized. The problem formulation results in a difficult mixed integer nonlinear programming (MINLP) that the state-of-art software can only solve for very small-sized networks. For large networks, we develop a heuristic approach that iteratively determines the optimal solution. We present numerical results, which show that the average packet delay and traffic handling capacity of a network, using w/o NC+SIC, NC, SIC and NC+SIC schemes, improves from left to right. The traffic capacity of NC+SIC is double of the w/o NC+SIC. Thus, combined utilization of NC and SIC techniques results in significant performance improvement.

Network coding (NC) has been shown to improve the throughput of multi-hop wireless networks (MWN). Prior work on performance modeling of NC mainly addresses the maximization of throughput. However, these works fail to capture the complete picture since there may be paths in the network for which end-to-end packet delay is prohibitively high. In this paper, we address the problem of delay minimization in MWNs with NC. The objective has been assignment of wireless node capacities in a way that the average packet delay is minimized for a given network topology and the traffic demand matrix. We develop a performance analysis of the system, which models network nodes as M/G/1 queues and takes into account wireless interference. The proposed model is valid both with and without opportunistic listening for any wireless network topology. The model also incorporates network coding-aware routing that routes the flows in a manner that increases coding opportunities. We present numerical results, which show that NC reduces the average packet delay in the network and extends the stable operating region of the network. We also present simulation results, which confirm the accuracy of the analysis.

Abstract For emerging wireless mesh networks, multicode multicarrier CDMA(MC‐CDMA) based technology is one of the most viable candidates. We perform stochastic modelling of the queues at the mobile station for uplink communication with multicode multicarrier CDMA system with two types of traffic, namely real‐time and non‐real‐time. Each traffic is assigned its own codes. However, the non‐real‐time traffic is allowed to use codes assigned to real‐time traffic, when real‐time traffic is not using its codes. Based on the probability of bit error for a multicode MC‐CDMA system, we first compute the probability of packet error. The packet in error will be inserted into the queue until it successfully gets through to the receiver. The packet arrival process at the input queue is modelled as Markov modulated Poisson processes (MMPP). The QoS performance in terms of packet loss for real‐time traffic and the occupancy distribution for non‐real‐time traffic is evaluated using matrix geometric techniques. We present numerical results for low and high load of real‐time traffic with varying loads of non‐real‐time traffic. We observe the binomial tweaking feature of occupancy distribution at higher loads due to batch departures. Copyright © 2009 John Wiley & Sons, Ltd.

TAT-1, the first transatlantic telephone system, came into service in 1956. Its design was dominated by the need for reliability. Coincidentally, the process of the deregulation of the telephone industry began the very same year. This process has led to the current competitive environment. We speculate on the effect that competition would have had on design decisions. Our focus is upon a particular component, the flexible repeater.

The nodes of wireless sensor networks (WSNs) have the dual function of gathering information and relaying it to a central collection point, the sink. For the latter function the key is connectivity involving paths over which data is passed from node to node to the sink. We derive connectivity, as expressed by the probability that a node lies on a path to the sink, as a function of the probability that adjacent cells in a grid are connected. This result is then applied to the typical scenario where nodes are randomly scattered throughout the area being monitored. Useful upper and lower bounds for the probability of adjacent cells being connected are derived as a function of the node density in a cell. For battery powered nodes, lifetime is an important factor. The effect of the demise of nodes on the nodal density and, in turn, on network connectivity is quantified.

Performance-analysis of a switching system using priority-based dynamic capacity allocation is presented. The system provides connectivity between a number of point-to-multipoint communication access clusters. The scheduling of traffic transmission at each access cluster is based on a priority scheme with priority given to real-time (rt) traffic over nonreal-time (nrt) traffic. An analytical model is developed to evaluate the covariance functions of both rt and nrt traffic arriving at the output ports. Aggregate traffic arrival streams are approximated to 2-state Markov-modulated Poisson processes (MMPPs) by matching their statistical characteristics. Analytical and simulation results on performance of an example 4 /spl times/ 4 switch for different traffic loads are discussed.

The performance of a priority-based dynamic capacity allocation suitable for wireless ATM systems is presented. The scheduling of ATM cell transmission in each uplink TDMA frame is based on a priority scheme with priority given to real-time traffic over nonreal-time traffic. Real-time traffic exceeding the uplink capacity is lost while nonreal-time traffic that cannot be served is stored in a first-in first-out (FIFO) queue. An analytical model is developed to evaluate the cell loss ratio (CLR) of both real-time and nonreal-time traffic. Aggregate voice, video, and data traffic is modeled by three two-state Markov-modulated Poisson processes (MMPPs). Analytical results for different system capacities and various traffic loads and scenarios are discussed. Simulation results with on-off sources and approximating MMPP sources are also presented.

Performance analysis of a wireless ATM switching system using priority-based dynamic capacity allocation is presented. The system provides connectivity between a number of clusters of wireless ATM remote terminals. The scheduling of ATM cell transmission at each lint with TDMA frame is based on a priority scheme with priority given to real-time traffic over non-real-time traffic. Both types of traffic arriving at the downstream links are approximated by a 2-state Markov-modulated Poisson process (MMPP) in order to obtain analytical results. Illustrative results for two different traffic loads and at the output of 4/spl times/4 switch are discussed.

We consider a priority based service for traffic on the up and down links of satellite networks employing on-board processing. Real-time and jitter tolerant traffic are modulated onto a frame based flow structure with priority given to the real-time traffic. The real-time cell arrivals exceeding the frame capacity are lost while excess jitter tolerant traffic is stored. We develop an analytical technique to find the cell loss probability of the real-time traffic and the buffer overflow probability of the jitter tolerant traffic. The two sources of real-time traffic, voice and video, are each modeled as two-state Markov modulated Poisson processes (MMPP). The MMPP is also used to model jitter tolerant traffic. These results are applied to the up link of a satellite system.

We consider the first passage to overload for a buffered statistical multiplexer loaded with N identical binary on-off sources. First passage times to overload are related to the characterization of congestion imminence which in turn is crucial in the design of effective congestion control algorithms for delay sensitive services in broadband wide area networks. We give the moments of the first passage time to overload as solutions of a set of linear first order ordinary differential equations. Furthermore, adapting the methodology developed by Anick, Mitra and Sondhi (1982) we express the moments of the first passage time to overload in a spectral expansion form, involving the system's eigenvalues. Numerical results for the first two moments are presented.

The performance of a multicast switching system with a cyclic priority input access scheme is evaluated by means of an analytic model which may treat two &tinct multicast switches in a unified way. The performance measure is the packet delay at the input buffer of the system. The analysis is subsequently performed using matrix-geometric techniques and the numericai results are compared with simulations.

A comparison of the performance of two input access mechanisms for multicast switching is presented. The first of these-a cyclic priority input access method-is a derivative of the ring token reservation method which eliminates the unfairness of the ordinary ring token reservation. It has the advantage of being relatively simple and easy to implement. A second approach employs a neural network to resolve output port conflict. While more difficult to implement, it has a delay-throughput performance advantage over the cyclic priority approach. The primary performance measurements are the switch throughput and the packet delay. A key assumption is that all copies of the same packet must be switched in the same slot.>

An analysis of the performance, in terms of average message delay, is presented for a system of interconnected ring networks. The system is hierarchical, with local rings served by a high-speed backbone ring through gateway queues. In both the local and the backbone rings, the access technique employed is token passing. Service disciplines, with and without priority, have been studied. In the former, priority is given to inter-ring traffic over local traffic. The study makes use of certain results on average delay in systems where the customer initiating a busy period receives special service for the M/G/1 queue with nonpreemptive priority and for the G/G/1 queue. The analysis, which involved several approximations, was verified by simulation.>

Broadband optical networks which carry a wide range of traffic classes in an integrated fashion are considered. The focus is on so-called stream traffic in which each class if allocated different quantities of broadband for the duration of a call on an equal sharing policy. An exact analysis of the blocking conditions experienced by different classes of traffic demanding transmission through a network with the star or the ring topology is presented. Thus, blocking probabilities on tandem links are calculated by means of a recursive relation that considerably simplifies the complexity of the problem without ignoring the interdependencies among links. Being a solution to a multiple-classes-multiple-links blocking problem, the present work is a multidimensional generalization of a well-known analysis for a single trunk. The efficiency of the solution results from the linearity of the necessary computations.>

Access control and performance for multicast packet switching in a broadband network environment are studied. In terms of scheduling the transmission of the copies of the packet onto output ports, two basic service disciplines are defined: one-shot scheduling (all the copies transmitted in the same time slot) and call splitting (transmission over several time slots). As subcategories of call splitting, SS (strict-sense) specifies that each packet can send at most one copy to the destination per time slot, whereas WS (wide-sense) does not carry this restriction. A scheme called revision scheduling, which mitigates the head-of-line (HOL) blocking effect by sequentially combining the one-shot scheduling and the call splitting disciplines, is proposed. Output contention resolution implementations, in the form of combinational logic circuits designed to resolve output contentions arising in each of the call scheduling disciplines, are introduced. A neural-network-based contention resolution algorithm is proposed to demonstrate the improvement of the optimal scheduling.>

The authors explore a metropolitan area network (MAN) configuration which assumes capabilities of optical fiber and optical components which are anticipated to be available within a ten-year time frame. There are two possible physical configurations: a basic topology, such as the star and the tree, and a compound configuration, such as the tree-star-tree. As a logical overlay which serves to route information packets between stations, a form of perfect shuffle, the ShuffleNet, is used. Performance is calculated in terms of average packet delay as a function of traffic load. Of particular interest is the effect of physical limitations on performance. In particular, the effect of a limitation on the bandwidth of optical amplifiers is delineated. This limitation increases the length of the path between originating and terminating stations.>

A study of the performance of a cyclic-priority input access mechanism for a multicast switch is carried out. The method is a derivative of the ring token reservation method which eliminates the unfairness of the ordinary ring token reservation. It has the further advantage of being simple and easy to implement. The primary performance measurements are the switch throughput and the packet delay. A key assumption is that all copies of the same packet must be switched in the same slot.>

A LAN or MAN (local or metropolitan area network) using token passing to allow stations to access the transmission medium is studied. Ibe and Cheng (1989) recently presented an approximate derivation of message delays for an asymmetric single-service token passing with only one type of message. In the present work, this analysis is extended to an operation with nonpreemptive priority queuing. The number of message priority levels and the walktime vary from one station to another. Moreover, the assumed Poisson message arrival process and the message transmission time vary, not only from one station to another, but also from one class to another. The performance, as measured by the mean delay for any message class at any station, is derived. The simulation results show excellent agreement with the analytical results, even under heavy loading. The results confirm earlier findings that the performance at a station is influenced by its position relative to heavily loaded stations.>

The performance of a multicast switch, a space division switch in which a packet at an input port is routed to a subset of the output ports, is discussed. The delay under the assumption of input port buffering is determined. The system is modeled as an independent set of M/G/1 queues. A key assumption in the analysis is that output port contention is settled by random selection among the contending input ports. In order to justify this as well as the other assumptions, a Monte-Carlo simulation of the system is devised. Numerical results from the analysis and simulation of the system are presented.>

Broadband optical networks which carry a wide range of traffic classes in an integrated fashion are considered. The focus is on so-called stream traffic in which each class is allocated different quantities of bandwidth for the duration of a call. An exact analysis of the blocking conditions experienced by different classes of traffic demanding transmission through an N/sub 1/*N/sub 0/ switch is presented. No particular structure is assumed for the switch besides its capability of resolving output port contention by rearranging the input traffic. A two-dimensional generalization of an analysis for a single trunk is considered. Its efficiency rests on the linearity of the necessary computations, thus the relative independence from the dimensionality of the switch.>

Two forms of fast circuit switching are modeled and studied through mathematical analysis and Monte Carlo simulation. The two examples described use the switching technique in an optical-fiber-based local area network with a star topology. The technique is compatible with time-division multiplexing techniques that are used for a range of traffic classes. Further, the technique trades transmission capacity for processing power, which is the critical limitation of the system. By means of a certain independence assumption, the first form of fast circuit switching is modeled as an M/G/1 queue. The results of the analysis show excellent agreement with simulation. The general result is that there is good system throughput, despite simplicity of processing. The second form, in which rather than first-come first-served the discipline is to search for a message whose destination queue is free, is studied by means of simulation alone. The results indicate an improved performance with a modest increase in processing power.>

Soft errors caused by ionizing radiation will be a limiting factor in the reliability of VLSI circuits with submicron-feature sizes. A new approach to the design of soft-error-tolerant digital integrated circuits'is presented. It is based on the filtering of transients at register inputs, and it incurs a lower area overhead than known techniques. The method, called soft-error filtering (SEF), is derived on the basis of the analogy between a noise-sensitive finite-state machine and a noisy communication channel. The necessary characteristics of the register are examined and a design is presented for the associated filter. It is shown that SEF can be used to reduce the associated error rate to insignificant levels.

As the semiconductor industry continues to scale down the feature sizes in VLSI digital circuits, soft errors will eventually limit the reliability of these circuits. An important source of these errors will be the products of radioactive decay. It is proposed to combat these transient errors by a new technique called soft-error filtering (SEF). This is based on filtering the input to every latch in the VLSI circuit, thereby preventing these transients, generated by alpha particle hits in the combinational section, from being latched in the corresponding registers. Several approaches to the problem of designing filtering latches are compared. This comparison demonstrates the superiority of a double-filter realization. The design for a CMOS implementation of the double-filter latch is presented. Not only is the design simple and efficient, but it can be expected to be tolerant to process variations. A comparison of SEF with conventional techniques for dealing with soft errors shows the former to be generally much more attractive, from the point of view of both area and time overhead.

The problem addressed is that of capacity allocation for networks carrying both voice and data. It is assumed that transmission in each of the links of the network is digital, with flow divided into fixed length frames. The frame is allocated between voice and data. The problem is to find the optimum division of capacity for each of the links so as to minimize the probability of blocking of a voice call with a constraint on the average delay of a data message. The performance criteria are such that the problem can be approximated by a linear programming problem. Examples demonstrating the value of the capacity allocation technique are given.

An algorithm is derived which performs optimal symbol-by-symbol detection of a pulse amplitude modulated sequence. The algorithm is similar to the Viterbi algorithm with the optimality criterion optimal symbol detection rather than optimal sequence detection. A salient common feature is the merge phenomenon which allows common decisions to be made before the entire sequence is received.

We consider the problem of optimal dynamic allocation of a limited number of processors to service the demands from different types of users. The types are differentiated by the rates at which they enter requests for service and the mean length of time they occupy a single processor. The decision to accept or reject a request for service may be based on the number of processors occupied by each type. Throughput, or utilization of processors, weighted differently for each type may be used as a performance measure. While the optimum allocation question is formulated for any finite number of customer types, our solution is limited to the case of two competing customer classes. For two types of users we show that among a large class of policies, the optimum is the easily implemented policy of restricting the maximum number of processors that one of the two types can occupy at any time. The requests from the other type are always honored as long as a processor is available for service. It is intuitively reasonable that, despite the complex interactivity permitted in some policies and the multidimensional characterization of a customer type, one of the customer types should have a relative advantage and be permitted open access while a hard limitation is enforced on the competition. The crux of the proof involves a policy space perturbation argument relying on the structure of the equilibrium density.

A basic property of data sources in interactive applications is burstiness, i.e., short periods of activity followed by long idle periods. In these same applications message delay is the primary performance criterion. The combination of bursty flow and a delay criterion leads to a source encoding problem in which delay plays a central role. A salient feature of this problem is that there is a tradeoff between delay and the number of protocol bits required to represent the state of the source. A simple model of a bursty source is studied with the objective of understanding the relationship between coding efficiency and delay. Two encoding schemes, a block encoding technique and a technique employing flags, are examined in some detail. For both the block encoding and the flag schemes, a significant result is that as the source becomes less bursty, delay grows without bound. This result is obtained in spite of the fact that both schemes are reasonable and in the limit the encoding problem disappears. It also appears that the flag encoding technique has much smaller delay than block encoding.

A critical component of computer communications networks is local distribution, i.e., techniques for connecting geographically dispersed users to a central facility. A drawback to conventional polling techniques for local distribution is excessive overhead. Thus, in systems with many lightly loaded terminals, message delay is more a function of the time required to poll all terminals than of traffic from competing sources. A technique for reducing overhead is presented together with the results of analysis and simulation. The technique identifies terminals having messages by a process of elimination starting with a poll of groups of terminals. Further, the technique is adaptive in that the sizes of groups to be polled are chosen according to the probability of a terminal having a message. The object of the adaptivity is to minimize the average time required to examine all terminals. The results of analysis and simulation show considerable reduction in this average for systems with many lightly loaded terminals. Moreover, the adaptive feature insures that there is no penalty for heavy loading. With reduced overhead there is a reduction in the average delay of messages.

The digital data-transmission network studied takes the form of interconnected loops or rings of users. The present report describes a simulation study of a single ring of users undertaken for the dual purpose of observing and evaluating such quantities as message delay, buffer occupancy, and busy-idle periods, and of comparing previous analytical work concerning message delay with values obtained from simulation. The study focused on homogeneous users although other user populations are discussed. Other aspects examined, though not in as great detail, are effects of quantization of message segments, line utilization, and system capture by competing communities of users. Principal conclusions reached can be stated as follows. 1) Under quite reasonable conditions, user-induced message delay is small for moderate line loads. 2) Simulated delays and theoretical estimates of message delays are in good agreement over a wide range of line loads.

Still pictures can be modeled as realizations of a two-dimensional random field. Similarly, pictures that unfold with time across an aperture can be modeled as realizations of three-dimensional fields. Correlated sources can be found by looking at different regions of the spectrum or at different areas of a picture. Under the assumption that the sources are Gaussian a method is presented for finding the rate distortion function for all such sources, under a mean-square-error criterion, in terms of their power spectral densities. In particular, the rate distortion functions for a pair of correlated processes and for a two-dimensional random field are derived.

Recent work on feedback communications systems is predicated on negligible delay in the forward and the feedback channels. The effect of delay on binary feedback systems of the type considered by Turin and Horstein is studied. Both sequential and nonsequential detection at the receiver are considered. It is shown that if the round-trip delay is small relative to the detection time at the receiver, uncertainty feedback offers considerable advantage. However, for the class of signals considered, the presence of delay precludes operation at channel capacity with zero probability of error.

The problem studied is the design of signals in a binary sequential detection system which has a feedback channel available to it. Until a decision is made on a particular transmission, the transmitter is informed via the feedback channel of the state of uncertainty at the receiver. This uncertainty feedback modulates the transmitted signal so that, for a prescribed probability of error, the average time of transmission of a binary digit is minimized subject to an average power constraint and a probabilistic peak power constraint. It is assumed that the forward and the feedback channels are coherent and are each disturbed independently by white Gaussian noise. Previous work has been predicated on noise-free feedback. Signals are derived, drawn from a certain class, which are optimum when the ratio of allowable peak-to-average power is either large or close to one. The performance of these signals is analyzed. It is shown that for a high signal-to-noise ratio in the feedback channel and a high allowable peak-to-average power ratio one can transmit at approximately channel capacity with Iow probability of error. However, an infinite feedback channel signal-to-noise ratio and an infinite allowable peak-to-average power ratio are required to transmit at channel capacity with zero probability of error. Results on signal design in a system whose configuration is slightly different from that considered in the main body of the paper are summarized, as well as the results of a study of the effect of delay in the forward and feedback channels.