 |
服務品質路由與轉送之延展性的設計 |
申請人姓名：林盈達，許乃斌，黃仁竑 先生
中文發明摘要：
一種服務品質路由與轉送之延展性的設計，用以減低
用戶要求的被阻絕率，並達到服務品質路由時的規模延展
性。在此我們設計三種技術：(1)溢流式快取、(2)封包轉送
機制以及(3)兩階段式路由，可同時或獨自作用下，由系統
模擬的評估結果，我們可以發現此三種延展性技術設計確
比以一對送端及收端為粒度的轉送機制有較小的阻絕率；
且比以個別資料流為粒度的轉送機制需要較少的路徑計算
及儲存空間。此優點使得本設計更具有規模延展性。
申請專利範圍
1.一種服務品質路由與轉送之延展性的設計，使用一溢流式快取技術，其一快取可分成三部分：一P-快取區、一O-快取區以及一D-快取區，當服務品質要求的一資料或一控制封包進入一服務品質路由器時，控制封包繞送及資料封包轉送的過程分為下列步驟：
先以一封包標頭的一送、收網路協定(IP)位址、一送、收埠(PORT)號碼及一協定代號，區別出該資料或該控制封包；
若是該控制封包則傳給一控制模組處理，該控制模組檢視資料流狀態資料庫，若狀態顯示此封包屬於既有的資料流，
則更新其狀態，否則再檢視該P-快取區及一剩餘頻寬資料庫；
若是一盡力式資料封包，則藉由事先計算最短路徑、以收端為刻度的該D-快取區轉送至連接下一點的輸出埠；以及
若是一服務品質資料封包，則同時檢視該O-快取區、該P-快取區以及該D-快取區，若該O-快取區成功查得相關路徑資料，
則依該O-快取區指引轉送，否則依該P-快取區指引轉送，若該O-快取區和該P-快取區都檢視失敗，
則依原有該盡力式檢視D-快取區轉送。
2.如申請專利範圍第1項所述之服務品質路由與轉送之延展性的設計，其中再檢視該P-快取區及該剩餘頻寬資料庫必需進行下列步驟：
以封包標頭的送、收網路協定位址來索引P-快取區記錄，若索引成功，則根據封包的要求頻寬b來檢視剩餘頻寬資料庫中，由此路由器至收端路徑剩餘頻寬是否充裕，若是，便暫時保留頻寬給此新的資料流，並沿用現存路徑轉送至收端，若剩餘頻寬資料庫顯示剩餘頻寬不足時，由服務品質路徑計算模組參考線路狀態資料庫及剩餘頻寬資料庫計算出新的可行路徑σ，並將此資料流的路由決定溢流記錄於O-快取區，若仍無法由目前的網路資源計算出可行的服務品質路徑時，再拒絕此資料流進入網路的要求；以及
若P-快取區索引失敗，表示此為全新的送收位址配對要求，故由路徑計算模組為此送收位址計算出該路由器至收端的可行路徑σ，並將相關資訊記錄於P-快取區。
3.如申請專利範圍第1項所述之服務品質路由與轉送之延展性的設計，其中更包括同時使用一路由記號分類之封包轉送技術，其執行下列步驟：
當封包進入邊際路由器時，首先檢視標頭欄位資訊，若是控制封包則傳給控制模組處理，控制模組檢視資料流狀態資料庫，若狀態顯示此封包屬於既有的資料流，則更新其狀態，否則再檢視轉送快取O-快取區和P-快取區及剩餘頻寬資料庫，即以控制封包的標頭送收位址用來選取O-快取區和P-快取區中送收位址記錄中有足夠頻寬且為最小成本的轉送路徑π，然後依送收位址(source-destination)記錄列中所填滿的情形分成三種狀況討論；
當盡力式資料封包進入路由器，則藉由事先計算最短路徑、以收端為刻度的D-快取區轉送至連接下一點的輸出埠；以及
若是服務品質資料封包進入邊際路由器，根據先前為此資料流選定的類別，標記資料封包的路由記號後轉送，當此封包進入核心路由器，則以送收位址及路由記號同時索引O-快取區、P-快取區和D-快取區，若O-快取區或P-快取區成功則依指引轉送，否則依原有盡力式方式依D-快取區指引轉送。
4.如申請專利範圍第3項所述之服務品質路由與轉送之延展性的設計，其中三種狀況包括：
(1)送收位址記錄列內的分類資料若為"空白"，使得索引失敗，則呼叫服務品質路徑計算模組為此送收位址計算出該路由器至收端的可行路徑σ，並將此路徑決定記載於送收位址記錄列中，記錄屬於F的封包將由此路徑轉送，若無法計算出可行的服務品質路徑時，拒絕此資料流進入網路的要求；
(2)若送收位址記錄列的分類資料已被"填滿"，且所選的π能滿足控制封包所提之服務品質需求，則記錄屬於F的封包將由此π轉送，若π並不滿足服務品質需求，則拒絕此資料流進入網路的要求；以及
(3)最後的一種狀況，若送收位址記錄的分類資料為介於空與滿之間，亦呼叫服務品質路徑計算模組，將計算之路徑σ的成本與快取記錄所選π的成本做比較，若π成本較低，則記錄由π轉送此F的封包，若σ成本較低，則記錄由σ轉送此F的封包，並記載於送收位址間的快取記錄中。
5.如申請專利範圍第1項所述之服務品質路由與轉送之延展性的設計，其中央包括同時使用一路徑計算模組使用兩階段式路由技術，係指當封包到達一服務品質路由器時，視封包種類不同，執行下列步驟：
若是控制封包(如記載點s至點d要求網路提供頻寬b和延遲D等的資源預約協定的路徑訊息)，則由控制模組檢視資料流狀態資料庫(FSDB)，若此封包屬於既有的資料流，則更新其狀態，否則以送收位址(S-D)檢視P-快取區及剩餘頻寬資料庫；
若是盡力式資料封包，則藉由事先計算最短路徑、以收端為刻度的D-快取區轉送至連接下一點的輸出埠；以及
若是服務品質資料封包，則同時索引P-快取區和D-快取區，若P-快取區成功則依P-快取區指引轉送，否則依原有盡力式(Best-effort)索引D-快取區轉送。
6.如申請專利範圍第5項所述之服務品質路由與轉送之延展性的設計，其中以送收位址(S-D)檢視P-快取區包括執行下列步驟：
若P-快取區索引成功，且剩餘頻寬資料庫顯示路徑剩餘頻寬充裕，則沿用現存路徑轉送至收端，若剩餘頻寬不足，則拒絕此資料流進入網路的要求；以及
若P-快取區索引失敗，表此為新的送收位址配對要求，由路徑計算模組參考線路狀態資料庫(線路狀態資料庫)及剩餘頻寬資料庫，以兩階段式路由技術為此送收位址計算出該路由器至收端的可行路徑σ，並將相關資訊記錄於P-快取區。
7.如申請專利範圍第5項或第6項所述之服務品質路由與轉送之延展性的設計，其中路徑計算模組依下述兩階段決定路徑：
第一階段會根據線路狀態資料庫和軟式剩餘頻寬資料庫，嘗試預留較多的頻寬給此送收位址路徑，亦即為持續相同送收位址間的資料流先預留比原需求b還多的頻寬給此所得路徑σ1，其中須滿足路徑頻寬width(σ1)≧b+bmore的條件，其中bmore值可粗估並根據交通量調整之，此階段並將路由決定σ1填入轉送快取，軟式剩餘頻寬記錄於軟式剩餘頻寬資料庫；以及
若無法找到符合的路徑，便由第二階段依線路狀態資料庫、實際頻寬需求及實際剩餘頻寬實際剩餘頻寬資料庫資料庫，預留原需求b的頻寬給此所得路徑σ2，此階段並將路由決定σ2填入轉送快取及實際剩餘頻寬紀錄於實際剩餘頻寬資料庫資料庫，若還是無法由目前的網路資源計算出可行的服務品質路徑時，表示此網路已接近較重負載，只好拒絕此資料流進入網路的要求。
8.一種服務品質路由與轉送之延展性的設計，使用一路由記號分類之封包轉送技術，其執行下列步驟：
當封包進入邊際路由器時，首先檢視標頭欄位資訊，若是控制封包則傳給控制模組處理，控制模組檢視資料流狀態資料庫，若狀態顯示此封包屬於既有的資料流，則更新其狀態，否則再檢視轉送快取O-快取區和P-快取區及剩餘頻寬資料庫，即以控制封包的標頭送收位址用來選取O-快取區和P-快取區中送收位址記錄中有足夠頻寬且為最小成本的轉送路徑π，然後依送收位址(source-destination)記錄列中所填滿的情形分成三種狀況討論；
當盡力式資料封包進入路由器，則藉由事先計算最短路徑、以收端為刻度的D-快取區轉送至連接下一點的輸出埠；以及
若是服務品質資料封包進入邊際路由器，根據先前為此資料流選定的類別，標記資料封包的路由記號後轉送，當此封包進入核心路由器，則以送收位址及路由記號同時索引O-快取區、P-快取區和D-快取區，若O-快取區或P-快取區成功則依指引轉送，否則依原有盡力式方式依D-快取區指引轉送。
9.如申請專利範圍第8項所述之服務品質路由與轉送之延展性的設計，其中三種狀況包括：
(1)送收位址記錄列內的分類資料若為"空白"，使得索引失敗，則呼叫服務品質路徑計算模組為此送收位址計算出該路由器至收端的可行略徑σ，並將此路徑決定記載於送收位址記錄列中，記錄屬於F的封包將由此路徑轉送，若無法計算出可行的服務品質路徑時，拒絕此資料流進入網路的要求；
(2)若送收位址記錄列的分類資料已被"填滿"，且所選的π能滿足控制封包所提之服務品質需求，則記錄屬於F的封包將由此π轉送，若π並不滿足服務品質需求，則拒絕此資料流進入網路的要求；以及
(3)最後的一種狀況，若送收位址記錄的分類資料為介於空與滿之間，亦呼叫服務品質路徑計算模組，將計算之路徑σ的成本與快取記錄所選π的成本做比較，若π成本較低，則記錄由π轉送此F的封包，若σ成本較低，則記錄由σ轉送此F的封包，並記載於送收位址間的快取記錄中。
10.如申請專利範圍第8項所述之服務品質路由與轉送之延展性的設計，其中更包括同時使用一路徑計算模組使用兩階段式路由技術，係指當封包到達一服務品質路由器時，視封包種類不同，執行下列步驟：
若是控制封包(如記載點s至點d要求網路提供頻寬b和延遲D等的資源預約協定(RSVP)的路徑訊息)，則由控制模組檢視資料流狀態資料庫(FSDB)，若此封包屬於既有的資料流，則更新其狀態，否則以送收位址(S-D)檢視P-快取區及剩餘頻寬資料庫；
若是盡力式資料封包，則藉由事先計算最短路徑、以收端為刻度的D-快取區轉送至連接下一點的輸出埠；以及
若是服務品質資料封包，則同時索引P-快取區和D-快取區，若P-快取區成功則依P-快取區指引轉送，否則依原有盡力式(Best-effort)索引D-快取區轉送。
11.如申請專利範圍第10項所述之服務品質路由與轉送之延展性的設計，其中以送收位址(S-D)檢視P-快取區包括執行下列步驟：
若P-快取區索引成功，且剩餘頻寬資料庫顯示路徑剩餘頻寬充裕，則沿用現存路徑轉送至收端，若剩餘頻寬不足，則拒絕此資料流進入網路的要求；以及
若P-快取區索引失敗，表此為新的送收位址配對要求，由路徑計算模組參考線路狀態資料庫(LSDB)及剩餘頻寬資料庫，以兩階段式路由技術為此送收位址計算出該路由器至收端的可行路徑σ，並將相關資訊記錄於P-快取區。
12.如申請專利範圍第10項或第11項所述之服務品質路由與轉送之延展性的設計，其中路徑計算模組依下述兩階段決定路徑：
第一階段會根據線路狀態資料庫和軟式剩餘頻寬資料庫，嘗試預留較多的頻寬給此送收位址路徑，亦即為持續相同送收位址間的資料流先預留比原需求b還多的頻寬給此所得路徑σ1，其中須滿足路徑頻寬width(σ1)≧b+bmore的條件，其中bmore值可粗估並根據交通量調整之，此階段並將路由決定σ1填入轉送快取，軟式剩餘頻寬記錄於軟式剩餘頻寬資料庫；以及
若無法找到符合的路徑，便由第二階段依線路狀態資料庫、實際頻寬需求及實際剩餘頻寬實際剩餘頻寬資料庫資料庫，預留原需求b的頻寬給此所得路徑σ2，此階段並將路由決定σ2填入轉送快取及實際剩餘頻寬紀錄於實際剩餘頻寬資料庫資料庫，若還是無法由目前的網路資源計算出可行的服務品質路徑時，表示此網路已接近較重負載，只好拒絕此資料流進入網路的要求。
13.一種服務品質路由與轉送之延展性的設計，使用一路徑計算模組使用兩階段式路由技術，係指當封包到達一服務品質路由器時，視封包種類不同，執行下列步驟：
若是控制封包(如記載點s至點d要求網路提供頻寬b和延遲D等的資源預約協定的路徑訊息)，則由控制模組檢視資料流狀態資料庫(FSDB)，若此封包屬於既有的資料流，則更新其狀態，否則以送收位址(S-D)檢視P-快取區及剩餘頻寬資料庫；
若是盡力式資料封包，則藉由事先計算最短路徑、以收端為刻度的D-快取區轉送至連接下一點的輸出埠；以及
若是服務品質質料封包，則同時索引P-快取區和D-快取區，若P-快取區成功則依P-快取區指引轉送，否則依原有盡力式(Best-effort)索引D-快取區轉送。
14.如申請專利範圍第13項所述之服務品質路由與轉送之延展性的設計，其中以送收位址(S-D)檢視P-快取區包括執行下列步驟；
若P-快取區索引成功，且剩餘頻寬資料庫顯示路徑剩餘頻寬充裕，則沿用現存路徑轉送至收端，若剩餘頻寬不足，則拒絕此資料流進入網路的要求；以及
若P-快取區索引失敗，表此為新的送收位址配對要求，由路徑計算模組參考線路狀態資料庫(LSDB)及剩餘頻寬資料庫，以兩階段式路由技術為此送收位址計算出該路由器至收端的可行路徑σ，並將相關資訊記錄於P-快取區。
15.如申請專利範圍第13項或第14項所述之服務品質路由與轉送之延展性的設計，其中路徑計算模組依下述兩階段決定路徑：
第一階段會根據線路狀態資料庫和軟式剩餘頻寬資料庫，嘗試預留較多的頻寬給此送收位址路徑，亦即為持續相同送收位址間的資料流先預留比原需求b還多的頻寬給此所得路徑σ1，其中須滿足路徑頻寬width(σ1)≧b+bmore的條件，其中bmore值可粗估並根據交通量調整之，此階段並將路由決定σ1填入轉送快取，軟式剩餘頻寬記錄於軟式剩餘頻寬資料庫；以及
若無法找到符合的路徑，便由第二階段依線路狀態資料庫、實際頻寬需求及實際剩餘頻寬實際剩餘頻寬資料庫資料庫，預留原需求b的頻寬給此所得路徑σ2，此階段並將路由決定σ2填入轉送快取及實際剩餘頻寬紀錄於實際剩餘頻寬資料庫資料庫，若還是無法由目前的網路資源計算出可行的服務品質路徑時，表示此網路已接近較重負載，只好拒絕此資料流進入網路的要求。
16.如申請專利範圍第13項所述之服務品質路由與轉送之延展性的設計，其中更包括同時使用一溢流式快取技術，其快取可分成三部分：一P-快取區、一O-快取區以及一D-快取區，當服務品質要求的一資料或一控制封包進入一服務品質路由器時，控制封包繞送及資料封包轉送的過程分為下列步驟：
先以一封包標頭的一送、收網路協定位址、一送、收埠(PORT)號碼及一協定代號，區別出該資料或該控制封包；
若是該控制封包則傳給一控制模組處理，該控制模組檢視資料流狀態資料庫，若狀態顯示此封包屬於既有的資料流，則更新其狀態，否則再檢視該P-快取區及一剩餘頻寬資料庫；
若是一盡力式資料封包，則藉由事先計算最短路徑、以收端為刻度的該D-快取區轉送至連接下一點的輸出埠；以及
若是一服務品質資料封包，則同時檢視該O-快取區、該P-快取區以及該D-快取區，若該O-快取區成功查得相關路徑資料，則依該O-快取區指引轉送，否則依該P-快取區指引轉送，若該O-快取區和該P-快取區都檢視失敗，則依原有該盡力式檢視D-快取區轉送。
17.如申請專利範圍第16項所述之服務品質路由與轉送之延展性的設計，其中再檢視該P-快取區及一剩餘頻寬資料庫必需進行下列步驟：
以封包標頭的送、收網路協定位址來索引P-快取區記錄，若索引成功，則根據封包的要求頻寬b來檢視剩餘頻寬資料庫中，由此路由器至收端路徑剩餘頻寬是否充裕，若是，便暫時保留頻寬給此新的資料流，並沿用現存路徑轉送至收端，若剩餘頻寬資料庫顯示剩餘頻寬不足時，由服務品質路徑計算模組參考線路狀態資料庫及剩餘頻寬資料庫計算出新的可行路徑σ，並將此資料流的路由決定溢流記錄於O-快取區，若仍無法由目前的網路資源計算出可行的服務品質路徑時，再拒絕此資料流進入網路的要求；以及
若P-快取區索引失敗，表示此為全新的送收位址配對要求，故由路徑計算模組為此送收位址計算出該路由器至收端的可行路徑σ，並將相關資訊記錄於P-快取區。