Theses supervised by Doç. Dr. Ezhan Karaşan
13 theses · İhsan Doğramacı Bilkent University
Boşluk-doldurma çizelgelemesi kullanan OBS ağlarında çoğuşma uzunluğunun kayıp olasılığına etkisi
Optical burst switching (OBS) is a new transport architecture for the next gener-ation optical internet infrastructure which is necessary for the increasing demandof high speed data traï¬c. Optical burst switching stands between optical packetswitching, which is technologically diï¬cult, and optical circuit switching, whichis not capable of eï¬ciently transporting bursty internet traï¬c. Apart from itspromising features, optical burst switching suï¬ers from high traï¬c blocking prob-abilities. Wavelength conversion coupled with ï¬ber delay lines (FDL) provide oneof the best means of contention resolution in optical burst switching networks.In this thesis, we examine the relation between burst loss probability and burstsizes for void ï¬lling scheduling algorithms. Simulations are performed for variousvalues of the processing and switching times and for diï¬erent values of wave-lengths per ï¬ber and FDL granularity. The main contribution of this thesis isthe analysis of the relationship between burst sizes and processing time and FDLinduced voids. This in turn creates a better understanding of the burstiï¬cationand contention resolution mechanisms in OBS networks. We show that voids gen-erated during scheduling are governed by the FDL granularity and the product ofthe per-hop processing delay and residual number of hops until the destination.We also show that diï¬erentiation between bursts with diï¬erent sizes is achievedfor diï¬erent network parameters and a diï¬erentiation mechanism based on burstlengths is proposed for OBS networks.
Kablosuz duyucu ağlarında enerji korunması için kısmi kapsamalı uyku düzenlemesi
Wireless sensor networks, which consist of many sensor devices communicatingwith each other in order to sense the environment, is an emerging field in thearea of wireless networking. The primary objective in these wireless networksis the efficiency of energy consumption. Since these networks consist of a largenumber of sensors, allowing some of the nodes to sleep intermittently can greatlyincrease the network lifetime. Furthermore, some applications do not require100% coverage of the network field and allowing the coverage to drop below100%, i.e., partial coverage, can further increase the network lifetime.A sleep scheduling algorithm must be distributed, simple, scalable and en-ergy efficient. In this thesis, the problem of designing such an algorithm whichextends network lifetime while maintaining a target level of partial coverage isinvestigated. An algorithm called Distributed Adaptive Sleep Scheduling Algo-rithm (DASSA) which does not require location information is proposed. Theperformance of DASSA is compared with an integer linear programming (ILP)based optimum sleep scheduling algorithm, an oblivious algorithm and with anexisting algorithm in the literature. DASSA attains network lifetimes up to 89%iof the optimum solution, and it achieves significantly longer lifetimes comparedwith the other two algorithms.Furthermore, the minimum number of sensors that should be deployed inorder to satisfy a given partial coverage target with a certain probability whilemaintaining connectivity is computed and an ILP formulation is presented forfinding the minimum number of sensors that should be activated within the setof deployed sensors.Keywords: Wireless Sensor Networks, Partial Coverage, Sleep Scheduling, Net-work Lifetimeii
Dilimli optik çoğuşma anahtarlamalı ağlarda hizmet niteliği çözümlemesi
Optical burst switching (OBS) is proposed as the switching paradigm of next-generation optical Internet. In OBS, IP packets from access networks are assembled into longer units of bursts allowing a lower level of switching granularity offered by the readily available optical technology. Although OBS was asynchronous in the earlier work, slotted OBS (SOBS) has recently caught the attention of the researchers due to performance gains achievable with synchronous infrastructures. In this thesis, we study the blocking probabilities in a slotted optical burst switching node fed with independent and identically distributed Poisson burst traffic and for which the burst sizes are a fixed integer multiple of the slot length. We develop a discrete time Markov chain based framework to obtain the blocking probabilities in systems with and without QoS differentiation. In particular, we study priority scheduling andoffset-based QoS differentiation mechanisms for SOBS networks. The latter problem suffers from the curse of dimensionality, which we address by a discrete phase type approximation for the discrete Poisson distribution. The results obtained by using themoment-matched phase type distribution are shown to provide a very accurate approximation for the blocking probabilities. Finally, we extend our framework to analyze the hybrid priority scheduling with unity-offset based differentiation scheme which proves to outperform the others in the degree of class isolation. We show that increasing burst length has an adverse affect on the attained QoS level. We also give a quantitative discussion of the trade off between the burst blocking probability and the slot granularity. As the slot duration is decreased, burst transmissions can be initiated in an earlier time decreasing the end-to-end delay in an SOBS network with a penalty of increased burst loss probability. We evaluate the burst blocking probabilities of a classless and two-class SOBS nodes as a function of the slot length, number of wavelengths and traffic load.
Optik çoğuşma ağlarındaki TCP trafikleri için sıkışıklık penceresi tabanlı uyarlamalı çoğuşma oluşturma algoritması
Burst assembly is one of the key factors affecting the TCP performance in Optical Burst Switching (OBS) networks. Timer based burst assembly algorithm generates bursts independent of the rate of TCP flows. When TCP congestion window is small, the fixed-delay burst assembler waits unnecessarily long, which increases the end-to-end delay and decreases the TCP goodput. On the other hand, when TCP congestion window becomes larger, the fixed-delay burst assembler may unnecessarily generate a large number of small-sized bursts, which increases the overhead and decreases the correlation gain, resulting in a reduction in the TCP goodput. Using simulations, we show that the usage of the congestion window (cwnd) size of TCP flows in the burst assembly algorithm consistently improves the TCP goodput (by up to 38.4%) compared with the fixed-delay timer based assembly even when the timer based assembler uses the optimum assembly period threshold value. One limitation of this proposed method is the assumption that the exact value of the congestion window is available at the burst assembler. We then extend the adaptive burstification algorithm such that the burst assembler uses estimated values of the congestion window that are obtained via passive measurements at the ingress node. It is shown through simulations that even when estimated values are used, TCP goodput can achieve values close to the results obtained by using exact values of the congestion window.
Optik çoğuşum anahtarlama ağları için düzenlenmiş kontrol düzleminin kapasitesine uygun uyarlanabilir çoğuşum oluşturma algoritması
Recent developments in wavelength-division multiplexing (WDM) technology increase the amount of bandwidth available in fiber links by many orders of magnitude. However, this increase in link capacities is limited by the conventional electronic router's capability. Optical burst switching (OBS) has been proposed as a promising and a short-term solution for switching technology to take advantage of increased capacity of optical links. The congestion in OBS control plane and the adaptive burst assembly algorithms are two important research topics that are among the most effective factors determining the performance of OBS networks. These two problems have been separately studied in the literature so far. It has been shown that contending bursts at a core optical switch in an OBS network may experience unfair loss rates based on their residual offset times and burst lengths, that are called path length priority effect (PLPE) and burst length priority effect (BLPE), respectively. In this thesis, we propose a new adaptive timer-based burst assembly algorithm (ATBA) which uses loss rate measurements for determining the burstification delays of traffic streams in order to mitigate the undesired effects of PLPE and BLPE. ATBA distributes the burst generation rates of traffic streams at an ingress node such that total rate of generated bursts is constant in order to constrain the congestion in the control plane. Without ATBA, the fairness index drops to 76% when per hop processing delay (PHPD) is increasing. With ATBA, the fairness index drops only to 85% with increasing PHPD. It is also shown that the total goodput of the OBS network improves by 5% compared with the case without ATBA.
Çok kanallı IEEE 802.11 ağlarda erişim noktalarının optimizasyonu
A wireless access point (WAP or AP) is a device that allows wireless communication devices to connect to a wireless local area network (WLAN). AP usually connects to a wired network, and can relay data between the wireless devices (such as computers or printers) and wired devices on the network. Optimal access point selection is a crucial problem in IEEE 802.11 WLAN networks. Access points (APs) cover a certain area and provides an adequate bandwidth to the users around them. When the area to be covered is large, several APs are necessary. Furthermore in order to mitigate the adverse effects of interference between APs, multi channels are used. In this thesis, a service area is divided into demand clusters (DCs) in which number of users per DC and average traffic rates are known. Next, we calculate the congestion of each AP by using the average traffic load. With our Optimal Access Point Selection Algorithm, we balance the traffic loads in APs using a mixed integer linear programming formulation. This algorithm guarantees that each DC is assigned an AP and there is sufficient received power. Furthermore, the interference between the adjacent APs is controlled so that the received signal to interferenceand noise ratio at each AP satisfies a minimum level. Interference control is accomplished by using a multi-channel WLAN. In this thesis, both orthogonal (non-overlapping) and non-orthogonal (overlapping) channel assignment schemes are considered. The total interference is computed taking into account both co-channel and inter-channel interferences.The developed AP selection methodology is applied to WLAN designs for several buildings. It is observed from the designated networks that a DC should not need to connect to the closest AP but it may be connected to an AP which may be farther away but less congested. DCs are assigned to APs such that all DCs are covered. The effects of the parameter such as traffic load, receiver sensitivity, number of APs, etc are also studied.Keywords: IEEE 802.11 networks, Access Point selection, Load balancing.
STDMA tabanlı çoklu-kanallı/radyolu/hızlı kablosuz örgü ağlarda birleşik link/paket planlaması, hız ataması ve yönlendirme
In this thesis, we study the joint scheduling and routing problem in spatial reuse Time Division Multiple Access (STDMA) based multi-channel/multi-radio/multi-rate wireless mesh networks (WMNs). The main objective of the joint scheduling and routing problem addressed in thesis is to reduce the number of required TDMA time slots to deliver all packets to their destinations. Since the optimum solution to the problem is NP-hard, we propose a greedy iterative solution methodology. The problem is formulated as an integer linear program (ILP) under the physical interference model. We consider two versions of the problem in order to investigate the factors affecting the capacity of WMNs. In the first one, we perform scheduling and routing when the number of channels and number of radios are varied for multi-rate WMNs where nodes are equipped with omni-directional antennas. This analysis is done for both single-class (best-effort traffic) and two-class (best-effort and delay sensitive classes) traffic models. We then extend this analysis by adding the power control scheme which allows transmitters to change the transmitting powers slot-by-slot. Finally, joint scheduling and routing problem is extended for WMNs where nodes are equipped with multiple sectored antennas. We show that the network performance is improved with more radio resources, e.g., using multiple orthogonal channels, multiple radios per node, transmit power control scheme, and directional antennas in terms of delay and total dissipated energy. The network throughput when using 3 channels and 3 radios is increased by up to 67.2% compared to single channel WMNs and the total dissipated energy is reduced by up to 45.5% with transmit power control scheme. Finally, when directional antennas with 6 sectors are used at both transmitters and receivers, the network throughput increases by up to 72.6% compared to omni-directional antenna case.
STDMA tabanlı tek-kanallı kablosuz örgü ağlarda birleşik link/paket planlaması, hız ataması ve yönlendirme eniyilemesi
Wireless Mesh Networks (WMN) are a promising solution for next generation wireless access networks since they cherish benefits of having a reliable backbone in an ad hoc nature. This thesis investigates the joint scheduling and routing problem in minimizing the maximum delay required for delivering a given packet traffic to the intended destinations in spatial reuse Time Division Multiple Access (STDMA) based single channel multi-rate WMNs. Firstly, an Integer Linear Programming (ILP) model is developed by considering the constraints inherent to the problem, such as the Signal-to-Noise and Inteference Ratio (SINR) and capacity. The model is then improved by using additional constraints, such that these constraints do not affect the final solution but narrow down the search space. Because of the computational complexity, this ILP based optimization model is limited to small sized networks. We then consider different approaches to obtain sub-optimum solutions and find good lower and upper bounds on the optimum solution. LP and Lagrangian relaxations are used for obtaining lower bounds. Improving LP relaxation with cutting planes and Lagrangian relaxation, we obtain lower bounds that are up to 100% tighter than the simple LP relaxation. Next, a greedy heuristic approach is employed as an upper bounding technique. Tabu Search technique is implemented to improve the upper bound provided by the greedy approach, and around 10 - 20% tighter bounds are obtained. The sub-optimum solutions obtained by using the heuristic Tabu Search algorithm are shown to provide maximum delays that are within 10 -50% of the bounds obtained by using the cutting planes and Lagrangian relaxation for the networks considered in this thesis.
Optik ağlarda fiziksel katman bozuklukları altında çok katmanlı trafik mühendisliği
We study Traffic Engineering (TE) in Multiprotocol Label Switching (MPLS)/Wavelength Division Multiplexing (WDM) networks and propose a multi-layer TE method. MPLS provides powerful TE features for IP networks and is widely deployed in backbone networks. WDM can increase the transmission capacity of optical fibers to tremendous amounts, therefore it has been the dominant multiplexing technology used in the optical layer.The proposed multi-layer TE solution facilitates efficient use of network resources where the TE mechanisms in the MPLS and WDM layers coordinate. We consider a static WDM layer and available traffic expectation information. The TE problem arising in the considered scenario is the Virtual Topology Design (VTD) problem, which involves the decision of WDM lightpaths to be established, calculation of MPLS Label Switched Paths (LSPs) on the resulting virtual topology, and calculation of the routes and wavelengths in the physical topology that correspond to the lightpaths in the virtual topology. We assume a daily traffic pattern changing with the time of day and aim to design a static virtual topology that satisfies as much of the offered traffic as possible, over the whole day.In our proposed solution, the multi-layer VTD problem is solved by decomposing it into two sub-problems, each involving in a single layer. The decomposition approach is used in the thesis due to the huge computational burden of the combined solution for real-life networks. The sub-problem in the MPLS layer is the design of the lightpath topology and calculation of the LSP routes on this virtual topology. This problem is known to be NP-complete and finding its optimum solution is possible only for small networks. We propose a Tabu Search based heuristic method to solve two versions of this problem, resource oriented and performance oriented. Integer Linear Programming (ILP) relaxations are also developed for obtaining upper and lower bounds. We show that the gap between the produced solutions and the lower and upper bounds are around 10% and 7% for the resource and performance oriented problems, respectively.Since the actual traffic can show deviations from the expected values, we also developed an MPLS layer online TE method to compensate the instantaneous fluctuations of the traffic flows. In the proposed method, the LSPs are rerouted dynamically using a specially designed cost function. Our numerical studies show that using the designed cost function results in much lower blockings than using commonly used Widest Shortest Path First and Available Shortest Path First approaches in the literature.The corresponding sub-problem of the multi-layer VTD problem in the WDM layer is the Static Lightpath Establishment (SLE) problem. Along with the capacity and wavelength continuity constraints, we also consider the Bit Error Rate (BER) constraints due to physical layer impairments such as attenuation, polarization mode dispersion and switch crosstalk. This problem is NP-complete even without the BER constraints. We propose a heuristic solution method and develop an exact ILP formulation to evaluate the performance of the proposed method for small problem sizes. Our proposed method produces solutions close to the optimum solutions for the cases in which the ILP formulation could be solved to optimality.Then, these solution methods for the single layer sub-problems are combined in a multi-layer TE scheme to solve the VTD problem in both layers jointly. The proposed TE scheme considers the physical layer limitations and optical impairments. This TE scheme can be applied by keeping each layer's information hidden from the other layer, but our simulations show that it can produce more effective and efficient solutions when the physical layer topology information is shared with the MPLS layer. We also investigate the effect of non-uniform optical components in terms of impairment characteristics. The numerical results show that more traffic can be routed when all the components in the network have moderate impairment characteristics, compared to the case in which some components have better and some have worse impairment characteristics.
Çok-sekmeli telsiz ağlar için bir analitik IEEE 802.11 DCF modeli ve modelin ulaştırılan iş ile enerji analizine uygulanması
In this thesis, we present an analytical model for the IEEE 802.11 DCF in multi-hop networks that considers hidden terminals and works for a large range of traffic loads. A goodput model which considers rate reduction due to collisions, retransmissions and hidden terminals, and an energy model, which considers energy consumption due to collisions, retransmissions, exponential backoff and freezing mechanisms, and overhearing of nodes, are proposed and used to analyze the goodput and energy performance of various routing strategies in IEEE 802.11 DCF based wireless multi-hop networks. Moreover, an adaptive routing algorithm which determines the optimal routing strategy adaptively according to the network and traffic conditions is suggested.Viewed from goodput aspect the results are as follows: Under light traffic, arrival rate of packets is dominant, making any routing strategy equivalently optimal. Under moderate traffic, concurrent transmissions dominate and multi-hop transmissions become more advantageous. At heavy traffic, multi-hopping becomes unstable due to increased packet collisions and excessive traffic congestion, and direct transmission increases goodput. From a throughput aspect, it is shown that throughput is topology dependent rather than traffic load dependent, and multi-hopping is optimal for large networks whereas direct transmissions may increase the throughput for small networks.Viewed from energy aspect similar results are obtained: Under light traffic, energy spent during idle mode dominates in the energy model, making any routing strategy nearly optimal. Under moderate traffic, energy spent during idle and receive modes dominates and multi-hop transmissions become more advantageous as the optimal hop number varies with processing power consumed at relay nodes. At the very heavy traffic conditions, multi-hopping becomes unstable due to increased collisions and direct transmission becomes more energy-efficient.The choice of hop-count in routing strategy is observed to affect energy-efficiency and goodput more for large and homogeneous networks where it is possible to use shorter hops each covering similar distances. The results indicate that a cross-layered routing approach, which takes energy expenditure due to MAC contentions into account and dynamically changes therouting strategy according to the network traffic load, can increase goodput by at least %18 and save energy by at least 21% in a realistic wireless network where the network traffic load changes in time. The goodput gain increases up to 222% and energy saving up to 68% for denser networks where multi-hopping with much shorter hops becomes possible.
WiMAX şebekelerinde kısmi frekans tekrar kullanımı için statik ve ayarlanabilir altkanal tahsis şemalarının performansı
We study the downlink performance of WiMAX under fractional frequency reuse (FFR)model. Conventional cellular planning methods can be used for broadband wireless accesssystems that operate in point-to-multipoint (PMP) conguration based on OFDMA/OFDMsuch as WiMAX. As an alternative planning method, FFR has been recently proposed forOFDMA/OFDM based cellular systems. FFR divides the cell into two regions: the innerand outer cell. Mobile Stations (MS) inside the inner cell can use the entire frequencyband (achieving full frequency reuse), while MSs in the outer ring use a fraction of theband (having fractional frequency reuse). Transmissions in the inner and outer cells occurduring dierent time periods so that users at the cell edge experience less interference. Inthis thesis, we investigate the eect of dynamically changing the number of subcarriersallocated to inner and outer cells. We use two metrics: total cell throughput and Jain'sfairness index for the distribution of cell throughput among MSs. As the ratio of subcarriersallocated to inner cell increases, the total cell throughput increases while the fairnessindex decreases. We use the product of cell throughput and fairness index in order to studythe trade-o between the two metrics. We show that by dynamically adjusting the ratioof subcarriers allocated to the inner cell based on the user distribution, the throughputiiifairness index product can be increased by about 5% compared with the xed optimumsubcarrier allocation.
Dağıtık ve kanal bilgisi kullanan; CSMA tabanlı kablosuz ağlarda zamanla değişen kanallar altında gecikmeye hassas uygulamalar için link çizelgeleme
In wireless networks, interference between neighboring links is an important issue. The link scheduling algorithm controls the interference between neighboring links such that no adjacent links can be concurrently active. Distributed throughput optimum algorithms for the link scheduling problem have been proposed in the literature. However, the maximum packet delays of these distributed throughput optimum algorithms can become arbitrarily large, which significantly degrades the performances of delay sensitive applications such as "Skype". In this thesis, we propose two distributed link scheduling algorithms: a full opportunistic algorithm and a delay based adaptive algorithm. The proposed algorithms, while maintaining throughput optimality, increase the average delay performance of the previously proposed throughput optimum scheduling algorithms by 20% under the fading radio channel. We propose a new metric "Effective Goodput", which measures the rate of packets that are successfully received before their respective playout times for delay sensitive applications. The delay based distributed adaptive scheduling algorithm proposed in the thesis increases the "Effective Goodput" by nearly 100% compared with the throughput optimum scheduling algorithms proposed in the literature.
Geniş bantlı kablosuz ağlarda gecikmeye hassas uygulamalar için yer-uydu bağı zamanlamaları
In wireless networks, there are two main scheduling problems: uplink (mobile station to base station) and downlink (base station to mobile station). During the downlink scheduling, scheduler at the base station (BS) has access to queue information of mobile stations (MS). On the other hand, for uplink scheduling, BS only has the partial information of the MS since distributing the detailed queue information from all MSs to BS creates significant overhead.In this thesis, we propose a novel uplink scheduling algorithm for delay sensitive traffic in broadband wireless networks. In this proposed algorithm, we extend the bandwidth request/grant mechanism defined in IEEE 802.16 standard and send two bandwidth requests instead of one: one greedy and the other conservative requests. MSs dynamically update these bandwidth requests based on their queue length and bandwidth assignment in previous frames. The scheduler at the BS tries to allocate these bandwidth requests such that the system achieves a high goodput (defined as the rate of error-free packets delivered within a maximum allowed delay threshold) and bandwidth is allocated in a fair manner, both in short term and in steady state. The proposed scheduling algorithm can utilize the network resources higher than 95% of the downlink scheduling algorithms that use the complete queue state information at the MS. Using just partial queue state information, the proposed scheduling algorithm can achieve more than 95% of the total goodput achieved by downlink scheduling algorithms utilizing whole state information. The proposed algorithm also outperforms several downlink scheduling algorithm in terms of short-term fairness.