| Home | Papers | Reports | Projects | Code Fragments | Dissertations | Presentations | Posters | Proposals | Lectures given | Course notes |
Object Gerichtheid en Message-Passing over Wide Area Networks - Mogelijke Agent-StrategienWerner Van Belle1* - werner@yellowcouch.org, werner.van.belle@gmail.com Abstract :
Keywords:
Mobile Multi Agent Systems, distributed load balancing, mobile objects, distributed applications |
Inleiding
Het is opvallend hoe vandaag binnen computernetwerken de grens tussen client en server gaandeweg vervaagt om plaats te maken voor een nieuwe vorm van gedistribueerde programma's. Door de enorme toename in performantie van de modale PC is de zogenaamde client immers reeds in staat om zuivere netwerkprogramma's zoals FTP- en WWW-servers te ondersteunen. Anderzijds blijven er natuurlijk een hele reeks diensten over die niet lokaal kunnen aangeboden worden en die toch een hoge graad van interactiviteit langs de client-kant vereisen. Een voorbeeld hiervan zijn de talrijke search-engines op het internet: door hun omvang en algemeenheid leveren ze minder relevante informatie op zodat een intelligente ineractie met de eindgebruiker onontbeerlijk wordt. Denken we hierbij aan een adaptieve filter die tijdelijk lokaal wordt ge\"\i nstalleerd om relevante informatie te herkennen en die nauw samenwerkt met de eigenlijke search-engine. Een ander voorbeeld zijn web-crawlers: aangezien deze vanuit een lokale machine het internet doorlopen geeft dit aanleiding tot een spectaculaire verspilling van de beschikbare bandbreedte. Eigenlijk moet men dus stellen dat de enorme toename in stabiliteit en performantie van de hardware een drastische terugloop in de verhouding aantal clients/aantal servers met zich meebrengt.
In deze evolutie is recent een bijkomende impuls gegeven door bijzondere ontwikkelingen in de technologie. Het meest opvallende verschijnsel hierbij is het succes van de Java virtuele machine die in zowat elke net browser (en weldra in elk uitbatingssysteem) is ingebouwd. Voor de eerste keer in de geschiedenis van de informatica geeft dit aanleiding tot een werkelijk uniform platform dat van de ontkoppeling van software en hardware een (economische) realiteit maakt. Op het gebied van de software architectuur treffen we in dit kader de grootste afwijkingen van het traditionele client/server beeld; Java-applets die delen van de programmatuur van een traditionele server exporteren naar de client zijn het best gekende voorbeeld. Nochtans zijn er reeds verschillende resultaten in de zoektocht naar een meer symmetrische structuur in gedistribueerde systemen: SUN en IBM ontwikkelen respectievelik zogenaamde servlets en aglets. De visie die hierbij ontstaat is er een van ver doorgedreven uniformiteit: alle processen binnen een dergelijk netwerken zijn in hetzelfde medium uitgedrukt. Daarom nemen wij ons hier voor toekomstige gedistribueerde systemen te beschouween als dynamische omgevingen waarbinnen mobiele software agents met elkaar en met menselijke gebruikers kunnen communiceren.
Probleemstelling
De voornaamste reden om de notie van mobiele software in overweging te nemen is de reductie van nodeloze communicatie binnen een groot netwerk. Dit zal een belangrijk effect zijn van de verhoogde intelligentie van software, zoals beschreven in de inleiding. In een systeem zoals het internet, waarbij een immens groot aantal machines op een niet reguliere manier met elkaar verbonden zijn kan het reactievermogen van agents, dat wil zeggen persistente en autonome softwarecomponenten, verhoogd worden door ze ook mobiel te maken. Zo kan bijvoorbeeld de mobiliteit van een menselijke gebruiker weerspiegeld worden in de mobileit van een persoonlijke agent die hem of haar op het internet vertegenwoordigt. Alhoewel de fysieke verandering van locatie van software (zijnde programmatuur + toestand) technisch reeds mogelijk is, blijft de migratiestrategie een open vraag. In de huidige stand van zaken ligt deze beslissing volledig bij de agent z\'elf: de agent zal tot migratie overgaan op basis van beschikbare hardware resources, interactie met andere agents of de eigen inwendige toestand. Het gedrag van zo een agent is dus volledig vastgebakken binnen de code en omwille van zijn autonomiteit is deze zijn enige migratiestrategie.
Deze zuiver autonome voorgeprogrammeerde migratiestrategie zal meestal aanleiding geven tot een alles behalve optimale globale verdeling van agents over een computernetwerk. Dit zal dan ook tot gevolg hebben dat de lokale performatie van de agent hieronder lijdt. Dit is analoog aan de klassieke spanning tussen bi voorbeeld micro- en macro-economie en wordt ook ge\"\i llustreerd door het bekende prisonner's dilemma. In beide gevallen moet het gebrek aan globale kennis gecompenseerd worden door een leerproces. Voor onze agents betekent dit dat lokale waarnemingen via verwerving van kennis dient omgeze te worden in een negotiatie- en migratiestrategie. Klassieke computernetwerken bezitten dit soort van strategie op het niveau van de host machines, van routers of bridges. In ons geval moet deze vervat zijn binnen individuele softwarecomponenten die totaal onafhankelijk van de onderlinge hardware evolueren. Op dit ogenblik ontbreken de formalismen of programmatie-idiomen om dergelijke nieuwe vormen van routing en load-balancing te bestuderen of te verwezenlijken.
Voorstel
Een allereerste doel van het onderzoek zal bestaan uit een uitputtende studie van de parameters die het probleem bepalen: welke factoren bepalen de performantie van een potentieel migrerende agent? Hierbij kan men zowel denken aan performantie-aspecten van de beschikbare hardware (geheugen, disk space, cpu-tijd, netwerk toegangstijden...) als aan samengestelde performatiebegrippen zoals de gemiddelde doeltreffendheid van agents of een sommatie van verschillende formele performantie-eigenschappen van agents [3]. Deze laatste moeten toelaten om op een macroscopische schaal formeel te kunnen redeneren over de performantie van agents of clusters van agents.
Eens de relevante criteria vastgelegd kunnen worden, dienen deze gekoppeld aan de handelingen die kunnen genomen worden om zowel de locale als globale performantie op te drijven. De vraag die zich hier stelt is welke agent wanneer [1] naar waar moet of mag migreren. Om het verband tussen deze criteria en handelingen beter te begrijpen dient de speltheorie zich aan als kandidaat-formalisme. Deze reeds dikwijls toegepaste benadering geeft een goed inzicht in de verbanden tussen het locale en globale niveau wanneer een reeks wedijverende agents handelingen dienen te ondernemen op basis van een reeks vooropgestelde beslissingscriteria. Om het verband tussen de criteria en de handelingen echter computationeel op te lossen, is een klassiek-algoritmische benadering niet aangewezen: zelfs in het statische geval (begrensde en niet evoluerende topologie) is het probleem NP-compleet. Zodoende zullen we onze toevlucht moeten zoeken tot heuristische benaderingstechnieken zoals genetische algoritmen [4] en/of neurale netwerken [5].
Daar de probleemstelling van dit onderzoeksvoorstel uit de re\"ele wereld werd gegrepen is een zuiver theoretische onderzoeksmethodologie echter niet voldoende. Daarom stel ik voor om een experimenteel raamwerk op te zetten dat gebaseerd is op de huidige Java Virtuele Machine architectuur. Op het ogenblik leg ik de laatste hand aan een licentiaatsverhandeling die Java als voertaal gebruikt om een meta-architectuur voor mobiele agents te bouwen. Op basis hiervan kan ik later de voorgestelde modellen experimenten verifi\"eren. Het huidige internet fungeert dan ook meteen als grootschalig laboratorium.
Het lab voor Programmeerkunde van de Vrije Universiteit Brussel heeft reeds een tiental jaar ervaring met het ontwerp van object-gerichte software. Zo speelt de dienst momenteel een pioniersrol in Vlaanderen wat betreft het distribueren van object-gerichte programmatuur in ondermeer Java. Verschillende licentiestudenten maken er projecten en afstudeerwerken omtrent distributie en virtuele machine architectuur. Dit wordt langs de formele kant ondersteund met een inmiddels jarenlange ervaring met formele modellen van object-georienteerdheid. Verder is het lab nauw verbonden met dat van Prof. Manderick waar de nodige expertise rond subsymbolische algoritmen bestaat.
Referenties
[1] Richard Goodwin; Reasoning about when to start acting
[2] Sven Koenig, Richard Goodwin, Reid G. Simmons; Robot navigation with Markov models: a framework for path planning and learning with limited computational resources
[3] Richard Goodwin; Formalizing properties of agents
[4] Melanie Mitchell; Genetic Algoritms
| http://werner.yellowcouch.org/ werner@yellowcouch.org |  |