Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-02-21
1998-12-01
Lintz, Paul R.
Data processing: database and file management or data structures
Database design
Data structure types
370601, 370912, 370395, G06I 1730
Patent
active
058452877
DESCRIPTION:
BRIEF SUMMARY
The invention relates to an apparatus for managing relationships between objects that are individually identifiable in a finite address field, and more particularly to an apparatus for real time applications. Each relationship associates two objects belonging to the same set of objects, or belonging to two respective sets containing objects of the same type or of different types. The term "relationship" should be understood broadly since the particular relationship may vary as a function of the application under consideration. Also, a given object may be associated with one or more other objects by one or more relationships of different kinds.
A particularly important application lies in the field of telecommunications, and more particularly in the field of managing relationships between cells transferred in asynchronous mode. An asynchronous transfer mode (ATM) switching system includes one or more buffer memories for temporary storage of cells to be switched. The buffer memory is generally used as a queue, e.g. of the first-in first-out (FIFO) type. In this first example of an application, it is necessary to manage order relationships between the various locations of the buffer memory to indicate the queue order of cells which are stored in respective ones of said locations.
In this application, the relationship is of the type "next cell in the queue" and it associates one cell which is situated at a certain location in the buffer memory with another cell that is "next" and that is situated in some other location in the buffer memory. In general, for a buffer memory that is shared by a plurality of queues, that other location is not an adjacent location, since locations are released in an order which is random and they are reused as they are released.
Conventionally, the order of respective cells in a queue is managed by managing cell identifiers, such as the addresses of the memory locations containing the cells. For example, to store the queue order of cells stored in a buffer memory, their addresses are written in successive addresses of a so-called "address memory", which is write addressed by a write pointer incremented by unity after each write operation, and read addressed by a read pointer that is incremented by unity after each read operation. The order in which the addresses are written in consecutive rows of this memory determines the order in which the cells will be read back from the buffer memory.
Another conventional method for managing the order of cells in a queue consists in making up a list of addresses that are chained in a random access memory referred to as a "link memory". Locations in the link memory correspond to respective locations in the buffer memory. Each location in the link memory contains an address which is the next address to be used, both for reading the next cell in the buffer memory and for reading the next address to be used in the link memory. Such a method of managing order between cells is described, for example, in European patent application No. 0 441 787 (Henrion 18).
In those two conventional examples of managing the order between cells in a queue, the explicit identifiers used are cell addresses, while the relationships between cells remain implicit.
There exists another type of relationship which does not define a special order or a special classification of objects, but rather that they belong to the same subset or group of objects, with all of the objects of the subset under consideration having exactly the same characteristics with respect to this relationship. In the field of telecommunications, an example of such a relationship is to be found between cells that are to be restored by a buffer memory during the same time interval for the purpose of resequencing cells in an order corresponding to their order of arrival. When a cell arrives in the switching system under consideration, the system associates therewith a time label indicating the time interval during which the cell is to be restored on one of the outlets of the switching system. All of the ce
REFERENCES:
patent: 4959776 (1990-09-01), Deerfield et al.
patent: 5467347 (1995-11-01), Petersen
patent: 5475644 (1995-12-01), Chauvel et al.
patent: 5541918 (1996-07-01), Ganmukhi et al.
patent: 5544104 (1996-08-01), Chauvel
patent: 5548588 (1996-08-01), Ganmukhi et al.
patent: 5570348 (1996-10-01), Holden
patent: 5583861 (1996-12-01), Holden
patent: 5619495 (1997-04-01), Yamanaka et al.
H. Yamanaka et al, "A Scalable Nonblocking Shared Multibuffer ATM Switch With a New Concept of Searchable Queue", ISS '95 World Telecommunications Congress, Berlin, DE 23 Apr. 1995, pp. 278-282.
J. Schultz et al, "CAM-Based Single-Chip Shared Buffer ATM Switch", SUPERCOMM/ICC'94, New Orleans, US, 1 May 1994, pp. 1190, 1995.
S. Kumar et al, "On Design of a Shared-Buffer Based ATM witch for Broadband-ISDN", IEEE 13th Annual International Phoenix Conference on Computers & Communications, Pheonix, US, pp. 377-383.
S. Mahmud, "Models of Asynchronous Packet-Switched Multiple and Partial Multiple Bus Systems", Micro-Processing and Microprogramming, vol. 40, No. 1, Jan. 1994, Amsterdam, NL, pp. 33-41.
ALCATEL N.V.
Lintz Paul R.
Wallace, Jr. Michael J.
LandOfFree
Apparatus for managing relationships between objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for managing relationships between objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for managing relationships between objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2403537