Explicit construction of regular graphs without small cycles

For every integerd>2 we give an explicit construction of infinitely many Cayley graphsX of degreed withn(X) vertices and girth >0.4801...(logn(X))/log (d−1)−2. This improves a result of Margulis. Dedicated to Paul Erdős on his seventieth birthday     

A multibus train communication (AMTRAC) architecture for high-speedfiber optic networks

A multibus train (ordered demand assignment) communication architecture, using the AMTRAC protocol (for efficient utilization of fiber-optic-based very-high-speed networks) is presented. Taking advantage of the emerging WDM (wavelength-division multiplexing) and FDM (frequency-division multiplexing) technologies, the proposed solution introduces a coordinated multichannel control combining the performance advantages of two known approaches for high-speed communication: multichannel and train protocols. As a result an AMTRAC-based high-speed network achieves channel utilization significantly higher than previous approaches. For a network consisting of N stations, with propagation delay to packet transmission time ratio given by a, the AMTRAC architecture reaches a capacity of 1/(1+a/N ²)     

Channel allocation protocols in frequency-time controlled highspeed networks

In conventional high-speed systems, the high ratio between the end-to-end propagation delay and the message transmission time severely restricts the system performance. Thus, the increase in channel bandwidth may be accompanied by only a marginal increase in actual system capacity. A combined frequency-time division-based control of the high-speed channel that significantly reduces this problem is proposed. The design of protocols subject to the unique channel control penalties of the resulting multichannel system is considered. The allocation of channels on a demand assignment basis is hindered in the multichannel configuration by the time penalty involved in locating an idle channel and by practical limitations on the transmit/receive multichannels mode interface. A new class of fixed allocation protocols is introduced in which the channel access is obtained without the aforementioned penalties. The protocols build on the allocation of source and destination oriented transmission rights, taking into account the implementation aspects of multichannel networks. It is shown that this class of protocols covers the whole range of random-access to fixed-channel-access control policies. An analytic approach for a uniform analytic treatment is introduced, showing the potential for a significant improvement in the system capacity and the average message delay     

Overflow control for UMTS high-speed downlink packet access

This paper proposes overflow control schemes to support high-speed downlink packet access (HSDPA) mechanism in the universal mobile telecommunication system (UMTS). To access the UMTS services, a user equipment (UE) communicates with all cells (base stations) in an active set. However, multiple links between the UE and the cells in the active set may reduce the transmission speed due to interference. Third-Generation Partnership Project specification TR 25.950 proposes HSDPA. In this mechanism, the UE only selects one cell (referred to as the serving cell) in the active set for high-speed downlink transmission. In HSDPA, the radio network controller sends the packet frames to the cells in the active set. For the serving cell, the packet frames are forwarded to the UE. On the other hand, every nonserving cell in the active set queues the packet frames in a buffer. If the link quality between the serving cell and the UE degrades below some threshold, the UE selects the best cell in the active set as the new serving cell. Since the nonserving cells do not send packet frames to the UE, their buffers may overflow. In this paper, we propose schemes to address the buffer overflow issue. Our schemes guarantee that when the buffer of a nonserving cell is full, the previously received packet frames in the buffer can be safely dropped, and after the UE has switched wireless link to the new serving cell, no packet frames are lost.     

Wavelength converter placement under different RWA algorithms in wavelength-routed all-optical networks

Sparse wavelength conversion and appropriate routing and wavelength assignment (RWA) algorithms are the two key factors in improving the blocking performance in wavelength-routed all-optical networks. It has been shown that the optimal placement of a limited number of wavelength converters in an arbitrary mesh network is an NP-complete problem. There have been various heuristic algorithms proposed in the literature, in which most of them assume that a static routing and random-wavelength assignment RWA algorithm is employed. However, the existing work shows that fixed-alternate routing and dynamic routing RWA algorithms can achieve much better blocking performance. Our study further demonstrates that the wavelength converter placement and RWA algorithms are closely related in the sense that a well-designed wavelength converter placement mechanism for a particular RWA algorithm might not work well with a different RWA algorithm. Therefore, the wavelength converter placement and the RWA have to be considered jointly. The objective of this paper is to investigate the wavelength converter placement problem under the fixed-alternate routing (FAR) algorithm and least-loaded routing (LLR) algorithm. Under the FAR algorithm, we propose a heuristic algorithm called minimum blocking probability first for wavelength converter placement. Under the LLR algorithm, we propose another heuristic algorithm called weighted maximum segment length. The objective of the converter placement algorithms is to minimize the overall blocking probability. Extensive simulation studies have been carried out over three typical mesh networks, including the 14-node NSFNET, 19-node EON, and 38-node CTNET. We observe that the proposed algorithms not only outperform existing wavelength converter placement algorithms by a large margin, but they also can achieve almost the same performance compared with full wavelength conversion under the same RWA algorithm.     

On automorphism groups of Cayley graphs

LetX _G,H denote the Cayley graph of a finite groupG with respect to a subsetH. It is well-known that its automorphism groupA(X_G,H) must contain the regular subgroupL _G corresponding to the set of left multiplications by elements ofG. This paper is concerned with minimizing the index [A(X_G,H)L_G] for givenG, in particular when this index is always greater than 1. IfG is abelian but not one of seven exceptional groups, then a Cayley graph ofG exists for which this index is at most 2. Nearly complete results for the generalized dicyclic groups are also obtained.     

Embedding graphs in Cayley graphs

IfY is a finite graph then it is known that every sufficiently large groupG has a Cayley graph containing an induced subgraph isomorphic toY. This raises the question as to what is sufficiently large. Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|³ suffices. Using a form of greedy algorithm we strengthen this to (2 + \sqrt 3 )|Y|^3 $$ " align="middle" border="0"> . Some related results on finite and infinite groups are included.     

Effects of Erlang call holding times on PCS call completion

This paper studies personal communications services (PCSs) channel allocation assuming the Erlang call holding time distribution (a generalization of the exponential distribution) to investigate the effect of the variance of the call holding times on the call completion probability. Our analysis indicates that the call completion probability decreases as the variance of the call holding times decreases. This effect becomes more pronounced as the variance of the cell residence times decreases     

Teletraffic analysis and mobility modeling of PCS networks

Channel holding time is of primary importance in teletraffic analysis of PCS networks. This quantity depends on user's mobility which can be characterized by the cell residence time. We show that when the cell residence time is not exponentially distributed, the channel holding time is not exponentially distributed either, a fact also confirmed by available field data. In order to capture the essence of PCS network behaviour, including the characterization of channel holding time, a correct mobility model is therefore necessary. The new model must be good enough to fit field data, while at the same time resulting in a tractable queueing system. We propose a new mobility model, called the hyper-Erlang distribution model, which is consistent with these requirements. Under the new realistic operational assumption of this model, in which the cell residence time is generally distributed, we derive analytical results for the channel holding time distribution, which are readily applicable to the hyper-Erlang distribution models. Using the derived analytical results we demonstrate how the distribution of the cell residence time affects the channel holding time distribution. The results presented in this paper can provide guidelines for field data processing in PCS network design and performance evaluation