American Institute of Mathematical Sciences

ISSN:
2155-3289

eISSN:
2155-3297

All Issues

Numerical Algebra, Control & Optimization

2011 , Volume 1 , Issue 4

Dedicated to Professor Yutaka Takahashi on the occasion of his 60th birthday

Select all articles

Export/Reference:

2011, 1(4): i-ii doi: 10.3934/naco.2011.1.4i +[Abstract](1229) +[PDF](33.7KB)
Abstract:
This Special Issue of Numerical Algebra, Control and Optimization (NACO) is dedicated to Professor Yutaka Takahashi on the occasion of his 60th birthday and in recognition of his fundamental contributions in queueing theory and network applications. It is a great honor and a pleasure for the Guest Editors to have this privilege to edit this Special Issue.

2011, 1(4): 563-576 doi: 10.3934/naco.2011.1.563 +[Abstract](1252) +[PDF](247.9KB)
Abstract:
In delay tolerant networks (DTNs), the opportunity of communication among isolated networks (clusters) can be provided by a message ferry which moves around the network to proactively collect bundles and deliver them to a sink node. When there are lots of distant static clusters, the message ferry should visit them efficiently to minimize the mean delivery delay of bundles. In this paper, we propose an algorithm for determining the optimal visiting order of isolated static clusters in DTNs. We show that the minimization problem of the overall mean delivery delay in our system is reduced to that of the weighted mean waiting time in the conventional polling model. We then solve the problem with the help of an existing approach to the polling model and obtain a quasi-optimal balanced sequence representing the visiting order. Through numerical examples, we show that the proposed visiting order is effective when arrival rates at clusters and/or distances between clusters and the sink are heterogeneous.
2011, 1(4): 577-592 doi: 10.3934/naco.2011.1.577 +[Abstract](1777) +[PDF](263.8KB)
Abstract:
In multi-hop wireless networks, broadcasting with flooding causes significant packet loss and battery power consumption, which is referred to as the broadcast storm problem. In this paper, we consider the broadcast storm problem in a broadcasting system in which each node generates a new packet periodically as in routing protocols. In order to resolve the problem, we apply network coding, which can reduce the number of forwarded packets by encoding several packets into a single packet at intermediate nodes. We propose a broadcasting system called asynchronous multiple-source network coding (AMSNC), where nodes encode received packets asynchronously generated from different source nodes. In order to apply multiple-source network coding to large multi-hop wireless networks, AMSNC has two mechanisms: timer-based coding scheduling and packet header format with compressed coding vector. With the timer-based coding scheduling, AMSNC effectively encodes packets asynchronously generated at source nodes. Further, with the packet header format with a compressed coding vector, we resolve the overhead problem, where the length of coding vectors becomes long in large multi-hop wireless networks. Simulation results show that AMSNC reduces the number of forwarded packets significantly and improves packet loss rate, end-to-end delay, and radio resource consumption.
2011, 1(4): 593-610 doi: 10.3934/naco.2011.1.593 +[Abstract](1727) +[PDF](257.1KB)
Abstract:
Voice over Internet protocol (VoIP) services using peer-to-peer (P2P) technology have become popular in recent years. In P2P-based VoIP networks such as Skype and P2P session initiation protocol (P2PSIP), super nodes are chosen from among all ordinary end-user nodes and handle particular tasks such as the management of user information, call establishment, and traffic relay. Future communication networks based on P2P technology must support a huge number of user nodes. A fundamental analysis of the load distribution in decentralized user-information management is needed to develop efficient and robust communication networks. In this paper, we analyze the performance of the P2P-based dynamic load distribution. In our analytical model, new nodes join the network according to a nonstationary Poisson process, and the stochastic behavior of the number of online nodes is analyzed approximately with an M($t$)/M/$\infty$ queue. We focus on two performance measures that significantly affect the quality of service (QoS) provided to the users: the churn rate and the load of super nodes. Numerical examples show that the performance of the P2P-based VoIP networks is sensitive to the sojourn time of super nodes and the maximum number of nodes managed by a super node.
2011, 1(4): 611-626 doi: 10.3934/naco.2011.1.611 +[Abstract](1474) +[PDF](216.3KB)
Abstract:
On-demand video streaming services have become popular in recent years. In current streaming services, however, the growth of user population leads to the lack of the upload rate of the video server. This mainly causes starvation in the playout buffer at a client, resulting in the degradation of user-level quality of service (QoS). In this paper, we consider an on-demand streaming service based on a peer-to-peer (P2P) technology. Focusing on the stochastic behavior of streaming data contents in the playout buffer at a client peer, we consider an analytical stochastic fluid model, which takes into account the heterogeneity among peer nodes and the peer churn. We derive the starvation probability that the playout buffer is empty. Numerical examples show that the starvation probability increases when the population of peer nodes grows. It is also shown that even when the population of peer nodes is extremely large, a small increase in the upload rate at ordinary-peer nodes significantly improves the QoS of P2P streaming services.
2011, 1(4): 627-638 doi: 10.3934/naco.2011.1.627 +[Abstract](1331) +[PDF](351.4KB)
Abstract:
In this paper, we propose a Call Admission Control (CAC) scheme by dynamic bandwidth reservation where a new call is admitted only when both the remaining resource units at the serving Base Station (BS) excluding the resource units of ongoing calls in the BS and the reserved resource units of anticipated incoming handoff calls from direct neighbor cell is enough to accommodate the new call, and when the next cell for this call to visit has enough resource units to accommodate the new call. The proposed call admission control incorporates both mobile information such as position, speed, and next cell to visit by using bidirectional navigator and road layout information. Simulation results show that the handoff call dropping probability and new call blocking probability of our proposed CAC scheme are lower than an existing similar CAC scheme, respectively. To show the practicality of the assumption of having bidirectional navigator for each Mobile Station (MS), we give a simulation where some MSs have bidirectional navigators and some MSs don't have. The simulation results show that more MSs with bidirectional navigators, less the new call blocking probability, while keeping handoff call dropping probability at the same level.
2011, 1(4): 639-656 doi: 10.3934/naco.2011.1.639 +[Abstract](1581) +[PDF](280.2KB)
Abstract:
This paper considers a multiserver queueing system with finite capacity. Customers that find the service facility being fully occupied are blocked and enter a virtual waiting room (called orbit). Blocked customers stay in the orbit for an exponentially distributed time and retry to occupy an idle server again. After completing a service, the server starts an additional job that we call an after-call work. We formulate the queueing system using a continuous-time level-dependent quasi-birth-and-death process, for which a sufficient condition for the ergodicity is derived. We obtain an approximation to the stationary distribution by a direct truncation method whose truncation point is simply determined using an asymptotic analysis of a single server retrial queue. Some numerical examples are presented in order to show the influence of parameters on the performance of the system.
2011, 1(4): 657-673 doi: 10.3934/naco.2011.1.657 +[Abstract](1280) +[PDF](228.6KB)
Abstract:
Supporting different services with different Quality of Service (QoS) requirements is not an easy task in modern telecommunication systems: an efficient priority scheduling discipline is of great importance.~Fixed or static priority achieves maximal delay differentiation between different types of traffic, but may have a too severe impact on the performance of lower-priority traffic.~In this paper, we propose a priority scheduling discipline with priority jumps to control the delay differentiation.~In this scheduling discipline, packets can be promoted to a higher priority level in the course of time.~We use probability generating functions to study the queueing system analytically.~Some interesting mathematical challenges thereby arise.~With some numerical examples, we finally show the impact of the priority jumps and of the system parameters.
2011, 1(4): 675-689 doi: 10.3934/naco.2011.1.675 +[Abstract](1621) +[PDF](226.6KB)
Abstract:
Recently various schedulers exploiting multiuser diversity in wireless networks have been proposed and studied. Although the utilization of multiuser diversity can increase the information theoretic capacity, there exists a tradeoff between the capacity and fairness. Among schedulers exploiting multiuser diversity, the one-bit feedback fair scheduler is considered as an attractive choice for the reduction of feedback overheads and the ease of implementation. In this paper, we study the short term fairness of the one-bit feedback fair scheduler. Since the short term fairness has a strong impact on the quality-of-service of each mobile station, it is important to examine the short term fairness properties of the scheduler. As a short term fairness index, we consider the statistical time-access fairness index (STAFI). We then develop two numerical methods to estimate the STAFI of the scheduler. The first method calculates the exact value of the STAFI by using the inverse discrete FFT method. The second method estimates the asymptotic decay rate of the STAFI by using the theory of large deviations. Numerical results show that the threshold value of the one-bit feedback fair scheduler greatly affects its short term fairness properties.
2011, 1(4): 691-711 doi: 10.3934/naco.2011.1.691 +[Abstract](1464) +[PDF](274.7KB)
Abstract:
In this paper, we analyze a single server queueing system $C_k/C_m/1$. We construct a general solution space of vector product-forms for steady-state probability and express it in terms of singularities and vectors of the fundamental matrix polynomial $\textbf{Q}(\omega)$. It is shown that there is a strong relation between the singularities of $\textbf{Q}(\omega)$ and the roots of the characteristic polynomial involving the Laplace transforms of the inter-arrival and service times distributions. Thus, some steady-state probabilities may be written as a linear combination of vectors derived in expression of these roots. In this paper, we focus on solving a set of equations of matrix polynomials in the case of multiple roots. As a result, we give a closed-form solution of unboundary steady-state probabilities of $C_k/C_m/1$, thereupon considerably reducing the computational complexity of solving a complicated problem in a general queueing model.
2011, 1(4): 713-725 doi: 10.3934/naco.2011.1.713 +[Abstract](1381) +[PDF](233.7KB)
Abstract:
We consider a stationary single-server queue with preemptive-resume last-come, first-served (LCFS-PR) queueing discipline. The LCFS-PR single-server queue has some interesting properties and has been studied in the literature. In this paper, we generalize the previous results such that the input process to the queue is given as a general stationary marked point process and derive some formulas concerning the joint distribution of queue length and remaining service times of respective customers in the system at arbitrary time instances as well as at arrival instances. The tool for derivation is the Palm-martingale calculus; that is, the connection between the notion of Palm probability and that of stochastic intensity.
2011, 1(4): 727-747 doi: 10.3934/naco.2011.1.727 +[Abstract](1422) +[PDF](429.4KB)
Abstract:
Addressing the bandwidth inefficiency problem of current IP over DWDM backbone switching, Optical Packet/Burst Switching (OPS/OBS) provide viable solutions, capitalizing on statistical multiplexing gain, through packet-oriented scheduling. To resolve packet/burst contention, the involved photonic switches contain wavelength converters and fiber delay lines, controlled through a channel and delay selection (CDS) algorithm. Recently proposed CDS algorithms all rely on heuristics, of which the optimality is unexamined to date.
This paper presents an in-depth analysis of the optimality of CDS algorithms. Methodologically, we rely on Markov chain analysis for performance evaluation, combined with a discrete Markov Decision Process formulation of the optimization problem, optimized for fast calculation, allowing to determine the exact optimum of a specific given setting of the switch, through numerical algebra solution techniques. Results point out that, for the basic switch setting assumed, of all known CDS algorithms, an algorithm called MING (MINimal Gap) is close to optimal, but never strictly optimal. Various graphs support this, showing that an algorithm optimal for any traffic load cannot (in general) be devised. Results for several other switch settings further confirm this, showing how known CDS algorithms might be modified, to attain improved control robustness.
2011, 1(4): 749-761 doi: 10.3934/naco.2011.1.749 +[Abstract](1632) +[PDF](224.3KB)
Abstract:
In this paper, the principle of connection oriented service in the next generation Internet is analyzed. Considering the finite capacity, a Geom/ G/1/K queueing model with Setup, Close Delay and Close Down is built based on the operating mechanism of the connection oriented service. By using the approach of embedded Markov chain and supplementary variable, this queueing model is analyzed. The probability distribution of the queue length and the Probability Generating Function (P.G.F.) of waiting time are derived under the steady state. Correspondingly, the performance measures in terms of average response time, blocking probability and system throughput of this connection oriented Internet service are given to describe the dependency relationships between these measures and the time length $T$ of the Close Delay timer mathematically. Both of the analytical results and the simulation results are provided to investigate and validate the influence of the system parameters on the system performance. The research work in this paper can provide theoretic bases for network design, network maintenance, network management and capacity design of the next generation network systems.
2011, 1(4): 763-780 doi: 10.3934/naco.2011.1.763 +[Abstract](1572) +[PDF](920.9KB)
Abstract:
While feeling honoured for being invited to write a paper dedicated to Prof. Yutaka Takahashi, I was enthusiastically wondering how to connect my current research on sensor networks to his excellent professional profile. The question or, better, the answer, was not simple. Considering, for instance, the field of Markov chains, as far as I know there are hardly works in literature that use this well-known modelling paradigm to represent the operational states of a sensor network. However, in a very recent work on time-driven sensor networks, I proposed the exponential randomization of the sense-and-transmit process, in order to avoid tight synchronization requirements while preserving good expectations in terms of lifetime and reconstruction quality. But$\ldots{}$oh, I said exponential, that's the connection! $\ldots{}$ So, specifically, in this paper a Markov chain is constructed to characterize the activity of a node in a time-driven sensor network based on stochastic (exponential) sampling. Since this activity can be translated to energy consumption, the exact solution to the Markov chain yields the complete statistical distribution of node lifetime. The effects of several parameters on the average and variance of this lifetime are also analyzed in detail.
2011, 1(4): 781-816 doi: 10.3934/naco.2011.1.781 +[Abstract](1434) +[PDF](632.4KB)
Abstract:
A generic maximum entropy (ME) product-form approximation is proposed for arbitrary single class open first-come-first-served (FCFS) queueing network models with blocking (QNMs-B), subject to bursty GE-type interarrival and service times and the mixed blocking mechanisms (BMs) of Blocking-After-Service (BAS), Blocking-Before-Service (BBS) and Repetitive-Service (RS) Blocking with Random (RS-RD) and Fixed (RS-FD) destinations. A new GE-type analytic framework is devised, based on the ME analysis of a virtual multiple class GE/GE/1/N+U queueing system with finite capacity, $N (N>1)$ augmented by $U (U\geq1)$ auxiliary-waiting lines, to determine the first two moments of BAS- and BBS-dependent effective service times towards a node-by-node decomposition of the entire network. In this context, a unified ME algorithm is devised for the approximate analysis of arbitrary open FCFS QNMs-B with a mixture of the BMs of BAS, BBS, RS-RD and RS-FD. Typical numerical tests are carried out to assess the credibility of the unified ME algorithm against discrete event simulation and also establish GE-type experimental performance bounds. A critique on the feasibility of ME formalism for QNMs-B and suggested extensions are included.