No description available.

Zhang, Zhenyi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 55-[58]). / Abstracts in Chinese and English. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Problem Formulation --- p.4 / Chapter 3 --- Examples --- p.7 / Chapter 3.1 --- Examples of Undirected Graph --- p.7 / Chapter 3.1.1 --- Example 1: SPF Routing --- p.7 / Chapter 3.1.2 --- Example 2: rings --- p.7 / Chapter 3.1.3 --- Example 3: grid --- p.8 / Chapter 3.1.4 --- Example 4: cube --- p.9 / Chapter 3.1.5 --- Example 5: random graph X --- p.10 / Chapter 3.1.6 --- Example 6: random graph Y --- p.10 / Chapter 3.2 --- An Example for Directive Graph --- p.11 / Chapter 4 --- The Framework --- p.13 / Chapter 4.1 --- The distributed algorithm --- p.13 / Chapter 4.2 --- The modules --- p.14 / Chapter 4.3 --- Path control --- p.15 / Chapter 4.4 --- The forwarding module --- p.18 / Chapter 4.5 --- The routing module --- p.19 / Chapter 4.5.1 --- Non-weighted Routing (NWR) --- p.19 / Chapter 4.5.2 --- Weighted Routing (WR) --- p.20 / Chapter 4.6 --- Packet Aggregation (PKA) --- p.21 / Chapter 5 --- Experiments of Path Aggregation --- p.23 / Chapter 5.1 --- System Setup --- p.24 / Chapter 5.2 --- Experiment Results --- p.25 / Chapter 6 --- Convergence --- p.28 / Chapter 6.1 --- Simulation study --- p.34 / Chapter 6.2 --- Optimality --- p.34 / Chapter 6.3 --- Speed of Convergence --- p.37 / Chapter 7 --- The adaptive property --- p.41 / Chapter 7.1 --- Adapting to new links --- p.42 / Chapter 7.2 --- Adapting to topology changing --- p.43 / Chapter 7.3 --- Adapting to interference and congestion --- p.45 / Chapter 7.4 --- Adapting to traffic flows --- p.45 / Chapter 7.5 --- Adapting to capacity --- p.46 / Chapter 8 --- Related works --- p.48 / Chapter 8.1 --- Spanning Tree --- p.48 / Chapter 8.2 --- Minimum Equivalent Directed Graph Problem --- p.49 / Chapter 8.3 --- Topology Control --- p.50 / Chapter 8.4 --- The Relationship with our problem --- p.53 / Chapter 9 --- Conclusion --- p.54

As modern CMPs scale to ever increasing core counts, Networks-on-Chip (NoCs) are emerging as an interconnection fabric, enabling communication between components. While NoCs are easy to implement and provide high and scalable bandwidth, current routing algorithms, such as dimension-ordered routing, suffer from poor load balance, leading to reduced throughput and high latencies. Improving load balance, hence, is critical in future CMP designs where increased latency leads to wasted power and energy waiting for outstanding requests to resolve. Adaptive routing is a known technique to improve load balance; however, prior adaptive routing techniques either use local, myopic information or misinformed, regionally-aggregated information to form their routing decisions. This thesis proposes a new, light-weight, adaptive routing algorithm for on-chip routers based on global link state and congestion information, Global Congestion Awareness (GCA). GCA leverages unused bits in existing packet header flits to "piggyback" congestion state information around the network and uses a simple, low-complexity route calculation unit, to calculate optimal packet paths to their destination without the myopia of local decisions, nor the aggregation of unrelated status information, found in prior designs. In particular GCA outperforms local adaptive routing by up to 82%, Regional Congestion Awareness (RCA) by up to 51%, and a recent competing adaptive routing algorithm, DAR, by 8% on average on realistic workloads.

Real time information about traffic conditions is becoming widely available through various media, and the focus on Advanced Traveler Information Systems (ATIS) is gaining importance rapidly. In such conditions, travelers have better knowledge about the system and adapt as the system evolves dynamically during their travel. Drivers may change routes along their travel in order to optimize their own objective of travel, which can be characterized by disutility functions. The focus of this research is to study the behavior of travelers with multiple trip objectives, when provided with real time information. A web based experiment is carried out to simulate a traffic network with information provision and different travel objectives. The decision strategies of participants are analyzed and compared to the optimal policy, along with few other possible decision rules and a general model is calibrated to describe the travelers' decision strategy. This research is a step towards calibrating equilibrium models for adaptive behavior with multiple user classes. / text

<p>The soaring demands for always-on and fast-response online services have driven modern datacenter networks to undergo tremendous growth. These networks often rely on scale-out designs with large numbers of commodity switches to reach immense capacity while keeping capital expenses under check. Today, datacenter network operators spend tremendous time and efforts on two key challenges: 1) how to efficiently utilize the bandwidth connecting host pairs and 2) how to promptly handle network failures with minimal disruptions to the hosted services.</p><p>To resolve the first challenge, we propose solutions in both network layer and transport layer. In the network layer solution, We advocate to design practical datacenter architectures for easy operation, i.e., an architecture should be reliable, capable of improving bisection bandwidth, scalable and debugging-friendly. By strictly following these four guidelines, We propose DARD, a Distributed Adaptive Routing architecture for Datacenter networks. DARD allows each end host to reallocate traffic from overloaded paths to underloaded paths without central coordination. We use congestion game theory to show that DARD converges to a Nash equilibrium in finite steps and its gap to the optimal flow allocation is bounded in the order of 1/logL, with L being the number of links. We use a testbed implementation and simulations to show that DARD can achieve a close-to-optimal flow allocation with small control overhead in practice.</p><p>In the transport layer solution, We propose Explicit Multipath Congestion Control Protocol (MPXCP), which achieves four desirable properties: fast convergence, efficiency, being fair to flows with different RTTs and negligible queue size. Intensive ns-2 simulation shows that MPXCP can quickly converge to efficiency and fairness without building up queues despite different delay-bandwidth products.</p><p>To resolve the second challenge, recent research efforts have focused on automatic failure localization. Yet, resolving failures still requires significant human interventions, resulting in prolonged failure recovery time. Unlike previous work, we propose NetPilot, a system aims to quickly mitigate rather than resolve failures. NetPilot mitigates failures in much the same way operators do -- by deactivating or restarting suspected offending components. NetPilot circumvents the need for knowing the exact root cause of a failure by taking an intelligent trial-and-error approach. The core of NetPilot is comprised of an Impact Estimator that helps guard against overly disruptive mitigation actions and a failure-specific mitigation planner that minimizes the number of trials. We demonstrate that NetPilot can effectively mitigate several types of critical failures commonly encountered in production datacenter networks.</p> / Dissertation

Chips will be designed with billions of transistors and heterogeneous components integrated to provide full functionality of a current application for embedded system. These applications also require highly parallel and flexible communicating architecture through a regular interconnection network. The emerging solution that can fulfill this requirement is Network-on-Chips (NoCs). Designing an ideal NoC with high throughput, low latency, minimum using resources, minimum power consumption and small area size are very time consuming. Each application required different levels of QoS such as minimum level throughput delay and jitter. In this thesis, firstly, we proposed an evaluation of the impact of design parameters on performance of NoC. We evaluate the impact of NoC design parameters on the performances of an adaptive NoCs. The objective is to evaluate how big the impact of upgrading the value on performances. The result shows the accuracy of choosing and adjusting the network parameters can avoid performance degradation. It can be considered as the control mechanism in an adaptive NoC to avoid the degradation of QoS NoC. The use of deep sub-micron technology in embedded system and its variability process cause Single Event Upsets (SEU) and ''aging'' the circuit. SEU and aging of circuit is the major problem that cause the failure on transmitting the packet in a NoC. Implementing fault-tolerant routing techniques in NoC switching instead of adding virtual channel is the best solution to avoid the fault in NoC. Communication performance of a NoC is depends heavily on the routing algorithm. An adaptive routing algorithm such as fault-tolerant has been proposed for deadlock avoidance and load balancing. This thesis proposed a novel adaptive fault-tolerant routing algorithm for 2D mesh called Gradient and for 3D mesh called Diagonal. Both algorithms consider sequences of alternative paths for packets when the main path fails. The proposed algorithm tolerates faults in worst condition traffic in NoCs. The number of hops, the number of alternative paths, latency and throughput in faulty network are determined and compared with other 2D mesh routing algorithms. Finally, we implemented Gradient routing algorithm into FPGA. All these work were validated and characterized through simulation and implemented into FPGA. The results provide the comparison performance between proposed method with existing related method using some scenarios.

Les systèmes embarqués sur puce modernes intègrent des milliards de transistors et des composants intégrés hétérogènes pour fournir toutes les fonctionnalités requises par les applications courantes. La solution support de la communication dans ce cadre s'appuie sur la notion de réseau sur puce (NoC pour network on chip). Les principaux objectifs de la conception d'un NoC sont d'obtenir des performances élevées, pour un coût d'implémentation (notamment en surface et en consommation électrique) le plus faible possible. Ainsi, le concepteur de NoC doit tenir compte de l'impact des paramètres du NoC sur le compromis entre les performances du réseau et la taille de silicium requis pour son implémentation. L'utilisation de la technologie submicronique profonde amène des phénomènes de variabilité et de vieillissement qui causes des événements singuliers uniques (SEU pour Single Event Upset). Un SEU provoque le changement d'état d'un bit qui provoque l'échec de la transmission d'une donnée dans un NoC. La mise en œuvre de routage supportant la tolérance aux fautes est donc nécessaire. Dans cette thèse, nous proposons dans un premier temps, une évaluation de l'impact des paramètres de conception des NoC sur ses performances. Le résultat permet de guider le concepteur dans ses choix et le réglage des paramètres du réseau permettant d'éviter la dégradation de ses performances. Deuxièmement, nous avons proposé de nouveaux algorithmes de routage adaptatifs tolérants aux pannes pour un réseaux maillé 2D appelé Gradient et pour un réseaux maillé 3D appelé Diagonal. Ces algorithmes s'adaptent et proposent des séquences de chemins alternatifs pour les paquets lorsque le chemin principal est fautif. Nous avons ainsi évalué le coût d'implémentation de Gradient sur un FPGA actuel. Tous ces travaux ont été validés et caractérisée par simulation et mis en œuvre en FPGA. Les résultats fournissent la comparaison des performances de nos algorithmes avec les algorithmes de l'état de l'art. / Chips will be designed with billions of transistors and heterogeneous components integrated to provide full functionality of a current application for embedded system. These applications also require highly parallel and flexible communicating architecture through a regular interconnection network. The emerging solution that can fulfill this requirement is Network-on-Chips (NoCs). Designing an ideal NoC with high throughput, low latency, minimum using resources, minimum power consumption and small area size are very time consuming. Each application required different levels of QoS such as minimum level throughput delay and jitter. In this thesis, firstly, we proposed an evaluation of the impact of design parameters on performance of NoC. We evaluate the impact of NoC design parameters on the performances of an adaptive NoCs. The objective is to evaluate how big the impact of upgrading the value on performances. The result shows the accuracy of choosing and adjusting the network parameters can avoid performance degradation. It can be considered as the control mechanism in an adaptive NoC to avoid the degradation of QoS NoC. The use of deep sub-micron technology in embedded system and its variability process cause Single Event Upsets (SEU) and ''aging'' the circuit. SEU and aging of circuit is the major problem that cause the failure on transmitting the packet in a NoC. Implementing fault-tolerant routing techniques in NoC switching instead of adding virtual channel is the best solution to avoid the fault in NoC. Communication performance of a NoC is depends heavily on the routing algorithm. An adaptive routing algorithm such as fault-tolerant has been proposed for deadlock avoidance and load balancing. This thesis proposed a novel adaptive fault-tolerant routing algorithm for 2D mesh called Gradient and for 3D mesh called Diagonal. Both algorithms consider sequences of alternative paths for packets when the main path fails. The proposed algorithm tolerates faults in worst condition traffic in NoCs. The number of hops, the number of alternative paths, latency and throughput in faulty network are determined and compared with other 2D mesh routing algorithms. Finally, we implemented Gradient routing algorithm into FPGA. All these work were validated and characterized through simulation and implemented into FPGA. The results provide the comparison performance between proposed method with existing related method using some scenarios.

A wireless mesh network is a mesh network implemented over a wireless network system such as wireless LANs. Wireless Mesh Networks(WMNs) are promising for numerous applications such as broadband home networking, enterprise networking, transportation systems, health and medical systems, security surveillance systems, etc. Therefore, it has received considerable attention from both industrial and academic researchers. This dissertation explores schemes for resource management and optimization in WMNs by means of network routing and network coding. In this dissertation, we propose three optimization schemes. (1) First, a triple-tier optimization scheme is proposed for load balancing objective. The first tier mechanism achieves long-term routing optimization, and the second tier mechanism, using the optimization results obtained from the first tier mechanism, performs the short-term adaptation to deal with the impact of dynamic channel conditions. A greedy sub-channel allocation algorithm is developed as the third tier optimization scheme to further reduce the congestion level in the network. We conduct thorough theoretical analysis to show the correctness of our design and give the properties of our scheme. (2) Then, a Relay-Aided Network Coding scheme called RANC is proposed to improve the performance gain of network coding by exploiting the physical layer multi-rate capability in WMNs. We conduct rigorous analysis to find the design principles and study the tradeoff in the performance gain of RANC. Based on the analytical results, we provide a practical solution by decomposing the original design problem into two sub-problems, flow partition problem and scheduling problem. (3) Lastly, a joint optimization scheme of the routing in the network layer and network coding-aware scheduling in the MAC layer is introduced. We formulate the network optimization problem and exploit the structure of the problem via dual decomposition. We find that the original problem is composed of two problems, routing problem in the network layer and scheduling problem in the MAC layer. These two sub-problems are coupled through the link capacities. We solve the routing problem by two different adaptive routing algorithms. We then provide a distributed coding-aware scheduling algorithm. According to corresponding experiment results, the proposed schemes can significantly improve network performance.

The objective of the research is to study optimal routing policy (ORP) problems and to develop an optimal adaptive routing algorithm practical for large-scale Stochastic Time-Dependent (STD) real-life networks, where a traveler could revise the route choice based upon en route information. The routing problems studied can be viewed as counterparts of shortest path problems in deterministic networks. A routing policy is defined as a decision rule that specifies what node to take next at each decision node based on realized link travel times and the current time. The existing routing policy algorithm is for explorative purpose and can only be applied to hypothetical simplified network. In this research, important changes have been made to make it practical in a large-scale real-life network. Important changes in the new algorithm include piece-wise linear travel time representation, turn-based, label-correcting, criterion of stochastic links, and dynamic blocked links. Complete dependency perfect online information (CDPI) variant is then studied in a real-life network (Pioneer Valley, Massachusetts). Link travel times are modeled as random variables with time-dependent distributions which are obtained by running Dynamic Traffic Assignment (DTA) using data provided by Pioneer Valley Planning Commission (PVPC). A comprehensive explanation of the changes by comparing the two algorithms and an in-depth discussion of the parameters that affects the runtime of the new algorithm is given. Computational tests on the runtime changing with different parameters are then carried out and the summary of its effectiveness are presented. To further and fully understand the applicability and efficiency, this algorithm is then tested in another large-scale network, Stockholm in Sweden, and in small random networks. This research is also a good starting point to investigate strategic route choice models and strategic route choice behavior in a real-life network. The major tasks are to acquire data, generate time-adaptive routing policies, and estimate the runtime of the algorithm by changing the parameters in two large-scale real-life networks, and to test the algorithm in small random networks. The research contributes to the knowledge base of ORP problems in stochastic time-dependent (STD) networks by developing an algorithm practical for large-scale networks that considers complete time-wise and link-wise stochastic dependency.

Congestion is a world-wide problem in transportation. One major reason is random interruptions. The traffic network is inherently stochastic, and strong dependencies exist among traffic quantities, e.g., travel time, traffic speed, link volume. Information in stochastic networks can help with adaptive routing in terms of minimizing expected travel time or disutility. Routing in such networks is different from that in deterministic networks or when stochastic dependencies are not taken into account. This dissertation addresses the optimal routing problems, including the optimal a priori path problem and the optimal adaptive routing problem with different information scenarios, in stochastic and time-dependent networks with explicit consideration of the correlations between link travel time random variables. There are a number of studies in the literature addressing the optimal routing problems, but most of them ignore the correlations between link travel times. The consideration of the correlations makes the problem studied in this dissertation difficult, both conceptually and computationally. The optimal path finding problem in such networks is different from that in stochastic and time-dependent networks with no consideration of the correlations. This dissertation firstly provides an empirical study of the correlations between random link travel times and also verifies the importance of the consideration of the spatial and temporal correlations in estimating trip travel time and its reliability. It then shows that Bellman's principle of optimality or non-dominance is not valid due to the time-dependency and the correlations. A new property termed purity is introduced and an exact label-correcting algorithm is designed to solve the problem. With the fast advance of telecommunication technologies, real-time traffic information will soon become an integral part of travelers' route choice decision making. The study of optimal adaptive routing problems is thus timely and of great value. This dissertation studies the problems with a wide variety of information scenarios, including delayed global information, real-time local information, pre-trip global information, no online information, and trajectory information. It is shown that, for the first four partial information scenarios, Bellman's principle of optimality does not hold. A heuristic algorithm is developed and employed based on a set of necessary conditions for optimality. The same algorithm is showed to be exact for the perfect online information scenario. For optimal adaptive routing problem with trajectory information, this dissertation proves that, if the routing policy is defined in a similar way to other four information scenarios, i.e., the trajectory information is included in the state variable, Bellman's principle of optimality is valid. However, this definition results in a prohibitively large number of the states and the computation can hardly be carried out. The dissertation provides a recursive definition for the trajectory-adaptive routing policy, for which the information is not included in the state variable. In this way, the number of states is small, but Bellman's principle of optimality or non-dominance is invalid for a similar reason as in the optimal path problem. Again purity is introduced to the trajectory-adaptive routing policy and an exact algorithm is designed based on the concept of decreasing order of time.