New bounds for multi-label interval routing

AbstractInterval routing (IR) is a space-efficient routing method for computer networks. For longest routing path analysis, researchers have focused on lower bounds for many years. For any n-node graph G of diameter D, there exists an upper bound of 2D for IR using one or more labels, and an upper bound of ⌈32D⌉ for IR using O(nlogn) or more labels. We present two upper bounds in the first part of the paper. We show that for every integer i>0, every n-node graph of diameter D has a k-dominating set of size O(ni+1) for k⩽(1−13i)D. This result implies a new upper bound of ⌈(2−13i)D⌉ for IR using O(ni+1) or more labels, where i is any positive integer constant. We apply the result by Kutten and Peleg [8] to achieve an upper bound of (1+α)D for IR using O(n/D) or more labels, where α is any constant in (0,1). The second part of the paper offers some lower bounds for planar graphs. For any M-label interval routing scheme (M-IRS), where M=O(n), we derive a lower bound of [(2M+1)/(2M)]D−1 on the longest path for M=O(n3), and a lower bound of [(2(1+δ)M+1)/(2(1+δ)M)]D, where δ∈(0,1], for M=O(n). The latter result implies a lower bound of Ω(n) on the number of labels needed to achieve optimality