Return to search

Ισορροπίες Nash σε πλήρως οπτικά δίκτυα

Στην εργασία αυτή ασχολούμαστε με το πρόβλημα της δρομολόγησης ενός συνόλου αιτήσεων επικοινωνίας σε 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.

Identiferoai:union.ndltd.org:upatras.gr/oai:nemertes:10889/879
Date28 August 2008
CreatorsΣιούτης, Λεωνίδας
ContributorsΚαββαδίας, Δημήτριος, Καββαδίας, Δημήτριος, Ράγγος, Όμηρος, Ζαγούρας, Χαράλαμπος
Source SetsUniversity of Patras
Languagegr
Detected LanguageGreek
TypeThesis
Rights0
RelationΗ ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της.

Page generated in 0.0027 seconds