Due to the existence of multiple stakeholders with conflicting goals and policies, alterations to the existing Internet architecture are now limited to simple incremental updates; deployment of any new, radically different technology is next to impossible. To fend off this ossification, network virtualization has been propounded as a diversifying attribute of the future inter-networking paradigm. In this talk, we provide an overview of the network virtualization environment (NVE) and address two basic problems in this emerging field of networking research. The identity management problem is primarily concerned with ensuring interoperability across heterogeneous identifier spaces for locating and identifying end hosts in different virtual networks. We describe the architectural and the functional components of a novel identity management framework (iMark) that enables end-to-end connectivity across heterogeneous virtual networks in the NVE without revoking their autonomy. The virtual network embedding problem deals with the mapping of virtual nodes and links onto physical network resources. We argue that the separation of the node mapping and the link mapping phases in the existing algorithms considerably reduces the solution space and degrades embedding quality. We propose coordinated node and link mapping to devise two algorithms (D-ViNE and R-ViNE) for the online version of the problem under realistic assumptions and compare their performance with the existing heuristics.

The high deployment and maintenance costs of last mile wireline networks (i.e., DSL and cable networks) have urged service providers to search for new cost-effective solutions to provide broadband connectivity. Broadband wireless access (BWA) networks, which offer a wide coverage area and high transmission rates in addition to their fast and low-cost deployment, have emerged as an alternative to last mile wireline networks. Therefore, BWA networks are expected to be deployed in areas with different terrain profiles (e.g., urban, suburban, rural) where wireless communication faces different channel impairments. This fact necessitates the adoption of various transmission technologies that combat the channel impairments of each profile. Implementation scenarios of BWA networks considered in this thesis are multicarrier-based direct transmission and single carrier-based cooperative transmission scenarios. The performance of these transmission technologies highly depends on how resources are allocated. In this thesis, we focus on the development of practical resource allocation schemes for the mentioned BWA networks implementation scenarios. In order to develop practical schemes, the imperfection of channel state information (CSI) and computational power limitations are among considered practical implementation issues. The design of efficient resource allocation schemes at the MAC layer heavily relies on the CSI reported from the PHY layer as a measure of the wireless channel condition. The channel estimation error and feedback delay renders the reported CSI erroneous. The inaccuracy in CSI propagates to higher layers, resulting in performance degradation. Although this effect is intuitive, a quantitative measure of this degradation is necessary for the design of practical resource allocation schemes. An approach to the evaluation of the ergodic mutual information that reflects this degradation is developed for single carrier, multicarrier, direct, and cooperative scenarios with inaccurate CSI. Given the CSI estimates and estimation error statistics, the presented evaluation of ergodic mutual information can be used in resource allocation and in assessing the severity of estimation error on performance degradation. A point-to-multipoint (PMP) network that employs orthogonal frequency division multiple access (OFDMA) is considered as one of the most common implementation scenarios of BWA networks. Replacing wireline networks requires not only providing the last mile connectivity to subscribers but also supporting their diverse services with stringent quality of service (QoS) requirements. Therefore, the resource allocation problem (i.e., subcarriers, rate and power allocation) is modeled as a network utility maximization (NUM) one that captures the characteristics of this implementation scenario. A dual decomposition-based resource allocation scheme that takes into consideration the diversity of service requirements and inaccuracy of the CSI estimation is developed. Numerical evaluations and simulations are conducted to validate our theoretical claims that the scheme maximizes resource utilization, coordinates with the call admission controller to guarantee QoS, and accounts for CSI inaccuracy. Cooperation has recently received great attention from the research community and industry because of its low cost and fast deployment in addition to the performance improvement it brings to BWA networks. In cooperative scenarios, subscribers cooperate to relay each other's signals. For this implementation scenario of BWA networks, a robust and constrained Kalman filter-based power allocation scheme is proposed to minimize power consumption and guarantee bit error probability (BEP) requirements. The proposed scheme is robust to CSI inaccuracy, responsive to changes in BEP requirements, and optimal in allocating resources. In summary, research results presented in this thesis contribute to the development of practical resource allocation schemes for BWA networks.

Wireless Mesh Networks (WMNs) built with commodity 802.11 radios are a cost-effective means of providing last mile broadband Internet access. Their multihop architecture allows for rapid deployment and organic growth of these networks. 802.11 radios are an important building block in WMNs. These low cost radios are readily available, and can be used globally in license-exempt frequency bands. However, the 802.11 Distributed Coordination Function (DCF) medium access mechanism does not scale well in large multihop networks. This produces suboptimal behavior in many transport protocols, including TCP, the dominant transport protocol in the Internet. In particular, cross-layer interaction between DCF and TCP results in flow level unfairness, including starvation, with backlogged traffic sources. Solutions found in the literature propose distributed source rate control algorithms to alleviate this problem. However, this requires MAC-layer or transport-layer changes on all mesh routers. This is often infeasible in practical deployments. In wireline networks, router-assisted rate control techniques have been proposed for use alongside end-to-end mechanisms. We evaluate the feasibility of establishing similar centralized control via gateway mesh routers in WMNs. We find that commonly used router-assisted flow control schemes designed for wired networks fail in WMNs. This is because they assume that: (1) links can be scheduled independently, and (2) router queue buildups are sufficient for detecting congestion. These abstractions do not hold in a wireless network, rendering wired scheduling algorithms such as Fair Queueing (and its variants) and Active Queue Management (AQM) techniques ineffective as a gateway-enforceable solution in a WMN. We show that only non-work-conserving rate-based scheduling can effectively enforce rate allocation via a single centralized traffic-aggregation point. In this context we propose, design, and evaluate a framework of centralized, measurement-based, feedback-driven mechanisms that can enforce a rate allocation policy objective for adaptive traffic streams in a WMN. In this dissertation we focus on fair rate allocation requirements. Our approach does not require any changes to individual mesh routers. Further, it uses existing data traffic as capacity probes, thus incurring a zero control traffic overhead. We propose two mechanisms based on this approach: aggregate rate control (ARC) and per-flow rate control (PFRC). ARC limits the aggregate capacity of a network to the sum of fair rates for a given set of flows. We show that the resulting rate allocation achieved by DCF is approximately max-min fair. PFRC allows us to exercise finer-grained control over the rate allocation process. We show how it can be used to achieve weighted flow rate fairness. We evaluate the performance of these mechanisms using simulations as well as implementation on a multihop wireless testbed. Our comparative analysis show that our mechanisms improve fairness indices by a factor of 2 to 3 when compared with networks without any rate limiting, and are approximately equivalent to results achieved with distributed source rate limiting mechanisms that require software modifications on all mesh routers.

Ad hoc networks and bluetooth systems operating over the unlicensed ISM band are in-stances of decentralized wireless networks. By definition, a decentralized network is com-posed of separate transmitter-receiver pairs where there is no central controller to assign the resources to the users. As such, resource allocation must be performed locally at each node. Users are anonymous to each other, i.e., they are not aware of each other's code-books. This implies that multiuser detection is not possible and users treat each other as noise. Multiuser interference is known to be the main factor that limits the achievable rates in such networks particularly in the high Signal-to-Noise Ratio (SNR) regime. Therefore, all users must follow a distributed signaling scheme such that the destructive effect of interference on each user is minimized, while the resources are fairly shared. In chapter 2 we consider a decentralized wireless communication network with a fixed number of frequency sub-bands to be shared among several transmitter-receiver pairs. It is assumed that the number of active users is a realization of a random variable with a given probability mass function. Moreover, users are unaware of each other's codebooks and hence, no multiuser detection is possible. We propose a randomized Frequency Hopping (FH) scheme in which each transmitter randomly hops over a subset of sub-bands from transmission slot to transmission slot. Assuming all users transmit Gaussian signals, the distribution of the noise plus interference is mixed Gaussian, which makes calculation of the mutual information between the transmitted and received signals of each user intractable. We derive lower and upper bounds on the mutual information of each user and demonstrate that, for large SNR values, the two bounds coincide. This observation enables us to compute the sum multiplexing gain of the system and obtain the optimum hopping strategy for maximizing this quantity. We compare the performance of the FH system with that of the Frequency Division (FD) system in terms of the following performance measures: average sum multiplexing gain and average minimum multiplexing gain per user. We show that (depending on the probability mass function of the number of active users) the FH system can offer a significant improvement in terms of the aforementioned measures. In the sequel, we consider a scenario where the transmitters are unaware of the number of active users in the network as well as the channel gains. Developing a new upper bound on the differential entropy of a mixed Gaussian random vector and using entropy power inequality, we obtain lower bounds on the maximum transmission rate per user to ensure a specified outage probability at a given SNR level. We demonstrate that the so-called outage capacity can be considerably higher in the FH scheme than in the FD scenario for reasonable distributions on the number of active users. This guarantees a higher spectral efficiency in FH compared to FD. Chapter 3 addresses spectral efficiency in decentralized wireless networks of separate transmitter-receiver pairs by generalizing the ideas developed in chapter 2. Motivated by random spreading in Code Division Multiple Access (CDMA), a signaling scheme is introduced where each user's code-book consists of two groups of codewords, referred to as signal codewords and signature codewords. Each signal codeword is a sequence of independent Gaussian random variables and each signature codeword is a sequence of independent random vectors constructed over a globally known alphabet. Using a conditional entropy power inequality and a key upper bound on the differential entropy of a mixed Gaussian random vector, we develop an inner bound on the capacity region of the decentralized network. To guarantee consistency and fairness, each user designs its signature codewords based on maximizing the average (with respect to a globally known distribution on the channel gains) of the achievable rate per user. It is demonstrated how the Sum Multiplexing Gain (SMG) in the network (regardless of the number of users) can be made arbitrarily close to the SMG of a centralized network with an orthogonal scheme such as Time Division (TD). An interesting observation is that in general the elements of the vectors in a signature codeword must not be equiprobable over the underlying alphabet in contrast to the use of binary Pseudo-random Noise (PN) signatures in randomly spread CDMA where the chip elements are +1 or -1 with equal probability. The main reason for this phenomenon is the interplay between two factors appearing in the expression of the achievable rate, i.e., multiplexing gain and the so-called interference entropy factor. In the sequel, invoking an information theoretic extremal inequality, we present an optimality result by showing that in randomized frequency hopping which is the main idea in the prevailing bluetooth devices in decentralized networks, transmission of independent signals in consecutive transmission slots is in general suboptimal regardless of the distribution of the signals. Finally, chapter 4 addresses a decentralized Gaussian interference channel consisting of two block-asynchronous transmitter-receiver pairs. We consider a scenario where the rate of data arrival at the encoders is considerably low and codewords of each user are transmitted at random instants depending on the availability of enough data for transmission. This makes the transmitted signals by each user look like scattered bursts along the time axis. Users are block-asynchronous meaning there exists a delay between their transmitted signal bursts. The proposed model for asynchrony assumes the starting point of an interference burst is uniformly distributed along the transmitted codeword of any user. There is also the possibility that each user does not experience interference on a transmitted codeword at all. Due to the randomness of delay, the channels are non-ergodic in the sense that the transmitters are unaware of the location of interference bursts along their transmitted codewords. In the proposed scheme, upon availability of enough data in its queue, each user follows a locally Randomized Masking (RM) strategy where the transmitter quits transmitting the Gaussian symbols in its codeword independently from symbol interval to symbol interval. An upper bound on the probability of outage per user is developed using entropy power inequality and a key upper bound on the differential entropy of a mixed Gaussian random variable. It is shown that by adopting the RM scheme, the probability of outage is considerably less than the case where both users transmit the Gaussian symbols in their codewords in consecutive symbol intervals, referred to as Continuous Transmission (CT).

No description available.

In this thesis, we study a series of closely related multi-stage stochastic programming models in production planning, from both a modeling and an algorithmic point of view. We first consider a very simple multi-stage stochastic lot-sizing problem, involving a single item with no fixed charge and capacity constraint. Although a multi-stage stochastic integer program, this problem can be shown to have a totally unimodular constraint matrix. We develop primal and dual algorithms by exploiting the problem structure. Both algorithms are strongly polynomial, and therefore much more efficient than the Simplex method. Next, motivated by applications in semiconductor tool planning, we develop a general capacity planning problem under uncertainty. Using a scenario tree to model the evolution of the uncertainties, we present a multi-stage stochastic integer programming formulation for the problem. In contrast to earlier two-stage approaches, the multi-stage model allows for revision of the capacity expansion plan as more information regarding the uncertainties is revealed. We provide analytical bounds for the value of multi-stage stochastic programming over the two-stage approach. By exploiting the special simple stochastic lot-sizing substructure inherent in the problem, we design an efficient approximation scheme and show that the proposed scheme is asymptotically optimal. We conduct a computational study with respect to a semiconductor-tool-planning problem. Numerical results indicate that even an approximate solution to the multi-stage model is far superior to any optimal solution to the two-stage model. These results show that the value of multi-stage stochastic programming for this class of problem is extremely high. Next, we extend the simple stochastic lot-sizing model to an infinite horizon problem to study the planning horizon of this problem. We show that an optimal solution of the infinite horizon problem can be approximated by optimal solutions of a series of finite horizon problems, which implies the existence of a planning horizon. We also provide a useful upper bound for the planning horizon.

The current dominate layered networking architecture, in which each layer is designed and operated independently, results in inefficient and inflexible resource use in wireless networks due to the nature of the wireless medium, such as time-varying channel fading, mutual interference, and topology variations. In this thesis, we focus on resource allocation and scheduling in wireless orthogonal frequency division multiplexing (OFDM) networks based on joint physical and medium access control (MAC) layer optimization. To achieve orders of magnitude gains in system performance, we use two major mechanisms in resource management: exploiting the time variance and frequency selectivity of wireless channels through adaptive modulation, coding, as well as packet scheduling and regulating resource allocation through network economics. With the help of utility functions that capture the satisfaction level of users for a given resource assignment, we establish a utility optimization framework for resource allocation in OFDM networks, in which the network utility at the level of applications is maximized subject to the current channel conditions and the modulation and coding techniques employed in the network. Although the nonlinear and combinatorial nature of the cross-layer optimization challenges algorithm development, we propose novel efficient dynamic subcarrier assignment (DSA) and adaptive power allocation (APA) algorithms that are proven to achieve the optimal or near-optimal performance with very low complexity. Based on a holistic design principle, we design max-delay-utility (MDU) scheduling, which senses both channel and queue information. The MDU scheduling can simultaneously improve the spectral efficiency and provide right incentives to ensure that all applications can receive their different required quality of service (QoS). To facilitate the cross-layer design, we also deeply investigate the mechanisms of channel-aware scheduling, such as efficiency, fairness, and stability. First, using extreme value theory, we analyze the impact of multiuser diversity on throughput and packet delay. Second, we reveal a generic relationship between a specific convex utility function and a type of fairness. Third, with rigorous proofs, we provide a method to design cross-layer scheduling algorithms that allow the queueing stability region at the network layer to approach the ergodic capacity region at the physical layer.

Aerospace systems are complex systems with interacting disciplines and technologies. As a result, the Decision Makers (DMs) dealing with such problems are involved in balancing the multiple, potentially conflicting attributes/criteria, transforming a large amount of customer supplied guidelines into a solidly defined set of requirement definitions. A variety of existing decision making methods are available to deal with this type of decision problems. The selection of a most appropriate decision making method is of particular importance since inappropriate decision methods are likely causes of misleading engineering design decisions. The research presented in this dissertation proposes a knowledge-based Multi-criteria Interactive Decision-making Advisor and Synthesis process (MIDAS), which can facilitate the selection of the most appropriate decision making method and which provides insight to the user for fulfilling different preferences. Once the most appropriate method is selected for the given problem, the advisor is also able to aid the DM to reach the final decision by following the rigorous problem solving procedure of the selected method. The MIDAS can also provide guidance as to the requirements needed to be fulfilled by a potentially new method for cases where no suitable method is found. In many other domains, such as complex system operation, decisions are often made in an environment with continuously changing situations. In addition, the decisions are usually completed based on uncertain or incomplete information due to the data availability and the environmental variation. This fact exacerbates the complexity of the decision making process because it results in the difficulties in perfectly and deterministically reasoning about the effects of the decisions and thus make it hard in determining the further decisions. In order to make proper decision and increase the system’s effectiveness, an advanced decision strategy is needed to capture the system’s dynamic characteristics and environmental uncertainty. An autonomous decision making advisor is developed to perform the real-time decision making under uncertainty. The development of the advisor system aims to solve a resource allocation problem to redistribute the limited resources to different agents under various scenarios and try to maximize the total rewards obtained from the resource allocation actions.

Multimedia services over wireless networks are getting popular. With multicast many mobile stations can join the same video multicast group and share the same radio resource to increase frequency utilization efficiently. However users may locate at different positions so as to suffer different path loss, interference and receive different signal to interference and noise ratio (SINR). Users at the cell-edge receiving lower SINR may degrade the multicast efficiency. In this thesis we propose four schemes considering fractional frequency reuse (FFR) over relay networks to reuse frequency in multi-cells. With fractional frequency reuse, users close to the base station (BS) have more resources to improve the total frequency utilization. A resource allocation scheme is also proposed to efficiently allocate wireless resources. Compared to the conventional relay scheme, the proposed schemes can provide more than 10% video layers for all users and give better video quality for users near BS.

In multi-cell downlink OFDMA radio network system, users in one cell would suffer from the inter-cell interference caused by frequency reuse, namely co-channel interference. For a practical system, the inter-cell interference seriously decreases the quality of communication, especially for cell-edge users. Therefore, some interference management techniques, such as resources allocation, beamforming¡Ketc., will become an important issue in this system. Therefore, how to allocate resources to enhance cell-edge user performance and total system throughput is the major problem of our research. In this thesis, for management the inter-cell interference in multi-cell downlink OFDMA radio network system, a power allocation method based on the Cross-Entropy algorithm is proposed to find the sub-optimal solution and corresponding subcarriers allocation. In the system, it is considered that a sum-rate maximization problem while satisfying the target rate of both cell-edge users and cell-interior users. The simulation results show that the proposed method can effectively reduce interference between cells, and increases the transmission performance of cell-edge users and overall system throughput.