Popularity of mobile devices along with the presence of ad hoc networks requiring no infrastructure has contributed to recent advances in the field of mobile computing in ad hoc networks. Mobile ad hoc networks have been mostly utilized in military environments. The recent advances in ad hoc network technology now introduce a new class of applications. In this thesis, we design, implement and analyze a multi-hop ad hoc messenger application using Pocket PCs and Microsoft .Net Compact Framework. Pocket PCs communicate wirelessly with each other using the IEEE 802.11b technology without the use of an infrastructure. The main protocol implemented in this application is based on Dynamic Source Routing (DSR), which consists of two important mechanisms, Route Discovery and Route Maintenance. We adopt DSR since DSR operates solely based on source routing and "on-demand" process, so each packet does not have to transmit any periodic advertisement packets or routing information. These characteristics are desirable for the ad hoc messenger application for which a conversation is source-initiated on-demand. To test our application easily, we have developed a testing strategy by which a mobility configuration file is pre-generated describing the mobility pattern of each node generated based on the random waypoint mobility model. A mobility configuration file thus defines topology changes at runtime and is used by all nodes to know whether they can communicate with others in a single-hop or multi-hops during an experimental run. We use five standard metrics to test the performance of the wireless ad hoc messenger application implemented based on DSR, namely, (1) average latency to find a new route, (2) average latency to deliver a data packet, (3) delivery ratio of data packets, (4) normalized control overhead, and (5) throughput. These metrics test the correctness and efficiency of the wireless ad hoc messenger application using the DSR protocol in an 802.11 ad hoc network that imposes limitations on bandwidth and resources of each mobile device. We test the effectiveness of certain design alternatives for implementing the ad hoc messenger application with these five metrics under various topology change conditions by manipulating the speed and pause-time parameters in the random waypoint model. The design alternatives evaluated include (1) Sliding Window Size (SWS) for end-to-end reliable communication control; (2) the use of per-hop acknowledgement packets (called receipt packets) deigned for rapid detection of route errors by intermediate nodes; and (3) the use of cache for path look-up during route discovery and maintenance. Our analysis results indicate that as the node speed increases, the system performance deteriorates because a higher node speed causes the network topology to change more frequently under the random waypoint mobility model, causing routes to be broken. On the other hand, as the pause time increases, the system performance improves due to a more stable network topology. For the design alternatives evaluated in our wireless ad hoc messenger, we discover that as SWS increases, the system performance also increases until it reaches an optimal SWS value that maximizes the performance due to a balance of a higher level of data parallelism introduced and a higher level of medium contention in 802.11 because of more packets being transmitted simultaneously as SWS increases. Beyond the optimal SWS, the system performance deteriorates as SWS increases because the heavy medium contention effect outweighs the benefit due to data parallelism. We also discover that the use of receipt packets is helpful in a rapidly changing network but is not beneficial in a stable network. There is a break-even point in the frequency of topology changes beyond which the use of receipt packets helps quickly detect route errors in a dynamic network and would improve the system performance. Lastly, the use of cache is rather harmful in a frequently changing network because stale information stored in the cache of a source node may adversely cause more route errors and generate a higher delay for the route discovery process. There exists a break-even point beyond which the use of cache is not beneficial. Our wireless ad hoc messenger application can be used in a real chatting setting allowing Pocket PC users to chat instantly in 802.11 environments. The design and development of the dynamic topology simulation tool to model movements of nodes and the automatic testing and data collection tool to facilitate input data selection and output data analysis using XML are also a major contribution. The experimental results obtained indicate that there exists an optimal operational setting in the use of SWS, receipt packets and cache, suggesting that the wireless ad hoc messenger should be implemented in an adaptive manner to fine-tune these design parameters based on the current network condition and performance data monitored to maximize the system performance. / Master of Science

Opportunistic Routing (OR) can be used as an alternative to the legacy routing (LR) protocols in networks with a broadcast lossy channel and possibility of overhearing the signal. The power line medium creates such an environment. OR can better exploit the channel than LR because it allows the cooperation of all nodes that receive any data. With LR, only a chain of nodes is selected for communication. Other nodes drop the received information. We investigate OR for the one-source one-destination scenario with one traffic flow. First, we evaluate the upper bound on the achievable data rate and advocate the decentralized algorithm for its calculation. This knowledge is used in the design of Basic Routing Rules (BRR). They use the link quality metric that equals the upper bound on the achievable data rate between the given node and the destination. We call it the node priority. It considers the possibility of multi-path communication and the packet loss correlation. BRR allows achieving the optimal data rate pertaining certain theoretical assumptions. The Extended BRR (BRR-E) are free of them. The major difference between BRR and BRR-E lies in the usage of Network Coding (NC) for prognosis of the feedback. In this way, the protocol overhead can be severely reduced. We also study Automatic Repeat-reQuest (ARQ) mechanism that is applicable with OR. It differs to ARQ with LR in that each sender has several sinks and none of the sinks except destination require the full recovery of the original message. Using BRR-E, ARQ and other services like network initialization and link state control, we design the Advanced Network Coding based Opportunistic Routing protocol (ANChOR). With the analytic and simulation results we demonstrate the near optimum performance of ANChOR. For the triangular topology, the achievable data rate is just 2% away from the theoretical maximum and it is up to 90% higher than it is possible to achieve with LR. Using the G.hn standard, we also show the full protocol stack simulation results (including IP/UDP and realistic channel model). In this simulation we revealed that the gain of OR to LR can be even more increased by reducing the head-of-the-line problem in ARQ. Even considering the ANChOR overhead through additional headers and feedbacks, it outperforms the original G.hn setup in data rate up to 40% and in latency up to 60%.:1 Introduction 2 1.1 Intra-flow Network Coding 6 1.2 Random Linear Network Coding (RLNC) 7 2 Performance Limits of Routing Protocols in PowerLine Communications (PLC) 13 2.1 System model 14 2.2 Channel model 14 2.3 Upper bound on the achievable data rate 16 2.4 Achieving the upper bound data rate 17 2.5 Potential gain of Opportunistic Routing Protocol (ORP) over Common Single-path Routing Protocol (CSPR) 19 2.6 Evaluation of ORP potential 19 3 Opportunistic Routing: Realizations and Challenges 24 3.1 Vertex priority and cooperation group 26 3.2 Transmission policy in idealized network 34 3.2.1 Basic Routing Rules (BRR) 36 3.3 Transmission policy in real network 40 3.3.1 Purpose of Network Coding (NC) in ORP 41 3.3.2 Extended Basic Routing Rules (BRR) (BRR-E) 43 3.4 Automatic ReQuest reply (ARQ) 50 3.4.1 Retransmission request message contents 51 3.4.2 Retransmission Request (RR) origination and forwarding 66 3.4.3 Retransmission response 67 3.5 Congestion control 68 3.5.1 Congestion control in our work 70 3.6 Network initialization 74 3.7 Formation of the cooperation groups (coalitions) 76 3.8 Advanced Network Coding based Opportunistic Routing protocol (ANChOR) header 77 3.9 Communication of protocol information 77 3.10 ANChOR simulation . .79 3.10.1 ANChOR information in real time .80 3.10.2 Selection of the coding rate 87 3.10.3 Routing Protocol Information (RPI) broadcasting frequency 89 3.10.4 RR contents 91 3.10.5 Selection of RR forwarder 92 3.10.6 ANChOR stability 92 3.11 Summary 95 4 ANChOR in the Gigabit Home Network (G.hn) Protocol 97 4.1 Compatibility with the PLC protocol stack 99 4.2 Channel and noise model 101 4.2.1 In-home scenario 102 4.2.2 Access network scenario 102 4.3 Physical layer (PHY) layer implementation 102 4.3.1 Bit Allocation Algorithm (BAA) 103 4.4 Multiple Access Control layer (MAC) layer 109 4.5 Logical Link Control layer (LLC) layer 111 4.5.1 Reference Automatic Repeat reQuest (ARQ) 111 4.5.2 Hybrid Automatic Repeat reQuest (HARQ) in ANChOR 114 4.5.3 Modeling Protocol Data Unit (PDU) erasures on LLC 116 4.6 Summary 117 5 Study of G.hn with ANChOR 119 5.1 ARQ analysis 119 5.2 Medium and PHY requirements for “good” cooperation 125 5.3 Access network scenario 128 5.4 In-home scenario 135 5.4.1 Modeling packet erasures 136 5.4.2 Linear Dependence Ratio (LDR) 139 5.4.3 Worst case scenario 143 5.4.4 Analysis of in-home topologies 145 6 Conclusions . . . . . . . . . . . . . . . 154 A Proof of the neccessity of the exclusion rule 160 B Gain of ORPs to CSRPs 163 C Broadcasting rule 165 D Proof of optimality of BRR for triangular topology 167 E Reducing the retransmission probability 168 F Calculation of Expected Average number of transmissions (EAX) for topologies with bi-directional links 170 G Feedback overhead of full coding matrices 174 H Block diagram of G.hn physical layer in ns-3 model 175 I PER to BER mapping 177

This thesis introduces a new model formulation to solve routing and scheduling problems, with the main applications in answering routing and scheduling problems faced by a sea-cargo shipping company and a railroad company. For the work in sea-cargo routing and scheduling, we focus on the tramp shipping operation. Tramp shipping is a demand-driven type of shipping operation which does not have fixed schedules. The schedules are based on the pickup and download locations of profitable service requests. Given set of products distributed among a set of ports, with each product having pickup and download time windows and a destination port, the problem is to find the schedule for a fleet of ships that maximizes profit over a specified time horizon. The problem is modeled as a Mixed Integer Non-Linear Program and reformulated as an equivalent Mixed Integer Linear Program. Three heuristic methods, along with computational results, are presented. We also exploit the special structure enjoyed by our model and introduce an upper-bounding problem to the model. With a little modification, the model is readily extendable to reflect soft time windows and inter-ship cargo-transfers. The other part of our work deals with train routing and scheduling. A typical train shipment consists of a set of cars having a common origin and destination. To reduce the handling of individual shipments as they travel, shipments are grouped into blocks. The problem is that given sets of blocks to be carried from origins to destinations, construct the most cost effective train routes and schedules and determine block-to-train assignments, such that the number of block transfers (block swaps) between trains, the number of trains used, and some other cost measures are minimized. Incorporating additional precedence requirements, the modeling techniques from the shipping research are employed to formulate a mixed integer nonlinear program for this train routing and scheduling problem. Computational results are presented.

This work deals with routing protocols for ad hoc wireless networks. First ad hoc networks are introduced. Routing protocols are then classified according to several criteria. Four routing protocols algorithms are described. They are proactive protocols DSDV and CGSR, reactive DSR and hybrid ZRP. Next AODV routing protocol is described in details. Advantages and disadvantages of AODV and two variants of AODV are also introduced. A new protocol is designed based on the disadvantages of the AODV protocol. This work also describes the implementation and integration of the new protocol in the ns-2 simulator. Results of the simulations are presented.

<p>Network on Chip is a scalable and flexible communication infrastructure for the design of core based System on Chip. Communication performance of a NoC depends heavily on the routing algorithm. Deterministic and adaptive distributed routing algorithms have been advocated in all the current NoC architectural proposals. In this thesis we make a case for the use of source routing for NoCs, especially for regular topologies like mesh. The advantages of source routing include in-order packet delivery; faster and simpler router design; and possibility of mixing non-minimal paths in a mainly minimal routing. We propose a method to compute paths for various communications in such a way that traffic congestion is avoided while ensuring deadlock free routing. We also propose an efficient scheme to encode the paths.</p><p>We developed a tool in Matlab that computes paths for source routing for both general and application specific communications. Depending upon the type of traffic, this tool computes paths for source routing by selecting best routing algorithm out of many routing algorithms. The tool uses a constructive path improvement algorithm to compute paths that give more uniform link load distribution. It also generates different types of traffics. We also developed a simulator capable of simulating source routing for mesh topology NoC. The experiments and simulations which we performed were successful and the results show that the advantages of source routing especially lower packet latency more than compensate its disadvantages. The results also demonstrate that source routing can be a good routing candidate for practical core based SoCs design using network on chip communication infrastructure.</p>

Ein großer Anteil des Datenverkehrs in „Internet Service Provider“ (ISP)-Netzen wird heutzutage von „Content Delivery Networks“ (CDNs) verursacht. Betreiber von CDNs verwenden Lastverteilungsmechanismen um die Auslastung ihrer CDN-Infrastruktur zu vergleichmäßigen (Load Balancing). Dies geschieht ohne Abstimmung mit den ISP-Betreibern. Es können daher große Verkehrslastverschiebungen sowohl innerhalb eines ISP-Netzes, als auch auf den Verbindungsleitungen zwischen ISP-Netz und CDNs auftreten. In der vorliegenden Arbeit wird untersucht, welche nicht-kooperativen Möglichkeiten ein ISP hat, um Verkehrslastverschiebungen, welche durch Lastverteilungsmechanismen innerhalb eines CDNs verursacht werden, entgegenzuwirken bzw. abzumildern. Die Grundlage für diese Untersuchung bildet die Analyse des Serverauswahlverhaltens des YouTube-CDNs. Hierzu ist ein aktives Messverfahren entwickelt worden, um das räumliche und zeitliche Verhalten der YouTube-Serverauswahl bestimmen zu können. In zwei Messstudien wird die Serverauswahl in deutschen und europäischen ISP-Netzen untersucht. Auf Basis dieser Studien wird ein Verkehrsmodell entwickelt, welches die durch Änderungen der YouTube-Serverauswahl verursachten Verkehrslastverschiebungen abbildet. Das Verkehrsmodell wiederum bildet die Grundlage für die Bestimmung optimaler Routen im ISP-Netz, welche hohe Robustheit gegenüber CDN-bedingte Verkehrslastverschiebungen aufweisen (Alpha-robuste Routingoptimierung). Für die Lösung des robusten Routing-Optimierungsproblems wird ein iteratives Verfahren entwickelt sowie eine kompakte Reformulierung vorgestellt. Die Leistungsfähigkeit des Alpha-robusten Routings wird anhand von drei Beispielnetztopologien untersucht. Das neue Verfahren wird mit alternativen robusten Routingverfahren und einem nicht-robusten Verfahren verglichen. Neben der robusten Routingoptimierung werden in der Arbeit drei weitere Ideen für nicht-kooperative Methoden vorgestellt (BGP-, IP-Präix- und DNS-basierte Methode), um CDN-bedingten Verkehrslastverschiebungen entgegenzuwirken.

There is a lot of alternative routing protocols used in wireless communications. One of these protocols is Ad Hoc On-Demand Distance Vector routing protocol (AODV). This protocol is used in the mobile ad-hoc networks which are self-configuring networks consisting of the independent mobile devices where each one of these devices acts as a router and forwards traffic from other devices. AODV protocol uses hop count as a routing metric, but in the many cases this metric is not optimal in the wireless networks. The goal of this thesis is to propose the alternative criteria which can be used to select best routes. An integral part of this thesis is the experimental implementations of suggested metrics which will be simulated and evaluated in the selected simulation tool. The conclusion of the thesis analyses results obtained from the simulations of the individual suggested versions.

L'objectif de ce travail de thèse est de proposer des approches algorithmiques permettant de traiter la problématique du routage adaptatif (RA) dans un réseau de communication à trafic irrégulier. L'analyse des algorithmes existants nous a conduit à retenir comme base de travail l'algorithme Q-Routing (QR); celui-ci s'appuie sur la technique d'apprentissage par renforcement basée sur les modèles de Markov. L'efficacité de ce type de routage dépend fortement des informations sur la charge et la nature du trafic sur le réseau. Ces dernières doivent être à la fois, suffisantes, pertinentes et reflétant la charge réelle du réseau lors de la phase de prise de décision. Pour remédier aux inconvénients des techniques utilisant le QR, nous avons proposé deux algorithmes de RA. Le premier, appelé Q-Neural Routing, s'appuie sur un modèle neuronal stochastique pour estimer et mettre à jour les paramètres nécessaires au RA. Afin d'accélérer le temps de convergence, une deuxième approche est proposée : K-Shortest path Q-Routing. Elle est basée sur la technique de routage multi chemin combiné avec l'algorithme QR, l'espace d'exploration étant réduit aux k meilleurs chemins. Les deux algorithmes proposés sont validés et comparés aux approches traditionnelles en utilisant la plateforme de simulation OPNET, leur efficacité au niveau du RA est mise particulièrement en évidence. En effet, ceux-ci permettent une meilleure prise en compte de l'état du réseau contrairement aux approches classiques.

The implementation of managed lanes (MLs), also known as dynamically priced express lanes, to improve freeway traffic flow and personal throughput is on the rise. Congestion pricing is increasingly becoming a common strategy for congestion management, often requiring microscopic simulation during both planning and operational stages. VISSIM is a recognized microscopic simulation software used for analyzing the performance of managed lanes (MLs). This thesis addressed two important microscopic simulation issues that affect the evaluation results of MLs. One of the microscopic simulation issues that has not yet been addressed by previous studies is the required minimum managed lane routing decision (MLRD) distance upstream of the ingress point of MLs. Decision distance is an optimal upstream distance prior to the ingress at which drivers decide to use MLs and change lanes to orient on a side of MLs ingress. To answer this question, this study used a VISSIM model simulating I-295 proposed MLs in Jacksonville, Florida, United States (U.S), varying the MLRD point at regular intervals from 500 feet to 7,000 feet for different levels of service (LOS) input. Three measures of effectiveness (MOEs) - speed, the number of vehicles changing lanes, and following distance - were used for the analysis. These MOEs were measured in the 500 feet zone prior to the ingress. The results indicate that as the LOS deteriorates, speed decreases, the number of vehicles changing lanes increases, and the following distance decreases. When the LOS is constant, the increase in the MLRD distance from the ingress point was associated with the increase in the speed at the 500 feet zone prior to the ingress, less number of lane changes, and the increase in following vehicle gap. However, the MOEs approached constant values after reaching a certain MLRD distance. LOS D was used to determine the minimum MLRD distance to the ingress of the MLs. The determined minimum MLRD distances were 4,000 and 3,000 feet for 6 and 3 lane segments prior to the ingress point, respectively. Another issue addressed in this thesis is the managed lane evaluation (MLE) outputs, which include speed, travel time, density, and tolls. In computing the performance measures, the existing VISSIM managed lane evaluation (EVMLE) tool is designed to use the section starting at the point when vehicles are assigned to use MLs, also known as the MLRD point, which is located upstream of the ingress. The longer the MLRD distance from the ingress, the more the EVMLE tool uses the traffic conditions of the MLs traffic before entering the ML in its computations. This study evaluates the impact of the MLRD distance on the EVMLE outputs and presents a proposed algorithm that addresses the EVMLE shortcomings. In order to examine the influence of the MLRD distance on the outputs of the above-mentioned two algorithms, simulation scenarios of varying MLRD distances from 500 ft to 7,000 feet from the ingress were created. For demonstration purposes, only the speed was used to represent other performance measures. The analysis of variance (ANOVA) test was performed to determine whether there was a significant difference in the speed results with the change in the MLRD distance. According to the ANOVA results, the EVMLE tool produced ML speeds that are MLRD dependent, yielding lower speeds with an increased MLRD distance. On the other hand, the ML speed results from the proposed algorithm were fairly constant, regardless of the MLRD distance.

Ein großer Anteil des Datenverkehrs in „Internet Service Provider“ (ISP)-Netzen wird heutzutage von „Content Delivery Networks“ (CDNs) verursacht. Betreiber von CDNs verwenden Lastverteilungsmechanismen um die Auslastung ihrer CDN-Infrastruktur zu vergleichmäßigen (Load Balancing). Dies geschieht ohne Abstimmung mit den ISP-Betreibern. Es können daher große Verkehrslastverschiebungen sowohl innerhalb eines ISP-Netzes, als auch auf den Verbindungsleitungen zwischen ISP-Netz und CDNs auftreten. In der vorliegenden Arbeit wird untersucht, welche nicht-kooperativen Möglichkeiten ein ISP hat, um Verkehrslastverschiebungen, welche durch Lastverteilungsmechanismen innerhalb eines CDNs verursacht werden, entgegenzuwirken bzw. abzumildern. Die Grundlage für diese Untersuchung bildet die Analyse des Serverauswahlverhaltens des YouTube-CDNs. Hierzu ist ein aktives Messverfahren entwickelt worden, um das räumliche und zeitliche Verhalten der YouTube-Serverauswahl bestimmen zu können. In zwei Messstudien wird die Serverauswahl in deutschen und europäischen ISP-Netzen untersucht. Auf Basis dieser Studien wird ein Verkehrsmodell entwickelt, welches die durch Änderungen der YouTube-Serverauswahl verursachten Verkehrslastverschiebungen abbildet. Das Verkehrsmodell wiederum bildet die Grundlage für die Bestimmung optimaler Routen im ISP-Netz, welche hohe Robustheit gegenüber CDN-bedingte Verkehrslastverschiebungen aufweisen (Alpha-robuste Routingoptimierung). Für die Lösung des robusten Routing-Optimierungsproblems wird ein iteratives Verfahren entwickelt sowie eine kompakte Reformulierung vorgestellt. Die Leistungsfähigkeit des Alpha-robusten Routings wird anhand von drei Beispielnetztopologien untersucht. Das neue Verfahren wird mit alternativen robusten Routingverfahren und einem nicht-robusten Verfahren verglichen. Neben der robusten Routingoptimierung werden in der Arbeit drei weitere Ideen für nicht-kooperative Methoden vorgestellt (BGP-, IP-Präix- und DNS-basierte Methode), um CDN-bedingten Verkehrslastverschiebungen entgegenzuwirken.