"Opportunistic routing (OR) takes advantages of the spatial diversity and broadcast nature of wireless networks to combat the time-varying links by involving multiple neighboring nodes (forwarding candidates) for each packet relay. This dissertation studies the properties, energy efficiency, capacity, throughput, protocol design and security issues about OR in multihop wireless networks. Firstly, we study geographic opportunistic routing (GOR), a variant of OR which makes use of nodes' location information. We identify and prove three important properties of GOR. The first one is on prioritizing the forwarding candidates according to their geographic advancements to the destination. The second one is on choosing the forwarding candidates based on their advancements and link qualities in order to maximize the expected packet advancement (EPA) with different number of forwarding candidates. The third one is on the concavity of the maximum EPA in respect to the number of forwarding candidates. We further propose a local metric, EPA per unit energy consumption, to tradeoff the routing performance and energy efficiency for GOR. Leveraging the proved properties of GOR, we propose two efficient algorithms to select and prioritize forwarding candidates to maximize the local metric. Secondly, capacity is a fundamental issue in multihop wireless networks. We propose a framework to compute the end-to-end throughput bound or capacity of OR in single/multirate systems given OR strategies (candidate selection and prioritization). Taking into account wireless interference and unique properties of OR, we propose a new method of constructing transmission conflict graphs, and we introduce the concept of concurrent transmission sets to allow the proper formulation of the maximum end-to-end throughput problem as a maximum-flow linear programming problem subject to the transmission conflict constraints. We also propose two OR metrics: expected medium time (EMT) and expected advancement rate (EAR), and the corresponding distributed and local rate and candidate set selection schemes, the Least Medium Time OR (LMTOR) and the Multirate Geographic OR (MGOR). We further extend our framework to compute the capacity of OR in multi-radio multi-channel systems with dynamic OR strategies. We study the necessary and sufficient conditions for the schedulability of a traffic demand vector associated with a transmitter to its forwarding candidates in a concurrent transmission set. We further propose an LP approach and a heuristic algorithm to obtain an opportunistic forwarding strategy scheduling that satisfies a traffic demand vector. Our methodology can be used to calculate the end-to-end throughput bound of OR in multi-radio/channel/rate multihop wireless networks, as well as to study the OR behaviors (such as candidate selection and prioritization) under different network configurations. Thirdly, protocol design of OR in a contention-based medium access environment is an important and challenging issue. In order to avoid duplication, we should ensure only the "best" receiver of each packet to forward it in an efficient way. We investigate the existing candidate coordination schemes and propose a "fast slotted acknowledgment" (FSA) to further improve the performance of OR by using a single ACK to coordinate the forwarding candidates with the help of the channel sensing technique. Furthermore, we study the throughput of GOR in multi-rate and single-rate systems. We introduce a framework to analyze the one-hop throughput of GOR, and provide a deeper insight on the trade-off between the benefit (packet advancement, bandwidth, and transmission reliability) and cost (medium time delay) associated with the node collaboration. We propose a local metric named expected one-hop throughput (EOT) to balance the benefit and cost. Finally, packet reception ratio (PRR) has been widely used as an indicator of the link quality in multihop wireless networks. Many routing protocols including OR in wireless networks depend on the PRR information to make routing decision. Providing accurate link quality measurement (LQM) is essential to ensure the right operation of these routing protocols. However, the existing LQM mechanisms are subject to malicious attacks, thus can not guarantee to provide correct link quality information. We analyze the security vulnerabilities in the existing link quality measurement (LQM) mechanisms and propose an efficient broadcast-based secure LQM (SLQM) mechanism, which prevents the malicious attackers from reporting a higher PRR than the actual one. We analyze the security strength and the cost of the proposed mechanism. "

Internet applications have varied Quality of Service (QoS) Requirements. Traditional applications such as FTP and email are throughput sensitive since their quality is primarily affected by the throughput they receive. There are delay sensitive applications such as streaming audio/video and IP telephony, whose quality is more affected by the delay. The current Internet however does not provide QoS support to the applications and treats the packets from all applications as primarily throughput sensitive. Delay sensitive applications can however sacrifice throughput for delay to obtain better quality. We present a Traffic Sensitive QoS controller (TSQ) which can be used in conjunction with many existing Active Queue Management (AQM) techniques at the router. The applications inform the TSQ enabled router about their delay sensitivity by embedding a delay hint in the packet header. The delay hint is a measure of an application's delay sensitivity. The TSQ router on receiving packets provides a lower queueing delay to packets from delay sensitive applications based on the delay hint. It also increases the drop probability of such applications thus decreasing their throughput and preventing any unfair advantage over throughput sensitive applications. We have also presented the quality metrics of some typical Internet applications in terms of delay and throughput. The applications are free to choose their delay hints based on the quality they receive. We evaluated TSQ in conjunction with the PI-controller AQM over the Network Simulator (NS-2). We have presented our results showing the improvement in QoS of applications due to the presence of TSQ.

Current congestion control approaches that attempt to provide fair bandwidth allocation among competing flows primarily consider only data rate when making decisions on which packets to drop. However, responsive flows with high round trip times (RTTs) can still receive significantly less bandwidth than responsive flows with low round trip times. This paper proposes a congestion control scheme called WHITE that addresses router unfairness in handling flows with significantly different RTTs. Using a best-case estimate of a flow's RTT provided in each packet by the flow source or by an edge router, WHITE computes a stabilized average RTT. The average RTT is then compared with the RTT of each incoming packet, dynamically adjusting the drop probability so as to protect the bandwidth of flows with high RTTs while curtailing the bandwidth of flows with low RTTs. We present simulation results and analysis that demonstrate that WHITE provides better fairness than other rate-based congestion control strategies over a wide-range of traffic conditions. The improved fairness of WHITE comes close to the fairness of Fair Queuing without requiring per flow state information at the router.

"This thesis explores techniques for improving the Quality of Service (QoS) driven routing of IP traffic in a Network Centric Military Communications System within an HC3 (High Capacity Communications Capability) tiered topology. In this specialized network various routing algorithms, including traditional, QoS-constrained search-based, and heuristic approaches, were evaluated. An automatic system for the probabilistic generation of appropriate networks and traffic was created for Monte Carlo simulation of the systems and testing of the various routing algorithms. A new algorithm we propose, based upon a hiercharical decomposition of routes about the minimum distance routes, is described and tested. These results provide both insight into this problem and demonstrate the possibility of highly optimized solutions without exhaustive search."

by Xu Haoyu. / Thesis submitted in: July 2003. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 89-95). / Abstracts in English and Chinese. / Acknowledgement --- p.i / Abstract --- p.ii / 摘要 --- p.iii / Contents --- p.iv / List of Abbreviations --- p.vii / List of Tables --- p.viii / List of Figures --- p.ix / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.2 / Chapter 1.1.1 --- Routing --- p.2 / Chapter 1.1.2 --- Ant Colony Optimization --- p.6 / Chapter 1.2 --- Research Statement --- p.8 / Chapter 1.3 --- Main Contributions --- p.10 / Chapter 1.4 --- Thesis Organization --- p.11 / Chapter Chapter 2 --- Ant Colony Optimization Routing --- p.12 / Chapter 2.1 --- ACO Routing Algorithms --- p.13 / Chapter 2.1.1 --- ACO Routing Algorithms in Circuit-Switched Networks --- p.13 / Chapter 2.1.2 --- ACO Routing Approaches in Packet-Switched Networks --- p.16 / Chapter 2.2 --- ACO Routing and Traditional Routing Algorithms --- p.23 / Chapter 2.3 --- ACO Routing and Optimal Routing Algorithms --- p.26 / Chapter Chapter 3 --- Reactive Ant Colony Optimization --- p.31 / Chapter 3.1 --- Problem Model --- p.31 / Chapter 3.2 --- RACO Routing Approach --- p.35 / Chapter 3.2.1. --- Node and Probabilistic Routing Table --- p.36 / Chapter 3.2.2. --- Ants --- p.38 / Chapter 3.2.3 --- Detailed Description of RACO routing approach --- p.43 / Chapter Chapter 4 --- Simulation Results --- p.45 / Chapter 4.1 --- Experiment Design --- p.45 / Chapter 4.1.1 --- Topology --- p.46 / Chapter 4.1.2 --- Network Layers --- p.48 / Chapter 4.2 --- Results --- p.50 / Chapter 4.2.1 --- NSFNET --- p.50 / Chapter 4.2.2 --- ARPANET --- p.52 / Chapter 4.3 --- Discussion --- p.53 / Chapter Chapter 5 --- Convergence Analysis --- p.58 / Chapter 5.1. --- Related Work --- p.59 / Chapter 5.2 --- "Two-Node, Two-Path Model" --- p.61 / Chapter 5.3 --- The Recursive Pheromone Values --- p.64 / Chapter 5.4 --- Pheromone Convergence --- p.70 / Chapter 5.5 --- General Models --- p.81 / Chapter 5.5.1 --- "Two - Node, N - Path Model" --- p.81 / Chapter 5.5.2 --- "M- Node, N(i.j) - Path Model" --- p.83 / Chapter 5.6. --- Conclusion and Discussion --- p.84 / Chapter Chapter 6 --- Conclusion and Future Work --- p.86 / Chapter 6.1 --- Conclusion --- p.86 / Chapter 6.2 --- Future Work --- p.87 / Reference --- p.89 / Appendices --- p.96 / "Appendix 1 The Detailed Form of P = f1（a,b) and Q = f2（a,b)" --- p.96 / "Appendix 2 To Validate Whether f1（a,b) in the Domain of (0,1)" --- p.102

Recently, the Birkhoff-von Neumann (BvN) switch has become a typical model for providing QoS in input-queued switch. The major idea is to consider a set of predetermined permutation matrices as independent flows, and the scheduling problem in the input-queued switch can be simply handled by single-server scheduling algorithms, such as weighted fair queueing (WFQ). However, a number of problems are observed. Firstly, although WFQ is a fair algorithm, it has a poor delay performance that depends on the port counts. Secondly, the BvN switch does not perform well under certain traffic requirement, thus unable to provide tight performance guarantees. In this thesis, a set of admission control strategies and scheduling algorithms are therefore developed to improve the QoS performance. / The input-queued switch architecture is widely used in Internet routers, due to its ability to run at very high speeds. A central problem in designing an input-queued switch is choosing the scheduling algorithm, i.e. deciding which packets to transfer from input ports to output ports in a given timeslot. Recent research in packet switch scheduling algorithms has moved beyond throughput maximization to quality of service (QoS) control. / Choy Man Ting. / "September 2006." / Adviser: Tony T. Lee. / Source: Dissertation Abstracts International, Volume: 68-03, Section: B, page: 1815. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (p. 89-94). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

(I) Architectural revisions: Probably due to historical reasons, programmable switches on conventional FPGA architectures are divided into two kinds of substructures: Connection boxes (C-boxes) and Switch boxes (S-boxes), where C-boxes are used to connect logic/pad pins with their crossing wire segments, and S-boxes are used to connect wire segments of surrounding routing channels. In this work, we will challenge if this divided C- and S-boxes structure is really necessary and will explore a new experimental architecture which adopts only one kind of switching components - Connection-Switch boxes (CS-boxes). Extensive experiments are conducted on MCNC benchmark circuits to justify its architectural performance impacts. The results show that this CS-box based FPGA outperforms the conventional FPGA in terms of channel width, circuit delay, and segment usage. Besides an over 20% drastic dropping in the total number of manufactured switches needed, circuit delay performance is improved by 10% under the usage of the same pin assignments and router. / (II) New EDA technique/flow: By applying circuit rewirings, logic perturbations can be carried out by shifting logic resources from perhaps costly Look-Up-Table (LUT) external to cost-free LUT internal areas, or from critical to non-critical paths. This work presents a simple, while effective and low-overhead postlayout logic perturbation scheme for improving LUT-based FPGA routings without altering placements. A rewiring-based logic perturbation technique is used to improve upon a timing-driven FPGA P&R tool - TVPR. Compared with the already high-quality pure TVPR results, our approach reduces critical path delay by up to 31.74% (avg. 11%) without disturbing the placement or sacrificing chip areas, where only 4% of the nets are perturbed in our scheme. The complexity of our algorithm is linear in the total number of nets of the circuit. The experimental results show that the CPU time used by the rewiring engine is only 5% of the total time consumed by the placement and routing of TVPR. / Based on these studies, we believe the prospect for FPGA performance improvement is still quite profound in both architectural and EDA aspects. On the EDA technique, we have also performed logic perturbations to improve both the technology mapping and routing to investigate the effectiveness of the logic perturbation if applied in a larger context. The results show that a best technology mapping is not always leading to a best final routing, which seems to suggest that an ideal FPGA EDA flow should consider more on trade-offs between different stages. To the best of our knowledge, this is the first work exploring the power of logic perturbations applied for multiple physical stages for LUT-based FPGAs. The encouraging hardware improvement shown in our proposed CS-box based FPGAs seems to suggest a new design direction for FPGA routing architectures. / With the advent of deep submicron technologies, the extreme high design and mask costs incurred for ASICs have made FPGAs an increasingly popular hardware implementation option. However, it has been shown that the programmable routing structure underlined contributes over 60% of the signal delay and as high as 90% of the total chip area. As a result, current FPGAs still cannot meet performance requirements of many high-end applications. To attack this issue, we propose new solutions along the two major tracks: (I) architectural revisions (hardware) and (II) new EDA technique/flow (software). / Zhou Lin. / "October 2007." / Adviser: Yu-Liang Wu. / Source: Dissertation Abstracts International, Volume: 69-08, Section: B, page: 4953. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 101-108). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Ma Ke. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 64-68). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- Motivation --- p.2 / Chapter 1.3 --- Contribution --- p.3 / Chapter 1.4 --- Organization --- p.4 / Chapter 2 --- Literature Review --- p.5 / Chapter 2.1 --- Overview --- p.5 / Chapter 2.2 --- Multi-Path Routing --- p.6 / Chapter 2.2.1 --- OSPF-ECMP --- p.7 / Chapter 2.2.2 --- LFI --- p.7 / Chapter 2.2.3 --- QSMP and QDMP --- p.9 / Chapter 2.2.4 --- WDP --- p.10 / Chapter 2.2.5 --- DMPR --- p.11 / Chapter 2.2.6 --- Cidon's Analysis --- p.13 / Chapter 3 --- LSLF and SLSLF Conditions --- p.15 / Chapter 3.1 --- Problem Formulation --- p.15 / Chapter 3.2 --- LFI Conditions --- p.16 / Chapter 3.3 --- LSLF Conditions --- p.17 / Chapter 3.4 --- SLSLF Conditions --- p.20 / Chapter 4 --- Performance of LSLF and SLSLF --- p.24 / Chapter 4.1 --- Overview --- p.24 / Chapter 4.2 --- Numerical Results --- p.26 / Chapter 5 --- Analysis of Multi-path Routing --- p.42 / Chapter 5.1 --- Assumptions --- p.43 / Chapter 5.2 --- M/M/C/C Queueing System --- p.44 / Chapter 5.3 --- Performance Analysis --- p.48 / Chapter 5.3.1 --- "Case 1 Only QoS flows between (s, d) exist" --- p.48 / Chapter 5.3.2 --- Case 2 QoS flows between other SD pairs also exist --- p.50 / Chapter 5.3.3 --- Case 3 A QoS flow can try m times before it is dropped --- p.53 / Chapter 5.4 --- Numerical Results --- p.56 / Chapter 6 --- Conclusion --- p.62

Li Cheng. / Thesis submitted in: November 2002. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 57-61). / Abstracts in English and Chinese. / Chapter CHAPTER 1 --- INTRODUCTION --- p.1 / Chapter 1.1 --- The Evolution of Ring Network Technologies --- p.1 / Chapter 1.1.1 --- Token Ring Technology --- p.1 / Chapter 1.1.2 --- Resilient Packet Ring Technology --- p.4 / Chapter 1.2 --- Optimal Routing --- p.7 / Chapter 1.3 --- Fairness --- p.8 / Chapter 1.4 --- Outline of Thesis --- p.10 / Chapter CHAPTER 2 --- OPTIMAL ROUTING --- p.11 / Chapter 2.1 --- Throughput Analysis --- p.11 / Chapter 2.2 --- Numerical Results --- p.13 / Chapter CHAPTER 3 --- OPTIMAL FAIR ROUTING --- p.19 / Chapter 3.1 --- Overview --- p.19 / Chapter 3.2 --- Max-min Fair Allocation --- p.19 / Chapter 3.3 --- Proportionally Fair Allocation --- p.32 / Chapter 3.4 --- Numerical Results --- p.33 / Chapter CHAPTER 4 --- TRADEOFF ANALYSIS --- p.40 / Chapter 4.1 --- Tradeoff between Throughput and Max-min Fairness --- p.40 / Chapter 4.2 --- Numerical Results --- p.42 / Chapter 4.3 --- Tradeoff between Throughput and Utility --- p.47 / Chapter 4.4 --- Numerical Results --- p.48 / Chapter CHAPTER 5 --- CONCLUSION --- p.54 / Chapter 5.1 --- Summary --- p.54 / Chapter 5.2 --- Discussion and Future Work --- p.55 / BIBLIOGRAPHY --- p.57

In the past few years Wireless Mesh Networks (WMNs) have developed as a promising technology to provide flexible and low-cost broadband network services. The Expected Transmission Count (ETX) routing metric has been put forward recently as an advanced routing metric to provide high QoS for static WMNs. Most previous research in this area suggests that ETX outperforms other routing metrics in throughput and efficiency. However, it has been determined that ETX is not immune to load sensitivity and route oscillations in a single radio environment. Route oscillations refer to the situation where packet transmission switches between two or more routes due to congestion. This has the effect of degrading performance of the network, as the routing protocol may select a non optimal path. In this thesis we avoided the route oscillation problem by forcing data transmission on fixed routes. This can be implemented in the AODV (Ad hoc On-demand Distance Vector) protocol by disabling both error messages and periodic updating messages (the HELLO scheme). However, a critical factor for our approach is that ETX must determine a high quality initial route in AODV. This thesis investigates whether the ETX metric improves initial route selection in AODV compared to the HOPS metric in two representative client-server applications: the Traffic Control Network (TCN) and the Video Stream (VS) network. We evaluate the ETX and HOPS metrics in a range of scenarios which possess different link qualities and different traffic loads. We find the ETX metric greatly improves initial route selection in AODV compared to the HOPS in the network in which only single flow exists. For networks in which there are multiple simultaneous flows, ETX behaves similar to HOPS in initial route selection. Based on these results, we find the solution of route stabilization to route oscillations in the context of ETX is only useful in the single flow case. To address this problem, we propose a modified solution of repeatedly broadcasting RREQ (Route Request) packets. Simulation results show that our modified solution allows ETX to be useful in the initial route selection in both single flow and multiple simultaneous flows cases.