\documentclass[12pt]{article}
\usepackage{CJK}
\topmargin 0in
\headheight 0in
\headsep 0in
\textheight 9.5in
\textwidth 6.3in
\evensidemargin 0in
\oddsidemargin 0in
\parskip 0.16in
\begin{document}
\begin{CJK*}{Bg5}{ming}
\title{心得報告（6/22）}
\author{R94922149 周恩冉}
\date{}
\maketitle
這次報告的\ paper 有兩篇，一篇是\ \textit{Optimal Content Location in Multicast Based Overlay Networks with Content Updates} 另一篇是\ \textit{Placement of Web-Server Proxies with Consideration of Read and Update Operation on the Internet}.  這篇心得中我選擇的是第二篇。

這裡討論的問題是在網路上放置\ transparent proxy 並考墦{\ read, update 的\ cost, 以及\ proxy hit ratio.  當\ client 發出\ request 時會走最短路徑到\ server（唯一的）讀取資料，若途中碰到\ transparent proxy 則有\ $\rho$ 的機率會\ hit, 由\ proxy 負責回應，$1 - \rho$ 的機率會\ miss, 則直接由原\ server 負責回應。Read 的\ cost 由\ request 到\ server 或\ hit 的 proxy 之間的距離決定，update 的\ cost 則是由\ short path tree (SPT) 的\ tree edge 總長決定，其中 SPT 就是從\ server 發出\ multicast 到各個\ proxy 所產生的\ tree.  又由於\ request 走\ shortest path 到\ server 的路徑會形成樹狀結構，因此我們可以把題目簡化到在樹上討論，由\ server multicast 到各個\ proxy 所產生的路徑會跟各\ proxy 走最短路徑到\ server 形成的\ tree 相同，也就是\ SPT.

解決這個問題的關鍵在把跟節點為\ $v$ 的\ tree 分成三部份，分法是先決定第一個\ proxy $u$ 在那裡，在\ $u$ 左邊的樹稱為\ $L_{v, u}$, $u$ 的子樹稱為\ $T_u$, 剩下的部份稱為\ $R_{v,u}$, 參考\ paper Figure~4.  如此，在\ $L_{v,u}$ 中全部的\ request 負責，在\ $T_u$ 中全部的點由\ $u$ 負責，而\ $R_{v,u}$ 就又形成一棵新的\ tree, 如此就可以用遞迴的方式處理。

把樹分成三部份後要計算\ cost 就輕而易舉了，$L_{v,u}$ 中不會有其他的\ proxy, 全部的\ node 都由\ $v$ 負責，直接加起來就可以了，$T_u$ 中也不會有其他的\ proxy, 全部由\ $u$ 負責，也是全部加起來即可，$R_{v,u}$ 則可以再遞迴展跚}成三部份，要注意的地方是\ update cost 的部份，update 路徑只要計算走到\ $\pi(u,v)$ 就可以了，以免重複計算\ update cost.  如此再搭配放置\ proxy 個數的條件，整個遞迴就完成了。

這篇\ paper 我蓋{為最有特別的地方在於這種把樹拆成三部的的作法，三部份中的前兩部份都不另外放\ proxy, 第三部份則遞迴定義，這個招式真是相當厲害。把樹拆成數個部份的方法除了最基本的，拆成\ root 和數個子樹，然後對子樹遞迴以外，我們這學期還看到了一些有趣的作法，例如之前有考墦{\ root 加上前\ $i$ 個子樹的拆法，以及在計算\ contribution function 時只看前\ $i$ 個子樹，不包含\ root 的拆法，從我們目前的經驗看來似乎可以把這些作法分成幾類，遇到類似的問題就可以直接套用，或是如老師說的，發展出一個萬能的方法，只要題目一來，套上這個萬用的方法就能自動產生遞迴方法。

另外從這幾篇\ paper 我們也可以發淚{樹狀結構真是一種非常好的結構，只要能把樹找到，多半可以找到\ dynamic programming 的方法，我想這大約是因為\ tree 是\ acyclic 的緣故，只要我們找到一點可以切斷，就可以把問題分成比較不相關的幾部份，而且有時子問題的解也會是整個大問題的解的一部分，非常有\ dynamic programming 的感覺。
	
\end{CJK*}
\end{document}