二分探索でホップ数を調べるスクリプトを書いてみた

# 概要

ホップ数を調べたい時はtracerouteを使うのが一般的(途中の経路も分かる)が、たまにtracerouteではホップ数がわからないときもある。

そういったホストに対してpingを使うとホップ数を調べることができる場合があるが、pingのオプションを1つずつ変えながら手作業で試すのが面倒だったので、二分探索でホップ数を調べるスクリプトを書いてみた。

追記:
恥ずかしながらコメントを頂いて初めて知りましたが、`traceroute -I`でICMPを使ったtracerouteができます。
ただ、root権限が必要ですので、一応pingを使った方法も価値はありそうです。


# スクリプト

~~~bash:get-hops.sh
#!/bin/bash

DEST=${1:-8.8.8.8}
MAXHOP=${2:-31}
IPV="-4"

# Ctrl + Cで中断
trap 'echo Breaked; exit 2' 2

# そもそも届かなければ終了
if ! ping -c 1 "${IPV}" "${DEST}" > /dev/null; then
  echo "Cannot connect to ${DEST}"
  exit 1
fi

# 2分探索
MAX=`expr ${MAXHOP} + 1`
MIN=1
while [ $MIN -lt $MAX ]
do
  i=`expr '(' $MIN + $MAX ')' / 2`
  echo -ne "(current, min, max) = ($i , $MIN , $MAX)\t" >&2
  if ping -c 1 -t $i "${IPV}" "${DEST}" > /dev/null; then
    echo "Reached" >&2
    MAX=$i
  else
    echo "Didn't reach" >&2
    MIN=`expr $i + 1`
  fi
done

if [ "$MAX" -gt "${MAXHOP}" ]; then
  echo "Hop count exceed ${MAXHOP}"
  exit 1
fi

echo $MAX
~~~

https://gist.github.com/330k/2e9f22721e1577c25a1d2cc122cc0aa8

## 使い方

~~~
$ ./get-hops.sh (調べたいホストのFQDN or IPアドレス)
~~~

2番目の引数に最大ホップ数を指定可能。

## 動作確認

Google Public DNS (8.8.8.8)に対してtracerouteと自作スクリプトの結果を比較してみる。

~~~text
$ traceroute 8.8.8.8
traceroute to 8.8.8.8 (8.8.8.8), 30 hops max, 60 byte packets
 1  _gateway (***.***.***.***)  2.681 ms  2.634 ms  3.592 ms
 2  10.168.0.1 (10.168.0.1)  37.969 ms  38.086 ms  44.399 ms
 3  10.140.32.82 (10.140.32.82)  47.688 ms  47.989 ms  48.185 ms
 4  10.140.31.6 (10.140.31.6)  47.780 ms  47.767 ms  48.197 ms
 5  175.130.252.69 (175.130.252.69)  48.375 ms  48.538 ms  48.521 ms
 6  175.130.252.94 (175.130.252.94)  48.641 ms  27.001 ms  27.206 ms
 7  111.87.218.85 (111.87.218.85)  30.860 ms  31.027 ms  37.544 ms
 8  27.86.45.209 (27.86.45.209)  40.683 ms  41.130 ms  41.449 ms
 9  27.86.44.190 (27.86.44.190)  37.276 ms 27.85.230.54 (27.85.230.54)  37.235 ms 27.86.45.222 (27.86.45.222)  37.189 ms
10  72.14.242.21 (72.14.242.21)  36.193 ms  36.359 ms  36.874 ms
11  * * *
12  dns.google (8.8.8.8)  44.492 ms  26.816 ms  26.300 ms
~~~

IPは一部伏せてます。

~~~text
$ ./get-hops.sh 8.8.8.8
(current, min, max) = (16 , 1 , 32)	Reached
(current, min, max) = (8 , 1 , 16)	Didn't reach
(current, min, max) = (12 , 9 , 16)	Reached
(current, min, max) = (10 , 9 , 12)	Didn't reach
(current, min, max) = (11 , 11 , 12)	Didn't reach
12
~~~

私の環境からはどちらもホップ数は12となったので、きちんと測定できている模様。

## tracerouteがうまく動作しないときの例

たとえば`yahoo.co.jp`に対してはtracerouteでホップ数が分からない。

~~~
$ traceroute yahoo.co.jp
traceroute to yahoo.co.jp (183.79.135.206), 30 hops max, 60 byte packets
 1  _gateway (***.***.***.***)  0.853 ms  1.003 ms  1.604 ms
 2  10.168.0.1 (10.168.0.1)  28.750 ms  36.552 ms  43.601 ms
 3  10.140.32.90 (10.140.32.90)  46.734 ms  46.864 ms  46.843 ms
 4  10.140.31.6 (10.140.31.6)  46.922 ms  47.160 ms  47.142 ms
 5  175.130.252.69 (175.130.252.69)  47.110 ms  47.342 ms  47.037 ms
 6  175.130.252.94 (175.130.252.94)  47.283 ms  45.906 ms  45.907 ms
 7  111.87.218.69 (111.87.218.69)  45.856 ms 111.87.218.85 (111.87.218.85)  29.374 ms 111.87.218.69 (111.87.218.69)  23.853 ms
 8  27.80.241.61 (27.80.241.61)  34.738 ms  30.564 ms  34.052 ms
 9  27.86.41.86 (27.86.41.86)  34.112 ms 27.85.134.50 (27.85.134.50)  39.771 ms 27.86.41.86 (27.86.41.86)  47.761 ms
10  210.132.124.210 (210.132.124.210)  47.944 ms  51.193 ms  47.883 ms
11  124.83.228.58 (124.83.228.58)  59.370 ms  59.146 ms  59.309 ms
12  124.83.252.178 (124.83.252.178)  51.212 ms  51.175 ms  43.205 ms
13  114.111.64.206 (114.111.64.206)  46.411 ms  43.513 ms  43.612 ms
14  100.96.24.146 (100.96.24.146)  50.902 ms  54.959 ms  48.502 ms
15  * * *
16  * * *
17  * * *
18  * * *
19  * * *
20  * * *
21  * * *
22  * * *
23  * * *
24  * * *
25  * * *
26  * * *
27  * * *
28  * * *
29  * * *
30  * * *
~~~

pingを使うとホップ数が16と分かる。

~~~
$ ./get-hops.sh yahoo.co.jp
(current, min, max) = (16 , 1 , 32)	Reached
(current, min, max) = (8 , 1 , 16)	Didn't reach
(current, min, max) = (12 , 9 , 16)	Didn't reach
(current, min, max) = (14 , 13 , 16)	Didn't reach
(current, min, max) = (15 , 15 , 16)	Didn't reach
16
~~~