The Internet has become one of the most widely used forms of communication available. Many applications used on the Internet require the user to interact constantly with the network. For example web browsing where the user will expect the browser to respond quickly, to finish loading pages quickly and to do all of this at an equal level for all users. The network's performance is dependant on the protocols it uses and how the resources of the network are distributed. This is why TCP (Transmission Control Protocol) is one of the most important protocols, because it controls the amount of data entering the network and provides reliability to most interactive applications. The thesis starts by introducing a basic TCP model which is later extended to model the effects of burstiness produced by TCP. Burstiness can cause a routers buffer to unnecessarily overflow. These overflows cause TCP connections to under-utilise link bandwidth because of unnecessary packet retransmissions. A model to define a quantitative measure of both burstiness and throughput of a system of TCP connections is introduced. The model gives insight into how the TCP protocol causes burstiness and can be used to find scenarios where burstiness is decreased. This helps to improve the utilization of links by reducing the burstiness of protocols. An important performance metric for interactive traffic is user perceived delay, the delay that an end user would encounter when using an application. An example of user perceived delay is the time a user waits before a HTML web page starts loading. The retransmission delays are the most important type of delay for interactive traffic because they are usually very large. A dynamic priority RED Queue (DPRQ) is introduced which changes the priority of the queues based on the goodput (throughput of succesfully transmitted packets) threshold of the interactive traffic. Using dynamic priority allows packet loss to be reduced by up to eight times for interactive traffic, which intern reduces retransmission delay. Fairness measures how equally network resources are allocated amongst different connections. When a link with TCP connections is overloaded each connection on the link will reduce its throughput to allow all the connections to have approximately equal load. This does not take into account that other links may be under utilized. The fairness issue is addressed by introducing Multipath TCP (MATCP) which allows path selection to occur at the TCP layer. This allows each unique flow to take a different path, instead of all the flows of one source using the same path. Using MATCP, a finer grain of load-balancing can be achieved and the complexity and state required in the network is greatly reduced. Two analytic models are provided in chapters three and four, which investigate slow start and TCP burstiness. In chapter five the DPRQ queue is introduced to reduce user perceived delay. An analytic model of the DPRQ is provided and verified through experimental simulation. In chapter six an analytic model of Multipath TCP is provided, which is also verified by simulation.

L’objectif que nous nous sommes fixés dans ce travail est la conception d’algorithmes d’ordonnancement temps réel en-ligne faisables optimisant l’utilisation de la plate-forme d’exécution et/ou des critères applicatifs de qualité de service propres à l’application. Nous avons en particulier étudié l’ordonnancement d’activités sur une ressource unique. Deux cas ont été analysés : le cas de tâches indépendantes périodiques s’exécutant sur un processeur et le cas de flux de messages indépendants périodiques sur un réseau de terrain avec accès au médium priorisé. Nos contributions reposent sur le “modèle classique” de l’ordonnancement temps réel où le système est représenté par un ensemble d’activités périodiques indépendantes et deux problématiques ont été abordées : • optimisation de l’utilisation de la plate-forme d’exécution : utiliser au mieux le potentiel de la plate-forme d’exécution tout en garantissant le respect des contraintes temporelles imposées au système ; ceci optimise le nombre de configurations faisables, • optimisation des critères applicatifs de qualité de service propres à l’application (i.e., pris en compte des performances de l’application autre que la faisabilité) : garantir les contraintes de temps tout en optimisant les performances de l’application. Nous avons donc proposé : • des méthodes de configurations permettant d’optimiser l’utilisation de la plate-forme d’exécution (i.e., maximiser faisabilité) en fixant les paramètres des politiques ou des systèmes considérés d’une manière appropriée. Deux études ont été conduites dans ce cadre : • allocation des “offsets” dans les systèmes “offset free”, • allocation de priorités, de politiques et de quantum dans les systèmes conformes au standard Posix 1003.1b, • une nouvelle classe de politiques d’ordonnancement permettant d’optimiser des critères de performances propres à l’application. De plus, une analyse d’ordonnancement générique pour cette classe a été proposée / Our goal is to come up with feasible (i.e., all required time constraints are met) on-line real-time scheduling algorithms. These algorithms have to optimise 1) the utilisation of the execution platform (i.e., meet time constraints and use platform at its fullest potential) and/or 2) optimise the application dependent performance criteria. We study two cases : the case of independent periodic tasks scheduled on a processor and the case of periodic traffic streams scheduled on a priority bus. To deal with these two problems, we propose : • Configuration methods to allow to optmlise the utilisation rate of the execution platform by setting the parameters of the policies or of the activities of the considered system. We perform two studies : the allocation of offsets in "Offset free" systems (I.E., offsets can be chosen off-line) and the priorities, policies and quantum allocations in systems compliant to the standard Posix 1003.1B, • A new class of scheduling policies to allow optimising application performance dependent criteria

With multiprocessors and multicore processors becoming ubiquitous, focus has shifted from research on uniprocessors to that on multiprocessors. Results derived for the uniprocessor case unfortunately do not always directly extend to the multiprocessor case in a straightforward manner. This necessitates a paradigm shift in the approach used to design and analyse the behaviour of such processors. In the case of Real-time systems, that is, systems characterised by explicit timing constraints, analysis and performance guarantees are more important, as failure is unacceptable. Scheduling algorithms used in Real-time systems have to be carefully designed as the performance of the system depends critically on them. Efficient tests for determining if a set of tasks can be feasibly scheduled on such a computing system using a particular scheduling algorithm thus assumes importance. Traditionally, the ‘task utilization’ parameter has been used for devising such tests. Utilization based tests for Earliest Deadline First(EDF) and Rate Monotonic(RM) scheduling algorithms are known and are well understood for uniprocessor systems. In our work, we derive limits on similar bounds for the multiprocessor case. Our work diners from previous literature in that we explore the case when the individual processors constituting the multiprocessor need not be identical. Each processor in such a system is characterised by a capacity, or speed, and the time taken by a task to execute on a processor is inversely proportional to its speed. Such instances may arise during system upgradation, when faster processors may be added to the system, making it a non-identical multiprocessor, or during processor design, when the different cores on the chip may have different processing power to handle dynamic workloads. We derive results for the partitioned paradigm of multiprocessor scheduling, that is, when tasks are partitioned among the processors, and interprocessor migration after a part of execution is completed is not allowed. Results are derived for both fixed priority algorithms(RM)and dynamic priority algorithms (EDF) used on individual processors. A maximum and minimum limit on the bounds for a ‘greedy’ class of algorithms are established, since the actual value of the bound depends on the algorithm that allocates the tasks. We also derive the utilization bound of an algorithm whose bound is close to the upper limit in both cases. We find that an expression for the utilization bound can be obtained when EDF is used as the uniprocessor scheduling algorithm, but when RM is the uniprocessor scheduling algorithm,an O(mn) algorithm is required to find the utilization bound, where m is the number of tasks in the system and n is the number of processors. Knowledge of such bounds allows us to carry out very fast schedulability tests, although we have the limitation that the tests are sufficient but not necessary to ensure schedulability. We also compare the value of the bounds with those achievable in ‘equivalent’ identical multiprocessor systems and find that the performance guarantees provided by the non-identical multiprocessor system are far higher than those offered by the equivalent identical system.