We propose a Capabilities-based approach for constructing complex emergent systems such that they are change-tolerant, and the development effort promotes change-reduction. The inherent complexity of software systems increases their susceptibility to change when subjected to the vagaries of user needs, technology advances, market demands and other change inducing factors. Despite the inevitability of change, traditional Requirements Engineering strives to develop systems based on a fixed solution. This is a mostly unsuccessful approach as evidenced by the history of system failures. In contrast, we utilize Capabilities — functional abstractions that are neither as amorphous as user needs nor as rigid as system requirements — to architect systems to accommodate change with minimum impact. These entities are designed to exhibit desirable characteristics of high cohesion, low coupling and balanced abstraction levels. Capabilities are generated by a two-phased process called Capabilities Engineering. Phase I mathematically exploits the structural semantics of the Function Decomposition graph — a representation of user needs — to formulate change-tolerant Capabilities. Phase II optimizes these Capabilities to conform to schedule and technology constraints. Results from an empirical evaluation of a real-world Course Evaluation System indicate, with statistical significance, that a Capabilities-based design is more change-tolerant than a requirements-based design. In addition, we observe that the use of the CE process inherently reduces change, otherwise generated, during the regular development effort. Empirical analysis on the change-requests of Sakai, a complex emergent system, supports this claim. Finally, we observe that the process of Capabilities Engineering assists in pre-requirement specification traceability by bridging the complexity gap between the problem and solution spaces. / Ph. D.

<p>Network and system management has always been of concern for telecommunication and computer system operators. The need for standardization was recognised already 20 years ago, hence several standards for network management exist today. However, the ever-increasing number of units connected to networks and the ever-increasing number of services being provided results in significant increased complexity of average network environments. This challenges current management systems. In addition to the general increase in complexity the trend among network owners and operators of merging several single service networks into larger, heterogeneous and complex full service networks challenges current management systems even further. The full service networks will require management systems more powerful than what is possible to realize basing systems purely on todays management standards. This thesis presents a distributed stochastic optimization algorithm which enables implementations of highly robust and efficient management tools. These tools may be integrated into management systems and potentially make the systems more powerful and better prepared for management of full service networks.</p><p>Emergent behavior is common in nature and easily observable in colonies of social insects and animals. Even an old oak tree can be viewed as an emergent system with its collection of interacting cells. Characteristic for any emergent system is how the overall behavior of the system emerge from many relatively simple, restricted behaviors interacting, e.g. a thousand ants building a trail, a flock of birds flying south or millions of cells making a tree grow. No centralized control exist, i.e. no single unit is in charge making global decisions. Despite distributed control, high work redundancy and stochastic behavior components, emergent systems tend to be very efficient problem solvers. In fact emergent systems tend to be both efficient, adaptive and robust which are three properties indeed desirable for a network management system. The algorithm presented in this thesis relates to a class of emergent behavior based systems known as swarm intelligence systems, i.e. the algorithm is potentially efficient, adaptive and robust.</p><p>On the contrary to other related swarm intelligence algorithms, the algorithm presented has a thorough formal foundation. This enables a better understanding of the algorithm’s potentials and limitations, and hence enables better adaptation of the algorithm to new problem areas without loss of efficiency, adaptability or robustness. The formal foundations are based on work by Reuven Rubinstein on cross entropy driven optimization. The transition from Ruinstein’s centralized and synchronous algorithm to a distributed and asynchronous algorithm is described, and the distributed algorithm’s ability to solve complex problems (NP-complete) efficiently is demonstrated.</p><p>Four examples of how the distributed algorithm may be applied in a network management context are presented. A system for finding near optimal patterns of primary/backup paths together with a system for finding cyclic protection paths in mesh networks demonstrate the algorithm’s ability to act as a tool helping management system to ensure quality of service. The algorithm’s potential as a management policy implementation mechanism is also demonstrated. The algorithm’s adaptability is shown to enable resolution of policy conflicts in a soft manner causing as little loss as possible. Finally, the algorithm’s ability to find near optimal paths (i.e. sequences) of resources in networks of large scale is demonstrated.</p>

Network and system management has always been of concern for telecommunication and computer system operators. The need for standardization was recognised already 20 years ago, hence several standards for network management exist today. However, the ever-increasing number of units connected to networks and the ever-increasing number of services being provided results in significant increased complexity of average network environments. This challenges current management systems. In addition to the general increase in complexity the trend among network owners and operators of merging several single service networks into larger, heterogeneous and complex full service networks challenges current management systems even further. The full service networks will require management systems more powerful than what is possible to realize basing systems purely on todays management standards. This thesis presents a distributed stochastic optimization algorithm which enables implementations of highly robust and efficient management tools. These tools may be integrated into management systems and potentially make the systems more powerful and better prepared for management of full service networks. Emergent behavior is common in nature and easily observable in colonies of social insects and animals. Even an old oak tree can be viewed as an emergent system with its collection of interacting cells. Characteristic for any emergent system is how the overall behavior of the system emerge from many relatively simple, restricted behaviors interacting, e.g. a thousand ants building a trail, a flock of birds flying south or millions of cells making a tree grow. No centralized control exist, i.e. no single unit is in charge making global decisions. Despite distributed control, high work redundancy and stochastic behavior components, emergent systems tend to be very efficient problem solvers. In fact emergent systems tend to be both efficient, adaptive and robust which are three properties indeed desirable for a network management system. The algorithm presented in this thesis relates to a class of emergent behavior based systems known as swarm intelligence systems, i.e. the algorithm is potentially efficient, adaptive and robust. On the contrary to other related swarm intelligence algorithms, the algorithm presented has a thorough formal foundation. This enables a better understanding of the algorithm’s potentials and limitations, and hence enables better adaptation of the algorithm to new problem areas without loss of efficiency, adaptability or robustness. The formal foundations are based on work by Reuven Rubinstein on cross entropy driven optimization. The transition from Ruinstein’s centralized and synchronous algorithm to a distributed and asynchronous algorithm is described, and the distributed algorithm’s ability to solve complex problems (NP-complete) efficiently is demonstrated. Four examples of how the distributed algorithm may be applied in a network management context are presented. A system for finding near optimal patterns of primary/backup paths together with a system for finding cyclic protection paths in mesh networks demonstrate the algorithm’s ability to act as a tool helping management system to ensure quality of service. The algorithm’s potential as a management policy implementation mechanism is also demonstrated. The algorithm’s adaptability is shown to enable resolution of policy conflicts in a soft manner causing as little loss as possible. Finally, the algorithm’s ability to find near optimal paths (i.e. sequences) of resources in networks of large scale is demonstrated.

Made available in DSpace on 2016-04-18T21:39:48Z (GMT). No. of bitstreams: 3 Lia Carrari Rodrigues1.pdf: 2007869 bytes, checksum: 5127705a8183cb3056356f8cba16af6a (MD5) Lia Carrari Rodrigues2.pdf: 1875473 bytes, checksum: 48cfbdbc52e6db38b63fd8d1622c69ed (MD5) Lia Carrari Rodrigues3.pdf: 2987315 bytes, checksum: 7dacd97c56a6b31303f12c62c9657e92 (MD5) Previous issue date: 2009-02-11 / Fundo Mackenzie de Pesquisa / The current worldwide popularity of on-line games has resulted in the formation of virtual communities with hundreds of people. This is due to the daily interaction of people in games called Massive Multiplayer Online Role-Playing Games (MMORPGs). These communities are culturally diverse and permeated by social ties estabilished through different ways in the game s virtual world. The present research held a study on the communities found in World of Warcraft through social network analysis. The goal of this approach was to define a typology of social ties and study the behavioural patterns related to the structure of these networks. This involved the construction of an efficient data collecting system, as well as analysis tools. That particular methodology verified that this kind of organization can be characterized as an emergent adaptive complex system. To that end, different theories were utilized, such as graph theory, Kohonen networks algebra and software engineering. / Atualmente a popularidade mundial de jogos on-line tem resultado na formação de comunidades virtuais com centenas de pessoas. Isso se deve à interação diária das pessoas em jogos chamados Massive Multiplayer Online Role-Playing Games (MMORPGs). Estas comunidades são culturalmente diversificadas e permeadas por laços sociais estabelecidos de diferentes maneiras no ambiente virtual do jogo. A presente pesquisa realizou um estudo de comunidades do jogo World of Warcraft por meio da abordagem da análise de redes sociais. O intuito desta abordagem foi definir uma tipologia de laços sociais e estudar padrões de comportamento vinculados à estrutura destas. Isso envolveu a construção de um sistema de coleta de dados eficiente desta rede, assim como ferramentas de análise. Com esta metodologia, verificou-se que este tipo de organização pode ser caracterizada como um sistema complexo adaptativo emergente. Para isso, foram utilizadas diferentes teorias, como a teoria dos grafos, redes de Kohonen, álgebra e engenharia de software.