US5761440A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method utilizing multiple search trees to route data within a data processing network
Assignee: International Business Machines Corp
•
Filing: 1994-09-15
•
Granted: 1998-06-02
•
Expires: 2014-09-15
Abstract
Abstract A system and method for efficiently routing data within a network, such as a local area network. A search tree is utilized within the bridge/router in order to store addresses. The search tree is utilized by the router for more efficiently and more quickly determining where one or more received frames of data are to be transmitted within the network. Maintenance of the search trees is also provided so that new addresses may be added to the search trees and addresses may be deleted from the search trees. The search trees are developed by partitioning the addresses into bit groups.
Inventors
- 👤 Jose Geraldo Bueno De Marco
- 👤 Jeffrey Wayne Kidd
- 👤 Edward Hau-Chun Ku
- 👤 Karen Park Heron
- 👤 Simin Hosne Sanaye
- 👤 Luis Filipe de Sousa Silva
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 23:37
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/48
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
122 words
A method for routing data in a data processing system, wherein said data is associated with a destination address within said system, said method comprising the steps of: comparing said destination address to a database of destination addresses by comparing a first portion of said destination address to a first partition of said database, wherein a subsequent comparison of a second portion of said destination address to a second partition of said database occurs when the first portion of said destination address and the first partition of said database match; and routing said data to said destination when said first and second portions of said destination address are matched with a corresponding one of the first and second partitions of said database.
Claim 2
Independent Claim
122 words
A method for routing data in a data processing system, wherein said data is associated with a destination address within said system, said method comprising the steps of: comparing said destination address to a database of destination addresses by comparing a first portion of said destination address to a first partition of said database, wherein a subsequent comparison of a second portion of said destination address to a second partition of said database occurs when the first portion of said destination address and the first partition of said database match; and routing said data to said destination when said first and second portions of said destination address are matched with a corresponding one of the first and second partitions of said database.
Claim 3
Dependent Claim
25 words
The method as recited in claim 1 wherein said first and second partitions of said database of destination addresses are arranged in a search tree.
Claim 4
Dependent Claim
54 words
The method as recited in claim 1 wherein each of the first and second partitions of said database includes a pointer to a subsequent partition, said pointer operable to initiate said subsequent comparison only when a previous comparison operation indicates a previous portion of said destination address matches a previous partition of said database.
Claim 5
Dependent Claim
31 words
The method as recited in claim 2, further comprising the step of: adding an unmatched portion of said destination address to said search tree when a portion/partition pair do not match.
Claim 6
Dependent Claim
17 words
The method as recited in claim 1 wherein said system comprises a network of data processing devices.
Claim 7
Independent Claim
162 words
A system adaptable for routing data between data processing devices within a network, said system comprising: interface means adaptable for communicating data with said data processing devices, wherein said data includes a destination address associated with one of said processing devices; means for comparing a plurality of portions of said destination address to a plurality of addresses stored in one or more search trees, wherein said plurality of addresses are associated with said data processing devices, a first one of the plurality of portions of said destination address matching a first one of the plurality of addresses before a second one of the plurality of portions of said destination address may be compared with a second one of the plurality of addresses; and means adaptable for transmitting said data to one of said data processing devices through said interface means when said comparing means matches each of the plurality of portions of said destination address to one of said plurality of addresses.
Claim 8
Independent Claim
162 words
A system adaptable for routing data between data processing devices within a network, said system comprising: interface means adaptable for communicating data with said data processing devices, wherein said data includes a destination address associated with one of said processing devices; means for comparing a plurality of portions of said destination address to a plurality of addresses stored in one or more search trees, wherein said plurality of addresses are associated with said data processing devices, a first one of the plurality of portions of said destination address matching a first one of the plurality of addresses before a second one of the plurality of portions of said destination address may be compared with a second one of the plurality of addresses; and means adaptable for transmitting said data to one of said data processing devices through said interface means when said comparing means matches each of the plurality of portions of said destination address to one of said plurality of addresses.
Claim 9
Dependent Claim
91 words
The system as recited in claim 6 wherein said data includes a source address associated with one of said processing devices from which said data originated, said system further comprising: means for comparing said source address to said plurality of addresses stored in said one or more search trees; and means for appending said source address to one of said one or more search trees when said means for comparing does not match said source address to one of said plurality of addresses stored in said one or more search trees.
Claim 10
Dependent Claim
36 words
The system recited in claim 6, further comprising: means for discarding said data when said means for comparing matches said destination address with an address associated with one of said devices from which said data originated.
Claim 11
Dependent Claim
51 words
The system as recited in claim 6, further comprising: means adaptable for broadcasting said data to all of said processing devices through said interface means when said means for comparing does not match said destination address to one of said plurality of addresses stored in said one or more search trees.
Claim 12
Dependent Claim
26 words
The system as recited in claim 6, further comprising: means for deleting one of said plurality of addresses stored in said one or more search trees.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-01 | 2001-12-01 | 2002-06-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-01 | 2005-12-01 | 2006-06-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-01 | 2009-12-01 | 2010-06-02 | $7700.00 | Window Closed / Lapsed |