TP-Link Archer T3U AC1300をLinuxから使う

09 Nov 2019

USB接続の無線LAN子機 TP-Link Archer T3U AC1300 を、Thinkpad X1 Carbon 2015（Fedora release 29 (Twenty Nine)、linux 5.3.6-100.fc29.x86_64）から使えるようにしたので手順を残しておく。

# 公式HPではドライバが配布されていなかったので rtl88x2bu を使った
git clone https://github.com/cilynx/rtl88x2bu
cd rtl88x2bu/
git rev-parse HEAD # 962cd6b1660d3dae996f0bde545f641372c28e12
VER=$(sed -n 's/\PACKAGE_VERSION="\(.*\)"/\1/p' dkms.conf)
sudo rsync -rvhP ./ /usr/src/rtl88x2bu-${VER}
# /usr/src/<module_name>_<module_version> に移動させて dkms で管理する
sudo dkms add -m rtl88x2bu -v ${VER}
sudo dkms build -m rtl88x2bu -v ${VER}
sudo dkms install -m rtl88x2bu -v ${VER}
sudo dkms status
sudo modprobe 88x2bu

2種類の子機（オンボードの子機とTP-Linkの子機）を同一のネットワークにつなぐと、metric によって優先順位が決まる。 metric の値を見ると、オンボードの子機側を優先していた（値が小さい）ので入れ替えた。

ip route
sudo nmcli con mod <connection name> ipv4.route-metric 599
sudo systemctl restart NetworkManager

追記: Fedora 30、31にアップデートしたあとも特に問題なかった。

sudo dkms status
# rtl88x2bu, 5.6.1, 5.3.6-100.fc29.x86_64, x86_64: installed
# rtl88x2bu, 5.6.1, 5.3.8-200.fc30.x86_64, x86_64: installed
# rtl88x2bu, 5.6.1, 5.3.8-300.fc31.x86_64, x86_64: installed

2019 越後湯沢秋桜ハーフマラソン

29 Sep 2019

#marathon

越後湯沢で開催された秋桜ハーフマラソンに参加してきた。大会自体はすごいよかったけど、コースの半分あたりから胃の調子が悪くなり、 13kmでリタイヤという悔しい結果となった。色々反省点があったので、記録として残しておく。

まず、そもそも食事のタイミングが悪かった。9時30分スタートで、8時あたりでおにぎりを食べた。 3時間前までに取るようにしたい。直前に口にいれるのであれば、ゼリー状のものにしたい。

6.7kmから15kmまで続く下り坂で飛ばしすぎた事も影響していると思う。お腹が激しく上下して気持ち悪くなってしまった。スタートから6.7kmまでの上り坂は走り方に気をつけていたが、それ以降については、なんとかなるだろうと考えていなかった。加えて、腰にポーチを巻いていたので、お腹を圧迫していたのかもしれない。塩飴を少量持っていただけなので、ポケットにいれておけば事足りていた。

前半の上下の坂でも貯金を作っておこうと、いつも以上に早めのペースで走っていたので、バテてしまったんだろうな。

ただ、自分でリタイヤを決断できたのは唯一よかったことだった。以前膝を故障してしまったときは、脚を引きずりながらも、無理して走っていて、沿道で応援してくれた方からリタイヤを勧められた。

どうも消化不良な感じなので、どこかでリベンジしたい。

TCP技術入門読書メモ

25 Sep 2019

#network

TCP技術入門を読んだので、気になったところを雑多な感じだがメモしておく。まず前半部分。ネットワークまわりの話は聞いたことはあるが、使わずに忘れてしまっていることが多い。

1章 TCP入門

伝送効率
- Ethernetフレーム 1500 バイト、TCPヘッダが 60 バイト、IPヘッダが20バイトとする
- アプリケーションが使えるのは 1420 バイト
- Ethernetヘッダ 14 バイト、FCS（Frame Check Sequence）4バイトを考慮すると、伝送効率は$1420/(1500+18) \times 100=93.5 \%$
UDP
- 実際にUDPがやっていることは、転送先へデータを送ることと、チェックサムの確認だけ
- TCPはユニキャストだが、UDPはユニキャストに加えて、マルチキャストとブロードキャストにも対応
- シーケンス番号とタイムスタンプを追加したRTP（Real-time Transport Protocol）や、それに加えて再送機能も追加したRUDP（Reliable user Datagram Protocol）もある
- QUIC はUDPベースで、それを使ったHTTP/3（HTTP-over-QUIC）。コネクション確立とTLS確立を同時に実施。
TCP
- ACKのシーケンス番号は、次に受信したい番号。当該セグメントが届くまで、同じシーケンス番号を返送し続ける。
- フロー制御：受信側のバッファ溢れを防ぐために、送信データ量を調整すること。TCPでは一度に送信可能なサイズをウィンドウと呼ぶ。特に、送信側がもつパラメータを swnd （send window）と表記する。対して、受信側はrwnd（recieve wndoe）。
TCP輻輳制御
- Loss-based：データの消失から輻輳を判断
- Delay-based：RTTから輻輳を判断
特定の用途向けプロトコル
- RUDP（Reliable User Datagram Protocol）：UDPベースで、シーケンス番号、ACK、再送、フロー制御を加えたもの
- DCCP（Datagram Congestion Control Protocol）：UDPにおける輻輳緩和が目的

2章 TCP/IPの変遷

ARPNETなどではネットワークが信頼性を担保していたが、TCP/IPは各ノードがその役割を担う
Nagleアルゴリズム：TCP/IPの送出パケット数削減の方法。輻輳制御アルゴリズムのはしり
Windows95（OSR2以降）にTCP/IPが搭載されたことが普及のきっかけになった
IEEE 802.11ではMACレイヤーでCSMA/CAを採用

3章 TCPとデータ転送

MTUは、イーサネットは1500バイト、PPPoEでは1492バイト、ATMは9180バイト。ただ最近は任意に設定できる
MSS（Maximum Segment Size）：TCPが区切る最大パケット長さ
MTU（1500バイト）= IPヘッダ（20バイト）+ TCPヘッダ（20~60バイト）+ アプリケーションデータ（MSS以下）
- MSSは、TCPのペイロードのみ
- MTUは、TCPのペイロードからTCPヘッダやIPヘッダまで。Ethernetヘッダは含まない
ACK（Acknoledgement Number）：確認応答番号。次に送ってほしいシーケンス番号
コントロールフラグ
- RST（Reset the connection）：コネクションを強制切断。使われていないポート番号に送るなど、異常があれば有効になる
- CWR（Congestion Window Reduced）：輻輳ウィンドウの減少を通知する。ECNとセットで使われる
- ECE（ECN echo）：輻輳が発生したら通知
ウィンドウ制御：一度に送信可能なウィンドウサイズ $swnd$ を調整 $swnd = min(rwnd, cwnd)$
- フロー制御：受信側から送信側に送信量を通知して、調整する。受信側は、送信側へ受信可能なバッファ量$rnwd$を通知
- 輻輳制御：輻輳ウィンドウ $cwnd$ を調整
スロースタート
- 通信開始時点で、ACKを受け取るたびに $cwnd$ を1セグメントずつ増やしていく $cwnd = cwnd + mss$
- 指数的に $cwnd$ が拡大
輻輳回避
- スロースタートを行うと、再び再送が起きやすい
- 再送が起きた時の $cwnd$ の半分 $cwnd/2$を閾値として、それを越えた時は更新を緩やかにする $cwnd = cwnd + mss/cwnd$
- RTTごとに線形に増える
高速リカバリー
- 輻輳のたびに、スロースタート→輻輳回避という挙動をするのは効率が悪い
- 重複ACKを契機とする
- Recoで採用
セグメントの消失
- 再送タイマーがタイムアウトした場合
- 重複ACKが一定数届いた場合

ABC139-141

20 Sep 2019

#atcoder

ABC #139 D - ModSum

$p_1=N, p_2=1, p_3=2, … , p_N=N-1$ とすると、$m_1=0, m_2=1, m_3=2, … , m_N=N-1$ となる。なので、答えは$1, 2, 3, …, N-1$の総和。

$i$と$j$の試合を頂点$(i,j)$と表す。ただし、$i$と$j$をひっくり返したものは同一視する。各頂点は、直前にすべき試合数$prev_{(i,j)}$と、その次に実行可能な試合の一覧$next_{(i,j)}$をもつ。そして、$prev_{(i,j)} = 0$である試合を見つけるたびに、貪欲にその試合をしていくよう、シミュレーションする。ここで、ある試合をするたびに、その次の頂点の$prev_{(p,q)}$をデクリメントすることに注意する。

ABC #139 F - Engines

あらかじめ各ベクトルを偏角ソートしておき、 720度分になるようにそのベクトルをつなげておく（後々、楽になる）。そうすると、この問題の答えは、連続したベクトルの和であることが分かる。すべてのベクトルについて、以下の操作を行う。

あるベクトルを始まりとして、連続したベクトルを足していき、長さが最長となるものを見つける。

ABC #140 D - Fce Produces Unhappiness

まず、幸福でない人に注目して、それをどれだけ減らせるかに注目する。たとえば、$RLLLLRRRRRLLRRLLRRR$から幸福でない人を抜きだすと、$RL…….RL..RL…R$となる。連続する人は同時に操作できるので、$RLRLRLR$と考えてよい。そして、$RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> （空）のように操作を繰り返せば良い。

ABC #140 E - Second Sum

Nから1まで、順番に見ていく。ある要素$i$について見た時、左右には$i+1, i+2, … , N$の要素が置かれていることになる。右側に最大値がある場合と、左側に最大値がある場合、それぞれについて、組み合わせを計算して、合算すればよい。最大値の位置については、setのlower_boundで見つけた。

ABC #140 F - Many Slimes

貪欲な感じで、できるだけ体力が大きなスライムから作っていけばよい。うーん、今回はE・F問題よりもD問題が難しく感じた。。

ABC #141 D - Powerful Discount Tickets

すべてのアイテムを優先度付きキューqに入れておく。割引券の枚数だけ順番に取り出して、以下の操作を行う。

qから最も値段の高いアイテムを取り出す。
そのアイテムの値段を半分（切り捨て）にして、再度qに入れる。

ABC #141 E - Who Says a Pun?

長さlenについて、二分探索する。ある長さについて、ローリングハッシュですべての部分文字列のハッシュ値を入れておき、mapなどで入れておく。ハッシュ値が一致して、なおかつ重複がなければ、その長さでは条件を満たすことが分かる。

ABC #141 F - Xor Sum 3

各ビットごとに考える。まず、$A_1 \oplus A_2 \oplus … \oplus A_N$ を計算しておき、 1が立っているビットについて、どのように色分けしても答えに影響しないので、取り出しておく。取り出した結果、$A_1 \oplus A_2 \oplus … \oplus A_N = 0$の状態になる。ここで、青色のXORを$X$、赤色のXORを$Y$とする。 $X \oplus Y = 0$なので、XORの性質から、$X = Y$となる。なので、$A_i$から幾つか選んで、そのXORを最大化するような、選び方を見つけたい。吐き出し法（連立1次方程式をといていくような感じ）で、上位のビットから見ていき、 1が立っている要素を pivot 行とみなして、他の要素とXORを取っていく。結果、$X = Y = A_1 \oplus A_2 \oplus … A_N$となる。

ABC136-138

24 Aug 2019

#atcoder

いくつかABCの問題を解いたけど、ブログに記録するのを忘れていた。まとめて書いておく。

ABC #136 D - Gathering Children

一度RLの組に入ると抜け出せない。偶数距離を移動させて、RLの組にくっ付ける。

ABC #136 E - Max GCD

ソートしておいて、小さい値は0に、大きい値は答え$d$に近づける。前と後の両方向から、累積和を求めておく。

ABC #136 F - Enclosed Points

ある点$x$がふくまれるような矩形の数は、その上下左右の4つの領域からそれぞれいくつの点を選ぶかによって計算できる。領域ごとに含まれる点の数を$A, B, C, D$とする。

点$x$を含まない場合は、それぞれの領域から点を取るかどうかで16個に場合分けして考える
点$x$を含む場合は単純に$ABCD$

領域ごとの点数の算出には、平面走査を使う。また、事前に座標は圧縮しておく必要がある。

$(1-(x-i)^{P-1})$のところは、フェルマーの小定理より、$x=i$のときだけ1となる。法 P において、以下が成り立つ。

$x^{P-1}= \begin{cases} 0 & (x = 0) \\ 1 & (x \neq 0) \end{cases}$

1) $X = Y$ の場合
- $Y \% X = Y \oplus X = 0$ なのでOK
2) $X < Y$ の場合
- 2A) 2進数で$X$と$Y$の桁数が同じ
  - $Y \oplus X = Y+X-2(Y\&X)$
  - $Y\%X = Y-X$ （なぜなら $X<Y<2X$ より $Y/X=1$なので）
  - つまり、$X = X \oplus Y$
  - ある桁において$X=1$で$Y=0$はNG（そのほかの3つの場合でOK）
- 2B) 2進数で$X$と$Y$の桁数が同じ
  - NG（$Y\%X$は1から始まり、MODは0から始まるため）
3) $X > Y$の場合
- 問題の対象外なので考えなくて良い

その後、桁DP dp[i][j][k][s] を埋めていく。

上からi桁番目まで見た時
jはX>=Lが確定しているかどうか
kはY<=Rが確定しているかどうか
sは先頭ビットが既に現れたかどうか

Previous Page: 1 of 22 Next