46660413
Optimal Scheduling Algorithms in WDM Optical Interconnects with Limited Range Wavelength Conversion Capability
In this paper we study optimal scheduling algorithms to resolve output contentions in time slotted WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion with arbitrary conversion capability, as it is easier to implement and more cost effective than full range wavelength conversion, and also includes full range wavelength conversion as a special case. We consider the conversion scheme in which each wavelength can be converted to multiple wavelengths belongs to an interval and the intervals for different wavelengths are “ordered”. To be specific, the conversion range of λ i can be written as [begin(i), end(i)], where begin(i) and end(i) are positive integers and if i < j then begin(i) ≤ begin(j) and end(i) ≤ end(j). We will present linear time optimal scheduling algorithms for both buffered and unbuffered WDM switches. We will also give performance studies of these switches when scheduled by these algorithms.
17015903
Optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability
All optical networking is a promising candidate for supporting high-speed communications because of the huge bandwidth of optics. In this paper, we study optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability. We formalize the problem of maximizing network throughput and minimizing total delay as a problem of finding an optimal matching in a weighted bipartite graph. We then give a simple algorithm, called the Scan and Swap Algorithm, that finds the optimal matching in O(kB) time, where k is the number of wavelengths per fiber and B is the buffer length, as compared to directly adopting other existing algorithms that need at least O(k/sup 2/N/sup 2/ + k/sup 2/BN) time, where N is the number of input fibers.
15502339
Optimal parallel scheduling algorithm for WDM optical interconnects with recirculating buffering
We study scheduling algorithms in WDM optical interconnects with recirculating buffering. The interconnect we consider has wavelength conversion capabilities. We focus on limited range wavelength conversion while considering full range wavelength conversion as a special case. We formalize the problem of maximizing throughput and minimizing packet delay in such an interconnect as a matching problem in a bipartite graph and give an optimal parallel algorithm that runs in O(Bk/sup 2/), as compared to O((N+B)/sup 3/k/sup 3/) time if directly applying other existing matching algorithms, where N is the number of input/output fibers, B is the number of fiber delay lines and k is the number of wavelengths per fiber.
5688571
Enhancing Downlink Performance in Wireless Networks by Simultaneous Multiple Packet Transmission
In this paper, we consider using simultaneous Multiple Packet Transmission (MPT) to improve the downlink performance of wireless networks. With MPT, the sender can send two compatible packets simultaneously to two distinct receivers and can double the throughput in the ideal case. We formalize the problem of finding a schedule to send out buffered packets in minimum time as finding a maximum matching problem in a graph. Since maximum matching algorithms are relatively complex and may not meet the timing requirements of real-time applications, we give a fast approximation algorithm that is capable of finding a matching at least 3/4 of the size of a maximum matching in O(|E|) time, where |E| is the number of edges in the graph. We also give analytical bounds for maximum allowable arrival rate, which measures the speedup of the downlink after enhanced with MPT, and our results show that the maximum arrival rate increases significantly even with a very small compatibility probability. We also use an approximate analytical model and simulations to study the average packet delay, and our results show that packet delay can be greatly reduced even with a very small compatibility probability.
15452852
Battery-aware router scheduling in wireless mesh networks
Wireless mesh networks emerge as a flexible, low-cost and multipurpose networking platform with wired infrastructure connected to the Internet. A critical issue in mesh networks is to maintain network activities for a long lifetime with high energy efficiency. As more and more outdoor applications require long-lasting, high energy efficient and continuously-working mesh networks with battery-powered mesh routers, it is important to optimize the performance of mesh networks from a battery-aware point of view. Study in battery technology reveals that discharging of a battery is nonlinear. Batteries tend to discharge more power than needed, and reimburse the over-discharged power later if they have sufficiently long recovery time. Intuitively, to optimize network performance, a mesh router should recover its battery periodically to prolong the lifetime. In this paper, we introduce a mathematical model on battery discharging duration and lifetime for wireless mesh networks. We also present a battery lifetime optimization scheduling algorithm (BLOS) to maximize the lifetime of battery-powered mesh routers. Based on the BLOS algorithm, we further consider the problem of using battery powered routers to monitor or cover a few hot spots in the network. We refer to this problem as the spot covering under BLOS policy problem (SCBP). We prove that the SCBP problem is NP-hard and give an approximation algorithm called the spanning tree scheduling (STS) to dynamically schedule mesh routers. The key idea of the STS algorithm is to construct a spanning tree according to the BLOS policy in the mesh network. The time complexity of the STS algorithm is O(r) for a network with r mesh routers. Our simulation results show that the STS algorithm can greatly improve the lifetime, data throughput and power consumption efficiency of a wireless mesh network
12591737
Distributed scheduling algorithms for wavelength convertible WDM optical interconnects
Optical communication is attracting more and more attention because of its huge bandwidth to meet the ever increasing demand of emerging computing/networking applications. In this paper we study distributed scheduling algorithms to resolve output contentions in WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion, including the full range wavelength conversion. Two types of limited range wavelength conversions, circular symmetrical and non circular symmetrical, are studied. We introduce the request graph and show that finding the largest group of contention-free connection requests to achieve maximum network throughput is equivalent to finding a maximum matching in the request graph. Compared with the existing algorithm for finding a maximum matching in an arbitrary bipartite graph with time complexity O(N/sup 3/2/ k /sup 3/2/d), the algorithms we present have time complexity of O(k) and O(dk) (independent of interconnect size N) for non-circular symmetrical and circular symmetrical wavelength conversion, respectively, where k is the number of wavelengths per fiber and d is the conversion degree. In addition, our algorithms can be easily implemented in hardware, and used for time slotted WDM optical interconnects where connections hold for different number of time slots.
29303828
Parameter estimation techniques: a tutorial with application to conic fitting
Almost all problems in computer vision are related in one form or another to the problem of estimating parameters from noisy data. In this tutorial, we present what is probably the most commonly used techniques for parameter estimation. These include linear least-squares (pseudo-inverse and eigen analysis); orthogonal least-squares; gradient-weighted least-squares; bias-corrected renormalization; Kalman filtering; and robust techniques (clustering, regression diagnostics, M-estimators, least median of squares). Particular attention has been devoted to discussions about the choice of appropriate minimization criteria and the robustness of the different techniques. Their application to conic fitting is described.
32960689
On Maximal Shadows of Members in Left-compressed Sets
Whereas Stanley, Proctor and others studied Sperner properties of the poset L(k,m) we consider shadows of left-compressed sets and derive asymptotic bounds on their sizes.
17900866
Robust extraction of specific signals with temporal structure
There is a trend to develop blind or semi-blind source extraction algorithms based on second-order statistics, due to its low computation load and fast processing speed. An important and primary work is done by Barros and Cichocki, who propose an extraction algorithm based on a time delay. The algorithm is simple and fast, but its performance is not satisfying. The paper extends their work and proposes a robust algorithm based on eigenvalue decomposition of several delayed covariance matrices. It is faster and has better performance, which is confirmed by theoretical analysis and computer simulations.
8228858
Coverage-aware proxy placement for dynamic content management over the Internet
In an effort to differentiate service quality, service providers have resorted to employing Content Distribution Networks (CDNs) over the Internet CDNs deploy geographically distributed proxy servers which manage content on behalf of the service provider's servers for better performance and enhanced availability. In this paper we explore the proxy placement problem for content distribution over the Internet. Its goal is to strategically place a number of proxies in the network to optimize certain criteria which improve performance of proxies. We motivate the various necessary factors and constraints that need to be taken into account for a good placement of proxies over the Internet which reflect real world scenario more accurately and which we claim hitherto has not been completely addressed. We introduce a novel concept of host coverage characterizing every Autonomous Systems (AS) and use this stable, coarse grained measure as a long-term estimate of the load being serviced by the proxy system. We then pose an optimal formulation of the proxy placement problem taking into consideration all the relevant factors. We propose a couple of proxy placement algorithms that solve the above problem and analyze their behavior. Finally we present the performance of those algorithms against the optimal solution and other schemes proposed in literature. We also study the stability of the proposed algorithms through a variety of experiments.
14053219
Distributed Algorithm for Service Replication in Service Overlay Network
The service overlay network (SON) is an effective mean to deploy end-to-end QoS guaranteed content delivery services on the current Internet. We model the content delivery service on a SON as a service delivery tree (SDT). Previous studies have addressed the optimal distribution tree formulation issues. In this paper, we focus on the problem of maximizing the total operation profit of the SON. In [1], authors introduced a cost model for optimal bandwidth provisioning in SON. In this paper, we extended this concept and propose an alternative approach to maximize the total effective throughput of SDT as well as to minimize the QoS violation penalty of the SON by service replication. We present both centralized and distributed algorithms for the placement of replicated servers on the SDT. Experiments are carried to quantify the merit, effectiveness and the scalability of the proposed service replication algorithm. In particular, the performance gain is very close to the exhaustive search. The algorithm performs well when we scale up the service overlay networks. Finally, we show that one only needs to perform a small number of replications to attain the optimal gain.