National Technical University of Athens (NTUA)
Δρομολόγηση και ανάθεση μήκους κύματος σε οπτικά δίκτυα
Abstract
dc:descriptionWe study models for routing and wavelength assignment in optical networks, aiming at showing properties of these models that must be taken into consideration when optical networks are deployed in practice. More specifically, we propose approximation algorithms for maximizing the number of satisfied requests in optical ring networks where the number of available wavelengths per fiber is given as part of the input. The proposed algorithms, which all possess a bounded approximation ratio, are also compared experimentally with other algorithms already known from the literature. From the comparison, we conclude that the algorithm with the theoretically best approximation ratio produces the best solutions but consumes too much running time. On the contrary, one of the proposed algorithms produces very satisfactory solutions with a running time several orders of magnitude faster than the time of the better algorithm. Moreover, we study a generalization of the problem where every communication request is associated with a given profit, and we seek to maximize the total profit of satisfied requests. We propose an extremely fast, purely combinatorial, and easily implemented algorithm for this problem, which has worse approximation ratio them an already known algorithm, but manages to produce competitive solutions—in some cases, it produces better solutions than all the other algorithms included in the study. From the experimental comparison, we conclude that the proposed algorithm is a decent choice whenever we require decent solutions in limited running time. We also study game-theoretic models for routing and wavelength assignment in multifiber optical networks. We present a full analysis of the price of anarchy when players selfishly choose the wavelength of already routed communication requests, they are charged according to the maximum fiber multiplicity incurred by their choice of wavelength, and the social cost is determined by the maximum wavelength multiplicity that appears at any edge of the network. We prove that the game thus defined always converges to a Nash equilibrium in a finite number of moves, and also propose algorithms for efficiently computing socially optimal and approximate Nash equilibria in specific network topologies. The price of anarchy can grow unbounded even in tree networks with maximum degree three. However, in the case of chains and rings, the price of anarchy is bounded by a constant when the number of available wavelengths is not too large compared to the load of the network—an assumption which covers most cases that can appear in practice. Extending the previous model, we propose a general framework for studying selfish routing and wavelength assignment games in multifiber optical networks, under player cost and social cost functions. We prove upper and lower bounds on the price of anarchy of these games. Finally, we study the complexity of scheduling a set of routes that must be executed periodically in a transportation network with a given period, so that the safety distance between successive vehicles that use the same portion of the network is maximized. For solving this problem, we prove and utilize its connection with a path coloring problem which has been used extensively for modeling routing and wavelength assignment problems in optical networks. Thus, we show the generality of the graph theoretic path coloring models which we studied in the thesis.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Bampas, Evangelos
- Μπαμπάς, Ευάγγελος
Subjects
dc:subject × 20- Οπτικά δίκτυα
- Οπτικά δίκτυα πολλαπλών ινών
- Πολυπλεξία διαίρεσης συχνότητας
- Χρωματισμός μονοπατιών
- Χρωματισμός τόξων
- Πολυχρωματισμός μονοπατιών
- Ικανοποίηση αιτήσεων
- Δρομολόγηση
- Optical networks
- Multifiber optical networks
- Wavelength division multiplexing networks
- Path coloring
- Arc coloring
- Path multicoloring
- Request satisfaction
- Routing
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/22953