Spelling suggestions: "subject:"dissertations -- computer science"" "subject:"dissertations -- coomputer science""
1 |
A software restructuring tool for oberonEloff, Johannes J. 12 1900 (has links)
Thesis (MComm) -- University of Stellenbosch, 2001. / ENGLISH ABSTRACT: Software restructuring is a form of perfective maintenance that modifies the structure
of a program's source code. lts goal is increased maintainability to better facilitate
other maintenance activities, such as adding new functionality or correcting previously
undetected errors.
The modification of structure is achieved by applying transformations to the source
code of a software system. Software engineers often attempt to restructure software by
manually transforming the source code. This approach may lead to undesirable and
undetectable changes in its behaviour. Ensuring that manual transformations preserve
functionality during restructuring is difficult; guaranteeing it is almost impossible.
One solution to the problem of manual restructuring is automation through use of
a restructuring tool. The tool becomes responsible to examine each transformation
and determine its impact on the software's behaviour. If a transformation preserves
functionality, it may be applied to produce new source code. The tool only automates
the application of transformations. The decision regarding which transformation to
apply in a specific situation still resides with the maintainer.
This thesis describes the design and implementation of a restructuring tool for the
Oberon language, a successor of Pascal and Modula-2, under the PC Native Oberon
operating system. The process of creating an adequate abstraction of a program's
structure and its use to apply transformations and generate new source code are investigated.
Transformations can be divided into different classes: Scoping, Syntactic,
Control flow and Abstraction transformations. The restructuring tool described in this
thesis contains implementations from all four classes. Informal arguments regarding
the correctness of each transformation are also presented. / AFRIKAANSE OPSOMMING: Die herstrukturering van programmatuur is daarop gemik om die struktuur van 'n
program se bronkode te wysig. Hierdie strukturele veranderings dien in die algemeen
as voorbereiding vir meer omvangryke onderhoudsaktiwiteite, soos byvoorbeeld die
toevoeging van nuwe funksionaliteit of die korrigering van foute wat voorheen verskuil
was.
Die verandering in struktuur word teweeggebring deur die toepassing van transformasies
op die bronkode. Programmatuur-ontwikkelaars voer dikwels sulke transformasies
met die hand uit. Sulke optrede kan problematies wees indien 'n transformasie
die funksionaliteit, in terme van programgedrag, van die programmatuur beïnvloed.
Dit is moeilik om te verseker dat bogenoemde metode funksionaliteit sal behou; om dit
te waarborg is so te sê onmoontlik.
'n Oplossing vir bogenoemde probleem is die outomatisering van die herstruktureringsproses
deur die gebruik van gespesialiseerde programmatuur. Hierdie programmatuur
is in staat om die nodige transformasies toe te pas en terselfdertyd funksionaliteit te
waarborg. Die keuse vir die toepassing van 'n spesifieke transformasie lê egter steeds
by die programmeerder.
Hierdie tesis bespreek die ontwerp en implementering van programmatuur om bronkode,
geskryf in Oberon (die opvolger van Pascal en Modula-2), te herstruktureer. Die
skep van 'n voldoende abstrakte voorstelling van bronkode, die gebruik van sodanige
voorstelling in die toepassing van transformasies en die reprodusering van nuwe bronkode,
word bespreek. Transformasies kan in vier breë klasse verdeel word: Bestek,
Sintaks, Kontrolevloei en Abstraksie. Die programmatuur wat ontwikkel is vir hierdie
tesis bevat voorbeelde uit elkeen van die voorafgenoemde klasse. Informele argumente
word aangebied om die korrektheid van die onderskeie transformasies te staaf.
|
2 |
Random generation of finite automata over the domain of the regular languagesRaitt, Lesley Anne 12 1900 (has links)
Thesis (MSc)--University of Stellenbosch, 2007. / ENGLISH ABSTRACT: The random generation of finite automata over the domain of their graph structures is a wellknown
problem. However, random generation of finite automata over the domain of the regular
languages has not been studied in such detail. Random generation algorithms designed for this
domain would be useful for the investigation of the properties of the regular languages associated
with the finite automata.
We studied the existing enumerations and algorithms to randomly generate UDFAs and binary
DFAs as they pertained to the domain of the regular languages. We evaluated the algorithms
experimentally across the domain of the regular languages for small values of n and found the distributions
non-uniform. Therefore, for UDFAs, we derived an algorithm for the random generation
of UDFAs over the domain of the regular languages from Domaratzki et. al.’s [9] enumeration of
the domain of the regular languages. Furthermore, for binary DFAs, we concluded that for large
values of n, the bijection method is a viable means of randomly generating binary DFAs over the
domain of the regular langagues.
We looked at all the random generation of union-UNFAs and -UNFAs across the domain of
the regular languages. Our study of these UNFAs took all possible variables for the generation of
UNFAs into account. The random generation of UNFAs over the domain of the regular languages
is an open problem / AFRIKAANSE OPSOMMING: Die ewekansige generasie van eindige toestand outomate (eto’s) oor die domein van hul grafiekstrukture
is ’n bekende probleem. Nieteenstaande het die ewekansige generasie van eindige toestand
outomate oor die domein van die regulˆere tale nie soveel aandag gekry nie. Algoritmes wat eindige
toestand outomate ewekansig genereer oor die domein van die regulˆere tale sal nuttig wees om die
ondersoek van die eienskappe van regulˆere tale, wat met eto’s verbind is, te bewerkstellig.
Ons het die bestaande aftellings en algoritmes bestudeer vir die ewekansige generasie van deterministiese
eindige toestand outomate (deto’s) met een en twee alfabetiese simbole soos dit betrekking
het op die domein van die regulˆere tale bestudeer. Ons het die algoritmes eksperimenteel beoordeel
oor die domein van die regulˆere tale vir outomate met min toestande en bevind dat die
verspreiding nie eenvomig is nie. Daarom het ons ’n algoritme afgelei vir die ewekansige generasie
van deto’s met een alfabetsimbool oor die domein van die regulˆere tale van Domaratzki et. al. [9]
se aftelling. Bowendien, in die geval van deto’s met twee alfabetsimbole met ’n groot hoeveelheid
toestande is die ‘bijeksie metode ’n goeie algoritme om te gebruik vir die ewekansige generasie van
hierdie deto’s oor die domein van die regulˆere tale.
Ons het ook die ewekansige generasie van [-nie-deterministiese eindige toestand outomate en
-nie-deterministiese eindige toestand outomate oor die domein van die regulˆere tale bestudeer.
Ons studie van hierdie neto’s het alle moontlike veranderlikes in ageneem. Die ewekansige generering
van deto’s oor die domein van die regulˆere tale is ’n ope probleem.
|
3 |
Automated program generation : bridging the gap between model and implementationBezuidenhout, Johannes Abraham 02 1900 (has links)
Thesis (MSc)--University of Stellenbosch, 2007. / ENGLISH ABSTRACT: The general goal of this thesis is the investigation of a technique that allows model checking to
be directly integrated into the software development process, preserving the benefits of model
checking while addressing some of its limitations. A technique was developed that allows a
complete executable implementation to be generated from an enhanced model specification.
This included the development of a program, the Generator, that completely automates
the generation process. In addition, it is illustrated how structuring the specification as a
transitions system formally separates the control flow from the details of manipulating data.
This simplifies the verification process which is focused on checking control flow in detail. By
combining this structuring approach with automated implementation generation we ensure
that the verified system behaviour is preserved in the actual implementation. An additional
benefit is that data manipulation, which is generally not suited to model checking, is restricted
to separate, independent code fragments that can be verified using verification techniques for
sequential programs. These data manipulation code segments can also be optimised for the
implementation without affecting the verification of the control structure. This technique
was used to develop a reactive system, an FTP server, and this experiment illustrated that
efficient code can be automatically generated while preserving the benefits of model checking. / AFRIKAANSE OPSOMMING: Hierdie tesis ondersoek ’n tegniek wat modeltoetsing laat deel uitmaak van die sagtewareontwikkelingsproses,
en sodoende betroubaarheid verbeter terwyl sekere tekorkominge van
die tradisionele modeltoetsing proses aangespreek word. Die tegniek wat ontwikkel is maak
dit moontlik om ’n volledige uitvoerbare implementasie vanaf ’n gespesialiseerde model spesifikasie
te genereer. Om die implementasie-generasie stap ten volle te outomatiseer is ’n
program, die Generator, ontwikkel. Daarby word dit ook gewys hoe die kontrolevloei
op ’n formele manier geskei kan word van data-manipulasie deur gebruik te maak van ’n
staatoorgangsstelsel struktureringsbenadering. Dit vereenvoudig die verifikasie proses, wat
fokus op kontrolevloei. Deur di´e struktureringsbenadering te kombineer met outomatiese
implementasie-generasie, word verseker dat die geverifieerde stelsel se gedrag behou word in
die finale implementasie. ’n Bykomende voordeel is dat data-manipulasie, wat gewoonlik nie
geskik is vir modeltoetsing nie, beperk word tot aparte, onafhanklike kode segmente wat geverifieer
kan word deur gebruik te maak van verifikasie tegnieke vir sekwensi¨eele programme.
Hierdie data-manipulasie kode segmente kan ook geoptimeer word vir die implementasie sonder
om die verifikasie van die kontrole struktuur te be¨ınvloed. Hierdie tegniek word gebruik
om ’n reaktiewe stelsel, ’n FTP bediener, te ontwikkel, en di´e eksperiment wys dat doeltreffende
kode outomaties gegenereer kan word terwyl die voordele van modeltoetsing behou
word.
|
4 |
Minimization of symmetric difference finite automataMuller, Graham 03 1900 (has links)
Thesis (MSc (Computer Science))--University of Stellenbosch, 2006. / The minimization of a Finite Automaton (FA) deals with the construction of an equivalent FA with the least number of states. Traditional FAs and the minimization thereof is a well defined and researched topic within academic literature. Recently a generalized form of the FA, namely the generalized FA(*-FA), has been derived from these traditional FAs. This thesis investigates the minimization and reduction of one case of ...
|
5 |
Inductive machine learning bias in knowledge-based neurocomputingSnyders, Sean 04 1900 (has links)
Thesis (MSc) -- Stellenbosch University , 2003. / ENGLISH ABSTRACT: The integration of symbolic knowledge with artificial neural networks is becoming an
increasingly popular paradigm for solving real-world problems. This paradigm named
knowledge-based neurocomputing, provides means for using prior knowledge to determine
the network architecture, to program a subset of weights to induce a learning bias
which guides network training, and to extract refined knowledge from trained neural
networks. The role of neural networks then becomes that of knowledge refinement. It
thus provides a methodology for dealing with uncertainty in the initial domain theory.
In this thesis, we address several advantages of this paradigm and propose a solution
for the open question of determining the strength of this learning, or inductive, bias.
We develop a heuristic for determining the strength of the inductive bias that takes the
network architecture, the prior knowledge, the learning method, and the training data
into consideration.
We apply this heuristic to well-known synthetic problems as well as published difficult
real-world problems in the domain of molecular biology and medical diagnoses. We
found that, not only do the networks trained with this adaptive inductive bias show
superior performance over networks trained with the standard method of determining
the strength of the inductive bias, but that the extracted refined knowledge from these
trained networks deliver more concise and accurate domain theories. / AFRIKAANSE OPSOMMING: Die integrasie van simboliese kennis met kunsmatige neurale netwerke word 'n toenemende
gewilde paradigma om reelewereldse probleme op te los. Hierdie paradigma
genoem, kennis-gebaseerde neurokomputasie, verskaf die vermoe om vooraf kennis te
gebruik om die netwerkargitektuur te bepaal, om a subversameling van gewigte te
programeer om 'n leersydigheid te induseer wat netwerkopleiding lei, en om verfynde
kennis van geleerde netwerke te kan ontsluit. Die rol van neurale netwerke word dan die
van kennisverfyning. Dit verskaf dus 'n metodologie vir die behandeling van onsekerheid
in die aanvangsdomeinteorie.
In hierdie tesis adresseer ons verskeie voordele wat bevat is in hierdie paradigma en stel
ons 'n oplossing voor vir die oop vraag om die gewig van hierdie leer-, of induktiewe
sydigheid te bepaal. Ons ontwikkel 'n heuristiek vir die bepaling van die induktiewe
sydigheid wat die netwerkargitektuur, die aanvangskennis, die leermetode, en die data
vir die leer proses in ag neem.
Ons pas hierdie heuristiek toe op bekende sintetiese probleme so weI as op gepubliseerde
moeilike reelewereldse probleme in die gebied van molekulere biologie en mediese diagnostiek.
Ons bevind dat, nie alleenlik vertoon die netwerke wat geleer is met die
adaptiewe induktiewe sydigheid superieure verrigting bo die netwerke wat geleer is met
die standaardmetode om die gewig van die induktiewe sydigheid te bepaal nie, maar
ook dat die verfynde kennis wat ontsluit is uit hierdie geleerde netwerke meer bondige
en akkurate domeinteorie lewer.
|
6 |
A language to support verification of embedded softwareSwart, Riaan 04 1900 (has links)
Thesis (MSc)--University of Stellenbosch, 2004. / ENGLISH ABSTRACT: Embedded computer systems form part of larger systems such as aircraft or chemical processing
facilities. Although testing and debugging of such systems are difficult, reliability is often
essential. Development of embedded software can be simplified by an environment that limits
opportunities for making errors and provides facilities for detection of errors. We implemented
a language and compiler that can serve as basis for such an experimental environment. Both
are designed to make verification of implementations feasible.
Correctness and safety were given highest priority, but without sacrificing efficiency wherever
possible. The language is concurrent and includes measures for protecting the address spaces
of concurrently running processes. This eliminates the need for expensive run-time memory
protection and will benefit resource-strapped embedded systems. The target hardware is
assumed to provide no special support for concurrency. The language is designed to be
small, simple and intuitive, and to promote compile-time detection of errors. Facilities for
abstraction, such as modules and abstract data types support implementation and testing of
bigger systems.
We have opted for model checking as verification technique, so our implementation language
is similar in design to a modelling language for a widely used model checker. Because of
this, the implementation code can be used as input for a model checker. However, since the
compiler can still contain errors, there might be discrepancies between the implementation
code written in our language and the executable code produced by the compiler. Therefore
we are attempting to make verification of executable code feasible. To achieve this, our
compiler generates code in a special format, comprising a transition system of uninterruptible
actions. The actions limit the scheduling points present in processes and reduce the different
interleavings of process code possible in a concurrent system. Requirements that conventional
hardware places on this form of code are discussed, as well as how the format influences
efficiency and responsiveness. / AFRIKAANSE OPSOMMING: Ingebedde rekenaarstelsels maak deel uit van groter stelsels soos vliegtuie of chemiese prosesseerfasiliteite.
Hoewel toetsing en ontfouting van sulke stelsels moeilik is, is betroubaarheid
dikwels onontbeerlik. Ontwikkeling van ingebedde sagteware kan makliker gemaak word met
'n ontwikkelingsomgewing wat geleenthede vir foutmaak beperk en fasiliteite vir foutbespeuring
verskaf. Ons het 'n programmeertaal en vertaler geïmplementeer wat as basis kan dien vir
so 'n eksperimentele omgewing. Beide is ontwerp om verifikasie van implementasies haalbaar
te maak.
Korrektheid en veiligheid het die hoogste prioriteit geniet, maar sonder om effektiwiteit prys
te gee, waar moontlik. Die taal is gelyklopend en bevat maatreëls om die adresruimtes van
gelyklopende prosesse te beskerm. Dit maak duur looptyd-geheuebeskerming onnodig, tot
voordeel van ingebedde stelsels met 'n tekort aan hulpbronne. Daar word aangeneem dat
die teikenhardeware geen spesiale ondersteuning vir gelyklopendheid bevat nie. Die programmeertaal
is ontwerp om klein, eenvoudig en intuïtief te wees, en om vertaaltyd-opsporing van
foute te bevorder. Fasiliteite vir abstraksie, byvoorbeeld modules en abstrakte datatipes,
ondersteun implementering en toetsing van groter stelsels.
Ons het modeltoetsing as verifikasietegniek gekies, dus is die ontwerp van ons programmeertaal
soortgelyk aan dié van 'n modelleertaal vir 'n modeltoetser wat algemeen gebruik word.
As gevolg hiervan kan die implementasiekode as toevoer vir 'n modeltoetser gebruik word.
Omdat die vertaler egter steeds foute kan bevat, mag daar teenstrydighede bestaan tussen die
implementasie geskryf in ons implementasietaal, en die uitvoerbare masjienkode wat deur die
vertaler gelewer word. Daarom poog ons om verifikasie van die uitvoerbare masjienkode haalbaar
te maak. Om hierdie doelwit te bereik, is ons vertaler ontwerp om 'n spesiale formaat
masjienkode te genereer bestaande uit 'n oorgangstelsel wat ononderbreekbare (atomiese) aksies
bevat. Die aksies beperk die skeduleerpunte in prosesse en verminder sodoende die aantal
interpaginasies van proseskode wat moontlik is in 'n gelyklopende stelsel. Die vereistes wat
konvensionele hardeware aan dié spesifieke formaat kode stel, word bespreek, asook hoe die formaat effektiwiteit en reageerbaarheid van die stelsel beïnvloed.
|
7 |
Ontology comprehensionBergh, Johann Rath 03 1900 (has links)
Thesis (MSc (Mathematical Sciences. Computer Science))--University of Stellenbosch, 2011. / ENGLISH ABSTRACT: Ontologies are conceptual models of a domain of discourse and are used in a number
of applications to model a field of knowledge. For example, SNOMED, an ontology
of medical terminology, is widely used among medical professionals. Commercial
ontologies, such as SNOMED, can have hundreds of thousands of concepts. People
who want to use these ontologies need an understanding thereof, but the sheer
magnitude of these ontologies hampers comprehension. It was within this context
that the need arose for software tools that facilitate the understanding of ontologies.
Given this background, our aim is to investigate a new area within the field of
ontologies, namely, ontology comprehension. We make a contribution to it by
developing an ontology comprehension framework and writing a software tool of our
own. This software tool, PathViz, helps users to understand how different concepts
in an ontology are related to each other and what effect entailments have on the
way concepts in an ontology relate to each other. The ontology comprehension
framework, PathViz and the reasoning measurement instruments were found useful
for ontology comprehension by participants at an ontology workshop. / AFRIKAANSE OPSOMMING: Ontologieë is konseptuele modelle van ’n domein en word in verskeie toepassings
gebruik om ’n kennisveld te modelleer. SNOMED is ’n voorbeeld van ’n ontologie
van mediese terme wat baie gebruik word deur die mediese beroepslui. Kommersiële
ontologieë, soos SNOMED, kan bestaan uit duisende konsepte. Dit is belangrik om
hierdie ontologieë wat gebruik word te verstaan, maar die enorme omvang van
hierdie ontologieë belemmer die verstaanproses. In hierdie konteks het die behoefte
ontstaan vir programmatuur wat die verstaanproses van ontologieë vergemaklik.
Met hierdie agtergrond inaggenome, is dit ons doel om ’n nuwe area in die veld
van ontologieë te ondersoek, naamlik, Ontologie-begrip. Ons maak ’n bydra tot
hierdie veld deur ’n raamwerk vir ontologie-begrip te ontwikkel en programmatuur
van ons eie te skryf. Hierdie programmatuur, PathViz, help gebruikers om te
verstaan hoe verskillende konsepte in ’n ontologie aan mekaar verwant is. Verder
help dit gebruikers om te verstaan watter invloed afleidings uit die ontologieë het
op konsepverwantskappe. Deelnemers aan ’n ontologie-werkswinkel het gevind dat
die raamwerk vir ontologie-begrip, PathViz en die instrumente wat die invloed van
die ontologie-redeneerder meet, ontologie-begrip bevorder.
|
8 |
Implementation of cell clustering in cellular automataAdams, Roxane 03 1900 (has links)
Thesis (MSc (Mathematical Sciences)) University of Stellenbosch, 2011. / ENGLISH ABSTRACT: Cellular Automata (CA) have become a popular vehicle to study complex dynamical
behaviour of systems. CA can be used to model a wide variety of physical,
biological, chemical and other systems. Such systems typically consist of subparts
that change their state independently, based on the state of their immediate surroundings
and some generally shared laws of change.
When the CA approach was used to solve the LEGO construction problem, the best
solution was found when using a variant of CA allowing for the clustering of cells.
The LEGO construction problem concerns the optimal layout of a set of LEGO
bricks. The advantages found for using the CA method with clustering in this case
are the ease of implementation, the significantly smaller memory usage to previously
implemented methods, and its trivial extension to construct multicoloured LEGO
sculptures which were previously too complex to construct.
In our research we propose to explore the definitions of clustering in CA and investigate
the implementation and application of this method. We look at the ant
sorting method described by Lumer and Faieta, and compare the implementation
of this algorithm using regular CA as well as the clustering variation. The ant
sorting model is a simple model, in which ants move randomly in space and pick
up and deposit objects on the basis of local information. / AFRIKAANSE OPSOMMING: Sellulêre Outomate (SO) het ’n populêre metode geword om die komplekse dinamiese
gedrag van sisteme bestudeer. SO kan gebruik word om ’n groot verskeidenheid
fisiese, biologiese, chemiese en ander tipe sisteme te modelleer. Sulke sisteme bestaan
tipies uit subafdelings wat, gebaseer op die status van hulle omgewing en ’n
paar algemene gedeelde reëls van verandering, hulle status onafhanklik verander.
Met die gebruik van die SO benadering om the LEGO konstruksieprobleem op te
los, is die beste oplossing bereik deur gebruik te maak van ’n variant van SO, waar
selle saamgroepeer kan word. Die LEGO konstruksieprobleem behels die optimale
uitleg van ’n stel LEGO blokkies. In hierdie geval is die voordele van die SO
met sel groepering die maklike implementasie, ’n beduidende kleiner geheuegebruik
teenoor voorheen geïmplementeerde metodes, en die triviale uitbreiding daarvan om
gekleurde LEGO beelde wat voorheen te kompleks was, te kan bou.
In ons ondersoek verken ons die definisies van selgroepering in SO en ondersoek die
implementasie en toepassing van die metode. Ons kyk na die miersorteringsmetode
beskryf deur Lumer en Faieta, en vergelyk die implementasie van hierdie algoritme
deur gewone SO asook die groeperingsvariasie te gebruik. Die miersorteringsmodel
is ’n eenvoudige model waarin miere lukraak in ’n omgewing beweeg en voorwerpe
optel of neersit volgens plaaslike inligting.
|
9 |
Computer-controlled human body coordinationHakl, Henry 12 1900 (has links)
Thesis (MSc) -- University of Stellenbosch, 2003. / ENGLISH ABSTRACT: A need for intelligent robotic machines is identified. Research and experiments have focussed
on stable, or relatively stable, dynamic simulated systems to demonstrate the feasibility of
embedding advanced AI into dynamic physical systems. This thesis presents an attempt to
scale the techniques to a dynamically highly unstable system - the coordination of movements
in a humanoid model. Environmental simulation, articulated systems and artificial intelligence
methods are identified as three essential layers for a complete and unified approach to embedding
AI into robotic machinery. The history of the physics subsystem for this project is discussed,
leading to the adoption of the Open Dynamics Engine as the physics simulator of choice. An
approach to articulated systems is presented along with the EBNF of a hierarchical articulated
system that was used to describe the model. A revised form of evolution is presented and
justified. An AI model that makes use of this new evolutionary paradigm is introduced. A
variety of AI variants are defined and simulated. The results of these simulations are presented
and analysed. Based on these results recommendations for future work are made. / AFRIKAANSE OPSOMMING: Die beheer van dinamiese masjiene, soos intelligente robotte, is tans beperk tot fisies stabilie
- of relatief stabiele - sisteme. In hierdie tesis word die tegnieke van kunsmatige intelligensie
(KI) toegepas op die kontrole en beheer van 'n dinamies hoogs onstabiele sisteem: 'n Humanoïede
model. Fisiese simulasie, geartikuleerde sisteme en kunmatige intelligensie metodes
word geïdentifiseer as drie noodsaaklike vereistes vir 'n volledige en eenvormige benadering tot
KI beheer in robotte. Die implementasie van 'n fisiese simulator word beskryf, en 'n motivering
vir die gebruik van die sogenaamde "Open Dynamics Engine" as fisiese simulator word gegee.
'n Benadering tot geartikuleerde sisteme word beskryf, tesame met die EBNF van 'n hierargiese
geartikuleerde sisteem wat gebruik is om die model te beskryf. 'n Nuwe interpretasie vir evolusie
word voorgestel, wat die basis vorm van 'n KI model wat in die tesis gebruik word. 'n
Verskeidenheid van KI variasies word gedefineer en gesimuleer, en die resultate word beskryf
en ontleed. Voorstelle vir verdere navorsing word gemaak.
|
10 |
A bandwidth market for traffic engineering in telecommunication networksCombrink, J. J. (Jacobus Johannes) 04 1900 (has links)
Thesis (MSc)--University of Stellenbosch, 2004. / ENGLISH ABSTRACT: Traffic engineering determines the bandwidth allocation required to meet the traffic loads in a
network. Similarly an economic market determines the resource allocation required to meet the
demand for resources. The term bandwidth market denotes traffic engineering methods that use
economic market methodology to determine the bandwidth allocation required to meet the traffic
loads. A bandwidth market is an attractive traffic engineering method because of its distributed
nature and ability to respond quickly to changes in network architecture or traffic loads.
Network terminology is frequently used to define bandwidth markets. Our approach is to use
the concepts of microeconomics to define a bandwidth market. The result is that our bandwidth
markets are similar to economic markets, which is advantageous for applying economic principles
correctly.
This thesis presents the theoretical basis for two bandwidth markets. The first bandwidth market
is a framework for building bandwidth markets. The second bandwidth market represents a society
of cooperating individuals. The society distributes resources via a mechanism based on economic
principles. An implementation of the bandwidth market is presented in the form of an optimisation
algorithm, followed by its application to several test networks.
We show that, in the test networks examined, the optimisation algorithm reduces the network
loss. For all test networks, the network loss achieved by the optimisation algorithm compares well
with the network loss achieved by a centralised optimisation algorithm. / AFRIKAANSE OPSOMMING: Verkeersingenieurswese bepaal die nodige bandwydtetoekenning om die verkeersvolume in 'n
netwerk te dra. Op 'n soortgelyke wyse bepaal 'n ekonomiese mark die nodige hulpbrontoekenning
om die aanvraag vir hulpbronne te bevredig. Die terme bandwydtemark stel verkeersingenieurswesetegnieke
voor wat ekonomiese-mark metodes gebruik om die bandwydtetoekenning vir die
verkeersvolume in 'n netwerk te bepaal. 'n Bandwydtemark is 'n aantreklike verkeersingenieurswesetegniek
omdat dit verspreid van aard is en vinnig kan reageer op veranderinge in netwerk
argitektuur en verkeersvolume.
Netwerkterminologie word gereeld gebruik om bandwydtemarkte te definieer. Ons benadering is
om mikro-ekonomiese begrippe te gebruik om 'n bandwydtemark te definieer. Die resultaat is
dat ons bandwydtemarkte soortgelyk aan ekonomiese markte is, wat voordelig is vir die korrekte
toepassing van ekonomiese beginsels.
Hierdie tesis lê die teoretiese grondwerk vir twee bandwydtemarkte. Die eerste bandwydtemark
is 'n raamwerk vir die ontwikkeling van bandwydtemarkte. Die tweede bandwydtemark stel 'n
vereniging van samewerkende individue voor. Die vereniging versprei bandwydte deur middel van
'n meganisme wat gebasseer is op ekonomiese beginsels. 'n Implementasie van hierdie bandwydtemark
word voorgestel in die vorm van 'n optimeringsalgoritme, gevolg deur die toepassing van
die optimeringsalgoritme op 'n aantal toetsnetwerke.
Ons wys dat die bandwydtemark die netwerkverlies verminder in die toetsnetwerke. In terme van
netwerkverlies vaar die bandwydtemark goed vergeleke met 'n gesentraliseerde optimeringsalgoritme.
|
Page generated in 0.1564 seconds