TY - JOUR
T1 - Task-execution scheduling schemes for network measurement and monitoring
AU - Qin, Zhen
AU - Rojas-Cessa, Roberto
AU - Ansari, Nirwan
N1 - Funding Information:
This work has been partially supported by Computation and Communication: Promoting Research Integration in Science and Mathematics (C2PRISM), NSF GK-12 Project #0638423, at New Jersey Institute of Technology.
PY - 2010/2/15
Y1 - 2010/2/15
N2 - Measurement is a required process in high performance networks for efficient quality-of-service (QoS) provisioning and service verification. Active measurement is an attractive approach because the measurement traffic injected into the network can be controlled and the measurement tasks can be distributed throughout the network. However, the execution of measurement tasks in common parts of a network may face contention for resources, such as computational power, memory, and link bandwidth. This contention could jeopardize measurement accuracy and affect network services. This contention for limited resources defines a conflict between measurement tasks. Furthermore, we consider two sets of measurement tasks, those used to monitor network state periodically, called periodic tasks, and those for casual measurements issued as needed, called on-demand measurement tasks. In this paper, we propose a novel scheduling scheme to resolve contention for resources of both periodic and on-demand measurement tasks from graph coloring perspective, called ascending order of the sum of clique number and degree of tasks. The scheme selects tasks according to the ascending order of the sum of clique number and conflict task degree in a conflict graph and allows concurrent execution of multiple measurement tasks for high resource utilization. The scheme decreases the average waiting time of all tasks in periodic measurement tasks scheduling. For on-demand measurement tasks, the proposed scheme minimizes the waiting time of inserted on-demand tasks while keeping time space utilization high. In other words, the total time spent on finishing all the tasks is shortened. We evaluate our proposed schemes under different measurement task assignment scenarios through computer simulations, and compare the performance of this scheme with others that also allow concurrent task execution. The simulation results show that the proposed scheme produces effective contention resolution and low execution delays.
AB - Measurement is a required process in high performance networks for efficient quality-of-service (QoS) provisioning and service verification. Active measurement is an attractive approach because the measurement traffic injected into the network can be controlled and the measurement tasks can be distributed throughout the network. However, the execution of measurement tasks in common parts of a network may face contention for resources, such as computational power, memory, and link bandwidth. This contention could jeopardize measurement accuracy and affect network services. This contention for limited resources defines a conflict between measurement tasks. Furthermore, we consider two sets of measurement tasks, those used to monitor network state periodically, called periodic tasks, and those for casual measurements issued as needed, called on-demand measurement tasks. In this paper, we propose a novel scheduling scheme to resolve contention for resources of both periodic and on-demand measurement tasks from graph coloring perspective, called ascending order of the sum of clique number and degree of tasks. The scheme selects tasks according to the ascending order of the sum of clique number and conflict task degree in a conflict graph and allows concurrent execution of multiple measurement tasks for high resource utilization. The scheme decreases the average waiting time of all tasks in periodic measurement tasks scheduling. For on-demand measurement tasks, the proposed scheme minimizes the waiting time of inserted on-demand tasks while keeping time space utilization high. In other words, the total time spent on finishing all the tasks is shortened. We evaluate our proposed schemes under different measurement task assignment scenarios through computer simulations, and compare the performance of this scheme with others that also allow concurrent task execution. The simulation results show that the proposed scheme produces effective contention resolution and low execution delays.
KW - Active measurement
KW - Clique
KW - Graph coloring
KW - Network measurement
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=72249101295&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=72249101295&partnerID=8YFLogxK
U2 - 10.1016/j.comcom.2009.11.005
DO - 10.1016/j.comcom.2009.11.005
M3 - Article
AN - SCOPUS:72249101295
SN - 0140-3664
VL - 33
SP - 124
EP - 135
JO - Computer Communications
JF - Computer Communications
IS - 2
ER -