MPLS is a widely used technology in the service providers and enterprise networks across the globe. MPLS-enabled infrastructure has the ability to transport any type of payload (ATM, Frame Relay and Ethernet) over it, subsequently providing a multipurpose architecture. An incoming packet is classified only once as it enters into the MPLS domain and gets assigned label information; thereafter all decision processes along a specified path is based upon the attached label rather than destination IP addresses. As network applications are becoming mission critical, the requirements for fault tolerant networks are increasing, as a basic requirement for carrying sensitive traffic. Fault tolerance mechanisms as provided by an IP/MPLS network helps in providing end to end “Quality of Service” within a domain, by better handling blackouts and brownouts. This thesis work reflects how MPLS increases the capability of deployed IP infrastructure to transport traffic in-between end devices with unexpected failures in place. It also focuses on how MPLS converts a packet switched network into a circuit switched network, while retaining the characteristics of packet switched technology. A new mechanism for MPLS fault tolerance is proposed.

Tor is a popular anonymity-preserving network, consisting of routers run by volunteers all around the world. It protects Internet users’ privacy by relaying their network traffic through a series of routers, thus concealing the linkage between the sender and the recipient. Despite the advantage of Tor’s anonymizing capabilities, it also brings extra latency, which discourages more users from joining the network. One of the factors that causes the latency lies in Tor’s circuit scheduling algorithm, which allows busy circuits to crowd out bursty circuits. In this work, we propose and implement a more advanced scheduling algorithm which treats circuits differently, based on their recent activity. In this way, bursty circuits such as those used for web browsing can gain higher priority over busy ones such as used for bulk transfer; the performance for most activities over Tor is improved, while minimal overhead is incurred. Our algorithm has been incorporated into the latest build of Tor.

Delay Tolerant Networks (DTNs) are characterized by the lack of continuous end-to-end connections because of node mobility, constrained power sources, and limited data storage space of some or all of its nodes. Applications of DTNs include vehicular networks and sensor networks in suburban and rural areas. The intermittent connection in DTNs creates a new and challenging environment that has not been tackled before in wireless and wired networks. Traditional routing protocols fail to deliver data packets because they assume the existence of continuous end-to-end connections. To overcome the frequent disconnections, a DTN node is required to store data packets for long periods of time until it becomes in the communication range of other nodes. In addition, to increase the delivery probability, a DTN node spreads multiple copies of the same packet on the network so that one of the copies reaches the destination. Given the limited storage and energy resources of DTN nodes, there is a trade off between maximizing delivery and minimizing storage and energy consumption. DTN routing protocols can be classified as either blind routing, in which no information is provided to select the next node in the path, or guided routing, in which some network information is used to guide data packets to their destinations. In addition they differ in the amount of overhead they impose on the network and its nodes. The objective of DTN routing protocols is to deliver as many packets as possible. Acquiring network information helps in maximizing packet delivery probability and minimizing the network overhead resulting from replicating many packet copies. Network information could be node contact times and durations, node buffer capacities, packet lifetimes, and many others. The more information acquired, the higher performance could be achieved. However, the cost of acquiring the network information in terms of delay and storage could be high to the degree that render the protocol impractical. In designing a DTN routing protocol, the trade-off between the benefits of acquiring information and its costs should be considered. In this thesis, we study the routing problem in DTN with limited resources. Our objective is to design and implement routing protocols that effectively handles the intermittent connection in DTNs to achieve high packet delivery ratios with lower delivery cost. Delivery cost is represented in terms of number of transmissions per delivered packet. Decreasing the delivery cost means less network overhead and less energy consumption per node. In order to achieve that objective, we first target the optimal results that could be achieved in an ideal scenario. We formulate a mathematical model for optimal routing, assuming the presence of a global observer that can collect information about all the nodes in the network. The optimal results provide us with bounds on the performance metrics, and show the room for improvement that should be worked on. However, optimal routing with a global observer is just a theoretical model, and cannot be implemented practically. In DTNs, there is a need for a distributed routing protocol which utilizes local and easily-collectable data. Therefore, We investigate the different types of heuristic (non-optimal) distributed routing protocols, showing their strengths and weaknesses. Out of the large collection of protocols, we select four protocols that represent different routing classes and are well-known and highly referred by others working in the same area. We implement the protocols using a DTN simulator, and compare their performance under different network and node conditions. We study the impact of changing the node buffer capacities, packet lifetimes, number of nodes, and traffic load on their performance metrics, which are the delivery ratio, delivery cost, and packet average delay. Based on these comparisons, we draw conclusions and guidelines to design an efficient DTN routing protocol. Given the protocol design guidelines, we develop our first DTN routing protocol, Eco-Friendly Routing for DTN (EFR-DTN), which combines the strengths of two of the previously proposed protocols to provide better delivery ratio with low network overhead (less power consumption). The protocol utilizes node encounters to estimate the route to destination, while minimizing the number of packet copies throughout the network. All current DTN routing protocols strive to estimate the route from source to destination, which requires collecting information about node encounters. In addition to the overhead it imposes on the network to collect this information, the time to collect this information could render the data worthless to propagate through the network. Our next proposal is a routing protocol, Social Groups Based Routing (SGBR), which uses social relations among network nodes to exclude the nodes that are not expected to significantly increase the probability of delivering the packet to its destination. Using social relations among nodes, detected from node encounters, every group of nodes can form a social group. Nodes belonging to the same social group are expected to meet each other frequently, and meet nodes from other groups less frequently. Spreading packet copies inside the same social group is found to be of low-added value to the carrying node in delivering a packet to its destination. Therefore, our proposed routing protocol spreads the packet copies to other social groups, which decreases the number of copies throughout the network. We compare the new protocol with the optimal results and the existing well-known routing protocols using real-life simulations. Results show that the proposed protocol achieves higher delivery ratio and less average delay compared to other protocols with significant reduction in network overhead. Finally, we discuss the willingness of DTN nodes to cooperate in routing services. From a network perspective, all nodes are required to participate in delivering packets of each other. From a node perspective, minimizing resource consumption is a critical requirement. We investigate the degree of fair cooperation where all nodes are satisfied with their participation in the network routing services. A new credit-based system is implemented to keep track of and reward node participation in packet routing. Results show that the proposed system improves the fairness among nodes and increases their satisfaction.

The objective of this project is to improve the performance of the Gnutella peer-to-peer protocol (version 0.4) by introducing a semantic-social routing model and several categories of interest. The Gnutella protocol requires peers to broadcast messages to their neighbours when they search files. The message passing generates a lot of traffic in the network, which degrades the quality of service. We propose using social networks to optimize the speed of search and to improve the quality of service in a Gnutella based peer-to-peer environment. Each peer creates and updates a friends list from its past experience, for each category of interest. Once peers generate their friends lists, they use these lists to semantically route queries in the network. Search messages in a given category are mainly sent to friends who have been useful in the past in finding files in the same category. This helps to reduce the search time and to decrease the network traffic by minimizing the number of messages circulating in the system as compared to standard Gnutella. This project will demonstrate by simulating a peer-to-peer type of environment with the JADE multi-agent system platform that by learning other peers interests, building and exploiting their social networks (friends lists) to route queries semantically, peers can get more relevant resources faster and with less traffic generated, i.e. that the performance of the Gnutella system can be improved.

The Internet is composed of thousands of diverse networks that exchange routing information using the Border Gateway Protocol (BGP). BGP is one of the most critical protocols of the Internet, since it connects these diverse networks to enable communication between remote domains. Despite its critical nature, BGP suffers from a variety of serious problems, which have triggered substantial research on developing improved versions of BGP and new routing architectures. In this dissertation, we introduce necessary tools and data-mining techniques for analyzing the present routing architecture and for evaluating new routing protocols. We focus on the problem of performing realistic BGP simulations and we first develop a BGP simulator enabling detailed and large-scale BGP simulations. Then, we introduce techniques to collect vital Internet routing data, which are essential in conducting realistic BGP simulations. Finally, we introduce models of the collected data.

Daily drayage operations involve moving loaded or empty equipment between customer locations and rail ramps. Drayage orders are generally pickup and delivery requests with time windows. The repositioning of empty equipment may also be required in order to facilitate loaded movements. The drayage orders are satisfied by a heterogeneous fleet of drivers. Driver routes must satisfy various operational constraints. In the first part of the dissertation, our goal is to minimize the cost of daily drayage operations in a region on a given day. We present an optimization methodology for finding cost-effective schedules for regional daily drayage operations. The core of the formulation is a set partitioning model whose columns represent routes. Routes are added to the formulation by column generation. We present numerical results for real-world data which demonstrate that our methodology produces low cost solutions in a reasonably short time. The second part of the dissertation addresses minimizing total empty mileage when driver capacity is not restrictive and new orders are added to the problem in an online fashion. We present a lower bound for the worst case guarantee of any deterministic online algorithm. We develop a solution methodology and provide results for the performance of different scheduling policies and parameters in a simulated environment. In the third part of the dissertation, we study a system with one rail ramp and one customer location which is served by a single driver. The problem has discrete time periods and at most one new order is released randomly each time period. The objective is to maximize the expected number of orders covered. With this simple problem, we seek to learn more about route planning for a single driver under uncertainty. We prove that carrying out an order ready to be picked up at the driver's current location is optimal for the case with one customer location. We show that the structure of the optimal policies is not simple and depends on various parameters. We devise a simple policy which yields provably near-optimal results and identify a case for which that policy is optimal.

With advancing technology, Chip Multi-processor (CMP) architectures have emerged as a viable solution for designing processors. Networks-On-Chip (NOCs) provide a scalable communication method for CMP architectures with increasing numbers of cores. Although there has been significant research on NOC designs for unicast traffic, the research on the multicast router design is still in its infant stage. Considering that one-to-many (multicast) and one-to-all (broadcast) traffic are more common in CMP applications, it is important to design a router providing efficient multicasting. In this thesis, a lookahead multicast routing algorithm with limited area overhead is proposed. This lookahead algorithm reduces network latency by removing the need for a separate routing computation (RC) stage. An efficient area optimization technique is put forward to achieve minimal area overhead for the lookahead RC stage. Also, a novel compression scheme is proposed for multicast packet headers to alleviate their big overhead in large networks. Comprehensive simulation results show that with the new route computation logic design and area overhead optimization, providing lookahead routing in the multicast router only costs less than 20 percent area overhead and this percentage keeps decreasing with larger network sizes. Compared with the basic lookahead routing design, our design can save area by over 50 percent. With header compression and lookahead multicast routing, the network performance can be improved on an average by 22 percent for a (16 x 16) network.

Track assignment is a critical step between global routing and detailed routing in modern VLSI chip designs. It greatly affects some very important design characteristics, such as routability, via usage and timing performance. Crosstalk, which is largely decided by wire adjacency, has significant impact on interconnect delay and circuit performance. Therefore, the amount of crosstalk should be restrained in order to satisfy timing constraints. In this work, a track assignment approach is proposed to control crosstalk-induced performance degradation. The problem is formulated as a Traveling Salesman Problem (TSP) and solved by a graph-based heuristic. The proposed approach is implemented and tested on benchmark circuits from the ISPD2011 contest and the experimental results are quite promising.

In this thesis, we present two e cent algorithms to compute shortest path between pair of vertices in directed and undirected double-loop networks. The algorithm for undirected double-loop networks is based on the concept "packed basis" proposed by Janez Zerrovnik and Toma z Pisanski. With O(logN) preprocessing time, both algorithms need only constant time to compute the shortest path between any pair of vertices in the network. This is an improvement of the best known algorithm, which needs O(l) time, where l is the length of the path in the directed double-loop networks. These algo- rithms are useful in message routing in the double-loop networks. Once the network has been constructed, the parameters for computing the shortest paths can be computed. At the time a message is to be delivered, the algo- rithm needs only constant time to determine which edge the message should be sent.

de Bruijn graphs are attractive due to its simplicity of routing messages between two nodes and the capability of fault tolerance. The shortest path from a node V to a node W in the directed binary de Bruijn graph can be obtained by firstly determining the longest substring, common to the right/left of V and to the left/right of W. Then L-operations/R-operations are performed to finish this routing process. However, this method does not always find the shortest path in the undirected binary de Bruijn graph. In this dissertation, we propose a shortest path routing algorithm which requires O(m2) time. We also design a fault-tolerant routing algorithm which provides the shortest path and another node-disjoint path of length at most m + log2m + 4. Our algorithm can tolerate one node failure in the m-dimensional binary de Bruijn network. In concurrent systems, a 1-fair alternator design is optimal if each processor can execute the critical step once in the fewest steps. This problem corresponds to use the minimum number of colors to color the processors in the system. Thus, the optimal design of a 1-fair alternator problem can be transformed into the coloring problem. We propose a simple and fast algorithm to solve the node coloring problem on the undirected binary de Bruijn graph. In our algorithm, the number of colors used is 3, and it is an optimal design. We also extend our method to solve the coloring problem on k-ary de Bruijn graphs. We first present a simple algorithm which needs 2k colors. By slight improvement, the number of required colors is reduced to k+1.