New bounds for multi-label interval routing

Abstract

Interval 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 ⌈3/2D⌉ 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( i+1√n) for k≤(1-1/3i)D. This result implies a new upper bound of ⌈(2-1/3i)D⌉ for IR using O( i+1√n) or more labels, where i is any positive integer constant. We apply the result by Kutten and Peleg 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( 3√n), 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. © 2003 Elsevier B.V. All rights reserved.