Packet scheduling and performance modeling of optical and wireless networks.

摘要

In this dissertation, we study packet scheduling and performance modeling in optical networks and wireless networks. We first consider Optical Packet Switching (OPS) network with Wavelength Division Multiplexing (WDM), which is a promising candidate for future high speed networks because of the very large bandwidth of optics and the high flexibility of packet switching systems. We systematically study optical WDM interconnects in OPS networks with various wavelength conversion capabilities and buffering mechanisms. Depending on the wavelength conversion capability, we formalize the problem of optimizing network performance as finding a maximum matching or an optimal matching in a bipartite graph. We start with the simplest case in which the interconnect has no buffer, and give a linear time scheduling algorithm that maximizes the throughout. We then study interconnects with output buffer, and give a linear time packet scheduling algorithm that maximizes the throughout and minimizes the total packet delay. We then study interconnects with shared buffer, and give a fast parallel packet scheduling algorithm that maximizes the throughout and minimizes the total packet delay. We also give a good analytical model for finding the performance of WDM interconnects with full range wavelength conversion and shared buffer, which can also be applied to electronic interconnects with shared buffer and can obtain much more accurate results than existing models.;Our second major topic is a two-layered heterogeneous wireless sensor network, where the network is partitioned into clusters, and a powerful cluster head controls all sensors in a cluster. Such network has better scalability, lower cost, and longer network life than other types of networks. We mainly focus on the energy efficient design within a cluster to prolong network lifetime. To reduce the energy consumption, we use polling to collect data from sensors instead of letting sensors send data randomly. We show that the problem of finding a minimum time contention-free polling schedule is NP-hard, and give a fast on-line algorithm to solve it approximately. We also conduct simulations on the NS-2 simulator and show that our polling scheme achieves 100% throughput even when the sensor's active time is not long.