Method and system of database management in an asynchronous transfer mode (ATM) environment5809501Abstract 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. Claims What is claimed is: Description DESCRIPTION
TABLE 1
______________________________________
CONNECTED- CONNECTED-
FROM PORT
VPI VCI TO PORT VPI VCI
______________________________________
A 1 -- C 10 --
A 2 -- D 6 --
B 5 3 C 7 4
B 5 2 D 3 5
______________________________________
An ATM cell is the basic multiplexing unit within an ATM transport system, with each cell or information unit containing its own connection and routing information. This feature enables direct multiplexing or demultiplexing of service channels wherein each channel may carry different bit-rates. Each ATM cell is identified and routed by information contained in the header within the virtual path identifier (VPI) and virtual channel identifier (VCI) fields. As mentioned above, a virtual path (VP) is a bundle of multiplexed circuits between two termination points, e.g., switching systems, Local Area Network (LAN) gateways, or private network gateways. A VP provides a direct logical link between virtual path terminations, with the VPI value identifying the particular virtual path. As also mentioned above, the virtual connection concept used within ATM technology allows multiple virtual channels (VCs) to be handled as a single unit. Virtual channels with common properties, such as those with the same quality of service (QoS), can be grouped together in bundles that can be transported, processed and managed as one unit. This flexible bundling simplifies the operation and maintenance of an ATM system. Both virtual paths and virtual channels can be used to provide semi-permanent paths within the ATM network. Routes are established and released from an operation support system by the setting of "path connect tables" in the cross-connect equipment or in the multiplexers along a path. Virtual channels can also be used for on-demand switching with connections being established by signaling either between a user and the network or within the network. One important characteristic of ATM technology relates to its protocol architecture and is built around the so-called "core-and-edge" principle. The protocol functions specific to the information type being transported, such as retransmissions, flow control, and delay equalization, are performed in terminals at the "edges" of the ATM network. This leaves an efficient, service-independent "core" network, that only includes simple cell-transport and switching functions. Within the ATM nodes in this "core", there is no error checking of the information field nor is there any flow control. The cell information is simply read, the HEC is then used to correct single-bit errors that might affect the address and the cell is then switched towards its destination. An ATM adaptation layer (AAL) is used at the "edge" of the network to enhance the services provided. As shown in FIG. 5, the CCITT reference model for B-ISDN services envisages that the AAL include service dependent functions. As depicted in FIG. 5, there are three layers in the ATM standard. The first layer is the physical layer defining the physical interfaces and framing protocols. The second ATM layer is independent of the physical medium chosen and defines cell structure, provides multiplexing and demultiplexing and VPI/VCI translation to control the flow of cells within the logical network. The third layer is the AAL which provides the important adaptation between the service and the ATM layer thereby allowing service-independent ATM transport. The AAL performs mapping between the original service format and the information field of an ATM cell. Exemplary functions provided by the AAL include variable-length packet delineation, sequence numbering, clock recovery and performance monitoring. Deployment of ATM in Telecommunications Networks One use of ATM technology can be within customer premises to support high-speed data communications in and between customer local area networks. In addition, ATM can be used as an infrastructural resource that is common to all services within a customer premises network, including voice and video communications, data transfers and multimedia applications. An exemplary service for which ATM nodes are introduced into a public telecommunications network is to provide virtual leased line (VLL) service. VLL service is based upon a virtual path concept and allows line capacity to be directly tailored to customer needs and easily changed without modifying the interface structure. A large number of logical connections can be offered to a user through user-network interfaces (UNIs). In addition, a custom tailored quality of service can also be offered to a customer, matching the needs of the user. Thus, multiple classes of service, quality of service classes and performance parameters can be selected. For example, voice services require low transmission delays but can tolerate high bit-errors, while data communications, on the other hand, are more tolerant of network delays but are sensitive to bit-errors. Thus, the quality of service level of a particular application can be contractually agreed to between a service provider and a customer and audited manually or automatically to ensure compliance. FIG. 6 shows an exemplary virtual channel based VLL service implemented within a ATM network. Network terminals A to E are each coupled through flow enforcement nodes 601 to 605, respectively, to ATM cross-connect nodes 611 to 614. The ATM network consist of a plurality of ATM cross-connects 611 to 614 which can provide routing both at the virtual path as well as at the virtual channel level. The flow enforcement functions 601 to 605 are located at the edge of the ATM network to protect the network against potential overloads. This function ensures that no connection violates the conditions that were agreed-to when the connections are set up. Additional services can be implemented by adding services to one or more of the cross-connect nodes 611 to 614. Within the network of FIG. 6, an exemplary virtual path is illustrated by the wavy line 621 between terminal C and D. A first virtual connection between terminals A and B is illustrated by the dashed line 631 while a second virtual connection is illustrated by the dotted line 632 between terminals C and E. In addition to the virtual leased line network shown in FIG. 6, other services, such as SMDS/CBDS and frame relay, can easily be added depending upon demand by connecting servers to the ATM nodes within the network. In residential areas, ATM technology can be used to provide new and enhanced entertainment services such as on-demand video to the end user. The flexibility of an ATM network makes it possible to simultaneously support a multitude of services, such as long distance education, home shopping, and games. FIG. 7 illustrates an ATM network that has been overlaid upon a SDH-based layered transport network. The layers include a customer premises network layer 701, a local transport network layer 702, a regional transport network layer 703 and a national transport network layer 704. A plurality of ATM business network nodes 711 to 714 control the flow of data from the customer premises terminals 715 and LANs 716 into respective ones of a plurality of add-drop multiplexers (ADM) 721 serving SDH cross-connect nodes 722 within the local transport network 705. The local cross-connect nodes 722 are in turn coupled through regional cross-connect nodes 731 in the regional transport network, two of which are coupled by add-drop multiplexers 732. Within the local transport network layer 702, a pair of ATM access nodes 723, and SDH rings, comprising the add-drop multiplexers 721, serve the cross-connects 722 and are used for subscriber access with a capacity of up to a full 155 megabits per second, the standardized STM-1 access rate for B-ISDN services. Existing traffic such as the Plain Old Telephone Service (POTS) can also be carried on this ring network, with remote multiplexers and other access nodes providing the final local-loop connection. The ATM access nodes 723 are shared for access to different services from one location and can include both voice and data using different VP/VCs. In the ATM access nodes 723, ATM traffic is concentrated to make more efficient use of the transport capacity. The size of an ATM access node can vary, depending upon the capacity required, from a small multiplexer to a large cross-connect. In the regional transport layer 703, ATM cross-connects 733 are used to route traffic between local areas. The use of ATM technology is not visible in the national transport network layer 704, illustrated in FIG. 7. In an ATM overlay network, such as the one illustrated in FIG. 7, services such as frame relay and SMDS/CBDS can be easily added. Functionality for B-ISDN can also be added to both access and regional nodes by adding appropriate software and hardware. As also illustrated in FIG. 7, a network management system 750, such as one operating in accordance with the TMN standard of the CCITT can be implemented to provide the necessary network management functionality to both the SDH and ATM elements of the network. The management of the ATM network by subsystem 750 may be implemented in accordance with the telecommunications management and operations support (TMOS) family of network management systems provided by Telefonaktiebolaget LM Ericsson, the assignee of the present application. Such network management may include various functionalities such as routing algorithms and congestion control. Organization of Connection Information in an ATM Exchange As detailed earlier, the header segment of an ATM cell includes an 8- or 12-bit Virtual Path Identifier (VPI) and a 16-bit Virtual Channel Identifier (VCI). The VPI and the VCI represent the global address of an ATM cell. In one embodiment of the present invention, a database is created inside each ATM exchange which consists of 41-bit records. The structure of data records within such a database is shown schematically in FIG. 8. Since the memory of most computing devices are organized in groups of eight bits, this 41-bit data record can be physically organized as a 48-bit (i.e., as a 6-octet) record. As can be seen from FIG. 8, each record in the database comprises a 12-bit VPI portion 801, a 16-bit VCI portion 802, a 12-bit CON portion 803 and a 1-bit PATH 804. TABLE 2 shows the C-syntax description of the structure of each data record.
TABLE 2
______________________________________
struct Connection {
int VPI;
int VCI;
int CON;
int PATH; /* The int PATH contains the bit
validating the VCI field (when low) */
};
______________________________________
.COPYRGT.1995 Telefonaktiebolaget L M Ericsson (publ.)
The records in the database are sorted according to the binary value of the VPI field 801 and the VCI field 802, with the VPI field 801 being the most significant. The PATH field 804 is used to indicate whenever multiple virtual channels are part of the same virtual path connection. Whenever the PATH field contains the binary value 1 (i.e., the PATH flag is "asserted"), the VPI value is required to be unique in the database. If the PATH field 804 contains the binary value 0 (i.e., the flag is "cleared"), then the database may contain multiple entries having the same VPI value as long as each such entry has a unique VCI value. The database is sorted in numerical order. This facilitates the implementation of hardware checks to prevent the addition of illegal entries into the database. Upon startup, all data records are initialized with the hexadecimal values FFF and FFFF in their VPI field 801 and VCI field 802, respectively. Likewise, whenever a record entry is eliminated from the connection table, the VPI and VCI values of that data record are overwritten with these default values after reorganizing the database using a technique described later in this specification. The CON field 803 contains a simplified local address that corresponds to the global address represented by the VPI field 801 and VCI field 802. The Data Lookup Algorithm Lookup requests to the connection database in an ATM exchange are executed using a modified binary search algorithm that uses the VPI field 801 (and optional the VCI field 802) as the search key(s) to retrieve the corresponding connection information from the CON field 803. The operation of the binary search algorithm can be briefly explained as follows: in a sorted database of 2.sup.m words, one begins the search by looking first at the word at position 2.sup.m-1. If w, the word one is looking for, matches d, the current retrieved value from the sorted database, the search terminates. If, however, w, the word one is looking for, is smaller than d, the retrieved value, then the search is continued at the location 2.sup.m-1 -2.sup.m-2. On the other hand, if d is larger than w, then the search is continued at the location 2.sup.m-1 +2.sup.m-2. This process is iteratively repeated until the address increment becomes less than one, when the search is terminated. The wanted record, w, is assumed to be absent from the database if it is not found within m attempts. FIG. 9 shows the state machine for the modified binary search algorithm used for executing lookup requests. In FIG. 9, j is a variable that points to a data record in the database. The integer variable k represents address increments or decrements at each stage of the search process and is local to the binary search process. In contrast, the variable j is quasi-global variable that may be manipulated by other computing routines inside the ATM exchange processor other than the binary search process. The input variable, w, and the retrieved data record, d, are both structured data types ("structs") of the type Connection, as shown in TABLE 2. The comparison of d and w is performed using both the VPI and the VCI fields of d and w or using only the VPI fields of d and w depending on the PATH values of d and w. If the PATH flags of either d or w is asserted, then the comparison of d and w is done on the basis of their VPI fields alone. Whenever the lookup process is used to determine the CON value of an arriving ATM cell "on the fly", only the VPI and VCI values of w will be available. Since the PATH value corresponding to w is not available in such cases, it is set to zero for purposes of executing the lookup process. When the lookup process is used to take down (i.e., disconnect) a connection, the record entry corresponding to this connection has to be located and removed from the database. In such a case the w value contains the data item to be located in the database and the PATH flag of w (which is received from an upstream system) indicates whether the connection to be taken down is a VP connection (i.e. its PATH value is 1) or a VC connection (i.e. its PATH value is 0). When the PATH flag of w is set to 1, it indicates that the VCI value of w is not important. The binary search algorithm may also be used to "investigate" an entry. In such a case too, the value of the PATH flag for the input variable w becomes meaningful. Further discussion of this situation is to be found later in this specification. Investigating entries involves many of the same actions as on-the-fly (OTF) lookup. Investigation of entries is sometimes used for verifying the consistency of data entries at the time of initial entry as well as for maintaining the consistency of data. It should be noted that requests for investigation of entries are often accorded lower execution priority than other processes competing for processor cycles, and may sometimes be (temporarily) suspended. As shown in FIG. 9, the search process starts at 901 when a lookup request to find a data record corresponding to an input variable w is received. At 902, the pointer j is initially set to point to the top of the table and the address increment variable k is initially set to half the size of the table. The search begins at 906 by retrieving the search record at the location corresponding to the value of j as decremented by k. If the increment value k is found to be zero, an error message is generated at 908 and the search terminates at 914. If the value of k is not found equal to zero, then the search proceeds to 909. If the value of k is found greater than one, then the Main Processing Loop 915 of the binary search process is entered and the search jumps to 903 where a data record corresponding to the pointer value j is retrieved from memory. The current value of d is compared with the input variable w at 904. If d is found equal to w the process jumps to 905. If d is found greater than w the process jumps to 906. If d is found less than w the process jumps to 907. If d is found less than w at 904, then the pointer j is incremented by current value of the local address increment variable k at 907. If the value of the address increment variable k is not equal to zero, then the search proceeds to 909 and continues as described earlier. However, if the address increment variable k is found equal to zero at 907, then an error message is generated at 908 and the search terminates at 914 as described earlier. If the data structure variables d and w are found to match at 904, and if the search request is an edit request, then the scope of the variables d and w is compared at 905 on the basis of the PATH flags of d and w. If the search request is an edit request and variables d and w are equal in scope, then the binary search process returns the value of the pointer j at 910 and terminates at 912. Alternatively, if the search request were a lookup request on an incoming cell and, if d and w are found to match, then the lookup request terminates successfully and the value of CON is returned. If on the other hand the search request is an edit request and the PATH flags of d and w do not match, then d and w are not equal in scope and an error message is generated at 911 and the process terminates at 913. It should be noted that if the PATH fields 804 of either d or w are found equal to one, then the comparison of d and w is performed using only their VPI fields 801. Whenever a connection needs to be taken down, then the PATH values of d and w need to be equal in scope. The checking of the PATH flag to determine the equality of scope of d and w ensures that a call for disconnecting a VC connection does not result in the removal of a VP connection and vice versa. The return value of the lookup process is *j (i.e., a pointer to the location of the matching record). In order for the binary search to work properly, all memory values that do not contain data entries corresponding to currently active connections also need to be in sorted order. This is achieved by initializing the entire memory to the binary value "1" and by rewriting abandoned or disused entries with the binary value "1" after bubbling them to the top of the memory. This is equivalent to initializing all VPI fields 801 to the hexadecimal value FFF and all VCI fields 802 to the hexadecimal value FFFF. The Data Entry Process FIG. 10 shows the state machine for the modified bubblesort process used for executing data entry requests. In a conventional bubblesort algorithm, a data entry can be added anywhere in the database before being "bubbled" up to the correct location. However, in any database (such as a connection database in an ATM exchange) that is organized to be searched using a binary search algorithm, a new entry can not be entered into a database until its final position is determined and room has been created for its entry. Further, the data entry process in an ATM exchange is continually subject to preemption by the data search process. Thus one needs a dummy placeholder that does not impact on the sorted order of the database while being bubbled to its final spot. This feature is essential since the data entry process may be preempted at any time by a data lookup request. If, the data lookup process is to run properly, then the database constantly needs to be in sorted order. Since the data entry process may be preempted by a data lookup process, the local parameters of the data entry algorithm must be preserved until the interrupted process is resumed. In the bubblesort entry process illustrated in FIG. 10, i, j, and t are pointers to structured records ("structs" or "records") of the type Connection. The data entry process starts at 1001 when a request to add an entry is received. i and j are local variables of the data entry process that are initialized upon the invocation of the data entry process to point to the same record as t as shown at 1002. t is a quasiglobal variable which points to the first unused location in memory that can be modified by several processes apart from the data entry process. The variable t initially points to an offset of zero from the start of the table. Upon successful termination, the data entry process either enters the element, or in the case of an error, returns a pointer to the location in memory where the erroneously duplicated data record (that needs to be discarded) is situated. Since one embodiment of the connection information database in an ATM exchange allocates 12 bits of each data record to the CON field 803, the maximum size of the database is 4096 records numbered 0, 1, 2 . . . 4095. At 1003, the pointer j is decremented by one and the pointer t is incremented by one. At 1004, a data entry corresponding to the pointer value j is retrieved from memory and stored in d. At 1005, this value stored in d is first written to address i. Then the d-value stored in the database at the address i is compared with the input variable w. If d is found greater than w, the pointers i and j are decremented by one at 1006 and the process jumps back to 1004 following the Main Processing Loop 1013. If d is found less than w or if the pointer i is found equal to zero, then the input variable w is written to address i at 1007 and the process ends at 1008. If the values of d and w are found to match at 1005, an error message is generated at 1009 and the invoking process is informed at 1010 that the input variable is already loaded in memory. If the value of t reaches 4095, then an error message is generated at 1011 that informs the invoking process at 1012 that the memory is full and that no more connections can be established in the database unless and until some existing connections are released or discarded. This is because the CON field 803 is 12-bits wide in one embodiment of the present invention and thus, the database can have no more than 4096 entries. In general, an error condition is triggered at 1011 if the value of t sets a preset maximum value that is related to the size of the connection database. This procedure of insertion is what the inventor herein calls `a modified bubblesort algorithm`. An Illustrative Example of the Data Entry Process FIG. 11 illustrates the stages in the data entry sequence for a database containing six data records. Since the database contains six data entries, the value of the variable t is six just prior to the entry of a seventh data record. Assume that a seventh data item w, with VPI, VCI and PATH values of 5COh, 001h and 0h respectively, is to be added to the database. Since the PATH value of the new data item w is zero, this new connection is a VC connection. The algorithm first enters the state s0 wherein the pointers i and j are set equal to t as shown at 1002. FIG. 11(a) shows the organization of the database after the algorithm goes through the states s0, s1, s3 and s4, i.e., after the pointer j has been decremented at 1003, the pointer t has been incremented at 1003, and the contents of database record 5 have been read at 1004 and copied to address location 6 at 1005. FIG. 11(b) shows the organization of the database following state s4 after one full round of the Main Processing Loop 1013 of FIG. 10. As shown in FIG. 10, a plain copy of the data record is made while preserving the sorted order of the database. The data entry process continues along the Main Processing Loop 1013 until i points to zero or until both i and j point to data items that are smaller than w. The comparison of d and w is done after the data entry process enters state s4, i.e., at 1005 of FIG. 10. The method of comparison is based on the contents of the PATH flag as described earlier in the specification. If the data entry d is found to be smaller than w, the data entry process enters the state s6 as shown at 1007 of FIG. 10. The organization of the database now looks as shown in FIG. 11(c). The state machine now enters the new item w into the database at address i overwriting the bubbled-up duplicated entry at that position. The organization of database at the end of the data entry process is shown in FIG. 11(d). One of the principal advantages of this data entry technique is that the data entry process is interruptible and permits a successful binary search for any of the items in the database after such an interruption. The number of cycles that the algorithm state machine spends in the Main Processing Loop 1013 of FIG. 10 is dependent on the final location of the data item and upon how full the database is initially. On the average, it will take 1.5t+4 cycles to determine the final location of a new data item. If all machine cycles are assumed to be equally long and further assumed to be dependent upon the access time of commercially-available semiconductor memory (e.g., 50 nanoseconds) then for an initial database of 4000 entries, the mean entry access time can be computed as 50*(1.5*4000+4) nanoseconds, i.e., 300 microseconds (.mu.s). This figure can be improved upon by using faster memory. However it should be noted that the access time in practice may be slower than the computed figure of 300 .mu.s if the data entry process is interrupted by other processes having higher priority. It should be noted that the disconnection process too places a similar computational load on the processor as the data entry process and is likely to be, on the average, as active as the data entry process. The Data Removal Process FIG. 12 shows the state machine for the modified bubblesort process used for executing data removal requests. Like the data entry process, the data removal process is also a variant of the bubblesort technique wherein data entries that are to be discarded are successively overwritten until the process reaches the top of the memory in use. The process starts as shown at 1201 in FIG. 12 with a request to remove an entry corresponding to a pointer value j. i, j, and t are pointers to structured data records ("structs") of the type Connection. i and j are variables local to the data removal process while the variable t is quasi-global. The variable t can be modified by other processes such as the data entry and the initialization processes. The variable t points to the lowest unused location in memory and initially points to an offset of zero from the start of the table. The variable d is the register that is used to temporarily store data records. The data record to be removed is first identified using the lookup process or by the failure of the data entry process, both of which yield the pointer *j. This pointer *j is used as the input to the data removal process state machine as shown at 1201. At 1202, an auxiliary variable i is initialized with the value j+1 and the data record at location *i is copied to the location *j as shown at 1203 and 1204 using the register d as intermediate storage. If the top of the table has not been reached, the process enters state s4 wherein the variables i and j are both incremented by one, as shown at 1205. The process continues along the Main Processing Loop 1208 shown in FIG. 12 to state s1 and repeats steps 1203 and 1204 until the pointer i points to the top of the in-use section of the table. When i is found equal to t, the process enters state s3, and results in the value of t being decremented by one at 1206. The data removal process signals successful completion of the process by issuing a confirmation to the invoking process at 1207. The requirement that the database always remain in a sorted order is satisfied by the bubblesort data removal process illustrated in FIG. 12. Interleaved Operation of Lookup, Entry and Removal Process The input to the data removal process is a pointer to the data entry that needs to be removed. In order to obtain this starting value, another process such as the binary search process needs to be executed on the database. The data removal process may also be initiated by the failure of the data entry process. This can happen as shown in FIG. 10 if the data entry process state machine reaches state s5 in step 1009 and exits with an error message at 1010. If the data entry algorithm exits through state s5, the database needs to be reorganized since the pointers i and j point to two adjacent duplicative entries in the database at the moment of exit and since all valid data at higher locations in memory have been shifted up by one position. It should be emphasized that this situation does not affect the efficiency of the lookup process as it only results in an address location being used up unnecessarily. If the data entry process reaches the state s5, the data entry process can then be run in order to restore the database to the state it was in prior to the failed attempt to add a new data entry. In such a case the output *j of the data entry process is fed back as an input to the data removal process. Since such failed attempts to add data entries waste processing time, they can be avoided entirely if a search is performed before the start of the data entry or by having the software verify data prior to attempting entry. Investigation of the correctness of data to be entered is thus useful to the efficient operation of a connection database in an ATM exchange. Safeguarding against the corruption of database entries can be done either in hardware or in software. In one embodiment of the present invention, it is assumed that very few of the connections that are sought to be entered will fail, and therefore software checking at entry time is deemed sufficient. However this design choice requires a memory restoration process whenever an error occurs. The need for this cumbersome correction process can be avoided by implementing stricter checks on the entry of data records. Although a preferred embodiment of the method and apparatus of the present invention has been illustrated in the accompanying drawings and described in the foregoing detailed description, it is to be understood that the invention is not limited to the embodiment(s) disclosed, but is capable of numerous rearrangements, modifications and substitutions without departing from the spirit of the invention as set forth and defined by the following claims.
|
Same subclass Same class Consider this |
||||||||||