IPTV is now offered by several operators in Europe, US and Asia using broadcast video over private IP networks that are isolated from Internet. IPTV services rely ontransmission of live (real-time) video and/or stored video. Video on Demand (VoD)and Time-shifted TV are implemented by IP unicast and Broadcast TV (BTV) and Near video on demand are implemented by IP multicast. IPTV services require QoS guarantees and can tolerate no more than 10-6 packet loss probability, 200 ms delay, and 50 ms jitter. Low delay is essential for satisfactory trick mode performance(pause, resume,fast forward) for VoD, and fast channel change time for BTV. Internet Traffic Engineering (TE) is defined in RFC 3272 and involves both capacity management and traffic management. Capacity management includes capacityplanning, routing control, and resource management. Traffic management includes (1)nodal traffic control functions such as traffic conditioning, queue management, scheduling, and (2) other functions that regulate traffic flow through the network orthat arbitrate access to network resources. An IPTV network architecture includes multiple networks (core network, metronetwork, access network and home network) that connects devices (super head-end, video hub office, video serving office, home gateway, set-top box). Each IP router in the core and metro networks implements some queueing and packet scheduling mechanism at the output link controller. Popular schedulers in IP networks include Priority Queueing (PQ), Class-Based Weighted Fair Queueing (CBWFQ), and Low Latency Queueing (LLQ) which combines PQ and CBWFQ.The thesis analyzes several Packet Scheduling algorithms that can optimize the tradeoff between system capacity and end user performance for the traffic classes. Before in the simulator FIFO,PQ,GPS queueing methods were implemented inside. This thesis aims to implement the LLQ scheduler inside the simulator and to evaluate the performance of these packet schedulers. The simulator is provided by ErnstNordström and Simulator was built in Visual C++ 2008 environmentand tested and analyzed in MatLab 7.0 under windows VISTA.

This paper presents an implementation of a lottery scheduler, presented from design through debugging to performance testing. Desirable characteristics of a general purpose scheduler include low overhead, good overall system performance for a variety of process types, and fair scheduling behavior. Testing is performed, along with an analysis of the results measuring the lottery scheduler against these characteristics. Lottery scheduling is found to provide better than average control over the relative execution rates of processes. The results show that lottery scheduling functions as a good mechanism for sharing the CPU fairly between users that are competing for the resource. While the lottery scheduler proves to have several interesting properties, overall system performance suffers and does not compare favorably with the balanced performance afforded by the standard Linux kernel’s scheduler.

Magíster en Ingeniería de Redes de Comunicaciones / En la actualidad las necesidades de los usuarios obligan a que la red LTE adopte nuevos procedimientos para incrementar el desempeño del sistema. Para esto, los mecanismos de Scheduler juegan un papel importante ya que son los responsables de distribuir los recursos de radio entre los diferentes móviles tomando en cuenta entre otras circunstancias las condiciones del canal y los requerimientos de calidad de servicio. Existen varios estudios comparativos de los distintos métodos de Radio Resource Management (RRM) que analizan el desempeño de los distintos parámetros de los schedulers. En cambio, en este trabajo se tiene como objetivo principal el cuantificar los schedulers con un valor escalar que califique directamente la calidad del audio de una conversación con el desempeño de los schedulers en el sistema LTE. Este trabajo tiene como finalidad obtener el valor estimado del Mean Opinion Score (MOS) de los schedulers: RR, PF, FD-MT, TD-MT, TTA, FD-TBFQ, TD-TBFQ, PSS y CQA. Estos schedulers son simulados en NS-3 y mediante el software estadístico R se revisan los datos para presentar un análisis estadístico y de esta manera generar modelos paramétricos y no paramétricos que intenten capturar la tendencia de los nueve schedulers simulados. En cada Scheduler se obtienen dos valores de MOS. El primero en base a cálculos y modelos estadísticos desde la capa PHY hasta la capa IP, mientras el segundo se obtiene de la información proporcionada directamente por el Flow Monitor a nivel de aplicación. Los resultados obtenidos indican que los valores del MOS mediante el primer método es considerablemente más bajo comparado con el MOS obtenido del Flow Monitor. El primero se interpreta como el MOS del sistema, mientras el segundo se categoriza como el MOS de los terminales, los cuales por defecto poseen un búfer que proporciona mayor calidad de servicio, pero con mayor variación en el tiempo, comparados al MOS del sistema.

Dans cette thèse, nous nous intéressons au calcul d'ordonnanceurs pour les systèmes hybrides. En fait, nous considérons deux sous-classes des systèmes hybrides, les systèmes temps-réels où des tâches doivent se partager l'accès à une ressource commune, et les systèmes à commutations où un choix doit être fait sur les dynamiques à choisir en fonction d'objectifs à atteindre. Dans la première partie de cette thèse, nous nous intéressons aux problèmes d'ordonnancement et prenons comme étude de cas l'ordonnancement de tâches périodiques sur des architectures multiprocesseurs. Nous nous intéressons plus particulièrement à déterminer si l'on peut modifier certaines valeur des paramètres du système tout en respectant les contraintes temporelles sans changer d'ordonnanceur. La méthode inverse permet de prouver de manière formelle la robustesse des systèmes temporisés paramétriques. Nous introduisons une méthode de réduction du nombre d'états nécessaire à la vérification. Cette réduction nous permet de traîter des études de cas intéressantes telle que celle proposée par Astrium EADS pour le lanceur Ariane 6. Nous montrons également comment la Cartographie Comportementale, une extension de la méthode inverse, permet de trouver la zone de l'espace des paramètres où l'on a l'existence d'un ordonnancement satisfaisant les contraintes temporelles. Nous comparons cette approche avec une méthode analytique pour montrer l'intérêt de notre approche. Dans la seconde partie de cette thèse, nous nous intéressons au contrôle de systèmes affines à commutation. Ces systèmes sont gouvernés par une famille d'équations différentielles linéaires et le contrôleur peut choisir laquelle va gouverner le système pendant le prochain pas de temps. Dans ce cadre, le contrôle peut être vu comme l'ordonnancement des dynamiques que le système va prendre. Le choix de la dynamique peut se faire pour des objectifs de stabilité ou d'accessibilité. Nous proposons une nouvelle méthode qui calcule un contrôleur dont la stratégie est la même pour des ensembles denses de points. Notre méthode utilise le calcul en avant, souvent préférable au calcul à rebours pour les systèmes contractants. Nous montrons que, sous certaines conditions, le système contrôlé évolue vers un comportement limite. Nous appliquons notre méthode sur plusieurs études de cas issues de la littérature ainsi qu'un exemple réel, un prototype de convertisseur de tension multiniveaux. Enfin, nous montrons que notre méthode s'étend aux systèmes comportant des perturbations ainsi qu'aux systèmes non linéaires. / In this thesis, we are interested in designing schedulers for hybrid systems. We consider two specific subclasses of hybrid systems, real-time systems where tasks are competing for the access to common resources, and sampled switched systems where a choice has to be made on dynamics of the system to reach goals. Scheduling consists in defining the order in which the tasks will be run on the processors in order to complete all the tasks before a given deadline. In the first part of this thesis, we are interested in the scheduling of periodic tasks on multiprocessor architectures. We are especially interested in the robustness of schedulers, i.e., to prove that some values of the system parameters can be modified, and until what value they can be extended while preserving the scheduling order and meeting the deadlines. The Inverse Method can be used to prove the robustness of parametric timed systems. In this thesis, we introduce a state space reduction technique which allows us to treat challenging case studies such as one provided by Astrium EADS for the launcher Ariane 6. We also present how an extension of the Inverse Method, the Behavioral Cartography, can solve the problem of schedulability, i.e., finding the area in the parametric space in which there exists a scheduler that satisfies all the deadlines. We compare this approach to an analytic method to illustrate the interest of our approach In the second part of this thesis, we are interested in the control of affine switched systems. These systems are governed by a finite family of affine differential equations. At each time step, a controller can choose which dynamics will govern the system for the next time step. Controlling in this sense can be seen as a scheduling on the order of dynamics the system will have to use. The objective for the controller can be to make the system stay in a given area of the state space (stability) or to reach a given region of the state space (reachability). In this thesis, we propose a novel approach that computes a scheduler where the strategy is uniform for dense subsets of the state space. Moreover, our approach only uses forward computation, which is better suited than backward computation for contractive systems. We show that our designed controllers, systems evolve to a limit cyclic behavior. We apply our method to several case studies from the literature and on a real-life prototype of a multilevel voltage converter. Moreover, we show that our approach can be extended to systems with perturbations and non-linear dynamics.

Since the emergence of solid state devices onto the storage scene, improvements in capacity and price have brought them to the point where they are becoming a viable alternative to traditional magnetic storage for some applications. Current file system and device level I/O scheduler design is optimized for rotational magnetic hard disk drives. Since solid state devices have drastically different properties and structure, we may need to rethink the design of some aspects of the file system and scheduler levels of the I/O subsystem. In this thesis, we consider the current approach to I/O scheduling and show that the current scheduler design may not be ideally suited to solid state devices. We also present a framework for extracting some device parameters of solid state drives. Using the information from the parameter extraction, we present a new I/O scheduler design which utilizes the structure of solid state devices to efficiently schedule writes. The new scheduler, implemented on a 2.6 Linux kernel, shows up to 25% improvement for common workloads.

In this thesis, we are interested in designing schedulers for hybrid systems. We consider two specific subclasses of hybrid systems, real-time systems where tasks are competing for the access to common resources, and sampled switched systems where a choice has to be made on dynamics of the system to reach goals. Scheduling consists in defining the order in which the tasks will be run on the processors in order to complete all the tasks before a given deadline. In the first part of this thesis, we are interested in the scheduling of periodic tasks on multiprocessor architectures. We are especially interested in the robustness of schedulers, i.e., to prove that some values of the system parameters can be modified, and until what value they can be extended while preserving the scheduling order and meeting the deadlines. The Inverse Method can be used to prove the robustness of parametric timed systems. In this thesis, we introduce a state space reduction technique which allows us to treat challenging case studies such as one provided by Astrium EADS for the launcher Ariane 6. We also present how an extension of the Inverse Method, the Behavioral Cartography, can solve the problem of schedulability, i.e., finding the area in the parametric space in which there exists a scheduler that satisfies all the deadlines. We compare this approach to an analytic method to illustrate the interest of our approach In the second part of this thesis, we are interested in the control of affine switched systems. These systems are governed by a finite family of affine differential equations. At each time step, a controller can choose which dynamics will govern the system for the next time step. Controlling in this sense can be seen as a scheduling on the order of dynamics the system will have to use. The objective for the controller can be to make the system stay in a given area of the state space (stability) or to reach a given region of the state space (reachability). In this thesis, we propose a novel approach that computes a scheduler where the strategy is uniform for dense subsets of the state space. Moreover, our approach only uses forward computation, which is better suited than backward computation for contractive systems. We show that our designed controllers, systems evolve to a limit cyclic behavior. We apply our method to several case studies from the literature and on a real-life prototype of a multilevel voltage converter. Moreover, we show that our approach can be extended to systems with perturbations and non-linear dynamics.

Submitted by ADEMIR MARQUES JUNIOR null (adejunior_marques@hotmail.com) on 2016-06-01T16:14:13Z No. of bitstreams: 1 dissertacao.pdf: 1570162 bytes, checksum: 62279b5b860975f65c7da1a5dbddaa90 (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-06-02T14:41:35Z (GMT) No. of bitstreams: 1 marquesjunior_a_me_sjrp.pdf: 1570162 bytes, checksum: 62279b5b860975f65c7da1a5dbddaa90 (MD5) / Made available in DSpace on 2016-06-02T14:41:35Z (GMT). No. of bitstreams: 1 marquesjunior_a_me_sjrp.pdf: 1570162 bytes, checksum: 62279b5b860975f65c7da1a5dbddaa90 (MD5) Previous issue date: 2016-04-28 / O conceito de Memória Transacional foi criado para simplificar a sincronização de dados em memória, necessária para evitar a computação de dados inconsistentes por processadores multinúcleos, que se tornaram padrão devido às limitações encontradas em processadores de um núcleo. Em evolução constante pela busca de desempenho, os escalonadores de transação foram criados como alternativa aos gerenciadores de contenção presentes nos Sistemas de Memória Transacional. O consumo de energia é preocupação crescente, desde os grandes data centers até os disposítivos móveis que dependem de tempo de bateria, sendo também explorado no contexto de sistemas com Memória Transacional. Trabalhos anteriores consideraram, em sua maioria, somente o uso de gerenciadores de contenção, sendo o objetivo deste trabalho uma análise sobre o uso de escalonadores de transação. Desta forma, são exploradas nesta dissertação as técnicas de escalonamento dinâmico de tensão e frequência (DVFS) para a criação de uma heurística para a redução do consumo de energia utilizando o escalonador LUTS como base. Com o uso de aplicações do benchmark STAMP e biblioteca de memória transacional TinySTM, este trabalho faz uma análise sobre a eficiência energética dos escalonadores de referência ATS e LUTS, enquanto propõe uma nova heurística com o objetivo de reduzir o consumo de energia, denominada LUTSDynamic-Serializer, que alterna entre o uso de spinlock e de trava mutex de forma dinâmica. O uso desta heurística reduziu o EDP em até 17% e 61% em valores de EDP (Eenergy-Delay Product), e 4,95% e 15,8% na média geométrica das aplicações estudadas, em comparação aos escalonadores LUTS e ATS respectivamente, quando se utilizou a configuração de 8 threads, que é a limitação física de threads do processador utilizado no ambiente de experimento. / The Transactional Memory concept was created to simplify the synchronization of data in memory, needed to avoid computation of inconsistent data in multicore processors, which became standard due to limitations in single core processors. In constant search for performance, transactional schedulers were created as a alternative to contention managers present in transactional memory systems. The energy consumption is a crescent worry, ranging from big data centers to mobile devices which are dependent on battery life, and also being studied in Transactional Memory systems. Past works only considered the use of contention managers, and therefore this work seeks to analyse the impact of transactional schedulers. The techniques involving Dynamic Frequency-Voltage Scaling (DVFS) were explored with the motivation to create a heuristic to reduce energy consumption using the LUTS scheduler as a start. Utilizing the STAMP benchmark and the TinySTM transactional memory library, this work does an analysis about the energy efficiency of the reference scheduler ATS and LUTS, while proposing a new heuristic, named LUTSDynamic-Serializer, with the aim to reduce energy consumption by making a choice between spin-lock and mutex lock in a dynamic manner. We achieve with our heuristic up to 17% and 61% in EDP (Energy-Delay Product), and 4,95% and 15,8% considering the geometric mean among the applications studied, compared against the schedulers LUTS and ATS respectively, when we used the configuration with 8 threads, which is the physical limit of threads in the processor used in the experiments.

This thesis investigates the analysis and optimization of safety and performance-critical computational tasks for autonomous robots, operating in unknown and unstructured environments with complex objectives under strict computational and power constraints. Our primary contribution is a novel safety-performance (SP) metric that emphasizes on safety while rewarding enhanced performance of real-time computational tasks, expanding the notion of nominal safety in the autonomous vehicle domain. We adopt the Stochastic Heterogeneous Parallel Directed Acyclic Graph (SHP-DAG) model to capture the uncertain nature of robotic applications and their required computations, modeling execution times using probability distributions instead of deterministic worst-case execution time (WCET). We argue that computational tasks enabling robotic autonomy, such as localization and mapping, path planning, task allocation, depth estimation, and optical flow, must be scheduled and optimized to guarantee timely and correct behavior while allowing for runtime reconfiguration of scheduling parameters. To attain computational awareness in autonomous robots, we conduct a data-driven study of these computational tasks from the resource management perspective, profiling and analyzing their timing, power, and memory performance across three embedded computing platforms. Our SP metric allows us to apply the schedulers First-In-First-Out (FIFO) and Completely Fair Scheduler (CFS) of the Linux kernel on complex robotic computational tasks and compare the SP metric with baseline metrics, such as average and worst-case makespan. Extensive experimental results on NVIDIA Jetson AGX Xavier hardware demonstrate the effectiveness of the proposed SP metric in managing computational tasks while balancing safety and performance in robotic systems. Our findings reveal a correlation between task performance and a robot's operational environment, which justifies the concept of computation-aware robots and highlights the importance of our work as a crucial step towards this goal. Finally, we also integrate a custom scheduler with the FIFO priorities with our SHP-DAG and show the efficacy of our framework in comparison to default fair scheduler. / Doctor of Philosophy / This paper explores how to improve the safety and performance of autonomous robots operating in unpredictable and complex environments. These robots need to carry out various tasks such as mapping, path planning, and depth estimation, while managing limited computing power and energy resources. To achieve this, we introduce a new safety-performance (SP) metric that prioritizes safety while rewarding better task performance. We use a cutting-edge model that captures the uncertainty of robotic tasks and their required computing resources. By doing so, we can better schedule and optimize these tasks to ensure timely and correct behavior while allowing for adjustments to scheduling parameters during operation. Our study investigates the performance of key computing tasks on various embedded computing platforms. By comparing our SP metric with traditional measures, we can demonstrate the effectiveness of our approach in managing these tasks while balancing safety and performance in robotic systems. We also do system integration of a real-time scheduler with robotic tasks, which shows the efficacy of our framework. Our findings show a connection between a robot's environment and its computing performance, highlighting the importance of our work as a critical step towards creating smarter and safer autonomous robots that can better adapt to their surroundings.

Large organizations and research institutes store a huge volume of data nowadays.In order to gain any valuable insights distributed processing frameworks over acluster of computers are needed. Apache Hadoop is the prominent framework fordistributed storage and data processing. At SICS Swedish ICT we are building Hops, a new distribution of Apache Hadoop relying on a distributed, highly available MySQL Cluster NDB to improve performance. Hops-YARN is the resource management framework of Hops which introduces distributed resource management, load balancing the tracking of resources in a cluster. In Hops-YARN we make heavy usage of the back-end database storing all the resource manager metadata and incoming RPCs to provide high fault tolerance and very short recovery time. This project aims in optimizing the mechanisms used for persisting metadata in NDB both in terms of transactional commit time but also in terms of pre-processing them. Under no condition should the in-memory RM state diverge from the state stored in NDB. With these goals in mind several solutions were examined that improved the performance of the system, making Hops-YARN comparable to Apache YARN with the extra benefits of high-fault tolerance and short recovery time. The solutions proposed in this thesis project enhance the pure commit time of a transaction to the MySQL Cluster and the pre-processing and parallelism of our Transaction Manager. The results indicate that the performance of Hops increased dramatically, utilizing more resources on a cluster with thousands of machines. Increasing the cluster utilization by a few percentages can save organizations a big amount of money. / Nu för tiden lagrar stora organisationer och forskningsinstitutioner enorma mängder data.För att kunna utvinna någon värdefull information från dessa data behöver den bearbetasav ett kluster av datorer. När flera datorer gemensamt ska bearbeta data behöver de utgåfrån ett så kallat "distributed processing framework''. I dagsläget är Apache Hadoop detmest använda ramverket för distribuerad lagring och behandling av data. Detta examensarbeteär har genomförts vid SICS Swedish ICT där vi byggt Hops, en ny distribution avApache Hadoop som drivs av ett distribuerat MySQL Cluster NDB som erbjuder en hög tillgänglighet.Hops-YARN är Hops ramverk för resurshantering med distribuerade ResourceManagers som lastbalanserarderas ResourceTrackerService. I detta examensarbete använder vi Hops-Yarn på ett sätt där ``back-end''databasen flitigt används för att hantera ResourceManagerns metadata och inkommande RPC-anrop. Vårkonfiguration erbjuder en hög feltolerans och återställer sig mycket snabbt vidfelberäkningar. Vidare används NDB-klustrets Event API för att ResourceManager ska kunnakommunicera med den distribuerade ResourceTrackers. Detta projekt syftar till att optimera de mekanismer som används för ihållande metadatai NDB både i termer av transaktions begå tid men också i termer av pre-bearbeta dem medan samtidigt garantera enhetlighet i RM: s tillstånd. ResourceManagerns tillståndi RAM-minnet får under inga omständigheteravvika från det tillstånd som finns lagrat i NDB:n. Med dessa mål i åtanke undersöktes fleralösningar som förbättrar prestandan och därmed gör Hops-Yarn jämförbart med Apache YARN.De lösningar som föreslås i denna uppsats förbättrar “pure commit time” när en transaktiongörs i ett MySQL Cluster samt förbehandlingen och parallelismen i vår Transaction Manager.Resultaten tyder på att Hops prestanda ökade dramatiskt vilket ledde till ett effektivarenyttjande av tillgängliga resurser i ett kluster bestående av ett tusental datorer. Närnyttjandet av tillgänliga resurser i ett kluster förbättras med några få procent kanorganisationer spara mycket pengar.

Les avancées technologiques ont conduit les grandes organisations telles que les entreprises,les universités et les instituts de recherche à se doter d'intranets constitués de plusieurs serveurs etd'un grand nombre de postes de travail. Cependant dans certaines de ces organisations, les postes detravail sont très peu utilisés pendant la nuit, les week-ends et les périodes de congés, libérant ainsiune grande puissance de calcul disponible et inutilisée.Dans cette thèse, nous étudions l'exploitation de ces temps de jachère afin d'exécuter desapplications de calcul haute performance. A cet effet, nous supposons que les postes acquis sontrebootés et intégrés à des grappes virtuelles constituées dynamiquement. Toutefois, ces temps dejachère ne permettent pas toujours d'exécuter les applications jusqu'à leur terme. Les mécanismes desauvegarde/reprise (checkpointing) sont alors utilisés pour sauvegarder, dans un certain délai, lecontexte d'exécution des applications en vue d'une éventuelle reprise. Il convient de noter que lasauvegarde de tous les processus dans les délais impartis n'est pas toujours possible. Nousproposons un modèle d'ordonnancement des sauvegardes en parallèle, qui tient compte descontraintes temporelles imposées et des contraintes liées aux bandes passantes (réseau et disque),pour maximiser les temps de calcul déjà effectués pour les applications candidates à la sauvegarde. / The technological advances has led major organizations such as enterprises, universities andresearch institutes to acquire intranets consisting of several servers and many workstations.However, in some of these organizations, the resources are rarely used at nights, weekends and onholidays, thus releasing a large computing power available and unused.This thesis discusses the exploitation of the idle period of workstaions in order to run HPCapplications. The workstations retained are restarted and integrated in dynamically formed clusters.However, the idle periods do not always permit the complete carrying out of the computationsallocated to them. The checkpointing mechanisms are then used to save in a certain period, theexecution context of applications for a possible restart. It is worth nothing that checkpointing all theprocesses in the required period is not always possible. We propose a scheduling model ofcheckpointing in parallel, which takes into account the time constraints imposed and the bandwidthconstraints (network and disk) to maximize the computation time already taken for the applicationswhich are to be checkpointed.