NDLI: Dynamic TCP acknowledgement: penalizing long delays

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

Optimal parallel selection

Algorithms for power savings

Sublogarithmic approximation for telephone multicast: path out of jungle (extended abstract)

Browsing around a digital library

Binary space partitions for 3D subdivisions

Improved bounds on the average length of longest common subsequences

Certifying algorithms for recognizing interval graphs and permutation graphs

Optimizing misdirection

Pass efficient algorithms for approximating large matrices

Certifying and repairing solutions to large LPs how good are LP-solvers?

The flow complex: a data structure for geometric modeling

Random walks on the vertices of transportation polytopes with constant number of sources

Space-efficient finger search on degree-balanced search trees

Data streams: algorithms and applications

Sparse distance preservers and additive spanners

Improved results for directed multicut

A note on the set systems used for broadcast encryption

Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk

Lower bounds for embedding edit distance into normed spaces

Better algorithms for high-dimensional proximity problems via asymmetric embeddings

On the rectilinear crossing number of complete graphs

Edge disjoint paths revisited

Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time

Who cares about permanents?

Between O(nm) and $O(n^{α})$

Efficient sequences of trials

Competitive queueing policies for QoS switches

Smaller core-sets for balls

Inferring tree topologies using flow tests

High-order entropy-compressed text indexes

Selection with monotone comparison costs

Dynamic TCP acknowledgement: penalizing long delays

On the performance of user equilibria in traffic networks

Allocating vertex π-guards in simple polygons via pseudo-triangulations

Directed scale-free graphs

Dominating sets in planar graphs: branch-width and exponential speed-up

Online learning in online auctions

Rangesum histograms

An improved approximation algorithm for the 0-extension problem

Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio

Smaller explicit superconcentrators

Multi-embedding and path approximation of metric spaces

Algorithms for k-colouring and finding maximal independent sets

Lower bounds for collusion-secure fingerprinting

Non-independent randomized rounding

Embedding k-outerplanar graphs into ℓ1

Lower bounds for external memory dictionaries

Matching planar maps

A new approximation algorithm for the asymmetric TSP with triangle inequality

Compact representations of separable graphs

Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons

Pursuit-evasion with imprecise target location

Dynamic routing on networks with fixed-size buffers

Zonotopes as bounding volumes

Wavelength assignment and generalized interval graph coloring

Multidimensional matching and fast search in suffix trees

Property testing of data dimensionality

Approximately optimal control of fluid networks

Faster approximation algorithms for the minimum latency problem

Straight-skeleton based contour interpolation

The cover time of sparse random graphs.

Quick and good facility location

An approximate truthful mechanism for combinatorial auctions with single parameter agents

Approximation of functions over redundant dictionaries using coherence

Packing Steiner trees

On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres

A (1 + ε)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma

Maintaining all-pairs approximate shortest paths under deletion of edges

Approximation algorithm for embedding metrics into a two-dimensional space

Equitable colorings with constant number of colors

Quantum property testing

Minimizing weighted flow time

Embeddings and non-approximability of geometric problems

Online paging with arbitrary associativity

Dynamic generators of topologically embedded graphs

Approximating asymmetric maximum TSP

Labeling schemes for small distances in trees

A 5/4-approximation algorithm for minimum 2-edge-connectivity

Unconditional proof of tightness of Johnson bound

Dynamic construction of Bluetooth scatternets of fixed degree and low diameter

Sublinear-time approximation of Euclidean minimum spanning tree

An improved approximation algorithm for the partial latin square extension problem

Inplace 2D matching in compressed images

Comparing top k lists

Minimum cost flows over time without intermediate storage

Data migration to minimize the average completion time

Möbius-invariant natural neighbor interpolation

Perfect matchings in random graphs with prescribed minimal degree

Chain decompositions and independent trees in 4-connected graphs

Competitiveness via consensus

Counting inversions in lists

Integrality ratio for group Steiner trees and directed steiner trees

Perturbations and vertex removal in a 3D delaunay triangulation

A spectral technique for random satisfiable 3CNF formulas

A faster and simpler fully dynamic transitive closure

On the complexity of distance-based evolutionary tree reconstruction

Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph

Quantum algorithms for some hidden shift problems

A combinatorial algorithm for computing a maximum independent set in a t-perfect graph

The set-associative cache performance of search trees

Computing homotopic shortest paths in the plane

The k-traveling repairman problem

On $AC^{0}$ implementations of fusion trees and atomic heaps

Fault-tolerant facility location

Deterministic identity testing for multivariate polynomials

Scheduling techniques for media-on-demand

An approximation algorithm for cutting out convex polygons

Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs

The similarity metric

Root comparison techniques applied to computing the additively weighted Voronoi diagram

Random MAX SAT, random MAX CUT, and their phase transitions

Computing strongly connected components in a linear number of symbolic steps

Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time

Directed graphs requiring large numbers of shortcuts

Dynamic TCP acknowledgement: penalizing long delays

Content Provider	ACM Digital Library
Author	Bals, Helge Albers, Susanne
Abstract	We study the problem of acknowledging a sequence of data packets that are sent across a TCP connection. Previous work on the problem has focused mostly on the objective function that minimizes the sum of the number of acknowledgements sent and the delays incurred for all of the packets. Dooly, Goldman and Scott presented a deterministic 2-competitive online algorithm and showed that this is the best competitiveness of a deterministic strategy. Recently Karlin, Kenyon and Randall developed a randomized online algorithm that achieves an optimal competitive ratio of e/(e -- 1) ≈ 1.58.In this paper we investigate a new objective function that minimizes the sum of the number of acknowledgements sent and the maximum delay incurred for any of the packets. This function is especially interesting if a TCP connection is used for interactive data transfer between network nodes. The TCP acknowledgement problem with this new objective function is different in structure than the problem with the function considered previously. We develop a deterministic online algorithm that achieves a competitive ratio of $π^{2}/6$ , ≈ 1.644 and prove that no deterministic algorithm can have a smaller competitiveness. We also study a generalized objective function where delays are taken to the p-th power, for some positive integer p. Again we give tight upper and lower bounds on the best possible competitive ratio of deterministic online algorithms. The competitiveness is 1 plus an alternating sum of Riemann's zeta function and tends to 1.5 as p → ∞. Finally we consider randomized online algorithms and show that, for our first objective function, no randomized strategy can achieve a competitive ratio smaller than 3/(3 -- 2/e) ≈ 1.324. For the generalized objective function we show a lower bound of 2/(2 -- 1/e) ≈ 1.225.
Starting Page	47
Ending Page	55
Page Count	9
File Format	PDF
ISBN	0898715385
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-01-12
Access Restriction	Subscribed
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