路由器的ip地址的建立和尋找方法及其裝置的製作方法
2023-09-20 22:04:20 5
專利名稱：：路由器的ip地址的建立和尋找方法及其裝置的製作方法
技術領域：
：本發明系關於一種使用於路由器的網際網路協定(InternetProtocol；IP)尋址方法，特別是關於一種利用多階段轉送表(forwardingtable)以求得IP位址的尋找方法。
背景技術：
：由於網際網路的快速發展及網路交通流量趨於無法預測的原因，原先的80/20法則(80％的交通流量在區域網路，20％的交通流量在廣域網路)已不再適用，加上千兆位乙太網(GigabitEthernet)的興起，使得路由器成為網路效能的瓶頸。一般而言，路由器內具有一個路由表，內含網路間的連結信息，而路由器在進行封包交換時即依據該路由表而進行路由信息處理。然而，由於路由器在進行路由信息處理時需耗費大量的資源，是造成路由器減緩速度的重要原因之一。為了提升第三層(網路層)處理封包交換的效能，因此必須有效地提升路由查詢的能力。對於每一個進入的封包，路由器必須通過此封包的目的地址在其路由表中執行一次IP位址搜尋以決定要送往哪一次落點。每一個路由表中的項目包含目的地址/網路屏蔽和輸出埠號。因CIDR的技術被提出，路由表中的項目被定義為前綴位(prefix)/前綴位的長度和輸出埠號，且該前綴位的長度限制在0到32之間。IP尋址機制即是在路由器中的路由表內，依每一個進入的封包目的地址進行符合最長前綴位的找尋(Longestprefixmatching)，以便找出該封包所對應之次落點(nexthop)。由於此過程較為複雜，目前大多的路由器均使用軟體來實現，然其轉換速度並無法滿足現今網路上龐大的流量，也使得IP位址搜尋成為目前網路上最主要的瓶頸。一種改善路由器查詢能力的方法為已知的間接查表法。該方法首先依照路由表內的前綴位虛擬一相對應的二進位樹形結構12，並定義出各前綴位所佔據的IP位址。之後建立一區段陣列(segmentarray)和多個次落點陣列，而IP尋址機制即是利用該區段陣列和次落點陣列的指引而找出該封包所對應的次落點。圖1(a)至圖1(c)為該間接查表法的一實例。圖1(a)由路由表內的十個前綴位(編號A至J)虛擬至一相對應的二進位樹形結構。圖1(b)定義出各前綴位(編號A至J)所佔據的IP位址。圖1(c)將該前綴位分為兩個半字節組(nibble)，較高的半字節組作為區段陣列13的地址，而較低的半字節組作為多個次落點陣列14、14′和14″的地址，且該區段陣列13和多個次落點陣列14-14″的內容依據編號A至J的各前綴位所佔據的IP位址而填入。例如，該區段陣列13的第一欄記錄次落點(當前綴位的位數小於等於四)或指向次落點陣列14-14″的指標，第二欄為該指標所對應的前綴位的最長偏移k(前綴位的位數減四)，且該指標所對應的次落點陣列14-14″共有2k個內容。該次落點陣列14-14″僅有一欄，用於記錄次落點。待建立該區段陣列13和多個次落點陣列14-14″之內容後，IP尋址機制即可利用封包的IP位址配合該區段陣列13和次落點陣列14-14″的指引，而找出該封包所對應的次落點。然而，上述間接查表法的區段陣列13和多個次落點陣列14-14″在使用上並不具有彈性，且需使用大量存儲器。另一種改善路由器查詢能力的方法揭示於中國臺灣的專利公告號第四一○二九二，發明名稱為「應用於超高速交換式路由器的路由信息建立及IP路徑查詢的方法與系統」的專利說明書中。該方法是通過壓縮的方式而使封包交換時的輸出埠查詢次數不超過三次，且將轉送表的大小限制於512KB以下。然而，上述壓縮方法非常複雜，且當路由器的連接有變更時，其相對的轉送表必須予以重建後才可以得到最完整的路由表，在使用上非常的不方便。綜上所述，為了滿足網路上越來越多的使用者能夠快速的使用，如何建立一個具有高度傳輸效率的路由器，實為目前一件非常重要的課題。
發明內容本發明的主要目的在提供一種路由器的IP位址的建立和尋找方法及其裝置。為達成上述的目的，本發明的IP位址建立和尋找方法及其裝置為有效降低間接查表法的區段陣列的大小，是以24個區段陣列內含為單位，由左至右掃描計算出一16位的壓縮位映射碼或次落點，然後將所得結果置入該第一階轉送表的次落點欄。因此整個區段陣列被分割為212個第一群組，且記錄於該第一階轉送表。當該第一群組的所有16位的值均相同時，則該第一階轉送表的次落點/映射欄記錄一次落點；否則該第一階轉送表的次落點/映射欄記錄一壓縮位映射碼，且指標欄記錄該第二階轉送表的地址。由於壓縮位映射碼的值若為1，則代表該區段陣列的相對應相鄰位值不相等，因此經由累計該壓縮位映射碼的位值為邏輯1的個數即可推得其相對應的該第二階轉送表的內含個數。若前綴位的位數小於16，則該第二階轉送表的次落點/指標欄依據各次落點在區段陣列的順序記錄。反之，該第二階轉送表的次落點/指標欄記錄一指標，且最長偏移欄記錄一最長偏移。若最長偏移的位長度大於4，則需使用第三階轉送表和第四階轉送表，否則僅需使用第三階轉送表。另，依上述方式依序計算出一16位的壓縮位映射碼或次落點，然後將所得結果置入該第三階轉送表的次落點欄。由於本發明是以24個次落點陣列內含進行掃描，因此整個次落點陣列被分割為2length-4個第二群組(length代表前綴位的最長偏移的位數減去IP位數的一半)，且記錄於該第三階轉送表。當該第二群組的所有位的值均相同時，則該第三階轉送表的次落點/映射欄記錄一次落點；否則該第三階轉送表的次落點/映射欄記錄一壓縮位映射碼，且指標欄記錄該第四階轉送表的地址。由於壓縮位映射碼的值若為1，則代表該次落點陣列的相對應相鄰位值不相等，因此經由累計該壓縮位映射碼的位值為邏輯1的個數即可推得其相對應的該第四階轉送表的內含個數。該第四階轉送表僅包含一次落點欄。本發明的路由器的IP位址建立和尋找方法及其裝置是先將佔用存儲器較多的路由表壓縮成較小的轉送表，再予以進行IP尋址。本發明具有下列優點1.存儲器查詢次數介於一次至四次之間，且若使用管線傳輸的方式(pipelinescheme)，則只須一次的存儲器查詢次數。2.當路由表有變更時，不需重建轉送表，且可以很快速地完成更新的動作。3.可使用於靜態隨機處理存儲器(SRAM)。4.所需的存儲器空間很小。本發明將依照後附圖式來說明，其中圖1(a)至1(c)為已知的路由器的IP位址建立和尋找方法及其裝置；圖2為本發明的路由器的IP位址建立和尋找方法及其裝置的一實施例；圖3為本發明建立第一階轉送表和第二階轉送表的一實施例；圖4為本發明建立第三階轉送表和第四階轉送表的一實施例；圖5為本發明建立第一階轉送表和第二階轉送表的流程圖；圖6為本發明建立第三階轉送表和第四階轉送表的流程圖；圖7為綜合圖5和圖6的示意圖；圖8為本發明的IP尋址方法的流程圖；圖9為本發明的IP尋址方法的一實施例；及圖10為本發明的IP尋址裝置的一實施例。具體實施例方式圖2為本發明的路由器的IP位址建立和尋找方法及其裝置的一實施例。為有效降低對存儲器的需求及加快查詢的速度，本實施例採用四組轉送表，分別為第一階轉送表21、第二階轉送表22、第三階轉送表23和第四階轉送表24，其中第一階轉送表21和第二階轉送表22對應至已知的間接查表法的區段陣列13，而第三階轉送表23和第四階轉送表24對應至已知的間接查表法的次落點陣列14。該第一階轉送表21包含一次落點/映射欄211和指標欄212。若該次落點/映射欄211內含一次落點，則該指標欄212為空白(null)；而若該次落點/映射欄211內含一壓縮位映射碼(CompressionBitMap；CBM)，則該指標欄212指向該第二階轉送表22的地址。該第二階轉送表22包含一次落點/指標欄221和最長偏移欄222。若該次落點/指標欄221內含一次落點，則該最長偏移欄222為空白(null)；而若該次落點/指標欄221內含一指標，則該最長偏移欄222內含一最長偏移(longestoffset)的位數。該第三階轉送表23包含一次落點/映射欄231和指標欄232。若該次落點/映射欄231包含一次落點，則該指標欄232為空白(null)；而若該次落點/映射欄231包含一壓縮位映射碼，則該指標欄232指向該第四階轉送表24的地址。該第四階轉送表24僅包含一次落點欄241。為有效降低間接查表法的區段陣列13的大小，本發明以24個區段陣列內含(entry)為單位由左至右掃描計算出一16位的壓縮位映射碼或次落點，然後將所得結果置入該第一階轉送表21的次落點欄211。一般而言，壓縮位映射碼是將最左的位設為邏輯1，其餘的位依據區段陣列的相鄰位而定。若相對應的區段陣列的相鄰位之值不相等，則相對應的壓縮位映射碼為邏輯1，反之則為邏輯0。由於本發明是以24個區段陣列內含為單位進行一次掃描，因此整個區段陣列被分割為212個第一群組，且記錄於該第一階轉送表21。當該第一群組的所有16位之值均相同時，則該第一階轉送表21的次落點/映射欄211記錄一次落點；否則該第一階轉送表21的次落點/映射欄211記錄一壓縮位映射碼，且指標欄212記錄該第二階轉送表22的地址。由於壓縮位映射碼的值若為1，代表該區段陣列的相對應相鄰位值不相等，因此經由累計該壓縮位映射碼的位值為邏輯1的個數即可推得其相對應的該第二階轉送表22的內含個數。若前綴位的位數小於16，則該第二階轉送表22的次落點/指標欄221依據各次落點在區段陣列的順序記錄。反之，該第二階轉送表22的次落點/指標欄221記錄一指標，且最長偏移欄222記錄一最長偏移。圖3為本發明的建立第一階轉送表21和第二階轉送表22的一實施例。由於區段陣列13的前段內含(AAAAAABBPDDDDDDD)的半字節組值SAk[i]並未全部相同，因此一壓縮位映射碼經計算得出1000001011000000。又，因為該壓縮位映射碼具有4個位值為邏輯1的位，因此其相對應的第二階轉送表22具有4個內含。另，區段陣列13的後段內含(CCCCCCCCCCCCCCCC)的半字節組值SAk[i]全部相同，因此該第一階轉送表21的次落點/映射欄211直接儲存C為次落點。以下的演算法可用於產生該第一階轉送表21和第二階轉送表22的內含的值。第一階轉送表和第二階轉送表(L1FT/L2FT)之演算法輸入區段陣列(Segment_array[j])輸出第一階轉送表和第二階轉送表/*SAk[i]代表區段陣列的第k個分群的第i個內含，CBMk[i]代表16位的CBM之值，L1FT[k]代表第一階轉送表的第k內含的值，L2FTk[j]代表第k個第二階轉送表的第j位的內含*/Fork＝0to212-1do{CBMk＝1，flag＝0，j＝0IfSAk＝指標then{建立一相對應的第三階轉送表L2FTk←(第三階轉送表的地址，最長偏移的位長度) j＝1 Flag＝1}Fori＝1to15do{IfSAk[i]＝SAk[i-1]thenCBMk[i]＝0Else{CBMk[i]＝1 flag＝1 IfSAk[i]＝指標then {建立一相對應的L3FT L2FTk[j]＝(第三階轉送表之地址，最長偏移之位長度) } ElseL2FTk[j]←(SAk[i]，空白) j＝j+1 }}<!--SIPO-->Ifflag＝0thenL1FT[k]←(SAk，空白)ElseL1FT[k]←(CBMk，第k個第二階轉送表的地址)}若最長偏移的位長度大於4，則需使用第三階轉送表23和第四階轉送表24，否則僅需使用第三階轉送表23。為有效降低間接查表法的次落點陣列的大小，本發明以24個次落點陣列內含為單位由左至右掃描計算出一16位的壓縮位映射碼或次落點，然後將所得結果置入該第三階轉送表23的次落點欄231。由於本發明是以24個次落點陣列內含進行掃描，因此整個次落點陣列被分割為2length-4個第二群組(length代表前綴位的最長偏移的位數減去IP位數的一半)，且記錄於該第三階轉送表23。當該第二群組的所有位的值均相同時，則該第三階轉送表23的次落點/映射欄231記錄一次落點；否則該第三階轉送表23的次落點/映射欄231記錄一壓縮位映射碼，且指標欄232記錄該第四階轉送表24的地址。由於壓縮位映射碼的值若為1，代表該次落點陣列的相對應相鄰位值不相等，因此經由累計該壓縮位映射碼的位值為邏輯1的個數即可推得其相對應的該第四階轉送表24的內含個數。該第四階轉送表24僅包含一次落點欄241。圖4為本發明的建立第三階轉送表23和第四階轉送表24的一實施例。由於次落點陣列的前段內含(AAAAAABBBDDDDDDD)的半字節組值HNAk[i]並未全部相同，因此一壓縮位映射碼經計算得出1000001001000000。又，因為該壓縮位映射碼具有3個位值為邏輯1的位，因此其相對應的第四階轉送表24具有3個內含。另，次落點矩陣的後段內含(EEEEEEEEEEEEEEEE)的半字節組值HNAk[i]全部相同，因此該第三階轉送表23的次落點/映射欄231直接儲存E為次落點。以下的演算法可用於產生該第三階轉送表23和第四階轉送表24的內含的值。第三階轉送表和第四階轉送表(L3FT/L4FT)的演算法輸入次落點矩陣(Next_hop_array[j])輸出第三階轉送表和第四階轉送表/*NHAk[i]代表第k個次落點矩陣的第i個內含，CBMk[i]代表16位的CBM之值，L3FT[k]代表第三階轉送表的第k內含的值，L4FTk[j]代表第k個第四階轉送表的第j位的內含*/If最長偏移＜4thenL3FT＝NHAElse{Fork＝0to2length-4-1do{ CBMk＝1，flag＝0，j＝0Fori＝1to15do{ IfNHAk[i]＝NHAk[i-1]thenCBMk[i]＝0 Else {CBMk[i]＝1 L4FTk[j]＝NHAk[i] j＝j+1，flag＝1 }} Ifflag＝0thenL3FT[k]←(NHAk[i]，空白) ElseL3FT[k]←(CBMk，L4FTk的地址)}}圖5為本發明的建立第一階轉送表21和第二階轉送表22的流程圖。在步驟50，本發明啟始。在步驟51，依間接查表法求得區段陣列和多個次落點陣列。在步驟52，以24個區段陣列內含為單位進行一次掃描，且將整個區段陣列分割為212個第一群組。在步驟53，判斷是否第一群組的所有16位的值均相同。若答案為肯定的，則進入步驟54，否則進入步驟55。在步驟54，該第一階轉送表的次落點/映射欄記錄一次落點，且指標欄記錄空白。在步驟55，該第一階轉送表的次落點/映射欄記錄一壓縮位映射碼，且指標欄記錄該第二階轉送表的地址。在步驟56，判斷前綴位的位數是否小於16。若答案為肯定的，則進入步驟57，否則進入步驟58。在步驟57，該第二階轉送表的次落點/指標欄依序且不重複地記錄在區段陣列內的次落點，且最長偏移欄記錄0。在步驟58，該第二階轉送表的次落點/指標欄記錄一指標，且最長偏移欄記錄一最長偏移。在步驟59，本發明結束。圖6為本發明的建立第三階轉送表23和第四階轉送表24的流程圖。在步驟60，本發明啟始。在步驟61，第一群組的最長偏移是否大於4。若答案為肯定的，則進入步驟63，否則進入步驟62。在步驟62，利用第三階轉送表記錄次落點。在步驟63，以24個次落點陣列內含進行掃描，且將整個次落點陣列被分割為2length-4個第二群組。在步驟64，第二群組的所有位之值是否均相同。若答案為肯定的，則進入步驟65，否則進入步驟66。在步驟65，該第三階轉送表的次落點/映射欄記錄一次落點，且指標欄填入空白。在步驟66，該第三階轉送表的次落點/映射欄記錄一壓縮位映射碼，且指標欄記錄該第四階轉送表的地址。在步驟67，該第四階轉送表記錄一次落點。在步驟68，本發明結束。圖7為綜合圖5和圖6的示意圖，並據此得到第一至第四階轉送表21-24。圖8為本發明的IP尋址方法的流程圖。在步驟80，本發明啟始。在步驟81，以IP位址的由左起算第0至第11位作為存取第一階轉送表的地址。在步驟82，判斷第一階轉送表的指標欄是否為空白。若答案為肯定的，則進入步驟83，否則進入步驟84。在步驟83，該第一階轉送表的次落點/映射欄得到次落點。在步驟84，由該第一階轉送表的次落點/映射欄得到一壓縮位映射碼，由指標欄得到該第二階轉送表的起始地址，且由IP位址的第12至15位配合該壓縮位映射碼得到該第二階轉送表的相對地址。在步驟85，檢查第二階轉送表的最長偏移欄是否為0。若答案為肯定的，則進入步驟86，否則進入步驟87。在步驟86，該第二階轉送表的次落點/映射欄得到次落點。在步驟87，以該第二階轉送表的最長偏移欄的最長偏移為m，由IP位址的第16至(m+11)位得到該第三階轉送表的相對地址。在步驟88，檢查第三階轉送表的指標欄是否為空白。若答案為肯定的，則進入步驟89，否則進入步驟90。在步驟89，該第三階轉送表的次落點/映射欄得到次落點。在步驟90，由該第三階轉送表的次落點/映射欄得到一壓縮位映射碼，由指標欄得到該第四階轉送表的起始地址，且由IP位址的第(m+12)位至(m+15)位配合該壓縮位映射碼得到該第四階轉送表的相對地址。在步驟91，該第二階轉送表的次落點/映射欄得到次落點。在步驟92，本發明結束。圖9為本發明的IP尋址方法的一實施例，其中為方便敘述，IP位址以8位表示。首先，以IP位址的前兩位(第0和第1位)作為存取第一階轉送表21的地址。若相對應的第一階轉送表21的內含的指標欄212為空白，則該次落點/映射欄211之值即代表次落點。反之，則該次落點/映射欄211之值(1011)代表一壓縮位映射碼。IP位址的第2和第3位用於計算該IP位址位於該壓縮位映射碼的第幾個邏輯1的位，以本例而言，是位於該第二階轉送表22的第二個內含。由於該第二階轉送表22的最長偏移值為3，因此取IP位址的第4位作為存取該第三階轉送表23的地址。若相對應的第三階轉送表23的內含的指標欄232為空白，則該次落點/映射欄231之值即代表次落點。反之，則該次落點/映射欄231之值(1110)代表一壓縮位映射碼。IP位址的第5和第6位用於計算該IP位址位於該壓縮位映射碼的第幾個邏輯1的位，以本例而言，位於該第四階轉送表24的第二個內含。以下的演算法可用於IP查表運算。IP查表運算的演算法輸入第一至第四階轉送表(L1FT至L4FT)輸出次落點/*L1FT[k1].I代表第一階轉送表的第k1個內含的次落點/映射，L1FT[k1].P代表第一階轉送表的第k1個內含的指標，L2FTk1[k2].I代表第二階轉送表的第k2個內含的次落點/映射，L2FTk1[k2].L代表第二階轉送表的第k2個內含的最長偏移值，L3FTk2[k3].I代表第三階轉送表的第k3個內含的次落點/映射，L3FTk2[k3].P代表第三階轉送表的第k3個內含的指標，L4FTk3[k4]代表第四階轉送表的第k4個內含的次落點Get(IP，a，b)代表一函數，其回覆IP位址由左方起算的第a至第b位之值*/j1＝Get(IP，0，11)IfL1FT[k1].P＝空白then回覆L1FT[k1].IElse{j2＝Get(IP，12，15)j3＝L1FT[j1].I之第0至第j2位的具有邏輯1的位個數j3＝j3-1IfL2FTj1[j3].L＝空白then回覆L2FTj1[j3].IIfL2FTj1[j3].L≤4hen回覆 L3FTj3[Get(IP，16，L2FTj1[j3].L+15)].IElse {j4＝Get(IP，16，L2FTj1[j3].L+11)<!--SIPO-->IfL3FTj3[j4].P＝空then回覆L3FTj3[j4].IElse{j5＝Get(IP，16，L2FTj1[j3].L+12，L2FTj1[j3].L+15)j6＝L2FTj3[j4].I的第0至第j5位的邏輯1之個數j6＝j6-1 回覆L4FTj4[j6] }}}圖10為本發明的IP尋址裝置的一實施例，包含一第一階轉送表101(包含16位的次落點/映射欄及16位的指標欄)、一第二階轉送表102(包含16位的次落點/映射欄及8位的最長偏移欄)、一第三階轉送表103(包含16位的次落點/映射欄及16位的指標欄)、一第三階轉送表104(包含8位的次落點欄)、一第四階轉送表105(包含8位的次落點欄)、兩個平行加法器106和107、一比較器108、兩個加法器110和111、一多工器109及兩遮冪器112和112′。IP位址為位0至位31，其中符號DAba代表IP位址的第a位至第b位，而DA110為存取第一階轉送表101的地址。若所存取的指標欄為空白，則將次落點/映射欄的值輸出至該多工器109。該遮冪器112用於轉換DA1512至16位遮冪；若DA1512的值為0001，則16位遮冪為1100000000000000；之值為0010，則16位遮冪為1110000000000000；並依此類推。該平行加法器106用於計算次落點/映射欄的值和經遮冪器112處理後的值的邏輯1的個數，且其輸出作為存取第二階轉送表102的相對地址。該加法器110用於將指標(代表存取第二階轉送表102的起始地址)和該平行加法器106的輸出(代表存取第二階轉送表102的相對地址)相加，且產生存取第二階轉送表102的地址。若所存取的第二階轉送表102的最長偏移欄為0，則將次落點/映射欄的值輸出至該多工器109。該比較器108用於比較最長偏移值是否大於4；若答案是肯定的，則尋找該第三階轉換表103，否則尋找另一第三階轉換表104。該平行加法器107用於計算次落點/映射欄之值和經遮冪器112處理後的值的邏輯1的個數，且其輸出作為存取第四階轉送表105的相對地址。該加法器111用於將指標(代表存取第四階轉送表105的起始地址)和該平行加法器107的輸出(代表存取第四階轉送表105的相對地址)相加，且產生存取第四階轉送表105的地址。該遮冪器112′的功能同遮冪器112，用於轉換DA1512至16位遮冪。該第四階轉送表105的次落點/映射欄之值輸出至該多工器109。表1為本發明和現有的間接查表法及中國臺灣專利公告號第410292的執行效能和硬體需求的比較分析表。經由表1的分析，可確認本發明無論在執行效能和硬體花費的表現上均較現有技藝優良。表1本發明的技術內容及技術特點已揭示如上，然而本專業技術人員仍可能基於本發明的教示及揭示而作種種不背離本發明精神的替換及修飾。因此，本發明的保護範圍應不限於實施例所揭示的內容，而應包括各種不背離本發明的替換及修飾，並為以下之申請專利範圍所涵蓋。權利要求1.一種路由器的IP位址的建立方法，其至少使用第一階轉送表至第四階轉送表來記錄相對於路由表的前綴位和次落點，包含下列步驟依間接查表法求得區段陣列和多個次落點陣列；將區段陣列分割為多個第一群組；若第一群組的IP位址的所有16位的值均相同，則第一階轉送表的次落點/映射欄記錄一次落點且第一階轉送表的指標欄記錄空白，否則該次落點/映射欄記錄一壓縮位映射碼且第一階轉送表的指標欄記錄第二階轉送表的地址；若路由表的前綴位的位數小於16，則第二階轉送表的次落點/指標欄依序且不重複地記錄區段陣列內的次落點且第二階轉送表的最長偏移欄記錄0，否則該第二階轉送表的次落點/指標欄記錄一指標，且第二階轉送表的最長偏移欄記錄一最長偏移；若第一群組的最長偏移大於4，則利用第三階轉送表記錄次落點，否則將次落點陣列分割為多個第二群組；若第二群組的IP位址的所有位的值均相同，則第三階轉送表的次落點/映射欄記錄一次落點且第三階轉送表的指標欄填入空白，否則該第三階轉送表的次落點/映射欄記錄一壓縮位映射碼且該第三階轉送表的指標欄記錄該第四階轉送表的地址；及利用第四階轉送表記錄一次落點。2.如權利要求1所述的路由器IP位址的建立方法，其中所述區段陣列以24個內含為單位進行一次掃描，且將整個區段陣列分割為212個第一群組。3.如權利要求1所述的路由器IP位址的建立方法，其中該次落點陣列以24個內含進行掃描，且將整個次落點陣列分割為2length-4個第二群組，其中length代表最長偏移。4.一種路由器的IP尋址方法，用於如權利要求1所述的路由器IP位址的建立方法中尋找IP位址，包含下列步驟以IP位址的x個位作為存取第一階轉送表的地址；若第一階轉送表的存取內含的指標欄為空白，則由第一階轉送表的次落點/映射欄得到次落點，否則由該第一階轉送表的次落點/映射欄得到一壓縮位映射碼且由該第一階轉送表的指標欄得到該第二階轉送表的起始地址；由IP位址的其餘16-x位配合該壓縮位映射碼得到該第二階轉送表之相對地址；若該第二階轉送表的存取內含的最長偏移欄為0，則由該第二階轉送表的次落點/映射欄得到次落點，否則以該第二階轉送表的最長偏移欄的最長偏移m，由IP位址的第16至(m+11)位得到該第三階轉送表的相對地址；若該第三階轉送表的存取內含的指標欄為空白，則由該第三階轉送表的次落點/映射欄得到次落點，否則由該第三階轉送表的次落點/映射欄得到一壓縮位映射碼，且由該第三階轉送表的指標欄得到該第四階轉送表的起始地址；由IP位址的第(m+12)位至(m+15)位配合該壓縮位映射碼得到該第四階轉送表的相對地址；且由該第四階轉送表的存取內含的次落點/映射欄得到次落點。5.如權利要求4所述的路由器的IP尋址方法，其中以IP位址的左起第0至第11位作為存取第一階轉送表的地址。6.一種路由器的IP尋找裝置，用於如權利要求1所述的路由器的IP位址建立方法中尋找IP位址，包含一第一階轉送表，包含次落點/映射欄及指標欄，且該第一階轉送表以該IP位址的x個位作為存取地址；一第一遮冪器，用於遮冪該IP位址的其餘16-x個位；一第一平行加法器，連接至該第一階轉送表的次落點/映射欄和該第一遮冪器，用於產生存取該第二階轉送表的相對地址；一第一加法器，用於加總該第一階轉送表的指標和該第一平行加法器的輸出；一第二階轉送表，包含次落點/映射欄及最長偏移欄，且該第二階轉送表以該第一加法器的輸出作為存取地址；一第三階轉送表，包含次落點/映射欄及指標欄，且該第三階轉送表以該第二階轉送表的最長偏移欄的最長偏移索引該IP位址而作為其存取地址；一第二遮冪器，用於遮冪該IP位址的其餘16-x位；一第二平行加法器，連接至該第三階轉送表的次落點/映射欄和該第二遮冪器，用於產生存取該第四階轉送表的相對地址；一第二加法器，用於加總該第三階轉送表的指標和該第二平行加法器的輸出；一第四階轉送表，包含次落點欄，且該第四階轉送表以該第二加法器的輸出作為存取地址；及一多工器，連接至該第一階轉送表的次落點/映射欄、該第二階轉送表的次落點/指標欄、該第三階轉送表的次落點/映射欄及該第四階轉送表的次落點欄。7.如權利要求6所述的IP尋找裝置，其還包含一比較器及一僅包含次落點欄的第三階轉送表，若第二階轉送表的最長偏移值大於4，則尋找該包含次落點/映射欄和指標欄的第三階轉換表，否則尋找該僅包含次落點欄的第三階轉換表。8.如權利要求6所述的路由器之IP尋找裝置，其中該第一階轉送表以IP位址的左起第0至第11位作為存取地址。全文摘要本發明揭示一種路由器的IP位址的建立和尋找方法及其裝置，其利用壓縮的技巧將間接查表法的區段陣列和多個次落點陣列所需的存儲器空間予以有效地降低，且存儲器查詢次數介於一次至四次之間，而若使用管線傳輸的方式，則只須一次的存儲器查詢次數。此外，當路由表有變更時，本發明不需重建轉送表，且可以很快速地完成更新的動作。文檔編號H04L29/12GK1412975SQ0113547公開日2003年4月23日申請日期2001年10月15日優先權日2001年10月15日發明者賓少鈺,伍麗樵申請人:智邦科技股份有限公司