..
SDN Exp#3 log
第三次實驗需要完成端口負載測量，帶寬測量，然後完成最優帶寬路徑的轉發。
本次實験需要搗鼓的地方不多。
測量端口負載
根據交換機對 OFPMP_PORT_STATS 的回覆中有的 tx_bytes, rx_bytes, duration_sec 以及 duration_nsec 字段可求得交換機端口的負載。
uint64_t rx_bytes; /* Number of received bytes. */
uint64_t tx_bytes; /* Number of transmitted bytes. */
uint32_t duration_sec; /* Time port has alive in seconds. */
uint32_t duration_nsec; /* Time port has alive in nanoseconds beyond duration_sec. */
由上聲明時的注釋可知：
rx_bytes 與 tx_bytes 之和即為總接收的字节數，故端口負載為：
(rx_bytes + tx_bytes - lst_rx_bytes + lst_tx_bytes) * 8 * 1e-6 \
/ (duration_sec + duration_nsec * 1e-9 - lst_duration_sec - lst_duration_nsec * 1e-9)
再多開一個線程進行周期性測量。
最佳帶寬路徑
約定交換機之間的總帶寬為 1000 Mbps，交換機與主機間則無有限制。
可用帶寬 = 總帶寬 - 負載
再建圖的 get_topo 中完善帶寬信息後，祗需完成瓶頸路的計算。指導書中利用 networkx 中的 shortest_simple_paths 返迴所有 s1 至 s2 的路徑而後一一检查，無疑是最烂的方法。當圖為有 $n$ 个結點的完全圖時，其路徑數為：
一種簡單易理解的方法就是二分答案，複雜度為 $O(n\log A)$，$A$ 為最大帶寬可能值。另外利用 Kruskal 算法得到的樹狀圖中的任意两點間的路徑即為瓶頸路，可利用反證的一些想法證明此點。這樣就能 $O(n\log m)$ 建圖而後 $O(n)$ 回答。最小生成樹的算法 networkx 亦有實現，調用即可。
附加題
附加題與前两問關係不大，意在實現一个路徑計算，必須先經過某個中間點 Tinker 再到目的地且未至 Tinker 前不允許經過目的主機直連的交換機。求最小跳數路經。
這個問題非常容易，bfs 並維護一個當前是否經過 Tinker 的記錄，複雜度 $O(n)$。