Hack109のブログ

ネットワーク、プログラミングなどで学んだことや試してみたことを投稿していきます。

一次元の累積和について【プログラミング】【競プロ】

はじめに

一次元の累積和は、このような問題で使用できます。

【例題】
N日間にわたって開催された展示会について、i日目にはAi人が来場しました。 この展示会について、Q個の質問に答えるプログラムを作成してください。

  • 展示会におけるL1日目からR1日目までの総来場数は?  
      ・・・  
  • 展示会におけるLQ日目からRQ日目までの総来場数は?   

制約

  • 1 <= N <= 100000
  • 1 <= A <= 10000
  • 1 <= L <= R <= N

累積和(一次元)の使いどころ

一列に並べられた数値について、x番目からy番目に格納されている値の総数を算出するときに使用できます。

累積和(一次元)のアルゴリズム

i日間の展示会の総来場数を下記とします。
累積和のアルゴリズムをしない場合、4日目から8日目の総来場数を求める場合は、
A4+A5+A6+A7+A8 で算出されます。

例題ではQ個の質問に答えるプログラムを作成することを求められています。 質問が1つならともかく、複数の質問に答えなければならないとなると、L,R日目に入力される値によっては実行時間が大きくなります。 (1つ目の質問が1日目から17日目、2つ目の質問が2日目から16日目みたいに…)

そこで、累積和のアルゴリズムを用いて効率的に算出していきます。

累積和により、i日目の総来場数を算出する。

L日目からR日目までの総来場数を算出する前に、i日目までの累計来場者数Siをあらかじめ計算しておきます。

L日目~R日目の総来場数は..?

i日目までの累計来場者数が分かれば、L日目からR日目の総来場者数は下記の計算で算出できます。

(R日目までの累計来場者数SR) - (L-1日目までの累計来場者数SL-1)

あらかじめi日目までの累計来場者数が算出されていることで、 例題のようにL日目からR日目までの総来場者数をQ個質問されていても、 総来場者数の計算は一度の計算で済みます。

#include <iostream>
#include <vector>

using namespace std;

int main() {

    int N = 0;
    int Q = 0;


    cin >> N >> Q;


    int offset = 1;
    vector<int> A(N + offset, 0);
    vector<int> S(N + offset, 0);
    vector<int> L(Q + offset, 0);
    vector<int> R(Q + offset, 0);

    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int j = 1; j <= Q; j++) cin >> L[j] >> R[j];

    for (int i = 1; i <= N; i++) S[i] = S[i - 1] + A[i];

    for (int j = 1; j <= Q; j++) {
        cout << S[R[j]] - S[L[j] - 1] << endl;
    }

    return 0;
}

さいごに

まとめ

一次元の累積和のアルゴリズムは、一列に並べられた数値について、x番目からy番目に格納されている値の総数を算出するときに使用できます。

今後

今回は一次元の累積和についての解説でしたが、次は二次元の累積和についても取り上げたいと思います。

二分探索について【プログラミング】【競プロ】

はじめに

二分探索は、探索範囲を半分ずつ絞りながら正解データを特定するアルゴリズムです。 下記のような問題に使用できます。 
 
【例題】  小さい順に並べられているN個のデータA=[A1 ~AN]があります。要素XはAの何番目に存在するかを出力してください。 
 
全探索でも解けますが、二分探索で実装してみます。 こちらが二分探索を用いた解法です。

#include <iostream>
#include <vector>

using namespace std;


int BinarySearch(vector<int> a, int x, int n) {

    int L = 1;
    int R = n;
    int M = 0;

    while (L <= R) {

        M = (L + R) / 2;

        if (a[M] == x)
            return M;

        if (a[M] < x)
            L = M + 1;

        if (a[M] > x)
            R = M - 1;
    }

    return NULL;
}

int main(){

    int N = 0;
    int X = 0;
    int ans = 0;


    cin >> N >> X;

    int offset = 1;
    vector<int> A(N + offset, 0);

    for (int i = 1; i <= N; i++)
        cin >> A[i];

    ans = BinarySearch(A, X, N);

    if (ans == NULL)
        cout << "No" << endl;
    else
        cout << ans << endl;

    return 0;
}

 

二分探索が可能となる条件

二分探索を行うための条件は下記です。 
 
・配列が小さい順になっている。 
 
そのため、小さい順になっていない配列に対して二分探索を行う場合は、配列を小さい順に整列するソートを行う必要があります。  

二分探索のアルゴリズム

探索範囲を半減させる。

配列の中央にあたる値と探索している値の大小関係を確認し、探索範囲を半減させていきます。 要素数17の配列から19を探索する流れを下記に示します。 1巡目では、インデックス番号9が真ん中の中央にあたるため、そこに格納されている値と探索している値の大小関係を比較します。結果、探索している値のほうが小さいので、インデックス番号1~8のどこかに格納されていることがわかります。 2巡目、3巡目でも同じ処理を行い、探索範囲を半分に絞り続けます。 4巡目の探索で、配列の5番目に19が格納されていることがわかりました。

49を探索した場合を下記に示します。探索範囲の中央の値が探索している値だった場合、その時点で探索完了となります。

二分探索を実装する。

二分探索を実装していきます。例題を再度提示します。

【例題】 小さい順に並べられているN個のデータA=[A1 ~AN]があります。要素XはAの何番目に存在するかを出力してください。  
データ数N, 探索したい値X, 配列の値Aを入力していきます。

    int N = 0;
    int X = 0;
    int ans = 0;


    cin >> N >> X;

    int offset = 1;
    vector<int> A(N + offset, 0);

    for (int i = 1; i <= N; i++)
        cin >> A[i];

 
入力した値を、二分探索を行う関数に引数として渡します。

 ans = BinarySearch(A, X, N);

 
二分探索の関数の中身です。L,R,Mはインデックス番号の値が格納されます。 
L:探索範囲のインデックス番号 最小値 
R:探索範囲のインデックス番号 最大値 
M:探索範囲のインデックス番号  中央値 

int BinarySearch(vector<int> a, int x, int n) {

    int L = 1;
    int R = n;
    int M = 0;

    while (L <= R) {

        M = (L + R) / 2;

        if (a[M] == x)
            return M;

        if (a[M] < x)
            L = M + 1;

        if (a[M] > x)
            R = M - 1;
    }

    return NULL;
}

 
中央値については、 M = (L + R)/2 で算出されます。探索範囲のデータ数が偶数だった場合、中央値の算出は切り捨てになります。 値が見つかればMの値を返します。 値が見つからなかった場合、Lの値がRを上回るため、ループから抜けるかたちとなり、NULL値を返します。

 while (L <= R) {

        M = (L + R) / 2;

        if (a[M] == x)
            return M;

        if (a[M] < x)
            L = M + 1;

        if (a[M] > x)
            R = M - 1;
    }

    return NULL;

 
探索完了後の処理です。探索していた値が見つからなければNoを出力します。

 ans = BinarySearch(A, X, N);

    if (ans == NULL)
        cout << "No" << endl;
    else
        cout << ans << endl;

 
全体のコードは以下です。

#include <iostream>
#include <vector>

using namespace std;


int BinarySearch(vector<int> a, int x, int n) {

    int L = 1;
    int R = n;
    int M = 0;

    while (L <= R) {

        M = (L + R) / 2;

        if (a[M] == x)
            return M;

        if (a[M] < x)
            L = M + 1;

        if (a[M] > x)
            R = M - 1;
    }

    return NULL;
}

int main(){

    int N = 0;
    int X = 0;
    int ans = 0;


    cin >> N >> X;

    int offset = 1;
    vector<int> A(N + offset, 0);

    for (int i = 1; i <= N; i++)
        cin >> A[i];

    ans = BinarySearch(A, X, N);

    if (ans == NULL)
        cout << "No" << endl;
    else
        cout << ans << endl;

    return 0;
}

 

二分探索の応用例

二分探索の応用例をいくつか示します。

X以下の最大値

【例題】 小さい順に並べられているN個のデータA=[A1 ~AN]があります。要素X以下の最大値にあたるAの値を出力してください。  

#include <iostream>
#include <vector>

using namespace std;


int BinarySearch(vector<int> a, int x, int n) {

    int L = 1;
    int R = n;
    int M = 0;

    while (L <= R) {

        M = (L + R) / 2;

        if (a[M] == x)
            return M;

        if (a[M] < x)
            L = M + 1;

        if (a[M] > x)
            R = M - 1;
    }

    return R;
}

int main(){

    int N = 0;
    int X = 0;
    int ans = 0;


    cin >> N >> X;

    int offset = 1;
    vector<int> A(N + offset, 0);

    A[0] = NULL;
    for (int i = 1; i <= N; i++)
        cin >> A[i];

    ans = BinarySearch(A, X, N);

    if (ans == NULL)
        cout << "No" << endl;
    else
        cout << A[ans] << endl;

    return 0;
}

 

X以上の最小値

【例題】 小さい順に並べられているN個のデータA=[A1 ~AN]があります。要素X以上の最小値にあたるAの値を出力してください。  

#include <iostream>
#include <vector>

using namespace std;


int BinarySearch(vector<int> a, int x, int n) {

    int L = 1;
    int R = n;
    int M = 0;

    while (L <= R) {

        M = (L + R) / 2;

        if (a[M] == x)
            return M;

        if (a[M] < x)
            L = M + 1;

        if (a[M] > x)
            R = M - 1;
    }

    if (L > n)
        return NULL;
    else
        return L;
}

int main(){

    int N = 0;
    int X = 0;
    int ans = 0;


    cin >> N >> X;

    int offset = 1;
    vector<int> A(N + offset, 0);

    for (int i = 1; i <= N; i++)
        cin >> A[i];

    ans = BinarySearch(A, X, N);

    if (ans == NULL)
        cout << "No" << endl;
    else
        cout << A[ans] << endl;

    return 0;
}

 

単調増加の関数

【例題】 正の整数Nが与えられます。N=x3を満たす正の実数xを出力してください。ただし、絶対誤差が0.001以下であれば正解とします。  
 
探索対象のデータが他の要素に対して強い正の相関関係であれば、二分探索を用いることで正解データを特定できます。

#include <iostream>

using namespace std;

double Function(double x) {
    return x * x * x;
}

int main(){

    double N = 0;

    double x_H = 1000000000;
    double x_L = 0;
    double x_M = 0;
    double answer = 0;

    cin >> N;

    while (x_L < x_H) {

        x_M = (x_L + x_H) / 2;
        answer = Function(x_M);

        if (answer >= (N - 0.001) && answer <= (N + 0.001)) {

            cout << x_M << endl;
            break;
        }

        if (answer < N)
            x_L = x_M;
        if (answer > N)
            x_H = x_M;
    }

    return 0;
}

 

まとめ

二分探索は、探索範囲を半分ずつ絞りながら正解データを特定するアルゴリズムです。 条件として、小さい順に並べられているデータが必要になります。 そのため応用例として、探索対象のデータが他の要素に対して強い正の相関関係であれば、二分探索を用いることで正解データを特定できます。

bit全探索について【プログラミング】【競プロ】

はじめに

bit全探索は、bit演算を使った全探索アルゴリズムの一種です。 部分和問題に応用できます。 例としては、下記のような問題です。

【例題】 N枚のカードがあり、カードA1 ~ANにそれぞれ異なる値段がつけられています。購入するカードをいくつか選んだ場合、購入金額がS円となる組み合わせは存在しますか?

bit全探索を用いた解法です。

#include <iostream>
#include <vector>

using namespace std;

int main(){

    int N = 0;
    int S = 0;

    cin >> N;
    cin >> S;


    vector<int> A(N, 0);

    for (int i = 0; i < N; i++)
        cin >> A[i];

    int sum = 0;
    bool answer = false;

    for (int pattern = 0; pattern < (1 << N); pattern++) {

        sum = 0;
        
        for (int bit = 0; bit < N; bit++) {

            if (pattern & (1 << bit)) {
                sum += A[bit];
            }
        }

        if (sum == S) {
            answer = true;
            break;
        }
    }

    if (answer == true)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

bit全探索のアルゴリズム

2進数表記による各組み合わせの導出

bit全探索のアルゴリズムでは2進数を用います。

桁数をデータ数とするため、データ数をNとすると組み合わせの総数は2Nとなります。 N=3の場合は、8つの組み合わせを0~7と表します。 さらに、0~7を2進数表記することで、1となっている桁を選択したデータと考えることができます。

カードAの値段それぞれをA1=30円,A2=40円,A3=20円とし、購入金額Sが50円となる組み合わせを見つける場合、購入金額がSとなる組み合わせが見つかるまで0から一つずつ確認していくことになります。この場合は6つ目の組み合わせで見つかりました。

bit全探索の実装

bit全探索を実装していきます。例題を再度提示します。

【例題】 N枚のカードがあり、カードA1 ~ANにそれぞれ異なる値段がつけられています。購入するカードをいくつか選んだ場合、購入金額がS円となる組み合わせは存在しますか?

 
まずは、カードの枚数N、購入金額S、カードのそれぞれの値段A1 ~ANを入力していきます。

    int N = 0;
    int S = 0;

    cin >> N;
    cin >> S;


    vector<int> A(N, 0);

    for (int i = 0; i < N; i++)
        cin >> A[i];

 
入力後、bit全探索の処理に入っていきます。全探索の基本的な処理は下記のとおりです。

    int sum = 0;
    bool answer = false;

    for (int pattern = 0; pattern < (1 << N); pattern++) {

        sum = 0;
        
        for (int bit = 0; bit < N; bit++) {


            if (pattern & (1 << bit)) {
                sum += A[bit];
            }
        }


        if (sum == S) {
            answer = true;
            break;
        }
    }

各組み合わせごとの購入金額をsum, 判定結果をanswerとして初期化します。

    int sum = 0;
    bool answer = false;

bit全探索では、選択肢の数に基づいて総組み合わせ数を算出する必要がありますが、シフト演算子<<を使用することで簡単に算出することができます。<<は左シフトで、2進数であらわされたデータを指定した分、左にシフトします。

カードAが3枚の場合は、3桁の2進数で表すことができる数値は0~7、つまり総組み合わせ数は8であり、1 << 3に一致します。 よって、N枚のカードから購入するカードを選択する場合、総組み合わせ数は 1 << Nで表すことができます。 forを使うことで、N枚のカードから選択する場合の組み合わせを一つずつ確認できます。patternが各組み合わせを示す数値となります。

    for (int pattern = 0; pattern < (1 << N); pattern++) {

        //各組み合わせを確認
    }

各組み合わせの購入金額を算出します。 まず、組み合わせを示す数値patternに対して、2進数で表記した場合に「1」となっている桁を探します。「1」となっている桁が見つかった場合、その桁に対応するデータを持ってきて加算処理を行っています。 この処理によって、sumに各組み合わせの購入金額が算出されます。

    sum = 0;
        
    for (int bit = 0; bit < N; bit++) {


        if (pattern & (1 << bit)) {
            sum += A[bit];
        }
    }

算出された購入金額がSと一致した場合、判定結果をtrueとし、ループ分を抜けます。

    if (sum == S) {
        answer = true;
        break;
    }

最後に判定結果を出力します。

    if (answer == true)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

全体のコードは以下です。

#include <iostream>
#include <vector>

using namespace std;

int main(){

    int N = 0;
    int S = 0;

    cin >> N;
    cin >> S;


    vector<int> A(N, 0);

    for (int i = 0; i < N; i++)
        cin >> A[i];

    int sum = 0;
    bool answer = false;

    for (int pattern = 0; pattern < (1 << N); pattern++) {

        sum = 0;
        
        for (int bit = 0; bit < N; bit++) {

            if (pattern & (1 << bit)) {
                sum += A[bit];
            }
        }

        if (sum == S) {
            answer = true;
            break;
        }
    }

    if (answer == true)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

まとめ

 bit全探索により、N個のものに対して「選ぶ」「選ばない」、「買う」「買わない」といった選択をした場合の探索を行うことができます。(部分和問題)

N個から選択する場合の総組み合わせ数は2N通りあります。

N個から選択する場合の組み合わせを2進数のN桁の値で表すことで、「選ぶ」「選ばない」を「1」「0」と考えることができます。

ルータのルーティング,ネットワーク構成を関西の駅や路線で例えて考える話

 



はじめに

ここ最近で、VPNルータを使ったルーティングの動作を確認していますが、ルータの経路情報とかネットワーク構成とか、何か身近なものに例えられないかと考えました。

ネットワーク構成図

前回、スタティックルーティングを実施したときのネットワーク構成図をもとに、考えてみます。

 

hack109.hatenablog.com

ネットワーク構成 経路情報を身近なもので例えると...

ネットワーク構成の例え

ネットワーク構成の例えとして、ぱっと浮かんだのは駅や路線です。

大阪環状線

各機器をそれぞれ下記のように考えてみます。

PCVPNルータは駅として例えられます。違いとしては、VPNルータは乗り換えのある駅で、PCは特に乗り換えのない駅です。

ネットワークは路線として考えられます。ネットワーク全体のアドレスを指すネットワークアドレスを京阪線JR線などの路線として考えることで、そのネットワークに属しているルータやPCを駅として考えられます。

 

VPNルータ       

(乗り換えあり)         

PC        

(乗り換えなし)     

ネットワーク    

路線          

 

経路情報の例え

ルータが持っている経路情報を何かに例えるとなると、駅員さんの路線に関する知識や路線図がそれにあたると思います。

駅員さん

経路情報は、VPNルータが記憶している目標の機器にデータを送るための経路になります。

電車で例えると、目標の駅までにいくには次にどの路線に乗り換える必要があるのかという情報を記憶している必要があるわけです。

駅を利用する客(データ)がどの路線に乗り換えるのかを把握していなくても、路線図を見たり駅員さんに聞いたりすることで、次に乗る路線が分かるわけです。

 

経路情報

駅員さんの路線に関する知識

乗客

通信データ

 

関西の駅や路線でネットワーク構成図を作る。

では、実際の駅や路線で例えて、ネットワーク構成図を作ってみたいと思います。

今回は関西の路線で考えてみます。

 

スタート,目標の駅はこちらです。

スタート      

大阪 岸和田駅 (南海線)

目的地       

京都 出町柳駅 (京阪線)

 

目的地までの乗り換えの方法はいろいろありますが、今回はこちらで考えます。多分この例がわかりやすいです。

乗り換え

では、ネットワーク構成図に落とし込んでみましょう。

駅や路線を例として考えるネットワーク構成図

イメージしやすくなったかなと思います。駅名は同じでも、どの路線の駅かでどこに行けるかが変わります。ルータを経由して別のネットワークに転送されるところを、その部分でうまく例えられました。このように見てみると面白いですね。

 

最後に

まとめ

 今回はルータのルーティングについて、実際の路線や駅に例えて考えてみました。ここまでの記事を読んで、全体の路線図みればどこへでも行けるだろうとか、スタート地点の駅に関西の路線を把握している駅員さんもいるのではといった意見があるかもしれませんが、そこはまあ...あくまでイメージとして。

 プログラミングとかも、変数のアドレスの話が出てきたときに、家の住所を変数のアドレスと例えて説明している記事や参考書が見られます。難しそうな話が出てきたとき、身近なもので例えて自分なりに解釈することができれば、イメージしやすくなりますし、理解が深まると思います。

素材

イラストAC

無料イラスト・フリー素材なら「イラストAC」 (ac-illust.com)

いらすとや

かわいいフリー素材集 いらすとや (irasutoya.com)

 

TP-Link ER605でスタティックルーティングを体験してみた。

はじめに

前回は、1つのルータを使ってルーティングを体験しました。

hack109.hatenablog.com

 

1つのルータに接続されている隣のネットワークに接続する際は、ルータに対してVLANの設定を実施すれば、直接接続のルート情報は自動的にルーティングテーブル(経路情報)に登録されていました。

しかし、ルータを2つ使用し、接続されている隣のルータで管理しているネットワークに接続するためには、

目標のネットワークへの経路情報をルーティングテーブルに追加する必要があります。

ネットワーク構成の変更が発生するたびに、ルータのルーティングテーブルを手動で修正する方法をスタティックルーティングと呼びます。

そこで今回は、実際にルータを2つ使用し、スタティックルーティングを行うことで隣のルータのネットワークに接続できるかを確認してみたいと思います。

 

目標

  • ルータを2つ使用し、スタティックルーティングを行うことで隣のルータのネットワークに接続できるかを確認する。
  • スタティックルーティングの方法を学ぶ。

使用機器・ネットワーク構成

 

ゲートウェイとして使用する機器

tp-link ER605ゲートウェイとして使用します。今回は2つ使用します。

ゲートウェイとして使用する機器

各ネットワークで使用する機器

カテゴリ

機種名

IPアドレス

PC①

DESKTOP-FLK5IJ4(OS:Windows)

192.168.0.2/24

PC②

Raspberry pi

192.168.11.2/24

 

ネットワーク構成図

ルータ同士を接続し、各ルータにPCを接続します。PC①,PC②が双方にping通信できることを確認します。

ネットワーク構成図

スタティックルーティング 設定方法

著作権の問題があるため、スクショなしで説明いたします。ご了承ください。

 

隣のルータとのネットワークを構成するためには、各ルータが同じネットワークに属している必要があります。今回の例では、192.168.3.0のネットワークが該当します。

隣のルータとの接続

VLAN設定

各ルータのVLANの設定を確認していきます。PCに接続するポートについてはDHCPは有効無効のどちらでも問題ありません。ルータ同士を接続するネットワークについてはDHCPは不要のため、無効としておきます。PC②のルータ同士の接続に使用するポートがVlan3となっていますが、特に影響はありません。

 

PC①側のLAN設定

ID

Name

Vlan

IP Address

Subnet Mask

DHCP Server

DHCP Relay

1

ToRouter

2

192.168.3.21

255.255.255.0

Disabled

Disabled

2

LAN

1

192.168.0.1

255.255.255.0

Enabled

Disabled

 

PC①側のVLAN設定

ID

VLAN ID

Name

Ports

Description

1

1

vlan1

2(UNTAG)

LAN1

2

2

vlan2

4(UNTAG)

ToRouter

 

 

PC②側のLAN設定

ID

Name

Vlan

IP Address

Subnet Mask

DHCP Server

DHCP Relay

1

ToRouter

3

192.168.3.22

255.255.255.0

Disabled

Disabled

2

LAN

1

192.168.11.1

255.255.255.0

Enabled

Disabled

 

PC②側のVLAN設定

ID

VLAN ID

Name

Ports

Description

1

1

vlan1

2(UNTAG)

LAN1

2

3

vlan3

4(UNTAG)

ToRouter

スタティックルーティング 設定前 動作確認

スタティックルーティング設定前の動作を確認してみます。ルータに直接接続されているネットワークと違い、別のルータのネットワークに接続するには、VLANの設定だけではつながりません。

 

PC①→PC② ping通信

C:>ping 192.168.11.2

 

192.168.11.2 ping を送信しています 32 バイトのデータ:

要求がタイムアウトしました。

要求がタイムアウトしました。

要求がタイムアウトしました。

要求がタイムアウトしました。

 

192.168.11.2 ping 統計:

パケット数: 送信 = 4、受信 = 0、損失 = 4 (100% の損失)

 

PC②→PC① ping通信

$ ping 192.168.0.2
PING 192.168.0.2 (192.168.0.2) 56(84) bytes of data.
From 169.254.11.21 icmp_seq=1 Destination Net Unreachable
From 169.254.11.21 icmp_seq=2 Destination Net Unreachable
From 169.254.11.21 icmp_seq=3 Destination Net Unreachable
From 169.254.11.21 icmp_seq=4 Destination Net Unreachable

スタティックルーティング 設定手順

スタティックルーティングを行っていきます。

 

まず、下記の手順でスタティックルーティングを行う画面に移行します。

①メニューより、Transmission→Routingを選択

Static Routeタブを選択

 

次に設定を行います。

結論から話しますと、各ルータで下記のように設定します。

VPNルータ①

ID

Name

Destination IP

Subnet Mask

Next Hop

Interface

Metric

Status

1

Routing

192.168.11.0

255.255.255.0

192.168.3.22

ToRouter

0

Enabled

 

VPNルータ②

ID

Name

Destination IP

Subnet Mask

Next Hop

Interface

Metric

Status

1

Routing

192.168.0.0

255.255.255.0

192.168.3.21

ToRouter

0

Enabled

ネットワーク構成図

一つずつ意味を確認していきます。

このうち、特に重要になるのはDestination IPNext Hopになります。

Name

経路の名称

Destination IP

目標となるネットワークアドレス

Subnet Mask

サブネットマスク。ネットワーク部とホスト部を識別する。

Next Hop

目標のネットワークアドレスに接続するために経由しなければならないルータのIPアドレス

Interface

他のルータを経由するときに使用する自分のルータのLANポートの名称(VLANの設定参照)

Metric

ルータの優先度であり、値が小さいほど優先度が高くなる。(0推奨)

Status

Enabled:有効

Disable:無効

 

VPNルータ①を例に説明します。

Destination IPでは、目標となる機器が属しているネットワークのネットワークアドレスを設定します。

PC①から見ると、PC②(192.168.11.2)と通信したいため、PC②が属しているネットワークアドレスである「192.168.11.0」を設定します。 

 Next Hopでは、目標のネットワークアドレスに行くために経由しなければならないルータのIPアドレスを設定します。VPNルータ①からみてPC➁にデータを送信するには、まずはVPNルータ②を経由する必要があります。そのため、VPNルータ①をVPNルータ②と同じネットワークに接続し、「PC②にデータを送信するためにはまずVPNルータ②のアドレスにデータを送信する。」と 経路を記憶させる必要があります。VPN①からみてVPNルータ②のアドレスは192.168.3.22になるため、そのアドレスをNext Hopに設定します。

これらの設定を行うことでVPNルータ①は、PC②を目標とした場合の経路情報を覚えることができます。

VPNルータ①におけるDestination IP, Next Hop

ルーティングテーブルを確認してみます。

Routing Tableタブを選択

Refreshをクリック

 

スタティックルーティングで設定された経路情報が追加されていることが分かります。

どちらかのルータの設定が欠けていると相互に通信ができません。

 

VPNルータ①のルーティングテーブル

ID

Destination IP

Subnet Mask

Next Hop

Interface

Metric

1

192.168.11.0

255.255.255.0

192.168.3.22

ToRouter

0

2

127.0.0.0

255.255.255.0

0.0.0.0

lo

0

3

192.168.0.0

255.255.255.0

0.0.0.0

LAN

0

4

192.168.3.0

255.255.255.0

0.0.0.0

ToRouter

0

 

 

VPNルータ②のルーティングテーブル

ID

Destination IP

Subnet Mask

Next Hop

Interface

Metric

1

192.168.0.0

255.255.255.0

192.168.3.21

ToRouter

0

2

127.0.0.0

255.255.255.0

0.0.0.0

lo

0

3

192.168.3.0

255.255.255.0

0.0.0.0

ToRouter

0

4

192.168.0.0

255.255.255.0

0.0.0.0

LAN

0

 

スタティックルーティング 設定後 動作確認

ルーティングテーブルを設定し終えたところで、再度結果を確認してみます。

ping通信にて問題なく応答されていることを確認しました。

 

PC①→PC② ping通信

C:>ping 192.168.11.2

192.168.11.2 に ping を送信しています 32 バイトのデータ:
192.168.11.2 からの応答: バイト数 =32 時間 =2ms TTL=62
192.168.11.2 からの応答: バイト数 =32 時間 =2ms TTL=62
192.168.11.2 からの応答: バイト数 =32 時間 =2ms TTL=62
192.168.11.2 からの応答: バイト数 =32 時間 =2ms TTL=62

192.168.11.2 の ping 統計:
    パケット数: 送信 = 4、受信 = 4、損失 = 0 (0% の損失)、
ラウンド トリップの概算時間 (ミリ秒):
    最小 = 2ms、最大 = 2ms、平均 = 2ms

 

PC②→PC① ping通信

$ ping 192.168.0.2
PING 192.168.0.2 (192.168.0.2) 56(84) bytes of data.
64 bytes from 192.168.0.2: icmp_seq=1 ttl=126 time=2.31 ms
64 bytes from 192.168.0.2: icmp_seq=2 ttl=126 time=2.30 ms
64 bytes from 192.168.0.2: icmp_seq=3 ttl=126 time=2.37 ms
64 bytes from 192.168.0.2: icmp_seq=4 ttl=126 time=2.42 ms
64 bytes from 192.168.0.2: icmp_seq=5 ttl=126 time=2.32 ms
64 bytes from 192.168.0.2: icmp_seq=6 ttl=126 time=2.38 ms

 

さいごに

まとめ

今回はスタティックルーティングの動作を確認しました。成功してみると設定自体はあまり難しくないですが、私は結構苦戦しました。というのも、設定はあっているのにLANケーブルをさす場所を間違えており、Ping通信がうまくいかず、解決に時間がかかりました。。。うまくいかない場合、ハード側で問題ないかを確認するくせを付けておく必要があると思います。

今後

Windows PC側でroute add経路情報を追加し、ルータに接続された機器と通信を行う...的なやつをやってみたいです。

素材

イラストAC

無料イラスト・フリー素材なら「イラストAC」 (ac-illust.com)

 

Windows PCにPing通信をしようとしたらファイアウォールではじかれた時の対処法

 

はじめに

前回の記事で、ER605を使ったネットワークのルーティングを体験しました。

その時、iPhoneRaspberry-piからDTPCPing通信を実施しましたが、DTPC側のファイアウォールにはじかれてしまい、応答されないことがありました。調べてみると、Windows Defender ファイアウォールにて、受信の規則を設定する必要があるようでした。

そこで今回は、その方法について記載します。

 

目標

 

使用機器・ネットワーク構成

各ネットワークで使用する機器

カテゴリ

機種名

IPアドレス

Wi-Fiルータ

WSR-1500AX2S-BK

192.168.20.254/24

スマートフォン

IPhone 12

192.168.20.100/24

PC①

DESKTOP-FLK5IJ4(OS:Windows 10)

192.168.0.2/24

PC②

Raspberry pi

192.168.11.2/24

 

ネットワーク構成図

ネットワーク構成図を下記に示します。DTPCにてファイアウォールの受信の規則が設定されていない場合、Raspberry-Pi, iPhoneからのpingがはじかれてしまいます。

 

ネットワーク構成図

受信の規則 設定前の動作

本記事では、Raspberry-Pi(PC②)からDTPC(PC①)ping通信を行った場合の動作で確認いたします。

 

まずはファイアウォールの設定をする前の動作です。

設定前にRaspberry-PiからDTPCpingを行った場合、下記のような動作になります。

 

要求元:Raspberry-Pi

宛先:DTPC

--@raspberrypi:~ $ ping 192.168.0.2

PING 192.168.0.2 (192.168.0.2) 56(84) bytes of data.

 

 

...この状態のまま何も進みません。DTPCの所属するネットワークのゲートウェイアドレスである192.168.0.1へのpingは成功しているため、DTPC側のファイアウォールの設定ではじかれていることが予想できます。

 

そこで、DTPCファイアウォールの設定を確認してみます。

 

受信の規則 設定方法

著作権の問題があるため、スクショなしで説明いたします。ご了承ください。

 

受信の規則の確認

Windowsの検索バーにて、「セキュリティが強化されたWindows Defender ファイアウォール」を検索し、画面を開きます。

 

②左のウィンドウより「受信の規則」を開きます。

 こちらの画面で、メッセージを受信した際に、パソコン側でどのように対処するかの規則が記載されています。

 

プロトコルの列をクリックします。

 

プロトコルの「ICMPv4」に着目します。ICMPv4IPv4アドレスを用いた場合のping通信プロトコルです。

 

pingの要求に関する受信の規則は、名前の列で「ファイルとプリンターの共有(エコー要求 – ICMPv4 受信)」と記載されている規則が該当します。初期状態では、リモートアドレスがローカルサブネットとなっている規則一つのみが有効になっていると思います。こちらの規則だけが有効の場合、同じネットワーク内のping以外は受け付けない設定になっています。

 

受信の規則 設定手順

①右のウィンドウから、「新しい規則...」をクリックします。

 

②新規の受信の規則ウィザードが開き、「どの種類の規則を作成するか」の画面に移ります。

 「カスタム(C)」を選択し、「次へ(N)」をクリックします。

 

③「すべてのプログラムと特定のプログラムのどちらにこの規則を適用しますか?」という画面に移ります。

 「すべてのプログラム(A)」を選択し、「次へ(N)」をクリックします。

 

④規則を適用するポートとプロトコルを選択する画面に移ります。

 プロトコルの種類で「ICMPv4」を選択し、「次へ(N)」をクリックします。

 

⑤規則を適用するローカルIPアドレス,リモートIPアドレスを選択する画面に移ります。

 それぞれ下記のように設定し、「次へ(N)」をクリックします。

 

 ローカルIPアドレス:任意

 リモートIPアドレス:

  1. これらのIPアドレス(H)を選択
  2. 「追加(D)...」をクリック
  3. 一致させるIPアドレスとして、Raspberry-PiIPアドレスである「192.168.11.2」を入力し、OKをクリック

 

⑥接続が条件に一致した場合にどのような動作を実行するかを選択する画面に移ります。

 「接続を許可する(A)」を選択し、「次へ(N)」をクリックします。

 

ドメイン、プライベート、パブリックのうち、規則をいつ適用させるかを選択する画面に移ります。

 「パブリック(U)」を選択し、「次へ(N)」をクリックします。

 

⑧名前、説明を入力する画面に移ります。

 ここは任意の値を入力し、「次へ(N)」をクリックします。

 

⑨規則が追加されます。規則が有効になっていることを確認してください。

 

⑩追加された規則を右クリックし、「プロパティ(R)」をクリックすると、先ほどの設定の内容を確認できます。

 

⑪詳細設定タブを選択し、インターフェイスの種類の「カスタマイズ(C)」をクリックします。

 ここで、規則が実行される時のインターフェイスの種類として「ローカルエリアネットワーク」を選択しておきます。

 

⑫これで設定は完了です。iPhoneからのping応答についても同様の手順で受信の規則を追加します。

 1つの受信の規則に対し、リモートIPアドレスを複数設定するという方法もあります。

 

受信の規則 設定後の動作

受信の規則を設定したところで、再度Raspberry-PiからDTPCpingを行ってみます。

問題なく応答されているようです。

 

要求元:Raspberry-Pi

宛先:DTPC

--@raspberrypi:~ $ ping 192.168.0.2
PING 192.168.0.2 (192.168.0.2) 56(84) bytes of data.
64 bytes from 192.168.0.2: icmp_seq=1 ttl=127 time=1.58 ms
64 bytes from 192.168.0.2: icmp_seq=2 ttl=127 time=1.42 ms
64 bytes from 192.168.0.2: icmp_seq=3 ttl=127 time=1.37 ms
64 bytes from 192.168.0.2: icmp_seq=4 ttl=127 time=1.41 ms
64 bytes from 192.168.0.2: icmp_seq=5 ttl=127 time=1.39 ms
64 bytes from 192.168.0.2: icmp_seq=6 ttl=127 time=2.76 ms
64 bytes from 192.168.0.2: icmp_seq=7 ttl=127 time=1.38 ms
64 bytes from 192.168.0.2: icmp_seq=8 ttl=127 time=1.40 ms
64 bytes from 192.168.0.2: icmp_seq=9 ttl=127 time=1.29 ms
64 bytes from 192.168.0.2: icmp_seq=10 ttl=127 time=1.34 ms
64 bytes from 192.168.0.2: icmp_seq=11 ttl=127 time=3.91 ms

 

 

まとめ

今回はWindowsDTPCファイアウォールの受信の規則を追加し、pingに応答できるようにしました。前回の記事でルーティングを体験した際に、場合によってはファイアウォールの設定を見直さなければならないことを知りました。ネットワークに限る話ではないですが、ただ技術書を読むだけではなく、実際に動かしてみないと気づけない点は多いと思います。

 

素材

イラストAC

無料イラスト・フリー素材なら「イラストAC」 (ac-illust.com)

 

TP-Link ER605でネットワークのルーティングを体験してみた。

 

はじめに

ネットワークのことをしっかり勉強したいと思い、技術書を読んだりして調べることが多くなりました。

www.kinokuniya.co.jp

ネットワークの勉強をしていると、必ず出てくるのがルーティングの話です。

説明を見ればなんとなくイメージはできますが、実際にはどのような設定が必要で、うまくいけばどのように動作するのかが気になるところです。そこで、実際にVPNルータを購入し、ネットワークのルーティングを試してみたいと思います。

 

目標

  • ルーティングの設定の仕方を確認する。
  • 各ネットワークから、別のネットワークにping通信で応答が可能かを確認する。

 

使用機器・ネットワーク構成

ゲートウェイとして使用する機器

今回ゲートウェイとして使用するのはTP-Link ER605です。Amazon9000円台で売られており、VPNルータとしては安価のため、勉強に使用するには最適です。

TP-Link ER605

各ネットワークで使用する機器

有線ルータにDTPC,raspberrypi,無線ルータを接続し、それぞれ別のネットワークに設定します。

 

カテゴリ

機種名

IPアドレス

Wi-Fiルータ

WSR-1500AX2S-BK

192.168.20.254/24

スマートフォン

iPhone 12

192.168.20.100/24

PC①

DESKTOP-FLK5IJ4

192.168.0.2/24

PC②

Raspberry Pi 4

192.168.11.2/24

 

ネットワーク構成図


VPNルータの設定

著作権の問題がありますのでスクショなしで説明いたします。ご了承ください。

 

 

ルータの管理画面にログインする

ルータのLANの設定を行うには、管理画面にログインする必要があります。簡易取説に記載がありますが、LAN側デフォルトのIPアドレスが192.168.0.1となっています。そのため、PCとルータを直接LANで接続し、Webブラウザ上で192.168.0.1を入力することで、簡易画面にログインすることができます。この時、PCDHCPで自動的にIPアドレスを取得する設定にしてください。

 

VLANの設定

ルータを介して別のネットワークと通信を行いたい場合は、事前にルータ側でVLANの設定が必要になります。

 

VLANとは

Virtual LANの略で、1つのLANを複数のネットワークを分割し、データが転送される範囲を限定します。今回の例ではネットワーク構成図の通り、3つのネットワークに分割します。

LANの設定

まずはネットワークリストを作成します。ここでは、使用するネットワークとデフォルトゲートウェイの設定を行います。

 

  1. メニューよりNetwork→LANを選択
  2. LANタブを選択

 

今回は下記3つのネットワークを登録します。DHCPは、DHCP ServerEnabledにしておきます。

 

ID

Name

Vlan

IP Address

Subnet Mask

DHCP Server

DHCP Relay

1

LAN

1

192.168.0.1

255.255.255.0

Enabled

Disabled

2

LAN2

2

192.168.11.1

255.255.255.0

Enabled

Disabled

3

LAN3

3

192.168.20.1

255.255.255.0

Enabled

Disabled

 

インターフェイスとネットワークの割付の設定

インターフェイスとネットワークの割付を設定し、V LANとして登録します。初期値でWANの設定がありますが、今回WANのポートは使用しません。

 

  1. メニューよりNetwork→VLANを選択
  2. VLANタブを選択

ID

VLAN ID

Name

Ports

Description

1

1

vlan1

2(UNTAG)

LAN1

2

2

vlan2

3(UNTAG)

LAN2

3

3

vlan3

4(UNTAG)

LAN3

4

4094

vlan4094

1(UNTAG)

WAN

 

ルーティングの設定

ルーティングとは

TCP/IPネットワークにおける通信において、経路を決定することや次の転送先にデータを転送することをさします。ルータを介して別のネットワークに接続する場合、ルータに対して事前にルーティングの設定をする必要があります。

 

ルーティングテーブルの設定

1つのルータで各VLANを直接接続している場合、ルータに対してVLANの設定を実施すれば、直接接続のルート情報は自動的にルーティングテーブルに登録されます。また、下記の手順で現在登録されているルーティングテーブルを表示させます。

 

  1. メニューより、Transmission→Routingを選択
  2. Routing Tableタブを選択
  3. Refreshをクリック

 

ID

Destination IP

Subnet Mask

Next Hop

Interface

Metric

1

127.0.0.0

255.0.0.0

0.0.0.0

Io

0

2

192.168.0.0

255.255.255.0

0.0.0.0

LAN1

0

3

192.168.11.0

255.255.255.0

0.0.0.0

LAN2

0

4

192.168.20.0

255.255.255.0

0.0.0.0

LAN3

0

各種接続機器の設定

各種接続機器のIPアドレスの設定、無線ルータのルーティングの設定が必要になります。機器によってはファイアウォールの設定も必要になりますが、今回の記事では設定方法は割愛します。

pingで動作確認

各機器から、別のネットワークにある機器に対してpingを実施し、応答が受信されることを確認します。

全組み合わせを確認しましたが、どの組み合わせでも応答が受信されていることを確認できました。

 

 

 

 

宛先

 

 

 

スマートフォン

(192.168.20.100)

PC①

(192.168.0.2)

PC②

(192.168.11.2)

 

スマートフォン(192.168.20.100)

-

要求元

PC①

(192.168.0.2)

-

 

PC②

(192.168.11.2)

-

 

PC①コマンドプロンプトより、pingを実施したときの結果です。

 

宛先:PC②

C:\>ping 192.168.11.2

192.168.11.2 に ping を送信しています 32 バイトのデータ:
192.168.11.2 からの応答: バイト数 =32 時間 =1ms TTL=63
192.168.11.2 からの応答: バイト数 =32 時間 =1ms TTL=63
192.168.11.2 からの応答: バイト数 =32 時間 =1ms TTL=63
192.168.11.2 からの応答: バイト数 =32 時間 =1ms TTL=63

192.168.11.2 の ping 統計:
    パケット数: 送信 = 4、受信 = 4、損失 = 0 (0% の損失)、
ラウンド トリップの概算時間 (ミリ秒):
    最小 = 1ms、最大 = 1ms、平均 = 1ms

 

宛先:スマートフォン

C:\>ping 192.168.20.100

192.168.20.100 に ping を送信しています 32 バイトのデータ:
192.168.20.100 からの応答: バイト数 =32 時間 =45ms TTL=62
192.168.20.100 からの応答: バイト数 =32 時間 =52ms TTL=62
192.168.20.100 からの応答: バイト数 =32 時間 =67ms TTL=62
192.168.20.100 からの応答: バイト数 =32 時間 =65ms TTL=62

192.168.20.100 の ping 統計:
    パケット数: 送信 = 4、受信 = 4、損失 = 0 (0% の損失)、
ラウンド トリップの概算時間 (ミリ秒):
    最小 = 45ms、最大 = 67ms、平均 = 57ms

 

最後に

まとめ

今回は実際にルータを用いて、ネットワークのルーティングを試してみました。直接接続の場合は、VLANの設定を行うことで自動的にルーティングテーブルに登録され、各ネットワークに接続できることを確認しました。

今後について

iPhoneやRaspberry PiからデスクトップPCping通信しようとすると、ファイヤーウォールではじかれてしまい、応答しないことがありました。そのため、デスクトップPC側で受信の規則を追加する必要があります。その設定方法については、また別の記事で公開します。

 

素材

イラストAC

無料イラスト・フリー素材なら「イラストAC」 (ac-illust.com)