---
tags: 網路架構作業
---

# Libtrace實作(2)

## 項目
1. 以TimeStamp來設定觀測區間，並統計區間內資訊
2. 選出Entry表上的Top10並印出
3. 給定%數以上才顯示

## 結果

承接上一次的[Multistage Filter](https://hackmd.io/BhZ0UsR-QKKAqz1Os5MvlA)，並在裡面新增幾個功能。

### 1.conservative update

保守更新的目的是為了將Hash Counter中的值因為碰撞的關係所產生的誤差降低，因此我們採取此種更新策略。可以看到下圖中紅框的部份，我們在更新計數器內容前先計算了所有計數器中最小的值，並且將其設定為更新的上限，但是若原本計數器中的值就已經大於此值我們則直接增加計數值，因為這有可能是小Flow碰撞到大Flow位置。

Update_Limit = Minmum + payload_length //計數上限

if(Counter_value > Update_Limit) //判斷是否原本就超過技術上限
{
    Counter_value += payload_length
}
else
{
    Counter_value = Update_Limit
}

其中compare為巨集，當程式中有許多簡短的邏輯判斷可以用巨集實現，更改及執行效率都較佳

#define compare(a,b)(a>=b?b:a)


### 2.Timestamp 設定觀測區間

我們可以透過萃取以及紀錄封包中時戳的資訊來設定觀測區間，我們可以從老師所給的範例timedemo.c中看到簡易的時戳呼叫及使用方式。我們可以透過以下函式來取得封包中的時間戳

ts = trace_get_timeval(packet);

並透過簡易的邏輯判斷來設定起始時間，因為時間戳是使用==Unix時間戳==因此第一個封包並不會像wireshark看到的是相對時間會從0開始算，因此我們必須要將第一個封包的時間讀出並設定為起始時間。因此我們可以透過簡易邏輯

while(ts>Current_TimeInterval)
{
    顯示封包計算結果
    更新 Current_TimeInterval
}


在每個觀測區間結束後我們需要清空相關計數器，因此我們需要且一個初始化函式
在每一次統計結束後我就將計數器們清空

### 3.Top 10 Heavy Hitter

做這件事會讓我們要排序已被登記在表上的資訊，所以我們使用泡泡排序法，當然還有其它比較快速有效率排序方式可以使用，其中的swap也是用巨集來代替實際函數

而我們只使用一個表來紀錄已被登記的IP，因此我們需要有另一個函式來透過IP讀取計數器上面所記錄的Byte數，因保守取值的關係，我們只取計數器中最小的值


最後我們使用以下的函數來取出流量前10名的IP與Byte數，其中我們可以自己定義我們要的輸出方式，這邊利用了ncurses來做為顯示模板，並且在每個觀測區間結束時都呼叫這一個函數來顯示到當前為止的統計值。


### 4.給定顯示%數

我們在輸入參數時可以給定%數，要超過固定%數的才可以登到TOP10榜上。


### 輸出結果
在下圖中每個觀測區都會更新當前流量的前10名，並且打印出所傳輸的Bytes和消耗頻寬百分比。

以下指令可以列出 觀測區間為10秒 只顯示該區前消耗流量%數為3%以上的Flow

$ ./Finn_MultiStage_Filter ../trace/2minutes.erf 10 3