日本語

Chapter 5: データリンク層
Chapter 5
Data Link Layer
目標:
ˆ データリンク層サービスの背景にある原理の理解:



A note on the use of these ppt slides:

We’re making these slides freely available to all (faculty, students, readers).
They’re in PowerPoint form so you can add, modify, and delete slides
(including this one) and slide content to suit your needs. They obviously
represent a lot of work on our part. In return for use, we only ask the
following:
‰ If you use these slides (e.g., in a class) in substantially unaltered form,
that you mention their source (after all, we’d like people to use our book!)
‰ If you post any slides in substantially unaltered form on a www site, that
you note that they are adapted from (or perhaps identical to) our slides, and
note our copyright of this material.
Computer Networking:
A Top Down Approach
Featuring the Internet,
誤り検出，訂正
ブロードキャストチャネルの共有：多重アクセス
リンク層アドレッシング
高信頼データ転送，フロー制御: 完了！
ˆ さまざまなリンク層技術の実例と実装
2nd edition.
Jim Kurose, Keith Ross
Addison-Wesley, July
2002.
Thanks and enjoy! JFK/KWR
All material copyright 1996-2002
J.F Kurose and K.W. Ross, All Rights Reserved
5: DataLink Layer
Chapter 5 内容
ˆ 5.1 イントロダクションとサ
ˆ
ˆ
ˆ
ˆ
ービス
5.2 誤り検出と訂正
5.3 多重アクセスプロトコ
ル
5.4 LAN アドレスとARP
5.5 イーサーネット
5: DataLink Layer
5a-1
Link Layer: イントロダクション
Some terminology:
ˆ 5.6 ハブ，ブリッジ，スイッ
ˆ
ˆ
ˆ
ˆ
5a-2
“link”
ˆ ノード：ホスト，ルータ（ブリッジ，ス
イッチも）
チ
5.7 無線リンク，ＬＡＮ
5.8 PPP
5.9 ATM
5.10 フレームリレー
ˆ リンク：通信パスに沿って隣接ノー
ドを接続する通信チャネル



有線リンク
無線リンク
LANs
ˆ フレーム：２層PDU，データグラムを
カプセル化
データリンク層は，データグラムをノードから
その隣接ノードへリンクを介して転送する責
任がある
5: DataLink Layer
リンク層：状況
ˆ データグラムは，異なるリン
クを介した，異なるリンクプ
ロトコルによって転送される:

例，最初にEthernet，中継リ
ンクはフレームリレー，最後に
802.11
ˆ 各リンクプロトコルは異なる
サービスを提供

例，リンク上で高信頼性データ
転送を提供するか，そうでな
いか
5: DataLink Layer
5a-3
5a-4
リンク層サービス
交通機関との類似性
ˆ Princeton から Lausanne への旅
行



リムジン: Princeton から JFK
飛行機: JFK から Geneva
鉄道: Geneva から Lausanne
ˆ 旅行者 = データグラム
ˆ 交通機関区間 = 通信リンク
ˆ 交通機関種別 = リンク層プ
ロトコル
ˆ 旅行代理店 = 経路制御アル
ゴリズム
5: DataLink Layer
5a-5
ˆ フレーミング，リンクアクセス:



ヘッダ・トレイラを追加し，データグラムをフレームにカプセル化
共有媒体の場合，チャネルアクセス
始点と終点の識別に 物理アドレス を使用
• IPアドレスとは違う！
ˆ 隣接ノード間の高信頼転送
 ３章で学習済み！
 低誤り率リンクではあまり使われない（光ファイバ，いくつかのよ
り対線）
 無線リンク：高誤り率
• 質問：リンクレベルとエンド間の信頼性の両方が必要なわけ
5: DataLink Layer
5a-6
1
リンク層サービス（つづき）
アダプタ間通信
データグラム
ˆ
フロー制御：
ˆ
誤り検出：



ˆ

受信側は，ビット誤りを同定し，再送を要求することなく訂正する
Ethernet card, PCMCI
card, 802.11 card
ˆ 送信側:

半二重では，リンク両端のノード双方が通信できるが，同時には
できない
5: DataLink Layer
frame
アダプタ
実装（NIC）
半二重，全二重

frame
アダプタ
ˆ リンク層は アダプタ 内に
誤り訂正：

ˆ
隣接する送受信ノード間で速度調整
信号劣化，ノイズによる誤り
受信端末は誤りの存在を検出:
• 送信側に再送を要求するかフレームを廃棄する

受信ノード
リンク層プロトコル
送信ノード
ˆ 受信側
 エラー，高信頼性制御，フロ
ー制御などをチェック
ˆ アダプタは半自動
ˆ リンク＆物理層
データグラムをフレームにカ
プセル化
エラーチェックビット，信頼性
，フロー制御などを追加
5: DataLink Layer
5a-7
Chapter 5 内容
5a-8
誤り検出
ˆ 5.1 イントロダクションとサ
EDC= Error Detection（検出） and Correction（訂正） bits （冗長ビット）
D = エラーチェックにより保護されるデータ部（ヘッダ部を含む場合がある）
ˆ 5.6 ハブ，ブリッジ，スイッ
ービス
チ
ˆ 5.2 誤り検出と訂正
ˆ 5.7 無線リンク，ＬＡＮ
ˆ 5.3 多重アクセスプロトコ
ˆ 5.8 PPP
ル
ˆ 5.4 LAN アドレスとARP
ˆ 5.5 イーサーネット
ˆ 5.9 ATM
•誤り検出は 100% 信頼できるわけではない！
• プロトコルはエラーを見逃しうるが，それはまれ
• EDC フィールドが大きいほど，誤り検出，訂正能力は向上する
ˆ 5.10 フレームリレー
5: DataLink Layer
5: DataLink Layer 5a-10
5a-9
パリティチェック
インターネットチェックサム
１ビットパリティ:
２次元ビットパリティ:
１ビット誤りを検出
１ビット誤りを検出訂正
0
目標: 伝送セグメント内の誤り検出 (例，ビット反転)
(注意: トランスポート層のみで用いられる)
送信側:
受信側:
ˆ セグメントの内容を 16ビ
ˆ 受信セグメントのチェックサム和
ット整数列として扱う
ˆ チェックサム：セグメント
内容の１６ビット整数の
１の補数和
ˆ チェックサム値をUDP，
TCPチェックサムフィー
ルドに記入
0
5: DataLink Layer 5a-11
を計算
ˆ 計算結果がチェックサムフィール
ドと同じかどうかをチェック:
 NO – 誤り検出
 YES – 誤り未検出. 誤りはあ
るかもしれない…
5: DataLink Layer 5a-12
2
チェックサム:巡回剰余チェック
CRC の例
ˆ データビットDを二進数とみなす
欲しいもの:
D.2r XOR R = nG
ˆ r+1 ビットパターン（生成多項式），G，を求める
ˆ 目標: CRC ビット（r ビット） R を計算する



等価:
<D,R> が G で割り切れる(モジュロ 2 演算)
受信側はGは既知，Gで<D,R>を除算．剰余が非ゼロなら誤り検出！
r+1 ビット以下のバーストエラーを検出可能
ˆ 広く利用されている (ATM, HDCL)
D.2r = nG XOR R
等価:
D.2r を Gで除算した余
り R が必要
R = remainder[
D.2r
G
]
5: DataLink Layer 5a-13
Chapter 5 内容
5: DataLink Layer 5a-14
多重アクセスリンク・プロトコル
リンク は２種類ある:
ˆ 5.1 イントロダクションとサ
ービス
ˆ 5.6 ハブ，ブリッジ，スイッ
チ
ˆ 5.2 誤り検出と訂正
ˆ 5.7 無線リンク，ＬＡＮ
ˆ 5.3 多重アクセスプロトコ
ˆ 5.8 PPP
ル
ˆ 5.4 LAN アドレスとARP
ˆ 5.5 イーサーネット
ˆ 5.9 ATM
ˆ １対１型
 ダイアルアップ接続のためのPPP


ˆ 5.10 フレームリレー
スイッチとホスト間のポイント・ツー・ポイントリンク
ˆ 放送型 (共有線・媒体)


旧型イーサネット
HFC上りチャネル（下りもそうだが競合はない）
802.11 無線 LAN
5: DataLink Layer 5a-15
5: DataLink Layer 5a-16
多重アクセスプロトコル
理想的多重アクセスプロトコル
ˆ 単一共有放送チャネル
レート R bps のブロードキャストチャネル
1. あるノードが転送する場合は レート R で送信できる．
2. M ノードが転送したい場合，各ノードは平均レート R/M
で転送する．
3. 完全分散化：
ˆ 複数ノードによる同時転送：干渉
 同時には一つのノードのみが送信成功できる
多重アクセスプロトコル
ˆ どのようにノードがチャネルを共有するか，つまり，い
つノードが送信できるかを決定するための分散アル
ゴリズム
ˆ チャネル共有のための通信はチャネル自身を用いな
ければならない！
5: DataLink Layer 5a-17


転送を調停するための特殊ノードなし．
クロック，スロットの同期なし
4. 簡単
5: DataLink Layer 5a-18
3
チャネル分割 MAC プロトコル: TDMA
MAC プロトコル: 分類
TDMA: time division multiple access
（時分割多重アクセス）
３種類に大別:
ˆ チャネル分割型
 チャネルを分割（時間スロット，周波数，コード）
 各ノードに排他的に分割チャネルを割当
ˆ 各局は，順番にチャネルにアクセスし，固定長スロットを
ˆ ランダムアクセス型
 チャネルは分割されない，コリジョン（衝突）が発生しうる
 コリジョンからの回復機能
得る（スロット長 = パケット送信時間）
ˆ 未使用スロットはアイドルのまま
ˆ 例：6局ＬＡＮで，局１，２，３がパケット送信する場合，スロ
ット２，５，６は未使用（アイドル）
ˆ 送信権巡回型
 コリジョン回避のために共有アクセスを厳密に管理
5: DataLink Layer 5a-19
チャネル分割 MAC プロトコル: FDMA
FDMA: frequency division multiple access
（周波数分割アクセス）
5: DataLink Layer 5a-20
チャネル分割 MAC プロトコル： CDMA
ˆ チャネル帯域を複数の周波数帯に分割
CDMA (Code Division Multiple Access)
（符号分割多重アクセス）
ˆ 各局に固定周波数帯を割当て
ˆ ユーザごとに一意のコードを割当：すなわちコード集合分
割
ˆ 周波数帯での未使用伝送時間はアイドルのまま
ˆ 例：6局ＬＡＮで，局１，２，３がパケット送信する場合，周波数
time
ˆ 全ユーザが同一周波数を共有するが，各ユーザはデータ
を符号化するために自身の拡散系列（符号）を使用
符号化信号 = (元データ) X (拡散符号)
ˆ 復号化: 符号化信号と拡散係数の内積
ˆ 複数ユーザが同時に最小の干渉で同時に送信できる （コ
ードが直交していれば）
frequency bands
帯２，５，６は未使用（アイドル）
ˆ たいていの無線放送チャネルで使用（セルラ，衛星，など）
ˆ
5: DataLink Layer 5a-21
CDMA 符号化/復号化
5: DataLink Layer 5a-22
CDMA: 2送信局間の干渉
5: DataLink Layer 5a-23
5: DataLink Layer 5a-24
4
Slotted ALOHA
ランダムアクセスプロトコル
ˆ ノードが送信すべきパケットを有する場合
 フルチャネルデータレート R で送信

ノード間での事前協調はなし
ˆ 複数ノードの同時送信→コリジョン
ˆ ランダムアクセス MAC プロトコルは以下を記述:


コリジョンをどのように検出するか
コリジョンからどのように回復するか（例，再送）
ˆ ランダムアクセス MAC プロトコルの例:
 Slotted ALOHA
 ALOHA
 CSMA, CSMA/CD, CSMA/CA
仮定
ˆ 全フレームは同一サイズ
ˆ 時間を同一サイズスロット（
1フレーム送信に要する時
間）に分割
ˆ ノードはスロット開始時に
のみフレーム送信開始
ˆ ノードは同期している
ˆ スロット内に複数ノードが
送信した場合，全ノードが
衝突を検出
動作
ˆ ノードは送信すべきフレーム
を受け取ると，次するっとで送
信
ˆ 衝突しなかった場合，ノードは
次スロットで新規フレームを
送信可能
ˆ 衝突した場合，成功するまで
続く各スロットで確率 p で再
送
5: DataLink Layer 5a-25
Slotted ALOHA
5: DataLink Layer 5a-26
Slotted ALOHA の効率
ˆ 効率 Np(1-p)N-1 が最大
効率： 送信すべきフレームを有す
る多数のノードがある場合の，ス
ロットが送信成功に利用されてい
る時間割合
となる確率 p* を見出す
ˆ 多数のノードに対し，N を
無限にしたときのNp*(1p*)N-1 の極限をとる
ˆ 1/e = .37 を得る
ˆ Nノードは，送信すべきフ
利点
ˆ 単一のアクティブなノード
は，フルチャネルレートで
連続して送信可能
ˆ 高い分散性： スロットが
同期している必要がある
のみ
ˆ 単純
欠点
ˆ 衝突によるスロットの浪費
ˆ アイドルなスロットが生じうる
ˆ ノードはパケット送信時間よ
り小さい時間で衝突を検出
レームを常に有し，確率
p で各スロットで送信する
ˆ 第１ノードがあるスロット
で送信成功する確率
チャネルが有効な転送に用い
られている割合は高々３７％！
= p(1-p)N-1
ˆ 任意のノードが送信成功
する確率
= Np(1-p)N-1
5: DataLink Layer 5a-27
5: DataLink Layer 5a-28
Pure (unslotted) ALOHA
Pure ALOHA の効率
ˆ unslotted ALOHA: より単純，非同期
P(success by given node) = P(node transmits) .
P(no other node transmits in [t0-1,t0] .
P(no other node transmits in [t0, t0-1]
= p . (1-p)N-1 . (1-p)N-1
ˆ フレームが到着すると
 即時送信
ˆ 衝突確率は増加:
 時刻 t0 に送信されたフレームは [t0-1,t0+1] に送信された他のフレー
ムと衝突する
= p . (1-p)2(N-1)
… 最適なpを選択して，nを無限大にすれば...
= 1/(2e) = .18
さらに悪い !
5: DataLink Layer 5a-29
5: DataLink Layer 5a-30
5
CSMA (Carrier Sense Multiple Access)
CSMA 衝突
ノードの空間的レイアウト
それでも衝突は起こりうる:
CSMA: 送信前に聞く:
ˆ もしチャネルがアイドルなら，全フレームを送信
ˆ もしチャネルがビジーなら，送信を延期
伝播遅延によって二つのノードは
互いの送信を聞くことができない
かもしれない
衝突:
全パケットの送信は時間の無駄
ˆ 人との類似点：他人の会話を邪魔しない！
注意:
距離と伝播遅延が衝突確率の決定
に影響を与える
5: DataLink Layer 5a-31
CSMA/CD (Collision Detection)
5: DataLink Layer 5a-32
CSMA/CD 衝突検出
CSMA/CD: キャリアセンスと送信延期はCSMAと同じ


衝突を短時間に検出
衝突した転送は中止することでチャネル浪費を減少
ˆ 衝突検出:
 有線 LAN では容易：信号強度を計測し，送受信信号を
比較する
 無線 LAN では困難：送信中は受信機はオフ
ˆ 人との類似：礼儀正しい座談家
5: DataLink Layer 5a-33
送信権巡回 MAC protocols
チャネル分割 MAC プロトコル:
高負荷では，チャネルを効率よく，公平に共有
 低負荷では非効率：チャネルアクセスにおける遅延大
，アクティブノードがひとつでも 1/N の帯域が割当て
られる
ランダムアクセス MAC プロトコル

低負荷では効率がよい：ひとつのノードがチャネルを
完全に利用できる
 高負荷：コリジョンオーバヘッド大
送信権巡回プロトコル
 両者の利点を追求

5: DataLink Layer 5a-35
5: DataLink Layer 5a-34
送信権巡回 MAC プロトコル
ポーリング:
トークンパッシング:
ˆ 主局は，順番に従局に
ˆ ノードからノードへ順番にわたさ
送信を問い合わせ
ˆ 問題:
ˆ トークンメッセージ

ポーリングオーバヘッド

遅延
単一故障点（主局）

れるトークンを制御
ˆ 問題:
 トークンオーバヘッド


遅延
単一故障点（トークン）
5: DataLink Layer 5a-36
6
MAC プロトコルのまとめ
LAN 技術
データリンク層（これまで）:
ˆ 共有媒体をどのように扱うか？
 チャネル分割：時間，周波数，符号

つぎ: LAN 技術
• 時分割，周波数分割，符号分割


ランダム分割（動的）
• ALOHA, S-ALOHA, CSMA, CSMA/CD
• 衝突検出: 有線では容易，無線では困難
• CSMA/CD は Ethernet で使用されている

サービス，誤り検出/訂正，多重アクセス

アドレッシング
Ethernet
ハブ，ブリッジ，スイッチ
802.11
 PPP
 ATM


送信権巡回
• 中央局からのポーリング（問い合わせ）
• トークンパッシング
5: DataLink Layer 5a-37
LAN アドレスと ARP
LAN アドレスと ARP
LAN 上の各アダプタは，ユニークな LAN アドレスを有する
32-bit IP アドレス:
ˆ
5: DataLink Layer 5a-38
ネットワーク層アドレス
ˆ 終点IPネットワークにデータグラムを運ぶために利用
(IPネットワークの定義を思い出そう)
LAN (or MAC or physical or Ethernet) アドレス:
ˆ データグラムを，あるインタフェースから物理的に接続された
インタフェースに運ぶために利用 (同一ネットワーク)
ˆ 48 bit MAC アドレス (ほとんどLANで使用)
アダプタの ROM に焼付けられている
5: DataLink Layer 5a-39
LAN アドレス（もっと）
ルーティングについて思い出そう
ˆ MAC アドレス割当ては IEEE によって管理
ˆ 製造業者は，MACアドレス空間の一部を買う（一意性を
保証するために）
ˆ 類似性:
(a) MAC address: 社会保障番号（SSN）に類似
(b) IP address: 郵便アドレス
ˆ 非階層 MAC アドレス => 移植性

5: DataLink Layer 5a-40
カードを LAN から LAN に移動できる
ノード A から B に向けられたIP
データグラム：
223.1.2.1
223.1.1.2
223.1.1.4 223.1.2.9
ˆ B のネットワークアドレスを調べ，B
が A と同一ネットワークにあるとわ
かる
ˆ リンク層はリンク層フレームにデー
タグラムをカプセル化して B に送信
フレーム始点
終点アドレス
B’s MAC A’s MAC
addr
addr
ˆ IP 階層アドレスはポータブルではない
 ノードが接続された IP ネットワークに依存
A 223.1.1.1
B
223.1.1.3
223.1.3.27
223.1.3.1
223.1.2.2
E
223.1.3.2
データグラム始点
終点アドレス
A’s IP
addr
B’s IP
addr
IP payload
datagram
frame
5: DataLink Layer 5a-41
5: DataLink Layer 5a-42
7
ARP: Address Resolution Protocol
疑問: B の IP アドレスを知っているとして，
どうやって B の MAC アドレスを知るか
ARP プロトコル
ˆ LAN 上の各 IP ノード（ノ
ード，ルータ）は，ARPテー
ブルをもつ
ˆ ARPテーブル: 同一 LAN
ノードにおける IP/MAC
アドレスマッピング
< IP address; MAC address; TTL>

TTL (Time To Live): アド
レスマッピングを忘れるまで
の時間（通常，２０分）
ˆ A は B にデータグラムを転送
したい，A は B の IP アドレス
を知っている
ˆ B のマックアドレスが A の
ARP テーブルがないと仮定し
よう
ˆ A は，B の IP アドレスを含む
ARP クエリパケットをブロード
キャストする
 LAN 上の全マシンは ARP
クエリを受信
ˆ B は ARP パケットを受信する
と，自身（B）の MAC アドレス
を A に応答する

ˆ A は情報が古くなるまで（タイ
ムアウトするまで） IP-toMAC アドレス対をARPテーブ
ルにキャッシュ（セーブ）する
 ソフトステート: リフレッシュ
されなければタイムアウト
する情報
ˆ ARP は “plug-and-play”:
 ノードは ARP テーブルを，
ネットワーク管理者が介在
することなく生成
A の MAC アドレスに送信さ
れる（ユニキャスト）
5: DataLink Layer 5a-43
他の LAN へのルーティング
5: DataLink Layer 5a-44
ˆ A は，始点A，終点Bのデータグラムを生成
ˆ A はARPを使って111.111.111.110に対するRのMAC アドレスを入手
ˆ A はRのMACアドレスを終点とするリンク層フレームを生成する．フ
段階的説明: AからBへRを介してデータグラムを送信
AはBのIPアドレスを知っていると仮定
レームはAからBへのIPデータグラムを含む
ˆ A のデータリンク層はフレームを送信
ˆ R のデータリンク層はフレームを受信
ˆ R はEthernetフレームからIPデータグラムを抽出し，これがB向け
であることを知る
ˆ R はBのMACアドレスを得るためにARPを使用する
ˆ R はAからBへのIPデータグラムを生成し，Bに送信する
A
A
R
B
ˆ ルータ R は二つのARPテーブルをもつ，各 IP ネットワー
ク（LAN）に対して一つもつ
R
5: DataLink Layer 5a-45
B
5: DataLink Layer 5a-46
Ethernet
Ethernet フレーム構造
最も普及している LAN 技術:
ˆ 100Mbsでも$20と安い！
ˆ トークンLANやATMよりも原理が簡単で安い
ˆ 速度競争でも負けていない: 10, 100, 1000 Mbps
送信アダプタは IPデータグラム（または他のネットワーク層
プロトコル）をEthernetフレームにカプセル化
Metcalfe’s Ethernet
sketch
5: DataLink Layer 5a-47
プリアンブル:
ˆ パターン10101010が7バイト続き，その後，パターン
10101011が１バイト続く
ˆ 送受信側のクロックレートを同期させるために利用
5: DataLink Layer 5a-48
8
Ethernet フレーム構造（つづき）
ˆ Address: 6 bytes
 アダプタが終点アドレスと自身のMACアドレスと一致するフレー
ムあるいはブロードキャストアドレス（例えば，ARPパケット）を受
信すると，フレームをネットワーク層プロトコルに渡す
 そうでなければ，アダプタはフレームを廃棄する
低信頼，コネクションレスサービス
ˆ コネクションレス: 送受信アダプタ間でハンドシェイクなし
ˆ 低信頼: 受信アダプタは送信アダプタに ACK や NACK
を返信しない
トコル．Novell IPX and AppleTalkなどもサポート．

ネットワーク層にわたされるデータグラムストリームには（フレー
ム廃棄による）ギャップ（抜け）がありうる
アプリがTCPを使用していればギャップを埋めることができる
ˆ CRC: 受信局でチェック，誤り検出の場合，フレーム廃棄

そうでなければ，アプリにはギャップがそのまま伝わる
ˆ Type: 上位層プロトコルを示す．たいていの場合 IPプロ

5: DataLink Layer 5a-49
Ethernet における CSMA/CD
ˆ スロットなし
ˆ 再送を試みる前に，ランダ
ム時間まつ，すなわちラン
ダムアクセス（random
access）
ˆ アダプタは，他のアダプタの
送信を検出（carrier sense）
すれば，送信をおこなわない
ˆ 送信中のアダプタが他のア
ダプタの送信を検出すれば，
送信を中止する（collision
detection）
5: DataLink Layer 5a-50
Ethernet CSMA/CD アルゴリズム
4. もしアダプタがフレーム送信
1. アダプタはデータグラムを上
中に他のフレーム送信を検出
位層から受け取るとフレーム
すれば，送信を中止し，ジャ
を生成
ム信号を送信
2. アダプタがチャネルがアイド
ルであることを検出すると，フ 5. 送信中止後，アダプタは，指
数バックオフ（exponential
レーム送信を開始．チャネル
backoff）をおこなう： m 回目
がビジーであることを検出す
の衝突の直後，アダプタは値
ると，アイドルになるまで待っ
K をランダムに{0,1,2,…,2m-1}
てから送信
から選択．アダプタは，
3. アダプタが他のフレーム送信
K*512 ビットタイム（ビット送
を検出することなくフレーム全
信時間）待ち，ステップ２に戻
体を送信すれば，フレーム送
る
信を終了
5: DataLink Layer 5a-51
Ethernet’s CSMA/CD （つづき）
ジャム信号: 他の全てのアダプタ
に衝突の発生を確実に知らせ
る；48 bits;
ビットタイム: 10 Mbps Ethernet
では 0.1 microsec； K=1023
の場合，約50 msec 待つ
指数バックオフ:
ˆ 目的: アダプタは，現在のトラ
ヒック負荷を推測しながら再送
をおこなう

5: DataLink Layer 5a-52
CSMA/CD の効率
ˆ Tprop = LANにおける2ノード間最大伝播遅延
ˆ ttrans = 最大サイズフレーム送信時間
高負荷時：ランダム待ち時間
は長くなる
efficiency =
ˆ 最初の衝突: K は{0,1}から選
ぶ；遅延は K x 512ビット送信
時間
ˆ ２回目の衝突以降： K を{0, 1,
2, 3} から選ぶ
ˆ １０回目の衝突以降，K を
{0,1,2,3,4,…,1023} から選ぶ
5: DataLink Layer 5a-53
1
1 + 5t prop / ttrans
ˆ 効率は，tprop が 0 に近づくと，1 に近づく
ˆ ttrans が無限大になれば 1 に近づく
ˆ ALOHA よりずっと効率が良く，また分散型で，簡単，安
い
5: DataLink Layer 5a-54
9
10BaseT and 100BaseT
Ethernet 技術: 10Base2
ˆ 10: 10Mbps; 2: 最大ケーブル長 200 meters
ˆ バストポロジ，細い同軸ケーブル(thin coaxial cable)
ˆ 10/100 Mbps rate; 後に “fast ethernet” と呼ばれる
ˆ T は Twisted Pair （より対線）をあらわす
ˆ ノードはハブに接続される: “スター型トポロジ”; ノード・ハ
ブ間の最大距離は 100 m
nodes
hub
ˆ ハブは，本質的には物理層リピータ（馬鹿ハブのこと）
ˆ 複数のセグメントを接続するためにリピータを使用
ˆ リピータは一方にインタフェースで聞こえた信号を他方のイ
ンタフェースに増幅して送信：物理層デバイスのみ
ˆ もはや古い技術になった
5: DataLink Layer 5a-55
Manchester 符号
あるリンクからきたビット列を他のリンクに流す
フレームバッファリングなし
 ハブはCSMA/CDをおこなわない：アダプタがコリジョ
ンを検出する
 ネットワーク管理機能を提供する


5: DataLink Layer 5a-56
Gbit Ethernet
ˆ Ethernet frame フォーマットを使用
ˆ ポイント・ツー・ポイントリンク，共有ブロードキャストチャ
ネルでの使用が可能
ˆ 共有モードでは，CSMA/CD を使用，効率をあげるため
にはノード間距離を短くする
ˆ “Buffered Distributors”と呼ばれるハブを使用する
ˆ 10BaseT, 10Base2で使用される
ˆ ポイント・ツー・ポイント接続では 1 Gbps 全二重
ˆ 各ビットが遷移をもつ
ˆ 送受信ノードが互いにクロック同期することを可能にする
 クロック同期をノード間で分散して実現できる
ˆ 現在では 10 Gbps
ˆ ただしこれは物理層の内容
5: DataLink Layer 5a-57
Chapter 5 内容
ˆ 5.1 イントロダクションとサ
ˆ
ˆ
ˆ
ˆ
ービス
5.2 誤り検出と訂正
5.3 多重アクセスプロトコ
ル
5.4 LAN アドレスとARP
5.5 イーサーネット
5: DataLink Layer 5a-58
LAN セグメント間接続
ˆ 5.6 ハブ，ブリッジ，スイッ
ˆ
ˆ
ˆ
ˆ
チ
5.7 無線リンク，ＬＡＮ
5.8 PPP
5.9 ATM
5.10 フレームリレー
5: DataLink Layer 5a-59
ˆ ハブ
ˆ ブリッジ
ˆ スイッチ
 注意: スイッチは本質的にはマルチポートブリッジ

ブリッジに関することはスイッチにもあてはまる
5: DataLink Layer 5a-60
10
ハブによる接続（いわゆるバカハブ）
ˆ バックボーンハブは LAN セグメントを相互接続
ブリッジ
ˆ リンク層デバイス
ˆ ノード間の最大距離を拡張

ˆ 各セグメントのコリジョンドメインは統合され一つの大きなコリジ

ョンドメインになる

CS 内のノードと EE 内のノードが同時送信した場合：衝突
ˆ 10BaseT と 100BaseT は相互接続できない
イーサネットフレームを蓄積，転送
フレームヘッダの MAC 終点アドレスにもとづいて選
択的にフレームを転送
 フレームをフォワードする必要があるときは，
CSMA/CD によりセグメントにアクセス
ˆ 透過性

ホストはブリッジの存在には気づかない
ˆ プラグ・アンド・プレイ，自己学習

ブリッジを設定する必要はない
5: DataLink Layer 5a-61
ブリッジ：トラヒックの分離
5: DataLink Layer 5a-62
フォワーディング
ˆ LAN を複数の LAN セグメントに分割できる
ˆ ブリッジはパケットをフィルタリングできる：
始点，終点 MAC アドレスが同じ LAN セグメントにあ
るフレームは，他のセグメントにフォワードされない
 セグメントは，分離されたコリジョンドメインになる

collision
domain
collision
domain
bridge
LAN segment
= hub
= host
どの LAN セグメントにフレームをフォワードすべきかをど
のように決定するのか？
LAN segment
LAN (IP network)
5: DataLink Layer 5a-63
5: DataLink Layer 5a-64
フィルタリング／フォワーディング
自己学習
When bridge receives a frame:
ˆ ブリッジはブリッジテーブルをもつ
ˆ ブリッジテーブルの内容:
(Node LAN Address, Bridge Interface, Time Stamp)
 古いエントリは廃棄（TTL は 60 minなどに設定）

ˆ ブリッジはどのホストがどのインタフェースから到達可能かを
学習する
 フレームを受信した際に，送信の場所（フレームがやってき
た LAN セグメント）を学習する

送信（アドレス）／位置（インタフェース）ペアをブリッジテー
ブルに記録
5: DataLink Layer 5a-65
index bridge table using MAC dest address
if entry found for destination
then{
if dest on segment from which frame arrived
then drop the frame
else forward the frame on interface indicated
}
else flood
forward on all but the interface
on which the frame arrived
5: DataLink Layer 5a-66
11
ブリッジ学習の例
ブリッジ学習の例
C が D にフレーム送信し，D が C に応答する場合を考える
ˆ ブリッジは C からのフレームを受信
 ブリッジテーブル内に C がインタフェース１側にいると記録
 D はテーブルにないため，ブリッジはインタフェース２，３にフレー
ムをフォワード
ˆ D がフレームを受信
ˆ D は C へのフレームを生成し，C へ送信
ˆ ブリッジはフレーム受信


ブリッジテーブルに D がインタフェース２側にいることを記録
ブリッジは C がインタフェース１側にいることを知っているので，
選択的にインタフェース１にフレームをフォワーディング
5: DataLink Layer 5a-67
バックボーンのない相互接続例
5: DataLink Layer 5a-68
バックボーン構成
ˆ 二つの理由からお勧めではない:
- コンピュータ学科のハブが故障するだめ
- EE と SE 間の全トラヒックが CS セグメントを通過する
5: DataLink Layer 5a-69
5: DataLink Layer 5a-70
ブリッジ スパニングツリー
ブリッジの特徴
ˆ 信頼性をあげるために，始点から終点までの冗長・予備
ˆ コリジョンドメインの分割は，トータルの最大スループット
パスをもつことが望ましい
ˆ マルチパスについては，ループが発生しうる- ブリッジが
bridges may multiply and forward frame forever
ˆ ノード数や地理的カバーエリアの制約がなくなる
ˆ 解：インタフェースの部分集合を無効化することでスパニ
ˆ 透過的 (“plug-and-play”): 設定の必要なし
ング木を構成する
を増加させる
ˆ 異なる Ethernet を接続できる
Disabled
5: DataLink Layer 5a-71
5: DataLink Layer 5a-72
12
ブリッジかルータか
ルータかブリッジか
ˆ どちらも蓄積・転送デバイス
 ルータ: ネットワーク層デバイス（ネットワーク層ヘッダを調べる）

ブリッジはリンク層デバイス
ˆ ルータはルーティングテーブルをもち，経路制御アルゴリ
ズムを実装
ˆ ブリッジはブリッジテーブルをもち，フィルタリング，自己学
習，スパニング木アルゴリズムを実装
ブリッジの + と + ブリッジ動作はパケット処理よりもずっと簡単
+ ブリッジテーブルは自己学習
- 別経路の帯域が空いていたとしても全トラヒックがスパニ
ング木で制約される
- ブリッジは，ブロードキャストストーム（ブロードキャストの
嵐）から守ってくれない
5: DataLink Layer 5a-73
5: DataLink Layer 5a-74
イーサネットスイッチ
ルータかブリッジか
ルータの + と + 任意のトポロジを想定可能で，パケットの巡回は TTL カウン
タ（あるいは良い経路制御）で制限可能
+ ブロードキャストストームからの保護
- IPアドレスの設定が必要（プラグアンドプレイじゃない）
- より高い負荷のパケット処理が必要
ˆ ブリッジは小さなネットワーク向け（数百ホスト），ルータは大
規模ネットワーク向け（数千ホスト）
ˆ 本質的にはマルチインタフェー
スブリッジ
ˆ レイヤ２（フレーム）フォワーディ
ング，LANアドレスによるフィル
タリング
ˆ スイッチング: AからA’，BからB’
への同時送信可能，衝突なし
ˆ 多数のインタフェース
ˆ 一般的に，個々のホストはスイ
ッチにスター接続
 Ethernetだけど衝突なし
5: DataLink Layer 5a-75
Ethernet スイッチ
5: DataLink Layer 5a-76
一般的 LAN 構成 (IP network)
Dedicated
ˆ カットスルースイッチ: 全フレームの到着をまたず
に入力ポートから出力ポートにフレームをフォワ
ーディング
 若干遅延を改善
ˆ 10/100/1000 Mbps インタフェースの共有/専
用の組み合わせ可能
5: DataLink Layer 5a-77
Shared
5: DataLink Layer 5a-78
13
Chapter 5 内容
まとめと比較
hubs
bridges
routers
switches
traffic
isolation
no
yes
yes
yes
plug & play
yes
yes
no
yes
optimal
routing
cut
through
no
no
yes
no
yes
no
no
yes
ˆ 5.1 イントロダクションとサ
ˆ
ˆ
ˆ
ˆ
ービス
5.2 誤り検出と訂正
5.3 多重アクセスプロトコ
ル
5.4 LAN アドレスとARP
5.5 イーサーネット
ˆ 5.6 ハブ，ブリッジ，スイッ
チ
ˆ 5.7 無線リンク，ＬＡＮ
ˆ 5.8 PPP
ˆ 5.9 ATM
ˆ 5.10 フレームリレー
5: DataLink Layer 5a-79
ベースステーション型
IEEE 802.11 無線 LAN
ˆ 802.11b
 2.4-5 GHz unlicensed
radio spectrum
 最大 11 Mbps
 物理層：direct sequence
spread spectrum
(DSSS)


• 全ホストは同じ拡散符
号を使用
広く普及
ベースステーションを使用
5: DataLink Layer 5a-80
ˆ 802.11a
 5-6 GHz range
 最大 54 Mbps
ˆ 802.11g
 2.4-5 GHz range
 最大 54 Mbps
ˆ 多重アクセスに
ˆ 無線ホストはベースステーションと通信
 base station = access point (AP)
ˆ Basic Service Set (BSS) (“cell”) は以下から構成:
wireless hosts
access point (AP): base station
ˆ BSSs を接続し，分散システム（distribution system: DS
）を構築


CSMA/CA を使用
ˆ 全て，ベースステーション
モードとアドホックモード
がある
5: DataLink Layer 5a-81
5: DataLink Layer 5a-82
IEEE 802.11: 多重アクセス
アドホックネットワーク型
ˆ 複数ノードが同時転送すると衝突発生
ˆ AP (ベースステーション)なし
ˆ CSMA は意味がある:
ˆ 無線ホストは互いに通信
ホストAからBにパケットを届けるためにはホストX, Y,
Z を経由しなければならないかもしれない
ˆ アプリケーション:
 会議室における“laptop”ミーティング



送信時は全帯域を使用
他の送信を検出したときは送信すべきではない
ˆ 衝突検出はうまく機能しない： 隠れ端末問題（hidden
terminal problem）
パーソナルデバイスの相互接続
戦場
ˆ IETF MANET
(Mobile Ad hoc Networks)
working group


5: DataLink Layer 5a-83
5: DataLink Layer 5a-84
14
IEEE 802.11 MAC プロトコル: CSMA/CA
802.11 CSMA: 送信局
- DISF sec. 間チャネルがアイド
ルと検出すれば全フレームを送
信（衝突非検出）
- チャネルビジーを検出すると，バ
イナリバックオフ
802.11 CSMA 受信局
- 受信成功なら
SIFS後にACK返信
(隠れ端末問題のためにACKが
必要)
衝突回避メカニズム
ˆ 問題：


互いに隠れ端末関係にある二つのノードがベースステーションに
同時送信
長期間帯域を浪費！
ˆ 解決方法:


小さな予約パケットを使用
各ノードは，内部の “network allocation vector”
(NAV)により予約期間を管理
5: DataLink Layer 5a-85
衝突回避: RTS-CTS交換
衝突回避: RTS-CTS 交換
ˆ RTS と CTS は短い:
ˆ 送信局は短いRTS
(request to send) パケッ
トを送信: 送信間隔が含ま
れている
ˆ 受信局は，短いCTS (clear
to send) パケットでもって
応答

5: DataLink Layer 5a-86
短時間なので衝突が発生し
にくい
 結果として衝突検出と同様
の効果がある
ˆ IEEE 802.11は以下が可能:
 CSMA
 CSMA/CA: reservations
 polling from AP

周囲のノード（送信端末から
みて隠れ端末の可能性のあ
る）にこれからデータパケット
を受信することを通知
ˆ 隠れ端末は，ある一定の間
（NAV）送信しない
5: DataLink Layer 5a-87
Bluetooth について
ˆ 小電力短距離無線技術
 10-100 meters
ˆ 無指向
 赤外線通信ではない（見通
せないとだめ）
ˆ 装置間接続
ˆ 2.4-2.5 GHz 特定小電力
無線(免許不要)
ˆ 最大 721 kbps
5: DataLink Layer 5a-88
Chapter 5 outline
ˆ 無線 LAN，ディジタルコー
ドレス電話，電子レンジとの
干渉:

サポート:

ˆ 5.6 Hubs, bridges, and
ˆ
ˆ 5.7 Wireless links and
周波数ホッピング
ˆ MAC プロトコルは以下を

ˆ 5.1 Introduction and
誤り訂正
ARQ
ˆ
ˆ
ˆ 各ノードは12-bitアドレスを
もつ
5: DataLink Layer 5a-89
ˆ
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 LAN addresses
and ARP
5.5 Ethernet
switches
LANs
ˆ 5.8 PPP
ˆ 5.9 ATM
ˆ 5.10 Frame Relay
5: DataLink Layer 5a-90
15
Point to Point Data Link Control
ˆ one sender, one receiver, one link: easier than
broadcast link:
 no Media Access Control
 no need for explicit MAC addressing
 e.g., dialup link, ISDN line
ˆ popular point-to-point DLC protocols:
 PPP (point-to-point protocol)
 HDLC: High level data link control (Data link
used to be considered “high layer” in protocol
stack!
PPP Design Requirements [RFC 1557]
ˆ packet framing: encapsulation of network-layer
ˆ
ˆ
ˆ
ˆ
datagram in data link frame
 carry network layer data of any network layer
protocol (not just IP) at same time
 ability to demultiplex upwards
bit transparency: must carry any bit pattern in the
data field
error detection (no correction)
connection liveness: detect, signal link failure to
network layer
network layer address negotiation: endpoint can
learn/configure each other’s network address
5: DataLink Layer 5a-91
5: DataLink Layer 5a-92
PPP non-requirements
PPP Data Frame
ˆ no error correction/recovery
ˆ Flag: delimiter (framing)
ˆ no flow control
ˆ Address: does nothing (only one option)
ˆ out of order delivery OK
ˆ Control: does nothing; in the future possible
ˆ no need to support multipoint links (e.g., polling)
multiple control fields
ˆ Protocol: upper layer protocol to which frame
delivered (eg, PPP-LCP, IP, IPCP, etc)
Error recovery, flow control, data re-ordering
all relegated to higher layers!
5: DataLink Layer 5a-93
5: DataLink Layer 5a-94
PPP Data Frame
Byte Stuffing
ˆ info: upper layer data being carried
ˆ “data transparency” requirement: data field must
be allowed to include flag pattern <01111110>
 Q: is received <01111110> data or flag?
ˆ check: cyclic redundancy check for error
detection
ˆ Sender: adds (“stuffs”) extra < 01111110> byte
after each < 01111110> data byte
ˆ Receiver:
two 01111110 bytes in a row: discard first byte,
continue data reception
 single 01111110: flag byte

5: DataLink Layer 5a-95
5: DataLink Layer 5a-96
16
Byte Stuffing
PPP Data Control Protocol
Before exchanging networklayer data, data link peers
must
ˆ configure PPP link (max.
frame length,
authentication)
ˆ learn/configure network
layer information
 for IP: carry IP Control
Protocol (IPCP) msgs
(protocol field: 8021) to
configure/learn IP
address
flag byte
pattern
in data
to send
flag byte pattern plus
stuffed byte in
transmitted data
5: DataLink Layer 5a-97
Chapter 5 outline
Asynchronous Transfer Mode: ATM
ˆ 5.1 Introduction and
ˆ 5.6 Hubs, bridges, and
ˆ
ˆ
ˆ
ˆ
ˆ
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 LAN addresses
and ARP
5.5 Ethernet
ˆ
ˆ
ˆ
5: DataLink Layer 5a-98
ˆ 1990’s/00 standard for high-speed (155Mbps to
622 Mbps and higher) Broadband Integrated
Service Digital Network architecture
ˆ Goal: integrated, end-end transport of carry voice,
switches
5.7 Wireless links and
LANs
5.8 PPP
5.9 ATM
5.10 Frame Relay
video, data
meeting timing/QoS requirements of voice, video
(versus Internet best-effort model)
 “next generation” telephony: technical roots in
telephone world
 packet-switching (fixed length packets, called
“cells”) using virtual circuits

5: DataLink Layer 5a-99
ATM architecture
5: DataLink Layer
5a100
ATM: network or link layer?
Vision: end-to-end
transport: “ATM from
desktop to desktop”
 ATM is a network
technology
Reality: used to connect
IP backbone routers
 “IP over ATM”
 ATM as switched
link layer,
connecting IP
routers
ˆ adaptation layer: only at edge of ATM network
data segmentation/reassembly
roughly analogous to Internet transport layer
ˆ ATM layer: “network” layer
 cell switching, routing
ˆ physical layer


5: DataLink Layer
5a101
5: DataLink Layer
5a102
17
ATM Adaptation Layer (AAL) [more]
ATM Adaptation Layer (AAL)
Different versions of AAL layers, depending on ATM
service class:
ˆ ATM Adaptation Layer (AAL): “adapts” upper
layers (IP or native ATM applications) to ATM
layer below
ˆ AAL present only in end systems, not in switches
ˆ AAL layer segment (header/trailer fields, data)
fragmented across multiple ATM cells
 analogy: TCP segment in many IP packets
ˆ AAL1: for CBR (Constant Bit Rate) services, e.g. circuit emulation
ˆ AAL2: for VBR (Variable Bit Rate) services, e.g., MPEG video
ˆ AAL5: for data (e.g., IP datagrams)
User data
AAL PDU
ATM cell
5: DataLink Layer
AAL5 - Simple And Efficient
AL (SEAL)
Service: transport cells across ATM network
ˆ analogous to IP network layer
ˆ very different services than IP network layer
datagrams
4 byte cyclic redundancy check
 PAD ensures payload multiple of 48bytes
 large AAL5 data unit to be fragmented into 48byte ATM cells
Network
Architecture

Internet
Service
Model
Guarantees ?
Congestion
Bandwidth Loss Order Timing feedback
best effort none
ATM
CBR
ATM
VBR
ATM
ABR
ATM
UBR
constant
rate
guaranteed
rate
guaranteed
minimum
none
no
no
no
yes
yes
yes
yes
yes
yes
no
yes
no
no
yes
no
no (inferred
via loss)
no
congestion
no
congestion
yes
no
5: DataLink Layer
5a105
ATM Layer: Virtual Circuits
5a106
ATM VCs
ˆ VC transport: cells carried on VC from source to dest
 call setup, teardown for each call before data can flow
 each packet carries VC identifier (not destination ID)
 every switch on source-dest path maintain “state” for each
passing connection
 link,switch resources (bandwidth, buffers) may be allocated to
VC: to get circuit-like perf.
ˆ Permanent VCs (PVCs)
long lasting connections
typically: “permanent” route between to IP routers
ˆ Switched VCs (SVC):
 dynamically set up on per-call basis


5: DataLink Layer
5a104
ATM Layer
ˆ AAL5: low overhead AAL used to carry IP
5: DataLink Layer
5: DataLink Layer
5a103
5a107
ˆ Advantages of ATM VC approach:
QoS performance guarantee for connection
mapped to VC (bandwidth, delay, delay jitter)
ˆ Drawbacks of ATM VC approach:
 Inefficient support of datagram traffic
 one PVC between each source/dest pair) does
not scale (N*2 connections needed)
 SVC introduces call setup latency, processing
overhead for short lived connections

5: DataLink Layer
5a108
18
ATM Layer: ATM cell
ATM cell header
ˆ 5-byte ATM cell header
ˆ VCI: virtual channel ID
ˆ 48-byte payload

Why?: small payload -> short cell-creation delay
for digitized voice
 halfway between 32 and 64 (compromise!)

will change from link to link thru net
ˆ PT: Payload type (e.g. RM cell versus data cell)
ˆ CLP: Cell Loss Priority bit
CLP = 1 implies low priority cell, can be
discarded if congestion
ˆ HEC: Header Error Checksum
 cyclic redundancy check

Cell header
Cell format
5: DataLink Layer
5: DataLink Layer
5a109
ATM Physical Layer (more)
ATM Physical Layer
Two pieces (sublayers) of physical layer:
Physical Medium Dependent (PMD) sublayer
ˆ Transmission Convergence Sublayer (TCS): adapts
ˆ SONET/SDH: transmission frame structure (like a
ATM layer above to PMD sublayer below
ˆ Physical Medium Dependent: depends on physical
medium being used
container carrying bits);
 bit synchronization;
 bandwidth partitions (TDM);
 several speeds: OC3 = 155.52 Mbps; OC12 = 622.08
TCS Functions:
 Header checksum generation: 8 bits CRC
 Cell delineation
 With “unstructured” PMD sublayer, transmission
of idle cells when no data cells to send
5: DataLink Layer
IP-Over-ATM
Classic IP only
ˆ 3 “networks” (e.g.,
LAN segments)
ˆ MAC (802.3) and IP
addresses
Mbps; OC48 = 2.45 Gbps, OC192 = 9.6 Gbps
ˆ TI/T3: transmission frame structure (old
telephone hierarchy): 1.5 Mbps/ 45 Mbps
ˆ unstructured: just cells (busy/idle)
5a112
IP-Over-ATM
IP over ATM
ˆ replace “network”
(e.g., LAN segment)
with ATM network
ˆ ATM addresses, IP
addresses
Ethernet
LANs
5: DataLink Layer
5a111
ATM
network
Ethernet
LANs
5a110
5: DataLink Layer
5a113
Issues:
ˆ IP datagrams into
ATM AAL5 PDUs
ˆ from IP addresses
to ATM addresses
 just like IP
addresses to
802.3 MAC
addresses!
ATM
network
Ethernet
LANs
5: DataLink Layer
5a114
19
Datagram Journey in IP-over-ATM Network
ˆ at Source Host:
 IP layer maps between IP, ATM dest address (using ARP)
 passes datagram to AAL5
 AAL5 encapsulates data, segments cells, passes to ATM layer
ˆ ATM network: moves cell along VC to destination

ˆ 5.1 Introduction and
ˆ 5.6 Hubs, bridges, and
ˆ
ˆ 5.7 Wireless links and
ˆ
ˆ at Destination Host:

Chapter 5 outline
AAL5 reassembles cells into original datagram
if CRC OK, datagram is passed to IP
ˆ
ˆ
5: DataLink Layer
services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 LAN addresses
and ARP
5.5 Ethernet
switches
LANs
ˆ 5.8 PPP
ˆ 5.9 ATM
ˆ 5.10 Frame Relay
5: DataLink Layer
5a115
Frame Relay
5a116
Frame Relay
ˆ Designed in late ‘80s, widely deployed in the ‘90s
Like ATM:
ˆ Frame relay service:
ˆ wide area network technologies

ˆ Virtual-circuit oriented

no error control
end-to-end congestion control
ˆ origins in telephony world
ˆ can be used to carry IP datagrams
 can
thus be viewed as link layers by IP
protocol
5: DataLink Layer
5: DataLink Layer
5a117
Frame Relay (more)
5a118
Frame Relay (more)
ˆ Designed to interconnect corporate customer LANs
typically permanent VC’s: “pipe” carrying aggregate
traffic between two routers
 switched VC’s: as in ATM
ˆ corporate customer leases FR service from public
Frame Relay network (e.g., Sprint, ATT)
flags address
data
CRC
flags

5: DataLink Layer
5a119
ˆ Flag bits, 01111110, delimit frame
ˆ address:


10 bit VC ID field
3 congestion control bits
• FECN: forward explicit congestion
notification (frame experienced congestion
on path)
• BECN: congestion on reverse path
• DE: discard eligibility
5: DataLink Layer
5a120
20
Frame Relay -VC Rate Control
Frame Relay - CIR & Frame Marking
ˆ Committed Information Rate (CIR)
ˆ Access Rate: rate R of the access link between
defined, “guaranteed” for each VC
 negotiated at VC set up time
 customer pays based on CIR

ˆ DE bit: Discard Eligibility bit
Edge FR switch measures traffic rate for each VC;
marks DE bit
 DE = 0: high priority, rate compliant frame; deliver
at “all costs”
 DE = 1: low priority, eligible for congestion discard

5: DataLink Layer
5a121
source router (customer) and edge FR switch
(provider); 64Kbps < R < 1,544Kbps
ˆ Typically, many VCs (one per destination router)
multiplexed on the same access trunk; each VC has
own CIR
ˆ Edge FR switch measures traffic rate for each
VC; it marks (i.e. DE = 1) frames which exceed CIR
(these may be later dropped)
ˆ Internet’s more recent differentiated service
uses similar ideas
5: DataLink Layer
5a122
Chapter 5: Summary
ˆ principles behind data link layer services:
 error detection, correction
 sharing a broadcast channel: multiple access
 link layer addressing, ARP
ˆ link layer technologies: Ethernet, hubs,
bridges, switches,IEEE 802.11 LANs, PPP,
ATM, Frame Relay
ˆ journey down the protocol stack now OVER!
 next stops: multimedia, security, network
management
5: DataLink Layer
5a123
21