Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-11-01
2003-03-18
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S226000, C709S228000, C711S216000
Reexamination Certificate
active
06535867
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to the field of computers and more particularly to external file access procedures in resource limited computer systems.
2. Description of Background Art
The ubiquity of the Internet is driving the inclusion of Transmission Control Protocol/Internet Protocol (TCP/IP) stacks in smaller and cheaper devices. Meeting the price and space demands of embedded applications forces designers to look for an alternative to the 32-bit processors historically required for TCP/IP.
As more products are designed with networking capabilities there is a need for networking functionality to be available at a lower price point. The TCP/IP protocol was designed to operate on 32-bit workstations. Consequently, the protocol makes few concessions to resource limited devices like embedded 8-bit microcontrollers.
One of the difficulties of using a resource limited microcontroller to implement a TCP/IP stack is that when data frames are sent, a data validity check value, e.g., checksum or cyclic redundancy check (CRC), is necessary to ensure that the frame is not corrupted during transmission. Conventional TCP/IP stack implementations buffer the entire frame such that a data check function can be performed on the frame. However, these conventional systems require that memory be used to buffer the frame. This is not a feasible option in devices where the amount of on-chip random access memory (RAM) is already small and any use of the RAM could significantly affect the performance of the device.
Another alternative is to limit the size of the data packets in order to minimize the amount of data that needs to be buffered. However, limiting the size of the data packets would decrease the efficiency of the system. Using smaller packets requires that more packets are sent in order to communicate the same amount of data. Since a portion of each packet is usually set aside for addressing and protocol information, smaller packets result in a lower proportion of the bytes being sent being data bytes and thus a lower efficiency. If the link is used less efficiently, then a faster, more complex, and more expensive, physical interface might be required to send the data in the same amount of time
A third possibility is that the no redundancy check is performed and the data is sent without being buffered. However, such a reduction in reliability is unacceptable for many potential uses of resource limited devices.
What is needed is a TCP/IP communications protocol system and method that is compatible with legacy systems and that uses a resource limited computer, e.g., an 8-bit microprocessor or microcontroller, that (1) reduces or eliminates the need for buffering (2) does not require addition additional memory, (3) does not require limiting the size of data packets; and (4) is reliable.
Another use of resource limited devices (processors) is to locate files stored in external memory, e.g., electrically erasable and programmable read only memory (EEPROM). For example, in order to access a web page on a web server, the device needs to identify the uniform resource identifier (URI). This URI typically corresponds to a file path in a file system. For example, the file “logo.gif” in the sub-directory “images” could have the URI: “/images/logo.gif”. In conventional file systems, a table of file names is stored along with pointers that identify the memory address at which the file data begins. Finding a particular file is achieved by searching through the table of file names, e.g., URIs, until a match is found. There are a variety of ways for optimizing this search, such as structuring the search as a tree. The use of hashing functions is possible, but in conventional systems the file name, e.g., the URI, still needs to be stored in the device when using hashing functions.
In resource limited devices, storing the file names, e.g., URIs, of the relevant files is an inefficient and impractical use of the limited memory resources on the device.
What is needed is a data storage and lookup procedure for use on resource limited computers, e.g., 8-bit microcontrollers, that will enable files stored in external memory to be identified without requiring that the file names or paths, e.g., URIs, be stored on the internal computer memory.
SUMMARY OF THE INVENTION
The invention is a system and method that computes a hash function based upon the file name, e.g. a URI, that is to be identified in a look-up table stored in external memory. The hash value is multiplied by a first multiplier. The result is used as a pointer to a lookup table that is stored in external memory. The present invention avoids the need to perform string comparisons or to store any file names or addresses on the server.
REFERENCES:
patent: 4464713 (1984-08-01), Benhase et al.
patent: 4586157 (1986-04-01), Rector et al.
patent: 5339398 (1994-08-01), Shah et al.
patent: 5386539 (1995-01-01), Nishi
patent: 5446854 (1995-08-01), Khalidi et al.
patent: 5579501 (1996-11-01), Lipton et al.
patent: 5713001 (1998-01-01), Eberhard et al.
patent: 5724512 (1998-03-01), Winterbottom
patent: 5812776 (1998-09-01), Gifford
patent: 6038231 (2000-03-01), Dolby et al.
patent: 6119131 (2000-09-01), Cabrera et al.
patent: 6119153 (2000-09-01), Dujari et al.
patent: 6134632 (2000-10-01), Looi et al.
patent: 6141690 (2000-10-01), Weiman
patent: 6216214 (2001-04-01), Bryg et al.
patent: 6353820 (2002-03-01), Edwards et al.
patent: 6377991 (2002-04-01), Smith et al.
Knuth, The Art of Computer Programming, vol. 3, 1973, pp. 506543.
Fenwick & West LLP
Le Debbie M.
Robinson Greta
LandOfFree
System and method for accessing external memory using hash... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for accessing external memory using hash..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for accessing external memory using hash... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3054457