第四章原則的運用-wenkub.com

　 　

【正文】 優化預期情形 ? 最 常見情形是兩個與會者之間對話，保留上一個說話人的視頻圖像可以提供視覺上的連續性。 ? 還 有擴放性更好的方案嗎？ 分析 ? 利用交換機硬件支持 manytomany VC的能力 （ P4c） ，但需要解決每次只能一個節點發送的問題 。 ? 當兩人進行對話時，能看到兩個人的表情 。 manytomany VC ? ATM交換機硬件很容易實現“多對多” VC： ? 交換機將任 何一個 源節點發送的數據復制 后發送 給所有的接收節點。 ? 如果有 N條標識符，該策略需要 log2N+M次查找 。 ? 算法出現錯誤的原因： ? 當查找移動到下一列、并且依據二分查找法確定一個新的查找位置時，假設該位置上的標識符和所要查找的標識符具有相同的字符前綴。 ? 如果表中有 N 條標識符，且已按字典序排列， 簡單的二分查找需要 W log2N 次比較操作。 ? 什么樣的簡單信息可以 刻畫 用戶的上一次請求？ ? 上一次請求的時間 ? 在數據庫中增加 什么 冗余狀態（ P12）， 可以 利用用戶傳遞的信息 來 加快增量查詢 ？ ? 數據庫更新歷史列表 解決方案 ? 增加一個更新歷史列表，僅保存數據庫發生的更新。 分析 ? 如果數據庫不存儲用戶上一次讀過的內容，那么用戶在讀請求中必須傳遞一些與上一次讀請求相關的信息 （ P10） 。 思考 ? 對于 TCP來說，以上方案是一個好主意嗎？ 思考 ? 對于 TCP來說，以上方案是一個好主意嗎？ ? 激進的確認抑制可能會影響 TCP的哪些方面？ ? 流量控制 ? 擁塞控制 ? RTT估算 思考 ? 對于 TCP來說，以上方案是一個好主意嗎？ ? 激進的確認抑制可能會影響 TCP的哪些方面？ ? 流量控制：發送方不能及時推進發送窗口，阻塞發送方 ? 擁塞控制：發送方不能及時檢測到擁塞，也不能利用確認調整擁塞窗口大小 ? RTT估算：不準確 思考 ? 對于 TCP來說，以上方案是一個好主意嗎？ ? 激進的確認抑制可能會影響 TCP的哪些方面？ ? 流量控制：發送方不能及時推進發送窗口，阻塞發送方 ? 擁塞控制：發送方不能及時檢測到擁塞，也不能利用確認調整擁塞窗口 ? RTT估算：不準確 ? Q3：對系統某部分的改變是否會影響系統的其它部分？ 對大數據庫的增量訪問 ? 假定用戶連續讀一個存放在 web網站的大數據庫，用戶只想知道自上一次讀過之后變化了的內容。 解決方案 ? 發送端應用傳遞 1個比特給發送端傳輸 層 ：當還有數據要發送時，該位置 1。 抑制確認 ? 不少傳輸協議（如 TCP）通過確認實現可靠傳輸 ， 大多數協議采用累積確認。 （需要雙向鏈表） ? 如果 不要求 立即回收 資源 ， 可以 只對節點做一個刪除標記，等方便的時候再 刪除 （ P2b， Evaluate Lazily） 。 ? Q3：對系統某一部分顯而易見 的改進可能影響系統的其它部分 問題 ? 能否 保留哈希表， 去 除線性鏈表 （ P1，消除顯而易見的浪費） ？ ? 能否實現哈希表快速遍歷，哪怕需要增加一些狀態 （ P2，增加狀態）？ ? 能否 使用單向鏈表 ，與此同時 又不影響刪除的速度？ 分析（ 1） ? 為避免檢查空的哈希表項，只需將非空的哈希表項用指針鏈起來， 并保存指向每個沖突鏈的指針 。 ? 每當一個 TCP包到來，掃描已打開連接鏈表，查找TCP包所屬的 TCP連接。 二項式桶排序 解決方案 ? 使用二項式桶，桶 i 包含資源使用在 [2i , 2i+11]之間的所有用戶，每個桶包含一組未經排序的資源使用記錄。 ? 用戶分組：將資源使用數量在 [2i, 2i+11]之間的用戶劃為一組。 找出資源使用大戶 ? 設備希望有一種簡單的方法找到資源使用大戶 ? 最簡單的方法是使用一個堆，但如果用戶數量很大，在高速網絡中不可接受 ? 如果資源使用數量的數值很大，桶排序也不適用 ? 假定不要求找到精確的最大值，可以接受 2倍以內的誤差 問題 ? 設計一個軟件或硬件模塊跟蹤用戶使用的資源 ? 該模塊需要一個簡單的方法來找到消費最多資源的用戶 ? 由于普通的堆太慢，設計者愿意放寬系統要求 （P3b，犧牲精度換時間） 不超過 2倍 ? 問題：在精度上放寬要求后，能夠找到一個更有效的算法嗎？ 分析 ? 放寬精度要求后，可以將資源使用差異在 2倍之內的用戶聚合到一個“資源使用組”，尋找最大用戶變為尋找最大組 （ P3b） 。 解決方案 ? 路由器使用一個 周期為 T 的 定時器和一個計數器。 分析（續） ? 能否只用一個定時器來抓住違約的流？ 分析（續） ? 能否只用一個定時器來抓住違約的流？ ? 一定要在 間隔 固定的時間 點上 啟動 測量 過程嗎？ 分析（續） ? 能否只用一個定時器來抓住違約的流？ ? 一定要在 間隔 固定的時間 點上 啟動 測量 過程嗎？ ? 利用自由度（ P13） ：測量過程 不需要 在 固定 的時間點上啟動 ，在連續的兩個 測量 周期之間 允許 有空隙。 ? 網絡應當 有 監督 應用 流量 的措施 ，以抓住那些不遵守約定的應用。 ? 原因： 同一個路由器發布的同一時刻的鏈路狀態必須放在同一個 LSP中傳輸 。 ? 路由器使用分組 序號識別重復 及過時 的 LSP，并只使用最新的鏈路狀態計算最小代價路由 。 ? Cache可看成是由 形如 a, f(a)的值對構成的數據庫， a為索引。 問題 ? 功能需求： ? 每個到來的數據包必須同所有的過濾器進行匹配，過濾器描述了數據包使用的源地址、源端口和目的端口。 ? 問題： ? 如何壓縮 trie節點，使得查找速度的降低不超過一個小的常數因子？ 分析 ? 必須保持數組索引的有效性，即不查找列表，就能迅速知道有無要查找的元素，