ルーティングアルゴリズムのしくみ

1. 物理的に接続されているルーターを特定し、それらのIPアドレスを取得します。ルーターが動作を開始すると、最初にネットワーク経由で「HELLO」パケットを送信します。このパケットを受信する各ルーターは、そのIPアドレスを含むメッセージで応答します。
2. 隣接ルーターの遅延時間（または平均トラフィックなど、ネットワークの他の重要なパラメーター）を測定します。これを行うために、ルーターはネットワークを介してエコーパケットを送信します。これらのパケットを受信するすべてのルーターは、エコー応答パケットで応答します。ラウンドトリップ時間を2で割ることにより、ルーターは遅延時間をカウントできます。 （ラウンドトリップ時間は、ネットワーク上の現在の遅延の尺度であり、パケットがリモートホストからバウンスされるタイミングによって検出されます。）この時間には、送信時間と処理時間の両方が含まれることに注意してください。受信者がそれを処理して応答するのにかかる時間。
3. ネットワークを介して他のルーターの情報をブロードキャストし、他のルーターの情報を受信するこのステップでは、すべてのルーターが知識を共有し、情報を相互にブロードキャストします。このようにして、すべてのルーターはネットワークの構造とステータスを知ることができます。
4. 適切なアルゴリズムを使用して、ネットワークの2つのノード間の最適なルートを特定します。このステップでは、ルーターはすべてのノードへの最適なルートを選択します。彼らは、ダイクストラ最短経路アルゴリズムなどのアルゴリズムを使用してこれを行います。このアルゴリズムでは、ルーターは、他のルーターから収集された情報に基づいて、ネットワークのグラフを作成します。このグラフは、ネットワーク内のルーターの位置とそれらの相互リンクを示しています。すべてのリンクには、重みまたはコストと呼ばれる番号が付けられています。この数は、遅延時間、平均トラフィック、および場合によっては単にノード間のホップ数の関数です。たとえば、ノードと宛先の間に2つのリンクがある場合、ルーターは重みが最も小さいリンクを選択します。

1. ルーターはネットワークのグラフを作成し、送信元ノードと宛先ノード（V1やV2など）を識別します。次に、「隣接行列」と呼ばれる行列を作成します。この行列では、座標は重みを示します。たとえば、[i、j]はViとVjの間のリンクの重みです。ViとVjの間に直接のリンクがない場合、この重みは「無限大」として識別されます。
2. ルーターは、ネットワーク上のすべてのノードのステータスレコードセットを作成します。レコードには、次の3つのフィールドが含まれます。先行フィールド-最初のフィールドは、前のノードを示します。長さフィールド-2番目のフィールドには、ソースからそのノードまでの重みの合計が表示されます。ラベルフィールド-最後のフィールドはノードのステータスを示します。各ノードには、「永続的」または「暫定的」の1つのステータスモードを設定できます。
3. ルーターは、ステータスレコードセット（すべてのノード）のパラメーターを初期化し、その長さを「無限大」に設定し、ラベルを「暫定」に設定します。
4. ルーターはTノードを設定します。たとえば、V1をソースTノードにする場合、ルータはV1のラベルを「永続的」に変更します。ラベルが「永続的」に変更されても、二度と変更されることはありません。Tノードはエージェントであり、それ以上のものではありません。
5. ルータは、送信元Tノードに直接リンクされているすべての仮ノードのステータスレコードセットを更新します。
6. ルータはすべての暫定ノードを調べて、V1への重みが最も低いノードを選択します。そのノードが宛先Tノードになります。
7. このノードがV2（目的の宛先）でない場合、ルーターはステップ5に戻ります。
8. このノードがV2の場合、ルータはステータスレコードセットから前のノードを抽出し、V1に到達するまでこれを実行します。このノードのリストは、V1からV2への最適なルートを示しています。

1. 最初の画像でわかるように、ソースノード（A）がTノードとして選択されているため、そのラベルは永続的です（塗りつぶされた円で永続ノードを示し、->記号でTノードを示します）。
2. 次のステップでは、Tノード（B、C）に直接リンクされている仮ノードのステータスレコードセットが変更されていることがわかります。また、Bの重みが小さいため、Tノードとして選択され、ラベルが永続的に変更されました（以下を参照）。
3. ステップ3では、ステップ2と同様に、Tノード（D、E）に直接リンクしている仮ノードのステータスレコードセットが変更されています。また、Dの重みが小さいため、Tノードとして選択され、ラベルが永続的に変更されました。
4. ステップ4では、暫定的なノードがないため、次のTノードを特定するだけです。Eの重みが最も小さいため、Tノードとして選択されています。

#define MAX_NODES 1024 / *ノードの最大数* /
#define INFINITY 1000000000 / *すべての最大パスよりも大きい数* /
int n、dist [MAX_NODES] [MAX_NODES]; / * dist [I] [j]は、iからjまでの距離です* /
void shortest_path（int s、int t、int path []）
{struct state {/ *作業中のパス* /
intの前身; / *前のノード* /
int length / *ソースからこのノードまでの長さ* /
列挙型{永続的、暫定的}ラベル/ *ラベル状態* /
}状態[MAX_NODES];
int I、k、min;
構造体の状態*
                     NS;
for（p =＆state [0]; p <＆state [n]; p ++）{/ *状態を初期化* /
p->先行= -1
p-> length = INFINITY
p-> label = tentative;
}
state [t] .length = 0; state [t] .label = permanent;
k = t;                                                          
/ * kは最初の作業ノードです* /
行う{                                                            
/ * kからのより良いパスですか？* /
I = 0の場合; I <n; I ++）                                       
/ *このグラフにはn個のノードがあります* /
if（dist [k] [I]！= 0 && state [I] .label ==暫定）{
            if（state [k] .length + dist [k] [I] <state [I] .length）{
		       state [I] .predecessor = k;
		       state [I] .length = state [k] .length + dist [k] [I]
		    }
}
/ *最小のラベルを持つ暫定的にラベル付けされたノードを見つけます。* /
k = 0; min = INFINITY;
for（I = 0; I <n; I ++）
     if（state [I] .label ==暫定&& state [I] .length <
min）= state [I] .length;
     k = I;
	}
state [k] .label = permanent
} while（k！= s）;
/ *パスを出力配列にコピーします* /
I = 0; k = 0
Do {path [I ++] = k; k = state [k] .predecessor;} while（k> = 0）;
}

1. 直接接続されているリンクの重みをカウントし、その情報をテーブルに保存します。
2. 特定の期間に、テーブルを隣接ルーター（すべてのルーターではない）に送信し、各隣接ルーターのルーティングテーブルを受信します。
3. ネイバーのルーティングテーブルの情報に基づいて、自身を更新します。

• ルーターのしくみ
• ルータークイズ
• ファイアウォールのしくみ
• インターネットインフラストラクチャの仕組み
• LANスイッチのしくみ
• ホームネットワークのしくみ
• ネットワークアドレス変換のしくみ
• パケットとは何ですか？
• 人々が「コンピュータアルゴリズム」に言及するとき、彼らは正確に何について話しているのですか？

• インターネット百科事典：ルーティング
• ルーティングテーブル
• ネットワークルーティング
• ネットワーク層
• 階層型ルーティング