| Conception of a Market-Oriented Routing-System for ATM-Networks based on Intelligent Agents |
Schlüsselwörter:
ATM, QoS, Traded Routing, Intelligente Agenten, Elektronische Marktplätze, gradientenbasierte Verhandlung
ATM, QoS, Traded Routing, Intelligent Agents, Electronic Marketplaces, gradient-based negotiations
Sachgruppe der DNBAbstract
The deregulation and liberalization of the telecommunication markets results
in a vast increasing number of services and respective their providers. Due
to a highly scalable Quality of Service (QoS) at the Asynchronous Transfer
Mode (ATM) novel multimedia services are possible now. Concerning the number
of service providers the service-customer is confronted with a continously
increasing number of tariffing models. Currently the choice of an adequate
provider is restricted to the customers' access area. Hence the customer has
no influence on the selection of the involved virtual channels respective
their providers for the aimed end-to-end connection. Accordingly the problem
to configurate an end-to-end connection out of cheap partial connections
within an ATM-WAN still exists. The individual quality of service of that
connection should be negotiated automatically via software means. For the
given problem a technically innovative solution based upon Agent Oriented
Technology (AOT) employing market-oriented concepts has been proposed. For
the setup of a connection the "Traded Routing" as an integrated solution
consists of a dynamic routing procedure as well as a negotiation mechanism.
A resource-market with service-customers as buyers and providers as sellers
has been mapped into an ATM-WAN using Gatewaymarketplaces as specialized
ATM-switches. Buyers and sellers negotiate via a specialized mechanism. The
latter is based upon n-dimensional price-functions, which enable a flexible
mapping of pricing-strategies onto the attributes of a connection link. The
convergence of price and performance within the negotiation process is controlled
via the gradients of the pricing-functions. Additionally the negotiation
system is characterized via "early decision criterions". The property of
partial convergence has been proven. Moreover a "Trusted Third Party" (TTP)
as a supervising entity has been provided. The foundation of the QoS-based
routing is a generalized form of the Bellman-Ford-Moore algorithm. He
calculates m disjunct paths through the network-graph, which comply to the
global optimization criterion of the the m-cheapest paths. A densification
of these paths results into the "Trading Graph" (TG). The latter corresponds
to a source-routing approach and contains alternative paths, which were
calculated in advance an can be selected within the dynamic routing process.
Total correctness as well as time complexity have been formally proven. In
addition the important criterion of cycles is discussed.
Die Deregulierung und Liberalisierung der Tk-Märkte bewirkt eine rapide
Zunahme an Diensten und Anbietern. Bedingt durch eine sehr flexibel
einstellbare Dienstgüte beim Asynchronen Transfer Modus (ATM) sind
darüberhinaus neuartige MM-Dienste möglich. Der Dienstkunde sieht sich bei
seiner Anbieterauswahl mit einer stetig steigenden Anzahl unterschiedlicher
Tariffierungsmodelle konfrontiert. Diese Wahlfreiheit bzgl. des Anbieters ist
heute allerdings auf den Teilnehmerzugangsbereich beschränkt und der
Dienstkunde hat keinen Einfluß auf die Auswahl der für die Erstellung der
Ende-zu-Ende Verbindung involvierten Teilverbindungen inklusive deren
Anbieter. Folglich besteht das Problem, eine kostengünstige Endverbindung
durch die Auswahl entsprechend preiswerter Teilverbindungen innerhalb des
ATM-Netzwerkes zu generieren. Eine individuell verhandelbare
Dienstgütequalität, die es softwaretechnisch zu automatisieren gilt, soll
möglich sein.
Für gegebenes Problem wird eine technisch innovative Lösung unter Einsatz
agentenorientierter Technologie (AOT) sowie marktorientierten Konzepten
vorgeschlagen. Auf der Basis Intelligenter Agenten wird für den
Verbindungsaufbau eine integrierte Lösung aus dynamischem Routing und
Verhandlungsverfahren, das sogenannte "Traded Routing", entworfen. Hierzu
wird im ATM-WAN mit Hilfe der Gatewaymarktplätze als spezialisierten
ATM-Switches ein Ressourcenmarkt mit Dienstkunden als Käufern und Anbietern
als Verkäufern modelliert. Sie verhandeln mittels eines Verfahrens, das auf
einmal stetig differenzierbaren, n-dimensionalen Preisfunktionen aus C(1)
basiert und den Akteuren eine flexible Abbildung ihrer Gebührenstrategien auf
die Gütekriterien einer Teilverbindung ermöglicht. Zur Steuerung der
Konvergenz von Preis und Leistung werden die Gradienten der Preisfunktionen
in die Suche mit einbezogen. Das Verfahren zeichnet sich zudem durch
„frühe Entscheidungskriterien“ aus. Die Eigenschaft der partiellen
Konvergenz wird nachgewiesen. Im Verhandlungsprotokoll ist ebenfalls eine
Trusted Third Party (TTP) als überwachende Instanz vorgesehen. Grundlage des
QoS-basierten Routings bildet eine generalisierte Form des Bellman-Ford-Moore
Algorithmusses. Er berechnet m disjunkte Pfade innerhalb des Netzwerkgraphen,
welche das globale Optimalitätskriterium der m-günstigsten Wege erfüllen.
Eine Verdichtung der Pfade führt zum Tradinggraphen (TG). Er entspricht einem
Sourceroutingansatz, enthält allerdings im voraus berechnete und bewertete
Alternativpfade, die im Rahmen des sich dynamisch vollziehenden Routings
ausgewählt werden können. Die totale Korrektheit sowie Komplexität werden
formal nachgewiesen. Ergänzend wird das wichtige Kriterium der Zyklenfreiheit
diskutiert.
| Betreuer | Krallmann, Hermann; Prof. Dr. |
| Gutachter | Krallmann, Hermann; Prof. Dr. |
| Gutachter | Stiller, Burkhard; Prof. Dr. |
| Upload: | 2000-09-19 |
| URL of Theses: | http://edocs.tu-berlin.de/diss/2000/toebben_hermann.pdf |