Approximate product-forms and reversed processes for performance analysis (APROPOS)

用于性能分析的近似产品形式和逆向过程 (APROPOS)

基本信息

批准号：
EP/I030921/1
负责人：
Peter Harrison
金额：
$ 42.68万
依托单位：
Imperial College London
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2012
资助国家：
英国
起止时间：
2012 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FI030921%2F1
关键词：
Approximate product forms reversed processes

项目摘要

The need for models in the quantitative design of complex computer and communicaton systems is indisputable but their construction is hampered by the lack of a uniform methodology for building large models from smaller component-models - mirroring the design process of the systems themselves. Various specific, often ad hoc, techniques have been developed over the last four decades in response to contemporary design features, beginning with queueing networks that modeled multiprogrammed mainframe systems through to network-calculus descriptions of mobile networks and stochastic models of telecommunication systems and the internet. Unfortunately, such models are prone to exponential (or higher) growth in computational complexity, a phenomenon often referred to as state-space explosion .The present proposal aims to provide techniques and tools for deriving efficient, mainly approximate, solutions to models of modern networks. As in almost all analyses of such complex systems, the aim is to find separable solutions, which allow subsystems (components) to be solved separately and their solutions to then be combined in a simple way. More specifically, we propose to develop the recent significant results obtained by the proposer and Dr Andrea Marin through a three-year project supporting Marin as the RA. The said results have led to a number of research and tutorial papers that have been accepted and/or presented at the highest quality international venues in our research area. It is the proposer's view that the research is at a knee in an upward curve and the opportunity to work directly with a rising-star such as Marin is one not to be missed if at all possible; in addition to the above papers and tutorials, Marin has won best paper awards at two international conferences for his work in this area in the last 12 months. Furthermore, the presentation at Sigmetrics 2010 in New York was well received and led to several discussions with leading international researchers and plans for specific collaboration - see the Case for Support. The theoretical research proposed will supplement existing analytical techniques, such as queueing network modeling (QNM), which are still relevant but are lacking in expressive power for modeling today's systems. For example, Stochastic Petri Nets (SPNs) are suitable for describing virtual resource systems, as used in cloud computing for example, which is not the case for standard queueing networks. Similarly, (non-standard) networks with batch movements are important in models of energy-efficient systems (see the Case for Support), but in general do not have separable (or other efficient) solutions; preliminary results relating to this will be presented as a poster at Performance'10 in November. Last, optimisation is facilitated by the ability of our unique approach, using the Reversed Compound Agent Theorem (RCAT), to perturb specifications so as to create separable solutions, admitting the possibility of searching for a best-fit product-form solution.Based on these theoretical and practical developments, the first objective of the proposed project is to enhance the RCAT-approach to product-forms and semi-product-forms for application in models with SPN specifications and in networks with batch-movements. Perhaps even more importantly, the probability density function of the response time of tasks in passing along a path will be investigated in a new class of networks; preliminary results have already been obtained and will also be presented in the aforementioned poster. This work is a substantial advance on established approaches, such as Boxma and Daduna's as well as that of the proposed PI previously. We believe that three years of uninterrupted collaboration between the proposer and Marin in the AESOP research group will attain the goals summarised above and listed under Objectives .

复杂计算机和通信系统的定量设计中对模型的需求是无可争议的，但由于缺乏从较小的组件模型构建大型模型（反映系统本身的设计过程）的统一方法，模型的构建受到阻碍。在过去的四十年中，为了响应当代的设计特征，开发了各种特定的（通常是临时的）技术，从建模多程序大型机系统的排队网络到移动网络的网络演算描述以及电信系统和互联网的随机模型。不幸的是，此类模型的计算复杂度容易呈指数（或更高）增长，这种现象通常被称为状态空间爆炸。本提案旨在提供技术和工具，用于导出现代网络模型的高效（主要是近似）解决方案。与此类复杂系统的几乎所有分析一样，目标是找到可分离的解决方案，从而允许单独求解子系统（组件），然后以简单的方式组合它们的解决方案。更具体地说，我们建议通过支持 Marin 作为 RA 的三年项目来发展提案者和 Andrea Marin 博士最近取得的重大成果。上述结果催生了许多研究和教程论文，这些论文已被接受和/或在我们研究领域的最高质量的国际场所发表。提议者认为，这项研究正处于上升曲线的拐点，如果可能的话，与马林这样的后起之秀直接合作的机会是不容错过的；除了上述论文和教程之外，Marin 在过去 12 个月内还因其在该领域的工作而在两次国际会议上获得了最佳论文奖。此外，在纽约 Sigmetrics 2010 上的演讲受到好评，并引发了与国际领先研究人员的多次讨论以及具体合作计划 - 请参阅支持案例。所提出的理论研究将补充现有的分析技术，例如排队网络建模（QNM），这些技术仍然相关，但缺乏对当今系统建模的表达能力。例如，随机 Petri 网 (SPN) 适合描述虚拟资源系统，例如云计算中使用的虚拟资源系统，而标准排队网络则不然。同样，具有批量移动的（非标准）网络在节能系统模型中很重要（请参阅支持案例），但通常没有可分离的（或其他有效的）解决方案；与此相关的初步结果将在 11 月的 Performance'10 上以海报形式展示。最后，我们独特的方法能够促进优化，即使用逆向复合代理定理 (RCAT) 来扰乱规范，从而创建可分离的解决方案，从而允许搜索最适合的产品形式解决方案。鉴于这些理论和实践的发展，拟议项目的首要目标是增强产品形式和半产品形式的 RCAT 方法，以便在具有 SPN 规范的模型和具有批量移动的网络中应用。也许更重要的是，将在一类新的网络中研究沿着路径传递的任务响应时间的概率密度函数；初步结果已经获得，也将在上述海报中展示。这项工作是对 Boxma 和 Daduna 以及之前提出的 PI 等既定方法的重大进步。我们相信，提案者和 Marin 在 AESOP 研究小组三年不间断的合作将实现上面概述和目标中列出的目标。