鍊表處理裝置、鍊表處理方法及相關網絡交換的製造方法

2023-06-10 09:50:06 2

鍊表處理裝置、鍊表處理方法及相關網絡交換的製造方法
【專利摘要】本發明提供一種鍊表處理裝置、鍊表處理方法及網絡交換機。鍊表處理裝置包含存儲裝置以及鍊表控制器，鍊表控制器用於設置鍊表信息以及將鍊表信息寫入存儲裝置，以在存儲裝置中創建鍊表；其中鍊表包含多個節點，每一節點具有下一節點地址欄，鍊表信息包含數據模式，數據模式用於指示鍊表的結尾以及輔助信息，並且鍊表控制器將數據模式儲存到鍊表的鍊表尾的下一節點地址欄。本發明的鍊表處理裝置、鍊表處理方法及網絡交換機可提供共享鍊表尾架構，充分使用存儲空間。
【專利說明】鍊表處理裝置、鍊表處理方法及相關網絡交換機 【【技術領域】】
[0001] 本發明有關於鍊表數據結構（link list data structure)，更具體來說，有關於使 用鍊表的鍊表尾（link-tail)儲存數據模式（data pattern)的裝置和方法，其中數據模式 指示鍊表的結尾以及輔助信息（auxiliary information)。 【【背景技術】】
[0002] 網絡交換機（network switch)是連結不同網絡設備的計算機網絡設備。舉例來 說，網絡交換機接收與其連接的第一網絡設備所產生的輸入封包，並將從已接收的封包導 出的修改後封包或者未修改封包僅傳輸至第二網絡設備，其中所述已接收的封包原本是由 第二網絡設備接收。一般來說，已接收的封包由多個數據塊組（datachunk)(亦即，多個單 元數據（cell data))組成。因此，從已接收的封包中導出的封包也由多個數據塊組（亦即， 多個單元數據）組成。網絡交換機具有用於緩衝導出封包的數據塊組的封包緩衝器。然而， 封包緩衝器中的空閒可用存儲空間並不能確保是連續的。因此，導出封包的多個數據塊組 在被儲存入封包緩衝器中後，可能隨機位於封包緩衝器中。
[0003] 為有效管理封包緩衝器中的導出封包的多個數據塊組，網絡交換機可使用鍊表。 基於鍊表數據結構，鍊表包含順序關聯的多個節點，其中每一節點與封包緩衝器中的導出 封包的多個數據塊組之一相關，並且具有下一節點地址欄，用於儲存下一節點的地址。關 於鍊表的鍊表尾節點，由於鍊表尾節點是鍊表的最後一個節點，並不存在與鍊表尾節點級 聯的下一節點。故在常規設計中，鍊表尾節點的下一節點地址欄將儲存指向空地址（null address)的空指針（null pointer),從而在封包傳輸期間，當封包傳輸電路讀取鍊表時，告 知封包傳輸電路鍊表的結尾。由於鍊表尾節點指向"零"（null)，鍊表尾的下一節點地址欄 被浪費掉了。 【
【發明內容】
】
[0004] 有鑑於此，本發明特提供以下技術方案：
[0005] 本發明實施例提供一種鍊表處理裝置，包含存儲裝置以及鍊表控制器。鍊表控制 器用於設置鍊表信息以及將鍊表信息寫入存儲裝置，以在存儲裝置中創建鍊表；其中鍊表 包含多個節點，每一節點具有下一節點地址欄，鍊表信息包含數據模式，數據模式用於指示 鍊表的結尾以及輔助信息，以及鍊表控制器將數據模式儲存到鍊表的鍊表尾節點的下一節 點地址欄。
[0006] 本發明實施例另提供一種鍊表處理方法，包含設置鍊表信息，其中鍊表信息包含 數據模式，數據模式用於指示鍊表的結尾以及輔助信息，以及將鍊表信息寫入存儲裝置，以 在存儲裝置中創建鍊表；其中鍊表包含多個節點，每一節點具有下一節點地址欄，以及述數 據模式被寫入鍊表的鍊表尾節點的下一節點地址欄。
[0007] 本發明實施例又提供一種網絡交換機，包含封包接收電路、鍊表處理裝置以及封 包傳輸電路。封包接收電路用於接收輸入封包，以及從已接收的輸入封包中導出多個第一 數據塊組；鍊表處理裝置，包含存儲裝置以及鍊表控制器，鍊表控制器用於將鍊表信息寫 入存儲裝置，以在存儲裝置中創建鍊表，其中鍊表包含與多個第一數據塊組分別相關的多 個節點，每一節點具有下一節點地址欄，鍊表信息包含數據模式，數據模式用於指示鍊表的 結尾以及輔助信息，以及鍊表控制器將數據模式儲存到鍊表的鍊表尾節點的下一節點地址 欄；封包傳輸電路用於依據鍊表從多個第一數據塊組導出輸出封包的多個第二數據塊組， 以及傳輸輸出封包，其中當產生輸出封包時，封包傳輸電路參考由鍊表尾節點指示的輔助 信息執行封包處理。
[0008] 以上所述的鍊表處理裝置、鍊表處理方法及網絡交換機可提供共享鍊表尾架構， 充分使用存儲空間。 【【專利附圖】

【附圖說明】】
[0009] 圖1是依據本發明一實施例的網絡交換機的示意圖。
[0010] 圖2是依據本發明一實施例的圖1中的網絡交換機的運行方案示意圖。
[0011] 圖3是圖1中的封包緩衝器及存儲裝置的數據存儲狀態的示意圖。
[0012] 圖4為依據本發明的另一實施例的網絡交換機的示意圖。
[0013] 圖5為依據本發明一實施例的產生自鍊表控制器的數據模式的示意圖。
[0014] 圖6是依據本發明一實施例的圖4中的網絡交換機的運行方案示意圖。
[0015] 圖7是圖4中的封包緩衝器及存儲裝置的數據存儲狀態的示意圖。 【【具體實施方式】】
[0016] 在說明書及權利要求書當中使用了某些詞彙來指稱特定的組件。所屬領域中的 技術人員應可理解，製造商可能會用不同的名詞來稱呼同樣的組件。本說明書及權利要求 書並不以名稱的差異來作為區分組件的方式，而是以組件在功能上的差異來作為區分的基 準。在通篇說明書及權利要求書當中所提及的「包含」是開放式的用語，故應解釋成「包含 但不限定於」。另外，「耦接」一詞在此包含任何直接及間接的電氣連接手段。因此，若文中 描述第一裝置耦接於第二裝置，則代表第一裝置可直接電氣連接於第二裝置，或透過其它 裝置或連接手段間接地電氣連接至第二裝置。
[0017] 本發明主要設想之一是使用鍊表尾節點的下一節點地址欄來儲存輔助信息。因 此，除指示鍊表的結尾之外，鍊表尾節點也提供與輸出封包的封包處理相關聯的附加信息 (additional information)(例如，控制信息或者數據信息）。簡言之，本發明提供共享鍊表 尾架構，以充分使用由鍊表尾節點佔據的存儲空間，從而節約原被要求用於緩衝封包處理 相關信息（例如，控制信息或者數據信息）的附加存儲空間。共享鍊表尾架構進一步的細 節描述如下。
[0018] 圖1是依據本發明一實施例的網絡交換機的示意圖。網絡交換機100是網際網路/ 內部網設備，並且包含封包接收電路102,耦接於封包接收電路102的鍊表處理裝置104,耦 接於封包接收電路102以及鍊表處理裝置104的封包傳輸電路106,以及耦接於封包接收 電路102及封包傳輸電路106之間的封包轉發（packet forward)電路108。封包接收電路 102包含接收單元112、封包緩衝器114以及緩衝器管理單元118。鍊表處理裝置104包含 鍊表控制器122以及存儲裝置124。請注意，圖1中僅繪示了與本發明相關的元件。在實踐 中，網絡交換機100可能包含附加的元件以支持其他功能。接收單元112用於接收產生自 源網絡設備的輸入封包P_IN，以及自接收到的輸入封包P_IN導出多個數據塊組（單元數 據）116,其中源網絡設備連接於網絡交換機100。舉例來說，輸入封包P_IN由多個數據塊組 116組成，其中數據塊組116由接收單元112相繼接收，並且每一數據塊組116攜帶一個單 元數據。緩衝器管理單元118用於管理封包緩衝器114的緩衝器存儲空間。舉例來說，緩 衝器管理單元118為已接收封包數據塊組分配封包緩衝器114中的空閒存儲空間，並且釋 放封包緩衝器114中由已傳輸封包數據塊組所佔據的已使用存儲空間。因此，當接收單元 112接收輸入封包P_IN的數據塊組時，緩衝器管理單元118在封包緩衝器114中動態分配 一空閒存儲空間，且接收單元112將已接收的數據塊組儲存於分配的空閒存儲空間中。在 本實施例中，在已接收的數據塊組被儲存於封包緩衝器114中之前，已接收的數據塊組未 作任何修改。
[0019] 緩衝器管理單元118進一步傳輸已分配的存儲空間的位置信息至鍊表控制器 122。鍊表控制器122也具有儲存管理功能。基於已分配的存儲空間的位置信息，鍊表控制 器122在存儲裝置124中分配一個存儲空間，並且將信息儲存入已分配的存儲空間以創建 鍊表的一個節點126,其中已分配的存儲空間儲存數據塊組，節點126與儲存於封包緩衝器 114中的已接收的數據塊組相關。節點126包含數據欄與下一節點地址欄。在本實施例中， 儲存於封包緩衝器114中的多個數據塊組116以及存儲裝置124中創建的鍊表的多個節點 126之間存在一對一的映射關係。換言之，自輸入封包P_IN導出並儲存於封包緩衝器114 中的多個數據塊組分別與創建並儲存於存儲裝置124中的鍊表的多個節點相關聯。因此， 通過將鍊表從鍊表頭（link-head)節點（亦即，第一節點）穿越（traversing)至鍊表尾節 點（亦即，最後節點），封包傳輸電路106可有序取出隨機儲存於封包緩衝器114中的數據 塊組以獲取輸出封包P_〇UT的多個數據塊組。此外，封包轉發電路108從接收單元112獲 取輸入封包P_IN的封包數據，並提供封包目的信息至封包傳輸電路106。隨後，封包傳輸電 路106將輸出封包P_0UT傳輸至連接於網絡交換機100的目的網絡設備。
[0020] 輸出封包？_0瓜的數據塊組成功傳輸至目的網絡設備後，封包緩衝器114中由該 已傳輸的數據塊組所佔據的已使用過的存儲空間可被釋放。從而，緩衝器管理單元118將 原本被分配給輸出封包P_〇UT的該已傳輸的數據塊組的存儲空間視為一空閒存儲空間。
[0021] 如圖1所示，鍊表節點架構具有數據欄（data field)及下一節點地址欄。根據實際 設計考慮，每一節點126的數據欄可以是空的。在本實施例中，每一節點126的下一節點地 址欄被設計為用來記錄下一節點的地址。從而，儲存在存儲裝置124中的鍊表可被配置為 一個節點連接於單一的下一個節點。鍊表控制器122設置儲存於存儲裝置124中的鍊表信 息INF UST，其中鍊表信息INFUST可包含數據模式INF。，數據模式INF。被配置為指示鍊表的 結尾以及輔助信息（例如，控制信息）。鍊表控制器122將數據模式INF。儲存入鍊表的鏈 表尾節點的下一節點地址欄中。以此種方式，當封包傳輸電路106從鍊表尾節點讀取出數 據模式INF。時，封包傳輸電路106不僅識別出當前節點為鍊表的最後節點，同時也獲得了 控制信息。當產生輸出封包P_〇UT時，封包傳輸電路106參考鍊表尾節點指示的輔助信息 (例如，控制信息）執行封包處理。
[0022] 如圖1所示，存儲裝置124至少包含位於第一地址範圍的第一存儲空間127及位 於第二地址範圍的第二存儲空間128。因此，並非存儲裝置124的所有存儲空間均用於儲 存鍊表。鍊表控制器122配置為將任一鍊表僅儲存於第一存儲空間127。請注意數據模式 INFC並非指向存儲裝置124的地址範圍（例如，第一地址範圍和第二地址範圍）之外的空 地址的空指針。在本實施例中，數據模式INF C具有與第二存儲空間128內多個地址之一 相同的位模式（bit pattern)。亦即，與使用空地址（亦即，不存在於存儲裝置124中的地 址）的空指針相反，數據模式INFC被設置為與存儲裝置124中的一個未使用地址相同的位 模式。由於封包傳輸電路106知曉任一鍊表應儲存於第一存儲空間127中，當儲存於下一 節點地址欄的位模式超出第一存儲空間127的第一地址範圍時，封包傳輸電路106可以容 易的識別出鍊表尾節點。此外，當偵測到儲存於鍊表節點的下一節點地址欄的位模式是位 於第二存儲空間128的第二地址範圍內的未使用地址時，封包傳輸電路106更從鍊表節點 中獲取控制信息。舉例來說，控制信息用於指示輸入封包P_IN與鍊表尾節點相關的數據塊 組的接收錯誤。
[0023] 請一併參考圖2和圖3。圖2是依據本發明一實施例的圖1中的網絡交換機100 的運行方案示意圖。圖3是圖1中的封包緩衝器114及存儲裝置124的數據存儲狀態的示 意圖。舉例來說，但並非本發明的限制，輸入封包P_IN是產生自連接於網絡交換機100的 源網絡設備的直通（cut-through)封包。故在輸入封包？_預所有的數據塊組（單元數據） 被接收之前，網絡交換機100便開始將輸出封包P_〇UT的數據塊組（單元數據）傳輸至連 接於網絡交換機100的目的網絡設備。如圖2所示，封包接收電路102的接收單元112順 序接收輸入封包P_IN的數據塊組（單元數據）RXD0_RXD4。當接收單元112接收第一單元 數據RXD0,並且封包緩衝器114在地址5,10, 7和12具有空閒存儲空間時，接收單元112 將第一單元數據RXD0儲存於位於封包緩衝器114的地址5的存儲空間，而鍊表控制器122 因此使用位於存儲裝置124的地址5的存儲空間創建鍊表頭節點。第一單元數據RXD0被 儲存於封包緩衝器114之後，封包傳輸電路106立即自封包緩衝器114讀取第一單元數據 RXD0,並將其作為輸出封包P_0UT的第一數據塊組（單元數據）TXD0傳輸（亦即，RXD0 = TXD0)。
[0024] 當接收單元112接收第二單元數據RXD1，且封包緩衝器114在地址10, 7和12具 有空閒存儲空間時，接收單元112將第二單元數據RXD1儲存於位於封包緩衝器114的地址 10的存儲空間，而鍊表控制器122因此使用位於存儲裝置124的地址10的存儲空間創建節 點0,並將地址10儲存入鍊表頭節點的下一節點地址欄，使得鍊表頭節點連結於節點0。類 似地，在第二單元數據RXD1被儲存於封包緩衝器114之後，封包傳輸電路106立即自封包 緩衝器114讀取第二單元數據RXD1，並將其作為輸出封包P_0UT的第二數據塊組（單元數 據）TXD1 傳輸（亦即，RXD1 = TXD1)。
[0025] 關於之後的兩個單元數據RXD2和RXD3,接收單元112及鍊表控制器122同樣執 行上述操作。故第三單元數據RXD2儲存於封包緩衝器114的地址7的存儲空間，而第四單 元數據RXD3儲存於封包緩衝器114的地址12的存儲空間。在存儲裝置124中，節點1和 2分別儲存於地址7和12,其中節點1連結於節點2,且節點2連結於節點3。
[0026] 當接收單元112接收第五單元數據RXD4時，封包緩衝器114沒有可用於緩衝第五 單元數據RXD4的空閒存儲空間。故由於缺乏足夠存儲資源而發生寫錯誤。接收單元112不 將接收到的第五單元數據RXD4儲存於封包緩衝器114中。鍊表控制器122設置寫錯誤信 息作為數據模式INF。，並將數據模式INF。寫入節點2的下一節點地址欄，使得節點2被設置 為鍊表尾節點，同時指示輸入封包P_IN的數據塊組的接收錯誤（亦即，第五單元數據RXD4 的接收錯誤）。當封包傳輸電路106自節點2的下一節點地址欄讀取數據模式INFC時，將 得知封包被截斷。在本實施例中，封包傳輸電路106將一預設錯誤數據塊組TXD4附加至輸 出封包P_OUT。當位於目的網絡設備的封包接收電路接收產生自網絡交換機100的輸出封 包P_OUT時，其將丟棄這個不完整的封包。
[0027] 在上述實施例中，儲存於鍊表尾節點的下一節點地址欄中的數據模式用於指示鏈 表的結尾以及輔助信息，其中輔助信息為控制信息。然而，其僅用作說明的目的。在其他替 代設計中，儲存於鍊表尾節點的下一節點地址欄中的數據模式可用於指示鍊表的結尾以及 輔助信息，其中輔助信息為數據信息。
[0028] 請參考圖4,其為依據本發明的另一實施例的網絡交換機的示意圖。網絡交換機 400的結構類似於圖1中所示的網絡交換機100。網絡交換機100和網絡交換機400的主 要不同在於網絡交換機400更包含校驗和處理器408,鍊表處理裝置404的鍊表控制器422 用於將數據模式INF D，包含數據信息（例如產生自校驗和處理器408的校驗和Das)，儲存 至鍊表的鍊表尾節點的下一節點地址欄，而封包傳輸電路406基於讀取於鍊表尾節點的校 驗和D CKS執行校驗和計算，以驗證輸出封包P_0UT'的正確性。舉例來說，校驗和處理器408 計算自輸入封包？_預'的原始數據塊組（單元數據）導出並儲存於封包緩衝器114中的修 改的數據塊組（單元數據）的校驗和，其中自輸入封包P_IN'導出並儲存於封包緩衝器 114中的數據塊組與創建並儲存於存儲裝置124中的鍊表的節點相關。關於封包傳輸電路 406，當產生輸出封包P_0UT'時，封包傳輸電路406參考鍊表尾節點指示的輔助信息（例如， 數據信息）執行封包處理（例如，校驗和驗證）。
[0029] 如上所述，存儲裝置124至少具有位於第一地址範圍的第一存儲空間127及位於 第二地址範圍的第二存儲空間128。類似地，由於並非存儲裝置124的所有存儲空間均用於 儲存鍊表，鍊表控制器422配置為將任一鍊表僅儲存於第一存儲空間127。請注意數據模式 INF D並非指向存儲裝置124的地址範圍（例如，第一地址範圍和第二地址範圍）之外的空 地址的空指針。請參考圖5,其為依據本發明一實施例的產生自鍊表控制器422的數據模式 INF D的示意圖。在本實施例中，數據模式INFD具有較高有效位（more significant bit，簡寫 為MSB)部分以及較低有效位（less significant bit，簡寫為LSB)部分，其中LSB部分作為 校驗和，MSB部分作為校驗值的詞頭（prefix)。更具體來說，鍊表控制器422設置數據模式 INF D的MSB部分來指示鍊表的結尾，並用產生自校驗和處理器408的校驗和DeKS設置LSB部 分。假定下一節點地址欄的大小為8位。若鍊表尾節點的下一節點地址欄被8位的校驗和 滿載，由於8位校驗和的數據模式可能與第一地址範圍內的多個8位地址其中之一的數據 模式相同，封包傳輸電路406可能不能夠區分第一存儲空間127的第一地址範圍內的8位 已使用地址以及由校驗和處理器408產生的8位校驗和。因此，詞頭被特別設計來指示鏈 表的結尾。舉例來說，詞頭有2位，而校驗和為6位而非8位。考慮下述情況，其中第一存 儲空間127的第一地址範圍從0x00000000至0x10000000,第二存儲空間128的第二地址範 圍從0x10000001至0x111 111 11。則鍊表中每一節點的已使用地址將為自地址0x00000000 至0x10000000中的一個。由於6位校驗和可由自0x000000至0x111111的多個位模式中 的一個來設置，2位的詞頭被故意設置為0x11以確保數據模式INF D具有不同於第一地址範 圍（亦即，0x00000000至0x10000000)內的任一地址的8位位模式。換言之，鍊表控制器 422將數據模式INFD的MSB部分設置為不同於第一存儲空間127的第一地址範圍內的每一 地址的共址MSB部分。
[0030] 請一併參考圖6和圖7。圖6是依據本發明一實施例的圖4中的網絡交換機400 的運行方案示意圖。圖7是圖4中的封包緩衝器114及存儲裝置124的數據存儲狀態的示 意圖。舉例來說，但並非本發明的限制，輸入封包P_IN'是產生自連接於網絡交換機400的 源網絡設備的存儲轉發（store-and-forward)封包。故在輸入封包？_預'所有的數據塊組 (單元數據）被接收之後，網絡交換機400開始將輸出封包P_0UT'的數據塊組傳輸至連接 於網絡交換機400的目的網絡設備。如圖6所示，封包接收電路102的接收單元112順序接 收輸入封包P_IN'的數據塊組（單元數據）RXD0_RXD3,並將對應的修改後的數據塊組（單 元數據）RXD0' -RXD3'順序儲存於封包緩衝器114的地址5,10, 7和12的存儲空間中。
[0031] 舉例來說，可通過修改輸入封包P_IN'的原始數據塊組的單元數據來產生修改後 的數據塊組，其中單元數據包含源IP位址，TCP源埠等。
[0032] 當修改後的第一單元數據RXD0'被儲存於位於封包緩衝器114的地址5的存儲空 間時，鍊表控制器422使用位於存儲裝置124的地址5的存儲空間創建鍊表頭節點。當修 改後的第二單元數據RXD1'被儲存於位於封包緩衝器114的地址10的存儲空間時，鍊表控 制器422使用位於存儲裝置124的地址10的存儲空間創建節點0,並將地址10儲存入鍊表 頭節點的下一節點地址欄，使得鍊表頭節點連結於節點0。當修改後的第三單元數據RXD2' 被儲存於位於封包緩衝器114的地址7的存儲空間時，鍊表控制器422使用位於存儲裝置 124的地址7的存儲空間創建節點1，並將地址7儲存入鍊表頭節點的下一節點地址欄，使 得節點〇連結於節點1。當自輸入封包P_IN'的最後單元數據導出的修改後的第四單元數 據RXD3'被儲存於位於封包緩衝器114的地址12的存儲空間時，鍊表控制器422使用位於 存儲裝置124的地址12的存儲空間創建節點3作為鍊表尾節點。
[0033] 當接收單元112將修改後的數據塊組（單元數據）RXDO' -RXD3'順序存入封包緩 衝器114中時，接收單元112也將修改後的數據塊組（單元數據）RXDO' -RXD3'順序送至 校驗和處理器408。以此種方式，接收到一個修改後的數據塊組（單元數據），校驗和處理 器408計算並更新一次校驗和。因此，當校驗和處理器408接收到修改後的第四單元數據 RXD4'時，校驗和處理器408產生自輸入封包P_IN'導出的所有修改後的數據塊組（單元數 據）的最終校驗和D as。當自輸入封包？_預'的最後一個單元數據導出的修改後的第四單 元數據RXD4'被儲存於位於封包緩衝器114的地址12的存儲空間時，鍊表控制器422用校 驗和D eKS來設置數據模式INFD的LSB部分，並將數據模式INFD儲存於存儲裝置124的地址 12的鍊表尾節點的下一節點地址欄中，其中數據模式INF D包含由詞頭"0x11"設置的MSB 部分和由校驗和DCKS設置的LSB部分。
[0034] 由於輸入封包P_IN'所有的數據塊組（單元數據）RXD0-RXD3均已被封包接收電 路102接收，封包傳輸電路406被允許基於修改後的數據塊組（單元數據）RXD0'-RXD3'產 生及傳輸輸出封包P_〇UT'。封包傳輸電路406參考儲存於存儲裝置124的鍊表從封包緩 衝器114順序讀取修改後的數據塊組（單元數據）RXDO' -RXD3'並儲存於本地FIFO中，用 於驗證校驗和。隨後，封包傳輸電路406從鍊表尾節點的下一節點地址欄讀取校驗和D CKS 並驗證校驗和。若校驗和正確，則封包傳輸電路406順序傳輸RXDO' -RXD3'作為輸出封包 P_0UT' 的數據塊組（單元數據）TXD0-TXD3(亦即，RXDO' = TXD0，RXD1' = TXD1，RXD2' = TXD2,且RXD3' = TXD3)。若校驗和不正確，封包傳輸電路406將丟棄上述數據。
[0035] 在上述實施例中提出的鍊表架構應用於網絡交換機100/400中，用於使用共享鏈 表尾節點來指示控制信息（例如，寫錯誤信息）或數據信息（例如，校驗和）。然而，其僅用 作說明的目的，並不能作為本發明的限制。亦即，任一使用提出的鍊表架構的電子設備均落 入本發明的範圍。
[0036] 以上所述僅為本發明的較佳實施例，本領域相關的技術人員依據本發明的精神所 做的等效變化與修改，都應當涵蓋在權利要求書內。
【權利要求】
1. 一種鍊表處理裝置，其特徵在於，包含： 存儲裝置；以及 鍊表控制器，用於設置鍊表信息以及將所述鍊表信息寫入所述存儲裝置，以在所述存 儲裝置中創建鍊表； 其中所述鍊表包含多個節點，每一節點具有下一節點地址欄，所述鍊表信息包含數據 模式，所述數據模式用於指示所述鍊表的結尾以及輔助信息，以及所述鍊表控制器將所述 數據模式儲存到所述鍊表的鍊表尾節點的所述下一節點地址欄。
2. 根據權利要求1所述的鍊表處理裝置，其特徵在於，所述數據模式並非指向空地址 的空指針。
3. 根據權利要求1所述的鍊表處理裝置，其特徵在於，所述存儲裝置至少包含位於第 一地址範圍的第一存儲空間及位於第二地址範圍的第二存儲空間，所述鍊表控制器用於將 任一鍊表僅儲存於所述第一存儲空間，並且所述數據模式具有與所述第二存儲空間內多個 地址之一相同的位模式。
4. 根據權利要求1所述的鍊表處理裝置，其特徵在於，所述輔助信息是控制信息。
5. 根據權利要求4所述的鍊表處理裝置，其特徵在於，所述控制信息指示與所述鍊表 尾節點相關的數據塊組的接收錯誤。
6. 根據權利要求5所述的鍊表處理裝置，其特徵在於，當無可用來緩衝所述數據塊組 的資源時，所述鍊表控制器設置寫錯誤信息作為所述數據模式，並將所述寫錯誤信息儲存 入所述鍊表尾節點的所述下一節點地址欄。
7. 根據權利要求1所述的鍊表處理裝置，其特徵在於，所述輔助信息是數據信息。
8. 根據權利要求7所述的鍊表處理裝置，其特徵在於，所述數據信息是與所述鍊表的 所述多個節點分別相關的多個數據塊組的校驗和。
9. 根據權利要求8所述的鍊表處理裝置，其特徵在於，所述數據模式具有較高有效位 部分以及較低有效位部分，所述鍊表控制器設置所述較高有效位部分以指示所述鍊表的所 述結尾，以及利用所述校驗和設置所述較低有效位。
10. 根據權利要求9所述的鍊表處理裝置，其特徵在於，所述存儲裝置至少包含位於第 一地址範圍的第一存儲空間及位於第二地址範圍的第二存儲空間，所述鍊表控制器用於將 任一鍊表僅儲存於所述第一存儲空間，並且所述數據模式的所述較高有效位部分不同於所 述第一地址範圍內的每一地址的共址較高有效位部分。
11. 一種鍊表處理方法，其特徵在於，包含： 設置鍊表信息，其中所述鍊表信息包含數據模式，所述數據模式用於指示鍊表的結尾 以及輔助信息；以及 將所述鍊表信息寫入存儲裝置，以在所述存儲裝置中創建所述鍊表； 其中所述鍊表包含多個節點，每一節點具有下一節點地址欄，以及所述述數據模式被 寫入所述鍊表的鍊表尾節點的所述下一節點地址欄。
12. 根據權利要求11所述的鍊表處理方法，其特徵在於，所述數據模式並非指向空地 址的空指針。
13. 根據權利要求11所述的鍊表處理方法，其特徵在於，所述存儲裝置至少包含位於 第一地址範圍的第一存儲空間及位於第二地址範圍的第二存儲空間，任一鍊表僅被儲存於 所述第一存儲空間，並且所述數據模式具有與所述第二存儲空間內多個地址之一相同的位 模式。
14. 根據權利要求11所述的鍊表處理方法，其特徵在於，所述輔助信息是控制信息。
15. 根據權利要求14所述的鍊表處理方法，其特徵在於，所述控制信息指示與所述鏈 表尾節點相關的數據塊組的接收錯誤。
16. 根據權利要求15所述的鍊表處理方法，其特徵在於，設置所述鍊表信息的步驟包 含： 當無可用來緩衝所述數據塊組的資源時，設置寫錯誤信息作為所述數據模式，使得所 述寫錯誤信息被儲存入所述鍊表尾節點的所述下一節點地址欄。
17. 根據權利要求11所述的鍊表處理方法，其特徵在於，所述輔助信息是數據信息。
18. 根據權利要求17所述的鍊表處理方法，其特徵在於，所述數據信息是與所述鍊表 的所述多個節點分別相關的多個數據塊組的校驗和。
19. 根據權利要求18所述的鍊表處理方法，其特徵在於，所述數據模式具有較高有效 位部分以及較低有效位部分，以及設置所述鍊表信息的步驟包含： 設置所述較高有效位部分以指示所述鍊表的所述結尾；以及 利用所述校驗和設置所述較低有效位。
20. 根據權利要求19所述的鍊表處理方法，其特徵在於，所述存儲裝置至少包含位於 第一地址範圍的第一存儲空間及位於第二地址範圍的第二存儲空間，任一鍊表僅被儲存於 所述第一存儲空間，並且所述數據模式的所述較高有效位部分不同於所述第一地址範圍內 的每一地址的共址較高有效位部分。
21. -種網絡交換機，其特徵在於，包含： 封包接收電路，用於接收輸入封包，以及從已接收的所述輸入封包中導出多個第一數 據塊組； 鍊表處理裝置，包含： 存儲裝置；以及 鍊表控制器，用於將鍊表信息寫入所述存儲裝置，以在所述存儲裝置中創建鍊表，其中 所述鍊表包含與所述多個第一數據塊組分別相關的多個節點，每一節點具有下一節點地址 欄，所述鍊表信息包含數據模式，所述數據模式用於指示所述鍊表的結尾以及輔助信息，以 及所述鍊表控制器將所述數據模式儲存到所述鍊表的鍊表尾節點的所述下一節點地址欄； 以及 封包傳輸電路，用於依據所述鍊表從所述多個第一數據塊組導出輸出封包的多個第二 數據塊組，以及傳輸所述輸出封包，其中當產生所述輸出封包時，所述封包傳輸電路參考由 所述鍊表尾節點指示的所述輔助信息執行封包處理。
22. 根據權利要求21所述的網絡交換機，其特徵在於，所述輔助信息指示所述輸入封 包的數據塊組的接收錯誤；以及當讀取所述鍊表尾節點時，所述封包傳輸電路將預設錯誤 數據塊組附加至所述輸出封包。
23. 根據權利要求21所述的網絡交換機，其特徵在於，更包含： 校驗和處理器，用於計算所述多個第一數據塊組的校驗和； 其中所述鍊表控制器利用所述校驗和設置所述輔助信息；以及當傳輸所述輸出封包 時，所述封包傳輸電路依據讀取於所述鍊表尾節點的所述校驗和驗證所述多個第二數據塊 組。
【文檔編號】H04L12/931GK104125169SQ201410175645
【公開日】2014年10月29日 申請日期:2014年4月28日 優先權日:2013年4月26日
【發明者】張建雄 申請人:聯發科技股份有限公司