路由器中用於有效的周期性csnp的csnp緩存的製作方法
2023-05-09 17:24:11
專利名稱：路由器中用於有效的周期性csnp的csnp緩存的製作方法
技術領域：
本發明一般地涉及聯網設備，更具體而言，涉及在諸如路由器之類的聯網設備中處理CSNP分組。
背景技術：
在計算機網絡中，路由協議在諸如路由器之類的聯網設備被添加到網絡或從網絡中刪除時，被用來動態傳輸路由信息。路由器可以基於它們的本地接口建立被稱為鏈路狀態分組(LSP)的分組或消息，並且LSP分組描述了路由器的接口和在網絡中的鄰居(即鄰近路由器)。通常，LSP消息包括發起該LSP分組的路由器的名稱、序號以及「鏈路」或相鄰路由器的列表。
每個路由器使用傳統的「泛播(flooding)」算法向鄰近路由器發送其LSP，並且LSP未經改變地被傳遞到其他鄰近路由器，直到區域中的所有路由器都已接收到它們為止。當被收集在一起時，LSP可被用來描述網絡的拓撲。
每個路由器維護著鏈路狀態資料庫(LSDB)，其包括路由器已經接收到的所有LSP。當網絡拓撲發生改變時，一個或多個LSP將跟著發生相應的改變。
指定的路由器發送被稱為CSNP分組(完整序號協議數據單元(PDU))的分組到其他路由器，以便維持與網絡拓撲信息相關的資料庫同步。CSNP分組包括發送該CSNP分組的路由器已知的所有鏈路狀態。例如，在路由協議IS-IS(中間系統-中間系統)中，指定的路由器發送CSNP分組，以確保參與該協議的所有路由器都具有鏈路狀態資料庫的完整拷貝。通常，CSNP消息包括這樣的條目，其中每個條目具有源標識(LSP ID，標識針對各個LSP的源路由器)和對應於該LSP的序號。
每個接收CSNP分組的路由器將CSNP分組中的鏈路狀態列表(即來自LSP ID和序號)與其自己的內部鏈路狀態資料庫相比較。例如，接收到CSNP的路由器中的序號不匹配指示接收方路由器可能不具有網絡中的另一路由器報告的最近的鏈路狀態。這些差異可以通過發送接收者的資料庫中的LSP或通過向另一路由器發送要其發送丟失的LSP的請求(以部分序號(PSNP)的形式)來解決。
CSNP分組或消息是基於CSNP間隔計時器來周期性地發送的，所述CSNP間隔計時器定義從接口發送CSNP分組之間的秒數。在根據IS-IS規範的區域網(LAN)上需要周期性的CSNP發送。傳統上，周期性的CSNP分組發送是通過使用CPU資源遍歷其鏈路狀態資料庫並且在每次CSNP計時器期滿時重建所產生的CSNP分組的方式在路由器中實現的。例如，如圖1所示，傳統的路由器10包括IS-IS軟體進程12，其操作性地包括鏈路狀態資料庫14和周期性CSNP功能16。
但是，當拓撲變得更密集時，會出現擴展問題。如本發明的發明人所意識到的，存在很多使得周期性的CSNP發送成問題的問題。在給定接口上的CSNP間隔是可配置的，各個接口上的最大發送單元(MTU)可能不相同，並且可能存在成百上千個諸如對等鏈路(P2P)之類的接口或鏈路需要支持。此外，可專用於CSNP處理的CPU時間量可能非常有限。在每次CSNP計時器期滿後通過遍歷鏈路狀態資料庫重建CSNP分組的做法可能需要路由器的過多的CPU資源。
因此，如本發明的發明人所意識到的，需要一種在減少CPU消耗和增大可擴展性的同時提供周期性的CSNP功能的方法和裝置。
本發明的各個實施例的特徵、功用和優點將從以下結合附圖對本發明實施例的具體描述中變得更加明顯。
圖1示出傳統路由器的框圖。
圖2示出根據本發明一個實施例的具有CSNP緩存的路由器的示例的框圖。
圖3示出本發明的實施例可以使用的各種數據結構的示例。
圖4示出根據本發明一個實施例的數據結構的示例。
圖5示出根據本發明一個實施例，用於初始化CSNP緩存的邏輯操作的示例。
圖6示出根據本發明一個實施例，用於改變CSNP緩存的條目的邏輯操作的示例。
圖7示出根據本發明一個實施例，用於處理期滿的CSNP計時器的邏輯操作的示例。
圖8示出根據本發明一個實施例，用於計算CSNP片斷(fragment)的邏輯操作的示例。
圖9示出根據本發明一個實施例接合CSNP條目的示例。
具體實施例方式
本發明的實施例提供了在形成將發送的CSNP分組時可用使用的緩存。緩存可被實現在諸如路由器之類的聯網設備中。本發明的各個實施例在這裡被公開。
如圖2所示，本發明的實施例提供了可被用於形成將從路由器24發送的CSNP消息22的緩存20。緩存20提供了在每次CSNP計時器期滿時無需CPU資源遍歷鏈路狀態資料庫26重建CSNP值的情況下執行CSNP功能所需的條目。這裡描述了可以在緩存中實現的各個特徵。在一個示例中，路由器24還可以包括IS-IS軟體進程28、包含一個或多個鏈路狀態的鏈路狀態資料庫(LSDB)26以及周期性CSNP進程30。
在一個實施例中，鏈路狀態資料庫26可以包括描述網絡中的鏈路的一個或多個條目，並且這些條目可以從接收自網絡中其他路由器的鏈路狀態分組(LSP)消息中得到，或者可以從當前路由器的接口得到，並描述了與其相鄰的路由器。鏈路狀態資料庫26可以利用任意用於管理鏈路狀態資料庫26的傳統進程或技術來實現。一般而言，鏈路狀態資料庫26可以包括來自LSP的所有相關數據，包括LSP頭部、LSP ID以及可以包括序號和相鄰路由器或鏈路的鏈路狀態分組的主體或有效載荷。例如，在一個示例中，鏈路狀態資料庫26可以包括所有LSP的樹。
圖2的示例的路由器24可以實現周期性CSNP功能30，其中路由器24向網絡中的其他路由器周期性地發送(一個或多個)CSNP消息22，其中CSNP消息22被用來向其他路由器傳達路由器24的鏈路狀態資料庫26的內容。根據本發明一個示例，路由器24可以具有多個接口32、34，其中每個接口可以具有獨立的CSNP計時器和「下一LSP ID」路由器。
為了減少在建立用於大量接口(例如(但不局限於)P2P和DIS LAN接口)的CSNP分組時由複製的LSDB遍歷所消耗的CPU資源，本發明的實施例提供了CSNP緩存20。在一個示例中，緩存20中的每個條目代表一個CSNP片斷，其尺寸可能局限於LSP MTU尺寸，以確保它可以通過任意IS-IS接口來發送。在CSNP計時器期滿之後，接口從緩存20中拾取下一片斷用於發送。結果，只要LSDB 26是穩定的，當CSNP計時器期滿時就不需要LSDB遍歷。
在一個示例中，路由器24的每個接口32、34可以訪問CSNP緩存20，以便生成CSNP分組22。所有CSNP接口計時器可經由計時器輪來分配。這可以提供時間上處理的統一分配。
圖3示出根據本發明實施例可被用作CSNP緩存20中的條目40的數據結構。CSNP條目40可以包括範圍欄位42，其包括開始和結束鏈路狀態PDU標識44、46，例如開始和結束LSP ID。優選地，每個緩存條目40的範圍欄位42具有開始和結束鏈路狀態標識，從而使得當在緩存中被列出時，所有範圍欄位42覆蓋了緩存20中代表的可能的鏈路狀態標識的完整範圍。
緩存條目40還可以包括「有效」標誌48(真或假)，其指示緩存條目40是有效的還是無效的。緩存條目40還可以包括PDU內容50，其可以包括標識相應LSP的LSP頭部的列表。在另一示例中，PDU內容50可以包括CSNP片斷，所述CSNP片斷可以包括將被包括在CSNP消息中的LSP ID的列表並且可以包括開始和結束LSP ID和PDU頭部。例如，每個緩存條目40可以包括標識相應LSP的一個或多個LSP頭部。
根據本發明一個實施例，緩存20的示例還如圖3所示。在一個示例中，CSNP緩存20可以包括標誌「ALL_VALID」60(真或假)，其指示緩存是有效的還是無效的。
緩存20還可以包括緩存條目40的AVL樹或其他數據結構62(例如鍊表)，並且允許快速插入、刪除和搜索數據結構62。在一個示例中，AVL樹62包括所有緩存條目或CSNP片斷40。AVL樹62(例如平衡的二元搜索樹)可被用來存儲記錄或條目40。在一個示例中，AVL樹實現方式62可以利用用於處理緩存條目40的線程化進程。
在一個示例中，緩存20可以利用緩存條目中列出的第一LSP ID來索引。在一個示例中，AVL樹中的每個節點可被單獨地使之無效，並且完整的緩存可被自動地使之無效。
對於正在提供CSNP分組22的路由器24的每個接口32、34，CSNP計時器值33、36可以與這樣的接口32、34相關聯。例如，CSNP計時器33可以是每隔10秒期滿一次的周期性計時器。此外，用於「下一LSP標識」的值或地址35、37也可以與這樣的接口32、34相關聯。
下面圖4示出根據本發明一個實施例的緩存條目的示例。在圖4的示例中，假設LSP ID範圍是A到Z，其中在鏈路狀態資料庫26中存在六個LSP(A、C、M、N、O、Y)。
還假設LSP最大發送單元(MTU)被設置為使得一個CSNP緩存條目/CSNP片斷40中僅裝入兩個LSP ID。由於在此示例中，在資料庫26中存在六個LSP，因此將存在三個緩存條目/CSNP片斷40。
在該示例中，CSNP緩存20可以如圖4所示「ALL_VALID」標誌60對於該緩存為真，並且存在如下三個CSNP條目40(A，C，真，[A，C])(D，N，真，[M，N])
(O，Z，真，[O，Y])緩存20中的第一條目的範圍欄位42為(A，C)，因為緩存條目40中的LSP具有的LSP ID為(A，C)，其範圍從(A)到(C)。緩存20中的第二條目的範圍欄位42為(D，N)，因為緩存條目中的LSP具有的LSP ID為(M，N)，它是總體範圍(D，N)的一部分。緩存20中的第三條目的範圍欄位42為(O，Z)，因為緩存條目中的LSP具有的LSP ID為(O，Y)，它是總體範圍(O，Z)的一部分。因此，每個緩存條目的範圍欄位一起覆蓋了從(A)到(Z)的總體範圍。
在操作中，例如，當路由器24的CSNP進程31使得CSNP計時器33在接口32(例如IS-IS接口)上期滿時，CSNP進程31查看緩存20以形成第一CSNP分組22。利用「下一LSP標識」35，CSNP進程31從適當的CSNP緩存條目獲得LSP信息，並將該信息通過接口32發送到其他路由器。「下一LSP標識」35被更新，並且CSNP進程31隨後通過接口32發送帶有來自下一CSNP緩存條目的LSP信息的CSNP分組22。該進程的實施例在圖7中有所描述。
圖5示出根據本發明實施例用於初始化CSNP緩存的操作示例。圖5用於CSNP緩存初始化的操作例如可以發生在LSP MTU(最大發送單元)的配置或重配置被指定時。在操作70處，CSNP緩存中的所有現有條目被刪除。在操作72中，向緩存添加條目。在一個示例中，緩存條目可以包括範圍欄位(即指定開始LSP ID和結束LSP ID)、有效標誌或位(真或假)以及PDU內容。如圖5所示，在一個示例中，當添加了新條目時，它可能具有初始設置，其中範圍欄位覆蓋了LSP ID的整個範圍(被示為(A，Z))，有效標誌或位為假並且PDU內容為空或null。
圖6的操作涉及根據本發明一個實施例單個LSP中的改變，其將影響CSNP緩存中的相應改變。這些操作可能發生在存在對本地LSP的更新或者路由器接收較新的LSP時。在操作80，在接收到LSP之後，對緩存中針對覆蓋或包括了受影響的LSP的範圍的條目進行查找。在操作82，與受影響的LSP相關聯的CSNP緩存條目被標記為無效的或假的。新LSP將被存儲在LSDB 26中。
圖7示出根據本發明一個實施例用於利用CSNP緩存形成和發送CSNP分組或消息的操作的示例。當CSNP計時器期滿時，例如通過路由器的一個或多個接口，圖7的示例性操作可以被執行。在一個示例中，CSNP計時器周期性地期滿，並因此，圖7的一個或多個示例性操作被周期性地執行。
在操作90，接口的「下一LSP ID」被用於從緩存中找到將發送的下一個緩存條目，並取得適當的緩存條目。在一個示例中，一旦該「下一LSP ID」緩存條目被找到，如果需要，「下一LSP ID」可被更新到被設置為緩存條目中的結束LSP ID，或被更新到LSP ID範圍的開始。如果希望，操作90可以利用圖8來操作來實現，如下所述。
在操作92，包含在操作90中取得的緩存條目中的CSNP片斷/PDU內容作為CSNP分組或消息通過各自的路由器接口被發送(即路由器將CSNP片斷作為分組從CSNP計時器已經期滿的接口發送出去)。CSNP分組或消息的發送可以利用傳統的用於發送CSNP分組的方法。在同一接口上的其他IS-IS路由器將接收CSNP片斷並檢查其與它們自己的鏈路狀態資料庫的一致性。
在一個示例中，操作92發送多個CSNP片斷，以覆蓋LSP ID範圍。例如，在圖4的示例中，如果下一LSP ID是「A」，則操作92發送第一緩存條目(A，C，真，(A，C))的相關內容，從而LSP LD為A、C的CSNP消息被發送。
在操作94處，如果CPU被加載，則控制傳遞到操作96，該操作96利用例如配置值的八倍的指數回退來啟動CSNP計時器。該計時器可加載其他值，或利用其他傳統的計時器加載程序或值來加載。因此，在操作96，計時器被重新加載，然後發送下一緩存條目。當操作96的計時器期滿時，控制可以返回操作90，以從下一緩存條目獲得和發送LSP信息。
在一個示例中，系統的加載可以在計算在重啟計時器時將提供給計時器的值時被使用。如果1分鐘加載平均值大於0.5，則例如可以使先前的CSNP間隔加倍。在一個示例中，該操作的上限可以是一個乘數，例如配置值的8倍，但是其他上限也是可能的。這可以確保某種CSNP生成將發生。
在操作94，如果CPU未被加載，控制則傳遞到操作98。操作98判斷發送CSNP片斷的一個周期是否已經完成。如果沒有，控制則傳遞到操作100(可選的)，操作100利用短步調(pacing)值來啟動CSNP計時器，例如短步調值66毫秒。當操作100的計時器期滿時，控制可以返回操作90，以從下一緩存條目獲得和發送LSP。
為了覆蓋整個鏈路狀態資料庫，可能需要發送多於一個CSNP片斷。常規配置的CSNP計時器可以是發送整組CSNP片斷的間隔(一個周期)。例如，假設存在CSNP片斷1、2和3和10秒的CSNP計時器，則CSNP片斷1、2、3將被發送；保持安靜10秒；發送CSNP片斷1、2、3；保持安靜10秒，以此類推。在一種實現方式中，作為短步調延時的等待時間(例如66毫秒)可被用作發送片斷1-2和2-3之間的等待時間量。
但是，如果操作98確定一個周期已經完成，則控制傳遞到操作102，其利用配置值啟動CSNP計時器。當操作102的計時器期滿時，控制可以返回操作90以從下一緩存條目獲得和發送LSP。
在一個示例中，在常規操作過程期間，用於接口的CSNP計時器將期滿，以指示到了路由器發送CSNP消息的時間，該CSNP消息具有來自該路由器的鏈路狀態資料庫的所有鏈路狀態。CSNP緩存不是遍歷鏈路狀態資料庫，而是將被用來生成CSNP消息。操作90將利用「下一LSP ID」獲得下一緩存條目。從該條目，操作92將發送存儲在該緩存條目中的LSP，作為CSNP消息。如果需要，操作98(可選的)隨後將引入短步調延時，直到進程返回操作90，以利用「下一LSP ID」獲得下一緩存條目，從而使得具有存儲在該緩存條目中的LSP的CSNP消息被發送。在一個示例中，該進程將繼續，直到緩存中的所有LSP都被發送為止。
圖8示出用於計算CSNP緩存條目的邏輯操作的示例。如果需要，這些操作可被用於圖7的操作90。
在圖8的操作110處，緩存標誌「ALL_VALID」被檢查以判斷是否CSNP緩存中的所有條目都是有效的，還是某些條目是無效的。如果某些條目無效，則在操作112，所有CSNP緩存條目都被標記為無效或假，並且控制傳遞到操作114(如下所述)。如果在操作110，緩存的「ALL_VALID」標誌為假(即緩存有效)，控制則傳遞到操作114。
在操作114，基於下一LSP ID，對範圍覆蓋下一LSP ID的CSNP緩存條目進行查找。
在操作116，如果緩存條目無效，則控制傳遞到操作118-122。但是，如果操作116確定CSNP緩存條目有效，則控制傳遞到操作124，其返回有效的CSNP緩存條目，並且該進程的迭代完成。
如果在操作116，CSNP緩存條目無效，控制則傳遞到操作118，其中所有先前CSNP無效緩存條目都被定位到並在一個實施例中被刪除。該操作還可以包括更新CSNP緩存條目的「開始LSP ID」以覆蓋新範圍。
操作120找到無效的所有後續CSNP緩存條目，並且在一個示例中，這些條目被刪除，下一有效的CSNP條目被包括進來，並且「結束LSPID」被更新以覆蓋新範圍。在操作122，CSNP緩存條目根據新範圍被重建，並且「有效」標誌針對該緩存條目被設置為真。
操作126判斷重建的緩存條目是否完全覆蓋新範圍，如果是，控制則傳遞到操作124，該操作124返回有效的CSNP片斷，並且該進程迭代完成。否則，操作126傳遞控制到操作128，在一個示例中，該操作128對範圍的其餘部分添加無效的CSNP緩存條目。該無效的條目將在下一CSNP計時器期滿之後被重建。
圖9示出根據本發明一個實施例，接合緩存20中的條目的一個示例。在圖9的示例中，假設鏈路狀態資料庫26已被從具有六個LSP(A、C、M、N、O、Y)改變到新的只具有三個LSP(A、M、O)。
在CSNP緩存20中，「ALL_VALID」標誌60可被設置為真，並且CSNP緩存條目40的AVL樹或鏈路列表62可以包括(A，C，假，[A，C])(D，N，假，[M，N])(O，Z，假，[O，Y])此外，還假設來自緩存條目(A，C)的LSP已被發送，並且接口「下一LSP ID」等於D。
利用D的下一LSP ID，緩存條目(D，N，假，[M，N])被找到。由於它是無效的，因此使用條目的接合/合併，並且它與周圍的無效片斷組合在一起。在接合以針對範圍(A，Z)建立並產生片斷(A，M，真，[A，M])時，由於完整的範圍(A，Z)未被覆蓋，因此添加新的無效條目(N，Z，假，[空])。
因此，CSNP緩存20將使得「ALL_VALID」標誌60設置為真，並且將具有CSNP緩存條目40(A，M，真，[A，M])(N，Z，假，[空])現在，片斷(A，M)作為CSNP消息被發送，並且片斷(N，Z)可以在下次下一CSNP計時器期滿之後被重建為(N，Z，真，
)，然後被發送。
如這裡所述，當鏈路狀態資料庫26的相應部分改變時，單獨的緩存條目40可以被無效。在一個示例中，每個被無效的緩存條目40隻能針對已經發出該片斷的接口被重建一次。如果LSDB 26在CSNP計時器下次期滿之前沒有改變，如果需要，緩存20則可以被其他接口重複使用。
在最壞情況下，LSDB 26一直改變，在每次CSNP計時器期滿時，覆蓋片斷範圍的LSDB 26的遍歷可以被執行，這將與在第一階段中沒有實現緩存20的情況具有類似的處理量。但是，緩存20可以提供在長時間段期間可實現的良好命中率。
如果計時器線程遇到已被全局無效的緩存20，則在一個示例中，在其他操作之前，計時器線程可以無效掉緩存20中的所有條目40，然後再全局地使緩存20有效。
緩存20可以被路由器24的每個接口32、34單獨參考。在一個實施例中，可能存在在每個接口(即32、34)上運行的一個計時器(即33或36)，並且每個這樣的計時器將以各自獨立地期滿。通過使用緩存20，可以在遍歷LSP資料庫26時實現高效率，並且對PDU的格式化將在任意緩存命中時已經完成。
為了進一步減小所需處理量，在一個示例中，如果所有接口32和34都被配置為支持LSP MTU尺寸，則CSNP分組可被格式化為該尺寸。雖然這可能產生更多的CSNP片斷，但PDU可以在所有接口上重複使用。
在一個示例中，當使用點對點鏈路時，由於接收CSNP分組的節點可以通過發送PSNP或LSP作出響應，因此正在接收CSNP分組的節點也不發送它們。因此，當接收到CSNP分組時，該接口上的CSNP計時器可以被重啟。
當接口的CSNP計時器期滿時，可以執行作為計時器線程一部分的緩存清除和重計算。這允許在其他線程上保持輕負載。
本發明的實施例還可被用於生成用於乙太網的CSNP分組。由於只有指定的路由器(DIS)發送用於乙太網的CSNP分組，因此如果需要，CSNP計時器可以只在接口或路由器變為DIS時啟動。此時，緩存的內容可被再次發送。
在一個示例中，緩存中的條目(即範圍欄位42)不再重疊。如果需要，條目40可以按單調遞增的順序被布置在AVL樹62中。在一個示例中，緩存20中的所有緩存條目40(無效的和有效的)都覆蓋完整的可能LSP ID範圍，因此完全代表資料庫26。緩存條目40可以例如通過使用上述圖9的示例的操作而被接合。
在一個示例中，每個緩存條目40可以承載它上次被重計算時保存的條目數目的計數值。這可被用來估計下次計算時的條目40的數目。
緩存無效可能發生在環境中的某些情況發生極大改變的情況下(例如LSP MTU改變)。如果需要，整個緩存20可以被無效掉。
在一個示例中，如果單個LSP改變(即被刷新、清除、添加)，則只有包含該LSP的緩存條目40可以被無效。清除和添加可以更新緩存條目40中的LSP的數目，以輔助估計用於緩存條目40的LSP的數目。
在一個示例中，如果緩存條目40是無效的並且需要被重新計算，則可以將其與其他緩存條目40接合。任意緩存條目40可以具有0、1或2個直接鄰居。每個緩存條目40可能包含該條目中列出的LSP的數目，但是對於無效的緩存條目，該數目可能不準確。優選地，儘可能地將三個緩存條目40接合在一起。在每個緩存條目40中列出的LSP的數目被用作對緩存條目40的尺寸的估計。如果無效的緩存條目40加上其左手邊的鄰居可以被接合，它們的LSP ID的範圍則可以被合併，並且可以從LSP資料庫26中刪除該左手邊的鄰居。關於接合後的緩存條目，可以判斷它是否可以與右手邊的片段接合。如果可以，則可以接合LSP範圍並且可以從AVL樹62中刪除該右手邊的鄰居。接下來，緩存條目40可以被重新計算。如果尺寸估計是不正確的，則將被返回的第一緩存條目將不覆蓋整個範圍。該緩存條目可以被插入到AVL樹62中，並且該範圍可以被從將被計算的緩存條目中減去。緩存條目40可以被迭代地計算，直到整個範圍被計算出為止，並且用於發送的第一片斷可以被使用。
如果將裝入到緩存條目40中的LSP的數目超過可能的數目(由於MTU限制或其他原因)，則在一個示例中，緩存條目40的計算將指示出這一點，並且LSP空間可以被再分成多個緩存條目。當緩存條目40被計算時，計算出的緩存條目被存儲，並且覆蓋的LSP空間可以被從正被計算的範圍中減去。
在其他實施例中，LSP到CSNP功能30、31的索引可以被維護。由於CSNP分組的格式是已知的，因此開銷是固定的。在一個示例中，每個LSP條目具有固定尺寸，因此整個CSNP分組可被視為LSP條目的陣列。如果LSP條目的索引被作為鏈路狀態資料庫26中的LSP的一部分存儲，則可以在常規的LSP刷新時更快速地更新LSP條目。在另一示例中，如果需要，CSNP分組可以按不同方式被重新打包。
如果需要，CSNP緩存條目40的無效和重計算的速率可以被限制。例如，可以為每個緩存條目維護一個時間戳，並且當沒有準備好重計算時，可以跳過一個緩存條目40，從而確保它在被重新計算時可以被發送。一種方法是使用用於此目的的發送列表。另一種方法是確保每個接口不會周期性地跳過某個給定的緩存條目。
本發明的實施例可以在聯網設備、通信設備或計算設備(例如路由器)中被使用或實現。
本發明的實施例可以被包含在電腦程式產品中。將會理解，包括本發明的特徵的電腦程式產品可以在具有計算機可讀代碼的計算機可用介質(例如CD-ROM或其他介質)中創建。計算機可用介質優選地包含被配置用於致使計算機執行實現本發明所需的各個功能的多個計算機可讀程序代碼設備，如這裡所述。
雖然這裡公開的方法被描述並示為參考按特定順序執行的特定操作，但是將會理解，這些操作可以被組合、細分或重新排序，以形成等同方法，而不會脫離本發明的教導。因此，除非特別指明，否則操作的順序和組合不是對本發明的限制。
應該意識到，說明書中對「一個實施例」或「實施例」或「一個示例」或「示例」的引用意味著如果需要，結合該實施例描述的特定特徵、結構或特性可以被包括在本發明的至少一個實施例中。因此，應該意識到，在說明書不同部分中對「一個實施例」或「實施例」或「一個示例」或「示例」的兩次或更多次引用不一定都引用同樣的實施例。此外，特定特徵、結構或特性可以按需要被組合在本發明的一個或多個實施例中。
應該意識到，在前面對本發明的示例性實施例的描述中，本發明的各個特徵有時被組合在單個實施例、附圖或描述中，以用於理清公開並付諸對各個發明方面的理解的目的。但是，該方法的公開不能理解為反映所要求保護的發明需要比每個權利要求中明確提出的特徵更多的特徵這一意圖。相反，如所附權利要求所反映的，發明的各個方面在於比單個所公開的實施例中的所有特徵更少的特徵，並且這裡描述的每個實施例可以包含多於一個發明特徵。
雖然已經參考實施例具體描述並示出了本發明，但是本領域技術人員將理解，在不脫離本發明的精神和範圍的情況下，可以對本發明的形式和細節作出各種其他修改。
權利要求
1.一種用在網絡中的聯網設備，包括存儲多個鏈路狀態條目的資料庫；以及可操作地耦合到所述資料庫的緩存，該緩存存儲了與所述資料庫的鏈路狀態條目相關的條目。
2.如權利要求1所述的聯網設備，其中所述鏈路狀態條目是從由所述聯網設備接收的鏈路狀態分組中得出的。
3.如權利要求1所述的聯網設備，其中所述聯網設備具有多個接口。
4.如權利要求1所述的聯網設備，還包括用於通過所述網絡發送包括鏈路狀態數據的分組的模塊，該模塊可操作地耦合到所述緩存。
5.如權利要求4所述的聯網設備，還包括計時器，用於提供控制包括鏈路狀態數據的網絡分組的發送的周期性間隔。
6.如權利要求5所述的聯網設備，其中當所述計時器期滿時，所述模塊訪問所述緩存，以創建包括鏈路狀態數據的一個或多個分組。
7.如權利要求1所述的聯網設備，其中存儲在所述緩存中的條目包括範圍欄位，該範圍欄位包含開始鏈路狀態標識和結束鏈路狀態標識。
8.如權利要求1所述的聯網設備，其中存儲在所述緩存中的條目包括指示所述條目是否有效的有效標誌。
9.如權利要求1所述的聯網設備，其中存儲在所述緩存中的條目包括鏈路狀態頭部的列表。
10.如權利要求1所述的聯網設備，其中存儲在所述緩存中的條目包括標識一個或多個鏈路狀態的數據。
11.如權利要求1所述的聯網設備，其中所述緩存包括指示所述緩存是否具有有效條目的有效標誌。
12.如權利要求1所述的聯網設備，其中存儲在所述緩存中的條目是按樹數據結構布置的。
13.如權利要求1所述的聯網設備，其中存儲在所述緩存中的條目是按鍊表數據結構布置的。
14.如權利要求1所述的聯網設備，其中所述聯網設備是路由器。
15.如權利要求4所述的聯網設備，其中所述分組是CSNP分組。
全文摘要
本發明公開了一種諸如路由器之類的聯網設備，在一個實施例中，其可以包括存儲多個鏈路狀態條目的資料庫和與資料庫可操作地耦合的緩存，該緩存存儲了與資料庫的鏈路狀態條目相關的條目。該聯網設備還可以包括用於通過網絡發送包括鏈路狀態數據的分組的模塊，該模塊可操作地耦合到緩存。在一個示例中，模塊訪問緩存以創建包括鏈路狀態數據的一個或多個分組。本發明的實施例可被用於在無需重複遍歷鏈路狀態資料庫以形成CNSP分組的情況下形成CSNP分組(完整序號分組)。
文檔編號H04L12/56GK101036349SQ200580031052
公開日2007年9月12日 申請日期2005年11月15日 優先權日2004年11月15日
發明者德裡克·延格, 克利斯汀·侯浦斯, 那伊爾·凡高帕勒, 安東尼·J·李 申請人:思科技術公司