2-Tier Hierarchical Frame-Based Queueing for Guaranteed Delay Performance in Packet-Switched Networks

Abstract

In this letter, we introduce a novel packet scheduling algorithm, so called 2-tier Hierarchical Frame-based Queueing (2tHFQ) that provides a deterministic delay bound without sorting operation complexity. The key idea of 2tHFQ is to divide a given frame into multiple sub-frames with frame indices assigned, and then transmit input packets according to the frame index hierarchy. We analytically predict how delay bound at a node depends on the number of sub-frames. Through NS-2-based network simulations, we also demonstrate a better performance of 2tHFQ under increased traffic loads and a well-controlled packet delay by varying sub-frame numbers.