Query-based sampling has become an increasingly popular technique for monitoring Markov sources in pull-based update systems. However, most of the contemporary literature on this assumes an exponential distribution for query delay and often relies on the assumption that the feedback or replies to the queries are instantaneous. In this work, we relax both of these assumptions and find optimal sampling policies for monitoring continuous-time Markov chains (CTMC) under generic delay distributions. In particular, we show that one can obtain significant gains in terms of mean binary freshness (MBF) by employing a waiting based strategy for query-based sampling.

Status update systems require the timely collection of sensing information for which deploying multiple sensors/servers to obtain diversity gains is considered as a promising solution. In this work, we construct an absorbing Markov chain (AMC) to exactly model Age of Information (AoI) in a discrete-time dual-queue (DTDQ) status update system with generate-at-will (GAW) status updates, discrete phase-type (DPH-type) distributed service times and transmission freezing. Specifically, transmission is frozen for a certain number of slots following the initiation of a transmission, after which one of the two servers is allowed to simultaneously sample the monitored physical process and transmit a status update packet, according to the availabilities and priorities of the two servers. Based on the discrete-time AMC, we provide the exact distributions of both AoI and peak AoI (PAoI), enabling the derivation of arbitrary order moments. In addition, we analytically study the role of freezing using several typical service time distributions, including geometric, uniform, negative binomial, and triangular distributions. The introduction of freezing for DTDQ systems is demonstrated to be significantly beneficial in reducing the mean AoI for various service time distributions. Additionally, we study the impact of the statistical parameters of the service times and heterogeneity between the two servers on the freezing gain, i.e., reduction in mean AoI attained with optimum freezing policies.

In this paper, we investigate the problem of remote estimation of a discrete-time joint Markov process using multiple sensors. Each sensor observes a different component of the joint Markov process, and in each time slot, the monitor obtains a partial state value by sending a pull request to one of the sensors. The monitor chooses the sequence of sensors to observe with the goal of minimizing the mean of age of incorrect information (MAoII) by using the partial state observations obtained, which have different freshness levels. For instance, a monitor may be interested in tracking the location of an object by obtaining observations from two sensors, which observe the$x$and$y$coordinates of the object separately, in different time slots. The monitor, then, needs to decide which coordinate to observe in the next time slot given the history. In addition to this partial observability of the state of Markov process, there is an erasure channel with a fixed one-slot delay between each sensor and the monitor. First, we obtain a sufficient statistic, namely the belief, representing the joint distribution of the age of incorrect information (AoII) and the current state of the observed process by using the history of all pull requests and observations. Then, we formulate the problem with a continuous state-space Markov decision problem (MDP), namely belief MDP. To solve the problem, we propose two model predictive control (MPC) methods, namely MPC without terminal costs (MPC-WTC) and reinforcement learning MPC (RL-MPC), that have different advantages in implementation.

In recent literature, when modeling for information freshness in remote estimation settings, estimators have been mainly restricted to the class of martingale estimators, meaning the remote estimate at any time is equal to the most recently received update. This is mainly due to its simplicity and ease of analysis. However, these martingale estimators are far from optimal in some cases, especially in pull-based update systems. For such systems, maximum aposteriori probability (MAP) estimators are optimum, but can be challenging to analyze. Here, we introduce a new class of estimators, called structured estimators, which retain useful characteristics from a MAP estimate while still being analytically tractable. Our proposed estimators move seamlessly from a martingale estimator to a MAP estimator.

Reduction of the energy consumption of wireless sensor nodes is key for the successful deployment of Internet of Things (IoT) services and applications. This paper investigates the trade-off between energy and information freshness from the perspective of the transmission module of IoT sensor nodes which can alternate between Sleep (or Low-power) and Active modes of operation. In particular, timer-based sleep-wake scheduling is investigated for a single sensor node. A variation of Age of Incorrect Information (AoII), which is termed as AoII+ in the literature, is used as the performance metric for information freshness. Then, we provide closed-form expressions for both average AoII+ and average power when updates take place according to a Poisson process and service times are either deterministic or phase-type distributed. Subsequently, we propose two optimal schedulers, namely AoII-Idling Scheduler (AoII-IS) and AoII-Zero Idling Scheduler (AoII-ZIS), which are devised to control the transitions between the Sleep and Active modes while the average AoII+ is kept below a pre-defined threshold. Moreover, we propose an adaptive version of both schedulers which dynamically tune their timer parameter when the update rate is allowed to vary in time. We validate our analysis and findings with simulations.

We consider the problem of assigning tasks efficiently to a set of workers that can exhaust themselves as a result of processing tasks. If a worker is exhausted, it will take a longer time to recover. To model efficiency of workers with exhaustion, we use a continuous-time Markov chain (CTMC). By taking samples from the internal states of the workers, the source assigns tasks to the workers when they are found to be in their efficient states. We consider two different settings where (i) the source can assign tasks to the workers only when they are in their most efficient state, and (ii) it can assign tasks to workers when they are also moderately efficient in spite of a potentially reduced success probability. In the former case, we find the optimal policy to be a threshold-based sampling policy where the thresholds depend on the workers’ recovery and exhaustion rates. In the latter case, we solve a non-convex sum-of-ratios problem using a branch-and-bound approach which performs well compared with the globally optimal solution.

Use of multipath network topologies has become a prominent technique to assert timeliness in terms of Age of Information (AoI) and to improve resilience to link disruptions in communication systems. However, establishing multiple dedicated communication links among network nodes is a costly endeavor. Therefore, quite often, these secondary communication links are shared among multiple entities. Moreover, these multipath networks come with the added challenge of out-of-order transmissions. In this article, we study an amalgamation of the above two aspects, i.e., multipath transmissions and link sharing. In contrast to the existing literature where the main focus has been scheduling multiple sources on a single shared server, we delve into the realm where each source sharing the shared server is also supplemented with its dedicated server so as to improve its timeliness. In this multipath link sharing setting with generate-at-will transmissions, we first present the optimal probabilistic scheduler, and then propose several heuristic-based cyclic scheduling algorithms for the shared server, to minimize the weighted average AoI of the sources.

The Age of Information (AoI), which measures the time since the generation of the latest update, quantifies information freshness in timeliness-critical systems. Minimizing AoI and characterizing it precisely are crucial for system efficiency and decision-making. This work investigates AoI under external interference modeled as an On-Off process, providing a foundation for future research in more complex scenarios. We consider a discrete-time remote status-updating system with a monitor and a sensor, where the sensor observes a physical process, generates timestamped updates, and sends them to the monitor. Both inter-arrival and service times follow geometric distributions, with service interrupted according to a two-state On-Off process. We analyze AoI under two queuing disciplines: 1) non-preemptive, where arriving updates are discarded if the server is occupied, and 2) preemptive, where in-service updates are replaced with new ones during the Off state. For both, we derive closed-form expressions for average AoI and peak AoI (PAoI). We also explore the relationship between discrete-time and continuous-time systems, showing that the latter is the limiting case of the former. Numerical results validate the theoretical analysis, revealing a linear relationship between the relative normalized increase in average PAoI and AoI and the proportion of Off state time. Frequent On-Off switching and higher service rates under the same system load help mitigate freshness deterioration caused by interruptions. The On-Off process is shown to have a large impact on the average AoI (resp. PAoI) of systems with relatively high (resp. low) arrival and service rates.

We study age of information (AoI) in a single-source dual-server continuous-time status update system for the generate-at-will (GAW) scenario, consisting of an information source, two heterogeneous servers, and a monitor (or destination). The technique of stochastic hybrid systems (SHS) has recently been used to obtain the average (or mean) AoI for a work-conserving (WC) zero wait (ZW) system imposed on the Non-parallel Transmission with Monitor Discarding (NT-MD) policy for which out-of-order packets are discarded upon reception by the monitor, for the case of exponentially distributed service times. In this paper, we exactly obtain the distributions (not only the means) of AoI and peak AoI (PAoI) processes for the NT-MD policy, in a more general setting with continuous phase-type distributed service times, by making use of the absorbing Markov chain (AMC) method, which was specifically developed for exact AoI modeling. Additionally, two Parallel Transmission (PT) policies resulting from either monitor discarding (PT-MD), or Source Preemption (PT-SP), are proposed and studied which allows us to comparatively evaluate these policies as a function of certain parameters of the service times. We also propose a non-work-conserving (NWC) NT policy with Freezing and source preemption, called NTF-SP, for which the transmission process is frozen for a certain amount of time upon each transmission, and we comparatively study NTF-SP against its NT-MD counterpart, for exponentially distributed, and also deterministic service times. Numerical results are presented for the validation of the proposed analytical models, and a comparative evaluation of the four transmission policies in terms of mean AoI.

We study the scheduling problem for a multi-source single-servergenerate-at-will(GAW) status update system with sources having heterogeneous service times and weights, for which the goal is to minimize the system age of information (AoI), or system peak AoI (PAoI), by employing scheduling algorithms with low runtime complexity. Here, system AoI/PAoI refers to weighted sum of the average AoI/PAoI values of information sources. In particular, we focus on open-loopcyclic schedulerswithO(1) runtime complexity, where status updates are scheduled according to a fixed finite transmission pattern whose construction is the main scope of this paper. We first develop an analytical method to obtain the exact average AoI/PAoI of the sources when a transmission pattern is given. Subsequently, we derive the optimum transmission pattern for system AoI in closed form, for the specific case of two sources. For general number of sources, a novel method is proposed based on adeletion search(DS) based algorithm which constructs a pattern whose system PAoI can be brought arbitrarily close to the minimum system PAoI that is attainable using open-loop scheduling. Using another outcome of the same DS-based algorithm, a heuristic scheduler is proposed for system AoI minimization, which is shown to outperform various existing age-agnostic schedulers in the literature, including theinsertion search(IS) based algorithm, in the majority of the examples we studied.

We study push-based sampling and transmission policies for a status update system consisting of a general finite-state continuous-time Markov chain (CTMC) information source with known dynamics, with the goal of minimizing the average age of incorrect information (AoII) defined via a linear time penalty function. The problem setting we investigate involves an exponentially distributed delay channel for transmissions and a constraint on the average sampling rate. We first show that the optimum sampling and transmission policy is amulti-thresholdpolicy, where the thresholds depend on both the estimation value and the state of the original process, and sampling and transmission need to be initiated when the instantaneous AoII exceeds the corresponding threshold, called the estimation-and state-aware transmission (ESAT) policy. Subsequently, we formulate the problem of finding the thresholds as a constrained semi-Markov decision process (CSMDP) and the Lagrangian approach. Additionally, we propose two lower complexity sub-optimum policies, namely the estimation-aware transmission (EAT) policy, and the single-threshold (ST) policy, for which it is possible to obtain these thresholds for CTMCs with relatively larger number of states. The underlying CSMDP formulation relies on themulti-regime phase-type(MR-PH) distribution which is a generalization of the well-known phase-type distribution, which allows us to obtain the first two moments of time until absorption in a CTMC whose transition rates change with respect to time, in a piece-wise manner. The effectiveness of the proposed ESAT, EAT, and ST sampling and transmission policies are shown through numerical examples, along with comparisons with a baseline scheme that transmits packets according to a Poisson process in out-of-sync periods.

Frame coalescing is a well-established technique which manages the low power idle (LPI) mode supported by energy efficient Ethernet (EEE) interfaces. Frame coalescing enables EEE interfaces to remain in the LPI mode for a certain amount of time upon the arrival of the first frame (timer-based coalescing), or until a predefined amount of traffic accumulates in the transmission buffer (size-based coalescing). In this paper, we propose a novel open-loop dynamic coalescing technique, namely MPC-mean, that is based on model predictive control (MPC) and queuing theory. In contrast to conventional timer-based coalescing, the proposed method enables the update of the timer parameter repeatedly throughout the duration of the LPI mode of a single coalescing cycle by taking into account the arrival instants and sizes, of the frames waiting in the buffer. The proposed MPC-mean method attempts to minimize the energy consumption of the Ethernet link, under constraints on mean of the queue waiting time. The effectiveness of the algorithm is validated using simulations with synthetic and actual traffic traces.

We study a pull-based monitoring system in which a common remote monitor queries the states of a collection of heterogeneous finite-state irreducible continuous time Markov chain (CTMC) based information sources, according to a Poisson process with different per-source sampling rates, in order to maintain remote estimates of the states. Three information freshness models are considered to quantify the accuracy of the remote estimates: fresh when equal (FWE), fresh when sampled (FWS) and fresh when close (FWC). For each of these freshness models, closed-form expressions are derived for mean information freshness for each source, as a function of the sampling rate. Using these expressions, optimum sampling rates for all sources are obtained using water-filling based optimization for maximizing the weighted sum freshness of the monitoring system, under an overall sampling rate constraint. Numerical examples are presented to validate the effectiveness of the proposed method by comparing it to several baseline sampling policies.

We consider a sensor that samples an$N-\mathbf{state}$continuous-time Markov chain (CTMC)-based information source process, and transmits the observed state of the source, to a remote monitor tasked with timely tracking of the source process. The mismatch between the source and monitor processes is quantified by age of incorrect information (AoII), which penalizes the mismatch as it stays longer, and our objective is to minimize the average AoII under an average sampling rate constraint. We assume a perfect reverse channel and hence the sensor has information of the estimate while initiating a transmission or preempting an ongoing transmission. First, by modeling the problem as an average cost constrained semi-Markov decision process (CSMDP), we show that the structure of the problem gives rise to an optimum threshold policy for which the sensor initiates a transmission once the AoII exceeds a threshold depending on the instantaneous values of both the source and monitor processes. However, due to the high complexity of obtaining the optimum policy in this general setting, we consider a relaxed problem where the thresholds are allowed to be dependent only on the estimate. We show that this relaxed problem can be solved with a novel CSMDP formulation based on the theory of absorbing MCs, with a computational complexity of$\mathcal{O}(N^{4})$, allowing one to obtain optimum policies for general CTMCs with over a hundred states.

Safety guarantees and security-latency problem of Nakamoto consensus have been extensively studied in the last decade with a bounded delay model. Recent studies have shown that PoW protocol is secure under random delay models as well. In this paper, we analyze the security-latency problem, i.e., how secure a block is, after it becomes k-deep in the blockchain, under general random delay distributions. We provide tight and explicit bounds which only require determining the distribution of the number of Poisson arrivals during the random delay. We further consider potential effects of recent Bitcoin halving on the security-latency problem by extending our results.

Most existing stochastic models on age of information (AoI) focus on a single shared server serving status update packets from N > 1 sources where each packet update stream is Poisson, i.e., single-hop scenario. In the current work, we study a two-hop edge computing system for which status updates from the information sources are still Poisson but they are not immediately available at the shared edge server, but instead they need to first receive service from a transmission server dedicated to each source. For exponentially distributed and heterogeneous service times for both the dedicated servers and the edge server, and bufferless preemptive resource management, we develop an analytical model using absorbing Markov chains (AMC) for obtaining the distribution of AoI for any source in the system. Moreover, for a given tagged source, the traffic arriving at the shared server from the N - 1 un-tagged sources, namely the interference traffic, is not Poisson any more, but is instead a Markov modulated Poisson process (MMPP) whose state space grows exponentially with N. Therefore, we propose to employ a model reduction technique that approximates the behavior of the MMPP interference traffic with two states only, making it possible to approximately obtain the AoI statistics even for a very large number of sources. Numerical examples are presented to validate the proposed exact and approximate models.

We consider a cache update system with a remote server delivering time-varying contents of multiple Internet of Things (IoT) items with heterogeneous popularities and service times to a local cache so as to keep the items as fresh as possible at the cache. New content for an item arrives at the server according to a Poisson process and the server is equipped with multiple queues each of which holds the most up-to-date content for the corresponding item. In this setting, we study several scheduling policies employed at the server so as to maximize the popularity-weighted binary freshness across the items. The scheduling problem is first formulated as an infinite-horizon average-reward Markov decision process (MDP) which suffers from the curse of dimensionality when the number of items is large. We then propose a water-filling-based scheduling (WFS) policy and its extension, namely, extended WFS (E-WFS) policy, with worst case complexities being quadratic and cubic in the number of items, respectively, based on convex optimization applied to a relaxation of the original system. Simulation results are provided to validate the effectiveness of the proposed policies.

We study a remote monitoring system in which a mutually independent and heterogeneous collection of finite-state irreducible continuous time Markov chain (CTMC) based information sources is considered. In this system, a common remote monitor queries the instantaneous states of the individual CTMCs according to a Poisson process with possibly different intensities across the sources, in order to maintain accurate estimates of the original sources. Three information freshness models are considered to quantify the accuracy of the remote estimates: fresh when equal (FWE), fresh when sampled (FWS) and fresh when close (FWC). For each of these freshness models, closed-form expressions are derived for mean information freshness for a given source. Using these expressions, optimum sampling rates for all sources are obtained so as to maximize the weighted sum freshness of the monitoring system, subject to an overall sampling rate constraint. This optimization problem leads to a water-filling solution with quadratic worst case computational complexity in the number of information sources. Numerical examples are provided to validate the effectiveness of the optimum sampling policy in comparison to several baseline sampling policies.

We study a multisource status update system with Poisson information packet arrivals and exponentially distributed service times. The server is equipped with a waiting room holding the freshest packet from each source referred to as single buffer per-source queueing (SBPSQ). The sources are assumed to be equally important, i.e., (nonweighted) average Age of Information (AoI) or average age violation probability are used as the information freshness metrics to optimize for, and subsequently, two symmetric SBPSQ-based scheduling policies are studied in this article, namely, first source first serve (FSFS) and the earliest served first serve (ESFS) policies. By employing the theory of Markov fluid queues (MFQs), an analytical model is proposed to obtain the exact distribution of the AoI for each source when the FSFS and ESFS policies are employed at the server. Additionally, a benchmark scheduling-free scheme named single buffer with replacement (SBR), which uses a single buffer to hold the freshest packet across all sources, is also studied with a similar but less complex analytical model. We comparatively study the performance of the three policies through numerical examples in terms of the average AoI and the age violation probability averaged across all sources, in a scenario of sources possessing different traffic intensities but sharing a common service time.

Information freshness in IoT-based status update systems has recently been studied through the Age of Information (AoI) and Peak AoI (PAoI) performance metrics. In this article, we study a discrete-time server arising in multisource IoT systems, which accepts incoming information packets from multiple information sources so as to be forwarded to a remote monitor for status update purposes. Under the assumption of Bernoulli information packet arrivals and a common general discrete phase-type service time distribution across all the sources, we numerically obtain the exact per-source distributions of AoI and PAoI in matrix-geometric form for three different queueing disciplines: 1) nonpreemptive bufferless; 2) preemptive bufferless; and 3) nonpreemptive single buffer with replacement. The proposed numerical algorithm employs the theory of discrete-time Markov chains of quasi-birth-death type and is matrix analytical. Numerical examples are provided to validate the accuracy and effectiveness of the proposed queueing model. We also present a numerical example on the optimum choice of the Bernoulli parameters in a practical IoT system with two sources with diverse AoI requirements.

Analytical modeling of Age of Information (AoI) and Peak AoI (PAoI) has recently drawn a lot of attention in the context of quantitative assessment of information freshness in status update systems. In this paper, we study a probabilistically preemptive bufferless M/PH/1/1 queue fed with information update packets from$N$separate information sources for which a new information packet arrival from source-$m$is allowed to preempt a packet from source-$n$in service, with a probability depending on$n$and$m$. To make the model even more general than the existing ones, we assume a distinct phase-type (PH-type) service time distribution, a distinct packet error and retransmission probability, for each of the information sources. Using sample path arguments and the theory of Markov Fluid Queues (MFQ), the exact distributions of the AoI and PAoI are numerically obtained for each of the sources. Numerical examples are provided to demonstrate the impact of various system parameters on AoI performance. In the context of a two-source system, we present a methodology on how to optimally choose the preemption probabilities and packet generation rates so as to minimize certain AoI-oriented cost functions.

Bufferless and single-buffer queueing systems have recently been shown to be effective in coping with escalated Age of Information (AoI) figures arising in single-source status update systems with large buffers and FCFS scheduling. In this paper, for the single-source scenario, we propose a numerical algorithm for obtaining the exact distributions of both the AoI and the peak AoI (PAoI) in (i) the bufferless PH/PH/1/1/P(p) queue with probabilistic preemption with preemption probability p, 0 ≤ p ≤ 1, and (ii) the single buffer M/P H/1/2/R(r) queue with probabilistic replacement of the packet in the queue by the new arrival with replacement probability r, 0 ≤ r ≤ 1. The proposed exact models are based on the well-established theory of Markov Fluid Queues (MFQ) and the numerical algorithms are matrix-analytical and they rely on numerically stable and efficient vector-matrix operations. Moreover, the obtained exact distributions are in matrix exponential form, making it amenable to calculate the tail probabilities and the associated moments straightforwardly. Firstly, we validate the accuracy of the proposed method with simulations, and for sume sub-cases, with existing closed-form results. We then comparatively study the AoI performance of the queueing systems of interest under varying traffic parameters.

A transmission profile refers to a transmission power and a modulation and coding scheme to be used for packet transmissions over a wireless link. The goal of this paper is to develop transmission profile selection policies so as to minimize the average power consumption on a wireless link while satisfying a certain delay constraint given in terms of a delay violation probability. Toward the assessment of profile selection policies, a multi-regime Markov fluid queue model is proposed to obtain the average power consumption and the queue waiting time distribution which allows one to analyze the energy-delay tradeoff in queuing systems for which the packet transmission duration is allowed to depend on the delay experienced by the packet until the beginning of service. Numerical examples are presented with transmission profiles obtained from realistic LTE simulations. Several transmission profile selection policies are proposed and subsequently compared using the analytical model.

A semicentralized joint cell muting and user scheduling scheme for interference coordination in a multicell network is proposed under two different temporal fairness criteria. In the proposed scheme, at a decision instant, each base station (BS) in the multicell network employs a cell‐level scheduler to nominate one user for each of its inner and outer sections and their available transmission rates to a network‐level scheduler which then computes the potential overall transmission rate for each muting pattern. Subsequently, the network‐level scheduler selects one pattern to unmute, out of all the available patterns. This decision is shared with all cell‐level schedulers which then forward data to one of the two nominated users provided the pattern they reside in was chosen for transmission. Both user and pattern selection decisions are made on a temporal fair basis. Although some pattern sets are easily obtainable from static frequency reuse systems, we propose a general pattern set construction algorithm in this paper. As for the first fairness criterion, all cells are assigned to receive the same temporal share with the ratio between the temporal share of a cell center section and that of the cell edge section being set to a fixed desired value for all cells. The second fairness criterion is based onmax-min temporal fairnessfor which the temporal share of the network‐wide worst case user is maximized. Extensive numerical results are provided to validate the effectiveness of the proposed schemes and to study the impact of choice of the pattern set.

Conventional multi-rate IEEE 802.11 Wireless LANs (WLANs) are associated with the so-called performance anomaly to describe the phenomenon of high bit rate nodes being dragged down by slower nodes. This anomaly is known to be an impediment to obtaining high cumulative throughputs despite the employment of effective link adaptation mechanisms. To cope with the performance anomaly, air-time fairness has been proposed as an alternative to throughput fairness, the latter being a main characteristic of the IEEE 802.11 Distributed Coordination Function (DCF). In this paper, we propose a novel distributed air-time fair MAC (Medium Access Control) without having to change the operation of the conventional DCF. In the proposed MAC, each node in the system runs multiple instances of the conventional DCF back-off algorithm where the number of DCF instances for the nodes can be chosen in a distributed manner. Both analytical and simulation-based results are provided to validate the effectiveness of the proposed air-time fair MAC.

In this paper, a buffer-less shared-per-wavelength optical switch is equipped with multi-fiber interfaces and operated in asynchronous context. An analytical model to evaluate loss performance is proposed using an approximate Markov-chain based approach and the model is validated by simulations. The model is demonstrated to be quite accurate in spite of the difficulty in capturing correlation effects especially for small switch sizes. The model is also applied to calculate the number of optical components needed to design the optical switch according to packet loss requirements. The impact of the adoption of multiple fiber interfaces is outlined in terms of the remarkable saving in the number of wavelength converters employed, while increasing at the same time the number of optical gates needed by the space switching subsystem. The numerical results produced are a valuable basis to optimize overall switch cost.

Optical buffers based on Fiber Delay Lines (FDL) have been proposed for contention resolution in optical packet/burst switching systems. In this article, we propose a retrial queuing model for FDL optical buffers in asynchronous optical switching nodes. In the considered system, the reservation model employed is of post-reservation type and optical packets are allowed to re-circulate over the FDLs in a probabilistic manner. We combine the MMPP-based overflow traffic models of the classical circuit switching literature and fixed-point iterations to devise an algorithmic procedure to accurately estimate blocking probabilities as a function of various buffer parameters in the system when packet arrivals are Poisson and packet lengths are exponentially distributed. The proposed algorithm is both accurate and fast, allowing one to use the procedure to dimension optical buffers in next-generation optical packet switching systems.

In this paper, we study an asynchronous optical packet switching node equipped with a number of limited range or full range wavelength converters shared per node. The packet traffic is realistically modeled by a superposition of a finite number of on-off sources as opposed to the traditional Poisson model which ignores the limited number of ports on a switch. We both study circular and non-circular limited range wavelength conversion schemes. In our simulations, we employ the far conversion policy where the optical packet is switched onto the farthest available wavelength in the tuning range, which is known to outperform the random conversion policy. We propose an approximate analytical method based on block tridiagonal Markov chains and fixed point iterations to solve for the blocking probabilities in share per node wavelength conversion systems. The method provides an accurate approximation for full range systems and acceptable results for limited range systems.

UMTS is designed to offer high bandwidth radio access with QoS assurances for multimedia communications. In particular, real-time video communications services are expected to become a successful experience under UMTS networks. In this context, a video transmission service can be designed over the basis that UMTS can provide either a constant bit rate data channel or a dynamic variable bit rate data channel adapted to load conditions. In this latter approach, which is more efficient for both the user and the service provider, multimedia sources have to be timely designed in order to adapt their output rate to the instantaneous allowed channel rate. The target of this paper is to define an analytical model of adaptive real-time video sources in a UMTS network where system resources are dynamically shared among active users.

Dynamic bandwidth reservation refers to the process of dynamically updating the bandwidth allocation to a connection between two network end points on the basis of actual aggregate traffic demand of the connection. We assume a scenario in which bandwidth updates for the connection should not be performed too frequently and the frequency of updates are thus limited to a so-called desired update rate. We propose an asynchronous model-free adaptive hysteresis algorithm for dynamic bandwidth reservations with such update frequency constraints. We validate the effectiveness of the proposed approach by comparing its bandwidth efficiency with that of a synchronous model-based dynamic bandwidth reservation mechanism from the existing literature.

In this paper, we propose a new low-complexity retransmission based optimal video streaming and rate adaptation algorithm. The proposed OSRC (Optimal packet Scheduling and Rate Control) algorithm provides average reward optimal solution to the joint scheduling and rate control problem. The efficacy of the OSRC algorithm is demonstrated against optimal FEC based schemes and results are verified over TFRC (TCP Friendly Rate Control) transport with ns-2 simulations.

In this work, we study an asynchronous optical packet/burst switching node equipped with a number of limited range wavelength converters shared per output link. A wave-length conversion policy is one by which the outgoing wavelength for an optical packet is selected if its incoming wavelength is in use. Through simulations, we show that the so-called "far conversion" policy in which the optical packet is switched onto the farthest available wavelength in the tuning range, outperforms the other policies we studied. We point out the "clustering effect" in the use of wavelengths to explain this phenomenon.

In this paper, we study the blocking probabilities in a wavelength division multiplexing-based asynchronous bufferless optical packet/burst switch equipped with a bank of tuneable wavelength converters dedicated to each output fiber line. Wavelength converter sharing, also referred to as partial wavelength conversion, corresponds to the case of a number of converters shared amongst a larger number of wavelength channels. In this study, we present a probabilistic framework for exactly calculating the packet blocking probabilities for optical packet/burst switching systems utilizing wavelength converter sharing. In our model, packet arrivals at the optical switch are first assumed to be Poisson and later generalized to the more general Markovian arrival process to cope with very general traffic patterns whereas packet lengths are assumed to be exponentially distributed. As opposed to the existing literature based on approximations and/or simulations, we formulate the problem as one of finding the steady-state solution of a continuous-time Markov chain with a block tridiagonal infinitesimal generator. To find such solutions, we propose a numerically efficient and stable algorithm based on block tridiagonal LU factorizations. We show that exact blocking probabilities can be efficiently calculated even for very large systems and rare blocking probabilities, e.g., systems with 256 wavelengths per fiber and blocking probabilities in the order of 10-40. Relying on the stability and speed of the proposed algorithm, we also provide a means of provisioning wavelength channels and converters in optical packet/burst switching systems.

In this paper, we study the blocking probabilities in a wavelength division multiplexing-based asynchronous bufferless optical burst switch equipped with a bank of tuneable wavelength converters that is shared per output link. The site of this bank is generally chosen to be less than the number of wavelengths on the link because of the relatively high cost of wavelength converters using current technologies; this case is referred to as partial wavelength conversion in the literature. We present a probabilistic framework for exactly calculating the blocking probabilities. Burst durations are assumed to be exponentially distributed. Burst arrivals are first assumed to be Poisson and later generalized to the more general phase-type distribution. Unlike existing literature based on approximations and/or simulations, we formulate the problem as one of finding the steady-state solution of a continuous-time Markov chain with a block tridiagonal infinitesimal generator. We propose a numerically efficient and stable solution technique based on block tridiagonal LU factorizations. We show that blocking probabilities can exactly and efficiently be found even for very large systems and rare blocking probabilities. Based on the results of this solution technique, we also show how this analysis can be used for provisioning wavelength channels and converters.

In this paper, dynamic capacity management refers to the process of dynamically changing the capacity allocation (reservation) of a pseudo-wire established between two network end points. This process is based on certain criteria including instantaneous traffic load for the pseudo-wire, network utilization, time of day, or day of week. Frequent adjustment of the capacity yields a scalability issue in the form of a significant amount of message processing in the network elements involved in the capacity update process. On the other hand, if the capacity is adjusted once and for the worst possible traffic conditions, a significant amount of bandwidth may be wasted depending on the actual traffic load. There is then a need for dynamic capacity management that takes into account the tradeoff between scalability and bandwidth efficiency. This problem is motivated by voice over packet networks in which end-to-end reservation requests are initiated by PSTN voice calls and these reservations are aggregated into one signal reservation in the core packet network for scalability. In this paper, we introduce a Markov decision framework for an optimal reservation aggregation scheme for voice over packet networks. Moreover, for problems with large sizes, we provide a suboptimal scheme using reinforcement learning. We show a significant improvement in bandwidth efficiency in voice over packet networks using aggregate reservations.

Several trunked private mobile radio (PMR) systems have been designed over the last decade, most of which have symmetric downlink and uplink channel capacities. These systems may not be spectrally efficient in case of group or broadcast-based voice and data calls, a common feature of PMR systems. We propose a new asymmetric PMR system comprising a wideband OFDM-based downlink and a narrowband uplink, which not only achieves a better spectral efficiency but also can support high bit rate multimedia applications. The system is shown to have high trunking efficiency since all users are assumed to use the pool of channels available in the wideband downlink. In this paper, we study the performance and capacity of a private mobile radio system using a digital audio broadcasting (DAB) downlink. In particular, we study the efficiency of such a system for voice calls using voice activity detection and statistical multiplexing. Moreover, we show that, the efficiency of the system can significantly increase, if the incoming calls, which can not find an available channel, are allowed to wait a certain amount of time before occupying a channel.

Transmission of high quality video over the Internet faces many challenges including unpredictable packet loss characteristics of the current Internet and the heterogeneity of receivers in terms of their bandwidth and processing capabilities. To address these challenges, we propose an architecture in this paper that is based on the temporally scalable and error resilient video coding mode of the H.263+ codec. In this architecture, the video frames are transported over a new generation IP network that supports differentiated services (Diffserv). We also propose a novel two rate three color promotion-capable marker (trTCPCM) to be used at the edge of the Diffserv network. Our simulation study demonstrates that an average of 30 dB can be achieved in the case of highly congested links.

This paper describes the impact of traffic handling mechanisms on network capacity for support of quality of service (QoS) in multi-service networks. The choice of which traffic handling strategy to employ requires a methodology that can be used to capture the trade-off between the different schemes and this is the focus of this paper. One key result of this work is that on the basis of capacity requirements, there is no significant difference between class-based traffic handling and per-flow traffic handling.

A general framework and architecture called differentiated services (Diffserv) has been proposed by the IETF to support service differentiation among different IP flows traversing a network. The key idea in Diffserv is to achieve scalability through handling aggregates of traffic instead of individual flows. More specifically, at the ingress edge router, each flow is shaped and classified into one of few service classes. Based on these service classes, packets are then forwarded and discarded (if necessary) with different priorities in network core routers/switches. As many network service providers today employ ATM in their backbone networks, there is tremendous interest in supporting IP Diffserv in an ATM environment. This paper presents a study on using ATM ABR service to support IP Diffserv. The idea is to use the flow control mechanism in ABR to eliminate the need for discarding packets inside the ATM network, while service differentiation among different IP flows can simply be supported by proper packet scheduling and/or discarding mechanisms at the ingress edge routers/switches. Scalability is achieved by setting up an ABR virtual circuit (VC) between each pair of ingress and egress routers rather than on a per-flow basis. A simulation study of this Diffserv framework over ATM using the Opnet simulation tool is presented to validate our idea.

We study the performance of TCP/ABR and TCP/UBR as a function of the number of bottlenecks in an IP/ATM inter-networking system. We define an efficiency metric that captures the amount of badput generated per unit of goodput. We define a gain metric to be the ratio of the efficiencies of these two services. With these new metrics, we demonstrate that the bandwidth efficiency of TCP/ABR is scalable in the number of bottlenecks, whereas TCP/UBR is scalable only if there are no greedy sources in the traffic mix. We examine the influence of ABR and UBR on TCP factors such as packet loss, round trip time delays (RTTs), and the fraction of lost packets detected via fast retransmit events. We show that TCP/ABR is more efficient than TCP/UBR because the ABR control loop has favorable effects on the TCP control loop via its its influence on RTTs and loss behavior. We demonstrate that fairness has far reaching consequences beyond throughput fairness because the improvements to TCP in efficiency and scalability are a ramification of fairness.

We present an algorithmic approach to find the stationary probability distribution of M/G/1-type Markov chains which arise frequently in performance analysis of computer and communication networks. The approach unifies finite- and infinite-level Markov chains of this type through a generalized state-space representation for the probability generating function of the stationary solution. When the underlying probability generating matrices are rational, the solution vector for level k, x/sub k/, is shown to be in the matrix-geometric form x/sub k+1/=gF/sup k/H, k/spl ges/0, for the infinite-level case, whereas it takes the modified form x/sub k+1/=g/sub 1/F/sup k//sub 1/H/sub 1/+g/sub 2/F/sup K-k-1//sub 2/H/sub 2/, 0/spl les/k/spl les/K, for the finite-level case. The matrix parameters in the above two expressions can be obtained by decomposing the generalized system into forward and backward subsystems, or, equivalently, by finding bases for certain generalized invariant subspaces of a regular pencil /spl lambda/E-A. We note that the computation of such bases can efficiently be carried out using advanced numerical linear algebra techniques including matrix-sign function iterations with quadratic convergence rates or ordered generalized Schur decomposition. The simplicity of the matrix-geometric form of the solution allows one to obtain various performance measures of interest easily, e.g., overflow probabilities and the moments of the level distribution, which is a significant advantage over conventional recursive methods.

In this paper, we present a novel algorithmic approach, the hybrid matrix geometric/invariant subspace method, for finding the stationary probability distribution of the finite quasi-birth-death (QBD) process which arises in performance analysis of computer and communication systems. Assuming that the QBD state space is defined in two dimensions with m phases and K+1 levels, the solution vector for level k, /spl pi//sub k/, 0/spl les/k/spl les/K is shown to be in a modified matrix geometric form /spl pi//sub k/=/spl upsi//sub 1/R/sub 1//sup k/+/spl upsi//sub 2/R/sub 2//sup K-k/ where R/sub 1/ and R/sub 2/ are certain solutions to two nonlinear matrix equations and /spl upsi//sub 1/ and /spl upsi//sub 2/ are vectors to be determined using the boundary conditions. We show that the matrix geometric factors R/sub 1/ and R/sub 2/ can simultaneously be obtained independently of K via finding the sign function of a real matrix by an iterative algorithm with quadratic convergence rates. The time complexity of obtaining the coefficient vectors /spl upsi//sub 1/ and /spl upsi//sub 2/ is shown to be O(m/sup 3/ log/sub 2/ K) which indicates that the contribution of the number of levels on the overall algorithm is minimal. Besides the numerical efficiency, the proposed method is numerically stable and in the limiting case of K/spl rarr//spl infin/, it is shown to yield the well-known matrix geometric solution /spl pi//sub k/=/spl pi//sub 0/R/sub 1//sup k/ for infinite QBD chain.

A large class of teletraffic analysis problems encountered in communication networks are based on Markov chains of M/G/1 and G/M/1 type, the study of which require numerically efficient and reliable algorithms to solve the nonlinear matrix equations arising in such chains. The traditional transform approach to solve these chains which requires root finding is known to cause problems when some roots are close or identical. The alternative iterative schemes based on matrix analytic methods have in general low linear convergence rates yielding a computation time bottleneck in solving large-scale probability models. We develop a novel algebraic theory for the solution of these chains based on which we propose numerically efficient algorithms. The key to our approach is an invariant subspace computation implemented using the matrix sign function iterations. These algorithms have high convergence rates unlike the linear convergence rates of existing algorithms, they are amenable to parallelization and can easily be implemented using standard linear algebra software packages.