TKK | Tietoverkkolaboratorio | Tutkimus
Abstract: The dynamic VP bandwidth management scheme developed by Mocci et al. in a series of papers calls for the calculation of the average blocking probability over a finite time interval of a system in a transient state. We develop a "precision weapon" which allows one to find the temporal evolution of the probability of the blocking state without the need to solve the probabilities of all the other states or to find the eigenvalues and eigenvectors of a very large matrix corresponding to the full system.
The full version is available here.
Abstract: In report COST257TD(97)14 we considered the technical problem of calculating the time dependent blocking probabilities for the dynamic VP bandwidth management scheme developed by Mocci et al. In this scheme, the bandwidth allocation for various VP's are updated at regular time intervals. At the beginning of an interval the system occupancy is observed and new VP capacity allocation is done in such a way that the expected time average of the blocking probability in the ensuing interval will be less than a predefined limit. In this report we assess the advantages and disadvantages of the scheme trying also to give a quantitative idea about the savings that can be achieved.
The full version is available here.
Abstract: For multiservice loss networks the calculation of the normalization constant is computationally impossible for realistic sized problems. This paper deals with two methods for simulating the loss probabilities in multiservice loss networks. The regenerative method is based on the regenerative nature of the process and the simulation is carried out by simulating the DTMC of the process. The second approach tries to combine the effectiveness of Monte Carlo simulation with the computational easiness of simulating the DTMC. Some considerations, on using importance sampling (IS) for increasing the efficiency of the simulations, are also given.
The full version is available here.
Abstract: When regenerative simulation is used for simulating blocking probabilities in loss systems, the estimator is known to be biased although strongly consistent. In this paper a method is developed for analysing the estimator's distribution as a function of increasing number of simulation cycles for the single link Erlang model. This allows us to examine in detail the effect of the choice of the regeneration state to the accuracy of the estimator in terms of its expected value and standard deviation. Some considerations on how the multiservice case can be analyzed are given as well.
The full version is available here.
Abstract: In this paper, a method for calculating blocking experienced by dynamic multicast connections in a single link is presented. An originating office provides a number of channels distributed to the users by multicast subtrees which evolve dynamically as users join and leave the channels. We reduce this problem to a generalized Engset system with unidentical users and generally distributed holding times, and derive the call and channel blocking probabilities as well as the link occupancy distribution.
Abstract: In this article we consider the problem of calculating the blocking probabilities of calls in a multiservice network by using simulation. The traditional approaches suffer from the fact that the state space explosion inherent in the system causes their efficiency to decrease correspondingly. We develop a method that alleviates the effect of the state space explosion. The method is based on using the so called Gibbs sampler to generate a Markov chain with the desired stationary distribution. In particular, by making an additional "virtual" step from each state and calculating the expected contribution from this step analytically, we are able to collect information from a subset of the whole state space for each generated sample. This leads to a smaller variance of the estimate for a given computational effort.
The full version is available here.
Abstract: In this paper we consider the use of traditional Monte Carlo simulation techniques for estimating very small blocking probabilities in multiservice loss systems. We derive an efficient sampling distribution, which has a composite form consisting of a weighted combination of exponentially twisted distributions. In the literature the composite distribution has been shown to be asymptotically efficient in systems such as the multiservice loss system. However, the asymptotic theory leaves open the question of how to choose the weights. For that we give heuristics to minimize the variance of the estimator by making the likelihood ratio as constant as possible in the set of the blocking states.
The full version is available here.
Abstract: ...
Abstract: ...
Abstract: The paper deals with tree-structured point-to-multipoint networks, where users from infinite user populations at the leaf nodes subscribe to a variety of channels, offered by one source. The users joining the network form dynamic multicast connections that share the network resources. An exact algorithm for calculating end-to-end call blocking probabilities for dynamic connections is devised for this multicast model. The algorithm is based on the well-known algorithm for calculating blocking probabilities in hierarchical multiservice access networks, where link occupancy distributions are alternately convolved and truncated. The resource sharing of multicast connections requires the modification of the algorithm by using a new type of convolution, the OR-convolution. The exact algorithm for end-to-end call blocking probabilities enables us to study the accuracy of earlier results based on Reduced Load Approximation. The model is further extended to include background traffic, allowing the analysis of networks carrying mixed traffic e.g. multicast and unicast traffic.
The full version is available here.
Abstract: In this paper we consider the problem of estimating blocking probabilities in the multiservice loss system via simulation, applying the static Monte Carlo method with importance sampling. Earlier approaches to this problem include the use of either a single exponentially twisted version of the steady state distribution of the system or a composite of individual exponentially twisted distributions. Here, a different approach is introduced, where the original estimation problem is first decomposed into independent simpler sub-problems, each roughly corresponding to estimating the blocking probability contribution from a single link. Then two importance sampling distributions are presented, which very closely approximate the ideal importance sampling distribution for each sub-problem. In both methods, the idea is to try to generate samples directly into the blocking state region. The difference between the methods is that the first method, the inverse convolution method, achieves this exactly, while the second one, using a fitted Gaussian distribution, only approximately. The inverse convolution algorithm, however, has a higher memory requirement. Finally, a dynamic control algorithm is given for optimally allocating the samples between different sub-problems. The numerical results demonstrate that the variance reduction obtained with the methods, especially with the inverse convolution method, is truly remarkable, between 400 and 500 000 in the considered examples.
The full version is available here.
Abstract: One of the activities of the ACTS project EXPERT is to perform trials demonstrating the use of advanced Resource Management and Routing (RM&R) algorithms in ATM networks. The RM&R model chosen for those trials is based on the Virtual Trunk (VT) concept. In ATM networks, a VT is a path connection setup by the network for reducing connection awareness at the transit nodes. A virtual trunk is considered as a connection by the network supporting it (the VP network), and as a logical trunk by the connections supported. In this context, VTs are considered to be VBR connections. In order to adapt the VT level to the changes in traffic, we use dynamic virtual trunks. In this paper, we compare the VBR-over-VBR approach mentioned above to a more traditional VBR-over-CBR approach. The comparison is based on the simulations performed in the EXPERT project by WP3.2. In addition, a dynamic VP bandwidth allocation method is demonstrated by simulations.
Abstract: We consider the ordinary M/M/1 queue with the FIFO queueing discipline. It seems that the sum of service times of the customers in the system (or the required work, as we call it briefly) is a random variable that is not considered before. In this paper we derive the equilibrium distribution of this variable. The task is not quite trivial because of the dependencies between the elapsed service time and the number of customers in the system. Our motivation for this problem comes from the performance analysis of a dynamic memory allocation scheme of a packet buffer.
Abstract: Multicast connections have a bandwidth saving nature. This means that a multicast connection --- in taking the form of a tree where streams merge at the nodes --- requires much less capacity from the network links than a bunch of separate point-to-point connections providing the same connectivity. In this paper, we consider dynamic multicast connections that can be used to model, for example, TV or radio delivery on a telecommunication network, such as an ATM network with virtual circuits. The model consists of a single multicast tree, whose root is called the originating office and leaves are called users. The originating office offers the users a set of programs, called channels. The programs run independently of their subscribers, who can join and leave the channel any time. The connections that deliver a specific channel to a group of users form a dynamic subtree of the multicast tree.
Because of the dynamic nature of the multicast connections, the traditional methods for calculating blocking probabilities, such as the Kaufman-Roberts recursion, are not adequate in our case. Thus, new methods are needed. Our purpose in this paper is to show how to calculate these blocking probabilities, first in a separate link, and then in the whole network. As regards the former case, we derive exact formulae for the blocking probabilities by mapping the problem to an equivalent generalized Engset system with unidentical users and generally distributed holding times. Reduced Load Approximation is used for estimating the blocking probabilities in the whole network. The accuracy of the estimation method is studied by simulations.
Abstract: In this paper, a method for calculating blocking experienced by dynamic multicast connections in a single link is presented. An originating office provides a number of channels distributed to the users by multicast subtrees which evolve dynamically as users join and leave the channels. We reduce this problem to a generalized Engset system with unidentical users and generally distributed holding times, and derive the call and channel blocking probabilities as well as the link occupancy distribution.
The full version is available here.
Abstract: In this article we consider the problem of calculating the blocking probabilities of calls in a multiservice network by using simulation. Traditional simulation methods become computationally intensive as the state space grows. We develop a method that alleviates this problem. The method is based on using the so called Gibbs sampler to generate a Markov chain with the desired stationary distribution. In particular, by making an additional "virtual" step from each state and calculating the expected contribution from this step analytically, we are able to collect information from a subset of the state space for each generated sample. This leads to a smaller variance of the estimate for a given computational effort.
Abstract: We consider the calculation of time-dependent blocking probabilities in the M/M/n/n loss system. We present a new method which allows one to find the temporal evolution of the probability of any given state, and, in particular, that of the blocking state without the need to solve the probabilities of all the other states or to find the eigenvalues and eigenvectors of a very large matrix corresponding to the full system. The problem is motivated by a dynamic VP bandwidth management scheme of an ATM network with full traffic segregation.
The full version is available here.
Abstract: In a batch service queueing system customers are served in batches not greater than the service capacity. We consider the optimal control problem of such queueing systems with finite service capacity. The control problem involves the determination of the epochs at which the service is initiated as well as the sizes of the batches served. In the literature optimal solutions for this control problem have been found either by requiring that the holding costs be linear or the service capacity be infinite. However, recent studies made by the author have shown that, by considering the so called non-trivial service epochs, it is possible to solve the optimal control problem with more general holding costs and finite service capacity. In this presentation we review the most important results found by the author in this research area, and point out the questions still open.
Abstract: We discuss efficient Monte Carlo simulation techniques for estimating performance measures of product form systems, e.g. the multiservice loss system. First, two methods for generating the samples are discussed, the traditional Monte Carlo and the so called Gibbs sampler. Then a variance reduction method, the conditional expectation method, is presented where the idea is to utilize known analytical results to the maximum degree. This is possible for systems with a product form probability distribution for which conditional one-dimensional expectations can easily be precomputed. The method is independent of the way the samples are generated. Finally, we study the use of heuristic importance sampling distribution in connection with the traditional Monte Carlo method and the conditional expectation method.
The full version is available here.
Abstract: With wavelength division multiplexing (WDM) several optical signals can be transferred in a single optical fiber. This technology allows more efficient use of the huge capacity of an optical fiber but also poses new network design and management problems, especially when wavelength conversion is not possible in the nodes. In this paper we consider the routing and wavelength assignment problem in such networks. Once routes are fixed the wavelength assignment is essentially a graph coloring problem. Several heuristic methods for coloring a given graph are studied. Also an iterative algorithm for finding a reasonably good routing and wavelength assignment is represented and tested with fully connected networks.
The full version is available here.
Abstract: Caches provide an important means for reducing latency times experienced by the users. This paper gives a short review of the most important arrival modules and some basic results related to these. The three arrival models are the Independent Reference Model (IRM), the Least Recently Used (LRU) stack model and the renewal model. We also discuss the problem of good replacement algorithm and, more specifically, study the performance of a set of algorithms by simulation, assuming renewal arrival process.
The full version is available here.
Abstract: With standard assumptions the routing and wavelength assignment problem (RWA) can be viewed as a Markov Decision Process (MDP). The problem, however, defies an exact solution because of the huge size of the state space. Only heuristic algorithms have been presented up till now. In this paper we propose an approach where, starting from a given heuristic algorithm, one obtains a better algorithm by the first policy iteration. In order to estimate the relative costs of states, we make a simulation on the fly studying, at each decision epoch, the consequences of all the alternatives actions. Being computationally intensive, this method can be used in real time only for systems with slow dynamics. Off-line it can be used to assess how close the heuristic algorithms come to the optimal policy. Numerical examples are given about the policy improvement.
Abstract: The routing and wavelength assignment problem (RWA) in WDM network can be viewed as a Markov Decision Process (MDP). The problem, however, defies calculation of the exact solution because of the huge size of the state space. Several heuristic algorithms have been presented in the literature. Generally, these algorithms, however, do not take into account the available extra information about the traffic, e.g. inhomogeneous arrival rates. In this paper we propose an approach where, starting from a given heuristic algorithm, one obtains a better algorithm by the first policy iteration. At each decision epoch a decision analysis is made where the costs of all the alternative actions are estimated by simulations on the fly. Being computationally intensive, this method can be used in real time only for systems with slow dynamics. Off-line it can be used to assess how close the heuristic algorithms come to the optimal policy. Numerical examples are given about the policy improvement.
Abstract: A variance reduction method for Monte Carlo type simulations is presented. The idea is to utilize known analytical results to the maximum degree. This is possible for systems with a product form probability distribution for which conditional one-dimensional expectations can easily be precomputed.
Abstract: We consider the calculation of blocking probabilities in multicast trees with dynamic membership. We extend the work by Karvo et al., where an approximate algorithm based on the Reduced Load Approximation was given to calculate end-to-end blocking for infinite sized user populations in multicast networks. The new end-to-end call blocking algorithm for an arbitrary sized user population is based on the known blocking probability algorithm in hierarchical multiservice access networks, where link occupancy distributions are alternately convolved and truncated. We show that the algorithm can be applied to multicast trees embedded in a network with an arbitrary topology carrying also non-multicast traffic. The resource sharing of multicast connections, however, requires the modification of the algorithm by using a new type of convolution, the OR-convolution. In addition, we discuss several different user population models for which the algorithm is applicable.
The full version is available here.
Abstract: The purpose of this work is to examine the performance if Simple Integrated Media Access (SIMA) with simulation. Specifically of interest is to see how the users influence the dynamics of the system.
The full version is available here.
Tietoverkkolaboratorio on nyt osa Tietoliikenne- ja tietoverkkotekniikan laitosta. Tällä sivulla oleva tieto voi olla vanhentunutta.
|
Tämän sivun sisällöstä vastaavat ja
Webmaster.
Sivua on viimeksi päivitetty 26.10.2001 17:26. URI: http://www.netlab.tkk.fi/tutkimus/cost257/abstract.shtml [ TKK > Sähkö- ja tietoliikennetekniikan osasto > Tietoverkkolaboratorio > Tutkimus ] |