マルチパスQUICのdraft-ma-quic-mpqoe とその論文 XLINK: QoE-Driven Multi-Path QUIC Transport in Large-scale Video Services を読んだ。

Alibabaによって書かれたマルチパスQUICの論文 https://dl.acm.org/doi/10.1145/3452296.3472893

マルチパスQUICの実装はdraft-liu-multipath-quicに datatracker.ietf.org

XLink固有の実装部分について5月に提出されたdraft draft-ma-quic-mpqoe www.ietf.org

本論文が解決したいサービス品質(Qos)や体感品質(QoE)改善に向けた課題

スムーズな動画開始

TikTokなど短い動画を大量に視聴するアプリが増えている。 短い動画を視聴するユーザは長い動画を視聴するユーザより動画開始までの時間などの体感品質に敏感である。 ユーザにスムーズな動画開始を提供するためにモバイル通信の帯域不足と通信の不安定さを克服する必要がある。

Wi-Fiからモバイル通信への移動

スマホで動画を視聴している時にWi-Fiがある環境からない環境へ移動するとWi-Fiへのアクセスが悪くなり通信が不安定になるのが現状である。QUICのconnection migration 機能はコネクションを従来の5 tuple(ip, port, protocol) 情報ではなくconnection ID で識別するためコネクション情報は失われずにモバイル通信を用いてコネクションを継続することが可能だが、マイグレイション時に輻輳制御windowのサイズはリセットされてしまうため帯域幅が動画を視聴するためのに不足する。マルチパス通信によってWi-Fi通信からモバイル通信にスムーズに移行できるようになることがWi-Fi付近でのモバイル通信の品質向上に繋がる。

論文には書かれていなかったがIETFでのアリババによるMPQUICのユースケースの例では、モバイル通信の品質が下がる新幹線内で、モバイル通信と新幹線が提供する Wi-Fiを組み合わせる例が挙げられていた。

使用する帯域を抑える

上記の課題を解決するために可能な限り帯域を使用してデータを送ることが考えられるが、動画はネットワークのうち8割の帯域を使用するためコストに直結する。(論文によるとコストは $0.085 per GB (https://aws.amazon.com/jp/cloudfront/pricing/ 日本だと0.114 USD) 品質改善を行いながらもコストが大きすぎない手法を取り入れることが経済的に望ましい。

論文で提案されている手法とその特徴

本論文ではQUICのMultipath拡張を用いて動画ストリームをの品質を向上させる。複数のパスを使用することで使用できる帯域を増やすことが目的である。

マルチパス通信だとMultipath-TCPがすでにRFC(RFC 8684)となっているが、こちらはOSサポートが必要なためモバイルデバイスを開発していないアプリ開発者にとってMultipath-TCPの開発コストは高い。QUICのMultipath拡張はアプリケーション層で実装されているため、OSで実装する必要なくデプロイが簡単なためアップグレードやテストがしやすく、アプリやコンテンツの種類によってカスタマイズが容易である。

packet re-injection

単純なMultipath拡張だとMP-HoL blockingによってシングルパスより遅くなってしまう問題がある。これは下の図のように一部のパケットが遅いパスを通ったために後続のパケットより到着が遅れた場合に、既に到着したパケットが遅いパケットが到着するまでに処理できない問題で、これにより遅い方のpathによってlatencyが決まってしまう。 この問題を解決するために本論文ではpacket re-injectionを行う。

XLINK: QoE-Driven Multi-Path QUIC Transport in Large-scale Video Services の Figure 3
packet re-injection では上図のように送信すべきパケットがなくなったとき、送信者は低速パスの損失回復(retransmission timeout)を待たずに、未ACKパケットの複製を高速パスに送信し、受信者はブロッキング効果を受けずにデータを受け取ることができる。 本論文ではre-injectionを行うタイミングはQUICレイヤでは一つのストリームを送り終えたタイミングで、アプリケーションレベルでは動画のフレームごととキリが良いタイミングでpacket re-injectionを行う。これによって後続の関係のないパケットより先にACKが行われていないパケットを再注入することができる。再注入されたパケットは速いパスで送信され、オリジナルのパケットより速く到達する。

packet re-injectionは余分なパケットを送るため帯域を多く使用してしまう問題がある。これはコストがかかるだけでなく、全体のスループットに悪影響を与えてしまう。実際ビデオ再生アプリケーションはバッファに先の動画のデータをためておくので、バッファに多くのデータがある場合はre-injectionは必要ない。本論文ではクライアントアプリケーションからのQoEフィードバックをを参考にre-injectionを行うかどうかを決定する。

以下の図では HoLブロッキングをQoEを用いたpacket re-injectionで解決する実験結果である。 (a) で表されるパスを用いて動画を再生した状況で、 (b) packet re-injectionを行わない場合, (c)毎秒 packet re-injectionを行う場合, (d) QoE情報をもとにpacket re-injectionを行う場合, の4つの実装を用いた場合でバッファに蓄えられたデータ量とre-injectionしたデータ量の時間経過を示す。

(b)ではバッファ量が0になることが確認できることからHoLブロッキングによりリバッファリングが発生していることがわかる。

QoE制御がない(c)ではバッファにデータが十分蓄えられているときもre-injectionが行われていて、不要なデータを使用していた。

(d)では動画をスムーズに流しつつネットワークトラフィックを減らすことに成功した。

QoEフィードバックをサーバに送るためにdraft-liu-multipath-quic-02で新しく紹介されたACK_MP と QOE_CONTROL_SIGNAL frameが使用される。(ただしdraftと異なり論文ではACK_MPでもACK_MP フレームの追加フィールドとして QoE フィードバックを送信する) このフィードバックではさまざまな情報を送ることができる(cached bytes, cached frames, bitrate, framerate)。具体的にスケジューラはQoEフィードバックから、クライアントのバッファに残っている動画再生時間Δtを推定し、クライアントにキャッシュされた動画プレイヤーが持つ残り時間が短い時は即座に再注入を行い、キャッシュされたデータがが十分に大きい時は再注入は行わない判断をします。 この機能により、ビデオ再生開始時や通信状況が悪い時など緊急性が高い時のみre-injectionを行い確実にパケットを早い方のパスからクライアントに届けることに成功した。

MPTCPでは、ACKは送信したときと同じパスで返ってくると仮定するが、XLINKではACK_MPをどのパスでも返せるようにし、早い方のパスでACK_MPを送るようにする。 またXLinkはパスの種類に着目してプライマリのパス選択を行う。例として論文内では以下の優先順位をあげている。5G SA > 5G NSA > Wi-Fi > LTE

シングルパケット番号空間/マルチパケット番号空間

本論文と本論文のMPQUIC実装であるdraft-liu-multipath-quicはパスごとに異なるパケット番号空間を使用する[draft 4.2]。これはパケットロス検出と回復の利便性のためである。

Multipath QUICにはもともとdraft-liuを含む3つの提案が存在していました。draft-liu-multipath-quicは他の二つのdraftと異なりQoEフィードバックを盛り込んでいます。この3つのコアの部分を統合した Multipath Extension for QUIC がwg draftとしてdraft-ietf-quic-multipath として標準化が進められています。

draft-lmbdhk-quic-multipath については こちらを。 asnokaze.hatenablog.com

この仕様の中ではパケット番号空間の使い方をオプションとしてユーザが選択できるように定めています。draft-huitemではシングルパケット番号空間を維持するのに対して、draft-deconinck と draft-liu ではパスごとのパケット空間を使用します。draft-ietf-quic-multipathは現在どちらか選べるようになっていますが、最終的にはどちらかのみが広くサポートされることが考えられる。

The Packet Number Space Debate in Multipath QUIC 内のFigure 1

複数のパケット番号空間は、現在のロス検出アルゴリズムをパス毎に維持でき、複雑なACKの生成(頻度も含む)無しで、受信側に依存しないパフォーマンスを維持できます。しかしパス毎にPacket Numberが異なるのでAEADのnonceの求め方が変わります。 シングルパケット番号空間の場合、zerolength connectionIDが使え、かつ、プロトコルへの追加は少なく、nonceの計算方法も変わりません。しかし、パケット番号を共有するためパケットスケジューリングやACKのロジックで工夫する必要があります。ACKに必要なスペースが多くなるという問題もあります。ACKブロックの数が制限されている実装では全てACKを送れない可能性がある。 The Packet Number Space Debate in Multipath QUIC ではネットワークシミュレータのNS3を使って、それぞれの手法が性能に与える影響を調べています。実験結果からシングルパケット番号空間の場合性能は受信側により依存することがわかった。The Packet Number Space Debate in Multipath QUICについての詳しい説明は以下がわかりやすいです。 like-cat.hatenablog.com

このような議論からXLinkのようにQoEによってパケットを再注入するマルチパス実装においては二つのパスのACKの処理がやりやすい、パスごとのパケット空間が良いと考えられる。

5月に提出されたdraft "An Advanced Scheduling Option for Multipath QUIC"

multipath quic のスケジューリングの部分についてを上記の論文をもとに、レイテンシの制約があるアプリケーションにおいてmultipath quicを使う方法が書かれている。 Alibaba の人たちとC. Huitema 先生がauthor。

www.ietf.org

本論文に書かれていたHoL Blocking の問題と Re-injectionとQoE feedbackの手法について書かれている。

実際にre-injectionを行う頻度を決定するためのQoE feedbackを送るためにQOE_CONTROL_SIGNALS frameを定義している。

  QOE_CONTROL_SIGNALS Frame {
    Type (i) = TBD-02 (experiments use 0xbaba02),
    Path Identifier (..),
    QoE Control Signals Length(8),
    QoE Control Signals (..)
  }

Christian Huitema先生の draft-liu-multipath-quicをpicoquicに実装した話。

Implementing Multipath in QUIChuitema.wordpress.com

draft-liu-multipath-quic-02 allows for acknowledgements of packets sent on one path to be carried over any other available path. Performance will be much better if the acknowledgements are sent on the short delay path rather than on the satellite path. This requires effective measuring delays on each path in each direction and using these measurements to schedule acknowledgement packets. ACKを早い方のパスで送ることができるこのdraftの実装だと 高帯域&高遅延 と 低帯域と低遅延の場合に高遅延の方のACKを低遅延の方で送ることができる。しかしそのためにはきちんと遅延をそれぞれのパスで測る必要がある。

また複数のパスを使うことで1つのパスを使う時より性能が落ちる時は自動的に良い方のパスのみを使うような実装が望ましく、これは輻輳制御によって自動的に行われ、パスの変更は頻繁に起きるため性能がおちてもそのパスを潰さないためにdummy packetを送ることがQUICには可能という話もしていました。

Estimating round trip and one way delays in multipath QUIC sessionshuitema.wordpress.com RTTをどう推定するかの話. 同じパスでACKを送るようにすれば楽だが、遅いパスからのACKが遅れたりそもそもパスが途中で使えなくなった時にACKが得られないのはよくないため、別のパスからACKを送れるようにした方が良い。 picoquicの実装では QUIC timestamp extension draft で定義されたタイムスタンプを使用している。

How many packet number spaces for QUIC Multipath?huitema.wordpress.com

マルチパケット番号空間を実際に実装するのはとても複雑という話。例えばテストを作成するコードはシングルパケット番号空間のコードだと従来のQUICにマルチパスのテストケースを加えるだけで良かったが、マルチパケット番号空間の実装の場合は一つのパスしか使用しないシナリオでもマルチパケット番号空間のためのテストケースが必要。

マルチパケット空間はパケットロス検出がしやすい。

パケットが送信された経路と、各経路で最後に確認されたパケットを追跡します。パケットが失われたかどうかを判断するとき、全体のACKが解された最後のパケットではなく、そのパケットが送られてきたパスに対してACKされた最後のパケットと比較する。

In conclusion, we have a trade-off. Managing separate number spaces for each path increases the complexity of the implementation but may result in slightly more efficient management of acknowledgements. Keeping a single number space for all spaces is much simpler but may require a few tweaks in the management of acknowledgements. The single number space variant supports use of zero length connection identifiers, while the separate number space variant does not. The multiple space variant requires adding a number of code paths that are not exercised by the “single path” tests, which has an effect on code safety. Overall, after implementing both options, I prefer the single-space variant but I am waiting to hear the opinions of other developers.

へー "Overall, after implementing both options, I prefer the single-space variant" なんだ。一年ちょい前のブログだからよくわからないけど。

論文 Toward Just-in-Time Data Communications over Shared Networks and Computational Resources on Massive Client Environmentを読んだ。

不急なデータを送ることが原因で緊急のデータのレイテンシーが増えるのは嬉しくないので、さまざまなアプリケーションを総括したフロー制御を提供するプロトコルスタックを提案する論文。

 

論文リンク: 

https://journals.sagepub.com/doi/full/10.1177/03611981211006731

実用例として、自動運転などで用いる通信を例に挙げている。

車が送受信するデータには、ハンドルやブレーキなどのセンサ情報や危険検知通知情報など安全な運転を行うのに必要なデータと、高度な地図データを作成するための画像データなど緊急ではないデータがある。この緊急でない地図作成データを送るせいで、安全/自動運転を行うのに必要なデータの到着が遅れてない様にしたいという。

 

just-in-time という単語について

論文中で以下の様に説明している

this paper refers to the data communication that completes the content delivery, at the time that content is actually required by an application, as just-in-time data communication.

つまりアプリケーションが実際にデータが必要な時点までにデータの配信を完了させるデータ通信 のことである。

車の例だとセンサ情報などはすぐに届ける必要があるが、地図作成データは数時間先でも良いという話。

 

 

関連技術

論文内で 挙げられている 既存のQoSカニズムとして使われいてるものとしてdiffservがある。Diffservは、インターネット・プロトコル(IP)ヘッダ内の6ビットDSCP(Differentiated Services Code Point)を使用してパケットを分類し、優先順位をつける。

datatracker.ietf.org

Originally defined as the type of service (ToS), this field specifies differentiated services (DiffServ) per RFC 2474.[a] Real-time data streaming makes use of the DSCP field. An example is Voice over IP (VoIP), which is used for interactive voice services.

-- IPv4 - Wikipedia

しかし,diffserv はトラフィックタイプをあらかじめ設定する必要があるため,多様化するアプリケーションに対応することはできない。

 

 

他の例としてNetwork slicing

Network Slicing in 5G: Survey and Challenges | IEEE Journals & Magazine | IEEE Xplore

を挙げている。

 

 

 

プロトコル内容

RFC1122 では プロトコルスタックを link layer, IP layer, transport layer, application layer と定義している。

論文の図

しかしこのIP層で疎通性を確保し、トランスポート層で再送などを実装する方法は最近の技術には合わない場合がある。モバイルエッジコンピューティング(MEC)でデータが前処理されたりする場合など。

 

下の図の様に chaining layer と data flow layerとそれらを実装するプロトコルDFMPとDFCPを提案する。

 

chaining layerはIPネットワーク上にオーバーレイネットワークを構築し、データフローはこのchaining layerを介して配信される。chaining layerは、モバイルエッジコンピューティング(MEC)ノードなどのミドルボックスを意識して、データ通信経路を考慮する。

DTLSとUDPを使用した Data Flow Multiplexing Protocol (DFMP) が使用される。

 

data flow layerはデータフローがアプリケーションで処理可能なデータ形式を保つことを保証する。フロー制御メカニズムを通じて、コンピューティングリソースを含むリソースのアービトレーションを実装する。

Data Flow Control Protocol (DFCP) が使われる。

論文の図

 

Data Flow Multiplexing Protocol (DFMP) and Data Flow Control Protocol (DFCP)

 

DFMPは、異なるjust-in-time要件を持つデータフローを多重化するためのチェーニング層プロトコルです。DFMPは DTLS/UDP上に実装され、データグラムとストリームの両方のデータフローを伝送するように設計されています。

The DFMP common header includes the version of DFMP, protocol flags for extension, the type of the DFMP header, the length of this header including the following DFMP multiplexing header, the flow count representing the number of flows multiplexed in the DFMP packet, the sequence number, and the timestamp for congestion control and data communication quality monitoring.

 

DFCPは、受信機の計算資源やネットワークの帯域幅などの様々な能力に応じてデータフローを制御するためのデータフローレイヤープロトコルである。このプロトコルの目的は、データフローに優先順位をつけ、just-in-timeの要求を満たすように制御することである。そのため、DFCP では、受信機の計算資源の過負荷などの外部(帯域外)資源不足情報と、パケットロスなどの内部(帯域内)輻輳指標によるフロー制御を行う。この仕組みにより、緩やかなjust-in-time要件のデータフローの帯域やパケット転送の一時停止を制限することができる。DFCPの各フローは、DFMPで多重化される。

DFCP は、ストリームとデータグラムの両方のデータフローをサポートする。DFCPの一般ヘッダは、ストリームとデータグラムのデータフローを運ぶための必須情報を定義している。しかし、ヘッダのオーバーヘッドを最小にし、データグラムデータフローとストリームデータフローの両方をサポートするために、追加のDFCPヘッダはデータフロータイプによって異なるものである。DFCP 一般ヘッダは、DFCP パケットのタイプ、タイプ固有の追加ヘッダを含むヘッダ長、ヘッダとペイロードを含む DFCP パケットのチェックサムペイロード長、次のデータフロー層のプロトコルである Next Header を含む。Next Header属性は、1つのDFMPパケットに複数のDFCPフローを多重化するために使用される。

 

 

TCPのフロー制御機構は、ウィンドウサイズフィールドを使用して受信者のメモリ量を考慮していた。DFMP/DFCPのリソースアービトレーションの考え方は、TCPのウィンドウサイズと類似しています。しかし、TCPのウィンドウサイズは、一度通知されたウィンドウサイズの縮小を許さないため、動的なリソースの変化に対する配慮を欠いています。また、TCPのウィンドウサイズは、他のフローとのリソースの調整を目的としたものではありません。その結果、TCPのフロー制御はjust-in-timeのデータ通信を実現することができなかった。

DFMPとDFCPのフロー制御は、他のデータフローとの資源調整の仕組みにより、just-in-timeのデータ通信を実現するように設計されています。

-- discussion の章より

 

実験

二つの車がサーバにデータを送るシナリオを考える。車はそれぞれ just-in-time 要件が 1s の継続的に送るデータ(遠隔運転監視やセンサ情報) と just-in-time 要件が無限のHD map 作成のための大容量画像データ の二種類のデータを送ることを想定する。

論文の図 実験シナリオの図

実験はvm上に4つのdockerコンテナを用いて以下のトポロジーを作成して、実験シナリオの状態を作った。

論文の図 実験で使用したトポロジー

 

 

実験では旧来のTCPUDPを使用した場合と提案手法のDFMPとDFCPを使った時で比較した。

緊急なデータ(遠隔運転監視やセンサ情報) は 再送を行わない UDP と DFCP stateful datagram を使用し、不急なデータ(HD mapのための画像データ)はストリームで送信するため TCP と DFCP stateful stream を使用した。

 

TCPUDPを使用した場合、即座に必要な遠隔運転監視のためのデータの受信が数回乱れることが確認されました。サーバ側で受信したUDPパケットとクライアント側で送信したUDPパケットを比較したところ、パケット8,491個中8個(0.094%)の遠隔運転監視トラフィックが、HD map (不急のデータ) を送るTCPのベストエフォート処理による輻輳のためよりドロップされた。このパケットドロップにより 遠隔運転監視映像の出力に支障をきたした。

 一方、DFMPとDFCPを使用した場合、DFCPの優先送信制御の結果、遠隔運転監視用のデータ受信は乱れることなかった(すなわち、パケットロス0%)。これは、DFMPとDFCPのデータフロー優先制御機構の有効性を示しています。

 

 

Overhead of DFMP/DFCP and effect of short packet multiplexing

提案手法は追加のheader情報の分だけ一つのパケットで送れるbyte数が減るよねという議論。

 

ヘッダーのオーバーヘッドを下表に示す。DFMPがなければ、パケットは多重化されない。そのため,ヘッダのオーバーヘッドが軽減されることはない.これに対し、DFMPでは、短いパケットを多重化することができます。そのため,DFMPは複数パケットの伝送に効率的である。

論文の表



 

 

RFC9218: Extensible Prioritization Scheme for HTTP をまとめてみた。

6月7日 2日前にHTTP/3 をはじめHTTP関連のRFCがHTTP wgよりたくさん発行された。

そのうち 新しいプライオリティ制御方式がRFC9218として標準化されたためまとめた。

www.rfc-editor.org

プライオリティ制御の必要性

  • HTTP/2 , HTTP/3 は、1 つの接続におけるリクエストとレスポンスの多重化が可能
  • 通信をより柔軟・効率的に行う為に各リクエストに優先順位をつけたい
  • 例: 
    • ブラウザが多重化によりCSSと画像のリクエストを同時に送る
    • レスポンスはレンダリングを開始するのに必要なCSSの優先度を上げて欲しい

↓上手なプライオリティ制御が大事というRobin Marxさんの図

引用元: https://h3.edm.uhasselt.be/

RFC7540のストリーム優先度との関係

RFC7540のストリーム プライオリティ制御を置き換える理由

もともと rfc7540 HTTP/2 の section 5.3で stream priority の説明をしている。リエストの依存関係(dependency)と重さ(weight)で優先度を管理する方式をもちいる。

引用元: https://speakerdeck.com/summerwind/2-prioritization?slide=4

しかし仕様が複雑すぎたために広く実装されず、CDNの実装もbugが多かったとのこと。

つまりRFC7540のプライオリティ制御は失敗だったと言えるでしょう。

github.com

 

RFC9218では、よりシンプルで制約が多く、解釈を必要とせず、バリエーションも少ないシグナリングを記述することでより簡単に優先度制御をできる様にしています。

 

RFC7540との互換性

RFC9113 HTTP/2 よりRFC7540のプライオリティ制御はdeprecatedとなった。

相互運用性のための互換性は残してあります。

The description of frame fields and some of the mandatory handling is retained to ensure that implementations of this document remain interoperable with implementations that use the priority signaling described in RFC 7540.

from: RFC 9113: HTTP/2

SETTINGS_NO_RFC7540_PRIORITIES によってRFC9218に従うエンドポイントは相手に RFC7540のHTTP/2 プライオリティシグナルを使用しないことを通知します。

ただしクライアントはサーバからSETTINGSフレームをもらうまではサーバがHTTP/2 プライオリティシグナルを無視するかわからないため、クライアントはHTTP/2 プライオリティシグナル と このRFC9218で定められるprioritization schemeの両方を送ることが推奨される(SHOULD)。

 

Priority Parameters (section4)

  • Urgency(緊急度) と Incremental (逐次処理可能か) の二つの値を送る。
  • RFC7540よりシンプルなアプローチ
  • リクエストとリスポンスどちらにも含まれることがある。
  • ASCII text
  • encoded using Structured Fields
  • HTTP/2 に存在したStream Dependency (依存関係) は完全に廃止。
  • サーバがこれに従ってスケジュールを組むことは RECOMMENDED

Urgency (緊急度)

0 (優先度最大) から7 (優先度最低) までの整数値をとる。 (デフォルト3)

urgency の 高い順に レスポンスをサーバに返して欲しい。

 

最も低い緊急度レベル(7)は、ソフトウェアアップデートの配信のような バックグラウンドタスクのために予約されている。この緊急度レベルは、ユーザーとの対話に影響を与える応答を取得するために 使用されるべきではない(SHOULD NOT)。

 

例: urgencyを 0 に設定して CSS ファイルを要求したもの。

:method = GET
:scheme = https
:authority = example.net
:path = /style.css
priority = u=0

 

Incremental (逐次処理可能か)

ブール値でデフォルト値は false(0)

false(0) に設定して複数同時リクエストを行う場合

  • クライアントは応答を受け取りながら処理できない
  • サーバは同じ緊急度を持つ非インクリメンタルな応答を一つずつ送る。

true(1) に設定して複数同時リクエストを行う場合

  • サーバは同じurgencyを持つリクエストを同時並行に送る。
  • 帯域を分け合うためそれぞれの応答が完了するまでに時間がかかる。
  • 複数の部分的な応答 がクライアントに何らかの価値を提供できる場合有用。

例: JPEGファイルのリクエストを、urgencyパラメータを5に、incrementalパラメータをtrueに設定したもの。

:method = GET
:scheme = https
:authority = example.net
:path = /image.jpg
priority = u=5, i

 

Reprioritization 優先度の変更 (section6)

クライアントがリクエストを送った後、応答の優先度を変更する必要がある時にPRIORITY_UPDATE frameを送ってurgencyパラメータを変更する。

 

例 : JavaScriptのプリフェッチ

  • urgency パラメータを u=7 (background) に設定したプリフェッチリクエストを発行
  • プリフェッチの進行中にユーザーが新しい JavaScript ファイルを参照するページに移動
  • ブラウザは Priority Field Value を u=0 に設定した優先度の変更シグナルを送信

 

複数PRIORITY_UPDATE frameが届いた場合サーバは最新の情報を用いる。

  • HTTP/3では 順番は保証されないためメインよりupdateが先に到着する場合もある。

 

 

PRIORITY_UPDATE frame (Section7)

HTTP/2 ではストリーム ID を指定するのに対し、HTTP/3 では追加で type としてリクエストス トリームなのか、プッシュストリームなのかを指定します。

 

HTTP RFC Publication Study で話しました。

RFCが発行された3日以内に発行されたRFCについて話そうという勉強会に参加させていただきました。自分は7分だけ喋りました。他の人たちはとても長いRFCをdraftの段階から追っていてすごいなと思うとともに自分もこれからもっとRFCとかdraftとか読んでいきたいなとおもいました。

www.youtube.com

 

 

色んな参考サイト

 

kazuho さんが 2019年にhttp wg に送った draft書きましたメール。

lists.w3.org

lists.w3.org

 

http wg adoptionまでの道のりが書かれているLucas先生のブログ

blog.cloudflare.com

 

robin marx 先生

 

 

datatracker.ietf.org

datatracker.ietf.org

datatracker.ietf.org

 

asnokaze.hatenablog.com

 

 

 

 

 

 

GSoC (Google Summer of Code)で chromiumに採択された。

GSoC (Google Summer of Code) は 参加しているoraganization のOSSにコントリブートするためにProposalを書き、採択されれば3ヶ月OSS活動をしてGoogleからお金がもらえるオープンソース活動をしたい人のためのプログラムです。オープンソース活動したいという人におすすめのプログラムです。

プログラムの流れ

  • まず、Googleは学生を受け入れることができるオープンソース団体(organization)を募集する。団体はメンター候補の人数などを伝えて承認されてもらえる様に願う。*1
  • 選考でGoogleに承認された団体は学生に取り組んでほしいタスクのリストを公開する。
  • 学生は各団体のリストを読んで自分に合った団体と課題を決める。課題はリストにない自分が考えた内容でも良い
  • 学生はその内容をProposal Paperと呼ばれる文書にまとめ、自分のやりたいこと、スキル、課題のスケジュールなどを盛り込んで提出する。*2
  • 各団体がそれを読んで選考を行い、学生に順位をつける。
  • GSoCがそれぞれの団体に参加学生枠を配る。*3それぞれの団体が提出した順位のうち参加枠に含まれる学生が合格となる。
  • 無事選考通過した学生はメンターとコミュニケーションを取りながら各々の活動を行っていく。
  • 全プログラムを無事終了しら、報酬金が受け取れる。

採択されました

summerofcode.withgoogle.com

無事に完遂できる様に頑張りたいと思います!!!!

 

応募内容

応募内容は "Implement Happy Eyeballs 2 to chromium" です。 Happy Eyeballs 2 とはDNSをAとAAAAクエリで非同期に行ってどちらかが早く結果が返されたらもう一方を必要以上に待たずに次のステップ(TCP SYNを送る)に移ろうねというアルゴリズムでRFC8305として標準化されています。

datatracker.ietf.org

Happy Eyeballs については以下で英語でまとめてみました。(いつか日本語で清書しようと思ってまだかけてません。近々書きたい)

momoka0122y.hatenablog.com

提出したProposalは以下です。

docs.google.com

応募までの道のり

自分のproposal は少し珍しいパターンで、もともとchromiumから提示されたアイデアではなくchromium全体のissueリストから見つけたプロジェクトなのですが、幸運なことにメンターしてくださる人(そのissueのもともとのowner)がいたのでGSoCとして応募できた形となります。

chromiumへのコントリビュートを始める

こちらのツイートがきっかけでchromiumにコントリビュートしたいという思いが具体的になる。年明けにchromiumをbuildしてissue一覧を見て面白そうand簡単そうなバグを見つけ直そうと頑張る。 (1月に初め時間はかかったが3月に無事にmerge)

 

Happy Eyeballs 2 の issue との出会い

おもしろそうなissue かつ 短時間ではできなさそうな難しそうなissue Implement Happy Eyeballs 2 を見つける。ちょうどこのissueの担当者が東京officeで働くgoogleの方だったので @toyoshim さんにこの内容でGSoCに応募したいことを相談する。GSoCでやっても良いと言われchromiumのprojectリストに追加される。(これは正式にchromiumのproject list が公開される前日ぐらいの出来事)

Proposal を執筆

他の人と違い事前にアイデアを決め、メンターとなる方と連絡をとっていたので逆に落ちる訳にはいかないという思いでProposalの執筆のために頑張りました。3月はずっとchromiumのコードを読んだり他の関連するissueを読んでchromiumのHappy Eyeballs の実装の概要を理解しようと頑張りました。

Proposalを書き終わった後はProposalを(特にProposalを読んで欲しい人をccして) chromiumのnet-devのメーリスに送りました。ccに入れたEric Orth さんにとても有用なコメントをいただけたのでメンター以外で詳しそうな人にもProposalを送るのはより良い計画を立てる上でとても大事だと思います。

groups.google.com

 

採択されるために気をつけたこと

採択されるための必要条件は同じプロジェクト(idea listの中のひとつのproject) に応募している人の中から一番になることです。そしてそれに加え、organizationに応募された全てのprojectのうち順位付された時に合格できる上位n人になることが必要です。

インド人のYouTube動画を見た時に organization は合格者を決める時に proposal, 今までの実績, そのorganizationとどれくらいコミュニケーションをとっているか の3つを見てると言っている人がいました。 (実際どうか知りません)

今までの実績 は今更どうしようもないので*4  Proposalとメンターとのコミュニケーションをきちんとすることにしました。ProposalはGSoCの選考に落ちてもプロジェクトは自分が無給で進めるつもりで何をしたいのかきちんと自分で理解できるまで調べて書きました。コミュニケーションについてはメンターとのチャットだけでなく net-devのメーリスに proposalを投げることや issueにコメントを残すなどしました。

 

先駆者のブログ

応募するにあたってたくさんの方のブログを参考にさせていただきました。過去に日本人の方が何人も参加されているのはとてもモチベーションになりました。ありがとうございます。

LLVM多い(?)

sksat.hatenablog.com

n-yoshikawa.hatenablog.com

n-yoshikawa.hatenablog.com

okuraofvegetable.hatenablog.com

yamaguchi-1024.hatenablog.com

travelingresearcher.com

tanishiking24.hatenablog.com

uenoku.hatenablog.com

tkmr.hatenablog.com

sanposhiho.com

maekawatoshiki.github.io

hakatashi.hatenadiary.com

tkmr.hatenablog.com

 

今年応募した人たち

note.com

 

そして今年同じchromiumに応募したbokkenさんのブログです。

blog.bokken.io

 

 

 

応募する時にProposalを見てくれた人に感謝します。

これから9月まで頑張ります。

*1:詳しく知りません

*2:最大3つのorganizationに対してProposalを提出できるが、一つのProposalに集中した方が採択される可能性は高まると思うのでおすすめされていない

*3:過去のGSoCの参加とか参加できるメンターの数とかによって決まるのかな?

*4:chromiumには2コミットcontribute3月までにできました。

chromium のソースコードにある //chrome と //content

//chrome の README には以下の様に書かれています。

Chrome


This directory contains the open source, application layer of Google Chrome.

Unlike other parts of Chromium like //content, which provide framework intended to support multiple products, this directory contains code that is focused on building specific products with opinionated UX.

 

そして //chrome と 対になるのが //content

Content module


High-level overview
The "content" module is located in src/content, and is the core code needed to render a page using a multi-process sandboxed browser. It includes all the web platform features (i.e. HTML5) and GPU acceleration. It does not include Chrome features, e.g. extensions/autofill/spelling etc.

Motivation
As the Chromium code has grown, features inevitably hooked into the wrong places, causing layering violations and dependencies that shouldn't exist. It's been hard for developers to figure out what the "best" way is because the APIs (when they existed) and features were together in the same directory. To avoid this happening, and to add a clear separation between the core pieces of the code that render a page using a multi-process browser, consensus was reached to move the core Chrome code into src/content (content not chrome :) ).

ここまで読んでも実際の違いがよくわからなかったけど //content の READMEを読み続けたらわかりやすかった。

content vs chrome


content should only contain code that is required to implement the web platform. Generally, a feature belongs in this category if and only if all of the following are true:

 


In contrast, many features that are common to modern web browsers do not satisfy these criteria and thus, are not implemented in content. A non-exhaustive list:

  • Extensions
  • NaCl
  • SpellCheck
  • Autofill
  • Sync
  • Safe Browsing
  • Translate

 

chromium slackを読んでわかったこと。

it's name is not "Chrome" the product, it's "chrome" the UI concept

//chrome は プロダクトの "Chrome" を意味するのではなく UI の 思想についてである。

 

//chrome のコードが変更された時にChromium-based browsers がその影響を受けるかは //chrome codeをどれくらい使うかによる。

 

For example, Edge uses a lot of the browser chrome, Vivaldi uses less.  But I don't know the exact fractions

Edge は chrome をたくさん使うけど Vivaldi はより独自の部分が多い。

 

 

 

nhiroki さんの説明。

nhiroki.jp

より勝手に引用。

コンポーネントによるディレクトリ分け (chrome / content / third_party / base)

 

まずはコンポーネントによるディレクトリ分けです。ウェブページの表示枠(ページフレーム)を表示する最低限のコンポーネントは Content モジュールにまとめられています。Content モジュールは content/ 以下に配置されます。よく Blink/Chromium という表記方法をすることがありますが、開発者はこの content/ ディレクトリを指して Chromium と呼ぶことが多いです。

ページフレームをラップし、さらに Chrome 独自の機能 (ブラウザ拡張とかプロファイルの同期機能など) を実装しているのが Chrome モジュールです。Chrome モジュールは chrome/ ディレクトリにまとめられています。ブラウザ拡張の API 実装が見たい場合はこのディレクトリ以下を探すことになります。

Chromium が依存しているライブラリは third_party/ 以下に配置されます。このディレクトリには動画処理ライブラリ FFmpeg やグラフィックスライブラリ Skia、シリアライザの Protocol Buffers など、様々なライブラリが含まれています。その中でもとりわけ重要なのは Blink モジュールでしょう。Blink は Chromiumレンダリングエンジンです。レンダリングエンジンという名前ですが、実際にはレンダリング以外にも JavaScript を実行したり、JavaScriptC++バインディングを提供したりします。Blink は Chromium プロジェクトの一部で現在は同じリポジトリ内で開発されていますが、WebKit からフォークされた (公式ブログ記事) という歴史的な経緯により third_party/ ディレクトリに配置されていて、さらにディレクトリ名も WebKit のままになっています1 (2018/04/09 追記: WebKit ディレクトリ内の大部分のファイルが新しい blink ディレクトリに移動されました。しかし LayoutTests など一部のファイルは依然として WebKit ディレクトリに残っています)。

v8/ ディレクトリは JavaScript の実行エンジン V8 が配置されます。V8 は Blink のコアコンポーネントですが、開発は別のリポジトリで行われていて、サブモジュールとしてインポートされます。一見すると third_party/ に置かれるべきものですが、必須コンポーネントであるという理由からトップレベディレクトリに置かれています。

base/ は chrome/ や content/ で使われる共通ライブラリで、OS の提供するシステムコールなどを抽象化した API を提供します。ChromiumWindows, Mac, Linux, Android, iOS など様々なプラットフォームをサポートしていますが、この base/ ライブラリのおかげで開発者は下位プラットフォームの差をあまり気にせずプログラミングすることができるようになっています。

 

東京大学 情報理工学系研究科 創造情報学専攻 院試 プログラミング問題 2022年

2022年 入試の過去問はは以下のリンクにあります。

www.i.u-tokyo.ac.jp

 

試験は自分のパソコンで受けます。ネットワーク使用不可。持ち込みあり。

第一部

第二部

そしてUSBで与えられたデータがこちら

問題で使用したデータはUSBで与えられました。

USBデータは他の年の過去問を探した時に共有している人がいなかったのでgithubに上げとくことにしました。

(もし共有不可だったら消します)

github.com

 

試験時間

試験時間は 50分*2 だった気がします。(45*2 かも)

50分*2 となっている理由は途中でトイレ休憩があったためかと思います。問題が地続きなので100分で解かせて欲しかったです。

時間が足りなくなることはないかと思います。

自分は最後の問題は解き方がわからなかったので諦めて寝てました。

 

提出したコード (参考にはならないと思いますが)

github.com

 

試験中のネットの使用は禁止でしたが、本やメモの持ち込みは大丈夫なので pythonのドキュメントページを全部wgetして、また過去問をといて使用した関数を全部パソコンにメモっておきました。

 

(感想)

今回の試験内容は全国のコロナの感染者数がテーマでしたが、データの数が47個あることが47都道府県を表していることに気づいたのは試験が終わった後でした。

rfc826 An Ethernet Address Resolution Protocol (ARP) を読んだ。

rfc826 An Ethernet Address Resolution Protocol (ARP)

リンクは以下から

datatracker.ietf.org

                            Abstract

The implementation of protocol P on a sending host S decides,
through protocol P's routing mechanism, that it wants to transmit
to a target host T located some place on a connected piece of
10Mbit Ethernet cable.  To actually transmit the Ethernet packet
a 48.bit Ethernet address must be generated.  The addresses of
hosts within protocol P are not always compatible with the
corresponding Ethernet address (being different lengths or
values).  Presented here is a protocol that allows dynamic
distribution of the information needed to build tables to
translate an address A in protocol P's address space into a
48.bit Ethernet address.
The Problem:
------------

The world is a jungle in general, and the networking game
contributes many animals.  At nearly every layer of a network
architecture there are several potential protocols that could be
used.  For example, at a high level, there is TELNET and SUPDUP
for remote login.  Somewhere below that there is a reliable byte
stream protocol, which might be CHAOS protocol, DOD TCP, Xerox
BSP or DECnet.  Even closer to the hardware is the logical
transport layer, which might be CHAOS, DOD Internet, Xerox PUP,
or DECnet.  The 10Mbit Ethernet allows all of these protocols
(and more) to coexist on a single cable by means of a type field
in the Ethernet packet header.  However, the 10Mbit Ethernet
requires 48.bit addresses on the physical cable, yet most
protocol addresses are not 48.bits long, nor do they necessarily
have any relationship to the 48.bit Ethernet address of the
hardware.  For example, CHAOS addresses are 16.bits, DOD Internet
addresses are 32.bits, and Xerox PUP addresses are 8.bits.  A
protocol is needed to dynamically distribute the correspondences
between a <protocol, address> pair and a 48.bit Ethernet address.

上位層のプロトコルの多くがイーサネットを使用しています。 しかし、10Mbit Ethernetは物理ケーブル上に48.bitのアドレスを必要としますが、ほとんどのプロトコルアドレスは48.bit長ではなく、またハードウェアの48.bit Ethernetアドレスと必ずしも関係があるわけでもない。 TCP/IP を使用するためにはIPアドレスを使うが、MACアドレスIPアドレスのアドレス解決をできる必要がある。

Packet format:
--------------

To communicate mappings from <protocol, address> pairs to 48.bit
Ethernet addresses, a packet format that embodies the Address
Resolution protocol is needed.  The format of the packet follows.

    Ethernet transmission layer (not necessarily accessible to
         the user):
        48.bit: Ethernet address of destination
        48.bit: Ethernet address of sender
        16.bit: Protocol type = ether_type$ADDRESS_RESOLUTION
    Ethernet packet data:
        16.bit: (ar$hrd) Hardware address space (e.g., Ethernet,
                         Packet Radio Net.)
        16.bit: (ar$pro) Protocol address space.  For Ethernet
                         hardware, this is from the set of type
                         fields ether_typ$<protocol>.
         8.bit: (ar$hln) byte length of each hardware address
         8.bit: (ar$pln) byte length of each protocol address
        16.bit: (ar$op)  opcode (ares_op$REQUEST | ares_op$REPLY)
        nbytes: (ar$sha) Hardware address of sender of this
                         packet, n from the ar$hln field.
        mbytes: (ar$spa) Protocol address of sender of this
                         packet, m from the ar$pln field.
        nbytes: (ar$tha) Hardware address of target of this
                         packet (if known).
        mbytes: (ar$tpa) Protocol address of target.

まず、Ethernet headerの情報がある。

    Ethernet transmission layer (not necessarily accessible to
         the user):
        48.bit: Ethernet address of destination
        48.bit: Ethernet address of sender
        16.bit: Protocol type = ether_type$ADDRESS_RESOLUTION

16.bit: Protocol type はこの場合ARPを示す0x0806を使用する。

Ethertype   Ethertype       Description              Reference
(decimal)    (hex)        

  2054        0806     Address Resolution Protocol    [RFC7042]

from: https://www.iana.org/assignments/ieee-802-numbers/ieee-802-numbers.txt

他のEthertypesとしてIETFが定めたものとして以下のものがある

B.1.  Some Ethertypes Specified by the IETF

   0x0800  Internet Protocol Version 4 (IPv4)
   0x0806  Address Resolution Protocol (ARP)
   0x0808  Frame Relay ARP
   0x22F3  TRILL
   0x22F4  L2-IS-IS
   0x8035  Reverse Address Resolution Protocol (RARP)
   0x86DD  Internet Protocol Version 6 (IPv6)
   0x880B  Point-to-Point Protocol (PPP)
   0x880C  General Switch Management Protocol (GSMP)
   0x8847  MPLS
   0x8848  MPLS with upstream-assigned label
   0x8861  Multicast Channel Allocation Protocol (MCAP)
   0x8863  PPP over Ethernet (PPPoE) Discovery Stage
   0x8864  PPP over Ethernet (PPPoE) Session Stage
   0x893B  TRILL Fine Grained Labeling (FGL)
   0x8946  TRILL RBridge Channel

from: https://datatracker.ietf.org/doc/html/rfc7042#appendix-B

そしてEthernet header のあとにEthernet Payloadが続く

    Ethernet packet data:
        16.bit: (ar$hrd) Hardware address space (e.g., Ethernet,
                         Packet Radio Net.)
        16.bit: (ar$pro) Protocol address space.  For Ethernet
                         hardware, this is from the set of type
                         fields ether_typ$<protocol>.
         8.bit: (ar$hln) byte length of each hardware address
         8.bit: (ar$pln) byte length of each protocol address
        16.bit: (ar$op)  opcode (ares_op$REQUEST | ares_op$REPLY)
        nbytes: (ar$sha) Hardware address of sender of this
                         packet, n from the ar$hln field.
        mbytes: (ar$spa) Protocol address of sender of this
                         packet, m from the ar$pln field.
        nbytes: (ar$tha) Hardware address of target of this
                         packet (if known).
        mbytes: (ar$tpa) Protocol address of target.

TCP/IP でのARPでは実際に何の値をいれるか。

Hardware address space (ar$hrd) には Ethernet (10Mb) を表す Hardware Types である0x0001を使用。

    Number   Hardware Type (hrd)              Reference
       0     Reserved                         [RFC5494]
       1     Ethernet (10Mb)                  [Jon_Postel]
       2     Experimental Ethernet (3Mb)      [Jon_Postel]
       .
       .

Protocol address space (ar$pro) には IPv4 を表すEthertypes である 0x0800 を使用。

アルゴリズム

RFCより引用

?Do I have the hardware type in ar$hrd?
Yes: (almost definitely)
  [optionally check the hardware length ar$hln]
  ?Do I speak the protocol in ar$pro?
  Yes:
    [optionally check the protocol length ar$pln]
    Merge_flag := false
    If the pair <protocol type, sender protocol address> is
        already in my translation table, update the sender
        hardware address field of the entry with the new
        information in the packet and set Merge_flag to true.
    ?Am I the target protocol address?
    Yes:
      If Merge_flag is false, add the triplet <protocol type,
          sender protocol address, sender hardware address> to
          the translation table.
      ?Is the opcode ares_op$REQUEST?  (NOW look at the opcode!!)
      Yes:
        Swap hardware and protocol fields, putting the local
            hardware and protocol addresses in the sender fields.
        Set the ar$op field to ares_op$REPLY
        Send the packet to the (new) target hardware address on
            the same hardware on which the request was received.

日本語に訳すと以下

?ハードウェアの種類はar$hrdにありますか?
はい:(ほぼ間違いなくEthernet)
  [オプションでハードウェアの長さar$hlnを確認する] 。
  
  ?ar$proで指定されたプロトコル(IPv4)を話しているか? 
  はい: 
    [オプションでプロトコルの長さを確認するar$pln]。
    
    Merge_flag := false
     <protocol type, sender protocol address>のペアが
     すでに変換テーブルにある場合、パケットの新しい情報でエントリ
     の送信者ハードウェアアドレスフィールドを更新し、
     Merge_flagをtrueに設定する。
     
    ?私はターゲットプロトコルアドレスですか?
    はい:
      Merge_flag が false の場合、<protocol type, 
      送信者プロトコルアドレス, 送信者ハードウェアアドレス>
      を変換テーブルに追加する。
      
      ?オペコードはares_op$REQUESTか? (今すぐオペコードを見よ!!)
      はい:
        ハードウェアとプロトコルのフィールドを入れ替え、
        ローカルハードウェアとプロトコルのアドレスを送信者フィールドに入れる。
        
        ar$opフィールドをairs_op$REPLYに設定する。
        
        要求を受けたハードウェアと同じハードウェア上の(新しい)
        ターゲット・ハードウェア・アドレスにパケットを送信する。

上記をコードにすると以下のようである。 コードはmicrops から github.com

static void
arp_input(const uint8_t *data, size_t len, struct net_device *dev)
{
    struct arp_ether_ip *msg;
    ip_addr_t spa, tpa;
    int merge = 0;
    struct net_iface *iface;

    if (len < sizeof(*msg)) {
        errorf("too short");
        return;
    }
    msg = (struct arp_ether_ip *)data;

    // ハードウェアアドレスのチェック
    if (ntoh16(msg->hdr.hrd) != ARP_HRD_ETHER || msg->hdr.hln != ETHER_ADDR_LEN) {
        errorf("unsupported hardware address");
        return;
    }

    // プロトコルアドレスのチェック
    if (ntoh16(msg->hdr.pro) != ARP_PRO_IP || msg->hdr.pln != IP_ADDR_LEN) {
        errorf("unsupported protocol address");
        return;
    }

    memcpy(&spa, msg->spa, sizeof(spa));
    memcpy(&tpa, msg->tpa, sizeof(tpa));

    if (arp_cache_update(spa, msg->sha)) {
        /* updated */
        merge = 1;
    }

    // デバイスに紐づくIPインタフェースを取得する
    iface = net_device_get_iface(dev, NET_IFACE_FAMILY_IP);

    // ARP要求のターゲットプロトコルアドレスと一致するか確認
    if (iface && ((struct ip_iface *)iface)->unicast == tpa) {
        if (!merge) {
            arp_cache_insert(spa, msg->sha);
        }
        if (ntoh16(msg->hdr.op) == ARP_OP_REQUEST) {
            arp_reply(iface, msg->sha, spa, msg->sha);
        }
    }
}

KLab camp の TCP/IP 自作キャンプに参加してARPRFCを読もうと思った時のまとめ。 その時の資料は以下から

drive.google.com