Worst Case Bounds for Shortest Path Interval Routing

Consider shortest path interval routing, a popular memory-balanced method for solving the routing problem on arbitrary networks. Given a network G, let IRS(G) denote the maximum number of intervals necessary to encode groups of destinations on an edge, minimized over all shortest path interval routing schemes on G. In this paper, we establish tight worst case bounds on IRS(G). More precisely for any n, we construct a network G of n nodes with IRS(G) in Theta(n), thereby improving on the best known lower bound of Omega(n / log n). We also establish a worst case bound on bounded degree networks: for any Delta >= 3 and any n, we construct a network G' of n nodes and maximum degree Delta with IRS(G') in Omega(n/(log n)^2).Nous considérons le problème du routage par intervalles de plus courts chemins, une méthode populaire et distribuée résolvant le problème du routage sur les réseaux arbritraires. Etant donné un réseau G, nous posons Irs (G) le nombre maximum d'intervalles nécessaires pour coder les groupes de destinations sur une arête, minimisé sur tous les routages par intervalles de plus courts chemins sur G. Dans cet article, nous établissons des bornes très étroite sur le pire cas pour Irs (G). Plus précisément, pour tout n, nous construisons un réseau G de n noeuds avec Irs(n) in Theta(n), améliorant par conséquent, la meilleure borne inférieure connue Omega(n/logn). Nous établissons également un pire cas pour les réseaux de degré borné : pour tout Delta >= 3 et tout n, nous construisons un réseau G\Delta de n noeuds et de degré maximum Delta avec Irs-G\Delta) in Omega(n/(log n)2)