NDLI: On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Trees Under <?Pub _newline ?>the <formula formulatype="inline"><tex Notation="TeX">$K$ -Hop Interference Model

Content Provider	ACM Digital Library
Author	Hariharan, Srikanth Shroff, Ness B.
Description	Author Affiliation: Depts. of Electr. & Comput. Eng. & Comput. Sci. & Eng., Ohio State Univ., Columbus, OH, USA(At&t labs, San Ramon (Hariharan, Srikanth; At&t labs., San Ramon, CA, USA (Hariharan, Srikanth); Departments of ece and cse, The Ohio State University (Shroff, Ness B.); Shroff, Ness B.))
Abstract	We investigate the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network with a tree topology. Nodes send their packets to the tree's root sink. We consider a time-slotted system and a K-hop interference model. We characterize the existence of causal sample-path optimal scheduling policies in these networks, i.e., we wish to find a policy such that at each time-slot, for any traffic arrival pattern, the sum of the queue lengths of all the nodes is minimum among all policies. We provide an algorithm that takes any tree and K as inputs, and outputs whether a causal sample-path optimal policy exists for this tree under the K-hop interference model. We show that when this algorithm returns FALSE, there exists a traffic arrival pattern for which no causal sample-path optimal policy exists for the given tree structure. We further show that for certain tree structures, even noncausal sample-path optimal policies do not exist. We provide causal sample-path optimal policies for those tree structures for which the algorithm returns TRUE. Thus, we completely characterize the existence of such policies for all trees under the K-hop interference model. The nonexistence of sample-path optimal policies in a large class of tree structures implies that we need to study other relatively weaker metrics for this problem.
Starting Page	2458
Ending Page	2471
Page Count	14
File Format	PDF
ISSN	10636692
DOI	10.1109/TNET.2015.2464723
Volume Number	24
Issue Number	4
Journal	IEEE/ACM Transactions on Networking (TON)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-08-01
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Networks and Communications Software Computer Science Applications

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

On sample-path optimal dynamic scheduling for sum-queue minimization in trees under the K-hop interference model

On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Forests

On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Forests

Optimal Distributed Scheduling in Wireless Networks Under the SINR Interference Model

Design of scheduling algorithms for end-to-end backlog minimization in wireless multi-hop networks under $\textit{k}-hop$ interference models

On optimal dynamic scheduling for sum-queue minimization in trees

Performance of Random Access Scheduling Schemes in Multi-Hop Wireless Networks

Leveraging Physical-Layer Capabilites: Distributed Scheduling in Interference Networks With Local Views

Control of wireless networks with flow level dynamics under constant time scheduling

On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Trees Under the $K$ -Hop Interference Model

Similar Documents

On sample-path optimal dynamic scheduling for sum-queue minimization in trees under the K-hop interference model

On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Forests

On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Forests

Optimal Distributed Scheduling in Wireless Networks Under the SINR Interference Model

Design of scheduling algorithms for end-to-end backlog minimization in wireless multi-hop networks under $\textit{k}-hop$ interference models

On optimal dynamic scheduling for sum-queue minimization in trees

Performance of Random Access Scheduling Schemes in Multi-Hop Wireless Networks

Leveraging Physical-Layer Capabilites: Distributed Scheduling in Interference Networks With Local Views

Control of wireless networks with flow level dynamics under constant time scheduling

On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Trees Under the $K$ -Hop Interference Model