Apresenta-se um framework que permite a caracterização, conformação e escalonamento de todas as categorias de serviços A TM, dentro do ambiente de usuário (CEP). Propõem-se um modelo de tráfego otimizado para este ambiente que oferece condições de garantias de QoS individuais para fluxos VBR, tempo real ou não, CBR, ABR e UBR. O modelo proposto, denominado de PCSTS (priority class services traffic shaping), inclui um módulo que permite a obtenção do descritor de tráfego de fluxos desconhecidos. Os fluxos são conformados de forma individual, e em tempo real, segundo um conformador baseado num algoritmo de escalonamento virtual duplo baseado no GCRA do ITU/ ATM Forum. Para a multiplexação dinâmica dos diferentes fluxos do ambiente de usuário, no enlace de acesso, é proposto um algoritmo de escalonamento EDD, modificado através de um sinal de realimentação entre conformador e escalonador, e desta forma tem-se condições de oferecer garantias de limite de atraso e jitter para fluxos individuais de serviços rt-VBR ou nrt-VBR. São apresentadas simulações, tanto da caracterização dos fluxos desconhecidos como da arquitetura do escalonador, que comprovam o comportamento esperado do modelo de tráfego PCSTS. / We present a framework that enhances the characterization, shaping and scheduling of ATM traffic flows for ali ATM service categories in the customer prernise equipment (CPE) environment. We propose an optirnized traffic model, capable to guarantee QoS parameters at per connection levei for VBR services, real time or not, CBR, ABR and UBR services. The model proposed, narned PCSTS (priority classes services traffic shaping), includes a module that performs the characterization of services with unknown traffic descriptor. The flows are shaped individually, in real time, through a shaper based on the double discrete time scheduling algorithm of the GCRA from ITU/ ATM Forum. For the dynarnic multiplexing of the different service flows , at the link levei, a modified EDD scheduling algorithm is proposed with a feedback signal between the scheduling and shaping modules. As a result, it is demonstrated that it is possible to grant jitter and delay bounds for the rt-VBR and nrt-VBR services. We present simulations of the traffic characterization module and of the scheduling architecture, for different services, which confirms the expected behavior of the PCSTS model.

Apresenta-se um framework que permite a caracterização, conformação e escalonamento de todas as categorias de serviços A TM, dentro do ambiente de usuário (CEP). Propõem-se um modelo de tráfego otimizado para este ambiente que oferece condições de garantias de QoS individuais para fluxos VBR, tempo real ou não, CBR, ABR e UBR. O modelo proposto, denominado de PCSTS (priority class services traffic shaping), inclui um módulo que permite a obtenção do descritor de tráfego de fluxos desconhecidos. Os fluxos são conformados de forma individual, e em tempo real, segundo um conformador baseado num algoritmo de escalonamento virtual duplo baseado no GCRA do ITU/ ATM Forum. Para a multiplexação dinâmica dos diferentes fluxos do ambiente de usuário, no enlace de acesso, é proposto um algoritmo de escalonamento EDD, modificado através de um sinal de realimentação entre conformador e escalonador, e desta forma tem-se condições de oferecer garantias de limite de atraso e jitter para fluxos individuais de serviços rt-VBR ou nrt-VBR. São apresentadas simulações, tanto da caracterização dos fluxos desconhecidos como da arquitetura do escalonador, que comprovam o comportamento esperado do modelo de tráfego PCSTS. / We present a framework that enhances the characterization, shaping and scheduling of ATM traffic flows for ali ATM service categories in the customer prernise equipment (CPE) environment. We propose an optirnized traffic model, capable to guarantee QoS parameters at per connection levei for VBR services, real time or not, CBR, ABR and UBR services. The model proposed, narned PCSTS (priority classes services traffic shaping), includes a module that performs the characterization of services with unknown traffic descriptor. The flows are shaped individually, in real time, through a shaper based on the double discrete time scheduling algorithm of the GCRA from ITU/ ATM Forum. For the dynarnic multiplexing of the different service flows , at the link levei, a modified EDD scheduling algorithm is proposed with a feedback signal between the scheduling and shaping modules. As a result, it is demonstrated that it is possible to grant jitter and delay bounds for the rt-VBR and nrt-VBR services. We present simulations of the traffic characterization module and of the scheduling architecture, for different services, which confirms the expected behavior of the PCSTS model.

隨著物聯網這個萬物連網的概念順勢推動智慧家庭在市場裡蓬勃發展，可預期未來ISP(Internet Service Provider)業者勢必面臨大量智慧家庭中各種不同應用服務互相競爭頻寬資源的情況，甚至遇到網路滿載壅塞時造成應用服務不堪使用的情形。 為改善上述問題，本文以ISP業者管理智慧家庭中眾多的物聯網設備為情境，透過軟體定義網路 (Software Defined Network，SDN)進行頻寬排程配置，排程演算法以可兼顧公平性(fairness)、時間延遲(delay)及應用服務優先權(service priority)的A-MLWDF (Adaptive Modified Largest Weighted Delay First) [7]演算法，確保優先配置頻寬給智慧家庭中優先權較高、時效較為急迫的流量，以降低應用服務的延遲來提升智慧家庭網路之服務品質(Quality of Service，QoS)。 本研究透過OMNet++模擬器建構SDN環境與傳統環境中有眾多物聯網設備之智慧家庭。家中物聯網設備包含M2M (Machine to Machine)和非M2M(non Machine to Machine)裝置，以提供各種智慧家庭應用服務。我們透過SDN架構進行頻寬配置，達到集中式管控家中的頻寬資源，其中排程演算法包括PF、MLWDF、A-MLWDF。實驗結果顯示，以上排程演算法雖然於SDN環境下在公平性與抖動率表現並不顯著，公平性約改善1.6%及抖動率約降低1%左右，但在產能與延遲方面表現較為顯著，能有效提高產能約52%，及降低延遲約 52%。 / With the concept of IoT (Internet of Things) spread rapidly, it is the opportunity to promote smart homes in the expanding market. We can see that the future ISP (Internet Service Provider) has to face a large number of smart homes having bandwidth competition in a variety of different applications and causing application services unavailable due to network congestion.     In order to resolve the above problems, we propose that each ISP (Internet Service Provider) has to manage a large number of IoT devices in a smart home to performs bandwidth scheduling through Software Defined Network (SDN). We choose to use A-MLWDF scheduling algorithm (Adaptive Modified Largest Weighted Delay First) [7] which considers fairness, delay and service priority. A-MLWDF is able to ensure services of higher priority and emergent traffic be allocated bandwidth earlier and greatly reduce delay and thus effectively enhance Quality of Service (QoS) of smart homes.     In this research, we implement a SDN environment by using OMNet++ to simulate the bandwidth competition among smart homes with IoT devices. The IoT devices consists of M2M (Machine to Machine) and non-M2M (non Machine to Machine) devices which offer a variety of intelligent home application services. We configure the bandwidth allocation under SDN control. The scheduling algorithms include PF, MLWDF and A-MLWDF. When the network traffic is congested, SDN can significantly increase throughput and reduce latency compared to traditional network management. The experimental results show that above scheduling algorithms using SDN environment having no significant performance improvements in fairness and jitter. The fairness increases around 1.6% and the jitter reduces around 1%. However, it shows significant improvement on throughout and delay. The throughput increases around 52% and the delay reduces around 52%.

With the increasing complexity of the chip architecture design for meeting different application requirements, the corresponding instruction scheduler of high-level synthesis tool needs to solve complex scheduling problems. Dynamically Reconfigurable Resource Array (DRRA) is a novel architecture based on Coarse-Grained Reconfigurable Architecture (CGRA) on SiLago platform, the instruction scheduler of Vesyla-II, the dedicated High-Level Synthesis (HLS) tool targets for DRRA needs to schedule the specific instruction sets designed for Distributed Two-level Control System (D2LC). This kind of instruction has different lifetimes and is fully cooperative and persistent. Based on these features, the instruction scheduler needs to be applied to the scheduling algorithm under complex constraints. The previously existing naive algorithm shows poor scalability and low efficiency. This thesis attempts to design and implement a new scheduling algorithm to improve the performance of a constraint programming engine-based scheduler. The new scheduling algorithm is based on the heuristic method, the scheduler with this algorithm does the order prediction during the resource scheduling process. Besides, a test bench for meeting different instruction scheduling behavior is also designed, and the test bench could generate the maximum boundary of the schedule to do the performance profiling of the developed algorithm. Several experiments are performed to compare the proposed method against the previous naive algorithm. The execution time and quality of the result are crucial to determine which algorithm has better performance. The experiment result shows that the scheduler with a heuristic algorithm could reduce the execution time and have comparable schedule quality, and it could solve all the test cases, whilst the naive algorithm only can solve part of them. / Med den ökande komplexiteten hos chiparkitekturdesignen för att möta olika applikationskrav, måste motsvarande instruktionsschemaläggare för högnivåsyntesverktyg lösa komplexa schemaläggningsproblem. Dynamically Reconfigurable Resource Array (DRRA) är en ny arkitektur baserad på Coarse-Grained Reconfigurable Architecture (CGRA) på SiLago-plattformen, instruktionsschemaläggaren för Vesyla-II, de dedikerade High Level Synthesis (HLS) verktygsmålen för DRRA behöver för att schemalägga de specifika instruktionsuppsättningar designade för distribuerat tvånivåstyrsystem (D2LC). Denna typ av undervisning har olika livslängder och är helt samarbetsvillig och ihållande. Baserat på dessa funktioner måste instruktionsschemaläggaren appliceras på schemaläggningsalgoritmen under komplexa begränsningar. Den tidigare existerande naiva algoritmen visar dålig skalbarhet och låg effektivitet. Den här avhandlingen försöker designa och implementera en ny schemaläggningsalgoritm för att förbättra prestandan hos en schemaläggare som är baserad på begränsningsprogrammeringsmotorer. Den nya schemaläggningsalgoritmen är baserad på den heuristiska metoden, schemaläggaren med denna algoritm gör ordningsförutsägelsen under resursschemaläggningsprocessen. Dessutom är en testbänk för att möta olika instruktionsschemaläggningsbeteenden också utformad, och testbänken kan generera den maximala gränsen för schemat för att göra prestandaprofileringen av den utvecklade algoritmen. Flera experiment utförs för att jämföra den föreslagna metoden mot den tidigare naiva algoritmen. Exekveringstiden och kvaliteten på resultatet är avgörande för att avgöra vilken algoritm som har bättre prestanda. Experimentresultatet visar att schemaläggaren med en heuristisk algoritm kan minska exekveringstiden och ha jämförbar schemakvalitet, och den kan lösa alla testfall, medan den naiva algoritmen bara kan lösa en del av dem.

The Electric/Electronic architecture of vehicle becomes more complex and costly, self-adaption can reduce the system, enhance the adaptive meanwhile reduce energy consumption and costs. The self-adaption needs the cooperation of both hardware and software reconfigurations, such that after the software is reconfigured the automotive network continues to fulfill the time constraints for time-critical applications. The thesis focuses on the real-time network reconfiguration. It uses EAST-ADL to model a real-time automotive system with timing events and constraints, which conforms to AUTOSAR timing extensions. The network media access is analyzed based on the model and a scheduling algorithm is developed. Then the concept is implemented by a use case, which is transformed from an EAST-ADL model to an executable simulation.

The Electric/Electronic architecture of vehicle becomes more complex and costly, self-adaption can reduce the system, enhance the adaptive meanwhile reduce energy consumption and costs. The self-adaption needs the cooperation of both hardware and software reconfigurations, such that after the software is reconfigured the automotive network continues to fulfill the time constraints for time-critical applications. The thesis focuses on the real-time network reconfiguration. It uses EAST-ADL to model a real-time automotive system with timing events and constraints, which conforms to AUTOSAR timing extensions. The network media access is analyzed based on the model and a scheduling algorithm is developed. Then the concept is implemented by a use case, which is transformed from an EAST-ADL model to an executable simulation.:1. Introduction 2. Research Fundamentals 2.1. AUTOSAR Specifications for Modeling Function Communication 2.2. Media Access Control in Real-time Network 3. Function Communication Model and Determination of Network Configuration 3.1. Function Communication Model 3.2. Scheduling Algorithm for Media Access 4. Implementation of Communication Model and Plugin for Model Transformation 4.1. EAST-ADL Modeling Language 4.2. Implementation of Function Communication Model in EAST-ADL 4.3. Model Transformation Plugin and Simulation Tool Integration 5. Evaluation of the Function Communication Model 5.1. Use-Case Model for Evaluation 5.2. Time Values of Use-Case Model 5.3. Analysis and Evaluation of Simulation Result 6. Conclusion and Outlook 6.1. Conclusion of the Work 6.2. Outlook of the Future Work A. OMNeT++ Simulation Log B. EAST-ADL Model to Artop Model Mapping Bibliography Nomenclature

The central thesis of this dissertation is that by combining classical scheduling methodologies with those of inventory management and queueing theory we can better model, understand and solve complex real-world scheduling problems. In part II of this dissertation, we provide models of a realistic supply chain scheduling problem that capture both its combinatorial nature and its dependence on inventory availability. We present an extensive empirical evaluation of how well implementations of these models in commercially available software solve the problem. We are therefore able to address, within a specific problem, the need for scheduling to take into account related decision-making processes. In order to simultaneously deal with combinatorial and dynamic properties of real scheduling problems, in part III we propose to integrate queueing theory and deterministic scheduling. Firstly, by reviewing the queueing theory literature that deals with dynamic resource allocation and sequencing and outlining numerous future work directions, we build a strong foundation for the investigation of the integration of queueing theory and scheduling. Subsequently, we demonstrate that integration can take place on three levels: conceptual, theoretical and algorithmic. At the conceptual level, we combine concepts, ideas and problem settings from the two areas, showing that such combinations provide insights into the trade-off between long-run and short-run objectives. Next, we show that theoretical integration of queueing and scheduling can lead to long-run performance guarantees for scheduling algorithms that have previously been proved only for queueing policies. In particular, we are the first to prove, in two flow shop environments, the stability of a scheduling method that is based on the traditional scheduling literature and utilizes processing time information to make sequencing decisions. Finally, to address the algorithmic level of integration, we present, in an extensive future work chapter, one general approach for creating hybrid queueing/scheduling algorithms. To our knowledge, this dissertation is the first work that builds a framework for integrating queueing theory and scheduling. Motivated by characteristics of real problems, this dissertation takes a step toward extending scheduling research beyond traditional assumptions and addressing more realistic scheduling problems.

The central thesis of this dissertation is that by combining classical scheduling methodologies with those of inventory management and queueing theory we can better model, understand and solve complex real-world scheduling problems. In part II of this dissertation, we provide models of a realistic supply chain scheduling problem that capture both its combinatorial nature and its dependence on inventory availability. We present an extensive empirical evaluation of how well implementations of these models in commercially available software solve the problem. We are therefore able to address, within a specific problem, the need for scheduling to take into account related decision-making processes. In order to simultaneously deal with combinatorial and dynamic properties of real scheduling problems, in part III we propose to integrate queueing theory and deterministic scheduling. Firstly, by reviewing the queueing theory literature that deals with dynamic resource allocation and sequencing and outlining numerous future work directions, we build a strong foundation for the investigation of the integration of queueing theory and scheduling. Subsequently, we demonstrate that integration can take place on three levels: conceptual, theoretical and algorithmic. At the conceptual level, we combine concepts, ideas and problem settings from the two areas, showing that such combinations provide insights into the trade-off between long-run and short-run objectives. Next, we show that theoretical integration of queueing and scheduling can lead to long-run performance guarantees for scheduling algorithms that have previously been proved only for queueing policies. In particular, we are the first to prove, in two flow shop environments, the stability of a scheduling method that is based on the traditional scheduling literature and utilizes processing time information to make sequencing decisions. Finally, to address the algorithmic level of integration, we present, in an extensive future work chapter, one general approach for creating hybrid queueing/scheduling algorithms. To our knowledge, this dissertation is the first work that builds a framework for integrating queueing theory and scheduling. Motivated by characteristics of real problems, this dissertation takes a step toward extending scheduling research beyond traditional assumptions and addressing more realistic scheduling problems.