如果sementation fault發生在STL的map中？

.

如果sementation fault發生在STL的map中，而非你寫的程式，該怎麼辦？
google了一下，大家都說是memory access跨boundary，這其實是廢話，因為sementation fault本身就imply這個事實

個人有發生過一個case，提出來供大家參考
當我在struct中宣告一個map時，這個struct能否動態被配置記憶體並使用？
答案是可以，但是在該struct被new出來後，不可以用memset去清空

如下的struct，在new出來後，若用memset去清空該struct，再去使用該struct中的map，就會出現
"程式記憶體區段錯誤"
若不清空，則就可以正常使用

struct peer_ent {
unsigned long IP; // the IP of the remote peer.
map tcp_conn_tbl; // key == lport + wport (4B)
map udp_conn_tbl; // key == lport + wport (4B)
unsigned long time; // 20100320: ????
unsigned char is_1st_pkt;
unsigned char dir; // when the peer's dir == the dir of 1st conn between the host and peer
unsigned char rsvr[2]; // reserved
};

.

Kad的心得

前言
Kad是Kademlia的縮寫，Kad是一個廣泛被實做的DHT protocol，目前最流行的BT和eMule都實做了Kad
DHT的目的就是為了實現沒有server的目標（decentralized)，更準確的說就是人人都是server，人人都是 client

理論上，p2p在實做Kad後，可以在沒有tracker (BT)或是server (eMule)的情況下，搜尋檔案或是找到抓同一個檔案的peer，在知道哪些peer在抓同一個檔案後，就可以開始p2p了，eMule和BT都是用udp實做Kad

Kad使用了xor (exclusive or)的方法去計算距離，需要注意的是，如果把Kad network視為overlay network，那麼Kad計算的是ovlay network上邏輯上的距離，而非真的實體距離

在暸解Kad之前，必需先暸解何為DHT（在BitTorrent的main line中，他只有DHT這個選項而沒有Kad這個選項，儘管他是Kad實作DHT）



我所理解的DHT
DHT是Distributed Hash Table的縮寫，在我的理解中，Table是一個2-column table，每一筆entry就是 pair，而DHT的行為大概接近如下，有檔案的檔腦將他的檔案hash之後得到key，而自己的電腦的IP就是value，再依照"特定的方法"指到一臺電腦將 pair存到他的電腦上，所有有同樣檔的人都會依照"特定的方法"找到"同一臺"電腦將 pair存到他的電腦上，而想要抓該檔案的人在有key的情況下，就可以找到"同一臺"電腦得到所有的 pair，由於value就是IP，因此他就知道哪些IP有這個檔案了，也就可以開始P2P了

在這個過程中，hash的value稱為key是因為，所有人只要有key就能找到同一臺電腦
在這我們稱該臺被找到的電腦為"負責人"，所有有同一個檔案的人都可以得到同一把key，然後全都可以告訢該負責人"他們都有這個檔案"，而所有要抓檔案的人只要有key都可以找到負責人問出"哪些人有這個檔案"，所有key是關鍵，而key又是經由hash得到的，而對DHT而言，"如何依照特定的方法找到負責人"才是研究的人要關心的，Kad就是這樣的一個方法，而Kad的前輩chord，也是一個方法



我所理解的chord
Kad和chord很像，暸解了chord，你就知道Kad怎運作
在chord中，每一個node的IP就是本身的ID，chord把一個object（object可以為實體的檔案，如歌、電影、文件之類的，也可以為任何邏輯上的物件）投影（就是hash，但是我認為hash的邏輯上的意義就是投影）到和4Byte(32bit)IP相同的空間

我們令投影的結果，也就是hash value為key，而value就是有這個object的node的IP，所有的P2P中server負責的任務不過就是讓所以query的人知道有這個檔案的IP是哪些，於是他就可以跟這些IP交換這個檔案，而DHT就是把這個工均攤到所有人身上，換句話說，在將object hash得到key，而有這個object的電腦的IP的value，於是我們就會有一對 pair，在DHT中，擁有該檔案的人或正在抓該檔案的人將 store 到某個被找到的"負責人"身上

假設所有的IP都存在於chord network中（這裡不考慮private IP的3段range），那麼最理想的狀況是，所有的key都找得到人負責，而且是1-to-1 mapping（別忘了，key落在IP的space，而每個IP都存在），所以這時的狀況就很簡單，誰的IP等於該key，那麼誰就是該key的負責人

遺憾的是，這種事不會發生，大部份的情況下，擁有該key的IP的node都不存在，那麼怎麼辦？參考下圖，我們將32bit的space想像是一個有方向性的圓，而且是單方向性（uni-directional）的圓，IP過了(2^32-1)會wrap around回0，於是可以存在一個很簡單的邏輯，那就是若不存在IP == key的node，那麼就從key往下搜尋（也就是IP++，incremental），直到遇到的第一個活著的node，那麼他就是負責人，依照這個邏輯，publish和query都可以輕易的找到同一個負責人，大概就如下圖所示的方法

大致流程可以這樣想像
假設，有三臺電腦分別為a, b, c，他們都有一條歌叫hero.mp3，假設hero.mp3的hash value為x，也就是說hero.mp3的key = x，於是在a, b, c進入chord network時，他們必需做publish這個動作
publish指的就是告訴別人你有什麼檔案，也就是說，如果你有10個檔案要分享，那麼你必需將這三個檔案publish出去，將10個檔案的 pair儲存在對應的負責人身上

於是a, b, c會而用key x找到一個負責人y，然後a, b, c會將 pair，也就是、、 儲存到負責人y的table中
現在有一臺腦z想要抓hero.mp3這首歌，而z也算出hero.mp3的key = x，於是z利用x找到負責人y，y再將table中的3個entry傳回，於是z就知道a, b, c都有這首歌，也就可以跟他們抓了



Kademlia
Kadd的paper只有6頁，很短 ，paper的全名為Kademlia: A Peer-to-peer Information System Based on the XOR Metric

Kad的想法很簡單，就是找出利XOR計算出任二點在Kad network上邏輯的距離，有了這個距離後，一個key就讓距離該key最近的K個node負責，同理，query時也是同時query距離該key最近的K個node，k是一個系統參數

Kad的paper中，他把NodeID和Key的space定為160bit，並且強調你可以認為Kad中的node是用類似random的方式產生，實際上，每個人實做或多或少都會修改，比如eMule的Kad就是使用128bit的space實做，而非paper中的160bit

有了NodeID後，Kad利用對NodeID和key使用xor計算出距離，這是xor的特性能夠保證結果唯一，xor具備以下特徵
若令d(a, b) = a xor b，則
d(a, a) = 0
對任意b!=a，則d(a, b) = d(b, a) != 0
且xor也有類似三角形兩邊之合大於第三邊的特質
d(a, b) + d(b, c) > d(a, c)

所以在Kad中，每個進入Kad network的人都會有一個160bit的NodeID，而每個object經過hash也會得到一個160bit的key
然後每一個node和key的距離就等於 distance between node and key = d(NodeID, key)，也就是NodeID xor key
然後，有檔案的人就把 pari存到距離key最近的k個node即可，也就是說找出k個和key distance最小的node，而要query的人就先找到離key最近的k個node，然後發出k個query，任何一個query有結果就可以p2p了，這樣可以達到parallel的效果以加速
整個Kad就像下圖所示





eMule的實做
eMule的Kad實做採用udp（BT也是），不同的是eMule是採用128bit(16Byte)的space，為什麼？
因為
1.eMule的NodeID剛好就是16Byte
2.eMule本來就是使用MD5來辨認file，而非檔名，而MD5 value剛好也是16Byte
於是一切就水到渠成，接下來Kad的實做就跟Kad的paper一樣了

但是由於eMule是對file content做MD5得到MD5 hash value(也就是key)，這樣會有個問題，沒有該檔案或是完整檔案的人沒法算出MD5，沒有key，就不能找到負責人，也就無法抓檔，這一點，除了透過論譠的ed2k連結來解決之外（eMule的ed2k連結中包合了檔名，檔案大小，以及MD5等欄位），還有另一種解法，也就是keyword search

簡單的說，keyword search要用Kad找兩次，第一次利用keyword找出要抓的檔案的MD5 hash，第二次才是找出哪些人有檔案

舉例來說，如果有一臺電腦a有一首歌the power of love.mp3，它的MD5為x，那麼他必需publish兩次，一次是file hash的publish，也就是的publish，另一次則是將file hash關聯到keyword

以the power of love中，關鍵字(keyword)有兩個，也就是power和love，假設power和love一樣做hash（看高興用什麼就用什麼，也可以padding再MD5）得到兩個key，分別為y和z，那麼a就必需將file hash關聯到keyword的 pair publish到離y和z的k個node上，只不過publish的value為(file name, file hash)，所以a會將和

於是今天我們想要抓the power of love這首歌，我們輸入the power of love給程式搜尋，程式判斷出keyword為power和love，同時算出key為y和z，做Kad query，離y和z最近的k臺電腦會傳回所有data，也就是file name和file hash的組合，程式再進行比對哪一組pair的file name等於the power of love，找到後就得到the power of love的file hash，有了file hash後於是就進入正常的kad流程了

keyword search中value必需包合file name是因為一個關鍵字會關聯到太多file name，所以必需再加入file name做篩選，比如說，power關鍵字可能還關聯到power supply，power point，power planet等相關檔名，而這些都會以power做關鍵字，所以value中才必需加入file name以做進一步的篩選

Kad的優缺點如下：
優點：
可平行處理
快速，paper 中證明只需要 (logn 取上高斯) + c 次就可找到，其中c是一個小的常數
缺點：
至少要認識一個Kad node才能進入Kad network，而該node就擔任bootstrap的角色
不平均的loading，雖然是達到把server的effort分散的效果，可是不保證loading是平均，舉例來說，若有人的NodeID剛好在某個熱門檔案的k個最近node的範圍內，那他的loading肯定會比某些只負責小檔案的node大很多

這是我present的ppt

Coolstreaming: Design, Theory, and Practice.ppt

這是李波在2005 infocom提出的coolstreaming system在加強後再撰寫的journal paper
這篇paper被刊登在2007 12月的IEEE Transaction on Multimedia
李波現在是香港科技大學的教授

他在2005提出的的coolstreaming是第一篇提出在p2p streaming system上使用data driven概念的paper，由於是第一篇，在這之後很多人都follow他的研究，講到topology，資工的人其實第一時間都會想到tree的架搆，但是tree根本就不適合用在p2p streaming，而data driven則打開了tree的桎梏，這種無序的topology就被命名為swarm，data driven說穿了不神奇，畢竟file based的p2p software如BT/eMule之類的就是data driven

現在的這篇journal paper則改進許多

他將peer定義成3種層次的關係，依序為member、partner、parent/child
一個client會收到固定大小的peer list並將其存到名單中，member是名單中的peer但沒有建TCP交換availability information，而partner就是有建TCP交換availability information的member，然後parent/child就是從partner中挑出來的，有真的傳出/收進sreaming data的peer了，所以顯然的，parent/child包含於partner，而partner又包含於member

他也觀察到原先pool based（BT like）的scheme無論是latency還是overhead都有點太大，latency會變長很直覺，而overhead則是per block的transmission都會有control message的overhead，畢竟每一個block都是要靠程式去拉回來的

可是若是改回push不就又變回tree的topology了嗎？於是他將stream分解成multiple substreams，分解的部份有點像是switch fabric的TDMA或是邏輯閘的Multiplexer，而接受的動作比較像是switch fabric的TDMA或是邏輯閘的DeMultiplexer

之後的一切改變都跟這個有關係了，於是一個stream就被分解成幾個substream，於是一個peer就變成他只需要決定跟哪一個peer要哪一個substream，而非要哪一個block，顯然的，第一，運算變簡單了，第二，control message變少了

他先將stream拆成固定大小的block，每個block都給個sequence number，由於是採用TCP，保證收到的block的順序是inorder的，所以顯然的，一個peer只需要告訴別人他substream的最新block的sequence number即可，於是有幾條substream，就只需要傳幾個sequence number，而用sequence number也比較好運算

他說他將本來的pure pull改進成hybrid pull and push scheme，我的理解是
一個peer (child)決定跟某個peer (parent)要哪個substream的動作是pull，因為是由要的人去跟人家拉回來的
而之後，被要的peer (parent)就一直將child要的substream主動送給他，這裡就是push了，這個部份就跟以前要一個block一個block去要差很多了

另外，他將選擇parent的權利留給child，所以一個parent從不obsolete一個child，而是由child來決定是否要obsolete一個parent
他引進了兩個threshold用來判斷是要obsolete一個parent，而這兩個threshold任何一個被違反那麼child就會決定obsolete他的parent，這兩個threshold分別是Ts和Tp
我的感覺是
Ts就是用來判斷child自己收到的substream的速度是否一致，所以Ts就是在child自己的substream之間比較
Tp就是用來判斷child的某個parnet是否落後其他partner太多的，所以Tp就是parent與自己的所有partner比較
在網路中最難判斷的就是一個peer的上傳頻寬是否足夠，他現在導入了這個機制雖然算出的是相對的結果，不過我覺得這個結果就夠用了，因為，網路的環境太過複雜，頻寬從來就不是固定值，所以不能夠被算出來，這種機制很適合實做的p2p streaming system參考

於是這個機制就可以讓這個p2p system變成self organized system，而self organized又是決定p2p system的scale的關鍵，因為self organized 就可以decentralized，而decentralized後p2p的scale才能變大

整個paper到這裡就差不多了，剩下的就是他證明他這樣設計的p2p overlay會是converge to stable
老實說這一段最關鍵的那個公式我看不懂，他說We can model peer adaptation by a continuous time branching process，很遺憾的，我不知道什麼是continuous time branching process，於是我就沒法理解為什麼他可以直接跳出那個結果，不過這並不防礙這是一篇優秀的實做的系統的paper的事實

後面的部份就是看圖說故事了，沒什麼

這篇paper值得一看

這是我present的ppt

A Simple Model for Analyzing P2P Streaming Protocols.

這篇paper是由香港中文大學的(Dah Ming Chiu)邱達民和他的學生發表在ICNP 2007上

paper的名稱就是
A Simple Model for Analyzing P2P Streaming Protocols

這篇paper的重點就是先算出一個model來evalute p2p streaming protocol的chunk selection strategy的performance
而model既然已經算出來了，於是就可以在上面代換不同的chunk selection strategy去評估不同的strategy的performance，然後做比較
當然，他還有設計自己的strategy，不過就是把兩種strategy混合而已，所以他的strategy就叫mixed

model是以buffer的觀點去看，最後算出不同buffer位置的probabiliy distribution
當然，model的過程中做了很多跟現行p2p streaming protocol不合理的假設，也就是說，其假說的東西在真實的環境是不可行的，不過如果不這樣假設，他就算不出來了，所以標題也說了，A Simple Model
然後他提出兩種model，一個是discrete的model，另一個是continuous的model，最後再跑一個simulation去比較

他說就他所知，他是第一個提出model來evaluate p2p streaming protocol的performance的paper，就我所知，好像也是這樣
因為p2p中peer一定是heterogeneous，而paper如果假設是homogeneous，那就不合理，可是若不假設成homogeneous，那又算不出來

paper中到discrete的model之前，都很合理，值得參考，從continuos model開始，就有點奇怪了，最詭異的是將discrete的model轉成continuos model的方法
continuos model那一段真的很難看，我自己是懷疑他有寫錯，不過也有可能是我數學功力太弱，沒法理解他的算法

model完之後就是看圖說故事了，這就沒什麼好說的

這是我present的ppt

關於"An Alliance Based Peering Scheme for P2P Live Media Streaming"的報告

這篇paper是發表在2007 IEEE TRANSACTIONS ON MULTIMEDIA的paper
其key idea很好玩，雖然只有simulation，沒有implementation，也不知道可不可行，可是idea非常新就是了
P2P中最討厭的就是leecher（指只下載不上傳的行為者），理論上，這篇paper的idea似乎可以剋制這種人
其key idea比較像是電影中，四個人各持有1/4的藏寶圖，若想要找到寶藏，則每個人都要貢獻出自己手上的那一份，否則就找不到寶藏

在論文中，p2p是由一個一個的alliance組成的，一個peer可以參與很多個alliance

而他的中心思想就是，將一個單位的data均分後，將均分後更小的單位的資料給在alliance中的其他人各發一份出去，之後他就不再發出去，其他人由餘只有一個等份，且原先傳給他的人不再上傳，想要獲得完整的一單位，就必須跟其他人交換，這就達到了強迫上傳的目的

舉例來說，若一個alliance(命名為X)由5個人組成，分別是a、b、c、d、e，假設a從別的alliance收到一單位的data，這他所參與的這個alliance X的其他人還沒有這份data，所以他必須在alliance X中散佈，因為alliance有4個其他人沒有(扣掉他自己)，於是他將此單位的data均分成4單位，再將此4單位對bcde各散佈一份，於是bcde都各只得1/4，想要全部就要跟其他人交換，為什麼說交換？因為你有的別人的一定沒有，反之亦然，所以在你將1/4給別人時，你同時也會希望別人將他那1/4給你

那萬一有人不給怎麼辦？

第一：這個人常犯的話，最後就會被踢出這個alliance，再找出其他人來遞補他的位址
第二：由於所有alliance的人數一樣，所以每個單位切成的小單位都一樣，若有人不給，大家都會缺他的那一塊，但由於每個人都可以參加好幾個alliance，所以還是有機會從別的地方得到缺的那一小塊，他再和其他人交換即可

這是我用來present的ppt

關於"Packet Classification on Multiple Fields"的報告

在網路的應用上常需要對封包分類，為封包分類的目的有很多，通常目的是為了有不同的service
為封包分類之所以不能快的原因是因為你想要用多少欄位來分類，你就必需查多少次的表(table lookup)，而查表除了用硬體的TCAM能達到O(1)的時間外，用軟體的速度最快也只是O(log n)

在封包的分類上通常是時間和空間的tradeoff，理論上，只要你的記憶體夠大，那麼你可以在一次memory access之後就得到分類結果，完全不需要考慮演算法這種東西，比如說，若要分類的packet header 欄位寬度總合為120bit，那麼你可以建一張2^120大小的表格，然後填入規則，然後在packet到達後，直接用120bit的欄位當index去在取表格，從查表結果就可以知道這個packet該分成哪一類，該採取什麼動作

一般來說，速度快的演算法秏記憶體大，秏記憶體小的演算法速度慢，那麼是不是存在一種演算法可以達到平衡？即，速度讓人滿意，而秏的記憶體空間也可以讓人接受

我想，Packet Classification on Multiple Fields應是可以讓人接受的solution，
Packet Classification on Multiple Fields是sigcomm99的paper，距今快有十年了，paper本身寫得不是那麼容昜讓人看懂(坦白說，我覺得他演算法的psudo code那裡有地方寫錯)，不過Idea很好，Idea 簡單講就是利用分類規則之間的相似性，將相同結果的規則算做一類

就結果來看，他可以在使用120bit寬度資料做分類時，只需要9次的記憶體存取(memory access)以及3次的計算就可以完成分類了，速度算很快了，畢竟，查表(table lookup)跟記憶體存取（memory access）這120bit的資料分別是src ip(32), dst ip(32), L4 proto & flags, L4 src port(16), L4 dst port(16), ToS(8)

這篇paper也不是沒缺點，缺點就是
建表的時間無法預測
建表時用到的暫在記憶體大小無法預測
建完表的表格大小也無法預測

不過這些缺點對你來講不甚重要的話，例如，規則不常更動（即不常建表），device的其它功能記憶體需求沒有那麼緊（即，有足夠的記憶體空間留給演算法建表），那麼這篇paper的Idea就很有價值

這是我用來present的power point file

NS2 2.31的安裝心得

因為需要用到NS2，目前可以下載的版本是ns2-2.31，然而網路上的安裝教學都只有到2.27，在成功的安裝2.31後，我就野人獻曝一下

事實上，我一開始是按照網路上的教學在windows下安裝ns2-2.27的，然而不得不說，在網路下安裝ns2實在是一件痛苦的過程，因為要先安裝Cygwin，而在安裝Cygwin時又要去手動選擇安裝一堆套件，因為Cygwin沒有select/install all之類的選項，而Cygwin又只提供Online Installer，也就是說，所有套件都是要在安裝時下載，而它的Installer在選擇從哪下載時，又不能使用文字選取，也就是說我雖然在學網下，我也知道NTU以及NCTU都在選單內，然而我只能使用眼睛在那一串長長的Ftp list中尋找這兩個Ftp site，然後，就等Cygwin安裝完

在經過一堆時間後，Cygwin終於安裝後，接下來終於要安裝NS2了，下載NS2後需要compile，在Cygwin下compile的速度只能說，慢！

不管如何，我Cygwin和Cygwin下的NS2安裝了好幾次（第一次應該是Cygwin的X-server沒有裝好，所以導致我NS2跑起來沒有畫面，之後又陸陸續續因為各種原因，裝的不是很順利）

而學弟的一席話點話點醒了我，之所以用cygwin是因為我主要的工作環境是在windows下

但是在windows下並不是只有cygwin一個solution

我最後採取了先裝VMWare，然後裝一個VMOS：RedHat FC6，然後在真正的Linux下安裝NS2

沒辦法，Cygwin實在太慢了，透過這樣的solution在linux下ns2 compile起來還蠻快的

而之所以要寫這一篇文章的原因是因為網路上的教學文章都只有教ns2 2.27的安裝，而這一次我裝的是2.31，有一些東西和2.27不同，因此我在這一篇寫出來，希望可以減低有幸看到這一篇文章的人的痛苦

NS2在Linux下的安裝和Windows下的Cygwin大同小異，網路上很多文章在教了，這裡稍微介紹一下就好，重點還是放在裝好之後的設定

以下的教學以Linux為主，Cygwin照表操課就好，而不管Linux還是Cygwin，你都必須要有一個裝好的Linux/Windows，若Linux不知道要安裝什麼module，則一開始安裝時選全部安裝即可，我裝的是FC6，算滿舊的，應該比FC6新的Linux都沒問題才對，Cygwin的部份請參考柯志亨老師的網頁

1.下載ns2 all at once到家目錄(home directory)：ns-allinone-2.31.tar.gz (released Mar 10, 2007)
2.解開它，tar zxvf ns-allinone-2.31.tar.gz
3.安裝它，cd ns-allinone-2.31，./install（中間需要按y確定才會往下走）

ns2到這裡為止算安裝完成了，裝完後它會告訴你需要設定一些環境變數才能跑，因此你需要編輯.bashrc，若使用vi，則在bash下，vi ~/.bashrc，若欲使用linux dektop，則需顯示隱藏檔才能看得到.bashrc並編輯它，在# User specific aliases and functions這一行下面，加入以下這一段然後存檔
export NS_HOME=`pwd`/ns-allinone-2.31

export PATH=$NS_HOME/tcl8.4.14/unix:$NS_HOME/tk8.4.14/unix:$NS_HOME/bin:$NS_HOME/ns-2.31:$PATH

export LD_LIBRARY_PATH=$NS_HOME/tcl8.4.14/unix:$NS_HOME/tk8.4.14/unix:$NS_HOME/otcl-1.13:$NS_HOME/lib:$LD_LIBRARY_PATH

export TCL_LIBRARY=$NS_HOME/tcl8.4.14/library


到這為止若沒有意外NS2應該已經裝好了，在ns 2.27的教學中會讓你以測試一個example來判斷ns2是否裝好，然而，由於ns 2.31的結構有改變，2.31的example實在太多，而我在2.31的目錄中也找不到2.27的那個example，不過後來我在NS by Example上有找到一個example可以測試，下載回來後在bash裡面執行
ns ns-simple.tcl
若出現下面這個畫面表示NS2安裝成功了，可以開始把玩NS2了