高網reading assignment 心得～

這學期修了一科高等網路，這門課蠻精采的，因為老師的學問十分淵博，而且也有王牌貝爾實驗室的實務經驗，所以也能夠透過一些實際上的例子，讓我們將複雜的網路理論、統計及數學和實務上要處理的問題連在一起。

不過像老師是這樣的強者，也是有一些令人傷腦筋的地方，比方說對強者而言，一些基礎的數學與統計是必備知識，上星期出了一篇reading assignment, 喵尾巴一看之下險些沒有昏倒，超多統計和積分的符號，不出幾秒就把acrobat關了，怕影響消化(當時在吃晚飯)，並且一面心想強者和弱者真的是差太多了~

不過這篇論文被擺了幾天之後，心裡還是隱隱覺得不安，想說難得修了高網，怎可輕易放過level up 的好機會? 所以再拿起來看，順便複習一些基礎的數學：
這篇文章要解的題目是，假設對於網路 QoS 的要求的Criteria 為end to end delay 對於某一延遲時間t(i.g., 5 sec) 的overdue probability(p) 的話；我們要如何將這樣的要求，allocate 在單一的network component 上? 而不用每一種可能的end to end path都做monitor ?
在這篇文章裏提到的數學武器有下列數種：
(0) 一個path 上關於end to end 的measure 由path 上element 貢獻所得

(1) Convolution
Convolution，這篇論文章的應用是：當有兩個random variable合成的時候，它們的probability distributed function (pdf)會形成何種分布? 答案即是此兩個變數的pdf 的Convolution.
單純用這個方法，配合(0)的定義，解得的解為:
每一個element 的delay 為t/k, 而每個element 的overdue probability 為 1- (1-p)^k。這樣的解簡單，但是太過保守。

(2) Laplace transform 是?
在通信領域中，是指將時間域中的函數轉換成在頻率域中的函數。在時間域中的捲積等於在頻率域中的乘積，可以簡化計算。在這篇文章中是應用重點。(其實是蠻古遠的記憶了，好像大二工程數學有教過嘿，不過全忘光光~)
本篇論文利用queue theory 的model，將interarrival time distribution 及 service time distribution作Laplace transform 之後，會很漂亮(神秘)的得到一個element 上waiting time pdf下限。這時卷積又可以派得上用場，大意是說函數下限的捲積是函數捲積的下限。利用對這個下限值的限制可以反推重要的參數，如，utilization.

(3) Markov inequality
Markov's inequality gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant (– from wikipedia)
它的form 為：
Pr(|X|>=a) <= E(|X|)/a
就是說，如果知道一個random variable 的Mean值，就可以用上面的式子求取這個random variable 大於某正數的機率. 可以直接套來解這個問題。所得的參數為每個element 上的mean delay.

(4) Chebychev inequality
In probability theory, Chebyshev's inequality (also known as Tchebysheff's inequality, Chebyshev's theorem, or the Bienaymé-Chebyshev inequality), named after Pafnuty Chebyshev but first formulated by his friend and colleague Irénée-Jules Bienaymé[1], states that in any data sample or probability distribution, nearly all the values are close to the mean value, and provides a quantitative description of "nearly all" and "close to". (- from wikipedia) (寫到這裏不禁慶幸網路可以讓我們與世界接軌~)
它的form 可以表示如下：
P[X-E(X)>=t] <= 1/(1 + t2/Var(X)) 這是one side 的Chebychev inequality, 就是說如果t > E(X)的話可以這樣用。(t < E(X)的話稍稍做點變化就可以算了。) 如果知道一個random variable 的mean和variance 就可以用上式求取此數大於某值的機率。也可以直接應用來解題。

(5) Normal distribution
如果有k個random variable, 其分佈為normal distribution, 它們線性組合出的數的probability distribution function也為normal distribution. 可以直接套用解題。
由以上五種方法看來，可知要解這個問題，統計的觀念必須要好一點才行…拿出課本K吧!