In the thesis of “Mohammed Aijaz Mohiuddin”, Engineering Nature-Inspired Heuristics for the Open Shortest Path First Weight Setting Problem, nature inspired heuristics were developed. Besides the existing two objectives, namely maximum utilization and the number of congested links, a third objective namely the number of unused links was used to formulate the fuzzy based objective function for the OSPFWS problem. The idea was to make use unused network links if any. Furthermore, a hybrid fuzzy based evolutionary Particle Swarm Optimization (FEPSO) algorithm was designed that harnessed evolutionary intelligence along with swarm intelligence. The proposed FEPSO algorithm was tested on different size test cases and its performance was mutually compared with other algorithms namely Simulated Annealing, Simulated Evolution, Particle Swarm Optimization, Weighted Aggregation Particle Swarm Optimization, Pareto-dominance Particle Swarm Optimization and Non-dominating Sorting Genetic Algorithm. Obtained results suggested the better performance of FEPSO among other algorithms over majority of test cases. / Thesis (PHD)--University of Pretoria, 2018. / Computer Science / PhD / Unrestricted

The progress which has been made in semiconductor chip production in recent years enables a multitude of cores on a single die. However, due to further decreasing structure sizes, fault tolerance and energy consumption will represent key challenges. Furthermore, an efficient communication infrastructure is indispensable due to the high parallelism at those systems. The predominant communication system at such highly parallel systems is a Network on Chip (NoC). The focus of this thesis is on NoCs which are based on deflection routing. In this context, contributions are made to two domains, fault tolerance and dimensioning of the optimal link width. Both aspects are essential for the application of reliable, energy efficient, and deflection routing based NoCs. It is expected that future semiconductor systems have to cope with high fault probabilities. The inherently given high connectivity of most NoC topologies can be exploited to tolerate the breakdown of links and other components. In this thesis, a fault-tolerant router architecture has been developed, which stands out for the deployed interconnection architecture and the method to overcome complex fault situations. The presented simulation results show, all data packets arrive at their destination, even at high fault probabilities. In contrast to routing table based architectures, the hardware costs of the herein presented architecture are lower and, in particular, independent of the number of components in the network. Besides fault tolerance, hardware costs and energy efficiency are of great importance. The utilized link width has a decisive influence on these aspects. In particular, at deflection routing based NoCs, over- and under-sizing of the link width leads to unnecessary high hardware costs and bad performance, respectively. In the second part of this thesis, the optimal link width at deflection routing based NoCs is investigated. Additionally, a method to reduce the link width is introduced. Simulation and synthesis results show, the herein presented method allows a significant reduction of hardware costs at comparable performance. / Die Fortschritte der letzten Jahre bei der Fertigung von Halbleiterchips ermöglichen eine Vielzahl an Rechenkernen auf einem einzelnen Chip. Die in diesem Zusammenhang immer weiter sinkenden Strukturgrößen führen jedoch dazu, dass Fehlertoleranz und Energieverbrauch zentrale Herausforderungen darstellen werden. Aufgrund der hohen Parallelität in solchen Systemen, ist außerdem eine leistungsfähige Kommunikationsinfrastruktur unabdingbar. Das in diesen hochgradig parallelen Systemen überwiegend eingesetzte System zur Datenübertragung ist ein Netzwerk auf einem Chip (engl. Network on Chip (NoC)). Der Fokus dieser Dissertation liegt auf NoCs, die auf dem Prinzip des sog. Deflection Routing basieren. In diesem Kontext wurden Beiträge zu zwei Bereichen geleistet, der Fehlertoleranz und der Dimensionierung der optimalen Breite von Verbindungen. Beide Aspekte sind für den Einsatz zuverlässiger, energieeffizienter, Deflection Routing basierter NoCs essentiell. Es ist davon auszugehen, dass zukünftige Halbleiter-Systeme mit einer hohen Fehlerwahrscheinlichkeit zurecht kommen müssen. Die hohe Konnektivität, die in den meisten NoC Topologien inhärent gegeben ist, kann ausgenutzt werden, um den Ausfall von Verbindungen und anderen Komponenten zu tolerieren. Im Rahmen dieser Arbeit wurde vor diesem Hintergrund eine fehlertolerante Router-Architektur entwickelt, die sich durch das eingesetzte Verbindungsnetzwerk und das Verfahren zur Überwindung komplexer Fehlersituationen auszeichnet. Die präsentierten Simulations-Ergebnisse zeigen, dass selbst bei sehr hohen Fehlerwahrscheinlichkeiten alle Datenpakete ihr Ziel erreichen. Im Vergleich zu Router-Architekturen die auf Routing-Tabellen basieren, sind die Hardware-Kosten der hier vorgestellten Router-Architektur gering und insbesondere unabhängig von der Anzahl an Komponenten im Netzwerk, was den Einsatz in sehr großen Netzen ermöglicht. Neben der Fehlertoleranz sind die Hardware-Kosten sowie die Energieeffizienz von NoCs von großer Bedeutung. Einen entscheidenden Einfluss auf diese Aspekte hat die verwendete Breite der Verbindungen des NoCs. Insbesondere bei Deflection Routing basierten NoCs führt eine Über- bzw. Unterdimensionierung der Breite der Verbindungen zu unnötig hohen Hardware-Kosten bzw. schlechter Performanz. Im zweiten Teil dieser Arbeit wird die optimale Breite der Verbindungen eines Deflection Routing basierten NoCs untersucht. Außerdem wird ein Verfahren zur Reduzierung der Breite dieser Verbindungen vorgestellt. Simulations- und Synthese-Ergebnisse zeigen, dass dieses Verfahren eine erhebliche Reduzierung der Hardware-Kosten bei ähnlicher Performanz ermöglicht.

Online decision making is a kind of machine learning problems where decisions are made in a sequential manner so as to accumulate as many rewards as possible. Typical examples include multi-armed bandit (MAB) problems where an agent needs to decide which arm to pull in each round, and network routing problems where each router needs to decide the next hop for each packet. Thompson sampling (TS) is an efficient and effective algorithm for online decision making problems. Although TS has been proposed for a long time, it was not until recent years that the theoretical guarantees for TS in the standard MAB were given. In this thesis, we first analyze the performance of TS both theoretically and practically in a special MAB called combinatorial MAB with sleeping arms and long-term fairness constraints (CSMAB-F). Then, we apply TS to a novel reactive network routing problem, called \emph{opportunistic routing without link metrics known a priori}, and use the proof techniques we developed for CSMAB-F to analyze the performance. / Graduate

The growing usage of computer networks is requiring improvements in network technologies and management techniques so users will receive high quality service. As more individuals transmit data through a computer network, the quality of service received by the users begins to degrade. A major aspect of computer networks that is vital to quality of service is data routing. A more effective method for routing data through a computer network can assist with the new problems being encountered with today's growing networks. Effective routing algorithms use various techniques to determine the most appropriate route for transmitting data. Determining the best route through a wide area network (WAN), requires the routing algorithm to obtain information concerning all of the nodes, links, and devices present on the network. The most relevant routing information involves various measures that are often obtained in an imprecise or inaccurate manner, thus suggesting that fuzzy reasoning is a natural method to employ in an improved routing scheme. The neural network is deemed as a suitable accompaniment because it maintains the ability to learn in dynamic situations. Once the neural network is initially designed, any alterations in the computer routing environment can easily be learned by this adaptive artificial intelligence method. The capability to learn and adapt is essential in today's rapidly growing and changing computer networks. These techniques, fuzzy reasoning and neural networks, when combined together provide a very effective routing algorithm for computer networks. Computer simulation is employed to prove the new fuzzy routing algorithm outperforms the Shortest Path First (SPF) algorithm in most computer network situations. The benefits increase as the computer network migrates from a stable network to a more variable one. The advantages of applying this fuzzy routing algorithm are apparent when considering the dynamic nature of modern computer networks. / Ph. D.

No / A new scheme is presented for partitioning a network having a specific number of nodes and degree of connectivity such that the number of operations required to find a constrained path between a source node and destination node, averaged over all source-destination pairs, is minimised. The scheme can speed up the routing function, possibly by orders of magnitude under favourable conditions, at the cost of a sub-optimal solution.

Satisfactory results obtained from sensor networks and the ongoing development in electronics and wireless communications have led to an impressive boost in the number of applications based on WSNs. Along with the growth in popularity of WSNs, previously implemented solutions need further improvements and new challenges arise which need to be solved. One of the main concerns regarding WSNs is the existence of security threats against their routing operations. Likelihood of security attacks in a structure suffering from resource constraints makes it an important task to choose proper security mechanisms for the routing decisions in various types of WSN applications. The main purpose of this study is to survey WSNs, routing protocols, security attacks against routing layer of a WSN, introduction of Trust based models which are an effective defense mechanism against security attacks in WSNs and finally, to implement a proposed Trust based routing protocol in order to overcome security attacks. The study begins with a survey of Sensor Networks, after the introduction of WSNs and their related routing protocols, the issue of security attacks against the network layer of a Sensor Network is described with a presentation of different types of attacks and some of Trust based related works. In the final chapters of this research, a novel Trust based AODV protocol will be proposed, implemented and examined in a simulation environment. For this purpose, multiple number of scenarios will be simulated on the AODV protocol with and without Trust mechanism, then the achieved results will be compared to derive a conclusion.

Satisfactory results obtained from sensor networks and the ongoing development in electronics and wireless communications have led to an impressive boost in the number of applications based on WSNs. Along with the growth in popularity of WSNs, previously implemented solutions need further improvements and new challenges arise which need to be solved. One of the main concerns regarding WSNs is the existence of security threats against their routing operations. Likelihood of security attacks in a structure suffering from resource constraints makes it an important task to choose proper security mechanisms for the routing decisions in various types of WSN applications. The main purpose of this study is to survey WSNs, routing protocols, security attacks against routing layer of a WSN, introduction of Trust based models which are an effective defense mechanism against security attacks in WSNs and finally, to implement a proposed Trust based routing protocol in order to overcome security attacks. The study begins with a survey of Sensor Networks, after the introduction of WSNs and their related routing protocols, the issue of security attacks against the network layer of a Sensor Network is described with a presentation of different types of attacks and some of Trust based related works. In the final chapters of this research, a novel Trust based AODV protocol will be proposed, implemented and examined in a simulation environment. For this purpose, multiple number of scenarios will be simulated on the AODV protocol with and without Trust mechanism, then the achieved results will be compared to derive a conclusion.

This dissertation focuses on modeling parking search behavior in traffic assignment models. Parking contributes greatly to urban traffic congestion. When the parking supply is scarce, it is very common for a vehicle to circle around for a considerable period just for an open parking spot. This circling or "cruising" add additional traffic flow onto the network. However, traditional traffic assignment models either ignore parking completely or simply treat it in limited ways. Most traffic assignment models simply assume travelers just directly drive from their origin to their destination without considering the parking search behavior. This would result in a systematic underestimation of road traffic flows and congestion which may mislead traffic managers to give inappropriate planning or control strategies. Models which do incorporate parking effects either constrain their implementation in limited small networks or ignore the stochasticity of parking choice by drivers. This dissertation improves upon previous research into network parking modeling, explicitly capturing drivers' behavior and stochasticity in the parking search process, and is applicable to general networks. This dissertation constructs three types of parking search models. The first one is to model a single driver's parking search process, taking into account the likelihood of finding parking in different locations from past experience as well as observations gained during the search itself. This model uses the a priori probability of finding parking on a link, which reflects the average possibility of finding a parking space based on past experience. This probability is then adjusted based on observations during the current search. With these concepts, the parking search behavior is modeled as a Markov decision process (MDP). The primary contribution of the proposed model is its ability to reflect history dependence which combines the advantages of assuming "full reset" and "no reset" . "Full reset" assumes the probability of finding a parking space on a link is independent of any observations in the current search, while "no reset" assumes the state of parking availability is completely determined by past observations, never changing once observed. For instance, assume that the a priori probability of finding parking on a link is 30%. "Full reset" implies that if a driver drives on this link and sees no parking available, if he or she immediately turns around and drives on the link again, the probability of finding parking is again 30% independent of the past observation. By contrast, "no reset" implies that if a parking space is available on a link, it will always be available to return to in the future at any point. This dissertation develops an "asymptotic reset" principle which generalizes these principles and allows past observations to affect the probability of finding parking on a link and this impact weakens as time goes by. Both full reset and no reset are shown to be special cases of asymptotic reset. The second problem is modeling multiple drivers through a parking search equilibrium on a static network. Similar to the first type of problem, drivers aim to minimize their total travel costs. Their driving and parking search behaviors depend on the probabilities of finding parkings at particular locations in the network. On the other side, these probabilities depend on drivers' route and parking choices. This mutual dependency can be modeled as an equilibrium problem. At the equilibrium condition no driver can improve his or her expected travel cost by unilaterally changing his or her routing and parking search strategy. To accomplish this, a network transformation is introduced to distinguish between drivers searching for parking on a link and drivers merely passing through. The dependence of parking probability on flow rates results in a set of nonlinear flow conservation equations. Nevertheless, under relatively weak assumptions the existence and uniqueness of the network loading can be shown, and an intuitive 'flow-pushing" algorithm can be used to solve for the solution of this nonlinear system. Built on this network loading algorithm, travel times can be computed. The equilibrium is formulated as a variational inequality, and a heuristic algorithm is presented to solve it. An extensive set of numerical tests shows how parking availability and traffic congestion (flows and delays) vary with the input data. The third problem aims at developing a dynamic equivalent for the network parking search equilibrium problem. This problem attempts to model a similar set of features as the static model, but aims to reflect changes in input demand, congestion, and parking space availability over time. The approach described in the dissertation is complementary to the static approach, taking on the flavor of simulation more than mathematical formulation. The dynamic model augments the cell transmission model with additional state variables to reflect parking availability, and integrates this network loading with an MDP-based parking search behavior model. Finally, case studies and sensitivity analysis are taken for each of the three models. These analyses demonstrate the models' validity and feasibility for practice use. Specifically, all the models show excess travel time and flow on the transportation networks because of taking into account the "parking search cruising" and can show the individual links so affected. They all reflect the scattered parking distribution on links while traditional traffic assignment models only assign vehicles onto specified destination nodes. / text

Wireless Sensor Networks (WSNs) have significant potential in many application domains, and are poised for growth in many markets ranging from agriculture and animal welfare to home and office automation. Although sensor network deployments have only begun to appear, the industry still awaits the maturing of this technology to realize its full benefits. The main constraints to large scale commercial adoption of sensor networks are the lack of available network management and control tools for determining the degree of data aggregation prior to transforming it into useful information, localizing the sensors accurately so that timely emergency actions can be taken at exact location, and scheduling data packets so that data are sent based on their priority and fairness. Moreover, due to the limited communication range of sensors, a large geographical area cannot be covered, which limits sensors application domain. Thus, we investigate a scalable and flexible WSN architecture that relies on multi-modal nodes equipped with IEEE 802.15.4 and IEEE 802.11 in order to use a Wi-Fi overlay as a seamless gateway to the Internet through WiMAX networks. We focus on network management approaches such as sensors localization, data scheduling, routing, and data aggregation for the WSN plane of this large scale multimodal network architecture and find that most existing approaches are not scalable, energy efficient, and fault tolerant. Thus, we introduce an efficient approach for each of localization, data scheduling, routing, and data aggregation; and compare the performance of proposed approaches with existing ones in terms of network energy consumptions, localization error, end-to-end data transmission delay and packet delivery ratio. Simulation results, theoretical and statistical analysis show that each of these approaches outperforms the existing approaches. To the best of our knowledge, no integrated network management solution comprising efficient localization, data scheduling, routing, and data aggregation approaches exists in the literature for a large scale WSN. Hence, we e±ciently integrate all network management components so that it can be used as a single network management solution for a large scale WSN, perform experimentations to evaluate the performance of the proposed framework, and validate the results through statistical analysis. Experimental results show that our proposed framework outperforms existing approaches in terms of localization energy consumptions, localization accuracy, network energy consumptions and end-to-end data transmission delay.

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.