高専祭が始まりました
今日10/20(金)から、福井高専の「高専祭」が始まりました。
データリンク層
サブネット分割
前述のように、1つのバス型接続のネットワーク内部には、同時に設置できる機器の数には限界がある。このため、小さなネットワークに分割したもの(サブネット)を、ブリッジやルータで接続し、隣接するサブネットにサブネット内の通信情報が出ないように分割することを行う。
MACアドレスとデータリンク層
Ethernetに接続する機器は、機器ごとにユニークな番号(MACアドレス)を持っている。このMACアドレスは、8bit✕6個の48bitの値で、メーカー毎に割振られた範囲の値を、機器ごとに異なる値がついている。
通信は、最大でも1500byteのパケットを単位として送受信が行われる。サブネット内の通信では、自分宛のパケットかどうかをMACアドレスを見て受け取る。これらのレイヤーは、データリンク層と呼ばれる。
ブリッジ
ブリッジは、2つのサブネット間に設置される機器で、MACアドレスを見てパケットを逆側に流すべきか、流す必要がないかを判断する。
旧式のHUB(リピータHUB)は、電気的に信号を増幅するだけなので、物理層(レイヤー1)だけで通信を行う。
スイッチングHUBは、MACアドレスを見て通信相手を判断(データリンク層)するので、レイヤ2スイッチとも呼ばれる。最近では、SW-HUBのコネクタ毎に、パケットにタグを付加することで、1本のネットワーク経路に仮想的な複数のネットワークを構築するタグV-LANといった方式を使う場合もある。
OSI参照モデル
前述の、物理層(レイヤ1),データリンク層(レイヤ2)といったものを、通信するプロトコルに合わせて細かくレイヤに分けたモデルを、OSI参照モデルと呼ぶ。
- 物理層
- データリンク層(MACアドレスによるサブネット内の通信)
- ネットワーク層(IPアドレスによるサブネット間通信)
- トランスポート層(TCP,UDPによるエラー訂正,再送制御)
- セッション層(通信開始から終了までの手順,接続が切れたら再接続)
- プレゼンテーション層(データの表現方法を合わせる取り決め)
- アプリケーション層(具体的な通信サービス)
EthernetとCSMA/CD
ネットワークトポロジ
ネットワークに機器を接続する方式をネットワークトポロジと言う。
1本の線を共有するバス型、機器どうしがリング型に接続するリング型、中央の機器を通して接続されるスター型が基本となる。
基本的に、Ethernet は 1本の線を機器で共有するバス型。ただし、10BASE-T,100BASE-TX などの HUB で繋がることから、HUB を中心に広がるスター型とも言える。それぞれれのネットワークは相互につながることから、木の枝状に見えるものはツリー型と呼ばれる。また、上流ネットワークでは、機器が故障した場合に一切の通信ができなくなるのは問題があるため、複数のネットワークで相互に接続される。この場合、網が絡むような構造になることから、ネットワーク型と呼ばれる。
CSMA/CD方式
Ethernet では、1本の線を共有するバス型であり、複数の機器が同時に信号を出力すると、電圧の高低がおかしい状態となる(衝突,コリジョン)ため、同時に信号を出さない工夫が必要となる。ただし、他の人が信号線を使っていないことを確認してから、信号を出せばいいけど、確認から信号を出すまでの遅延により、衝突を避けるのは難しい。
また、1本の線を共有する機器の数が増えてくると、衝突の発生の可能性が高まってくる。
これらの問題を解決するためのルールが CSMA/CD(Carrier Sense Multiple Access with Collision Detection)方式である。
- 機器は、信号を出す場合、信号線が空いている状態を待ち、出力を行う。
- もし、複数の機器が同時に信号を出した場合、電圧異常を検知したら衝突なので再送を試みる。
- 再送を行う場合には、乱数時間待つ。(機器が多い場合は、これでも衝突が起こるかもしれない)
- 乱数時間待っても信号線が空かない場合は、乱数時間の単位時間を倍にする。
どちらにしろ、バス共有する機器の台数が増えてくると、衝突の可能性は高まり、100台を越えるような状態は通信効率も悪くなる。
スイッチングHUB
＊BASE-T のような、HUB による接続では、複数の機器が異なる機器どうしで通信をする場合、その通信路を時分割多重するのではなく、通信相手に応じて内部回路を直接つながるように接続するスイッチングHUB(以下SW-HUB)が普及している。
バス型通信では、1本の線を共有するため、同じネットワーク内の別機器間の通信は、傍受することができる(タッピング)。しかし、SW-HUB の場合、機器同士が直接つながるので、傍受するのが困難であり、セキュリティ的にも望ましい。
無線LANと暗号化
本当は、データリンク層の話をする予定だったけど、リピータHUBでの通信傍受の可能性の話をしていたら、これに合わせて無線LANの話もする必要がある。ということで、内容追加
無線LAN(通称 WiFi)は、IEEE 802.11 にて規格が定められている。無線LANは、使う通信周波数で、2.4GHz帯を使うものと、最近増えてきた5GHz帯のものに分けられる。
- IEEE802.11b 2.4GHz帯を使う、最大11Mbps
- IEEE802.11g 2.4GHz帯を使う、最大54Mbps
- IEEE802.11n 2.4GHz/5GHzを使う、最大600Mbps
- IEEE802.11ac 5GHz帯を使う、最大1GBps以上
ただし無線は、電波で信号を飛ばすため、近くに行くだけで通信を傍受できる。このため、データの暗号化が必須となる。この暗号化は、そのアルゴリズムにより解読の困難さが変わる。
- WEP 64bit / 128bit – すでに古い暗号化で専用ソフトを使うとすぐに解読される可能性が高い。
- WPA/WPA2 – 現時点の主流。2017/10/18時点でKRACK脆弱性が指摘された。
無線LANでは、車でセキュリティの甘いアクセスポイントを探し、その無線LANを使ってクラッキングなどをおこなう場合も多い。(ウォードライビング)
2分探索木への追加
2分木へのデータの追記
前回の授業で、2分探索木のデータに対する処理を説明したので、今回は木にデータを追加する処理。
struct Tree {
int data ;
struct Tree* left ;
struct Tree* right ;
} ;
struct Tree* tcons( int x, struct Tree*L, struct Tree*R )
{
struct Tree* ans ;
ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->left = L ;
ans->right = R ;
}
return ans ;
}
struct Tree* top = NULL ;
void insert( int x )
{
struct Tree** tail = &top ; // 書換えるべき末端ポインタへのポインタ
while( (*tail) != NULL ) {
if ( (*tail)->data == x )
break ; // 同じデータは重複するので、追加処理は行わない
else if ( (*tail)->data > x )
tail = &( (*tail)->left ) ; // 左の枝を降りていく
else
tail = &( (*tail)->right ) ; // 右の枝を降りていく
}
if ( (*tail) == NULL )
(*tail) = tcons( x , NULL , NULL ) ;
}
単純リストの時は、2重ポインタの混ざった式の部分的に、型を意識する説明をした。今回は、”tail = &( (*tail)->left )“の赤のカッコが省略されたら、青のカッコが省略されたら、どちらが文法エラーかを「演算子の優先順位」の話を交えながら説明する。
不均衡な木の成長
この insert() を使って、
- insert(50); insert(20); insert(70); insert(30); insert(60);を実行した場合と、
- insert(20); insert(30); insert(50); insert(60); insert(70);を実行した場合を考える。
後者は、下図の右の用に一方的に伸びる木構造ができて、高速な検索の恩恵がない。
50 20
／ ＼ ＼
20 70 30
／ ＼ ／ ＼ ＼ O(N)
30 60 50
＼
O(log N) 60
＼
70
これらの問題を解決するため、枝の途中でデータの配置を動かして、左右均衡のとれた構造に書換える方法として、AVL木がある。
サーバのメンテナンス
Azureサーバのバックアップ
管理しているAzureサーバだけど、クラウドだし簡単には落ちないとバックアップ処理を真面目にしてなかったけど、そろそろ対策をと設定を行った。
- 各仮想サーバの定時処理で、主要データディレクトリを .tar.gzでバックアップ
- 自室のサーバで、RAID-NAS上に仮想サーバのバックアップを rsync
- 仮想サーバの容量逼迫を防ぐために、2月以上は削除。自室サーバは空き容量をみて削除時期を考えよう。
差分バックアップを加える(2017/10/19追記)
バックアップ処理、2週間おきに設定していたけど、いざという時のためにもう少し頻繁にバックアップを取りたい。
そこで、1週間毎に差分バックアップを取るように、処理を追加する。
MovableTypeの記事を復活
サーバ故障による移行作業で、CMS を MovableType から WordPress に変更したけど、古い記事の移行ができていなかった。自宅サーバも同様の移行作業を行い、過去記事の吸出しがうまくいったので、同様に電子情報の過去記事を吸い出し、WordPress にインポート。
# メモ
((追記))
古い記事を抽出する際に、preタグ内の空白が削除されてらぁ。おかげで、プログラムのコードのインデントが消えてしまってる。(x_x;;
サーバの更新作業
職場で管理しているサーバの更新作業。
snapd の更新トラブル
以前より、snapd の更新に失敗しているサーバだけど、post-install , prerm スクリプトのエラーが出るので、スクリプトに”exit 0″などを書き加えながら、無理やり更新。
AzureサーバのUbuntu wilyがサポート外
別サーバでは、Ubuntu wily が対象サポート外になって、更新が止まっていたので、Ubuntu 16系 の xenial に更新。
aptitude safe-upgrade を実行したら、定番の競合,保留パッケージ数がガンガン増えていく。自宅サーバなら、競合パッケージの探索処理の途中で止まっちゃうけど、今回はなんとかクリア。数百程度のパッケージ更新で無事に xenial に更新完了だった。
物理層WAN接続
前回の物理層のLANの話に引き続き、WANの話を説明。
バス接続(LAN)と転送速度
基本的な Ethernet の接続では、1本の通信路を共有するバス型接続のため、1本の信号線をパケット単位の通信の短い時間に区切って、送信を交代しながら行う時分割多重方式で行い通信を行う。
このため、下図で通信路が10BASE/T であった場合、PC-A から PC-B にCD1枚のデータ700MBを送る場合、
>-----+-----------+------< CD1枚 700MB
| | をPC-A⇒PC-Bに転送
PC-A PC-B 何秒かかる？
700M[Byte] * 8 = 5.6 G[bit] を 10M[bps] で送ると
5.6G[bit] / 10M[bit/sec] = 560[sec]
また、PC-A から、PC-B , PC-C に同時にCDデータをダウンロードする場合、時分割多重となるため、時間は倍かかる。
>-----+------+------+-----<
| | |
PC-A PC-B PC-C
電話線接続
同じ敷地内のネットワーク接続のLANどうしを、ネットワークで相互接続するWAN(Wide Area Network)では、昔は電話線を用いていた。電話は、本来音声を伝えるためのものであるため、0/1のデジタル信号を、音の信号に変換(変調)し、受信側は音をデジタル信号に(復調)する。これらを行う機器は、変復調装置(モデム)と呼ばれる。
変調の際には、0/1信号を、音の強弱(振幅変調/AM),音程の高低(周波数変調/FM),位相の前後(位相変調/PM)の組み合わせによって、送受信を行う。
当初は、300bps程度であったが、最終的には64Kbps 程度の通信速度が得られた。
これらの通信速度の改善のため、電話線にデジタル信号で送る ISDN , 電話線の音の信号の高帯域を使った通信 ADSLなどが用いられた。
最近では、光ファイバによる FTTH(Fiber To The Home) により 1Gbps を越える通信が可能となっている。
通信速度の理解と、古い時代の通信速度を体験してもらうため、試しに「2000ドット✕1500ドットのRGB画像(1ドット3byte)のデータを、9600bps で通信したら、どの程度の時間を要するか…」を計算してもらった。
データ量 2000✕1500✕3✕8 [bit] = 72 M[bit] 通信速度 9600[bps] であれば、72 M / 9600 = 7500[sec] = 約2時間
2分探索木
2分木(2分探索木)
struct Tree {
int data ;
struct Tree* left ;
struct Tree* right ;
} ;
struct Tree* tcons( int x, struct Tree*L, struct Tree*R )
{
struct Tree* ans ;
ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->left = L ;
ans->right = R ;
}
return ans ;
}
void main() {
struct Tree* top
= tcons( 52 ,
tcons( 24 ,
tcons( 10 , NULL , NULL ) ,
tcons( 35 , NULL , NULL ) ) ,
tcons( 73 ,
tcons( 60 , NULL , NULL ) ,
tcons( 95 , NULL , NULL ) ) ) ;
}
出来上がった木構造のイメージ
top ＼ 52 ／ ＼ ／ ＼ 24 73 ／ ＼ ／ ＼ 10 35 60 95
データに対する処理
int find( struct Tree* p , int key ) { // データを探す
while( p != NULL ) {
if ( p->data == key )
return 1 ; // 見つかった
else if ( p->data > key )
p = p->left ; // 左の枝
else
p = p->right ; // 右の枝
}
return 0 ; // 見つからなかった
}
void print( struct Tree* p ) { // 全データの出力
if ( p != NULL ) {
print( p->left ) ;
printf( "%d¥n" , p->data ) ;
print( p->right ) ;
}
}
int count( struct Tree* p ) { // 全データの件数をカウント
if ( p == NULL )
return 0 ;
else
return 1 + count( p->left )
+ count( p->right ) ;
}
int depth( struct Tree* p ) { // データの深さをカウント
if ( p == NULL ) {
return 0 ;
} else {
int dl = depth( p->left ) ;
int dr = depth( p->right ) ;
if ( dl > dr )
return 1 + dl ;
else
return 1 + dr ;
}
}
データベースとガイダンス
今日が後期の選択科目「データベース」の第一回目ということで、シラバス説明＆ガイダンスをしてからぁ〜のぉ〜、概要説明。
インターネットの情報量
インターネット上の情報量の話として、2010年度に281EB(エクサバイト)参考:kMGTPEZYの情報があるらしい。また 2013年度で、1.2 ZB(ゼタバイト)という情報があった。これらをムーアの法則(2年で2倍)の概算に照らし合わせても、それなりに近い。2017年であれば、約4年で、5 ZBにはなっているかな。
そして、これらの情報をGoogleなどで探す場合、すぐにそれなりに情報をみつけてくれる。これらは、どの様に実装されているのか？
Webシステムとデータベース
まず、指定したキーワードの情報を見つけてくれるものとして、検索システムがあるが、このデータベースはどのようにできているのか？
Web創成期の頃であれば、Yahooがディレクトリ型の検索システムを構築した。(ページ作者がキーワードとURLを登録する方式) しかし、ディレクトリ型では、自分が考えたキーワードではページが見つからないことが多い。
そこで、GoogleはWebロボット(クローラー)による検索システムを構築した。Webロボットは、定期的に登録されているURLをアクセスし、そのページ内の単語を分割しURLと共にデータベースに追加する。さらに、ページ内にURLが含まれていると、そのURLの先で、同様の処理を再帰的に繰り返す。
これにより、巨大なデータベースが構築されているが、これを少ない コンピュータで実現すると、処理速度が足りず、3秒ルール/5秒ルール (Web利用者は次のページ表示が3秒を越えると、次に閲覧してくれない)を満たす処理をするには負荷分散が重要となる。
一般的に、Webシステムを構築する場合には、 1段:Webサーバ、2段:動的ページ言語、3段:データベースとなる場合も 多い。この場合、OS=Linux,Web=Apache,DB=MySQL,言語=PHPの組合せで、 LAMP構成とする場合も多い。(Webシステムの3段スキーマ構成)
一方で、大量のデータを処理するDBでは、フロントエンドDB,スレーブDB,マスタDBの3段スキーマ構成となることも多い。(データベースの3段スキーマ構成)
データベースシステム
データベースには、ファイル内のデータを扱うためのライブラリの、BerkleyDBといった場合もあるが、複雑なデータの問い合わせを実現する場合には、リレーショナル・データベース(RDB)を用いる。RDBは、1970年にコッド博士によりよって発案され、複雑なデータはすべて表形式とその組み合わせで表現し、SQLというデータベース 問い合わせ言語でデータを扱う。また、SQLでの問い合わせはネットワーク越しに実行可能で、マスタ・スレーブ型の運用ができるようになっている。こういった RDBで有名なものとして、Oracle , MySQL , PostgreSQL などが有名である。 単一コンピュータ内でのデータベースには、SQLite などがある。
しかし、RDBでは複雑なデータの問い合わせはできるが、大量のデータ処理のシステムでは、フロントエンドDB,スレーブDB,マスタDB の同期が問題となる。この複雑さへの対応として、最近は NoSQL が注目されている。
データベースが無かったら
これらのデータベースが無かったら、どのようなプログラムを作る 必要があるのか？
情報構造論ではC言語でデータベースっぽいことをしていたが、 大量のデータを永続的に扱うのであれば、ファイルへのデータの読み書き 修正ができるプログラムが必要となる。
こういったデータをファイルで扱う場合には、1件のデータ長が途中で 変化すると、N番目のデータは何処？といった現象が発生し、先頭からシーケンシャルアクセスをすることになる。 このため、目的のデータの場所を一発で見つけることができる簡単なデータベースを自力で書くには、1件あたりのデータ量を 固定し、lseek() , fseek() , fwrite() , fread() などの関数でランダムアクセスのプログラムを書く必要がある。
また、データの読み書きが複数同時発生する場合には、排他処理も重要となる。例えば、銀行での預け金10万の時、3万入金と、2万引落としが 同時に発生したらどうなるか？ 最悪なケースでは、 (1)入金処理で、残金10万を読み出し、 (2)引落し処理で、残金10万を読み出し、 (3)入金処理で10万に+3万で、13万円を書き込み、 (4)引落し処理で、残金10万-2万で、8万円を書き込み。 で、本来なら11万になるべき結果が、8万になるかもしれない。(参照 C言語のflock() 関数)
さらに、コンピュータといってもハードディスクの故障などは発生する。 障害が発生してもデータの一貫性を保つためには、バックアップや 障害対応が重要となる。
ランダムアクセスの処理、排他処理、バックアップ、障害対策…といったものを総合して扱えるようになったものがデータベースシステムである。