３層スィッチとルーターの差、分割アルゴリズム

最近ルーターの設定とネットワーク構成を学びながらレイヤ３スィッチも考えています。ルーターがルーテイング表を使って転送の判断を行う。それ以外ルーチングプロトコル経由ルートを他のルーターに宣伝します。スイッチもこの機能を持つらしいです。主な違いはルーターが低速回線のインターフェースを持つ事に対してスイッチはイーサーネット回線の未を向きます。The switch apparently can also perform more logic in hardware and maps routes to VLANS as opposed to single interfaces. It uses floating programmable gated arrays (FPGA) to perform routing logic (i.e. table lookup), whereas routers utilize software. ルータの経路情報とARP表がレイヤ３スイッチのFDBを似ています。L2スイッチが基本的に宛先のハードウェアアドレス(MAC)をポートを翻訳します。レイヤ３スイッチはIPアドレスも処理できるからLANで直接に接続されていないホストを結べます。
分割アルゴリズムが動的計画法を使用します。Given a string of o's and x's, the goal is to:
1. generate all possible strings of 1/2 the length containing 1/2 the x's and 1/2 the o's.
2. for each possible substring above, count the number of ways to partition the original string into two such substrings (e.g. by selecting the first char and third char of a string of 4 characters).
The strategy to solve this used memorization and dynamic programming function DP(a,b), where "a" is the number of characters in the first substring and "b" is the number of characters in the second substring. The original string "s" is processed left to right, where the current character is a+b. All possible (a,b) pairs are checked for each candidate string in 1 above.
The key insight here is that, when many candidate strings are possible ie many ways to get half of the x's and half the o's, the number of a,b pairs is small. When the number of a,b pairs is large, the number of candidate strings is small.