NDLI: Packet-mode policies for input-queued switches

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

On delivery times in packet networks under adversarial traffic

Object location in realistic networks

Fighting against two adversaries: page migration in dynamic networks

Packet-mode policies for input-queued switches

Balanced graph partitioning

Scheduling against an adversarial network

Sharing the cost of multicast transmissions in wireless networks

A scalable lock-free stack algorithm

Effectively sharing a cache among threads

Improved combination of online algorithms for acceptance and rejection

Online algorithms for network design

Dynamic analysis of the arrow distributed protocol

Adaptive channel queue routing on k-ary n-cubes

Simple efficient load balancing algorithms for peer-to-peer systems

Online hierarchical cooperative caching

Parallelism versus memory allocation in pipelined router forwarding engines

Bi-criteria algorithm for scheduling jobs on cluster platforms

On achieving optimized capacity utilization in application overlay networks with multiple competing sessions

Selfish load balancing and atomic congestion games

DCAS is not a silver bullet for nonblocking algorithm design

Cache-oblivious shortest paths in graphs using buffer heap

Time complexity of practical parallel steiner point insertion algorithms

Expansion properties of (secure) wireless networks

Optimal early stopping uniform consensus in synchronous systems with process omission failures

Compact name-independent routing with minimum stretch

Consistent and compact data management in distributed storage systems

New results on web caching with request reordering

Lower bounds for graph embeddings and combinatorial preconditioners

On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs

Pagoda: a dynamic overlay network for routing, data management, and multicasting

How to route and tax selfish unsplittable traffic

Efficient orchestration of sub-word parallelism in media processors

Online algorithms for prefetching and caching on parallel disks

The inherent queuing delay of parallel packet switches

The effect of faults on network expansion

Writing-all deterministically and optimally using a non-trivial number of asynchronous processors

Geometric generalizations of the power of two choices

An NC algorithm for finding a maximal acyclic set in a graph

Efficient search in unstructured peer-to-peer networks

The potential in energy efficiency of a speculative chip-multiprocessor

Packet-mode policies for input-queued switches

Content Provider	ACM Digital Library
Author	Rosén, Adi Guez, Dan Kesselman, Alex
Abstract	This paper considers the problem of packet-mode scheduling of input queued switches. Packets have variable lengths, and are divided into cells of unit length. Each packet arrives to the switch with a given deadline by which it must traverse the switch. A packet successfully passes the switch if the sequence of cells comprising it is contiguously transmitted out of the switch before the packet's deadline expires. A packet transmission may be preempted and restarted from the beginning later. The scheduling policy has to decide at each time step which packets to serve. The problem is online in nature, and thus we use competitive analysis to measure the performance of our scheduling policies.First we consider the case where the goal of the switch policy is to maximize the total number of successfully transmitted packets. We derive two algorithms achieving the competitive ratios of (22√log L +1) and N+ 1, respectively, where L is the ratio between the longest and the shortest packet lengths and N is the number of input/output ports. We also show that any deterministic online algorithm has a competitive ratio of at least (⌊log L⌋ + 1, N).Then we study the general case in which each packet has an intrinsic value representing its priority, and the goal is to maximize the total value of successfully transmitted packets. We derive an algorithm which achieves a competitive ratio of 2κ+2√κ+1/2+ (2κ+√κ+1/2+1) (√κ+1/2+3), where κ is the ratio between the maximum and the minimum value per cell. We note that [4] gives a lower bound of Ω(κ) on the performance of any deterministic online algorithm. In particular, our algorithm achieves a competitive ratio of approximately 11.123 for κ=1, which improves upon the previous best-known upper bound for this problem [17].We complement our results by studying the offline version of the problem, which is NP-hard We give a pseudo-polynomial 3-approximation algorithm for the general case and a polynomial 3-approximation algorithm for the case of unit value packets.
Starting Page	93
Ending Page	102
Page Count	10
File Format	PDF
ISBN	1581138407
DOI	10.1145/1007912.1007927
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-06-27
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Input-queued switches Competitive analysis Packet-mode scheduling
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