ターン制限ルーティング

ルーティング アルゴリズムは、 ネットワーク内の送信元ルータから宛先ルータまでのパケットのパスを決定します。ルーティング アルゴリズムを設計する際に考慮すべき重要な点は、デッドロックを回避することです。ターン制限ルーティング^[1]は、メッシュトポロジ ファミリのルーティング アルゴリズムであり、ネットワーク内の送信元ノードから宛先ノードまでのルートを決定する際にアルゴリズムで許可されるターンの種類を制限することでデッドロックを回避します。

デッドロック（図1参照）は、バッファやリンクなどのネットワークリソースが飽和状態になり、パケットの転送がそれ以上行われない状況です。デッドロックの主な原因は、ネットワーク内のチャネルの循環的な取得です。^[2]たとえば、ネットワークに4つのチャネルがあるとします。4つのパケットがこれら4つのチャネルの入力バッファをいっぱいにし、次のチャネルに転送する必要があります。ここで、これらすべてのチャネルの出力バッファも、次のチャネルに送信する必要があるパケットでいっぱいになっているとします。これら4つのチャネルがサイクルを形成する場合、すべてのチャネルの出力バッファと入力バッファがすでにいっぱいになっているため、パケットをそれ以上送信することはできません。これはチャネルの循環的な取得と呼ばれ、デッドロックを引き起こします。

デッドロックは検出、解消、または発生を完全に回避することができます。ネットワーク内のデッドロックを検出して解消するには、遅延とリソースの面でコストがかかります。したがって、簡単で安価な解決策は、チャネルの循環的な取得を防ぐルーティング技術を選択してデッドロックを回避することです。^[3]

ターン制限ルーティングの背後にあるロジックは、重要な観察から派生しています。チャネルの循環取得は、可能な 4 つの時計回り (または反時計回り) ターンがすべて発生した場合にのみ実行できます。つまり、少なくとも時計回りのターンの 1 つと反時計回りのターンの 1 つを禁止することで、デッドロックを回避できます。制限のないルーティング アルゴリズムで可能なすべての時計回りと反時計回りのターンは、図 2 に示されています。

ターン制限ルーティングは、ルーティング アルゴリズムで時計回りのターン 4 つのうち少なくとも 1 つと反時計回りのターン 4 つのうち少なくとも 1 つを禁止することで実現できます。つまり、時計回りのターン 4 つと反時計回りのターン 4 つから選択できるため、ターン制限ルーティング手法は少なくとも 16 種類 (4x4) 存在することになります。これらの手法のいくつかを以下にリストします。

次元順 (XY) ルーティング^[1] (図 3 参照) は、y 次元から x 次元へのすべての回転を制限します。これにより、実際に必要な数を超える反時計回りの 2 回と時計回りの 2 回の回転が禁止されます。それでも、許可される回転数が制限されるため、これは回転制限ルーティングの例であることがわかります。

西優先ルート^[1]（図4参照）は、すべての方向転換を西方向に制限します。つまり、提案されたルートでは、必要に応じて西方向を最初に通行する必要があります。

北への最終ルート^[1]（図5参照）は、現在の方向が北の場合、他の方向への旋回を制限します。つまり、提案されたルートでは、必要に応じて北方向を最後に取る必要があります。

負の優先ルーティング^[1]（図6参照）は、現在の方向が正である間は負の方向への旋回を制限します。西はX次元の負の方向とみなされ、南はY次元の負の方向とみなされます。つまり、負の方向のいずれかへのホップは、他の旋回を行う前に実行する必要があります。

• デッドロックを回避する技術は、デッドロックを検出して解除する技術よりも実装コストが低くなります。
• ターン制限により、1 つのノードから別のノードへの代替最小長パスと非最小長パスが提供され、混雑したリンクや障害が発生したリンクを迂回してルーティングできるようになります。

たとえば、下の図 7 を考えてみましょう。F1、F2 など、複数のルータがあり、送信元ルータ S から宛先ルータ D への混雑しているが低コストのリンクにパケットを供給しているとします。ターン制限ルーティングを実装すると、フィーダ ルータのいずれかから混雑しているルータ S へのターンの一部が制限される可能性があります。これらのフィーダ ルータは、宛先 D に到達するために長いパスを使用する必要があるため、S から D へのリンクの混雑がある程度緩和されます。

• ポリシーベースルーティング
• デッドロック
• ヒューリスティックアルゴリズム