CA2303118A1 - Procede et systeme de recherche rapide d'acheminement - Google Patents
Procede et systeme de recherche rapide d'acheminement Download PDFInfo
- Publication number
- CA2303118A1 CA2303118A1 CA002303118A CA2303118A CA2303118A1 CA 2303118 A1 CA2303118 A1 CA 2303118A1 CA 002303118 A CA002303118 A CA 002303118A CA 2303118 A CA2303118 A CA 2303118A CA 2303118 A1 CA2303118 A1 CA 2303118A1
- Authority
- CA
- Canada
- Prior art keywords
- bit
- chunk
- array
- level
- hop
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Abandoned
Links
- 238000000034 method Methods 0.000 title claims abstract description 28
- 238000013461 design Methods 0.000 description 10
- 230000006870 function Effects 0.000 description 10
- 238000004891 communication Methods 0.000 description 6
- 230000006854 communication Effects 0.000 description 6
- 238000005259 measurement Methods 0.000 description 6
- 238000012545 processing Methods 0.000 description 6
- 241000238876 Acari Species 0.000 description 5
- 238000013507 mapping Methods 0.000 description 5
- 241000712062 Patricia Species 0.000 description 4
- 238000002474 experimental method Methods 0.000 description 4
- ACWBQPMHZXGDFX-QFIPXVFZSA-N valsartan Chemical class C1=CC(CN(C(=O)CCCC)[C@@H](C(C)C)C(O)=O)=CC=C1C1=CC=CC=C1C1=NN=NN1 ACWBQPMHZXGDFX-QFIPXVFZSA-N 0.000 description 4
- 238000005457 optimization Methods 0.000 description 3
- 230000008569 process Effects 0.000 description 3
- 238000013459 approach Methods 0.000 description 2
- 238000003491 array Methods 0.000 description 2
- 239000000470 constituent Substances 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 2
- 238000000605 extraction Methods 0.000 description 2
- 239000004744 fabric Substances 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 230000008929 regeneration Effects 0.000 description 2
- 238000011069 regeneration method Methods 0.000 description 2
- 239000011800 void material Substances 0.000 description 2
- 238000007792 addition Methods 0.000 description 1
- 238000004458 analytical method Methods 0.000 description 1
- 230000006399 behavior Effects 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000018109 developmental process Effects 0.000 description 1
- 239000003102 growth factor Substances 0.000 description 1
- 230000001788 irregular Effects 0.000 description 1
- 230000007246 mechanism Effects 0.000 description 1
- 239000000203 mixture Substances 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- REQCZEXYDRLIBE-UHFFFAOYSA-N procainamide Chemical compound CCN(CC)CCNC(=O)C1=CC=C(N)C=C1 REQCZEXYDRLIBE-UHFFFAOYSA-N 0.000 description 1
- 230000035755 proliferation Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 230000011664 signaling Effects 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
- 238000012360 testing method Methods 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
L'invention concerne un procédé de recherche d'acheminement Internet dans une table d'acheminement comportant des rubriques préfixes de longueur arbitraire associées à des informations Saut Suivant dans une table Saut Suivant. Ce procédé permet de déterminer où des datagrammes Internet doivent être envoyés. Une représentation de la table d'acheminement est mémorisée sous la forme d'un arbre de préfixes complet (7), défini par les préfixes de toutes les rubriques de la table d'acheminement. En outre, une représentation du vecteur binaire (8) contenant les données d'une coupe transversale de l'arbre de préfixes (7) à une profondeur courante (D) et un ensemble de pointeurs comprenant des indices désignant la table Saut Suivant et un fragment Niveau Suivant sont mémorisés. Ledit vecteur binaire (8) est divisé en des masques binaires et une représentation de ces masques binaires est mémorisée dans une table de correspondances. Ensuite, un ensemble de mots de code, chacun codant une rangée d'indices dans la table de correspondances et un décalage de pointeur, ainsi qu'un ensemble d'adresses de base sont mémorisées. La recherche est enfin effectuée.
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| SE9703332A SE9703332D0 (sv) | 1997-05-09 | 1997-09-15 | Method and system for fast routing lookups |
| SE9703332-8 | 1997-09-15 | ||
| PCT/SE1998/000854 WO1999014906A1 (fr) | 1997-09-15 | 1998-05-11 | Procede et systeme de recherche rapide d'acheminement |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CA2303118A1 true CA2303118A1 (fr) | 1999-03-25 |
Family
ID=20408258
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CA002303118A Abandoned CA2303118A1 (fr) | 1997-09-15 | 1998-05-11 | Procede et systeme de recherche rapide d'acheminement |
Country Status (7)
| Country | Link |
|---|---|
| JP (1) | JP2001517024A (fr) |
| KR (1) | KR20010030607A (fr) |
| CA (1) | CA2303118A1 (fr) |
| EA (1) | EA200000328A1 (fr) |
| ID (1) | ID24241A (fr) |
| IL (1) | IL134835A0 (fr) |
| SK (1) | SK3692000A3 (fr) |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3570323B2 (ja) * | 1999-05-11 | 2004-09-29 | 日本電気株式会社 | アドレスに関するプレフィクスの格納方法 |
| EP1250775A2 (fr) * | 1999-12-10 | 2002-10-23 | Mosaid Technologies Incorporated | Procede et appareil pour la plus longue consultation d'adresses de correspondance |
| KR100364433B1 (ko) * | 2000-04-28 | 2002-12-11 | 학교법인 동국학원 | 비트-벡터 테이블을 이용한 ｉｐ 주소 검색방법 |
| US7966421B2 (en) | 2000-06-21 | 2011-06-21 | SAtech Group, A.B. Limited Liability Company | Method and apparatus for logically expanding the length of a search key |
| KR100493099B1 (ko) * | 2000-12-22 | 2005-06-02 | 삼성전자주식회사 | 고속 인터넷프로토콜 라우터의 라우팅/포워딩 룩업 및라우팅 테이블 관리 |
| KR100378599B1 (ko) * | 2001-04-02 | 2003-04-03 | 한국전자통신연구원 | 주소 메모리 블록의 간섭 인덱싱에 기반한 라우팅 테이블검색 방법 |
| KR20020067469A (ko) * | 2002-07-25 | 2002-08-22 | 크로스반도체기술 주식회사 | Ip 패킷의 목적지 어드레스 룩업 시스템 및 그 방법 |
| ES2766861T3 (es) * | 2013-01-29 | 2020-06-15 | Huawei Tech Co Ltd | Método de procesamiento de paquetes y elemento de reenvío |
| JP6016215B2 (ja) | 2013-12-20 | 2016-10-26 | インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ | トライ木構造を有するレコード群を高い効率でマージソートする方法、装置及びコンピュータプログラム |
| JP5960863B1 (ja) * | 2015-03-11 | 2016-08-02 | エヌ・ティ・ティ・コミュニケーションズ株式会社 | 検索装置、検索方法、プログラム、及び記録媒体 |
| JP6205463B2 (ja) * | 2016-06-23 | 2017-09-27 | エヌ・ティ・ティ・コミュニケーションズ株式会社 | 検索装置、検索方法、プログラム、及び記録媒体 |
| JP6946937B2 (ja) * | 2017-10-31 | 2021-10-13 | 日本電信電話株式会社 | ネットワーク制御装置、アドレス設計方法およびアドレス設計プログラム |
-
1998
- 1998-05-11 IL IL13483598A patent/IL134835A0/xx unknown
- 1998-05-11 KR KR1020007002749A patent/KR20010030607A/ko not_active Withdrawn
- 1998-05-11 ID IDW20000478A patent/ID24241A/id unknown
- 1998-05-11 SK SK369-2000A patent/SK3692000A3/sk unknown
- 1998-05-11 CA CA002303118A patent/CA2303118A1/fr not_active Abandoned
- 1998-05-11 EA EA200000328A patent/EA200000328A1/ru unknown
- 1998-05-11 JP JP2000512323A patent/JP2001517024A/ja active Pending
Also Published As
| Publication number | Publication date |
|---|---|
| ID24241A (id) | 2000-07-13 |
| JP2001517024A (ja) | 2001-10-02 |
| SK3692000A3 (en) | 2000-09-12 |
| IL134835A0 (en) | 2001-05-20 |
| EA200000328A1 (ru) | 2000-10-30 |
| KR20010030607A (ko) | 2001-04-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6266706B1 (en) | Fast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagrams | |
| Degermark et al. | Small forwarding tables for fast routing lookups | |
| Zane et al. | CoolCAMs: Power-efficient TCAMs for forwarding engines | |
| US6985483B2 (en) | Methods and systems for fast packet forwarding | |
| Dharmapurikar et al. | Longest prefix matching using bloom filters | |
| Waldvogel et al. | Scalable high speed IP routing lookups | |
| Dharmapurikar et al. | Longest prefix matching using bloom filters | |
| US8200686B2 (en) | Lookup engine | |
| US8780926B2 (en) | Updating prefix-compressed tries for IP route lookup | |
| Tzeng et al. | On fast address-lookup algorithms | |
| Waldvogel et al. | Scalable high-speed prefix matching | |
| Warkhede et al. | Multiway range trees: scalable IP lookup with fast updates | |
| US20040167923A1 (en) | Method and apparatus for longest matching prefix determination in a communication network | |
| JP2005198285A (ja) | ハードウエアにおけるｉｐルックアップソリューションを効率的に実現するためにハッシングを使用する装置及び方法 | |
| CA2303118A1 (fr) | Procede et systeme de recherche rapide d'acheminement | |
| US6996559B1 (en) | IP address resolution methods and apparatus | |
| WO2002098055A2 (fr) | Equilibrage des charges dans une recherche d'adresse ip | |
| Yu et al. | Forwarding engine for fast routing lookups and updates | |
| US20050114393A1 (en) | Dynamic forwarding method using binary search | |
| WO2001022667A1 (fr) | Procede et systeme destines a la compression de table de routage et a la consultation rapide du routage | |
| Li et al. | Address lookup algorithms for IPv6 | |
| Wang et al. | A fast table update scheme for high-performance IP forwarding | |
| Chang et al. | Efficient IP routing table lookup scheme | |
| Wang et al. | Efficient entry-reduction algorithm for TCAM-based IP forwarding engine | |
| GB2407674A (en) | Lookup engine |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FZDE | Discontinued |