このレッスン/投稿では、ネットワークについて話します。
世界中の通信ネットワークを介して情報を配信および交換できる機能は、人々の働き方、遊び方、生活の仕方に革命をもたらしました。今世紀の変わり目に、米国国立工学アカデミーは、20 世紀で最も社会に大きな影響を与えた 20 のテクノロジーをリストしました。このリストには、電化、自動車、飛行機など、生活を変えるイノベーションが含まれていました。また、ラジオ、テレビ、電話、インターネット、コンピューターという 4 つの通信技術も含まれており、その技術的基盤が本書の焦点です。
驚くべきことに、インターネットは今世紀後半に開発され、その最も重大な影響は 21 世紀に起こると委員会が信じていたため、順位は 13 位に過ぎませんでした。この予測は正確であるようです。ワイヤレス ネットワークとモバイル デバイスの普及、ソーシャル ネットワークの台頭、いつでもどこでも通信できるようになったことで、商業や社会的つながりが変化し、さらには社会的および政治的変化さえも引き起こされました。
コミュニケーションは現代生活の基本です。インターネット、そのアプリケーション、またはネットワーク接続されたモバイル デバイスのない生活を想像するのは困難です。 2011 年初頭までに、世界中で 50 億台を超える携帯電話が使用され、そのうち 10 億台以上が「ブロードバンド」接続に対応しており、これは 2011 年の電気、靴、歯ブラシ、トイレを備えた人口を超えています。
この投稿/レッスン (どのように呼んでも構いません) は、通信ネットワークがどのように機能するかを説明することを目的としています。これは 2 つの理由から研究する価値があります:
MIT (マサチューセッツ工科大学) では、2 年生が確率とフーリエ級数に触れるこのようなコースを受講します。
伝統的に、「低レベル通信」(単一リンク上で情報がどのように移動するか) は EE のトピックとみなされ、「ネットワーキング」(複数のリンクのネットワークの構築) は CS のトピックとされてきました。従来のデジタル コミュニケーション コースではネットワーク構築についてはほとんど取り上げられず、コンピュータ ネットワーク コースでは物理リンクを介した通信がブラック ボックスとして扱われます。本書は、このギャップを埋めることを目的としており、両方の側面の包括的な理解を提供します。
通信システムをエンドツーエンドで取り上げます: 送信する情報を含むソースから、パケット (送信用に分解されたメッセージ)、ビット (「0」または「1」)、信号 (アナログ波形)ワイヤー、ファイバー、無線、音波などのリンクを介して送信されます）。シンプルなポイントツーポイント リンク、複数のノードによる共有メディア、さらに大規模なネットワークを形成するために接続された大規模なマルチホップ ネットワークなど、多様なネットワークを調べます。
デジタル コミュニケーションの中心となるのは、信頼性、共有、拡張性という 3 つの課題です。この導入セクションでは、最初の 2 つに焦点を当てます。
コミュニケーションの信頼性を低下させる要因は数多くあります。私たちは、信頼性を向上させるための技術を研究します。その技術はすべて、独立したコンポーネントの障害に依存して、信頼性の低いコンポーネントで信頼性を実現する冗長性を採用しています。
主な課題は、通信品質を低下させるノイズ、干渉、ビット エラー、パケット損失 (修正不可能なエラー、キューのオーバーフロー、リンク/ソフトウェア障害による) を克服することです。
信頼性に加えて、スピードも重要です。信頼性技術では冗長性が使用されることが多く、速度が低下します。多くの通信システムは信頼性と速度のバランスを保っています。
通信速度は、1980 年代初頭のキロビット/秒から、無線では毎秒 100 メガビット、今日では有線リンクでは毎秒 1 ～ 10 ギガビットまで劇的に増加しました。
通信の信頼性が低い理由と、エラー訂正コードの使用、シンボル間干渉の処理、再送信プロトコル、およびフォールトトレラントなルーティングを使用して、その問題に対処する方法を探ります。
すべてのノードペアの専用リンクは法外に高価です。共有は不可欠です。ポイントツーポイント リンク、共有メディア、マルチホップ ネットワークの共有について研究します。
メディアの共有 (イーサネット、WiFi、セルラー ネットワーク、衛星ネットワークに関連)、変調/復調 (異なる周波数での送信)、およびメディア アクセス制御 (MAC) プロトコル (ネットワーク ノードの動作を管理するルール) について説明します。 。時間共有 (各ノードが専用の時間送信) と周波数共有 (帯域幅の分割) について説明します。次に、スイッチによって調整され、多くの通信がリンクを共有するマルチホップ ネットワークに移ります。
主な質問には、複数の通信がネットワークをどのように共有するか、メッセージがネットワークをどのように通過するか、マルチホップ ネットワーク全体で信頼性の高い通信を確保する方法が含まれます。
共有技術と信頼性メカニズムがネットワークの効率を決定します。効率とは、特定の要件に対するコストを最小化すること、または特定のネットワークの「有用な作業」（総スループット、スループット変動、平均遅延/レイテンシ）を最大化することとして組み立てることができます。この投稿では、スループットとレイテンシに焦点を当てます。
スケーラビリティ (大規模なサイズを処理できるネットワークの設計) が重要です。この投稿ではこれについて簡単に触れ、詳細な説明は後のレッスンに残しておきます。
レッスンは 4 つの部分に分かれています。ソース、ビット、信号、パケットの抽象化をこの順序で学習します。
クロード シャノンの情報理論 (1940 年代後半に開発) は、多くの技術分野、特に通信システムやネットワークに変革をもたらした画期的なアイデアです。この章では、情報の背後にある直感を紹介し、それを数学的に定義し、それをデータ ソースの特性であるエントロピーに関連付けます。
これらの概念により、通信または保存前の効率的なデータ圧縮が可能になり、歪みのない元のデータの復元が可能になります。 中心となるアイデアは ソース コーディング です。これは、データ ソースの各シンボルを、望ましいプロパティを持つ コードワード にマッピングします。メッセージは一連のシンボルです。私たちはロスレス ソース コーディングに焦点を当てており、破損していない送信から元のメッセージを完全に復元できます。
シャノンは、ハートリーの研究を基にして、アプリケーションやメッセージのセマンティクスとは無関係に、情報を一般的に定義できることに気づきました。通信には、送信者 (S) がいくつかのメッセージの中から 1 つを選択して受信者 (R) に送信することが含まれます。たとえば、S は英国の到着ルートを示すことができます:
各選択肢の可能性が等しい場合 (事前知識なし)、伝達される情報は 1 ビットです。このビットは選択をエンコードできます。 1000 個のこのような独立したイベントを 1000 ビットでエンコードできます。
事前知識が 1 つの選択肢 (嵐による陸地など) の可能性が高いことを示唆している場合、可能性が低いメッセージ (海) がより多くの情報を伝えます。 同様に、1 月のボストンの気温 75°F は、32°F よりも有益です。
イベントに関する情報は、その確率 (p) によって決まります。確率が低い (可能性が低いイベント) ということは、情報が高いことを意味します。
Hartley は情報 (I) を次のように定義しました:
I = log(1/p) = -log(p) (2.1)
底 2 の対数が使用され、情報の単位はビットです。 対数関数は 加法性 を保証します: 2 つの独立したイベント A と B (確率 pA と pB) からの情報は合計されます:
IA IB = log(1/pA) log(1/pB) = log(1/(pA*pB)) = log(1/P(A および B))
エントロピー (H) は、相互に排他的な一連のイベントから期待される情報を定量化します。イベント i が確率 pi を持つ場合:
H(p1, p2, ... pN) = Σ pi * log(1/pi) (2.2)
エントロピーはビット単位で測定され、平均の不確実性を表します。確率 p および 1-p の 2 つの相互に排他的なイベントの場合:
H(p, 1-p) = -p*log(p) - (1-p)*log(1-p) (2.3)
H(p) は p = 1/2 の周りで対称で、p = 1/2 で最大 1 ビットになります。 H(0) = H(1) = 0。エントロピーは常に負ではなく、H(p1, p2, ... pN) ≤ log N.
ソースコーディング はメッセージを効率的にエンコードします。 多くのメッセージには標準エンコーディング (ASCII、画像ピクセル、音声サンプル) が含まれています。これらは固定長エンコーディングであり、簡単に操作できます。
ただし、これらのエンコードは非効率になる可能性があります。 英語のテキストでは、「e」は「x」よりも頻繁に出現します。 「e」をより少ないビットでエンコードし、「x」をより多くのビットでエンコードすると、平均メッセージ長を短縮できます。 これは、情報の概念と一致しています。つまり、頻繁に使用されるシンボル (パイが大きい) は、伝達する情報が少なくなり、必要なビット数も少なくなります。
コードは、情報をビット シーケンスにマッピングします。 コードワード は、コード内のビット シーケンスです。 ソース コード は、エンコードされたメッセージの長さを情報内容 (エントロピー) に一致させることでデータを圧縮することを目的としています。
例: 1000 のグレード (A、B、C、D) を確率でエンコードします:
固定長エンコーディング: 2 ビット/グレード (合計 2000 ビット)。 デコードは簡単ですが、非効率的です。
可変長符号化(例): A=10、B=0、C=110、D=111。 長さはメッセージによって異なります。 デコードには逐次処理が必要です。 このコード例は最適ではありません。
理想的には、圧縮では情報を表現するために必要なビットのみが使用されます。エントロピー (式 2.2) は、曖昧さを避けるために必要な平均ビット数の下限を示します。送信するビット数を少なくすると、受信側で選択が未解決になる可能性があります。
学年の例では、学年ごとに期待される情報は 1.626 ビットです。 1000 グレードのエンコードには平均 1626 ビットが必要です。サンプルの可変長コードは 1667 ビットを使用しているため、最適ではありません。 グレードのシーケンスをエンコードすると、圧縮を向上させることができます。
良いコードを見つけるのは難しいです。場合によっては、コンテキスト固有のコードが非常に効率的になることがあります (例: 送信者と受信者の両方がすべてのソネットを知っている場合、わずか 8 ビットを使用してシェイクスピアのソネットをエンコードする)。
圧縮にはいくつかの利点があります:
圧縮は通常、エンドツーエンドの機能 (アプリケーション層) ですが、データが圧縮可能で冗長性が含まれている場合は、リンク層で適用することもできます。 次の章では、ハフマン コードと Lempel-Ziv-Welch (LZW) 圧縮について説明します。
この章では、メッセージ圧縮 (メッセージはシンボルのシーケンス) のための 2 つのソース コーディング アルゴリズム、ハフマン コーディングと Lempel-Ziv-Welch (LZW) について説明します。ハフマン符号化は、シンボル確率が既知で独立している場合に効率的です。 LZW は適応型であり、確率に関する事前の知識は必要ありません。 どちらも広く使用されています (GIF、JPEG、MPEG、MP3 など)。
コードは、アルファベットのシンボル (テキスト、ピクセル強度、または抽象シンボル) を コードワード にマップします。 バイナリ コードワードは、多くの通信チャネルに便利です。
例: 6.02 でのエンコーディング グレード: A=1、B=01、C=000、D=001。一連の成績は 0010001110100001 として送信され、「DCAAABCB」としてデコードされます。
瞬間コード: シンボルは、そのコードワードが受信されるとすぐにデコードされます。 上記のグレードのエンコードは瞬時に行われます。非瞬間的なコードは、先を読むか、最後からデコードする必要があるため、デコードが難しくなります。
コード ツリーとプレフィックス フリー コード: コード ツリー はコードを視覚化します。 バイナリ コード ツリーでは、エッジに 0 または 1 のラベルが付けられます。ルートからシンボルまでのパスによって、そのエンコーディングが決まります。 プレフィックスフリー コード はリーフ ノードにのみシンボルを持ち、どのコードワードも別のプレフィックスにならないようにします。プレフィックスのないコードは瞬時に生成されます。
予想されるコード長 (L): 確率 pi とコードワード長 li を持つ N 個のシンボルの場合: L = Σ pi *リー。 圧縮するには、L が小さいコードが望ましいです。 最適なコードは最小の L を持ちます。シャノンは L ≥ H (エントロピー) を示し、エントロピーを達成するコードが漸近的に存在することを示しました。
ハフマン コードは、シンボル確率が与えられた場合に効率的なエンコードを提供します。 シンボルがより短いコードになる可能性が高くなります。
ハフマンのアルゴリズムは、最も可能性の低いシンボルから始めて、コード ツリーをボトムアップで構築します。
結果のコード ツリーは可変長コードを定義します。
文字確率に基づく単純なハフマンコーディングには限界があります。 メッセージの内容に合わせて調整するアダプティブ エンコーディングは、パフォーマンスを向上させることができます。 LZW は人気のある適応アルゴリズムです。
LZW は、シンボル シーケンスを N ビットのインデックスにマッピングする文字列テーブルを構築します。テーブル (2^N エントリ) はシングルバイト シーケンス (0 ～ 255) で初期化されます。 エンコーディング:
デコーダはコードを受信するとテーブルを再構築し、元のメッセージを復元できるようにします。
LZW 観測:
この章では、アナログの問題点とデジタルの理論的根拠に焦点を当てて、アナログとデジタルのコミュニケーションについて説明します。これは、アナログ通信リンクを介してデジタル データを送受信する方法を示します (物理リンクは基本的に最下位レベルでアナログであるため必要です)。また、階層化された通信モデル (メッセージ → パケット → ビット → 信号) も紹介されており、これが本書の残りの部分の基礎となります。
通信テクノロジーにより、ユーザー (人間またはアプリケーション) はメッセージを交換できます。 データ ソースは本質的にデジタル (コンピューター生成データなど) またはアナログ (ビデオ、オーディオ、センサー データなど) の場合があります。 最新のシステムでは、ソースに関係なく、すべてのデータがデジタル化されることがよくあります。
デジタル コミュニケーションが優れている理由は 2 つあります:
ただし、物理リンクはアナログであるため、デジタルからアナログへの変換、およびアナログからデジタルへの変換が必要です。
アナログ表現は物理リンクのプロパティに適切にマッピングされます。例:
白黒テレビ: 画像の輝度 (グレーの階調) は電圧レベル (0V = 黒、1V = 白) で表されます。
アナログ電話: 音波は電気信号に変換されます。
アナログ信号はさまざまな電圧/強度/波長レベルで送信でき、受信機で簡単に測定できます。
エラーのない通信リンクはありません。ノイズと歪みにより信号が乱され、これらのエラーは複数の送信ステージにわたって蓄積されます (カスケード効果)。このため、アナログ システム、特に複雑なシステムを確実に構築することが困難になります。デジタル信号はこの問題に対処します。
デジタル信号はビットを表すために離散値を使用し、ノイズとの確実な区別を可能にします。 バイナリ信号では、「0」の場合は V0、「1」の場合は V1 という 2 つの電圧が使用されます。 ノイズを処理するには、V0 と V1 を十分に分離する必要があります。
受信機は、しきい値電圧 (Vth = (V0 V1) / 2) を使用して、受信電圧をビットにマッピングします (電圧
送信信号は一定時間保持された固定電圧の波形です。 連続信号は離散時間サンプルによって表されます。 サンプルレート (1 秒あたりのサンプル数) は、送信者と受信者によって合意されます。 サンプル間隔 はサンプル間の時間です。
送信者と受信者はクロックレートについて合意する必要があります。ビットはクロック遷移時に送信されます。 Samples_per_bit は、ビットあたりのサンプル数です。受信機は、受信したサンプルの遷移からクロック エッジを推測します。
課題:
受信側のクロックは送信側のクロックよりわずかに速いか遅い場合があります。 受信機は、遷移に基づいてサンプリング インデックスを動的に調整します。
初期補正は、送信開始時に 0 と 1 を交互に繰り返すトレーニング シーケンスによって支援されます。
8b/10b は DC バランスと頻繁な遷移に対処します。 8 ビットのシンボルを 10 ビットの送信シンボルにマッピングし、次のことを保証します。
エンコードプロセス:
通信システムには、マッパー (ビットから信号)、デマッパー (信号からビット)、チャネル コーディング (誤り訂正)、チャネル デコーディングといったいくつかのモジュールが含まれます。メッセージはパケットに分割され、複数のリンクを介して送信されます。 3 つの主要な抽象化は、パケット、ビット、および シグナルです。 この本は、これらと通信ネットワーク内での相互作用に焦点を当てています。
この章では、通信チャネルや記憶媒体における避けられないビットエラーに対処するための冗長性の追加に焦点を当て、信頼性の高いデジタル通信のための技術について説明します。 中心となる概念はチャネルコーディングです。送信側でエンコードし、受信側でデコードしてエラーを修正したり、修正不可能なエラーを検出したりします。 この章では、エラー訂正 コード、特に線形ブロック コードと (後の) 畳み込みコードに焦点を当てます。
バイナリ対称チャネル (BSC) モデルは、単一パラメータ ε (ビット反転確率) を使用してビット エラーを特徴付けます。送信されたビットは、他のビットとは独立して、確率 ε で反転します。 ε は経験的に推定できます。 サイズ S ビットのパケットのパケット エラー確率 (PER):
PER = 1 - (1 - ε)^S (5.1)
ε
実際のチャネルでは、バースト エラーが発生する可能性があります。この場合、エラーの確率は履歴に依存します (最近のビットにもエラーがあった場合はより高くなります)。
繰り返しコードは、ビットbをbのnコピーとしてエンコードします。 コードレートは 1/n です。 最尤復号 では、受信したコードワードから最も可能性の高いメッセージを選択します。 BSC の場合、これは、受信したコードと共通するビットが最も多いコードワードを選択することを意味します。
繰り返しコードの復号エラー確率 (原文の式 5.3 を参照)。確率はコード レートとともに指数関数的に減少しますが、オーバーヘッドが高いため非効率です。
ハミング距離 (HD) は、異なるビット位置の数です。単一誤り訂正 (SEC) の場合、任意の 2 つの有効なコードワード間の HD は少なくとも 3 である必要があります。最小ハミング距離 D を持つコードは、D-1 エラーを検出し、フロア(D/2 -1) エラー。
線形ブロック コード (n, k) は、メッセージ ビットに対する線形関数 (加重和) を使用して、k ビットのメッセージを n ビットのコードワードにマッピングします。 代数ブロック コード は、ブロック内でそのような演算を実行します。 (n,k,d) コードは、最小ハミング距離「d」を持つブロック コードを示します。コードレート = k/n.
線形コード では、任意の 2 つのコードワードの合計もコードワードである必要があります。 すべてゼロのコードワードは、どの線形コードにも存在します。線形ブロック コードの最小ハミング距離は、ゼロ以外のコードワードの最小の重み (1 の数) に等しくなります。 バイナリ線形コードは、モジュロ 2 演算 (ガロア体 F2) を使用します。
パリティ は、ビットのモジュロ 2 の合計です。 偶数パリティ コード は、各メッセージにパリティ ビットを追加し、コードワードに偶数パリティを持たせます。これにより、単一エラー (HD=2) が検出されます。
方形パリティ コード は、k ビットを r x c 配列に配置し、行パリティと列パリティを追加します。コードワード: メッセージ行パリティ列パリティ。長さ: n = rc r c。このコードは SEC コード (HD=3) です。 デコードには、行と列のパリティをチェックし、両方のパリティがエラーを示している場合は対応するビットを修正することが含まれます。
あらゆる線形コードは、体系的コード (メッセージ ビットの後にパリティ ビットが続く) に変換できます。 SEC の場合、パリティの組み合わせの数 (2^(n-k)) は、修正可能な状況の数 (n 1) 以上でなければなりません:
n 1 ≤ 2^(n-k) (5.6)
パリティ ビット数は、メッセージ ビットに応じて少なくとも対数的に増加します。
ハミング コード は、対数パリティ ビット増加を伴う効率的な SEC コードです。 各パリティ ビットは複数のデータ ビットを保護し、単一のエラーは固有のパリティ エラーの組み合わせを生成します。
シンドローム ビット (Ei) は、受信側でパリティをチェックすることによって計算されます。シンドローム ビットの組み合わせは、エラーのあるビット (存在する場合) を示します。
ハミングコードの構築:
2 進数として扱われるシンドローム ビット ((7,4) の例では E3E2E1) は、修正するビットのインデックスを与えます。
注: これは Web 開発に必要な単なる情報です。 Sysops の場合、ネットワークとその基礎は 2 学期制のコースです。
以上がインターネットはどのように機能するのでしょうか?パート 2の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
