US5434799A - Method and apparatus for recognizing data traveling on a data transmission network using a dichotomizing search process - Google Patents

Method and apparatus for recognizing data traveling on a data transmission network using a dichotomizing search process Download PDF

Info

Publication number
US5434799A
US5434799A US08/037,583 US3758393A US5434799A US 5434799 A US5434799 A US 5434799A US 3758393 A US3758393 A US 3758393A US 5434799 A US5434799 A US 5434799A
Authority
US
United States
Prior art keywords
search
search table
dichotomizing
low
station
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.)
Expired - Lifetime
Application number
US08/037,583
Other languages
English (en)
Inventor
Bernard Aguilhon
Jean-Francois Karcher
Jean-Hughes Potiron
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Telemecanique SA
Original Assignee
Telemecanique SA
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Telemecanique SA filed Critical Telemecanique SA
Assigned to TELEMECANIQUE S.A. reassignment TELEMECANIQUE S.A. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: AGUILHON, BERNARD, KARCHER, JEAN-FRANCOIS, POTIRON, JEAN-HUGHES
Application granted granted Critical
Publication of US5434799A publication Critical patent/US5434799A/en
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
    • G06F15/161—Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning

Definitions

  • This invention relates to a method and apparatus for recognizing data traveling on a data transmission network by receiving, in a station of the network, identifiers.
  • the identifiers each have a bit field for indicating if the identifiers belong to the reference identifiers attached to the station.
  • a data transmission network particularly in an industrial environment (a so-called ground network, for example) includes, in reference to FIG. 1, stations that are interconnected, through communication interfaces, by a transmission line 1 called a bus.
  • Each of the stations transmits and receives on the network, data items; each data item constituting a field, i.e., an indivisible unit of bits.
  • An identifier, a bit field or byte corresponding to each data item transmitted, allows the identification of the data item.
  • each station determines if a particular data item is intended for the station. If it is intended for the station, information in the data item is given to that station.
  • each of the stations comprises a memory containing all of the identifiers which are associated with it.
  • a first known technique includes, at each station, a memory that can hold all the possible identifiers. By way of indication, this memory will have 2 16 entries for 16-bit identifiers. It associates, with each identifier relating to the station, the address of the corresponding service specification. This technique exhibits the advantage of speed of recognition since the identifier itself constitutes the memory address, but the technique is restricting in memory space.
  • a second known technique performs a dichotomizing search in a table of identifiers grouping the identifiers recognized by the station, ranked by ascending order.
  • the dichotomizing search determines by successive comparisons, in which half, then in which fourth, then in which eighth, then in which sixteenth, etc. the identifier is located.
  • n dichotomizing search iterations must be performed. This technique exhibits the advantage of limiting the memory space but its identification time is too long to guarantee an acceptable performance (i.e., high speed performance).
  • an object of this invention is to provide a novel process and device for recognizing identifiers which minimize, in comparison with the known technique of the direct search, the memory space occupied and accelerating, in comparison with the technique of the dichotomizing search, the speed of identification.
  • This technique therefore, makes it possible to reduce the identification time, while limiting the memory size.
  • This and other objects of the invention are accomplished by a method and apparatus which uses a high-order byte of a received identifier.
  • the high-order octet is looked up in a direct read table which contains the size and the address of a search table containing a low-order byte of the reference identifiers of the station.
  • a dichotomizing search is then performed by comparing the reference bytes of the search table with the low-order byte of the identifier received.
  • the direct read table for each high-order byte, contains a byte corresponding to the size of the associated dichotomizing search table and a byte corresponding to the address of this table.
  • each dichotomizing search table contains the low-order bytes attached to the station and corresponding service specifications.
  • a memory in which at least one direct read table is located that provides, for each high-order byte received, the address and the size of an optionally associated dichotomizing search table containing the reference low-order bytes of the station;
  • the device comprises:
  • the device comprises means for storing the high-order byte of the identifier received, means for storing the base address of the direct read table and for adding these values and delivering an address corresponding to the sum, to the memory.
  • the device comprises means for storing the base address of the search table and for adding this base address to the mean value and delivering an address corresponding to the sum, to the memory.
  • the device comprises means for storing the low-order byte read into the search table and corresponding to the mean address value of said table and means for comparing the low-order byte received and said low-order byte read.
  • FIG. 1 is a diagram of a network used to transmit data between stations
  • FIG. 2 is a functional diagram of the data recognition device constructed according to the invention.
  • FIG. 3 is a diagram of the memory tables used by the invention.
  • FIG. 4 illustrates the contents of the direct read table of FIG. 3
  • FIG. 5 illustrates the contents of one of the dichotomizing search tables of the low-order octets of the identifiers
  • FIG. 6 is a detailed illustration of the device illustrated in FIG. 2.
  • FIG. 1 For example, several stations ST 1 , ST 2 ... ST n have throughout the several views, and more particularly to been illustrated which exchange digital data between one another. For example, variables and/or messages are transmitted between the stations by a serial data bus 1 between the stations.
  • Each station has, with reference to FIG. 2, a physical bus interface 2 which implements the physical layer of the bus and an asynchronous transmitting/receiving sequencer 3 (also referred to as transmitting/receiving unit 3) which recognizes any data item traveling on the bus.
  • transmitting/receiving unit 3 recognizes an identifier, it transmits or receives the associated data.
  • the station also has a memory 5 (e.g., RAM memory) and a microprocessor 6.
  • a memory access arbitrator 4 manages the partitioning of memory 5, between the microprocessor 6 of the station and transmitting/receiving unit 3.
  • the field transmitted on serial bus 1 has an identifier which is composed of, for example, two bytes, one of which is the high-order byte and the other of which is the low-order byte.
  • the identifier is made up of 16 bits comprising two octets (eight-bit bytes). One is the high-order octet and the other is the low-order octet.
  • the invention can be practiced using identifiers which have other sizes.
  • the identifiers received on the bus which are received by the station are distinguished from the reference identifiers which are the identifiers attached to the station and stored in the memory 5.
  • a direct read table 51 and associated dichotomizing search tables 53 and 55 are stored in the memory 5 of the stations.
  • Table 51 is used in the direct reading of the high-order octets of the identifiers and the corresponding or associated tables 53 and 55 (also referenced T -- ID -- L n ) are used in the dichotomizing search of the low-order octets relating to the corresponding identifiers.
  • the number of dichotomizing search tables is equal to the number of high-order octets assigned to the reference identifiers attached to the station.
  • EMPTY bit or flag
  • table 51 contains the address marked @ID -- Ln of the corresponding dichotomizing search table (T -- ID -- L n ) of the low-order octets used by the station, these octets bytes being ranked by ascending order.
  • bits @ID -- L1 and @ID -- LO are not contained in the table in the preferred embodiment but are considered to be zero. This is because the address stored therein will be a multiple of four and therefore, bits 1 and 0 will be zero.
  • dichotomizing search table 53 A dichotomizing search table such as this exists for each high-order octet stored in the direct read table 51.
  • This information can be considered the service specification. It is also possible for other and different sized information to be stored as the service specification.
  • Dichotomizing search table 55 and any other dichotomizing search tables used by the invention can have the same basic structure as the table illustrated in FIG. 5.
  • FIG. 6 represents the transmitting/receiving unit 3 which performs the recognition process of the identifiers received from bus 1.
  • the high-order octet and the low-order octet of an identifier received from bus 1 are stored respectively in internal registers 7 and 17.
  • Register 7 is connected via a multiplexer 26 to an adder 8.
  • This adder 8 is connected to the memory 5 via a 20 bit address bus 22.
  • Two 20 bit address registers 13 and 14 are connected to the adder 8 through the multiplexer 26.
  • the address register 13 is loaded in three parts (lower, middle, upper) with the base address of the dichotomizing search table.
  • An address register 14 receives an address which is on the bus 22.
  • An address register 9 is loaded by the microprocessor 6 with the base address of the direct read table 51. Its contents are transferred to the adder 8 through a multiplexer 24.
  • a register 11 has an input connected to data bus 30 and an output connected to a high delimiter register 10 working with a low delimiter register 12.
  • the contents of the delimiter registers 12 and 10 are transferred to an adder 15 whose output, divided by two, via a divider 16 which can be a wired device, loops around on the inputs of the registers 12 and 10 via bus 28.
  • the output of divider 16 is also connected, via a multiplexer 24, to the input of the adder 8.
  • the high delimiter register 10 contains a "high" address of the dichotomizing search tables (search tables) while the low delimited register 12 contains a "low” address of the search tables, the qualifiers "low” or "high” referring to the ascending addresses of the search tables.
  • the low delimiter register will be loaded with the value O which can be from a register 32, for example, which stores this value.
  • Comparator unit 18 compares the low-order octet of the identifier received and contained in register 17 with the octet ID -- Ln read from the dichotomizing search table T -- ID -- L n and contained in register 11.
  • Instruction sequencer 19 sequences the instructions from the various resources relative to the identifier search operations which have been described above and can be used to control all of the functional elements illustrated in FIG. 6.
  • the high-order octet of this identifier is loaded into the register 7.
  • the base address of the direct read table 51 which is contained in the register 9 and the high-order octet of the identifier received which is contained in the register 7 are added by the adder 8 to obtain the address of the high-order octet in the direct read table 51.
  • a read access into the direct read table in the memory 5, through the adder 8, is performed at the address which is the sum of the registers 9 and 7.
  • the high-order octet of the identifier is an address with immediate access in the direct read table.
  • the address bus 22 connected to the memory 5 is a 20-bit bus. The two low-order bits are zero and the address where the reading into the memory 5 is performed is therefore a multiple of four. This is permissible as both the direct read table 51 and the dichotomizing search tables contain new entries every four octets.
  • the direct read table 51 comprises four consecutive octets for each high-order octet.
  • the first octet of the direct read table (N -- ID -- L) is read at the address defined above (i.e. the result of the addition) and contains the size of the dichotomizing search table that corresponds to the high-order octet.
  • the read data of this first octet (the size of the corresponding search table) is written as a high delimiter in the register 10, via the register 11.
  • the address resulting from the addition mentioned above (the address of the last entry in the direct read table) is stored in register 14.
  • This result in register 14 is added with a constant equal to 1 which can be stored in a register 22, for example.
  • the result of this addition is a second address, corresponding to the second octet (octet 1), containing the "Empty" bit of the high-order octet of the direct read table 51.
  • This second octet of the direct read table 51 is read from memory 5 via bus 30 and is loaded into register 11 to examine the "empty" state (generation of instruction) and into the lower part of register 13 for bits @ID -- L3 and @IDL2 (i.e. address bits 3 and 2) of the corresponding dichotomizing search table.
  • the reading of the last 2 octets (octets 2 and 3) of the direct read table 51 is conditional on the state of the "Empty" bit (the second bit of octet 1 in FIG. 4). If the "Empty" bit is equal to 0, the reading of the third and fourth octets of the entry in the direct read table is performed to load them respectively in the middle and upper part of register 13. If the empty bit is equal to 1, the station does not recognize any identifier having this high-order, and the search is terminated.
  • the dichotomizing search process which follows is conditional on the loading, in register 17, of the low-order octet of the identifier received.
  • the low delimiter register 12 contains a value O which can be loaded from the register 32, while the high delimiter register 10 contains the number of low-order octets (N -- ID -- L) of the corresponding dichotomizing search table (i.e., the size of the search table).
  • the adder 15 and the divider 16 calculate the average (MID) of the value contained in the low delimiter register 12 and of the value contained in the high delimiter register 10. This average value MID is added, by adder 8, to the base address contained in register 13. The sum of this addition is sent to memory 5 by address bus 20 and the octet in memory 5 corresponding to this address is transmitted to register 11 via data bus 30.
  • the present invention determines that a received identifier is intended for a station, that station can perform any known type of processing associated with the received identifier including receiving data associated with the identifier and any other type of processing such as alerting a user of the received information, searching a data base, using the received data within a program, etc.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • General Physics & Mathematics (AREA)
  • Communication Control (AREA)
  • Computer And Data Communications (AREA)
US08/037,583 1992-03-27 1993-03-26 Method and apparatus for recognizing data traveling on a data transmission network using a dichotomizing search process Expired - Lifetime US5434799A (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR9203728 1992-03-27
FR9203728A FR2689267B1 (fr) 1992-03-27 1992-03-27 Procede de reconnaissance de donnees circulant sur un reseau de transmission de donnees et dispositif pour la mise en óoeuvre de ce procede.

Publications (1)

Publication Number Publication Date
US5434799A true US5434799A (en) 1995-07-18

Family

ID=9428164

Family Applications (1)

Application Number Title Priority Date Filing Date
US08/037,583 Expired - Lifetime US5434799A (en) 1992-03-27 1993-03-26 Method and apparatus for recognizing data traveling on a data transmission network using a dichotomizing search process

Country Status (4)

Country Link
US (1) US5434799A (fr)
EP (1) EP0562894B1 (fr)
DE (1) DE69324725T2 (fr)
FR (1) FR2689267B1 (fr)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020047915A1 (en) * 2000-04-24 2002-04-25 Nec Corporation Segmented processing method for a transport stream for digital television and recording media for the same
US7099324B2 (en) 1999-12-08 2006-08-29 Nec Corporation System and method for processing packets

Citations (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0076408A2 (fr) * 1981-10-02 1983-04-13 Hughes Aircraft Company Méthode d'adressage fonctionnelle pour un bus de données multiplexées
US4413318A (en) * 1980-11-20 1983-11-01 International Business Machines Corporation Use of nodes to uniquely identify processes
EP0130802A2 (fr) * 1983-06-29 1985-01-09 Westinghouse Electric Corporation Système de commande distribuée de processus avec des moyens et une méthode pour la gestion automatique de base de données pour des informations à diffuser
US4718005A (en) * 1984-05-03 1988-01-05 International Business Machines Corporation Distributed control of alias name usage in networks
US4870571A (en) * 1983-05-04 1989-09-26 The Johns Hopkins University Intercomputer communications based on message broadcasting with receiver selection
US4930159A (en) * 1989-01-18 1990-05-29 International Business Machines Corporation Netbios name authentication
US4949337A (en) * 1989-01-30 1990-08-14 Honeywell Inc. Token passing communication network including a node which maintains and transmits a list specifying the order in which the token is passed
US5077694A (en) * 1988-12-16 1991-12-31 Pitney Bowes Inc. Distribution mailing system having a control database for storing mail handling categories common to the databases of selected mailer stations
US5133053A (en) * 1987-02-13 1992-07-21 International Business Machines Corporation Interprocess communication queue location transparency
US5167035A (en) * 1988-09-08 1992-11-24 Digital Equipment Corporation Transferring messages between nodes in a network
US5304992A (en) * 1990-11-16 1994-04-19 Kabushiki Kaisha Toshiba Method of allocating identifiers and apparatus for the same

Patent Citations (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4413318A (en) * 1980-11-20 1983-11-01 International Business Machines Corporation Use of nodes to uniquely identify processes
EP0076408A2 (fr) * 1981-10-02 1983-04-13 Hughes Aircraft Company Méthode d'adressage fonctionnelle pour un bus de données multiplexées
US4870571A (en) * 1983-05-04 1989-09-26 The Johns Hopkins University Intercomputer communications based on message broadcasting with receiver selection
EP0130802A2 (fr) * 1983-06-29 1985-01-09 Westinghouse Electric Corporation Système de commande distribuée de processus avec des moyens et une méthode pour la gestion automatique de base de données pour des informations à diffuser
US4718005A (en) * 1984-05-03 1988-01-05 International Business Machines Corporation Distributed control of alias name usage in networks
US5133053A (en) * 1987-02-13 1992-07-21 International Business Machines Corporation Interprocess communication queue location transparency
US5167035A (en) * 1988-09-08 1992-11-24 Digital Equipment Corporation Transferring messages between nodes in a network
US5077694A (en) * 1988-12-16 1991-12-31 Pitney Bowes Inc. Distribution mailing system having a control database for storing mail handling categories common to the databases of selected mailer stations
US4930159A (en) * 1989-01-18 1990-05-29 International Business Machines Corporation Netbios name authentication
US4949337A (en) * 1989-01-30 1990-08-14 Honeywell Inc. Token passing communication network including a node which maintains and transmits a list specifying the order in which the token is passed
US5304992A (en) * 1990-11-16 1994-04-19 Kabushiki Kaisha Toshiba Method of allocating identifiers and apparatus for the same

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
"Indexing Method for Fast Random Access to Collated Data", IBM Technical Disclosure Bulletin, vol. 29, No.4, Sep. 1986.
Indexing Method for Fast Random Access to Collated Data , IBM Technical Disclosure Bulletin, vol. 29, No.4, Sep. 1986. *

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7099324B2 (en) 1999-12-08 2006-08-29 Nec Corporation System and method for processing packets
US20020047915A1 (en) * 2000-04-24 2002-04-25 Nec Corporation Segmented processing method for a transport stream for digital television and recording media for the same
EP1150496A3 (fr) * 2000-04-24 2003-03-12 Nec Corporation Méthode de segmentation d'un flux de données pour télévision digitale et moyen d'enregistrement associé

Also Published As

Publication number Publication date
EP0562894A1 (fr) 1993-09-29
FR2689267A1 (fr) 1993-10-01
DE69324725T2 (de) 1999-09-02
FR2689267B1 (fr) 1994-05-06
EP0562894B1 (fr) 1999-05-06
DE69324725D1 (de) 1999-06-10

Similar Documents

Publication Publication Date Title
US5781772A (en) Compressed prefix matching database searching
CA1173928A (fr) Circuit d'interface de voie
US4817080A (en) Distributed local-area-network monitoring system
CA1060121A (fr) Appareil de tri et systeme de traitement de donnees
US5317708A (en) Apparatus and method for an improved content addressable memory
US5511210A (en) Vector processing device using address data and mask information to generate signal that indicates which addresses are to be accessed from the main memory
US5307494A (en) File name length augmentation method
EP0752651A2 (fr) Référence valeur index pour structures de données partagées
EP0470798B1 (fr) Système de recherche par dictionnaire
US4866445A (en) Method and programmable device for transcoding character strings
US5893137A (en) Apparatus and method for implementing a content addressable memory circuit with two stage matching
US4004278A (en) System for switching multiple virtual spaces
WO1992020028A1 (fr) Procede et appareil destines a mettre des donnees en memoire tampon au sein de stations d'un reseau de telecommunication
WO2000052883A2 (fr) Procede et appareil de mise en lots dynamique de paquets avec une interface reseau haute performance
US5958029A (en) Method and system for efficient message validation
JPH0213040A (ja) ネットワークシステムにおけるアドレス情報登録／検索方式
US20070112991A1 (en) System for transmitting data between two bus systems
US5434799A (en) Method and apparatus for recognizing data traveling on a data transmission network using a dichotomizing search process
US5604842A (en) Fuzzy reasoning processor and method, and rule setting apparatus and method
US5274835A (en) Merge device using FIFO buffers
EP0333181B1 (fr) Dispositif de recherche de chaîne de données
US6314099B1 (en) Address match determining device, communication control system, and address match determining method
US6148376A (en) Method and apparatus for an improved stack arrangement and operations thereon
US4864493A (en) Instruction address producing unit capable of accessing an instruction segment of an extended size
US5963720A (en) Method and system for expediting transfer of data over a network using an additional field

Legal Events

Date Code Title Description
STPP Information on status: patent application and granting procedure in general

Free format text: APPLICATION UNDERGOING PREEXAM PROCESSING

AS Assignment

Owner name: TELEMECANIQUE S.A., FRANCE

Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:AGUILHON, BERNARD;KARCHER, JEAN-FRANCOIS;POTIRON, JEAN-HUGHES;REEL/FRAME:006669/0898

Effective date: 19930406

FEPP Fee payment procedure

Free format text: PAYOR NUMBER ASSIGNED (ORIGINAL EVENT CODE: ASPN); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

FEPP Fee payment procedure

Free format text: PAYOR NUMBER ASSIGNED (ORIGINAL EVENT CODE: ASPN); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

FEPP Fee payment procedure

Free format text: PAYER NUMBER DE-ASSIGNED (ORIGINAL EVENT CODE: RMPN); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

FPAY Fee payment

Year of fee payment: 4

FPAY Fee payment

Year of fee payment: 8

FPAY Fee payment

Year of fee payment: 12