Στην εργασία αυτή ασχολούμαστε με το πρόβλημα της δρομολόγησης ενός συνόλου αιτήσεων επικοινωνίας σε WDM (Wavelength Division Multiplexing) πλήρως οπτικά δίκτυα από την άποψη της θεωρίας παιγνίων. Αν θεωρήσουμε κάθε αίτηση δρομολόγησης (ζεύγος κόμβων αφετηρία-προορισμός) ως παίκτη, τότε μία στρατηγική περιλαμβάνει ένα μονοπάτι από τον κόμβο-αφετηρία στον κόμβο-προορισμό και μία συχνότητα (χρώμα). Λαμβάνοντας υπόψη τον περιορισμό ότι δύο παίκτες δεν μπορούν να χρησιμοποιήσουν την ίδια συχνότητα στην ίδια ακμή, θεωρούμε ότι το κόστος δύο αλληλοσυγκρουόμενων στρατηγικών είναι απαγορευτικά μεγάλο.
Στο παραπάνω πλαίσιο, μελετάμε διάφορες φυσικές συναρτήσεις κόστους επικεντρώνοντας στην ύπαρξη αμιγών σημείων ισορροπίας Nash και στην υπολογιστική πολυπλοκότητα αναγνώρισης και υπολογισμού τους. / We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a
strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost.
Under this formulation, we consider several natural cost functions focusing on the existence of Nash equilibria and on the complexity of recognizing and computing them.
Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/879 |
Date | 28 August 2008 |
Creators | Σιούτης, Λεωνίδας |
Contributors | Καββαδίας, Δημήτριος, Καββαδίας, Δημήτριος, Ράγγος, Όμηρος, Ζαγούρας, Χαράλαμπος |
Source Sets | University of Patras |
Language | gr |
Detected Language | Greek |
Type | Thesis |
Rights | 0 |
Relation | Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0748 seconds