NDLI: Minimizing the Total Weighted Completion Time of Coflows in Datacenter Networks

Please wait, while we are loading the content...

Sorting with Asymmetric Read and Write Costs

Matrix Multiplication I/O-Complexity by Path Routing

Myths and Misconceptions about Threads

Brief Announcement: New Streaming Algorithms for Parameterized Maximal Matching & Beyond

The Cilkprof Scalability Profiler

Speed Scaling in the Non-clairvoyant Model

The Revolution in Graph Theoretic Optimization Problems

Space and Time Efficient Parallel Graph Decomposition, Clustering, and Diameter Approximation

Seer: Probabilistic Scheduling for Hardware Transactional Memory

Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff

Communication-Efficient Computation on Distributed Noisy Datasets

Practical Massively Parallel Sorting

Online Caching with Convex Costs: Extended Abstract

Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees

Race Detection in Two Dimensions

Cost-Oblivious Reallocation for Scheduling and Planning

Improved Parallel Algorithms for Spanners and Hopsets

Conflict Reduction in Hardware Transactions Using Advisory Locks

Distributed Backup Placement in Networks

Parallel Computation of Persistent Homology using the Blowup Complex

A Top-Down Parallel Semisort

Brief Announcement: Efficient Approximation Algorithms for Computing k Disjoint Restricted Shortest Paths

Efficiently Detecting Races in Cilk Programs That Use Reducer Hyperobjects

Temporal Fairness of Round Robin: Competitive Analysis for Lk-norms of Flow Time

Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints

Transactional Acceleration of Concurrent Data Structures

Better Deterministic Online Packet Routing on Grids

Self-Stabilizing Repeated Balls-into-Bins

Brief Announcement: Fast and Better Distributed MapReduce Algorithms for k-Center Clustering

ThreadScan: Automatic and Scalable Memory Reclamation

Scheduling Non-Unit Jobs to Minimize Calibrations

Branch-Avoiding Graph Algorithms

Efficient Memory Management for Lock-Free Data Structures with Optimistic Access

Minimizing the Total Weighted Completion Time of Coflows in Datacenter Networks

Randomized Local Network Computing

Brief Announcement: Fair Adaptive Parallelism for Concurrent Transactional Memory Applications

Scheduling in Bandwidth Constrained Tree Networks

Electing a Leader in Wireless Networks Quickly Despite Jamming

Brief Announcement: Managing Resource Limitation of Best-Effort HTM

Brief Announcement: On Scheduling Best-Effort HTM Transactions

Brief Announcement: Towards a Universal Approach for the Finite Departure Problem in Overlay Networks

Brief Announcement: MultiQueues: Simple Relaxed Concurrent Priority Queues

Brief Announcement: A Compiler-Runtime Application Binary Interface for Pipe-While Loops

Brief Announcement: Hypergraph Partitioning for Parallel Sparse Matrix-Matrix Multiplication

Minimizing the Total Weighted Completion Time of Coflows in Datacenter Networks

Content Provider	ACM Digital Library
Author	Zhong, Yuan Stein, Cliff Qiu, Zhen
Abstract	Communications in datacenter jobs (such as the shuffle operations in MapReduce applications) often involve many parallel flows, which may be processed simultaneously. This highly parallel structure presents new scheduling challenges in optimizing job-level performance objectives in data centers. Chowdhury and Stoica introduced the coflow abstraction to capture these communication patterns, and recently Chowdhury et al. developed effective heuristics to schedule coflows. In this paper, we consider the problem of efficiently scheduling coflows with release dates so as to minimize the total weighted completion time, which has been shown to be strongly NP-hard. Our main result is the first polynomial-time deterministic approximation algorithm for this problem, with an approximation ratio of 67/3, and a randomized version of the algorithm, with a ratio of 9+16√2/3. Our results use techniques from both combinatorial scheduling and matching theory, and rely on a clever grouping of coflows. We also run experiments on a Facebook trace to test the practical performance of several algorithms, including our deterministic algorithm. Our experiments suggest that simple algorithms provide effective approximations of the optimal, and that our deterministic algorithm has near-optimal performance.
Starting Page	294
Ending Page	303
Page Count	10
File Format	PDF
ISBN	9781450335881
DOI	10.1145/2755573.2755592
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-06-13
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Greedy algorithms Approximation algorithms Algorithm analysis Concurrent open shop scheduling with coupled resources Map-reduce
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in