| 主权项 |
1.一种路由方法,用于执行于一路由系统中,该路由系统具有一全路由表,该全路由表储存该路由系统所应处理之复数路由字首,及该复数路由字首所对应的复数路由资料,该路由方法包括下列步骤:该路由系统利用复数路由快取记忆体建立m个路由表,分别为第一~第m快取路由表;其中,该第一快取路由表储存复数L1位元之路由字首及该复数路由字首所对应的复数路由资料;该第二快取路由表储存复数L2位元之路由字首及该复数路由字首所对应的复数路由资料;依此类推,该第m快取路由表储存复数Lm位元之路由字首及该复数路由字首所对应的复数路由资料;其中m为正整数且0<L1<L2<…<Lm;接收一Lm位元之目的端位址的网路封包;将该目的端位址的前L1位元在该第一快取路由表中进行搜寻,同时将该目的端位址的前L2位元在该第二快取路由表中进行搜寻,依此类推,同时将该目的端位址的前Lm位元在该第m快取路由表中进行搜寻;以及当于第n快取路由表中搜寻到与该目的端位址的前Ln位元相同之路由字首时,依据该路由字首所对应的路由资料,将该网路封包传出,其中n为正整数且1≦n≦m。2.如申请专利范围第1项所述之路由方法,更包括下列步骤:当于该第一~第m快取路由表中都搜寻不到与该目的端位址的前L1,L2,…,Lm位元相同之路由字首时,在该全路由表中查询该目的端位址所对应的路由资料;以及依据该路由资料,将该网路封包传出,并判断该路由资料属于该第一~第m快取路由表中的那一个快取路由表,并将该目的端位址之前Lp位元以及该路由资料,交由第p快取路由表储存,其中p表示该路由资料属于第p快取路由表。3.如申请专利范围第2项所述之路由方法,其中建立该路由系统之该全路由表的步骤包括:将该路由系统所应处理之路由字首依次加入,以形成一路由字首树;每加入一路由字首而为一节点时,检查该路由字首之长度是否超过Li位元;以及当该路由字首之长度超过Li位元时,于该节点之路由字首长度为Li位元之父节点设定一Li标记,其中i为正整数且1≦n<m。4.如申请专利范围第3项所述之路由方法,其中建立该路由系统之该全路由表尚包括下列子步骤:当该路由字首之长度超过Li位元,而该节点之路由字首长度为Li位元之父节点不存在时,先建立对应之路由字首长度为Li位元之父节点,而于该父节点设定一Li标记。5.如申请专利范围第2项所述之路由方法,其中判断该路由资料属于该第一~第m快取路由表中的那一个快取路由表的步骤包括:于该含路由表中搜寻时,若没有经过已设定标记的节点,则所查询到之路由资料属于第一快取路由表;若有经过已设定标记的节点,且最后经过已设定标记的节点的标记为Li,则所查询到之路由资料属于第i+1快取路由表,其中i为正整数且1≦i<m。6.如申请专利范围第1项所述之路由方法,其中m为2,而L1为24且L2为32。7.如申请专利范围第1项所述之路由方法,其中m为3,而L1为16.L2为24且L3为32。8.如申请专利范围第1项所述之路由方法,其中m为4,而L1为24.L2为48.L3为64且L4为128。9.如申请专利范围第1项所述之路由方法,其中该路由快取记忆体为二元内容定址记忆体(Binary Content Addressable Memory)。10.一种路由系统,其包括:一第一路由装置,其包括:一目的端位址接收单元,其接收一长度为Lm位元之目的端位址的网路封包;复数路由快取记忆体,其耦接至该目的端位址接收单元以接收该网路封包,包括复数快取路由表,分别为第一~第m快取路由表;其中,该第一快取路由表储存复数长度为L1位元之路由字首及所对应的复数路由资料,并依据该目的端位址的前L1位元在该第一快取路由表中搜寻和该目的端位址的前L1位元相同之路由字首之所对应的路由资料;该第二快取路由表储存复数长度为L2位元之路由字首及所对应的复数路由资料,并依据该目的端位址的前L2位元在该第二快取路由表中搜寻和该目的端位址的前L2位元相同之路由字首之所对应的路由资料;依此类推,该第m快取路由表储存复数长度为Lm位元之路由字首及所对应的复数路由资料,并依据该目的端位址的所有Lm位元在该第m快取路由表中搜寻和该目的端位址的所有Lm位元相同之路由字首之所对应的路由资料;其中m为正整数且0<L1<L2<…<Lm;以及一选择单元,其耦接至该复数路由快取记忆体,用以判断是否于该第一~第m快取路由表中搜寻到与该目的端位址的前L1,L2,…,Lm位元相同之路由字首;以及一第二路由装置,其包括:一全路由表,用以储存该路由系统所应处理之复数路由字首,及该复数路由字首所对应的复数路由资料,其耦接至该选择单元,于该第一~第m快取路由表中都没有搜寻到与该目的端位址的前L1,L2,…,Lm位元相同之路由字首时,在该全路由表中查询该目的端位址对应的一路由资料;以及一传送单元,其耦接该全路由表及该选择单元,依据上述路由资料,将该网路封包传出。11.如申请专利范围第10项所述之路由系统,更包括:一分配单元,用于在该第二路由装置的全路由表查询到该目的端位址所对应的路由资料时,判断该路由资料属于该第一~第m快取路由表中的那一个快取路由表,并将该目的端位址之前Lp位元以及该路由资料,交由第p快取路由表储存,其中p表示该路由资料属于第p快取路由表。12.如申请专利范围第11项所述之路由系统,其中该全路由表建立于该第二路由装置中,而将该路由系统所应处理之路由字首依次加入,为一路由字首树;每加入一路由字首而为一节点时,检查该路由字首之长度是否超过Li位元;当该路由字首之长度超过Li位元时,于该节点之路由字首长度为Li位元之父节点设定一Li标记;其中,当该路由字首之长度超过Li位元,而该节点之路由字首长度为Li位元之父节点不存在时,先建立对应之路由字首长度为Li位元之父节点,而于该父节点设定一Li标记;其中i为正整数且1≦n<m。13.如申请专利范围第12项所述之路由系统,其中该分配单元藉着判断于该全路由表中搜寻时,若没有经过已设定标记的节点,则所查询到之路由资料属于第一快取路由表;若有经过已设定标记的节点,且最后经过已设定标记的节点的标记为Li,则所查询到之路由资料属于第i+1快取路由表,其中i为正整数且1≦i<m。14.如申请专利范围第10项所述之路由系统,其中m为2,而L1为24且L2为32。15.如申请专利范围第10项所述之路由系统,其中该路由快取记忆体为二元内容定址记忆体(Binary Content Addressable Memory)。图式简单说明:第1图系表示本发明实施例的路由方法之处理过程的示意图。第2图系表示本发明实施侧中对于无法在路由快取记忆体中找到该目的端位址所对应的路由资料时之处理过程的示意图。第3a图系表示本发明实施例中建立全路由表的一范例示意图。第3b图系表示本发明实施例中建立全路由表的另一范例示意图。第4图系表示本发明实施例之路由系统的方块图。 |
