EP0365337A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for accessing data in a table and its application to the routing of data between remote stations
Assignee: HP Inc
•
Filing: 1989-10-20
•
Granted: —
•
Expires: 2009-10-20
Abstract
Abstract The present invention relates to the accessing data in tables and its application to apparatus for providing a communication bridge interconnecting two or more local area networks (LAN). A LAN (1) is connected to another LAN 2 by means of a bridge generally designated by the numeral (3). Input buffers (11, 21) forward packet headers of received data packets through to a routing engine (5). The routing engine (5) contains one or more routing tables each having a plurality of table locations containing table data in the form of station addresses and routing data. The table is accessed by applying a hashing algorithm to a received destination address contained in the data packet to determine the table location and then checking that the station address retrieved from the table location corresponds with the destination address in the received data packet. If the table location is empty or the destination address does not match the station address, the data packet is forwarded to all interconnected LANs. Otherwise, the data packet is forwarded according to the retrieved routing data. Embodiments are described wherein the table locations are over-written by applying the hashing algorithm to the source address of a received data packet and writing in at the resultant table location the source address and routing information of the received data packet. A time stamp can also be written at this time so that obsolete data entries are not employed for routing.
Inventors
- 👤 Alan David Marshall
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-27 06:04
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/28; H04L12/46; H04L12/4604; H04L12/462; H04L12/4625; H04L45/00; H04L45/74; H04L45/745
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
121 words
A method for accessing a datum from data that have been sorted in a table at locations determined by applying one or more hashing algorithms to at least a part of each datum, the method comprising applying one or more hashing algorithms to said part of the datum and accessing a table location on the basis thereof, comparing the said part of the datum in the table location with the said part of the datum being accessed, and, if the parts correspond, retrieving the datum stored in the table location, the method being characterised by the fact that the number of table accesses which can be made in order to locate said corresponding parts is limited to a predefined maximum number.
Claim 2
Independent Claim
121 words
A method for accessing a datum from data that have been sorted in a table at locations determined by applying one or more hashing algorithms to at least a part of each datum, the method comprising applying one or more hashing algorithms to said part of the datum and accessing a table location on the basis thereof, comparing the said part of the datum in the table location with the said part of the datum being accessed, and, if the parts correspond, retrieving the datum stored in the table location, the method being characterised by the fact that the number of table accesses which can be made in order to locate said corresponding parts is limited to a predefined maximum number.
Claim 3
Independent Claim
174 words
A method for controlling the routing of data packets between stations where the route for transmission of the packets needs to be determined, the data packets including a destination address indicative of the station to which the packet is to be routed, the method comprising the steps of:- storing table data at table locations of a routing table or tables, the table data comprising station addresses together with the respective routing data; receiving data packets at a routing table; applying a hashing algorithm to the destination address of a data packet when received and on the basis thereof accessing a said table location to retrieve routing data and said station address therefrom; and, after one or a predefined limited number of hash probes, forwarding the data packet onto all or a given number of routes if the accessed table location is empty or does not contain a station address corresponding to said data packet destination address, or, in the event that the addresses correspond forwarding the data packet according to the retrieved routing data.
Claim 4
Independent Claim
174 words
A method for controlling the routing of data packets between stations where the route for transmission of the packets needs to be determined, the data packets including a destination address indicative of the station to which the packet is to be routed, the method comprising the steps of:- storing table data at table locations of a routing table or tables, the table data comprising station addresses together with the respective routing data; receiving data packets at a routing table; applying a hashing algorithm to the destination address of a data packet when received and on the basis thereof accessing a said table location to retrieve routing data and said station address therefrom; and, after one or a predefined limited number of hash probes, forwarding the data packet onto all or a given number of routes if the accessed table location is empty or does not contain a station address corresponding to said data packet destination address, or, in the event that the addresses correspond forwarding the data packet according to the retrieved routing data.
Claim 5
Dependent Claim
16 words
A method as claimed in claim 1 or claim 2 wherein said limited number is one.
Claim 6
Dependent Claim
165 words
A method as claimed in claim 2 or claim 3 wherein the step of storing said table data includes the step of over over-writing table locations with data derived from a received data packet, each of which also includes a source address indicative of the source station, the table location being selected by applying said hashing algorithm to the source address of the data packet when received, and if the table location is empty or the source address of the received packet corresponds to the existing station address in the table location, entering a station address together with routing information into said table location, said station address being the source address of the received packet, or if the source address of the received packet does not correspond to the station address of the table location, entering a station address together with routing information into a table location after said predefined number of hash probes, said station address being the source address of the received packet.
Claim 7
Independent Claim
88 words
A method as claimed in any one of claims 2 to 4 which provides a communication bridge to route data packets containing a source address and destination address, the bridge interconnecting two or more Local Area Networks (LAN's) in which the stations have unique addresses wherein after said predefined limited number of hash probes the data packet is forwarded onto all LAN's other than the one from which the packet was received if the accessed table location is empty or does not contain a said corresponding station address.
Claim 8
Dependent Claim
179 words
Apparatus for controlling the routing of data packets between stations where the route for transmission of the packet needs to be determined, the data packets including a destination address indicative of the station to which the packet is to be routed, the apparatus comprising means providing a routing table (31) in which are stored table data at table locations thereof, the table data comprising station addresses together with the respective routing data; hashing means (34) to apply a hashing algorithm to the destination address of a received data packet and accessing a said table location on the basis thereof to retrieve the routing data and said station address therefrom; and routing means (5) operative, after one or a predefined limited number of hash probes, to forward the data packet onto all or a given number of routes if the accessed table location is empty or does not contain a station address corresponding to the destination address of the received data packet, or, in the event that the addresses correspond forwarding the data packet according to the retrieved routing data.
Claim 9
Dependent Claim
179 words
Apparatus for controlling the routing of data packets between stations where the route for transmission of the packet needs to be determined, the data packets including a destination address indicative of the station to which the packet is to be routed, the apparatus comprising means providing a routing table (31) in which are stored table data at table locations thereof, the table data comprising station addresses together with the respective routing data; hashing means (34) to apply a hashing algorithm to the destination address of a received data packet and accessing a said table location on the basis thereof to retrieve the routing data and said station address therefrom; and routing means (5) operative, after one or a predefined limited number of hash probes, to forward the data packet onto all or a given number of routes if the accessed table location is empty or does not contain a station address corresponding to the destination address of the received data packet, or, in the event that the addresses correspond forwarding the data packet according to the retrieved routing data.
Claim 10
Dependent Claim
12 words
Apparatus as claimed in claim 6 wherein said limited number is one.
Claim 11
Dependent Claim
46 words
Apparatus as claimed in claim 6 or claim 7 wherein a plurality of routing tables (31) are connected in parallel; and a plurality of hashing means (34) are provided, each connected to a respective routing table for employing an independent hashing algorithm to retrieve table data.
Claim 12
Dependent Claim
149 words
Apparatus as claimed in any one of claims 6 to 8 wherein each packet include a source address and the or each routing table has a respective writing means operative to apply the table hashing algorithm to the source address of a received data packet and, on the basis thereof, if the table location is empty or the source address of the received packet corresponds to the existing station address in the selected location, entering a station address together with routing information into said table location, said station address being the source address of the received packet, or if the source address of the received packet does not correspond to the station address of the selected table location, entering a station address together with routing information into a table location after said predefined number of hash probes, said station address being the source address of the received data packet.
Claim 13
Dependent Claim
93 words
Apparatus as claimed in any one of claims 6 to 9 wherein the apparatus provides communication bridges (3) to route data packets containing a source address and a destination address, the bridge interconnecting two or more Local Area Networks (LAN's) (1, 2) in which the stations have unique address, and wherein after said predefined limited number of hash probes the data packet is forwarded onto all LAN's other than the one from which the packet was received if the accessed table location is empty or does not contain a said corresponding station address.
Claim 14
Dependent Claim
49 words
Apparatus as claimed in claim 9 or claim 10 wherein each written table location includes a time stamp and said routing means is also operative to forward the data packet onto the LANs if the date stamp of a retrieved table location is at least a predetermined time ago.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.