Development of computer networks able to operate at the speed of 10 Gb/s imposes new requirements on newly developed network devices and also on a process of their testing. Such devices are tested by replaying synthetic or previously captured network traffic on an input link of the tested device. We must be able to perform both tasks also at full wire speed. Current testing devices are either not able to operate at the speed of 10 Gb/s or they are too expensive. Therefore, the aim of this thesis is to design and implement a hardware accelerated application able to generate and replay network traffic at the speed of 10 Gb/s. The application is accelerated in the FPGA of the COMBOv2 card and it also utilizes the NetCOPE platform. Architecture of the application is modular, which allows easy implementation of different modes of operation. The application implements both capturing and replaying network traffic at full wire speed, but traffic can be limited to a specified value of bitrate at the output. The thesis is concluded by a comparison of the implemented application and the packet generator implemented on the NetFPGA platform. According to this comparison, the implemented application is better than the NetFPGA packet generator.

Random number generation can be based on physical events with probabilistic character, or on algorithms that use complex or one-way functions, alternatively on both of these approaches. A magnetic vortex is a basic state of magnetization that forms in magnetic micro- and nanostructures of an appropriate shape, dimensions and material. Quantities of the magnetic vortex form randomly if ambient conditions are chosen eligibly. A concept of a true random number generator using a random switching of states of the magnetic vortex is presented in this thesis. This concept is realized and random numbers were experimentally generated and numbers were statistically analysed.

This thesis solves the problem of generating random numbers on low-power devices. Author describes possible ways of generating and implements selected generators of (pseudo)random numbers on MSP430F5438A. 4 generators were added by the enhancement of one of them and a new generator was created, using the phenomenon of temperature change in the surroundings. For each generator, test sequences were generated and these sequences were tested by the Dieharder, STS-NIST, and Visual Test. The output of the thesis is the functional implementation of the generators, their testing by statistical methods and their comparison between each other.

Im Kern der vorliegenden Arbeit wird eine neue Vorfahrtstrategie zur Steuerung von Materialflüssen an Zusammenführungen vorgestellt. Das Hauptanwendungsgebiet stellen innerbetriebliche Transportsysteme dar, wobei die Erkenntnisse auf beliebige Transport- bzw. Bediensysteme übertragbar sind. Die Arbeit grenzt sich mit der Annahme autokorrelierter Ankunftsprozesse von bisheriger Forschung und Entwicklung ab. Bis dato werden stets unkorrelierte Ströme angenommen bzw. findet keine spezielle Beachtung autokorrelierter Ströme bei der Vorfahrtsteuerung statt. Untersuchungen zeigen aber, dass zum einen mit hoher Konfidenz mit autokorrelierten Materialflüssen zu rechnen ist und in diesem Fall zum anderen von einem erheblichen Einfluss auf die Systemleistung ausgegangen werden muss. Zusammengefasst konnten im Rahmen der vorliegenden Arbeit 68 Realdatensätze verschiedener Unternehmen untersucht werden, mit dem Ergebnis, dass ca. 95% der Materialflüsse Autokorrelation aufweisen. Ferner wird hergeleitet, dass Autokorrelation intrinsisch in Materialflusssystemen entsteht. Die Folgen autokorrelierter Prozesse bestehen dabei in längeren Durchlaufzeiten, einem volatileren Systemverhalten und höheren Wahrscheinlichkeiten von Systemblockaden. Um die genannten Effekte an Zusammenführungen zu eliminieren, stellt die Arbeit eine neue Vorfahrtstrategie HAFI – Highest Autocorrelated First vor. Diese priorisiert die Ankunftsprozesse anhand deren Autokorrelation. Konkret wird die Vorfahrt zunächst so lange nach dem Prinzip First Come First Served gewährt, bis richtungsweise eine spezifische Warteschlangenlänge überschritten wird. Der jeweilige Wert ergibt sich aus der Höhe der Autokorrelation der Ankunftsprozesse. Vorfahrt bekommt der Strom mit der höchsten Überschreitung seines Grenzwertes. Die Arbeit stellt ferner eine Heuristik DyDeT zur automatischen Bestimmung und dynamischen Anpassung der Grenzwerte vor. Mit einer Simulationsstudie wird gezeigt, dass HAFI mit Anwendung von DyDeT die Vorzüge der etablierten Vorfahrtstrategien First Come First Served und Longest Queue First vereint. Dabei wird auch deutlich, dass die zwei letztgenannten Strategien den besonderen Herausforderungen autokorrelierter Ankunftsprozesse nicht gerecht werden. Bei einer Anwendung von HAFI zur Vorfahrtsteuerung können Durchlaufzeiten und Warteschlangenlängen auf dem Niveau von First Come First Served erreicht werden, wobei dieses ca. 10% unter dem von Longest Queue First liegt. Gleichzeitig ermöglicht HAFI, im Gegensatz zu First Come First Served, eine ähnlich gute Lastbalancierung wie Longest Queue First. Die Ergebnisse stellen sich robust gegenüber Änderungen der Auslastung sowie der Höhe der Autokorrelation dar. Gleichzeitig sind die Erkenntnisse unabhängig der Analyse einer isolierten Zusammenführung und der Anordnung mehrerer Zusammenführungen in einem Netzwerk.:1 Einleitung 1 1.1 Motivation 1 1.2 Zielsetzung, wissenschaftlicher Beitrag 4 1.3 Konzeption 5 2 Grundlagen 7 2.1 Automatisierung, Steuern, Regeln 7 2.2 System, Modell 10 2.3 Stochastik, Statistik 14 2.3.1 Wahrscheinlichkeitsverteilungen 14 2.3.2 Zufallszahlengeneratoren 21 2.3.3 Autokorrelation als Ähnlichkeits- bzw. Abhängigkeitsmaß 24 2.4 Simulation 29 2.5 Warteschlangentheorie und -modelle 32 2.6 Materialflusssystem 35 2.7 Materialflusssteuerung 37 2.7.1 Steuerungssysteme 37 2.7.2 Steuerungsstrategien 40 2.8 Materialflusssystem charakterisierende Kennzahlen 46 3 Stand der Forschung und Technik 51 3.1 Erzeugung autokorrelierter Zufallszahlen 51 3.1.1 Autoregressive Prozesse nach der Box-Jenkins-Methode 52 3.1.2 Distorsions-Methoden 54 3.1.3 Copulae 56 3.1.4 Markovian Arrival Processes 58 3.1.5 Autoregressive Prozesse mit beliebiger Randverteilung 61 3.1.6 Weitere Verfahren 64 3.1.7 Bewertung der Verfahren und Werkzeuge zur Generierung 65 3.2 Wirken von Autokorrelation in Bediensystemen 68 3.3 Fallstudien über Autokorrelation in logistischen Systemen 75 3.4 Ursachen von Autokorrelation in logistischen Systemen 89 3.5 Steuerung von Ankunftsprozessen an Zusammenführungen 96 3.6 Steuerung autokorrelierter Ankunftsprozesse 100 4 Steuerung autokorrelierter Ankunftsprozesse an Zusammenführungen 105 4.1 Modellannahmen, Methodenauswahl, Vorbetrachtungen 106 4.2 First Come First Served und Longest Queue First 114 4.3 Highest Autocorrelated First 117 4.3.1 Grundprinzip 117 4.3.2 Bestimmung der Grenzwerte 127 4.3.3 Dynamische Bestimmung der Grenzwerte mittels „DyDeT“ 133 4.4 Highest Autocorrelated First in Netzwerken 150 4.5 Abschließende Bewertung und Diskussion 161 5 Zusammenfassung und Ausblick 167 Primärliteratur 172 Normen und Standards 194 Abbildungsverzeichnis 197 Tabellenverzeichnis 199 Pseudocodeverzeichnis 201 Abkürzungsverzeichnis 203 Symbolverzeichnis 205 Erklärung an Eides statt 209 / The work at hand presents a novel strategy to control arrival processes at merges. The main fields of application are intralogistics transport systems. Nevertheless, the findings can be adapted to any queuing system. In contrast to further research and development the thesis assumes autocorrelated arrival processes. Up until now, arrivals are usually assumed to be uncorrelated and there are no special treatments for autocorrelated arrivals in the context of merge controlling. However, surveys show with high reliability the existence of autocorrelated arrivals, resulting in some major impacts on the systems\' performance. In detail, 68 real-world datasets of different companies have been tested in the scope of this work, and in 95% of the cases arrival processes significantly show autocorrelations. Furthermore, the research shows that autocorrelation comes from the system itself. As a direct consequence it was observed that there were longer cycle times, more volatile system behavior, and a higher likelihood of deadlocks. In order to eliminate these effects at merges, this thesis introduces a new priority rule called HAFI-Highest Autocorrelated First. It assesses the arrivals\' priority in accordance to their autocorrelation. More concretely, priority initially is given in accordance to the First Come First Served scheme as long as specific direction-wise queue lengths are not exceeded. The particular thresholds are determined by the arrival processes\' autocorrelation, wherein the process with the highest volume gets priority. Furthermore, the thesis introduces a heuristic to automatically and dynamically determine the specific thresholds of HAFI-so called DyDeT. With a simulation study it can be shown that HAFI in connection with DyDeT, combines the advantages of the well-established priority rules First Come First Served and Longest Queue First. It also becomes obvious that the latter ones are not able to deal with the challenges of autocorrelated arrival processes. By applying HAFI cycling times and mean queue lengths on the level of First Come First Served can be achieved. These are about 10% lower than for Longest Queue First. Concomitantly and in contrast to First Come First Served, HAFI also shows well balanced queues like Longest Queue First. The results are robust against different levels of throughput and autocorrelation, respectively. Furthermore, the findings are independent from analyzing a single instance of a merge or several merges in a network.:1 Einleitung 1 1.1 Motivation 1 1.2 Zielsetzung, wissenschaftlicher Beitrag 4 1.3 Konzeption 5 2 Grundlagen 7 2.1 Automatisierung, Steuern, Regeln 7 2.2 System, Modell 10 2.3 Stochastik, Statistik 14 2.3.1 Wahrscheinlichkeitsverteilungen 14 2.3.2 Zufallszahlengeneratoren 21 2.3.3 Autokorrelation als Ähnlichkeits- bzw. Abhängigkeitsmaß 24 2.4 Simulation 29 2.5 Warteschlangentheorie und -modelle 32 2.6 Materialflusssystem 35 2.7 Materialflusssteuerung 37 2.7.1 Steuerungssysteme 37 2.7.2 Steuerungsstrategien 40 2.8 Materialflusssystem charakterisierende Kennzahlen 46 3 Stand der Forschung und Technik 51 3.1 Erzeugung autokorrelierter Zufallszahlen 51 3.1.1 Autoregressive Prozesse nach der Box-Jenkins-Methode 52 3.1.2 Distorsions-Methoden 54 3.1.3 Copulae 56 3.1.4 Markovian Arrival Processes 58 3.1.5 Autoregressive Prozesse mit beliebiger Randverteilung 61 3.1.6 Weitere Verfahren 64 3.1.7 Bewertung der Verfahren und Werkzeuge zur Generierung 65 3.2 Wirken von Autokorrelation in Bediensystemen 68 3.3 Fallstudien über Autokorrelation in logistischen Systemen 75 3.4 Ursachen von Autokorrelation in logistischen Systemen 89 3.5 Steuerung von Ankunftsprozessen an Zusammenführungen 96 3.6 Steuerung autokorrelierter Ankunftsprozesse 100 4 Steuerung autokorrelierter Ankunftsprozesse an Zusammenführungen 105 4.1 Modellannahmen, Methodenauswahl, Vorbetrachtungen 106 4.2 First Come First Served und Longest Queue First 114 4.3 Highest Autocorrelated First 117 4.3.1 Grundprinzip 117 4.3.2 Bestimmung der Grenzwerte 127 4.3.3 Dynamische Bestimmung der Grenzwerte mittels „DyDeT“ 133 4.4 Highest Autocorrelated First in Netzwerken 150 4.5 Abschließende Bewertung und Diskussion 161 5 Zusammenfassung und Ausblick 167 Primärliteratur 172 Normen und Standards 194 Abbildungsverzeichnis 197 Tabellenverzeichnis 199 Pseudocodeverzeichnis 201 Abkürzungsverzeichnis 203 Symbolverzeichnis 205 Erklärung an Eides statt 209

This thesis is about linear random number generators with a large integer modulus. It is essential to be able to check that a generator has good properties in Monte-Carlo simulation. The generator family studied here produces points that possess a well known lattice structure that can be studied to assess the uniformity of these generators. The present work is motivated by the update of the LatMRG software which studies the lattice structure of the aforementioned generators. This thesis first presents the different types of generators the software considers. It explains how they can be used to produce random numbers and how to study their period length. It then presents equivalences between some members of this family that are used to simplify LatMRG. It then covers the lattice structure. The thesis describes what it is and how to characterize it. It describes the characterization of the lattice structure for the considered generators. From that, it presents a few algorithms that extract information on the uniformity of generators. At last, the thesis describes the LatMRG software. LatMRG contains both an executable program and a library. The thesis presents both their purpose and their functionalities. It describes upgrades of the software that aim to simplify its usage. Along with the software description are a few examples that serve to illustrate the flexibility and future research avenues. / Ce mémoire s’intéresse au générateurs de nombres aléatoires linéaires modulo un grand entier. Vérifier qu’un générateur possède de bonnes propriétés théoriques est essentiel pour la simulation Monte-Carlo. La famille de générateurs dont il est question produit des points possédant une structure de réseau bien connue pouvant être étudiée pour vérifier l’uniformité de ces générateurs. Le présent travail est motivé par la mise à jour du logiciel LatMRG qui permet d’étudier la structure de réseau de tels générateurs. Ce mémoire présente d’abord les types de générateurs qui sont considérés par le logiciel. Il explique comment ils peuvent être utilisés pour produire des nombres et comment étudier la longueur de leur période. Il présente ensuite des équivalences entre certains membres de la famille dont l’utilisation permet de simplifier le travail dans LatMRG. Il couvre ensuite la structure de réseau. En plus de décrire en quoi elle consiste, il explique comment la caractériser. On décrit une caractérisation de cette structure pour les générateur considérés. À partir de cela, on présente quelques algorithmes permettant d’extraire de l’information sur l’uniformité des générateurs. Le mémoire fait ensuite la description du logiciel LatMRG. LatMRG contient un programme exécutable et une librairie. Ce mémoire présente leur raison d’être et décrit leurs fonctionnalités. Il décrit aussi diverses améliorations qui ont été faites au logiciel avec pour objectif principal de simplifier son utilisation. La description du logiciel s’accompagne de quelques exemples illustrant sa flexibilité et des voies de recherche intéressantes.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Les fichiers qui accompagnent mon document ont été réalisés avec le logiciel Latex et les simulations ont été réalisés par Splus(R). / Dans ce mémoire, nous travaillons sur une méthode de simulation de Monte-Carlo qui utilise des variables antithétiques pour estimer un intégrale de la fonction f(x) sur un intervalle (0,1] où f peut être une fonction monotone, non-monotone ou une autre fonction difficile à simuler. L'idée principale de la méthode qu'on propose est de subdiviser l'intervalle (0,1] en m sections dont chacune est subdivisée en l sous intervalles. Cette technique se fait en plusieurs étapes et à chaque fois qu'on passe à l'étape supérieure la variance diminue. C'est à dire que la variance obtenue à la kième étape est plus petite que celle trouvée à la (k-1)ième étape ce qui nous permet également de rendre plus petite l'erreur d’estimation car l'estimateur de l'intégrale de f(x) sur [0,1] est sans biais. L'objectif est de trouver m, le nombre optimal de sections, qui permet de trouver cette diminution de la variance. / In this master thesis, we consider simulation methods based on antithetic variates for estimate integrales of f(x) on interval (0,1] where f is monotonic function, not a monotonic function or a function difficult to integrate. The main idea consists in subdividing the (0,1] in m sections of which each one is subdivided in l subintervals. This method is done recursively. At each step the variance decreases, i.e. The variance obtained at the kth step is smaller than that is found at the (k-1)th step. This allows us to reduce the error in the estimation because the estimator of integrales of f(x) on interval [0,1] is unbiased. The objective is to optimize m.

Dans ce mémoire, nous travaillons sur une méthode de simulation de Monte-Carlo qui utilise des variables antithétiques pour estimer un intégrale de la fonction f(x) sur un intervalle (0,1] où f peut être une fonction monotone, non-monotone ou une autre fonction difficile à simuler. L'idée principale de la méthode qu'on propose est de subdiviser l'intervalle (0,1] en m sections dont chacune est subdivisée en l sous intervalles. Cette technique se fait en plusieurs étapes et à chaque fois qu'on passe à l'étape supérieure la variance diminue. C'est à dire que la variance obtenue à la kième étape est plus petite que celle trouvée à la (k-1)ième étape ce qui nous permet également de rendre plus petite l'erreur d’estimation car l'estimateur de l'intégrale de f(x) sur [0,1] est sans biais. L'objectif est de trouver m, le nombre optimal de sections, qui permet de trouver cette diminution de la variance. / In this master thesis, we consider simulation methods based on antithetic variates for estimate integrales of f(x) on interval (0,1] where f is monotonic function, not a monotonic function or a function difficult to integrate. The main idea consists in subdividing the (0,1] in m sections of which each one is subdivided in l subintervals. This method is done recursively. At each step the variance decreases, i.e. The variance obtained at the kth step is smaller than that is found at the (k-1)th step. This allows us to reduce the error in the estimation because the estimator of integrales of f(x) on interval [0,1] is unbiased. The objective is to optimize m. / Les fichiers qui accompagnent mon document ont été réalisés avec le logiciel Latex et les simulations ont été réalisés par Splus(R).

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Les nombres aléatoires sont indispensables dans de nombreuses applications notamment en cryptographie où l’aléa est utilisé dans les protocoles de sécurité. Les générateurs de nombres aléatoires, plus connus sous le nom de RNG comme “Random Number Generator” se déclinent en deux familles, les PRNG (Pseudo RNG) qui sont des générateurs de nombres aléatoires ayant des séquences déterministes et les TRNG (True RNG) qui sont des générateurs d’aléa “vrai”, donc non prédictibles. Les applications cryptographiques utilisent à la fois les TRNG et les PRNG. Un PRNG nécessite une valeur initiale, ou graine, qui peut être la sortie d’un TRNG. Les TRNG tirent profit de l’aléa des phénomènes physiques. Les TRNGs dans les technologies numériques comme les FPGAs font appel à des oscillateurs qui présentent l’inconvénient de pouvoir être attaqués par couplage harmonique. De façon à évaluer la qualité entropique d’un TRNG, des standards basés sur des tests statistiques ont été élaborés par des organismes de certification comme le NIST ou la BSI. Cependant, il est recommandé de formaliser, par le biais d’un modèle, le caractère stochastique de la génération d’aléa. Dans cette thèse, nous étudions une architecture de TRNG, peu coûteuse et robuste face aux attaques harmoniques car elle n’utilise pas d’oscillateurs. Ce TRNG extrait une variable aléatoire en exploitant à la fois les états métastables des bascules et les fluctuations temporelles (ou gigue) des signaux échantillonnés. Nous proposons par la suite un modèle stochastique qui nous permet de décrire le comportement aléatoire du TRNG indépendamment de la technologie ciblée. Les caractérisations et évaluations sur des circuits prototypes en technologies FPGA et ASIC montrent que l’architecture TRNG proposée génère de l’aléa de qualité et est robuste face aux variations environnementales / Random numbers are required in numerous applications namely in cryptography where randomness is used in security protocols. There are two main classes of Random Number Generators (RNG) : The Pseudo RNG (PRNG) which have a deterministic sequence, and the True RNG (TRNG) which generates unpredictable random numbers. Cryptographic applications use both TRNG and PRNG. The PRNG needs an initial value, or seed, which can be the output of a TRNG. In digital technologies, like FPGAs, TRNG are commonly based on oscillators which have the drawback of being biased by harmonic coupling. In order to assess the entropic quality of TRNGs, standards based on statistical tests have been elaborated by certification organisms namely the NIST and the BSI. However, it is recommended to formalize the stochastic behaviour of the randomness generation process. In this Ph.D, we address the design and quality evaluation of TRNGs in digital circuits. We study of a low-cost digital TRNG without oscillators, hence robust against harmonics attacks. The proposed TRNG exploits both the metastability phenomenon and the jitter noise in CMOS digital flip-flops to generate the random numbers. A stochastic model of this TRNG has been formalized. This model describes the random generation process regardless of the targeted technology. The characterization and evaluation on a prototype circuit, in FPGA and ASIC technologies, has shown that the proposed TRNG architecture generates randomness of good quality and is robust against environmental variations.