ルーティングアルゴリズムの仕組み

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 short_path(int s,int t,int path[ ])
{struct state { /* 作業中のパス */
int 先行関数 ; /*前のノード */
int length /*ソースからこのノードまでの長さ*/
enum {永続的、暫定的} label /*ラベルの状態*/
}状態[MAX_NODES];
int I、k、分;
構造体の状態 *
                     p;
for (p=&state[0];p < &state[n];p++){ /*状態を初期化します*/
p->先行=-1
p->長さ=無限大
p->label=暫定;
}
状態[t].length=0;状態[t].label=永続的;
k=t ;                                                          
/*k は最初の作業ノードです */
する{                                                            
/* k からのパスの方が良いですか? */
I=0の場合;私は<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=私;
	}
state[k].label=永続的
}while (k!=s);
/*パスを出力配列にコピーします*/
I=0;k=0
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0);
}

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