マツシタのお勉強

welcome to my engineering blog
Cracking the Coding Interview
AtCoder
Network
LeetCode
iOS
Hacker Rank

【グラフ理論とネットワーク理論】Graph #1

ネットワーク グラフ理論 ネットワーク理論

グラフとは何か

グラフは以下のコンポーネントで成り立つ。

  • 節点、頂点: 対象物(スイッチ、ルータ)
    Node, Vertex: Objectives(Switch, Router)

  • 枝、辺: 接点間の関係(伝送路)
    Branch, Edge: Relation among nodes(Transmission lines)

つまり、グラフとは節点と枝によって構成される。

グラフには既に名前が付けられているものがある。

・空グラフ Empty graph: ノードだけでエッジを持たない。
・完全グラフ Complete graph: 全てのノード間にエッジを持っている。
・補グラフ Complement graph: 元のグラフを補完するグラフ。元のグラフと補グラフを足すと完全グラフとなる。

グラフの性質

・同形 Isomorphic: あるグラフと同じグラフ。接点数、枝数、関係性も同じなグラフ。
・平面グラフ Plane graph: どの辺同士も交差しないグラフ。
・非平面グラフ Non-plane graph: どんな同形も枝同士の交差を生んでしまうグラフ。
・有向グラフ Directed graph: 辺に向きがあるグラフ。
・無向グラフ Undirected graph: 辺に向きが無いグラフ。

経路と連結性 Path and Connectivity

経路、連結は以下のように定義されている。

  • 経路、道: 始点Vsから終点Vtに至る枝の系列
    Route, Path: Series of branches from source Vs to sink Vt
  • 連結: VsからVtに経路がある
    Connected: There is a route from Vs to Vt
  • 強度に連結 Strongly connected: Vs→Vt、Vt→Vs

グラフ理論における経路、連結性に関する性質

・連結グラフ: すべての節点が他のどの節点とも連結しているグラフ
　Connected graph: Every node is connected to any other node.
・オイラー線: グラフの全ての枝を通る一筆書きの閉路
　Euler line: Loop drawn with a single stroke of the brush.
・オイラーグラフ: オイラー線が存在するグラフ
　Euler graph: Graph which has an Euler line.
・局所次数: 節点に付いている枝の数
　Local degree: The number of branches of a node

グラフ理論における定理(教養として)

グラフがオイラーグラフであるための必要十分条件は、すべての節点の局所次数が偶数であることである。

木とカットセット Tree and Cutset

木とは以下のようの定義されている。

  • 木: 閉路を持たない連結グラフ
    Tree: Connected graph without loops

木の性質

・木は枝数が最も少ない:
　今の状態から枝を足そうとすると閉路ができてしまい、木ではなくなる。
・覆う:
　元のグラフをGとし、Gからできる木をTとした時に、TはGを覆うと言う。
　通信網を作る時に始めはTの状態からスタートさせ、トラフィックが増えるにつれてGの状態にしていく。

カットセットとは

あるグラフGを２つに分けて見た時(それぞれをサブグラフV1、V2とすると)、V1とV2を繋ぐ辺のセットをカットセットと呼ぶ。例としては、島が２つあり、それぞれの島にはグラフ(ネットワークなど)が形成されてる状態を考える。この時、２つの島を繋ぐ辺の事をカットセットと呼ぶ。生命線のようなもの。

木とカットセットに関する定理

Gを覆うTは、Gのあらゆるカットセットと少なくとも１本の共通な枝を持っている。

AtCoder ARC 004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

AtCoder

B - 2点間距離の最大と最小 ( Maximum and Minimum )

B: 2点間距離の最大と最小 ( Maximum and Minimum ) - AtCoder Regular Contest 004 | AtCoder

N + 1個(0 ~ N)点がx,y平面上にある時、i番目の点とi+1番目の点との距離が与えられる(0 <= i < N)。 この時、０番目の点とN番目の点の距離で取り得る最大の距離と最小の距離を出力する問題。

解法

最大距離

最大距離は与えられた各点の距離を全て足し合わせることで取得することができる。この時、与えられた点は全て一直線上に存在することになる。

最小距離

与えられた点の内０番目とN番目を除いた点で上手く直線を折ることで、０番目とN番目の距離を短くすることができる。 なので、どのように直線を折るかを考える。

与えられた点と点の距離の中で最も長い距離を見つけ、その線分の両サイドの点で直線を折り返す。これによって０番目とN番目の距離を最小にすることができる。

ソースコード

AtCoder ARC 004 A - 2点間距離の最大値 ( The longest distance )

AtCoder 三平方の定理

A - 2点間距離の最大値 ( The longest distance )

A: 2点間距離の最大値 ( The longest distance ) - AtCoder Regular Contest 004 | AtCoder

N個のx,y座標が与えられ、任意の２つの点の距離が最大となる値を出力する問題

解法

与えられる点の数がN(2 <= N <= 100)なので、任意の２点を全列挙すると計算量はO(104)となり、問題なく間に合う。 任意の２点を決めたら、三平方の定理により２点間の距離を算出し、最大となる値を出力する。

ソースコード

HimotokiとAPIKitでAPIクライアント

iOS Himotoki APIKit API Swift

APIKitとは

GitHub - ishkawa/APIKit: Type-safe networking abstraction layer that associates request type with response type.

Himotokiとは

GitHub - ikesyo/Himotoki: A type-safe JSON decoding library purely written in Swift

単一のモデルをデコード

Requestプロトコル継承したGithubRequestを作成・Extension。

リクエストを生成するためのStructを定義

リクエスト実行

ポイント

通常のAPIKitの使い方では、リクエストを生成するための構造体にresponseメソットを定義する。 しかし、Himotokiを使うことで、responseメソッドの処理もGithubRequestプロトコルをExtensionする形で実装させることができる。 こりによりよりコードがシンプルになる。

コードだけみるとRateLimit構造体のdecodeが呼ばれていないように見えるが、

これのメソッドを呼ぶと内部的にT.decodeを読んでいる。

Himotokiのカスタムオペレータ

Himotokiのdecodeメソッドを見ると<|という謎のメソッドが使われている。これはカスタムオペレータといういうもので、+や-といったようなオペレータを独自で定義する方法である。Himotokiのソースコードを見ると以下のように定義されている。

<|の左側に記述したものが上のメソッドの第一引数で右側に記述したものが第２引数となる。

複数のモデルをデコード

以下の例は、Github上のリポジトリーを検索し複数のリポジトリーの情報をレスポンスとして返すようなものである。

先程の例と同様に、typealiasに指定したモデル(今回でいうとRepositoryCollection)のdecodeが内部的に呼ばれる。 さらに、RepositoryCollectionをdecodeする過程で子モデルであるRepositoryモデルのdecodeも呼ばれるので、結果的にモデル配列をdecodeすることができる。

サンプルプロジェクト

github.com

ネットワークの仮想化

ネットワーク VLAN VPN 仮想化 クラウド

ポートベースVLANとタグベースVLAN

VLANとは、物理的にには１つのネットワークを理論的に複数のネットワークに分ける技術。

営業部が入居するオフィスに、経理部も同居することになった時、LAN配線は既存のもの使いながら、営業部と経理部とであたかも別の２つのLANがあるかのように使う事ができる。

これを実現する技術として、ポートベースVLANとタグベースVLANがある。

ポートベースVLAN

スイッチやルーターに搭載されている複数のポートのうち、いくつかをグループとして指定し、そのグループに属するポート郡を独立した１つのLANのように見せる技術。

タグベースVLAN

１つのLANケーブルの中に複数のLANの情報を流す技術。 ポートベースVLANによって複数のLANを同じネットワーク内に作ることができるが、物理的にはLANケーブルは１つである。そこで、LANケーブルに流す情報にどのLANかを示すタグを付けることで、複数のLANを識別することがでる。


VPNとトンネル

VPN(Virtual Private Network)とは、インターネットなどの既存のネットワークの中に、新たに仮想的なネットワークを作る技術。

トンネル技術と認証

トンネルとは、ある通信回線の中に作り出した、仮想的な通信回線の事。

VPNにはインターネットのような安全性が保証されないネットワーク何に作るので、暗号化をする必要がある。この時IPsecなどのプロトコルを使用する。


仮想化

仮想化とは、物理的なネットワークやコンピュータを使って、論理的にネットワークやコンピュータを作り出す技術

仮想化によって物理的に１つのネットワークを論理的に複数のネットワークを作り出したり、その逆を行うことができる。例としてはVLANやVPNも当てはまる。

VALN: 物理的には１つのLANの中に、仮想的に複数のLANを作り出すこと。 VPN: 物理的には１つのLANケーブルの中に、仮想的に複数のLANケーブルを作り出すこと。

仮想化のメリット

  • 物理的な装置の数や場所に制約されず機能を利用出来ること
  • 装置の処理能力を有効活用できること(持っている能力を持て余していることが多い)
  • 必要に応じてスケールアップ/ダウン出来ること


クラウド

クラウドとは、ユーザ自身が、Web画面などを返して、コンピューター、ネットワーク、各種サービスを自由に組合せて必要なシステムやサービスを組み立て、それをネットワーク経由で利用できること。

TCP/IPで通信するための仕組み

ネットワーク TCP/IP 可変長サブネットマスク CIDR MACアドレス ARP ルーティング デフォルトゲートウェイ スタティックルーティング ダイナミックルーティング DHCPサーバー NAT NAPT

可変長サブネットマスクとCIDR

可変長サブネットマスク

サブネット毎に、サビネットマスクの長さを変えることができる技術。サブネットマスクの長さを自由に変えられるようになると、サブネット毎に接続するコンピュータ数を柔軟に決める事ができる。

CIDR

複数のネットワークへの転送を１つの転送ルールで済ませる技術。

ルーターB (192.168.0.0/22宛は全部、ルーターAに渡すよ)
↓
ルーターA
↓            
192.168.**0**.0/24,    192.168.**1**.0/24,    192.168.**2**.0/24

/24はサブネットマスクのビット数を表しており、CIDR記法と呼ぶ。


MACアドレスを使った情報転送

MACアドレスとは、イーサネットなどのネットワークハードウェアに１つずつ割り当てられているアドレス。物理アドレスとも呼ばれる。

昔と現在とでMACアドレスの使い方は異なる。

古いイーサネットでのMACアドレスの使い方

全てのコンピュータに同じデータを送り、MACアドレスが自分宛ての場合のみ受信、そうでなければスルーする。

現在のイーサネットでのMACアドレスの使い方

どのポートにどのMACアドレスの機器がつながれているかをMACアドレステーブルに保存しておき、その機器だけに送る。


ARPが必要なわけ

ARPとは、ネットワーク内に同じIPアドレスのコンピュータが存在するかを確認するためのプロトコル。

パケットを相手に送る時、その相手が同じネットワーク内に存在したらその相手のMACアドレスが知りたいです。相手が同じネットワーク内にいる場合は、IPアドレスからMACアドレスを導きだし、別のネットワーク内に相手がいる場合は、パケットを次のルータに引き渡す必要がある。これらの操作をするためのプロトコルがARPである。

ARPの動作

ARPにはブロードキャストが使われる。これはARPリクエストとARPリプライから成る。

ARPリクエスト

ネットワークに対して、送り先のIPと同じIPを持つコンピュータがあるかをネットワーク内に対して聞く事。

ARPリプライ

ARPリクエストに対して、送り先と同じIPを持つコンピュータから、自分自身のMACアドレスの情報を含めて、送信元に送りかえる事。

これにより、送信元は送信先のMACアドレスを特定することができる。


ルーティングとデフォルトゲートウェイ

ルーティングとは、ルーターによるパケットの転送の事。ルーティングは何をどこへ転送すればいいかを定めた転送ルールに従って行われている。そのための重要な要素がルーティングテーブルである。

ルーティングテーブルとは、宛先のネットワークとそのネットワークに対する配送方法が登録されている。

デフォルトゲートウェイ

送り先が分からない時にとりあえず送っておく先。


スタティックルーティングとダイナミックルーティング

ルーティングテーブルは、ネットワークの構成が変わった時にその情報を更新する必要がある。 この時、ルーティングテーブルを更新するスタイルが２つある。

スタティックルーティング

ネットワーク接続が更新するたびに、関連するルーターなどのルーティングテーブルを手動で修正する方法。小さな規模のネットワークでは手軽にできるので有効。

ダイナミックルーティング

ネットワークの構成が変わる度に、自動でルーティングテーブルを更新する。大規模ネットワークに有効。


DHCPサーバー

新たにネットワークにコンピュータを接続する場合、IPアドレスやサブネットマスク、DNSサーバーのIPアドレスなどを逐一設定する必要がある。DHCPサーバーを用いることでこれらの設定を自動で行う事ができる。

DHCPサーバーの動作の流れ

**① DHCPディスカバー**
新たに接続したいコンピュータ(クライアント)からDHCPサーバーに対して、IPアドレスを付けて下さいと呼びかける事
↓
**② DHCPオファー**
DHCPサーバーからクライアントに対して、IPアドレスの候補が送られる
↓
**③ DHCPリクエスト**
クライアントからDHCPサーバーに対して、候補を使用することを伝える
↓
**④ DHCPアック**
DHCPサーバーからクライアントへ、設定情報の使用を開始を承諾したことを知らせる。


NATとNAPT

企業や家庭内で通信する際はプライベートIPアドレスを使用するが、インターネットと通信する時には、グローバルIPアドレスが必要になる。この時、アドレス交換という方法用いてグローバルIPアドレスを使えるようにしている。アドレス交換の方法はNATとNAPTの２つ存在する。 グローバルIPアドレスは、ネットワーとネットワークを繋ぐルータが持っている。

NAT

NATとは、ルータに複数のグローバルIPアドレスを保持しておき、LAN内のコンピュータがインターネットに接続しようとした時に、複数あるグローバルIPアドレス内のどれかを使用して通信を行う方法。 NATの場合、同時にインターネットに接続できるコンピュータの数はルーターが持っているグローバルIPアドレス数に依存する。

NAPT

NAPTとは、IPアドレスを変換する際にポート番号も変換することで、１つグローバルIPを複数のコンピュータで共有できる仕組み。