A Complete Solution to Spectrum Problem for Five‐Vertex Graphs with Application to Traffic Grooming in Optical Networks

A G‐design of order n is a decomposition of the complete graph on n vertices into edge‐disjoint subgraphs isomorphic to G. Grooming uniform all‐to‐all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph on n vertices into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The existence spectrum problem of G‐designs for five‐vertex graphs is a long standing problem posed by Bermond, Huang, Rosa and Sotteau in 1980, which is closely related to traffic groomings in optical networks. Although considerable progress has been made over the past 30 years, the existence problems for such G‐designs and their related traffic groomings in optical networks are far from complete. In this paper, we first give a complete solution to this spectrum problem for five‐vertex graphs by eliminating all the undetermined possible exceptions. Then, we determine almost completely the minimum drop cost of 8‐groomings for all orders n by reducing the 37 possible exceptions to 8. Finally, we show the minimum possible drop cost of 9‐groomings for all orders n is realizable with 14 exceptions and 12 possible exceptions.     

Optimal Groomings with Grooming Ratios Six and Seven

Grooming uniform all‐to‐all traffic in optical (SONET) rings with grooming ratio C requires the determination of a decomposition of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The determination of optimal C‐groomings has been considered for , and completely solved for . For , it has been shown that the lower bound for the drop cost of an optimal C‐grooming can be attained for almost all orders with 5 exceptions and 308 possible exceptions. For , there are infinitely many unsettled orders; especially the case is far from complete. In this paper, we show that the lower bound for the drop cost of a 6‐grooming can be attained for almost all orders by reducing the 308 possible exceptions to 3, and that the lower bound for the drop cost of a 7‐grooming can be attained for almost all orders with seven exceptions and 16 possible exceptions. Moreover, for the unsettled orders, we give upper bounds for the minimum drop costs.     

高负荷下带重尾服务强占优先排队的扩散逼近

考虑的排队系统是单服务台,顾客的初始到来是依泊松过程来到服务台,顾客的服务时间是重尾分布,服务的原则是强占优先服务.在高负荷条件下对此模型进行研究,获得了系统中的负荷过程,离去过程和队长过程的扩散逼近.     

Dynamic routing in open queueing networks: Brownian models,cut constraints and resource pooling

We present an introductory review of recent work on the control of open queueing networks. We assume that customers of different types arrive at a network and pass through the system via one of several possible routes; the set of routes available to a customer depends on its type. A route through the network is an ordered set of service stations: a customer queues for service at each station on its route and then leaves the system. The two methods of control we consider are the routing of customers through the network, and the sequencing of service at the stations, and our aim is to minimize the number of customers in the system. We concentrate especially on the insights which can be obtained from heavy traffic analysis, and in particular from Harrison's Brownian network models. Our main conclusion is that in many respects dynamic routingsimplifies the behaviour of networks, and that under good control policies it may well be possible to model the aggregate behaviour of a network quite straightforwardly.Supported by SERC grant GR/F 94194.     

Heavy and light traffic in fluid models with burst arrivals

We consider the problem of finding a heavy and light traffic limits for the steady-state workload in a fluid model having a continuous burst arrival process. Such a model is useful for describing (among other things) the packetwise transmission of data in telecommunications, where each packet is approximated to be a continuous flow. Whereas in a queueing model, each arrival epoch,t _n , corresponds to a customer with a service timeS _n , the burst model is different: each arrival epoch,t _n , corresponds to a burst of work, that is, a continuous flow of work (fluid, information) to the system at rate 1 during the time interval [t _n ,t _n +S _n ]. In the present paper we show that the burst and queueing models share the same heavy-traffic limit for work, but that their behavior in light traffic is quite different.Research supported by the Japan Society for the Promotion of Science, during the author's fellowship in Tokyo.Research funded by C & C Information Technology Research Laboratories, NEC, and the International Science Foundation.     

On the Moments of Overflow and Freed Carried Traffic for the GI/M/C/0 System

In circuit-switched networks call streams are characterized by their mean and peakedness (two-moment method). The GI/M/C/0 system is used to model a single link, where the GI-stream is determined by fitting moments appropriately. For the moments of the overflow traffic of a GI/M/C/0 system there are efficient numerical algorithms available. However, for the moments of the freed carried traffic, defined as the moments of a virtual link of infinite capacity to which the process of calls accepted by the link (carried arrival process) is virtually directed and where the virtual calls get fresh exponential i.i.d. holding times, only complex numerical algorithms are available. This is the reason why the concept of the freed carried traffic is not used. The main result of this paper is a numerically stable and efficient algorithm for computing the moments of freed carried traffic, in particular an explicit formula for its peakedness. This result offers a unified handling of both overflow and carried traffics in networks. Furthermore, some refined characteristics for the overflow and freed carried streams are derived.     

由路段交通量推算OD矩阵的一种有效方法及其应用

针对现有OD矩阵估计方法的不足，本讨论了一种新的有效的估计方法，它包括一个路段流量的预处理过程，以消除路段观测流量的不相容，然后经过流量加载和卸载两个逆过程，进行反复迭代，最终得到再现路段交通量的OD矩阵，中例证了该方法的有效性。     

Inequalities for the Moments and Distribution of the Ladder Height of a Random Walk

We obtain upper bounds for the tail distribution of the first nonnegative sum of a random walk and for the moments of the overshoot over an arbitrary nonnegative level if the expectation of jumps is positive and close to zero. In addition, we find an estimate for the expectation of the first ladder epoch.     

The Law of the Iterated Logarithm for Extreme Waiting Time in Multiphase Queueing Systems

The objective of this research in the queueing theory is the law of the iterated logarithm (LIL) under the conditions of heavy traffic in multiphase queueing systems (MQS). In this paper, the LIL is proved for the extreme values of some important probabilistic characteristics of the MQS, namely, maxima and minima of the summary waiting time of a customer, and maxima and minima of the waiting time of a customer.