published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

Wireless scheduling is a fundamental problem in wireless networks that involves scheduling transmissions of multiple users in order to support data flows with as high rates as possible. This problem was first addressed by Tassuilas and Ephremides, resulting in the celebrated Back-Pressure network scheduling algorithm. This algorithm schedules network links to maximize throughput in an opportunistic fashion using instantaneous network state information (NSI), i.e., queue and channel state knowledge across the entire network. However, the Back-Pressure (BP) algorithm suffers from various drawbacks - (a) it requires knowledge of instantaneous NSI from the whole network, i.e. feedback about time-varying channel and queue states from all links of the network, (b) the algorithm requires solving a global optimization problem at each time to determine the schedule, making it highly centralized. Further, Back-pressure algorithm was originally designed for wireless networks where interference is modeled using protocol interference model. As recent break-throughs in full-duplex communications and interference cancelation techniques provide greatly increased capacity and scheduling flexibility, it is not clear how BP algorithm can be modified to improve the data rates and reduce the delay. In this thesis, we address the drawbacks of Back-Pressure algorithm to some extent. In particular, our first work provides a new scheduling algorithm (similar to BP) that allows users to make individual decisions (distributed) based on heterogeneously delayed network state information (NSI). Regarding the complexity issue, in our second work, we analyze the performance of the greedy version of BP algorithm, known as Greedy Maximal Scheduling (GMS) and understand the effect of channel variations on the performance of GMS. In particular, we characterize the efficiency ratio of GMS in wireless networks with fading. In our third and fourth work, we propose and analyze new scheduling algorithms that can benefit from new advancements in interference cancelation techniques. / text

<p>Much effort today in the Internet research community isaimed at providing network services for applications that werenot under consideration when the Internet was originallydesigned. Nowadays the network has to support real-timecommunication services that allow clients to transportinformation with expectations on network performance in termsof loss rate, maximum end-to-end delay, and maximum delayjitter. Today there exist two quality of service (QoS)architecture for the Internet: The integrated services, whichis usually referred to as intserv, and the differentiatedservices referred to as diffserv. Although the intserv clearlydefines the quality levels for each of its three serviceclasses, the limited scalability of this QoS architecture is acontinuous topic for discussion among the researchers. Theanalysis of the tradeoffs of the two QoS architecturesmotivated us to design a new QoS architecture which will takethe strength of the existing approaches and will combine themin a simpler, efficient and more scalable manner.</p><p>In this LicentiateThesis we introduce a guaranteed servicefor the Internet, which definition is similar to the one inintserv: The guaranteed service (GS) is a network servicerecommended for applications with firm requirements on qualityof end-to-end communication. The service should provide zeropacket loss in routers and tightly bound the end-to-end delay.The capacity for a GS connection should be explicitly reservedin every router along a path of a connection. However, incontrary to intserv the necessary quality level will beprovided without per-flow scheduling in the core routers, whichis the major drawback of the intserv architecture. We use thediffserv principle of dealing with aggregates in the corenetwork since this approach is proven to be scalable andefficient.</p><p>The thesis considers two major building blocks of the newarchitecture: The packet scheduling and the signaling protocol.We have developed a special scheduling algorithm. Our formaland experimental analysis of its delay properties shows thatthe maximum end-to-end delay is acceptable for real-timecommunication. Moreover, our scheme provides a fair service tothe traffic of other service classes. In order to achieve thedesired QoS level, a sufficient amount of capacity should bereserved for the GS connections in all intermediate routersend-to-end. We have developed a both simple and robustsignaling protocol. The realization of our protocol shows thatrouters are able to process up to 700,000 signaling messagesper second without overloading the processor.</p>

<p>There is seemingly a never-ending consumer demand for mobileterminals such as cellular phones and personal digitalassistants (PDAs). Each new generation of terminals comes withmore elaborate functions than in the previous generation. Thistrend results in a higher performance demand on the computerarchitecture that performs the required computations within theterminal. To satisfy the projected requirements on cominggenerations of mobile terminals, we propose an architecturethat when intelligently managed can provide the necessaryperformance at low power and energy consumption. Thisarchitecture, a chip-multiprocessor (CMP), thus amulti-processor implemented on a single chip, has incombination with adaptive scheduling strategies the potentialto efficiently fullfill future requirements.</p><p>This licentiate thesis spans over several studies done onthe effectiveness of the adaptive CMP. In our studies, we haveshown that an adaptive CMP can satisfy the same performancerequirements as a comparable uni-processor, still consumingless power and energy. Furthermore, we have made an effort toaccurately model the workload behaviour of mobile terminals,which is of paramount importance when comparing candidatearchitectures. In the future, apart from proposing moreadaptive scheduling techniques, we expect to do more thoroughstudies on workload modeling as well as on the operating systeminfluence on the overall performance and power consumption.</p>

<p>The LOIS project aims at building a radio sensor and IT infrastructure in the south of Sweden, primarily with but not limited to the goal of space observations. Signals received produce a gigantic stream of data that has to be processed in real time. Our purpose is scheduling stream computations to computation nodes in such a way that the performance requirements are met. We built a framework where different local and global scheduling algorithms can be executed and tested including a number of benchmarking programs, comparing the performances.</p><p>We will try to use a method as simple as possible. Given the results of the different local schedules as input – mapping parallel computations (tasks) to processors – along with some parameters such as the algorithm to apply and machine parameters, the framework will compute a global schedule. Moreover, the framework will visualize the results. We understand that framework as a graphic interface able to simulate the manipulation of different tasks, as well as different measurement groups. Showing the better performances is a big aid in order to improve the stream computation.</p>

No description available.

No description available.