Filtern
Erscheinungsjahr
Dokumenttyp
- Dissertation (26) (entfernen)
Schlagworte
- Algorithmus (3)
- Middleware (3)
- Abfrageverarbeitung (2)
- Ad-hoc-Netz (2)
- Mobile Computing (2)
- OBDD (2)
- OBDDs (2)
- Peer-to-Peer-Netz (2)
- Selbstorganisation (2)
- mobile computing (2)
Institut
- Informatik (26) (entfernen)
In den letzten Jahren führte die intensive Forschung im Bereich der Hochleistungskommunikationsnetze zu kontinuierlichen technologischen Verbesserungen. Gegenwärtig ist eine schnell wachsende Nachfrage nach mobilen Kommunikationssystemen wie Mobiltelefonen oder kabellosen Computernetzen zu verzeichnen. Parallel zu diesen Entwicklungen stiegen die Anforderungen an die Methoden zur Leistungsanalyse derartiger Systeme. Die Warteschlangentheorie stellt klassische Modelle zur Analyse von Kommunikationsnetzen bereit. Ein Bereich in der modernen Warteschlangentheorie sind die Matrixanalytischen Methoden. Hier konzentriert sich die Forschung auf den Batch Markovian Arrival Process (BMAP), welcher äquivalent zu Neuts Versatile Markovian Point Process ist, und Warteschlangensysteme mit diesem Ankunftsprozeß. Der BMAP ist eine Verallgemeinerung des Poisson Prozesses, des Markov Modulated Poisson Process (MMPP) und des Markovian Arrival Process (MAP). Das BMAP/G/1 Warteschlangensystem wurde analysiert von Ramaswami (damals noch mit der Bezeichnung N/G/1) und Lucantoni. Weitere Varianten wurden später untersucht. Die bisher betrachteten Ankunftsprozesse sind räumlich homogen und somit unabhängig vom aktuellen Zustand des Warteschlangensystems. In modernen Kommunikationsnetzen, wie z.B. ATM, kann jedoch ein dynamisches Routing erfolgen, so daß der Ankunftsstrom in einen Knoten vom aktuellen Zustand dieses Knotens abhängt. Dies war unser Ausgangspunkt für die Definition eines Level-abhängigen BMAPs und die Analyse des BMAP/G/1 Warteschlangensystems mit Level-abhängigen Ankünften. Letzteres stellt eine Verallgemeinerung des klassischen BMAP/G/1 Warteschlangensystems dar. Es umfaßt auch das BMAP/G/1 Warteschlangensystem mit beschränktem Warteraum. Im ersten Teil dieser Arbeit definieren wir einen Level-abhängigen BMAP und leiten wichtige Eigenschaften der Generatormatrix und der Übergangswahrscheinlichkeiten her. Wir zeigen, daß die Übergangsmatrix des Level-abhängigen BMAPs die Vorwärts- und Rückwärtsdifferentialgleichungen erfüllt und somit als Matrixexponentialfunktion der Generatormatrix darstellbar ist. Der zweite Teil befaßt sich mit der Analyse des BMAP/G/1 Warteschlangensystems mit Level-abhängigen Ankünften. Dieses Warteschlangensystem und die zugehörigen stochastischen Prozesse werden in Kapitel 2 eingeführt. Um die Grenzverteilung der Warteschlangenlänge zu bestimmen, verwenden wir die Methode der eingebetteten Markov Kette. In Kapitel 3 bestimmen wir die Einträge der Übergangsmatrix der eingebetteten Markov Kette und die mittlere Zahl Ankünfte während einer Bedienzeit. Stabilitätsbedingungen für das BMAP/G/1 Warteschlangensystem mit Level- abhängigen Ankünften werden durch Anwendung eines verallgemeinerten Foster Kriteriums hergeleitet. Im Level-unabhängigen Fall spielt die Fundamentalperiodenmatrix G die Hauptrolle bei der Bestimmung der Gleichgewichtsverteilung. In unserem Fall hängen die Fundamentalperioden vom Anfangslevel k ab. Daher erhalten wir verschiedene Fundamentalperiodenmatrizen G ( k ) für alle Level k >= 1 . Wir leiten zwei Algorithmen zur Berechnung dieser Matrizen her. Weiterhin zeigen wir, daß die Vektoren der mittleren Anzahlen Bedienabschlüsse während einer Fundamentalperiode die eindeutige Lösung eines unendlich - dimensionalen Systems linearer Gleichungen bilden. Mit diesen Ergebnissen kann die stationäre Verteilung der Warteschlangenlänge zu Bedienabschlußzeitpunkten bestimmt werden. Wir wenden ein Ergebnis aus der Theorie der Semi-Markov Prozesse an, um die Gleichgewichtswahrscheinlichkeiten für Level 0 zu erhalten. Um die Gleichgewichtswahrscheinlichkeiten der übrigen Level zu berechnen, verallgemeinern wir die Formel von Ramaswami. Die Grenzverteilung der Warteschlangenlänge zu beliebigen Zeitpunkten wird unter Verwendung des Hauptsatzes der Erneuerungstheorie hergeleitet. Im dritten Teil betrachten wir einige Spezialfälle. Zunächst nehmen wir an, daß der Phasenprozeß Level-unabhängig sei. In diesem Fall können wir einige unserer Ergebnisse erweitern. Insbesondere leiten wir eine stärkere Stabilitätsbedingung her. Wir beenden diesen Teil, indem wir zeigen, daß unsere Ergebnisse mit den für das klassische BMAP/G/1 Warteschlangensystem und das BMAP/G/1 Warteschlangensystem mit beschränktem Warteraum übereinstimmen. Zum Abschluß dieser Arbeit geben wir einige Hinweise für weitere Forschungen.
Insbesondere im wissenschaftlichen Bereich ist es zur Selbstverständlichkeit geworden, zur Befriedigung eines Informationsbedürfnisses zunächst das World Wide Web (Web) zu benutzen. Der komplexe Aufbau des Webs und die dort herrschende Unordnung machen das Auffinden bestimmter Dokumente zu einem diffizilen Vorgang. Suchmaschinen und Web-Verzeichnisse unterstützen den Benutzer hierbei; ihre effektive Nutzung ist jedoch nicht einfach. Es ist daher hilfreich, Suchdienste zu entwickeln, welche Kontextwissen mitbringen. In der vorliegenden Arbeit wird das Verfahren der thematisch spezialisierten Suche präsentiert und anhand der Menge der persönlicher Home Pages von Informatikern exemplifiziert. Der Bibliographie-Server DBLP.uni-trier.de liefert u.a. zu über 4.000 Wissenschaftlern manuell gesammelte persönliche Home Pages. Durch verschiedene Analysen werden in dieser Menge häufig vorkommende, also relevante Eigenschaften ermittelt. Dies ist ein kreativer Prozess, in den sowohl Suchwissen -- Wissen über Techniken des Suchens im Web -- als auch Fachwissen -- Wissen über die Beschaffenheit persönlicher Home Pages -- einfließen. Nach der Überprüfung dieser Eigenschaften auf ihre Signifikanz in der Gesamtheit der Web-Dokumente ist ein thematisch spezialisiertes Wissen erschaffen worden. Zur Durchführung der Suche würde man idealerweise alle Web-Dokumente mit Hilfe des erarbeiteten Wissens und des Anfrageterms -- des vollständigen Namens eines Informatikers -- untersuchen. Da das Web aus mehreren Milliarden Dokumenten besteht, ist dies praktisch nicht durchführbar: Es ist notwendig, eine geeignete Vorauswahl zu treffen. Suchmaschinen haben Daten zu vielen Web-Dokumenten erfasst. Deshalb wird mit ihrer Hilfe unter Verwendung des Anfrageterms eine Vorauswahl getroffen. Um nun die Dokumente der Vorauswahlmenge gemäß der Anfrage zu bewerten wird das thematisch spezialisierte Wissen adäquat in einer Bewertungsfunktion repräsentiert, welche jedem Dokument einen Wert zuweist und somit eine Rangfolge erstellt. Das Design der Bewertungsfunktion ist eine schöpferische Tätigkeit: Die sachgerechte Gewichtung der verschiedenen Eigenschaften bestimmt maßgeblich das Gelingen des Verfahrens. Der vornehmlich in Java implementierte, vollautomatisierte Web-Dienst HomePageSearch (hpsearch.uni-trier.de) führt regelmäßig für über 100.000 Namen diesen Suchvorgang durch. Der Benutzer kann auf das in einer DB2-Datenbank gespeicherte Ergebnis zurückgreifen. Durch die periodische Neuberechnung des thematisch spezialisierten Wissens wird der Dynamik des Webs Rechnung getragen. Der modulare und stark parametrisierte Aufbau des Systems erleichtert die Portierung des Verfahrens auf andere Mengen von Web-Dokumenten. Nicht zuletzt aufgrund der starken Verlinkung mit DBLP und ResearchIndex wird HomePageSearch von vielen Wissenschaftlern intensiv genutzt.
Die eigene Web-Präsenz hat sich für Unternehmen zu einem nicht mehr wegzudenkenden Instrument, einer flexiblen Schnittstelle zum Kunden, entwickelt. Mit ihr wird eine global erreichbare Anlaufstelle offeriert: Die Chancen der Online-Techniken nutzend ist dem Unternehmen mit seiner Web-Präsenz ein Medium für die "klassische" Werbung, darüber hinaus ein Direkt-Marketing- und Dialog-Medium sowie weiterhin ein eigenes Marktforschungs-Instrument an die Hand gegeben. Dessen Entwicklung und speziell sein Betrieb stellen für ein Unternehmen in verschiedenen Hinsichten eine ernstzunehmende Herausforderung dar. Aus organisatorischer Sicht ist hier die nicht einfach zu realisierende Integration der Web-Präsenz in das Unternehmen anzustreben: Nicht einem isoliert arbeitenden, technikverliebten Mitarbeiter, dem "`Webmaster"', obliegt die Pflege der Web-Präsenz als Allein-Zuständigen, sondern entsprechend ihren Zuständigkeiten übernehmen anteilig die in den Fachabteilungen des Unternehmens tätigen Arbeitskräfte diese Aufgabe. Aus technischer Sicht stellt eine moderne Web-Präsenz ein umfangreiches, und bei hoher Dynamik entsprechend komplexes Produkt dar, für dessen Realisierung nicht unerhebliche Anstrengungen unternommen werden müssen -- insbesondere dann, wenn die zugrundeliegende Technik den organisatorischen Anforderungen innerhalb des Unternehmens gerecht werden soll. Bedingt durch die hohe Innovationsrate im Umfeld der Internet-Technologie befinden sich die Anforderungen an die Betreiber einer Web-Präsenz in einem steten Wandel und erschweren damit den Unternehmen den Einstieg in dieses Medium. Gerade die in vielen Fällen in den Unternehmen noch eingesetzten proprietären Lösungen erfordern aus technischer Sicht einen hohen Integrationsaufwand, wenn die darin vorgehaltenen Informationen für die Web-Präsenz automatisiert einer Zweitverwendung zugeführt werden sollen. Über die zusätzliche Nutzung der Unternehmens-Web-Präsenz bzw. des Systems, mit dem sie erstellt und verwaltet wird, für die unternehmensinterne Arbeit, d.h. für das Intranet, kann der für das Unternehmen entstehende Aufwand relativiert werden. In das Bild des Lebenszyklus' einer modernen Web-Präsenz eingebettet, steht die Konzeption und Entwicklung eines an die im Umfeld des Web-Präsenz-Managements in Unternehmen vorzufindenden Randbedingungen flexibel anpassbaren Online-Redaktionssystems im Vordergrund dieser Arbeit. Zentraler Bestandteil seiner Konzeption ist die Idee, ein sich aus derart vielen separaten Elementen zusammensetzendes, komplexes Gesamtdokument wie eine Unternehmens-Web-Präsenz durch eine wachsende Mitarbeiterzahl -- direkt von deren jeweiligen Arbeitsplätzen aus -- gemeinsam aufzubauen und zu pflegen. Der Praxiseinsatz des bedarfsgerecht in seinen endgültigen Ausprägungen auf die speziellen Belange der Unternehmen maßgeschneiderten Systems begründet die konsequente Nutzung von Internet-Technologien sowie die auf offenen Standards basierende Implementation durch flexible plattformunabhängige Installation und einfache Integration. Im Anschluss an ein einleitendes Kapitel beschreibt diese Arbeit ausgehend von der Problemstellung sowie technischen Grundlagen die Konzeption, Implementation und den Einsatz des webbasierten Online-Redaktionssystems bevor eine Einordnung und schließlich die Zusammenfassung den Abschluss dieser Arbeit bilden.
Due to the breath-taking growth of the World Wide Web (WWW), the need for fast and efficient web applications becomes more and more urgent. In this doctoral thesis, the emphasis will be on two concrete tasks for improving Internet applications. On the one hand, a major problem of many of today's Internet applications may be described as the performance of the Client/Server-communication: servers often take a long time to respond to a client's request. There are several strategies to overcome this problem of high user-perceived latencies; one of them is to predict future user-requests. This way, time-consuming calculations on the server's side can be performed even before the corresponding request is being made. Furthermore, in certain situations, also the pre-fetching or the pre-sending of data might be appropriate. Those ideas will be discussed in detail in the second part of this work. On the other hand, a focus will be placed on the problem of proposing hyperlinks to improve the quality of rapid written texts, at first glance, an entirely different problem to predicting client requests. Ultra-modern online authoring systems that provide possibilities to check link-consistencies and administrate link management should also propose links in order to improve the usefulness of the produced HTML-documents. In the third part of this elaboration, we will describe a possibility to build a hyperlink-proposal module based on statistical information retrieval from hypertexts. These two problem categories do not seem to have much in common. It is one aim of this work to show that there are certain, similar solution strategies to look after both problems. A closer comparison and an abstraction of both methodologies will lead to interesting synergetic effects. For example, advanced strategies to foresee future user-requests by modeling time and document aging can be used to improve the quality of hyperlink-proposals too.
Many real-life phenomena, such as computer systems, communication networks, manufacturing systems, supermarket checkout lines as well as structural military systems can be represented by means of queueing models. Looking at queueing models, a controller may considerably improve the system's performance by reducing queue lengths, or increasing the throughput, or diminishing the overhead, whereas in the absence of a controller the system behavior may get quite erratic, exhibiting periods of high load and long queues followed by periods, during which the servers remain idle. The theoretical foundations of controlled queueing systems are led in the theory of Markov, semi-Markov and semi-regenerative decision processes. In this thesis, the essential work consists in designing controlled queueing models and investigation of their optimal control properties for the application in the area of the modern telecommunication systems, which should satisfy the growing demands for quality of service (QoS). For two types of optimization criterion (the model without penalties and with set-up costs), a class of controlled queueing systems is defined. The general case of the queue that forms this class is characterized by a Markov Additive Arrival Process and heterogeneous Phase-Type service time distributions. We show that for these queueing systems the structural properties of optimal control policies, e.g. monotonicity properties and threshold structure, are preserved. Moreover, we show that these systems possess specific properties, e.g. the dependence of optimal policies on the arrival and service statistics. In order to practically use controlled stochastic models, it is necessary to obtain a quick and an effective method to find optimal policies. We present the iteration algorithm which can be successfully used to find an optimal solution in case of a large state space.
Spatial Queues
(2000)
In the present thesis, a theoretical framework for the analysis of spatial queues is developed. Spatial queues are a generalization of the classical concept of queues as they provide the possibility of assigning properties to the users. These properties may influence the queueing process, but may also be of interest for themselves. As a field of application, mobile communication networks are modeled by spatial queues in order to demonstrate the advantage of including user properties into the queueing model. In this application, the property of main interest is the user's position in the network. After a short introduction, the second chapter contains an examination of the class of Markov-additive jump processes, including expressions for the transition probabilities and the expectation as well as laws of large numbers. Chapter 3 contains the definition and analysis of the central concept of spatial Markovian arrival processes (shortly: SMAPs) as a special case of Markov-additive jump processes, but also as a natural generalization from the well-known concept of BMAPs. In chapters 4 and 5, SMAPs serve as arrival streams for the analyzed periodic SMAP/M/c/c and SMAP/G/infinity queues, respectively. These types of queues find application as models or planning tools for mobile communication networks. The analysis of these queues involves new methods such that even for the special cases of BMAP inputs (i.e. non-spatial queues) new results are obtained. In chapter 6, a procedure for statistical parameter estimation is proposed along with its numerical results. The thesis is concluded by an appendix which collects necessary results from the theories of Markov jump processes and stochastic point fields. For special classes of Markov jump processes, new results have been obtained, too.