Sun Weng Hong. / Thesis submitted in: October 2002. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 116-121). / Abstracts in English and Chinese. / Chapter 1. --- Introduction --- p.7 / Chapter 2. --- Ant Colony Optimization (ACO) --- p.9 / Chapter 2.1 --- ACO vs. Traditional Routing --- p.10 / Chapter 2.1.1 --- Routing information --- p.10 / Chapter 2.1.2 --- Routing overhead --- p.12 / Chapter 2.1.3 --- Adaptivity and Stagnation --- p.14 / Chapter 2.2 --- Approaches to Mitigate Stagnation --- p.15 / Chapter 2.2.1 --- Pheromone control --- p.15 / Chapter 2.2.1.1 --- Evaporation: --- p.15 / Chapter 2.2.1.2 --- Aging: --- p.16 / Chapter 2.2.1.3 --- Limiting and smoothing pheromone: --- p.17 / Chapter 2.2.2 --- Pheromone-Heuristic Control --- p.18 / Chapter 2.2.3 --- Privileged Pheromone Laying --- p.19 / Chapter 2.2.4 --- Critique and Comparison --- p.21 / Chapter 2.2.4.1 --- Aging --- p.22 / Chapter 2.2.4.2 --- Limiting pheromone --- p.22 / Chapter 2.2.4.3 --- Pheromone smoothing --- p.23 / Chapter 2.2.4.4 --- Evaporation --- p.25 / Chapter 2.2.4.5 --- Privileged Pheromone Laying --- p.25 / Chapter 2.2.4.6 --- Pheromone-heuristic control --- p.26 / Chapter 2.3 --- ACO in Routing and Load Balancing --- p.27 / Chapter 2.3.1 --- Ant-based Control and Its Ramifications --- p.27 / Chapter 2.3.2 --- AntNet and Its Extensions --- p.35 / Chapter 2.3.3 --- ASGA and SynthECA --- p.40 / Chapter 3. --- Multiple Ant Colony Optimization (MACO) --- p.45 / Chapter 4. --- MACO vs. ACO --- p.51 / Chapter 4.1 --- Analysis of MACO vs. ACO --- p.53 / Chapter 5. --- Applying MACO in Load Balancing --- p.89 / Chapter 5.1 --- Applying MACO in Load-balancing --- p.89 / Chapter 5.2 --- Problem Formulation --- p.91 / Chapter 5.3 --- Types of ant in MACO --- p.93 / Chapter 5.3.1 --- Allocator. --- p.94 / Chapter 5.3.2 --- Destagnator. --- p.95 / Chapter 5.3.3 --- Deallocator. --- p.100 / Chapter 5.4 --- Global Algorithm --- p.100 / Chapter 5.5 --- Discussion of the number of ant colonies --- p.103 / Chapter 6. --- Experimental Results --- p.105 / Chapter 7. --- Conclusion --- p.114 / Chapter 8. --- References --- p.116 / Appendix A. Ants in MACO --- p.122 / Appendix B. Ants in SACO. --- p.123

Output queues in network switches are known to provide a suitable architecture for scheduling disciplines that need to provide quality of service (QoS) guarantees. However, today’s memory technology is incapable of meeting the speed requirements. Combined input and output queued (CIOQ) switches have emerged as one alternative to address the problem of memory speed. When a switch of this architecture uses a stable matching algorithm to transfer packets across the switch fabric, an output queued (OQ) switch can be mimicked exactly with a speedup of only two. The use of a stable matching algorithm typically requires complex and time-consuming calculations to ensure the behaviour of an OQ switch is maintained. Stable matching algorithms are well studied in the area in which they originally appeared. However, little is presently known on how the stable matching algorithm performs in CIOQ switches and how key parameters are affected by switch size, traffic type and traffic load. Knowledge of how these conditions affect performance is essential to judge the practicability of an architecture and to provide useful information on how to design such switches. Until now, CIOQ switches were likely to be dismissed due to the high complexity of the stable matching algorithm when applied to other applications. However, the characteristics of a stable matching algorithm in a CIOQ switch have not been thoroughly analysed. The principal goal of this thesis is to identify the conditions the stable matching algorithm encounters in a CIOQ switch under realistic operational scenarios. This thesis provides accurate mathematical models based on Markov chains to predict the value of key parameters that affect the complexity and runtime of a stable matching algorithm in CIOQ switches. The applicability of the models is then backed up by simulations. The results of the analysis quantify critical operational parameters, such as the size and number of preference lists and runtime complexity. These provide detailed insights into switch behaviour and useful information for switch designs. Major conclusions to be drawn from this analysis include that the average values of the key parameters of the stable matching algorithm are feasibly small and do not strongly correlate with switch size, which is contrary to the behaviour of the stable matching ii algorithm in its original application. Furthermore, although these parameters have wide theoretical ranges, the mean values and standard deviations are found to be small under operational conditions. The results also suggest that the implementation becomes very versatile as the completion time of the stable matching algorithm is not strongly correlated to the network traffic type; that is, the runtime is minimally affected by the nature of the traffic.

The growing acceptance of B-ISDN (Broadband Integrated Services Digital Network) requires entirely new switching support a wide range of service demands including voice, video and data. At the same time, advances in the field of VLSI have enabled new principles to the design and architecture high-performance switching fabrics. Direct binary switch fabrics are a suitable candidate for future B- switches. Binary hypercubes have regular topology, are highly fault and have multiple paths for routing cells which help avoid performance penalties due to congestion and faults. In addition, these switches can adopt the novel, distributed, and adaptive routing scheme called 'deflection routing'. In normal routing, cells are routed along shortest paths to their destinations; in case of multiple cells contending for a single outgoing channel, the rest of the contending cells are either buffered or dropped to avoid congestion. In the case of deflection routing, cells can be routed along non-shortest paths. As a result, deflection routing helps avoid dropping cells. The scheme may be implemented with and without queuing buffers at the routers. In order to properly provision, control, and design these hypercube switches, it is essential that their performance capabilities be completely understood. Researchers have used both analytical model and simulations to evaluate performance of hypercube switches. The presence of distributed logic, multi-path routing, deflection routing, and queuing buffers make modeling tasks highly challenging. Building a reasonably accurate model of a hypercube switch with queuing buffers and deflection routing and using that model to gain practical insights into some of the important design parameters of the switch has been the major motivation of this thesis. An approximate Markov model of a single switching element is built to capture the behavior of a d-dimension switch. The numerical model is solved iteratively. Accuracy of the model is established by validating against simulation results. One disadvantage of having multiple paths, queuing buffers, and deflection motion of cells in hypercube switches is that the cells belonging to a particular traffic stream may not be delivered at their destinations in sequence. This phenomenon is known as 'out-of-orderness' of cells. An additional goal of this thesis has been development of a model to capture out-of-orderness phenomenon. The model is validated by comparing model results against simulation. Results show that the model is accurate and reveals significant insight into switch's behavior that can be used to design and engineer d-dimension hypercube switches.

MPLS-Based Best-Effort Traffic Engineering Jerapong Rojanarowan 120 Pages Directed by Dr. Henry L. Owen The objective of this research is to develop a multipath traffic engineering framework for best-effort traffic in Multiprotocol Label Switching (MPLS) networks so as to deliver more equal shares of bandwidth to best-effort users as compared to the traditional shortest-path algorithm. The proposed framework is static and the input to the traffic engineering algorithm is restricted to network topology. Performance evaluation of this framework is conducted by simulation using ns-2 network simulator. In a multi-service capable network, some portion of the bandwidth is reserved for guaranteed services and the leftover portion is dedicated to best-effort service. This research examines the problem of traffic engineering for the remaining network bandwidth that is utilized by best-effort traffic where demands are not known a priori. This framework will result in making the limited available best-effort traffic bandwidth more equitably shared by the best-effort flows over a wide range of demands. Traditional traffic engineering research has not examined best-effort traffic.

Not available

Les systèmes hybrides sont des systèmes dynamiques, caractérisés par un comportementdual, une interaction entre une partie discrète et une partie continue de fonctionnement.Dans le centre de notre travail se trouve une classe particulière de systèmeshybrides, plus spécifiquement les systèmes stochastiques à commutation que nous modélisonsà l’aide des Chaînes de Markov en temps continu et des équations différentielles.Le comportement aléatoire de ce type de système nécessite une commande spécialequi s’adapte aux événements arbitraires qui peuvent changer complètement l’évolutiondu système. Nous avons choisi une politique de contrôle basée sur les événements quiest déclenchée seulement quand il est nécessaire (sur un événement incontrôlable - parexemple un seuil qui est atteint), et jusqu’à ce que certaines conditions de fonctionnementsont remplies (le système revient dans l’état normal).Notre approche vise le développement d’un modèle probabiliste qui permet de calculerun critère de performance (en occurrence l’énergie du système) pour la politiquede contrôle choisie. Nous proposons d’abord une méthode de simulation à événementsdiscrets pour le système stochastique à commutation commandé, qui nous donne la possibilitéde réaliser une optimisation directe de la commande appliquée sur le système etaussi de valider les modèles analytiques que nous avons construit pour l’application ducontrôle.Un modèle analytique pour déterminer l’énergie consommée par le système a étéconçu en utilisant les probabilités de sortie de la région de contrôle, respectivement lestemps de séjour dans la chaîne de Markov avant et après avoir atteint les limites decontrôle. La dernière partie du travail présente la comparaison des résultats obtenusentre la méthode analytique et la simulation. / Hybrid systems are dynamical systems, characterized by a dual behaviour, a continuousinteraction between a discrete and a continuous functioning part. The center ofour work is represented by a particular class of hybrid systems, more specific by thestochastic switching systems which we model using continuous time Markov chains anddifferential equations.The random behaviour of such systems requires a special command which adapts tothe arbitrary events that can completely change the evolution of the system. We chose anevent-based control policy which is triggered only when it’s necessary (on an unforeseenevent - for example when a threshold that is reached), and until certain functioningconditions are met (the system returns in the normal state).Our approach aims to develop a probabilistic model that calculates a performancecriterion (in this case the energy of the system) for the proposed control policy. We startby proposing a discrete event simulation for the controlled stochastic switching system,which gives us the opportunity of applying a direct optimisation of the control command.It also allows us to compare the results with the ones obtained by the analytical modelswe have built when the event-based control is applied.An analytical model for computing the energy consumed by the system to apply thecontrol is designed by using the exit probabilities of the control region, respectively, thesojourn times of the Markov chain before and after reaching the control limits. The lastpart of this work presents the results we have obtained when comparing the analyticaland the simulation method.

No description available.

No description available.

The growth of mobile networks and the imminent deployment of third generation networks and services will require signalling networks to maintain their integrity during increased unanticipated traffic volumes. As signalling networks become larger and more complex, an analysis ofprotocol operation is necessary to determine the effectiveness of the current protocol implementation and to evaluate the applicability of the proposed enhancements. The objective of this study ,is to develop analytical models to analyse the impact of Signalling Transfer Point congestion on network performance when simple message discard schemes are used as the primary flow control mechanism, and to investigate suitable congestion and flow control mechanisms to help alleviate the congestion. Unlike previous studies, that are localised and only concentrate on the nodes around the congested entity, the models presented here examine the impact of network wide and focused overloads on the entire network. The study considers both the fixed-line and mobile network environments, and analyses the performance of the ISDN User Part and Mobile Application Part protocols. The call completion rate and location update success rate are used to measure performance, instead of message throughput, since these parameters provide a more appropriate measure of the grade-of-service and more accurately reflect the level of service provided to a customer. The steady state equilibrium models, derived here, can be used to quickly estimate the safe operating regions of a signalling network, while the transient models provide a more intuitive perspective of the traffic processes that lead to congestion . Furthermore, these models can be used to examine the network performance for different message priority schemes, routing algorithms, overload scenarios and network configurations. The performance of various congestion control mechanisms that incorporate non-linear throttling schemes is also evaluated, together with an examination of the impact of congestion on multiple user parts in a mobile network environment. Message priority schemes are found to offer little or no advantage in a fixed network environment, but in a mobile network they can be used to maintain the network's performance at an optimum level during periods of overload. Network performance is also improved if congestion controls block load-generating traffic at the initial onset of congestion and then gradually restore traffic as the performance improves . / Thesis (Ph.D.)-University of Natal, Durban, 2002.

Este trabalho consiste na especificação e desenvolvimento da arquitetura de um Comutador Digital para TDM Determinístico E1, visando sua posterior implementação em microeletrônica. Inicialmente são apresentados os conceitos gerais sobre os Sistemas de Comutação, bem como das principais modalidades de comutação, seguidos de um estudo aprofundado da Comutação de Circuitos e suas técnicas mais utilizadas, devido a sua Intima relação com a multiplexação TDM e a hierarquia E1. Do mesmo modo, são descritas as características das Redes Corporativas E1 e dos multiplexadores E1, junto com as funções principais do Comutador dentro do ambiente de uma rede ponto-a-ponto. Com base no estudo prévio, e proposta a arquitetura de um Comutador Digital baseado em técnicas TSI capaz de fornecer funções de comutação local e remota entre os dispositivos conectados aos multiplexadores El, que formam os nos de uma Rede Corporativa com controle centralizado. 0 projeto logico e a simulação do Comutador Digital foram realizados dentro do framework SOLO/Cadence, usando a biblioteca de Standard Cells da tecnologia CMOS de 1.2µ. O simulador lógica SILOS, disponível no SOLO/Cadence, foi utilizado para validar a arquitetura proposta. Detalhes de implementação e resultados de simulação são apresentados. O módulo de controle do Comutador Digital e apenas especificado. / This work consists in the specification and development of a Digital Circuit Switch architecture for E1l Deterministic TDM, looking toward a future microelectronics implementation. First, general concepts about Switching Systems and its basic elements, as well as the main kinds of switching are presented. Also, a meticulous study about Circuit Switching and its more used techniques is realized, because of the intrinsec relation with TDM and E1 hierarchy. In the same way, the characteristics of E1 Corporate Networks and E1 multiplexers are described, along with the main functions of the Digital Switch into an end-to-end network. Taking into account the previous study, the architecture of a Digital Switch based on TSI techniques, is proposed. This architecture is able to perform local and remote switching between the devices connected to E1 multiplexers, which form the network nodes of an end-to-end Corporate Network. The logic design and the circuit simulation of the Digital Switch were performed within SOLO/Cadence Standard Cells desing framework, using CMOS 1.2µ technology. The logic simulator SILOS was used to validate the proposed architecture. Implementation details and simulation results are presented. The Control module of the Digital Switch is only specified.