ホーム » 2017 » 11月 » 13

日別アーカイブ: 2017年11月13日

2017年11月
« 10月   12月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

トランスポート層とTCP/IP

最初に簡単に転送速度の例題の解説。

毎年、意外と間違いが多いのが、異なる速度のネットワークを経由した転送時間。パケットは、バケツリレー方式で送られるので、通信路の一番遅い部分の通信速度で計算すればいい。

サブネット同士をつなぐプロトコルとして、IPプロトコルを紹介したが、データ通信ではノイズなどの影響で通信に失敗することがある。これらを補うためのTCPがある。

TCP

TCP(Transmission Control Protocol/トランスミッションコントロールプロトコル)では、分割されたパケットを元の順序に組み上げたり、パケットが途中で消えた場合の再送などの処理を行う。この機能により確実に相手に送る機能が実現されている。

3way ハンドシェーク

TCPの通信では、最初に相互に通信が可能かを確認するハンドシェークが行われる。パケットには、SYN,ACK,FINといった種別を表すフラグがついており、SYNは接続確立の要求を表す。ACKは了解を表す。FINは切断要求を表す。通信開始の時には、(1)通信OK?,(2)OKだよ、そっちもOK?,(3)OKだよ!といった3つの通信パケットで確認してから通信を行う。この最初のやり取りを3way ハンドシェークという。

(さらに…)

B木の構造とデータベース

2分探索木の考え方を拡張したもので、B木がある。

B木の構造

B木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。

B木からデータの検索

データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(N) O(logN) 資料修正注意となる。 (さらに…)