The focus of this dissertation is design and analysis of scheduling algorithms for distributed computer systems, i.e., data centers. Today’s data centers can contain thousands of servers and typically use a multi-tier switch network to provide connectivity among the servers. Data centers are the host for execution of various data-parallel applications. As an abstraction, a job in a data center can be thought of as a group of interdependent tasks, each with various requirements which need to be scheduled for execution on the servers and the data flows between the tasks that need to be scheduled in the switch network. In this thesis, we study both flow and task scheduling problems under the features of modern parallel computing frameworks.For the flow scheduling problem, we study three models. The first model considers a general network topology where flows among the various source-destination pairs of servers are generated dynamically over time. The goal is to assign the end-to-end data flows among the available paths in order to efficiently balance the load in the network. We propose a myopic algorithm that is computationally efficient and prove that it asymptotically minimizes the total network cost using a convex optimization model, fluid limit and Lyapunov analysis. We further propose randomized versions of our myopic algorithm. The second model consider the case that there is dependence among flows. Specifically, a coflow is defined as a collection of parallel flows whose completion time is determined by the completion time of the last flow in the collection. Our main result is a 5-approximation deterministic algorithm that schedule coflows in polynomial time so as to minimize the total weighted completion times. The key ingredient of our approach is an improved linear program formulation for sorting the coflows followed by a simple list scheduling policy. Lastly, we study scheduling coflows of multi-stage jobs to minimize the jobs’ total weighted completion times. Each job is represented by a DAG (Directed Acyclic Graph) among its coflows that captures the dependencies among the coflows. We define g(m) = log(m)/log(log(m)) and h(m, μ) = log(mμ)/(log(log(mμ)), where m is number of servers, μ is the maximum number of coflows in a job. We develop two algorithms with approximation ratios O(√μg(m)) and O(√μg(m)h(m, μ)) for jobs with general DAGs and rooted trees, respectively. The algorithms rely on random delaying and merging optimal schedules of the coflows in the jobs’ DAG, followed by enforcing dependency among coflows and the links’ capacity constraints. For the task scheduling problem, we study two models. We consider a setting where each job consists of a set of parallel tasks that need to be processed on different servers, and the job is completed once all its tasks finish processing. In the first model, each job is associated with a utility which is a decreasing function of its completion time. The objective is to schedule tasks in a way that achieves max-min fairness for jobs’ utilities. We first show a strong result regarding NP-hardness of this problem. We then proceed to define two notions of approximation solutions and develop scheduling algorithms that provide guarantees under these approximation notions, using dynamic programming and random perturbation of tasks’ processing times. In the second model, we further assume that processing times of tasks can be server dependent and a server can process (pack) multiple tasks at the same time subject to its capacity. We then propose three algorithms with approximation ratios of 4, (6 + ε), and 24 for different cases where preemption and migration of tasks among the servers are or are not allowed. Our algorithms use a combination of linear program relaxation and greedy packing techniques. To demonstrate the gains in practice, we evaluate all the proposed algorithms and compare their performances with the prior approaches through extensive simulations using real and synthesized traffic traces. We hope this work inspires improvements to existing job management and scheduling in distributed computer systems.

Relays in communication networks is a well-researched topic. Historically, relays were used in analog radio and television to extend the coverage. Using relays in wireless data networking applications is a more recent problem. In the early 2000s, relays were introduced for Micro-cellular and Wi-Fi deployments. Recently it has been considered for sensor networks and Vehicular Ad-hoc Networks (VANETs) applications. In this dissertation we present a novel approach to determine the optimal bounds for the Medium Access Control (MAC) throughput at the target receiver in a multi-hop multirate wireless data network. For a given relationship between the throughput and the distance, and a given distance between the access point and the target receiver, there is a minimum number of nodes that provides the maximum throughput to the target receiver. It is always desirable to optimize the deployment from various aspects. These aspects are application dependent and they range from energy conservation in sensor networks to throughput and coverage maximization in data networks. We apply this novel approach to vehicular ad-hoc network (VANET) scenarios. Using multi-hop relays, we show how to determine the optimum throughput for communciation between two vehicles. The optimal number of relays is chosen to maximize the throughput for point-to-point communication between a source and a destination as well as broadcast among all vehicles in the coverage area of the source. Additionally, in the physical layer, performance issues arise from the effects of interference and fading. The physical layer performance will in turn impact medium access control performance, effectively reducing the network throughput. We evaluate the ii performance of dense small cells for wireless local area networks (WLAN) and femto cells for data applications under the effects of interference and fading. We assume the network is fully saturated. We use the throughput-distance relationship to take into consideration the effects of interference, fading as well as the medium access control overheads. Using this model, we show that under certain conditions, the medium access control throughput for WLANs can outperform that of femto cells.

It is clear that the internet is being used more often for social interactions but the reasons why people adopt these newer technologies are still unclear. Over the last thirty years numerous adoption theories have been proposed however few account for the newer types of technology, such as social website usage. Purpose – The study will compare and contrast two different models of adoption to see if one model is better than the other in understanding the usage of social networking websites such as Facebook. At an organisational level the idea of extended usage of technology has been encapsulated in the construct of infusion of technology into a work place. The study will also show that infusion of technology may occur at an individual level of research. The argument is made that since national culture has been shown to affect usage, national culture may moderate the level of infusion that is found. Methodology – The study will use a quantitative methodology to survey potential (or actual) users of Facebook using a structured questionnaire. Since two adoption models are being tested, two questionnaires were developed and tested. The items for the questionnaires have been adapted from prior literature. Reliability and validity tests confirmed the scales from prior literature. The sample was selected from higher education institutions within the Johannesburg region .Specifically, students from the University of the Witwatersrand and the University of Johannesburg were invited to complete the questionnaires. The two questionnaires were mixed randomly between the students. Findings – It was found that the traditional technology acceptance model could better explain the usage of social networking websites when compared to the more modern WebQual framework. The study found that there is a strong positive relationship between usage and infusion. In line with the prior research on national culture moderating usage, the study found that national culture does moderate the relationship between usage and infusion. Implications – The study has a number of implications. Firstly, the research compared two models of technology usage. The study showed that the technology acceptance model was better at explaining the usage of social networking websites. Future research should focus on improving the TAM model and may result in better understanding the usage of social websites. Secondly, a set of scales are provided for future research which allow for the measurement of infusion at an individual level. These scales were tested for reliability and validity in two separate data collections and in both collections the scales met or exceeded the statistical requirements. Thirdly, the relationship between usage and infusion is seen to be moderated by national culture. This has 5 large implications for organisations and people who use Web2.0 as a medium for business. As an example, marketers could use the results in better understanding the usage of these types of websites, in the hope that it would allow for better targeting and placement of adverts. Lastly, the implications may extend beyond the context of the research. The study found a relationship between usage and infusion at an individual level of analysis. The relationship may exist in other areas of research which relate to Information systems including but not limited to Marketing (increasing the life cycle of products and increasing the value of customers through brand loyalty) and human resources (increasing employee efficiency through understanding peoples infusion of different types of technology). Research limitations – The research is limited to the sample that was achieved. The findings can be directly inferred to a similar sample base within South Africa, however cannot be generalised to samples of dissimilar natures. While the study used Facebook as a case, it should be cautioned that the results should not be generalised to other forms of social networking websites such as Twitter. Originality – The study is original in the following ways: Firstly, the study was conducted in South Africa where few other studies been found with a similar nature. Secondly, the study extended the thoughts on usage to the idea of infusion. Thirdly, two models were directly compared with independent data collections occurring. Fourthly, the relationship between usage and infusion is seen to be moderated by national culture. Both the relationship as well as the moderation effects has previously been empirically shown.

The Internet supports a perpetually evolving patchwork of network services and applications. Popular applications include the World Wide Web, online commerce, online banking, email, instant messaging, multimedia streaming, and online video games. Practically all networked applications have a common objective: to directly or indirectly process requests generated by humans. Some users employ automation to establish an unfair advantage over non-automated users. The perceived and substantive damages that automated, adversarial users inflict on an application degrade its enjoyment and usability by legitimate users, and result in reputation and revenue loss for the application's service provider. This dissertation examines three challenges critical to addressing the undesirable automation of networked applications. The first challenge explores individual methods that detect various automated behaviors. Detection methods range from observing unusual network-level request traffic to sensing anomalous client operation at the application-level. Since many detection methods are not individually conclusive, the second challenge investigates how to combine detection methods to accurately identify automated adversaries. The third challenge considers how to leverage the available knowledge to disincentivize adversary automation by nullifying their advantage over legitimate users. The thesis of this dissertation is that: there exist methods to detect automated behaviors with which an application's service provider can identify and then systematically disincentivize automated adversaries. This dissertation evaluates this thesis using research performed on two network applications that have different access to the client software: Web-based services and multiplayer online games.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.