\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{心得報告（5/25）}
\author{R94922149 周恩冉}
\date{}
\maketitle
這次討論的\ paper 是\ {\it Placement of File Replicas in Data Grid Environments} 以及\ {\it Optimal Replica Placement Strategy for Hierarchical Data Grid Systems,} 我們想要解決的問題是在\ tree 狀（hierarchical）的\ grid environment 上放置\ replica 的最佳化問題。

這裡所用的\ model 是在\ tree 上每個\ node 皆代表一個\ site, tree edge 則表兩個 site 間有直接的連線。若有兩個\ site 互相溝通。所有的\ request 都來自\ leaf, 且\ request 總是往\ parent 發送，直到抵達擁有\ replica 的\ node, 並由該\ node 負責\ serve 這個\ request. 且在\ root 上有一份\ master copy, 所有的\ request 最遲將會由\ root 負責\ serve.

今天我們要討論的問題是每個\ leaf 都有\ $w(n)$ 的\ request 量，每個\ node 都有一個\ workload, 即若在該\ node 上有一份\ replica, 則該\ node 的負擔量，並給定每個\ node 的最大\ workload, $D.$ 我們希望在給定\ $w(n)$ 與\ $D$ 時知道最少需要多少份\ replica, 且讓最大的\ workload 為最低。

第一篇\ paper 中提出了一個\ heuristic 解，proportional share replica (PSR), 第二篇\ paper 則提出了一個\ optimal 的演算法，利用\ {\it MinMaxLoad} 與\ {\it FindR} 找到最佳解，其中\ {\it MinMaxLoad} 是在給定\ replica 數量下找到一組\ $R$ 最小化\ $R$ 中\ workload 最高的那個\ node 的\ wordload. {\it FindR} 是給定\ workload 的最大值\ $D$，求出在不讓\ workload 超過\ $D$ 的狀況下，找到讓數量最少的那組\ $R$。

我覺得較關鍵的地方有二，一是我們將\ workload 超過\ $D$ 的\ node 定為\ {\it heavy}, 否則為\ {\it light}, 而\ parent 為\ heavy 的 light node 為\ {\it critical}, 在做\ {\it FindR} 時我們將\ replica 放在\ workload 最高的那個\ critical leaf 上，並更新\ workload 紀錄，重複\ $k$ 次後看看\ root 是否變為\ light.

二是我們又用了慣用技倆\ {\it binary search} 來決定最後\ replica 到底要放在那裡，在用了\ {\it FindR} 知道到底該放多少\ replica 後，使用\ {\it binary search} 來決定放置\ replica 的\ threshold.

再深入的方向除了後面會討論到的加上\ {QoS} 限制外，我想還有把題目的\ model 延伸成\ planer graph, 在\ planer graph 上應該有很好的實際應用。另外值得注意的是課堂上提到的，request 不一定要總是來自\ leaf, 因為來自\ internal node 的\ request 我們可透過在該\ node 上多接一個\ leaf 以模擬來自\ internal node 的\ request.

\end{CJK*}
\end{document}