US5809501A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system of database management in an asynchronous transfer mode (ATM) environment
Assignee: Telefonaktiebolaget LM Ericsson AB
•
Filing: 1996-01-30
•
Granted: 1998-09-15
•
Expires: 2016-01-30
Abstract
Abstract A system and method for the efficient execution of interleaved lookup and edit requests received by a connection database in an ATM exchange is described. The global address of an ATM cell is mapped to a smaller, equipment-specific local address using a connection database stored in each local exchange. When an ATM cell arrives at an ATM exchange, lookup request is sent to the connection database along with the global address values. Since the database operating system accords high priority to these lookup requests, the connection database temporarily suspends execution of all other tasks and return the local address of the ATM cell. A modified binary search algorithm is used for executing the interrupt-driven local address lookup requests. Entries in the connection database continually need to be added, deleted, replaced or verified. Efficient execution of these management tasks can be facilitated by maintaining the database in a sorted order using a modified bubblesort algorithm. Sort requests are interleaved with lookup requests in such a way as to permit lookup requests to preempt sort requests in execution priority without imposing additional computational costs because of the interruption.
Inventors
- 👤 Geir Åge Noven
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 16:19
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/30; H04L49/3081; H04L45/00; H04L45/74; H04L45/742; H04L49/20; H04L49/3009; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5625; H04L2012/5626; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
155 words
A method of managing a connection information database in the exchange portion of an asynchronous transfer mode (ATM) system, said method comprising the steps of: mapping the global address of an ATM cell to a local address that is specific to the ATM exchange; looking up entries in the connection information database of the exchange portion using a binary search algorithm; adding data entries to the database using a bubblesort algorithm which has been modified, said modification of the bubblesort algorithm being to move a dummy data record to the appropriate location in the database while maintaining the connection information including any dummy records in said database in a fully sorted order; and deleting data entries from the database using a bubblesort algorithm which has been modified, said modification of said bubblesort algorithm being to delete data entries while maintaining the connection information including any deleted records, in said database in a fully sorted order.
Claim 2
Independent Claim
155 words
A method of managing a connection information database in the exchange portion of an asynchronous transfer mode (ATM) system, said method comprising the steps of: mapping the global address of an ATM cell to a local address that is specific to the ATM exchange; looking up entries in the connection information database of the exchange portion using a binary search algorithm; adding data entries to the database using a bubblesort algorithm which has been modified, said modification of the bubblesort algorithm being to move a dummy data record to the appropriate location in the database while maintaining the connection information including any dummy records in said database in a fully sorted order; and deleting data entries from the database using a bubblesort algorithm which has been modified, said modification of said bubblesort algorithm being to delete data entries while maintaining the connection information including any deleted records, in said database in a fully sorted order.
Claim 3
Dependent Claim
35 words
The method of claim 1 wherein the global address of an ATM cell header used in said ATM system comprises a 12-bit Virtual Path Identifier (VPI) portion and a 16-bit Virtual Channel Identifier (VCI) portion.
Claim 4
Dependent Claim
35 words
The method of claim 1 wherein the global address of an ATM cell header used in said ATM system comprises an 8-bit Virtual Path Identifier (VPI) portion and a 16-bit Virtual Channel Identifier (VCI) portion.
Claim 5
Dependent Claim
24 words
The method of claim 1 wherein the local address of an ATM cell used in said ATM system includes a 12-bit connection (CON) value.
Claim 6
Dependent Claim
26 words
The method of claim 1 wherein the local address of an ATM cell used in said ATM system additionally identifies data entries having unique VPI values.
Claim 7
Dependent Claim
21 words
The method of claim 5 wherein the identification of data entries having unique VPI values is performed using a binary flag.
Claim 8
Dependent Claim
31 words
The method of claim 1 wherein the step of data deletion takes as its input a pointer to the data entry being deleted, said pointer being generated by a search algorithm.
Claim 9
Dependent Claim
14 words
The method of claim 7 wherein the search algorithm is a binary search algorithm.
Claim 10
Dependent Claim
35 words
The method claim 1 wherein the step of data deletion takes as its input a pointer to the data entry being deleted, said pointer being automatically generated upon the failure of the data entry algorithm.
Claim 11
Dependent Claim
28 words
The method of claim 1 wherein the local address of an ATM cell used in said ATM system is generated from the global address using a hash function.
Claim 12
Independent Claim
92 words
A method of managing a connection information database in the exchange portion of an asynchronous transfer mode (ATM) system, said method comprising the steps of: mapping the global address of an ATM cell used in said ATM system to a local address that is specific to the ATM exchange; using a binary search algorithm to look up entries in the database; adding data entries to the database while maintaining the database in a fully sorted order, and deleting data entries from the database while maintaining the database in a fully sorted order.
Claim 13
Independent Claim
92 words
A method of managing a connection information database in the exchange portion of an asynchronous transfer mode (ATM) system, said method comprising the steps of: mapping the global address of an ATM cell used in said ATM system to a local address that is specific to the ATM exchange; using a binary search algorithm to look up entries in the database; adding data entries to the database while maintaining the database in a fully sorted order, and deleting data entries from the database while maintaining the database in a fully sorted order.
Claim 14
Dependent Claim
21 words
The method of claim 11 wherein the step of adding data entries to the database is performed using a bubblesort algorithm.
Claim 15
Dependent Claim
21 words
The method of claim 11 wherein the step of deleting data entries from the database is performed using a bubblesort algorithm.
Claim 16
Dependent Claim
150 words
A management system for managing a connection information database in the exchange portion of an asynchronous transfer mode (ATM) system, said management system comprising: means for mapping the global address of an ATM cell used in said ATM system to a local address that is specific to the ATM exchange; means for looking up connection entries in the database using a binary search algorithm; means for adding data entries to the database using a bubblesort algorithm which has been modified, said modification of the bubblesort algorithm being to move a dummy data record to the appropriate location in the database while maintaining the database including any dummy records in a fully sorted order; and means for deleting data entries from the database using a bubblesort algorithm which has been modified, said modification to said bubblesort algorithm being to delete data entries while maintaining the database in a fully sorted order.
Claim 17
Dependent Claim
150 words
A management system for managing a connection information database in the exchange portion of an asynchronous transfer mode (ATM) system, said management system comprising: means for mapping the global address of an ATM cell used in said ATM system to a local address that is specific to the ATM exchange; means for looking up connection entries in the database using a binary search algorithm; means for adding data entries to the database using a bubblesort algorithm which has been modified, said modification of the bubblesort algorithm being to move a dummy data record to the appropriate location in the database while maintaining the database including any dummy records in a fully sorted order; and means for deleting data entries from the database using a bubblesort algorithm which has been modified, said modification to said bubblesort algorithm being to delete data entries while maintaining the database in a fully sorted order.
Claim 18
Dependent Claim
34 words
The system claim 14 wherein the global address of an ATM cell header used in said ATM system comprises a 12-bit Virtual Path Identifier (VPI) portion and a 16-bit Virtual Channel Identifier (VCI) portion.
Claim 19
Dependent Claim
35 words
The system of claim 14 wherein the global address of an ATM cell header used in said ATM system comprises an 8-bit Virtual Path Identifier (VPI) portion and a 16-bit Virtual Channel Identifier (VCI) portion.
Claim 20
Dependent Claim
24 words
The system of claim 14 wherein the local address of an ATM cell used in said ATM system includes a 12-bit connection (CON) value.
Claim 21
Dependent Claim
26 words
The system of claim 14 wherein the local address of an ATM cell used in said ATM system additionally identifies data entries having unique VPI values.
Claim 22
Dependent Claim
21 words
The system of claim 18 wherein the identification of data entries having unique VPI values is performed using a binary flag.
Claim 23
Dependent Claim
36 words
The system of claim 14 wherein the means for performing the data deletion comprises means to take as an input a pointer to the data entry being deleted, said pointer being generated by a search algorithm.
Claim 24
Dependent Claim
14 words
The system of claim 20 wherein the search algorithm is a binary search algorithm.
Claim 25
Dependent Claim
41 words
The system of claim 14 wherein the means for performing the data deletion comprises means to take as an input a pointer to the data entry being deleted, said pointer being automatically generated upon the failure of the data entry algorithm.
Claim 26
Dependent Claim
28 words
The system of claim 14 wherein the local address of an ATM cell used in said ATM system is generated from the global address using a hash function.
Claim 27
Dependent Claim
103 words
A management system for managing a connection information database in the exchange portion of an asynchronous transfer mode (ATM) system, said management system comprising: means for mapping the global address of an ATM cell used in said ATM system to a local address that is specific to the ATM exchange; means for looking up entries in the connection database of said exchange portion, using a binary search algorithm; means for adding data entries to the database while maintaining the database in a fully sorted order; and means for deleting data entries from the database while maintaining the database in a fully sorted order.
Claim 28
Dependent Claim
103 words
A management system for managing a connection information database in the exchange portion of an asynchronous transfer mode (ATM) system, said management system comprising: means for mapping the global address of an ATM cell used in said ATM system to a local address that is specific to the ATM exchange; means for looking up entries in the connection database of said exchange portion, using a binary search algorithm; means for adding data entries to the database while maintaining the database in a fully sorted order; and means for deleting data entries from the database while maintaining the database in a fully sorted order.
Claim 29
Dependent Claim
20 words
The system of claim 24 wherein the means for adding data entries to the database additionally comprises a bubblesort algorithm.
Claim 30
Dependent Claim
20 words
The system of claim 24 wherein the means for deleting data entries from the database additionally comprises a bubblesort algorithm.
References Cited (Backward Citations)
US3611316A
Cited
UST972003I4
Cited
US4510567A
Cited
US4809158A
Cited
US5089985A
Cited
US4882699A
Cited
US5321843A
Cited
US5179698A
Cited
US5355474A
Cited
US5323389A
Cited
EP0594196A1
Cited
US5414704A
Cited
US5649109A
Cited
US5615366A
Cited
US5487164A
Cited
US5467349A
Cited
WO1995023380A1
Cited
US5502723A
Cited
US5414701A
Cited
US5621728A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-14 | 2002-03-16 | 2002-09-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-14 | 2006-03-16 | 2006-09-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-14 | 2010-03-16 | 2010-09-15 | $7700.00 | Window Closed / Lapsed |