ホーム » 2022 » 10月 » 18

日別アーカイブ: 2022年10月18日

2022年10月
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

検索・リンク

Ethernet と CSMA/CD方式

CSMA/CD方式

Ethernet では、1本の線を共有するバス型であり、複数の機器が同時に信号を出力すると、電圧の高低がおかしい状態となる(衝突,コリジョン)ため、同時に信号を出さない工夫が必要となる。ただし、他の人が信号線を使っていないことを確認してから、信号を出せばいいけど、確認から信号を出すまでの遅延により、衝突を避けるのは難しい。

また、1本の線を共有する機器の数が増えてくると、衝突の発生の可能性が高まってくる。

これらの問題を解決するためのルールが CSMA/CD(Carrier Sense Multiple Access with Collision Detection)方式である。

  • 機器は、信号を出す場合、信号線が空いている状態を待ち、出力を行う。
  • もし、複数の機器が同時に信号を出した場合、電圧異常を検知したら衝突なので再送を試みる。
  • 再送を行う場合には、乱数時間待つ。(機器が多い場合は、これでも衝突が起こるかもしれない)
  • 乱数時間待っても信号線が空かない場合は、乱数時間の単位時間を倍にする。

どちらにしろ、バス共有する機器の台数が増えてくると、衝突の可能性は高まり、100台を越えるような状態は通信効率も悪くなる。

ただし、最近はスイッチングHUBで通信制御を行うことが一般的になり、CSMA/CD方式が使われることは減っている。

スイッチングHUB

*BASE-T のような、HUB による接続では、複数の機器が異なる機器どうしで通信をする場合、その通信路を時分割多重するのではなく、通信相手に応じて内部回路を直接つながるように接続するスイッチングHUB(以下SW-HUB)が普及している。

バス型通信では、1本の線を共有するため、同じネットワーク内の別機器間の通信は、傍受することができる(タッピング)。しかし、SW-HUB の場合、機器同士が直接つながるので、傍受するのが困難であり、セキュリティ的にも望ましい。

データリンク層とMACアドレス

前述のように、1つのバス型接続のネットワーク内部には、同時に設置できる機器の数には限界がある。このため、小さなネットワークに分割したもの(サブネット)を、ブリッジやルータで接続し、隣接するサブネットにサブネット内の通信情報が出ないように分割することを行う。

Ethernetに接続する機器は、機器ごとにユニークな番号(MACアドレス)を持っている。このMACアドレスは、8bit✕6個の48bitの値で、メーカー毎に割振られた範囲の値を、機器ごとに異なる値がついている。

通信は、一般的に1500byte程のパケットを単位として送受信が行われる。サブネット内の通信では、自分宛のパケットかどうかをMACアドレスを見て受け取る。これらのレイヤーは、データリンク層と呼ばれる。

旧式のHUB(Dumb HUB)は、電気的に信号を増幅するだけなので、物理層(レイヤー1)だけで通信を行う。
スイッチングHUBは、MACアドレスを見て通信相手を判断(データリンク層/レイヤー2)する。最近では、SW-HUBのコネクタ毎に、パケットにタグを付加することで、1本のネットワーク経路に仮想的な複数のネットワークを構築するタグV-LANといった方式を使う場合もある。このような機能を持つSW-HUBは特にレイヤ2スイッチとも呼ばれる。

L2スイッチとL3スイッチ

サブネットに分割し、それぞれに異なるネットワーク番号を割り振り、中継するルータで FireWall を機能させることで、セキュリティを高めることが行われる。しかし、性能の高いスイッチングHUBは高価でもあり、1つのHUBに異なるネットワークを接続する必要がでてくることもある。この場合、IPアドレスを異なるネットワークの番号を偽装されると、データが盗み見られるかもしれない。

こういった相互に分離すべきネットワークであっても、柔軟なネットワーク構成とするためには、VLAN機能を持った L2スイッチ(レイヤ2スイッチングHUB) が使われる。タグVLAN機能付きのL2スイッチでは、特定のポートにVLANのタグ番号を割り当て、ポートに入る時にパケットに VLAN のタグ情報を付加し、そのパケットは同じ VLAN のタグをもつポートからしかデータを取り出せない。

L2スイッチ(レイヤ2スイッチ)は、機器のMACアドレスやパケットに付けられたVLANのタグ番号の情報(レイヤ2=データリンク層)でパケットの流れを制御している(下記OSI参照モデルの表を参照)。最近では、許可されていない機器がネットワークに侵入する不正侵入を防ぐために、登録されていないMACアドレスのパケットを通さないといった機能がある。

OSI参照モデルとレイヤ
第7層 アプリケーション層 アプリケーションの種類の規定
第6層 プレゼンテーション層 データフォーマットの交換
第5層 セッション層 コネクションの確立や切断などの管理
第4層 トランスポート層 パケットの分割合成や再送といった管理(TCP)
第3層 ネットワーク層 隣接するネットワーク間の通信(IPアドレス)
第2層 データリンク層 直接接続された機器間の通信(MACアドレス)
第1層 物理層 物理的な接続方法(コネクタや電圧など)

スイッチングHUBの中には、レイヤ3(IPアドレス)の情報でパケットの流れを制御するものもある。こういったスイッチは、L3スイッチ(レイヤ3スイッチ)と呼ばれるが、機能的にはルータと同じである。

一般的には、LANとWANを接続するための機器はルータ、LAN内部のネットワークを分離するためのものはL3スイッチと呼ぶ。

無線LANと暗号化

無線LAN(通称 WiFi)は、IEEE 802.11 にて規格が定められている。無線LANは、使う通信周波数で、2.4GHz帯を使うものと、最近増えてきた5GHz帯のものに分けられる。

  • IEEE802.11a 5GHz帯を使う、最大54Mbps
  • IEEE802.11b 2.4GHz帯を使う、最大11Mbps
  • IEEE802.11g 2.4GHz帯を使う、最大54Mbps
  • IEEE802.11n 2.4GHz/5GHzを使う、最大600Mbps
  • IEEE802.11ac 5GHz帯を使う、最大6.9GBps
  • IEEE802.11ad 60GHz 最大6.8Gbps
  • IEEE802.11ax 2.4GHz/5GHz 最大 9.6Gbps

2.4GHz帯は、電子レンジで使う電波の周波数と重なるため、電波干渉を受けやすい。5GHz帯は、障害物の影響を受けやすい。
2.4GHzは様々な家電製品・電子機器で利用されているため、他の機器との干渉を受けやすく速度低下を起しやすいが、遠くまで電波が届きやすい。 5GHzは、この周波数帯を利用している機器が少ない為、干渉を受けにくく安定して通信できるが、あまり遠くには電波が届かず、通信が極端に不安定になる場合がある。

無線LANに接続する場合には、接続先(アクセスポイント)に付けられた名前(SSID)と、SSIDに割り振られたパスワードが必要となる。ただし無線は、電波で信号を飛ばすため、近くに行くだけで通信を傍受できる。このため、データの暗号化が必須となる。この暗号化は、そのアルゴリズムにより解読の困難さが変わる。

  • WEP 64bit / 128bit – すでに古い暗号化で専用ソフトを使うとすぐに解読される可能性が高い。使うべきではない。
  • WPA/WPA2 – 現時点の主流。
    • 暗号化方式 TKIP や 暗号化アルゴリズム AES

無線LANでは、車でセキュリティの甘いアクセスポイント(暗号化無しやWEPを使うAP)を探し、その無線LANを使ってクラッキングなどをおこなう場合も多い。(ウォードライビング)

勝手に無線LANを使われないようにするために一般的には、(1)アクセスポイントに接続できる機器をMACアドレス(機器に割り当てられた48bitの固有値)で制限したり、(2)SSIDのステルス化(APが出す電波にSSIDを入れない方式)を行う場合も多い。ただし、これらの制限をかけても専用の機器を使えば通信は傍受可能。

双方向リスト

リスト構造の利点と欠点

リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。

例えば、整数型のデータを最大 MAX 件保存したいけど、実際は それ以下の、平均 N 件扱うとする。この時のメモリの使用量 M は、以下のようになるであろう。

配列の場合 リスト構造の場合

(ただしヒープ管理用メモリ使用量は無視)

シーケンシャルアクセス・ランダムアクセス

もう1つの欠点がシーケンシャルアクセスとなる。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目 データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。

一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。

このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、1つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも1つ前にもどるだけでも処理時間を改善してみよう。

単純リストから双方向リストへ

ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、1つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、1つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。でも、これは O(N) の処理であり時間がかかる処理。
ではどうすればよいのか?

この場合、一つ前のデータの場所を覚えているポインタがあれば良い。

// 双方向リストの宣言
struct BD_List {
    struct BD_List* prev ; // 1つ前のデータへのポインタ
    int             data ;
    struct BD_List* next ; // 次のデータへのポインタ
} ;

このデータ構造は、双方向リスト(bi-directional list)と呼ばれる。

双方向リストは以前は、プログラムのエディタなどを実装する場合によく使われていた。エディタであれば、1つ前の行や次の行を参照することが多いため。しかし、最近では単純な双方向リストでエディタを実装することはない。

では、簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。

// リスト生成補助関数
struct BD_List* bd_cons( struct BD_List* p ,
                         int d ,
                         struct BD_List* n ) {
    struct BD_List* ans ;
    ans = (struct BD_List*)malloc(
                         sizeof( struct BD_List ) ) ;
    if ( ans != NULL ) {
        ans->prev = p ;
        ans->data = d ;
        ans->next = n ;
    }
    return ans ;
}
void main() {
    struct BD_List* top ;
    struct BD_List* p ;

    // 順方向のポインタでリストを生成
    top = bd_cons( NULL , 1 ,
          bd_cons( NULL , 2 ,
          bd_cons( NULL , 3 , NULL ) ) ) ;
    // 逆方向のポインタを埋める
    top->next->prev = top ;
    top->next->next->prev = top->next ;

    // リストを辿る処理
    for( p = top ; p->next != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    for(         ; p->prev != NULL ; p = p->prev )
        printf( "%d\n" , p->data ) ;
}

双方向リストの関数作成

以上の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。

先のプログラムでは、1,2,3 を要素とするリストを、ナマで記述していた。実際には、どんなデータがくるか分からないし、指定したポインタ p の後ろに、データを1件挿入する処理 bd_insert( p , 値 ) , また、p の後ろのデータを消す処理 bd_delete( p ) を書いてみよう。

// 双方向リストの指定場所 p の後ろに、値 d を要素とするデータを挿入せよ。
void bd_insert( struct BD_List* p , int d ) {
   struct BD_List*n = bd_cons( p , d , p->next ) ;
   if ( n != NULL ) {
      p->next->prev = n ;
      p->next = n ;
   }
}

// 双方向リストの指定場所 p の後ろのデータを消す処理は?
void bd_delete( struct BD_List* p ) {
   struct BD_List* d = p->next ;
   d->next->prev = p ;
   p->next = d->next ;
   free( d ) ;
}

// この手のリスト処理のプログラムでは、命令の順序が重要となる。
// コツとしては、修正したい箇所の遠くの部分を操作する処理から
// 書いていくと間違いが少ない。

番兵と双方向循環リスト

前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか?
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか?

同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか?
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか?

こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。

しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、先頭と末尾のデータを1つにまとめた方がムダがない。この場合上図のように末尾データが先頭データにつながる循環リストとなる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。

deque(両端キュー)

この双方向循環リストを使うと、(1)先頭にデータを挿入(unshift)、(2)先頭のデータを取り出す(shift)、(3)末尾にデータを追加(push)、(4)末尾のデータを取り出す(pop)、といった処理が簡単に記述できる。この4つの処理を使うと、単純リスト構造で説明した、待ち行列(queue)やスタック(stack) が実現できる。この特徴を持つデータ構造は、先頭・末尾の両端を持つ待ち行列ということで、deque (double ended queue) とも呼ばれる。

理解確認

  • 双方向リストとはどのようなデータ構造か図を示しながら説明せよ。
  • 双方向リストの利点と欠点はなにか?
  • 番兵を用いる利点を説明せよ。
  • deque の機能と、それを実現するためのデータをリストを用いて実装するには、どうするか?
  • 双方向リストが使われる処理の例としてどのようなものがあるか?

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー