Spelling suggestions: "subject:"distributed scheduling"" "subject:"eistributed scheduling""
1 |
SQ-CSMA : universally lowering the delay of queue-based CSMA/CAGanesh, Rajaganesh 1987- 14 October 2014 (has links)
Recent works show that, by incorporating queue length information, CSMA/CA multiple access protocols can achieve maximum throughput in general ad-hoc wireless networks. In all of these protocols, the aggressiveness with which a link attempts to grab the channel is governed solely by its own queue, and is independent of the queues of other interfering links. While this independence allows for minimal control signaling, it results in schedules that change very slowly. This causes starvation and delays - especially at moderate to high loads. In this work we add a very small amount of signaling - an occasional few bits between interfering links. These bits allow us a new functionality: switching - a link can now turn off its interfering links with a certain probability. The challenge is ensuring maximum throughput and lower delay via the use of this new functionality. We develop a new protocol - Switch-enabled Queue-based CSMA (SQ-CSMA) - that uses switching to achieve both of these objectives. This simple additional functionality, and our protocol to leverage it, can be “added on'' to every existing CSMA/CA protocol that uses queue lengths. Interestingly, we see that in every case it has a significant positive impact on delay, universally furthering the performance of existing protocols. / text
|
2 |
Hard Real Time guarantees using Switched Ethernet and distributed scheduling (EDF)KinShe, Kam, Bhavani Chandrasekhar, Kondreddi January 2006 (has links)
<p>Ethernet technology is being accepted by industrial community due to its open standardization </p><p>and low cost. To meet the requirements of industrial applications, a switched Ethernet </p><p>network with hard real time guarantees using relative deadlines is presented as a first step to </p><p>verify the functionality. The goal of the project was primarily to implement a real-time </p><p>switched Ethernet with EDF (Earliest Deadline First) scheduling algorithm. </p><p>In this project, the function simulations of real-time switched Ethernet with distributed control </p><p>software have been implemented, by using a standard switch with priority-queues and the </p><p>distributed software, as well as EDF-scheduled TDMA (Time Division Medium Access). The </p><p>network topology is the star type. There is no extra hardware added into the switch and the </p><p>nodes. All functions are implemented by software and the setting in the switch. </p><p>The project focuses on hard real-time service guarantees but soft real-time traffic and non </p><p>real-time traffic, as well as real time administration are also taken into the consideration. </p><p>Our simulations show that 100 percent of the network usage could be scheduled and the result </p><p>of deterministic real-time properties of the system are achieved as expected.</p>
|
3 |
Beyond Interference Avoidance: Distributed Sun-network Scheduling in Wireless Networks with Local ViewsSantacruz, Pedro 16 September 2013 (has links)
In most wireless networks, nodes have only limited local information about the state of the network, which includes connectivity and channel state information. With limited local information about the network, each node’s knowledge is mismatched; therefore, they must make distributed decisions. In this thesis, we pose the following question - if every node has network state information only about a small neighborhood, how and when should nodes choose to transmit? While link scheduling answers the above question for point-to-point physical layers which are designed for an interference-avoidance paradigm, we look for answers in cases when interference can be embraced by advanced code design, as suggested by results in network information theory.
To make progress on this challenging problem, we propose two constructive distributed algorithms, one conservative and one aggressive, which achieve rates higher than link scheduling based on interference avoidance, especially if each node knows more than one hop of network state information. Both algorithms schedule sub-networks such that each sub-network can employ advanced interference-embracing coding schemes to achieve higher rates. Our innovation is in the identification, selection and scheduling of sub-networks, especially when sub-networks are larger than a single link.
Using normalized sum-rate as the metric of network performance, we prove that the proposed conservative sub-network scheduling algorithm is guaranteed to have performance greater than or equal to pure coloring-based link scheduling. In addition, the proposed aggressive sub-network scheduling algorithm is shown, through simulations, to achieve better normalized sum-rate than the conservative algorithm for several network classes. Our results highlight the advantages of extending the design space of possible scheduling strategies to include those that leverage local network information.
|
4 |
Hard Real Time guarantees using Switched Ethernet and distributed scheduling (EDF)KinShe, Kam, Bhavani Chandrasekhar, Kondreddi January 2006 (has links)
Ethernet technology is being accepted by industrial community due to its open standardization and low cost. To meet the requirements of industrial applications, a switched Ethernet network with hard real time guarantees using relative deadlines is presented as a first step to verify the functionality. The goal of the project was primarily to implement a real-time switched Ethernet with EDF (Earliest Deadline First) scheduling algorithm. In this project, the function simulations of real-time switched Ethernet with distributed control software have been implemented, by using a standard switch with priority-queues and the distributed software, as well as EDF-scheduled TDMA (Time Division Medium Access). The network topology is the star type. There is no extra hardware added into the switch and the nodes. All functions are implemented by software and the setting in the switch. The project focuses on hard real-time service guarantees but soft real-time traffic and non real-time traffic, as well as real time administration are also taken into the consideration. Our simulations show that 100 percent of the network usage could be scheduled and the result of deterministic real-time properties of the system are achieved as expected.
|
5 |
Solving the Distributed Constraint Satisfaction Problem for Cooperative Supply Chains Using Multi-agent SystemsKuo, Hui-chun 23 July 2004 (has links)
Facing global and dynamic competition environment, companies have to collaborate with other companies instead of struggle alone to optimize performance of supply chain. In a distributed supply chain structure, it is an important issue for companies to coordinate seamlessly to effectively fulfill customer orders. In this thesis, we seek to propose a fast and flexible method to solve the order fulfillment scheduling conflicts among partners in a supply chain.
Due to the risk of exposing trade secrets and the cost of gathering information, the centralized constraint satisfaction mechanism is infeasible to handle distributed scheduling problem in real world environment. Moreover, the distributed constraints satisfaction model just focuses on finding a globally executable order fulfillment schedule. Therefore, we propose an agent-based distributed coordination mechanism that integrates negotiation with generic algorithm. We chose the mold manufacturing industry as an example and conducted experiments to evaluate the performance of the proposed mechanism and to compare with other benchmark methods proposed by researchers prior to this study. The experimental results indicate that the distributed coordination mechanism we proposed is a feasible approach to solve the order fulfillment scheduling conflicts in outsourcing activities in a supply chain.
|
6 |
Development Of A Bidding Algorithm Used In An Agent-based Shop-floor Control SystemUluer, Muhtar Ural 01 January 2007 (has links) (PDF)
In this study a time based bidding framework is developed which is used for dispatching jobs to manufacturing resources in a virtual shop-floor environment. Agent-based shop-floor control approach is implemented with machine and part agents. The Contract-net communication protocol is utilized as the negotiation scheme between these agents. Single step product reservation (SSPR) technique is adopted throughout the study. Primary objective is determined as meeting the due dates and if the lateness is inevitable, avoiding the parts of high priority from being late. A balanced machine utilization rate is set as the secondary objective.
During bid construction step, the SSPR technique is augmented with W(SPT+CR) sequencing rule in order to obtain weighted tardiness results. Bids containing Earliest Finishing Time (EFT) and machine loading values of the corresponding machine are evaluated with considering the priority of the part. An elimination algorithm which discards the highly deviated bids having obvious differences is implemented at the initial stage of the bid evaluation step. A basic algorithm to control the maximum tardiness value is applied, as well.
A simulation test bed is developed in order to implement the time concept into the presented bidding framework. The test bed is mainly based on the Computer Integrated Manufacturing Laboratory (CIMLAB) located in Middle East Technical University, Department of Mechanical Engineering.
The developed bidding algorithm is tested under several cases. Results revealed that the proposed bidding framework was quite successful in meeting the objectives. The study is concluded with some specific future work, outlined in the light of the results obtained.
|
7 |
ssIoTa: A system software framework for the internet of thingsLillethun, David 08 June 2015 (has links)
Sensors are widely deployed in our environment, and their number is increasing rapidly. In the near future, billions of devices will all be connected to each other, creating an Internet of Things. Furthermore, computational intelligence is needed to make applications involving these devices truly exciting. In IoT, however, the vast amounts of data will not be statically prepared for batch processing, but rather continually produced and streamed live to data consumers and intelligent algorithms. We refer to applications that perform live analysis on live data streams, bringing intelligence to IoT, as the Analysis of Things.
However, the Analysis of Things also comes with a new set of challenges.
The data sources are not collected in a single, centralized location, but rather distributed widely across the environment. AoT applications need to be able to access (consume, produce, and share with each other) this data in a way that is natural considering its live streaming nature. The data transport mechanism must also allow easy access to sensors, actuators, and analysis results. Furthermore, analysis applications require computational resources on which to run. We claim that system support for AoT can reduce the complexity of developing and executing such applications.
To address this, we make the following contributions:
- A framework for systems support of Live Streaming Analysis in the Internet of Things, which we refer to as the Analysis of Things (AoT), including a set of requirements for system design
- A system implementation that validates the framework by supporting Analysis of Things applications at a local scale, and a design for a federated system that supports AoT on a wide geographical scale
- An empirical system evaluation that validates the system design and implementation, including simulation experiments across a wide-area distributed system
We present five broad requirements for the Analysis of Things and discuss one set of specific system support features that can satisfy these requirements. We have implemented a system, called \textsubscript{SS}IoTa, that implements these features and supports AoT applications running on local resources. The programming model for the system allows applications to be specified simply as operator graphs, by connecting operator inputs to operator outputs and sensor streams. Operators are code components that run arbitrary continuous analysis algorithms on streaming data. By conforming to a provided interface, operators may be developed that can be composed into operator graphs and executed by the system. The system consists of an Execution Environment, in which a Resource Manager manages the available computational resources and the applications running on them, a Stream Registry, in which available data streams can be registered so that they may be discovered and used by applications, and an Operator Store, which serves as a repository for operator code so that components can be shared and reused. Experimental results for the system implementation validate its performance.
Many applications are also widely distributed across a geographic area. To support such applications, \textsubscript{SS}IoTa must be able to run them on infrastructure resources that are also distributed widely. We have designed a system that does so by federating each of the three system components: Operator Store, Stream Registry, and Resource Manager. The Operator Store is distributed using a distributed hast table (DHT), however since temporal locality can be expected and data churn is low, caching may be employed to further improve performance. Since sensors exist at particular locations in physical space, queries on the Stream Registry will be based on location. We also introduce the concept of geographical locality. Therefore, range queries in two dimensions must be supported by the federated Stream Registry, while taking advantage of geographical locality for improved average-case performance. To accomplish these goals, we present a design sketch for SkipCAN, a modification of the SkipNet and Content Addressable Network DHTs. Finally, the fundamental issue in the federated Resource Manager is how to distributed the operators of multiple applications across the geographically distributed sites where computational resources can execute them. To address this, we introduce DistAl, a fully distributed algorithm that assigns operators to sites. DistAl also respects the system resource constraints and application preferences for performance and quality of results (QoR), using application-specific utility functions to allow applications to express their preferences. DistAl is validated by simulation results.
|
8 |
Uma abordagem de predição da dinâmica comportamental de processos para prover autonomia a ambientes distribuídos / An approach to provide autonomy to distributed environments by predicting the dynamics of process behaviorDodonov, Evgueni 01 July 2009 (has links)
A evolução de sistemas distribuídos resultou em aumento significativo de complexidade para manutenção e gerenciamento, tornando pouco eficientes técnicas convencionais baseadas em intervenções manuais. Isso motivou pesquisas que deram origem ao paradigma de computação autônoma (Autonomic Computing), que provê aspectos de auto-configuração, auto-recuperação, auto-otimização e auto-proteção a fim de tornar sistemas auto-gerenciáveis. Nesse contexto, esta tese teve como objetivo prover autonomia a ambientes distribuídos, sem a necessidade de mudar o paradigma de programação e as aplicações de usuários. Para isso, propôs-se uma abordagem que emprega técnicas para compreensão e predição de dinâmicas comportamentais de processos, utilizando abordagens de sistemas dinâmicos, inteligência artificial e teoria do caos. Os estudos realizados no decorrer desta pesquisa demonstraram que, ao predizer padrões comportamentais, pode-se otimizar diversos aspectos de computação distribuída, suportando tomadas de decisão autônomas pelos ambientes. Para validar a abordagem proposta, foi desenvolvida uma política de escalonamento distribuído, denominada PredRoute, a qual utiliza o conhecimento sobre o comportamento de processos para otimizar, transparentemente, a alocação de recursos. Experimentos realizados demonstraram que essa política aumenta o desempenho em até 4 ordens de grandeza e apresenta baixo custo computacional, o que permite a sua adoção para escalonamento online de processos / The evolution of distributed systems resulted in a significant growth in management and support complexities, which uncovered the inefficiencies incurred by the usage of conventional management techniques, based in manual interventions. This, therefore, has motivated researches towards the concept of Autonomic Computing, which provides aspects of self-configuration, self-healing, self-optimization and self-protection, aiming at developing computer systems capable of self-management. In this context, this thesis was conceived with the goal of providing autonomy to distributed systems, without changing the programming paradigm or user applications. In order to reach this goal, we proposed an approach which employs techniques capable of modelling and predicting the dynamics of application behavior, using concepts introduced in dynamical systems, artificial intelligence, and chaos theory. The obtained results demonstrated that it is possible to optimize several aspects of distributed computing, providing support for autonomic computing capabilities to distributed environments. In order to validate the proposed approach, a distributed scheduling policy was developed, named PredRoute, which uses the knowledge about the process behavior to transparently optimize the resource allocation. Experimental results demonstrated that this policy can improve the system performance by up to a power of 4, and also requires a considerably low computational cost, which suggests its adoption for online process scheduling in distributed environments
|
9 |
Optimisation des flux logistiques : vers une gestion avancée de la situation de crise / Optimization of logistics flows : towards an advanced crisis management supply chainKaddoussi, Aida 26 November 2012 (has links)
La logistique de gestion de crise fait de plus en plus parler d’elle. En effet, que ce soit au sujet de conflits géopolitiques ou de catastrophes naturelles, ou encore lorsqu’il s’agit d’urgences de proximité, on ne peut plus passer à côté de la gestion de crise pour faire face à des faits internationaux ou nationaux. La logistique de gestion de crise œuvre pour que les secours soient optimisés et que l’aide et le ravitaillement en nourriture, eau, médicaments, soit apportés rapidement aux zones sinistrées. Les travaux de recherche présentés dans cette thèse, dans le cadre d’une coopération avec le département logistique d’EADS, visent à apporter une réponse à ces défis. Nous présentons, dans ce contexte, des solutions basées sur une approche de modélisation, optimisation et simulation orientée agents de flux logistiques. Les problèmes de gestion de flux abordés nous ont permis d’étudier et développer trois volets d’investigation : un module d’aide au positionnement des zones logistiques qui permet de minimiser les distances entre les zones et d’optimiser leurs nombre et ce pour une meilleure circulation des flux, une approche innovante pour l’ordonnancement distribué des tâches de livraison qui permet d’apporter une solution à un problème de gestion des flux fortement distribué, et finalement un agent holonique qui permet de fournir une estimation de la consommation à venir d’un site logistique, en alliant l’expertise des logisticiens aux modèles à base de logique floue. Pour démontrer l’efficacité des approches utilisées, un démonstrateur baptisé OBAC (Optimisation à Base d’Agents Communicants) a été réalisé, intégrant toutes ces approches et applications militaires / Nowadays, crisis management logistics is facing new challenges. Indeed, geopolitical conflicts, natural disasters or emergencies can cause big damages and so require rapid and effective response. Due to their sudden occurrence, we are countering a high disturbances context: a Crisis Management Supply Chain (CMSC). Working in such an uncertain environment incites to be equipped with optimization and cooperation mechanisms assuring all the chain actors satisfaction, while acting in a collective way to reach a common objective: the crisis management.In this thesis, we focus on the definition of a modeling approach and an agent-based simulation of the Crisis Management Supply Chain. We propose a decision support system that deals with three problems: the optimal positioning of logistics zones to facilitate the flows circulation, an innovative method for solving a highly-distributed delivery scheduling problem, based on a multi-agent system, for the distribution of relief materials (food, water, clothes, etc.) to the areas affected by the disaster, and finally a need estimating agent to give an accurate forecast of resources’ consumption in the logistic zones. Blending the agent paradigm with the optimization technics helped reach our goals of implementing a large-scale decision support system. The simulation results highlight our contributions
|
10 |
Uma abordagem de predição da dinâmica comportamental de processos para prover autonomia a ambientes distribuídos / An approach to provide autonomy to distributed environments by predicting the dynamics of process behaviorEvgueni Dodonov 01 July 2009 (has links)
A evolução de sistemas distribuídos resultou em aumento significativo de complexidade para manutenção e gerenciamento, tornando pouco eficientes técnicas convencionais baseadas em intervenções manuais. Isso motivou pesquisas que deram origem ao paradigma de computação autônoma (Autonomic Computing), que provê aspectos de auto-configuração, auto-recuperação, auto-otimização e auto-proteção a fim de tornar sistemas auto-gerenciáveis. Nesse contexto, esta tese teve como objetivo prover autonomia a ambientes distribuídos, sem a necessidade de mudar o paradigma de programação e as aplicações de usuários. Para isso, propôs-se uma abordagem que emprega técnicas para compreensão e predição de dinâmicas comportamentais de processos, utilizando abordagens de sistemas dinâmicos, inteligência artificial e teoria do caos. Os estudos realizados no decorrer desta pesquisa demonstraram que, ao predizer padrões comportamentais, pode-se otimizar diversos aspectos de computação distribuída, suportando tomadas de decisão autônomas pelos ambientes. Para validar a abordagem proposta, foi desenvolvida uma política de escalonamento distribuído, denominada PredRoute, a qual utiliza o conhecimento sobre o comportamento de processos para otimizar, transparentemente, a alocação de recursos. Experimentos realizados demonstraram que essa política aumenta o desempenho em até 4 ordens de grandeza e apresenta baixo custo computacional, o que permite a sua adoção para escalonamento online de processos / The evolution of distributed systems resulted in a significant growth in management and support complexities, which uncovered the inefficiencies incurred by the usage of conventional management techniques, based in manual interventions. This, therefore, has motivated researches towards the concept of Autonomic Computing, which provides aspects of self-configuration, self-healing, self-optimization and self-protection, aiming at developing computer systems capable of self-management. In this context, this thesis was conceived with the goal of providing autonomy to distributed systems, without changing the programming paradigm or user applications. In order to reach this goal, we proposed an approach which employs techniques capable of modelling and predicting the dynamics of application behavior, using concepts introduced in dynamical systems, artificial intelligence, and chaos theory. The obtained results demonstrated that it is possible to optimize several aspects of distributed computing, providing support for autonomic computing capabilities to distributed environments. In order to validate the proposed approach, a distributed scheduling policy was developed, named PredRoute, which uses the knowledge about the process behavior to transparently optimize the resource allocation. Experimental results demonstrated that this policy can improve the system performance by up to a power of 4, and also requires a considerably low computational cost, which suggests its adoption for online process scheduling in distributed environments
|
Page generated in 0.1136 seconds