一種信元頭轉換表的動態存儲管理方法
2023-05-13 17:27:36
專利名稱：一種信元頭轉換表的動態存儲管理方法
技術領域：
本發明涉及一種採用共享內存型交換結構的ATM(異步傳輸模式)交換系統中信元頭轉換表(Input Translation Table-ITT)的動態存儲方法，具體地說，涉及交換機領域中ATM信元的交換管理機制。
ATM網是面向連接的通信網，端到端接續是在網絡通信開始以前建立，每一個ATM信元在網中獨立傳輸。ATM信元交換實質是根據信元信頭的路由選擇標號(虛通道指針VPI/虛電路指針VCI)，將輸入ATM邏輯信道的信元輸出到指定的輸出ATM邏輯信道上。ATM邏輯信道由以下兩個標示符構成物理埠編號和路由選擇標號(VPI/VCI)。
在採用共享內存型交換結構的ATM交換機中，必須有一套有效的交換機制，來保證交換網絡對信元的解析、轉換和存儲，以及管理信元淨荷在內存區的存儲。其中，信元淨荷實際並不參與具體的交換過程，而只是信元淨荷在內存中的存儲地址指針從輸入端傳到輸出端。在輸出端，只是把轉換後的信元頭加到信元淨荷上，輸出到指定的ATM邏輯信道上。在此過程中，信元頭的解析、轉換和存儲，顯得非常重要。
在目前採用的共享內存型交換結構的ATM交換系統中，採用了多種信元頭轉換和存儲管理機制，其中採用最多的是固定長度空間的存取方法，這種方法是對空閒塊採用固定大小的分配，雖然存取速度比較快，但是，存儲空間的利用率很低，浪費也嚴重，限制了連接的建立數量，從而，限制了交換機的整體性能。
本發明的技術方案是運用buddy(夥伴)系統，這種方法檢索合適大小的空閒塊很有效率，合併相鄰的空閒塊也很簡單，能有效實現ITT表的動態存儲分配。
本發明採用的buddy(夥伴)系統的ITT表動態存儲分配方法，其與連接相關的ITT表內存塊存取並不遵循一種簡單的模式，例如後分配先釋放(棧順序)，或者是先分配後釋放(隊列順序)，而是以任何順序請求和釋放任意大小的動態存儲分配模式。為了節約存儲空間，本發明針對基於同一ITT基址的VCI的實際使用範圍，分配與之大小相當的內存塊。ITT表項空間是在連接建立過程中由軟體根據一定的內存分配策略動態分配的，連接拆除時釋放該ITT表項空間。
對於VC(虛電路)連接來說，如果多條VC連接享有同樣的輸入埠、子埠和VPI(虛通道指針)，那麼，他們將有同樣的LUT(THE LOOKUPTABLE信元頭檢索表)地址，因此，就有同樣的ITT基地址，每條連接對於ITT基地址的偏移量由VCI(虛電路指針)決定。在本發明的內存分配策略中，把整個ITT表所能使用的存儲空間分成若干長度不一的空間塊，對享有同樣的ITT基地址的所有VCI，統一申請一塊內存區。ITT表的內存空間分配以內存塊為單位。分配的空間塊的大小，必須大於映射到同一ITT表基址的VCI的使用範圍。VCI為16位，但在實際的使用中，並不是從0x0到0xffff都使用了，只是使用了一部分，因此，映射到同一基址的ITT表的實際所需存儲空間是可變的。這就意味著在為ITT表分配內存塊時，並不是每個內存塊都必須分配涵蓋整個VCI範圍的同樣大小的空間。如何提供基於同一ITT表基址的VCI使用範圍呢？連接參數裡的VCI_base提供與此ITT表基址相關的VCI的最小值。例如如果預先知道連接的VCI最小為1024，最大為2000，就不會安排2k大小的ITT段，因此節約了空間。可設置VCI_base＝1024，ITT片段分配代碼則會分配1k大小的ITT片段，並調整ITT基址。所以，如果改變了VCI_base，必須把與該LUT相應的連接都關掉，並重建。
本發明所述的夥伴系統，其核心算法是K階夥伴系統的數學定義S[i+1]＝S[i]+S[i-k]，此處S[i]為第i的片段的塊大小。
因此，如果K＝0，S指指數夥伴系統。K＝1，指Fibonaci(斐波納契數列)夥伴系統。K值越大，塊空間就越大。為了簡化，本發明設置最小的塊空間為64，(也就是說S
＝64)。因為最大的塊空間大小由VCI的最大值決定，也就意味著●對於0階的夥伴系統，可能的塊空間大小有如下幾種0x40，0x80，0x100，0x200，0x400，0x800，0x1000，0x2000，0x4000，0x8000。●對於1階的夥伴系統，S[1]＝0x80，可能的塊空間大小有如下幾種0x40，0x80，0xc0，0x140，0x200，0x340，0x540，0x880，0xdc0，0x1640，0x2400，0x3a40，0x5e40，0x9880，0xf6c0，0x18f40。●對於2階的夥伴系統，S[1]＝0x80，S[2]＝0x100，可能的塊空間大小有如下幾種0x40，0x80，0x100，0x140，0x1c0，0x2c0，0x400，0x5c0，0x880，0xc80，0x1240，0x1ac0，0x2740，0x3980，0x5440，0x7d80，0xb500，0x10940。
夥伴系統處理固定大小的塊，當需要一個空閒塊時，獲得一個有效的塊空間。如果沒有該空間大小的塊時，就把比該空間稍大一點的塊分段，以獲得所需空間，當一段塊被釋放後，它尋找自己的夥伴，如果能夠找到，則共同組合成更大的空閒塊。當釋放不再使用的佔用塊時，系統需要將這新的空閒塊插入到ITT空閒塊鍊表中去。即把地址相鄰的空閒塊歸併成更大空閒塊，在夥伴系統中則僅考慮互為「夥伴」的兩個空閒塊的歸併。何謂「夥伴」？如前所述，在分配時經常需要將一個空閒塊分裂成兩個大小相等的存儲區，這兩個由同一塊分裂出來的小塊就稱之「互為夥伴」。回收空閒快時，只當其夥伴為空閒塊時才歸併成大塊。也就是說，若有兩個空閒塊即使是地址相鄰，但不是又同一大塊分裂出來的，也不歸併在一起。
在ITT表的動態存儲分配中，具體選用幾階夥伴系統取決於連接VPI，VCI的使用情況。例如，如果多條連接的VCI需要的空間是2的n次冪，適合應用指數夥伴系統。因為用於指數系統的空間塊正好合適。而如果所需的空間是1025，比較以上三種階數的夥伴系統的塊值，1階夥伴系統的最佳。
更具體地，本發明中使用0階夥伴系統，設S
＝64。在任何給定的時間，都可能有各種大小的空閒塊和佔用塊。為實現對ITT空間的管理，在每個ITT段中，可配置3種類型的ITT鍊表A.為每一種大小的空閒塊保留一個單獨的ITT空閒塊鍊表；B.ITT佔用塊表C.VP連接ITT表對ITT表的存儲空間有分配和回收的管理兩個步驟，其中，1.對ITT表的存儲空間分配實現步驟如下步驟一、選定夥伴系統的階數，在ITT表空間初始化過程中，把整個ITT表空間切割成一組依序排列的各種空間塊，並為每一種大小的空閒塊保留個單獨的ITT空閒塊鍊表；步驟二、建立連接時，如果該連接所映射的ITT表空間塊已經分配過，則在該空間塊中建立一項ITT表項即可；否則，根據VCI-base，確定所需ITT表空間塊的大小；步驟三、從最小空閒塊鍊表依次向更大的空閒鍊表查找，如果存在大小與之一致的空閒塊，則分配所需空間。如果並不存在大小與之一致的空閒塊，則需要從空間範圍更大的空閒塊中去查找，直到找到一個空閒塊，則將其中的一部分分配給它，而將剩餘部分夥伴塊插入大小與之一致空閒塊的空閒表中。例如當需要分配一個0x1500位元組的空間時，由於沒有與之相對應的空閒塊鍊表，也就沒有0x1500空間的空閒塊。於是查找大小為0x2000空閒塊的連結表，如果該連結表裡沒有空閒塊可分配，則從大小為0x4000空閒塊的連結表中得到一個空閒塊，並把它分成兩個0x2000空閒塊，把其中一個空閒塊分配出去，另一塊連結在0x2000空閒塊的空閒鍊表裡。
2.對ITT表的存儲空間回收實現步驟如下步驟一、拆除一條連接時，判斷該連接是否是所在的ITT表空間裡的取後一條連接；如果是，則進行以下的ITT表空間回收算法，否則不回收該ITT表空間；步驟二、在回收ITT表空間塊時，應首先判斷其夥伴是否為空閒。若不空閒，則只要將釋放的空閒塊簡單插入在相應大小的空閒鍊表中即可。若空閒，則從相應大小的空閒鍊表中找到其夥伴，並在該鍊表中刪除它，然後再判斷合併後的空閒塊的夥伴是否為空閒塊；步驟三、重複步驟二，直到歸併所得空閒塊的夥伴不是空閒塊時，再把該空閒塊插入到相應大小的空閒鍊表中。
進一步，上述的本發明方法中，選取0階夥伴系統，在ITT表空間初始過程中，把整個ITT表空間切割成大小為0x40，0x80，0x100，0x200，0x400，0x800，0x1000，0x2000，0x4000，0x8000的各種空間塊。
本發明的有益效果是採用所述ITT表夥伴系統存儲管理機制，有效地節省了系統存儲空間，提高了檢索合適大小的塊空間的效率，簡化了合併相鄰空閒塊的步驟，實現了對ITT表空間的有效存儲管理。
圖2是本發明中的ITT表的存儲空間分配流程圖。
圖3是本發明中的ITT表的存儲空間回收流程圖。
先參閱
圖1所示它給出了信元頭的輸入轉換表之間的關係，在採用共享內存型交換結構的ATM交換系統中，信元頭的解析、轉換不是一次完成的，而是需要經過多次轉換才能完成。因為如果只用一次轉換完成，那麼所需的轉換表空間為2**(VPI長度+VCI長度)，即2**28＝256M。要佔用這麼大的存儲空間，一般的交換網系統是無法滿足的。信元頭的多次轉換基於這樣一個前提並不是所有的256M連接都在同一個時刻同時存在，因而並不需要這麼大的存儲空間。信元頭的轉換在輸入端涉及以下幾個輸入轉換表信元頭輸入埠表11(Port Mode Table，PMT)、信元頭檢索表12(The LookupTable，LUT)、信元頭轉換表13(Input Translation Table，ITT)。
上述的這些輸入轉換表11、12、13都是在連接建立時，在相應的存儲空間建立與該連接相關的各個表項。當連接建立後，有信元從該連接輸入時通過硬體查表PMT11、LUT12、ITT13等表，得到輸出的信元頭值。PMT11值由輸入埠號110索引得到，PMT11表裡存放LUT12表的基址111，加上信元的VPI120值作偏移地址得到ITT表基址121，再加上VCI130值作偏移地址，得到ITT地址131，從而讀取到ITT表項。
請參閱圖2，其系ITT表13的存儲空間分配流程圖，把其編成程序2駐留在交換機的只讀存儲器中，並由其CPU執行啟動本程序2，實施對ITT表13的存儲空間的分配，在所分配的空間塊中建立信元頭從ATM邏輯輸入信通道至指定的ATM邏輯輸出信道的連接表項。本實施例中，選定0階夥伴系統，程序啟動，執行步驟21，把整ITT表13的內存空間切割成10種大小的空間塊，並為每一種大小的空間塊保留一個單獨的ITT空間塊鍊表，之後，執行步驟22，建立一條連接，並根據該連接的信元頭路由選擇標VPI、VCI查接其所屬的ITT表13中的空閒塊是否已經存在？若存在，則跳躍而執行步驟27，在所分配的ITT表13中空間塊中建立該連接的ITT表項；若該信元頭路由連接指向的空閒塊不存在，則執行步驟23，根據VCI-base，所需ITT表13空間塊的大小，再從最小空閒塊鍊表依次向更大的空閒鍊表查找，是否存在大小與之一致的空閒塊？如果存在大小一致的空閒塊，便執行步驟26，把找到的空閒塊分配出去，然後執行步驟27，建立此連接的ITT表項；若執行步驟23而知道不存在大小一致的空閒塊，則執行步驟24，查詢能找到稍大一點的空閒塊嗎？若不能找到，則仍跳回執行步驟24；若能找到稍大一點的空閒塊，便執行步驟25，找到一個稍大的空閒塊，將該空閒塊中分割出一塊大小一致的空閒塊予以分配，而將剩餘部分插入大小與之一致的空閒塊的空表中，之後，執行步驟27，建立此連接的ITT表項。按所選的0階夥伴系統，在執行步驟21時，把ITT表13的空間切割成大小為{0X40，0X100，0X200，0X400，0X800，0X1000，0X2000，0X4000，0X8000，}10種大小空間塊。
請參閱圖3，它是ITT表13的存儲空間回收的流程圖，把其編成程序3駐留在交換機的只讀存儲器中，並由其CPU執行，啟動程序3，其任務是拆除信元頭進入的連結，回收已使用過的ITT表13的空間塊，使夥伴空間塊重新恢復成原有的大小的空間塊。啟動程序3，首先執行步驟31，折除一條連接時，判斷該連接是否是所在的ITT表13空間裡的最後一條連結，若不是最後一條連接，執行步驟35，程序返回；若是最後一條連結，則執行步驟32，判斷夥伴是否為空閒塊？若不空閒，須執行步驟34，從相應大小的空閒鍊表中找到其夥伴，並在該鍊表中刪除它，然後再判斷合併後的空閒塊的夥伴是否為空閒塊？若空閒，須返回執行步驟32；若不空閒塊，則執行步驟34，再把該空閒塊插入到相應大小的空閒鍊表中，再執行步驟35，程序返回。
權利要求
1.一種信元頭轉換表的動態存儲管理方法，其包括對ITT表的存儲空間分配和回收兩大步驟，其中a.對ITT表的存儲空間分配主要有如下步驟(1).根信元信頭的路由選擇標號VPI/VCI的使用情況，選用相適應階數的夥伴系統，並在ITT表空間初始化過程中，把整個ITT表空間切割成一組大小依序排列的各種空間塊，且為每一種大小的空間塊保留一個單獨的ITT空閒塊鍊表；(2).建立連接時，如果該連接所映射的ITT表空間塊已經分割過，則在該空間塊中建立一項ITT表；否則，根據VCI-base，確定所需ITT表空間塊的大小；(3).從最小空閒塊鍊表依次向更大的空閒鍊表查找，如果存在大小與之一致的空閒塊，則分配所需空間；如果並不存在大小與之一致的空閒塊，則需要從空間範圍更大的空閒塊中去查找，直到找到一個空閒塊，並從其中切割出所需大小的空閒塊分配給它，而餘下的夥伴空閒塊部分插入大小與之一致的空閒塊表中；b.對ITT表的存儲空間回收主要步驟如下(1).拆除一條連接時，判斷該連接是否是所在的ITT表空間裡的最後一條連接；如果是，則進行以下的ITT表空間回收算法，否則不回收該ITT表空間，(2).在回收ITT表空間塊時，應首先判斷其夥伴塊是否為空閒，若不空閒，則只要將釋放的空閒塊簡單插入在相應大小的空閒鍊表中即可；若空閒，則從相應大小的空閒鍊表中找到夥伴塊，並在該鍊表中刪除它，然後再判斷合併後的空閒塊的夥伴是否為空閒塊，(3).依此重複，直到歸併所有空閒塊的夥伴不是空閒塊時，再把該空閒塊插入到相應大小的空閒鍊表中。
2.根據權利要求1所述的信元頭轉換表的動態存儲空間管理方法，其特徵在於，所選用的夥伴系統為0階夥伴系統，在ITT表空間初始化過程中，把整個ITT表空間切割成大小為{0X40，0X80，0X100，0X200，0X400，0X800，0X1000，0X2000，0X4000，0X8000，}10種空間塊。
全文摘要
一種信元頭轉換表的動態存儲管理方法，其包括對ITT表的存儲空間分配和回收兩大步驟，其中主要選用合適階數的夥伴系統，先將ITT表空間切割成一組大小依序排列的各種大小空間塊，並為每一種大小空間塊保留一個單獨的ITT空閒塊鍊表，建立輸入輸出邏輯通道連接時，在ITT空閒空間塊中檢索相應一致大小的空閒塊，然後建立該連接ITT表項。拆除連接時，如果該連接不是所映射的ITT空間塊中最後一條連接，則直接刪除該連接的ITT表項即可。本發明的ITT表夥伴系統存儲管理機制，有效地節省了系統存儲空間，提高了檢索合適大小的空間塊效率，簡化了合併相鄰空閒塊的步驟，實現了對ITT表空間的有效存儲管理。
文檔編號H04L12/40GK1409519SQ01126789
公開日2003年4月9日 申請日期2001年9月18日 優先權日2001年9月18日
發明者周雲 申請人:深圳市中興通訊股份有限公司上海第二研究所