JP2000506658A - Managing data structures - Google Patents

Abstract

(57) [Summary] A data structure such as a connection map for telecommunications, comprising at least one of a list of data elements stored in a predetermined order of locations in a memory device (52). The structure can be modified by moving parts of the list through predetermined locations to insert new elements at specific locations in the structure, or delete or modify existing elements. Update while maintaining the order of the list. The elements of the structure are read in the order in which they were stored, and the structure is updated while accessing the structure by moving the element through the predetermined order of storage locations. An application specific to the present invention is the maintenance of a telecommunications switch connection map, which stores connection instructions that define in which ATM cell payload to assemble the received narrowband call data.

Description

DETAILED DESCRIPTION OF THE INVENTION Title of invention Managing data structures Field of the invention The present invention relates to data structures, and more particularly, to managing dynamic data lists in a real-time environment. One application unique to the present invention is the updating of connection maps in telecommunications systems. Background art One known data storage method takes the form of a linked list. Chained lists allow you to dynamically store even or uneven data items. Many related data items can be contained in a single list, with each item linked by a pointer field to the next item in the list. This is essentially a software process. This pointer field allows you to change the direction of the list and access the data. In the simplest form, new items are always added to the bottom of the list, and old items are always removed from the top of the list. The most common example of this scheme is a FIFO device. Updating this type of list requires actions such as chaining the list and deleting items. One example of an application in which this type of list is used is the queuing of tasks in an operating system, where the tasks are simply scheduled according to their arrival times. By using a linked list in a more complex way, all or part of the data information can be ordered in the list. Updating this type of list requires the ability to add new items or delete existing lists anywhere in the list. Examples of applications in which this type of list is used are routing tables, call records, translation table arrays in telecommunications systems, and task scheduling according to priorities in computer operating systems. There is. U.S. Pat. No. 5,274,768 (by Traw et al.) Describes an interface for an asynchronous transfer mode (ATM) network using this type of chained list management. International Patent Application WO 95/32596 A1 (Northern Telecom) describes an SDH / ATM interface that links the time slots of a particular ATM virtual circuit using a chain structure. An example of this type of list is shown in FIG. The memory 30 has a plurality of storage locations (memory locations), which are numbered from 1 to 20. Like location 1, the reserved portion in memory holds a pointer start_ptr that indicates the location of the first element in the list. In this example, the first element in the list occupies memory location 4. However, this element can occupy any of the storage locations. The enlarged portion shows the contents of the storage location 4 in detail. This storage location stores a data item DATA and a pointer ptr_next. This pointer points to the location of the next element in the chained list. It has the value "16", which is the storage location where the second element in the list is stored. This memory holds many identical elements linked together in such a way. Therefore, a process of updating this type of list will be described with reference to FIGS. 1A to 1C. FIG. 1A shows two elements, an element stored in storage location 4 and a second element stored in storage location 9. The pointer of the element at location 4 points to storage location 9. First, the situation where new elements need to be added to the list is considered. This new element is inserted into an available location in memory. This is location 16. This element must be tied to the list at the point where it is needed. FIG. 1B shows the result of adding a new element to the list between two existing elements. The pointer value of this element, held in memory location 4, now points to memory location 16, and the pointer value of the newly inserted element now points to memory location 9. Second, it takes into account the situation of existing elements that need to be removed from the list. Existing elements in storage location 16 need to be removed from the list. The pointer value of the element held at location 4 is changed to point to the storage location of the element following the element to be deleted (ie, the element at location 9). The problem with chained lists is that you need to search the list systematically to find a particular data item, starting with the first element in the list and continuing to the end of the list until the item is found. That is, there is. Therefore, the search process becomes slow. To improve access processing, a doubly linked list is generally used. In a doubly linked list, for each data item, a pointer is used to point to both the next element in the list and the previous item. In this way, the list can be changed in either direction. There are many problems with using linked and double linked lists. First, the process of constructing and maintaining lists becomes complicated, and therefore requires execution using software. Therefore, these lists cannot be used as real-time, high-throughput applications. Second, the task of updating the chained list usually hinders the process of accessing data. And third, it is necessary to store both data elements and pointers that link the elements together. A well-known method of updating a data list in a real-time hardware system is to use shadow memory. First, the updated list is constructed in this shadow memory and then replaced with the original memory to complete the update process. The use of shadow memory has the disadvantage of doubling the overall memory requirement. Therefore, choosing this method is particularly expensive for very fast real-time applications that require expensive, high performance memory devices. Both of these technologies have undesirable attributes, especially when used in real-time applications. The present invention provides an improved method for updating data tables and lists that minimizes the disadvantages of the prior art methods. Summary of the Invention According to a first aspect of the present invention, in a method for reading and updating at least one of a list of data elements stored in a predetermined order of storage locations of a memory device, a read pointer capable of pointing to individual storage locations. Providing read and write pointers; using the read pointer to read the elements of the list in the order in which they were stored; and during reading of the list, using the write pointer to Updating the list by writing elements to the read storage locations, wherein the written elements comprise elements read in the reading step, new elements inserted into the list, The step of updating includes, when the list is read, as a result, the list is stored through the storage locations in the predetermined order. A method for moving parts is provided. Storing data elements in a predetermined order eliminates the need for a complicated pointer mechanism to link one element in the list to the next. Several linked lists can be managed simultaneously while sharing common memory resources. This method is suitable for many applications that traditionally use chained and double chained lists to maintain dynamic data structures under software and / or hardware control. This moving process eliminates the need for a large-capacity additional high-speed memory as used in the known shadow memory technology. The method is simple and can be performed with minimal equipment. Performing the update during normal access to the list eliminates the need to interrupt the system during the update period. This technique is perfectly suitable for periodic applications where a complete set of data is read sequentially, once per operating cycle. An example of such a periodic read occurring is a connection table for a telecommunications application. The order in which the elements of the list are maintained may be important. Move parts of the list through the ordered storage location, update the list by inserting new elements into the list, or deleting or modifying existing elements at specific positions in the list This has the important advantage of keeping the elements in the list in their order as updates occur. Preferably, the step of updating the list, moving the data element and inserting a new element at a specific position in the list, comprises moving the data element that is earlier than the position through the storage locations in the predetermined order. And providing a space corresponding to the new element and inserting the new element into the space. Preferably, the step of updating the list is a step of deleting an existing item at a specific position in the list, and moving a data element in a direction returning from the position through the storage locations in the predetermined order. And overwriting the existing items. Preferably, the storage locations in the predetermined order in which the data elements are stored are a series of adjacent storage locations. This simplifies the process of navigating between data elements in the list. The proposed technology minimizes the control overhead and the operation is simpler than the conventional chained list, so the whole system is a hardware system or a combination of hardware and minimum software. Very fast access and maintenance speeds can be reliably achieved in the system. Data updates can be completely transparent to normal operation of the memory. That is, it is not necessary to interrupt the read access process while the update occurs. Preferably, sets of instructions for updating the data list are stored, the sets being arranged according to the order in which the lists are accessed. Therefore, a complete list update of the list including addition and deletion of a plurality of data items can be performed in one cycle. Preferably, the method further comprises reading the contents of the storage location determined by the read pointer into a second memory, and storing the content of the second memory in the storage location determined by the write pointer. Writing the oldest content, writing a new item to be inserted into the list, or writing nothing. This second memory is preferably composed of a FIFO device. Alternatively, it may be constituted by a designated portion of the main memory, which is configured to function as a FIFO. The step of deleting an existing element at a specific position in the list preferably includes the step of setting the write pointer to lag the read pointer so that the data element in a direction returning from the delete position is set to the predetermined position. Moving through the order storage location to overwrite the desired data element. Inserting a new element at a particular location in the list preferably comprises reading the data element stored at the location into a second memory; writing the new element to the storage location; Accessing, reading the data element at the next location into the second memory, and writing the oldest data element in the second memory to the next location, thereby leading the new element. Moving the data elements in the storage locations in the predetermined order. According to another aspect of the present invention, there is provided a method of managing a connection map of a telecommunications switch, the map comprising a list of connection instructions for the switch, stored in a predetermined order in a memory, The method includes providing a read pointer and a write pointer that can point to individual memory locations; using the read pointer to read the instructions in the list in the order in which they were stored; Updating the list by using the write pointer to write instructions to previously read storage locations during reading of the list, wherein the written instructions are read by the reading step. And the step comprising a new instruction to be inserted into the list. The step of updating, as a result of reading the list, It provides a way to move a part of the list through the memory locations of the predetermined order. Preferably, the method of managing a connection map forms part of a method of operating a telecommunications switch, the method comprising receiving data from a plurality of sources at an input to the switch; Buffering the received data, assembling the received data into a payload, transmitting the payload from the output of the switch to a plurality of destinations, wherein the connection command Specifies whether to assemble buffered data. Preferably, the connection map is ordered to assemble the payloads in the order in which the payloads will be decomposed at their destination. By doing so, it is not necessary to store the frame at the destination, and it is possible to avoid transmission delay caused by storing the frame. The received data can consist of a narrowband channel and the payload can consist of the payload of an ATM cell. The method of managing a connection map further includes receiving a request for a multicast connection between a source and a plurality of destinations, creating a series of update instructions for the map, and using the map. Updating the map with the series of update instructions. The ability to easily configure and manage the connectivity required for multicast narrowband telephone calls is a particularly desirable feature in future networks that support advanced features such as multimedia and conferencing services. The method of managing a connection map further comprises: summing elements of the map indicating a connection to a particular destination; calculating a size of a payload corresponding to the sum; and padding the payload. A step of deciding whether it is necessary and a step of activating padding according to the result of the decision. By executing the connection map in this manner, the size of the payload for each destination can be easily calculated. According to a further aspect of the invention, there is provided an apparatus for managing at least one of a list of data elements, a storage device for storing the data elements in storage locations in a predetermined order, and a read pointer capable of pointing to individual storage locations. Means for providing read and write pointers; means for reading the elements of the list using the read pointer in the order in which they are stored; and means for using the write pointer during reading of the list. Means for updating the list by writing elements to the read storage locations, the written elements comprising: elements read by the reading means; new elements inserted into the list; The updating means, when the list is read, as a result, through the storage locations in the predetermined order. To provide an apparatus for moving some of the bets. This device can be implemented in hardware only. According to a further aspect of the invention, an input for receiving data from a plurality of sources, a buffer for storing the received data, means for assembling the received data into a payload, and transmitting the payload to a plurality of destinations An output unit, a memory for storing a map of connection instructions as at least one of a list of data elements in a predetermined order in the memory, and a management unit for managing the map. Means for providing a read pointer and a write pointer capable of pointing to the list, means for reading the elements of the list in the order in which they are stored using the read pointer, and means for reading the list during reading of the list. Means for updating the list by writing an element to a storage location that has already been read, using a write pointer. These written elements include the element read by the reading unit, the management unit having the unit, which includes a new element to be inserted into the list, and the updating unit includes: When read, the result is to provide a telecommunications switch that moves a portion of the list through the predetermined order of storage locations. This method is particularly suitable for updating connection maps and routing tables used in communication systems and data networks. These applications will be described in detail. However, it will be appreciated that the method is also capable of other applications, such as scheduling events and processes in a real-time operating system. As will be apparent to those skilled in the art, suitable features may be combined as appropriate, or those features may be combined with any of the aspects of the present invention. BRIEF DESCRIPTION OF THE FIGURES Embodiments will be described below with reference to the accompanying drawings in order to better understand the present invention and illustrate how it is carried out. FIG. 1 shows a known method of implementing a linked list. 1A to 1C show a method of updating a list using the configuration of FIG. FIG. 2 schematically shows the arrangement of the linked list in the memory. FIG. 3 illustrates updating a set of linked lists in memory. FIG. 4 shows a system for performing the method shown in FIG. 5 to 5B show the system of FIG. 4 used for updating the linked list. FIG. 6 shows a flowchart of a method for updating a linked list. FIG. 7 shows a communication system using the method. FIG. 8 shows an example of implementing the interconnection via the network of FIG. FIG. 9 shows another example of implementing the interconnection via the network of FIG. FIG. 10 shows a system for realizing the interconnection by the method of FIG. 11 and 11A show a process of updating the connection table used in the system of FIG. FIG. 12 illustrates the concept of multicast. FIGS. 13 and 13A show processing for updating the connection table used in the system of FIG. 10 and executing multicast. Embodiment of the Invention FIG. 2 shows the basic structure of a linked list in a memory. This memory can be used to maintain a single data list and can contain multiple linked lists. The total size of the memory places an upper limit on the combined length of all data lists. Each list is stored in a predetermined order of storage locations. In the arrangement of FIG. 2, the storage locations in the predetermined order are a series of adjacent storage locations. This eliminates fragmentation of the list and eliminates the control logic required to traverse the structure of conventional chained lists. In addition, all unallocated locations in memory occur consecutively as a group at the lowest location in memory. One way to distinguish between a chained list and unallocated memory is to keep the end-of-list marker EOL in the first free location. In a static operation, the data items in the list are accessed by sequentially reading memory. Thus, in one complete cycle, the contents of the entire memory can be accessed and used in the next process. When a plurality of linked lists are held in the memory, it is necessary to be able to describe the boundary position of each list. There are several ways to do this, such as maintaining an external count of the current length of each list. Alternatively, the list identifier 35 can be held using an additional field in the memory. For this reason, the total amount of memory required for processing increases, but it is not necessary to add an external control element. This is the method shown in FIG. This additional field can display one piece of information that needs to be stored in another way, so that no additional memory capacity is required. For example, in a telecommunications connection map application described below, the list number indicates the identity of the virtual channel in which each octet is assembled and the information that needs to be stored. FIG. 3 shows a process for updating the list. To update the list, the memory is sequentially moved in the usual manner until there is an item to be deleted or to the position of the item to be inserted. An insert or delete operation occurs at this point. Subsequent memory accesses move the original data down one location in memory to compensate for insertion, or up one location in memory. Go to make up for the deletion. In this way, the structure of the chained list can be completely updated in one complete memory cycle. Individual linked lists remain contiguous, and empty locations are still at the bottom of memory. The updated data list becomes effective in use from the subsequent memory cycle onward. Block 40 indicates the original state of the memory. Block 41 indicates the memory state after the memory cycle of performing a delete operation to delete item "334" from list 1. Block 42 further indicates the memory state after the memory cycle of adding an additional item "45" to linked list 2. Details of the system that performs the update process are shown in FIG. The system includes a general control component 54, a memory 52 for storing a chained list (the size of which is the same as the sum of the maximum lengths of all lists), and a single A memory access mechanism (the read and write pointer locations may be different) that can perform a read operation and a single write operation, a small FIFO 53 used for intermediate data storage during a shuffle down operation, And a comparator / logic function unit 51 for specifying the position of each update operation in the memory. The size of FIFO 53 is arbitrary, but there is an upper limit on the total number of inserts that can be performed during each memory cycle. This is because, as described later in detail, the process of inserting an item into the memory temporarily changes the position of some elements. This memory is preferably a standard RAM device. These components are desirably integrated in an ASIC. To perform the update, the control component must provide the process with list identity (and in the case of an insert, a new data item must be provided). In the simplest case, where new data is always added to the top of the list and old items are always deleted from the bottom of the list, this is enough information to perform the update process. However, this technique is not limited to pushing or popping data into memory; it allows data items to be inserted or deleted anywhere in each list. In such a case, the control component must also provide enough information for the process to be able to fully locate the insertion / deletion. This information may take the form of a relative position in the list (eg, the third item in list 4), or the value of a data item (deleted or currently at the insertion position). Can be Next, the insertion processing and the deletion processing will be described in detail. The term "memory cycle" refers to a single, sequential, full scan of the contents of the memory during which individual storage locations are searched and updated. "Access cycle" is a term that refers to searching one memory location during one such memory cycle. To insert new data items into the list, the memory is accessed sequentially in the usual manner until an insertion point is found. At this point, the contents of this storage location are transferred to the FIFO for temporary storage before a new data item is written to memory. In the next access cycle, the data item at the next storage location is put into the FIFO before it is overwritten (in memory) by the data held in the FIFO. This process continues until the end of the memory cycle, at which point all data items located after the insertion point will be moved back one position in memory. This process can be deployed such that multiple insertions are performed during a single memory cycle. This requires increasing the size of the FIFO to equal the desired maximum number of insertions per cycle, and separating the data items by control component in the order of insertion. As described above, when each input point is positioned, the data held in the FIFO becomes larger by one element, and the shuffle length becomes longer by the increased position. The removal process works in the same way. The memory is accessed sequentially until the location where the item to be deleted is found. At this position, the write pointer is set to be one position behind the read pointer. In the next access cycle, data read from the next memory location is written to the previous location (overwriting the item to be deleted). This process is repeated until the end of the memory cycle, at which point all data immediately following the delete point is advanced one position in memory. This process can be expanded so that a plurality of deletions can be performed within one memory cycle. In one deletion, the write pointer is further decremented by one position than the read pointer. Therefore, the shuffle length becomes longer. Since the insertion processing and the deletion processing are compatible, a plurality of insertions and deletions can be executed within one cycle. The only condition in this case is that the control component commands the update according to the input / delete position. In addition, it is also possible to perform an insertion operation and a deletion operation on the list continuously to change items in the list. Detailed examples of the update processing are shown in FIGS. In this example, three linked lists are held in 16 element memories. In one update, three inserts and two deletes are performed. It should be apparent that other combinations of insertion and deletion are possible. FIG. 5 shows a state at the start of a memory cycle before an update is performed. A series of update instructions for the cycle 50 are arranged in the order in which the update needs to be executed. FIG. 5A shows a state in the middle of the cycle, and the remaining three updates are waiting for execution. FIG. 5B shows the last state of the cycle. Table 1 describes in detail each step of this example, which lists the read and write operations and the contents of the FIFO for each of the 16 accesses of a complete memory cycle. . Note that the following notation is used when describing the read and write operations. "List number / data value ... storage location" For example, "1/3 from 1" means that data having the value "3" in list 1 is read from storage location 1. Table 1 (Update processing status during each access cycle) When a pure deletion update is performed on this configuration, that is, in an update in which a deletion operation is performed more frequently than an insertion operation in a previously full memory, it is necessary to reinsert the end-of-list boundary marker. One way to do this is to insert a marker in the next memory cycle using a spare write access. This is necessary because the write pointer is always behind the read pointer. The control component ensures that this method is incorporated into updates that are to be made in the next cycle. In very rare situations, where the immediately following update uses all available write accesses (ie, full memory shuffle), the control component needs to delay this new update by one cycle. is there. Alternatively, a housekeeping period may be provided between successive memory cycles where a "holdover" write cycle is performed. Update algorithm The details of the update algorithm will be described with reference to the flowchart shown in FIG. (A) Initialize Read_Ptr and Write_Ptr for the first position of the memory 52. The contents of the first update are read into the comparison circuit 51. (B) Read the storage location indicated by Read_Ptr into the FIFO. Read_Ptr for the next position is added and updated. (C) Compare the current update field with the contents held at the top of the FIFO in the comparator 51. (I) If the deletion position is found, the storage location indicated by the write pointer is overwritten with an empty marker (null marker). This write pointer is not additionally updated. The data content held at the top of the FIFO is destroyed. The comparison circuit 51 is updated with the next update content in the list 50. (Ii) If the insertion position is found, the storage location indicated by Write_Ptr is overwritten with the insertion data. This Write_Ptr is additionally updated to indicate the next storage location. The FIFO is not updated (the comparator uses the same data value in the next cycle when comparing with the updated content) and its length increases by one position. The comparison circuit 51 is updated by the next update content in the list 50. (Iii) If neither an insertion position nor a deletion position is found, the top content of the FIFO is written to a storage location indicated by Write_Ptr, and the FIFO advances by one position. Print_Ptr is additionally updated by one position. Alternatively, if the first update position has not been reached, the memory content indicated by Write_Ptr does not change after a write operation. Therefore, it is not necessary to perform a write access, and use this write access for other housekeeping tasks, such as performing some holdover write from the next frame cycle, caused by the pure delete operation described above. Can be. (D) Repeat steps (b) and (c) until the end of the map or until all updates have been performed (all insertions and deletions have been performed and the end of the file has been reached by the read operation, FIFO becomes empty). An application for which the method is particularly suitable is a telecommunications routing table. Details of this application will be described with reference to FIGS. 7 to 13A. Mechanisms are being developed to efficiently carry narrowband voice or data traffic over wideband ATM networks. This concept is shown in FIG. Synchronous narrowband traffic POTS, ISDN BA, ISDN PRA are carried through a 64 kb / s structure (fabric) 70. It terminates at the first interworking unit (interwork unit: IWU) 71. The IWU 71 converts the narrowband traffic into ATM cells, which are then transmitted through the ATM network 72 to the far-end IWU 73. This far-end IWU converts the narrowband traffic back to the synchronous domain for transmission to the farther 64 kb / s fabric 74. An ATM conversion device called an adaptive virtual junctor (AVJ) has been proposed. This device performs the task of assembling and disassembling the narrowband voice channel into an ATM payload while preserving the synchronous framing information of the original data. This is described in detail in patent application WO 95/35008 (Northern Telecom). AVJ performs bulk conversion. That is, all voice traffic destined for a particular trunk is combined into a single PVC cell stream for transmission over the ATM network. In consolidating traffic in this manner, the cell assembly delay typically associated with bundling voice traffic into ATM cells is greatly reduced. Further, by defining a minimum channel size (the minimum number of voice circuits integrated into a single PVC), a minimum cell assembly delay is guaranteed, eliminating the need for an echo canceller per voice circuit. . This considerably reduces the cost and complexity of the network. A second important function of AVJ is that bandwidth is allocated to destinations according to the instantaneous traffic load. Thus, the size of the PVC can be increased or decreased to match the number of voice channels currently connected to the associated trunk destination. If traffic drops below a specified minimum channel size, padding can be used to maintain a guaranteed cell assembly period. The input (ingress) function of the AVJ serves to convert the narrowband voice channel into cells before transmitting the cells over the ATM network 72. The output (egress) function of the AVJ plays a role of inverting the narrowband voice channel from the ATM cell to the synchronous domain. Within this system, there is a means by which the AVJ can maintain a dynamic connection table to bundle (pack) narrowband, frame-synchronous voice traffic into an ATM cell payload or unpack (unpack) it from the ATM cell payload. Required. The connection map needs to be continuously scanned and one complete scan occurs at a frame interval of 125 μs. This eliminates the need to use an existing (software-based) linked list structure. Furthermore, any ingress time slot must be able to connect to any egress time slot to provide full interconnectivity over the network. One way to do this is to provide a switching stage in both the ingress function and the egress function. This is shown conceptually in FIG. Each switching stage includes frame storage units 80 and 82, and access to them is controlled by connection maps 81 and 83. The frame storage performs a time switching function. That is, the order of loading and unloading can be changed. In this way, ATM cells can be packed and unpacked in any order, and the connection tables can be ordered in any way, while still achieving full interconnectivity. The problem with this method is that each switching stage results in a large time delay (of 125 μs), and the net effect of double switching exceeds the imminent narrowband delay budget specified in today's communication networks. Is to put it. Referring to FIG. 8, details of the ingress operation and the egress operation of virtual channel (VC) “A” will be described. On the ingress side, the payloads of the VC A are loaded in ascending order. That is, the data in the ingress time slot 2 follows the data in the ingress time slot 2 from the frame storage unit 80, and then the data in the ingress time slot 6 follows. However, on the egress side, this data needs to be delivered to time slots 2, 1, and 4, respectively. Therefore, the data does not follow the required order of positions in the structure of the egress time slot in its payload. To solve this problem, on the egress side, the frame store needs to provide an indirect level between the decomposition of the payload and the structure of the egress synchronization time slot. In this example, data from ingress time slot 1 is read from VC payload A and written to location 2 of egress frame store 82, and data from ingress time slot 2 is stored in egress frame storage. The data from ingress time slot 6 is written to position 4 in the egress frame store. Therefore, in the next 125 μs cycle, the frame storage unit configured in this cycle can be sequentially written to the synchronous backplane structure. Eliminating one of the switching stages can reduce the delay and balance the narrowband delay. The egress switching stage can be eliminated by assembling the ATM cells (at the ingress function) in the order required to unpack the ATM cells at the egress function. The narrowband channel can then be written directly to the synchronous backplane without the egress frame storage stage 82. This is shown in FIG. The payload of the virtual channel (VC) “A” is assembled in data order from the ingress time slots 2, 1, 6. On the egress side, no additional frames need to be stored and the payload is decomposed directly to the synchronization backplane. The egress map then simply asserts the VC, from which it retrieves the relevant data octets to be written to the synchronous backplane. Thus, in egress time slot 1, data octets from ingress time slot 2 are read from the payload and written to the backplane. In egress time slot 2, data octets from ingress time slot 1 are read from the payload and written to the backplane. Then, in egress time slot 4, data octets from ingress time slot 6 are read from the payload and written to the backplane. Thus, the ordering of the ingress connection map is dictated by the egress function. In order to set up a new connection, the egress function must signal the new call order related to other connections. This can be done with minimal signaling message overhead. This is because a full signal handshake is performed between the ingress function and the egress function as usual, and a reliable call setup procedure can be executed reliably. However, one new connection may require a complete reordering of the ingress connection table. This is not feasible with the conventional method of updating the connection map without interrupting the processing. The characteristics of the dynamic data structure manager described here are ideal for this process. Thus, the structure and maintenance of a dynamic connection table in the ingress function is an application of the present invention. FIG. 10 is a block diagram of the ingress function unit and the egress function unit. The ingress function unit includes a frame storage unit 80 in which synchronous narrowband data from the backplane is stored. The payload RAM 91 is used to store ATM cells while they are being constructed. Further, a prepared memory stores the connection map. Octets are read from the frame store under the control of the connection map and written to the payload RAM. The completed ATM cell is then sent over the ATM network to the egress function, where it is stored in the egress payload RAM and awaiting disassembly. These ATM cells are decomposed under the control of the egress connection table 90. Narrowband channels are written directly to the synchronous TDM backplane. The connection table is organized as a series of contiguous linked lists, one list for each trunk destination (identified by a PVC identifier). Each list contains the set of backplane addresses currently associated with the narrowband channel connected to its destination. The order of the addresses in the list indicates the order of unpacking on the egress side. In the static operation, the connection table is sequentially assigned an address, and for each non-empty storage location, the address information is used to store the voice channel on the TDM backplane stored in the frame storage unit 80. To access. On the other hand, the identifier of the chained list identifies which payload (channel A, B, C) the octet should be allocated to. Because the concatenated list is held contiguously in memory, it is a simple process for the AVJ to calculate the current channel size for each traffic destination when an ATM payload is included. It is easy to see that The current channel size is represented by the sum of the number of connections in the list. If the instantaneous channel size is smaller than the predefined minimum size, the padding of the payload is automatically activated and a predetermined transmission delay per narrowband circuit carried over the ATM network is maintained. The connection table needs to be updated when a new call is set up or an existing call is released. In order to add a new call, the egress function must signal the order of the new call in the VC. This order is calculated as an offset. For example, an offset of 0 indicates that the new channel will be the first channel in the VC. The ingress control component classifies the updates (multiple requests from multiple egress AVJs to which this component is connected) in VC order. The update of the connection table is shown in FIGS. 11 and 11A. The update request is presented on the connection map at the start of the frame. FIG. 11 shows a queue of three update requests, consisting of two new connections and one existing connection to be deleted. These updates are arranged in the order in which they are processed, with two updates corresponding to virtual channel A and one corresponding to virtual channel C. Since the connection table is accessed sequentially, the updated information is inserted or deleted along with the original connection information, and is shuffled in the memory accordingly. A complete update is performed with new connection information at one 125 μs frame interval and becomes effective from the next frame onward. FIG. 11A shows the state at the end of the memory cycle when the update is complete. It can be seen that this update process is completely transparent to the normal operation of ATM cell assembly. A further feature of the update process is that multicast calls can be easily connected and maintained. A multicast call consists of a single ingress backplane voice channel transcribed to several egress backplane connections, the concept of which is shown in FIG. A particular channel is replicated within a particular payload or for a number of different payloads. In FIG. 12, the contents of the frame store location "1" (indicating a particular narrowband channel) are duplicated twice in the payload for virtual channel A and once in the payload for virtual channel C. Be replicated. To set up a multicast call, the control component need only provide its processing with the TDM backplane address in the connection table and multiple insertion points (call replication is done within a single PVC). Or across multiple PVCs). If the connection table is updated, each duplicate call occupies one place in the connection map. The operation of providing a multicast call is completely transparent to other conversion processes. Providing a multicast call with this technique also has the important advantage that complicated octet duplication circuits are not required. This is because the data is simply read from the frame store, rather than being duplicated. FIGS. 13 and 13A show processing for updating the connection table and supporting the multicast operation. FIG. 13 shows a queue of three update requests, where the contents of location "1" in the frame storage are added twice to channel A and once to channel C. FIG. 13A shows the resulting updated connection table.

────────────────────────────────────────────────── ─── Continuation of front page    (81) Designated countries EP (AT, BE, CH, DE, DK, ES, FI, FR, GB, GR, IE, IT, L U, MC, NL, PT, SE), CA, JP, US (72) Inventor Stacy David John             England, ESG12 8H,             Hartford Shear, Stansted             Abbott, Orchard Close 28

Claims (1)

[Claims] 1. A small list of data elements stored in a predetermined order of storage locations of the memory device. In a method of reading and updating at least one,   Provide read and write pointers that can point to individual memory locations Providing,   Using the read pointers, in the order in which the elements of the list were stored Reading the elements of   During the reading of the list, the write pointer is used to read the already read record. Updating the list by writing elements to the memory location, The read elements are the elements read in the read step and the new elements inserted in the list. Comprising the steps of   The step of updating includes, when the list is read, as a result, the predetermined order. Moving a portion of said list through an introductory storage location. 2. The elements of the list are maintained in order and the process of updating this list The procedure is to insert a new element at a specific position in the list, or Maintain the order of the list by removing or modifying existing elements in The method of claim 1, comprising the step of: 3. Further, storing a set of instructions for updating the list of data elements. Arranging the sets according to the order in which the lists are accessed. The method of claim 1, comprising the steps of: 4. The storage locations in the predetermined order are a series of adjacent storage locations. The method of claim 1, wherein 5. The step of updating the list includes inserting a new element at a specific position in the list. And storing the data elements prior to the position in the predetermined order. Move through the place to make room for the new element, 3. The method according to claim 2, further comprising the step of inserting an element into the space. The method described. 6. The step of updating the list comprises the step of updating an existing item at a particular position in the list. And deleting the data element in the direction returning from the position to the predetermined position. Providing a step to move through the order storage location and overwrite the existing item 3. The method according to claim 2, further comprising the steps of: 7. Writing the element to a memory location each time an element of the list is read. The method of claim 1, comprising: 8. Further, the contents of the storage location determined by the read pointer are stored in a second Reading into memory,   In the storage location determined by the write pointer, Whether to write the oldest content or a new item to be inserted into the list, Or a step of writing nothing. The method of claim 1. 9. The second memory operates as a FIFO device. Item 9. The method according to Item 8. 10. Deleting an existing element at a particular position in the list may include By setting the write pointer to be later than the read pointer, The data element in the direction from the delete position is returned through the storage locations in the predetermined order. 3. The method according to claim 2, further comprising the step of moving. 11. Inserting a new element at a specific position in the list,   Reading the data element stored at the location into a second memory;   Writes the new element to the memory location and on subsequent accesses will be at the next location Reading the data element into the second memory and storing the data element in the second memory By writing one oldest data element to the next location, the new element Moving the data elements that precede the element through the predetermined order of storage locations; 3. The method according to claim 2, comprising: 12. A method for managing a connection map of a telecommunications switch, this map A list of the switch connection instructions stored in a predetermined order location in the memory. And the method is   Provide read and write pointers that can point to individual memory locations Providing,   Using the read pointer, in the order in which the instructions of the list were stored, Reading the instruction of   During the reading of the list, the write pointer is used to read the already read record. Updating the list by writing instructions to the memory location, The read instruction is the instruction read in the read step and the new instruction inserted in the list. Comprising the steps of:   The step of updating includes, when the list is read, as a result, the predetermined order. Moving a portion of said list through an introductory storage location. 13. In a method of operating a telecommunications switch,   Receiving data from a plurality of sources at an input to the switch;   Buffering the received data;   Assembling the received data into a payload,   Transmitting the payload from the output of the switch to a plurality of destinations. e,   The method further comprises the step of managing a connection map according to claim 12, wherein The connection instruction is used to determine in which payload the buffered data is to be assembled. A method characterized in that: 14． The connection map shows the order in which the payloads are decomposed at their destination Contracts that are ordered to assemble these payloads. 14. The method of claim 13. 15. The received data comprises a narrowband channel, and the 14. The method of claim 13, wherein the code comprises a payload of an ATM cell. . 16. In addition, a request for a multicast connection between the source and multiple destinations Receiving the   Creating a set of update instructions for the map;   Updating the map with the set of update instructions while using the map. 14. The method of claim 13, comprising providing. 17． Aggregating the elements of the map, further indicating a connection to a particular destination; When,   Calculating the size of the payload corresponding to the total,   Determining whether padding of the payload is required;   Activating padding according to the result of the determination. The method of claim 13. 18. In an apparatus for managing at least one of a list of data elements,   A storage device for storing the data elements in storage locations in a predetermined order;   Provide read and write pointers that can point to individual memory locations Means to provide;   Using the read pointers, in the order in which the elements of the list were stored Means for reading the elements of   During the reading of the list, the write pointer is used to read the already read record. Means for updating the list by writing elements to a storage location, The elements read are the elements read by the reading means and the new elements inserted in the list. Said means consisting of the elements of the   The updating means, when the list is read, results in the predetermined order. Apparatus for moving a portion of said list through an introductory storage location. 19. An input for receiving data from a plurality of sources;   A buffer for storing the received data;   Means for assembling the received data into a payload,   An output unit for transmitting the payload to a plurality of destinations,   At least one of a list of data elements in a predetermined order of locations in memory A memory for storing a map of connection instructions,   A management unit that manages the map,   Provide read and write pointers that can point to individual memory locations Means to provide;   Using the read pointers, in the order in which the elements of the list were stored Means for reading the elements of   During the reading of the list, the write pointer is used to read the already read record. Means for updating the list by writing elements to a storage location, The read element is the element read by the reading means and the new element inserted in the list. Comprising the element, the management unit having the means,   The updating means, when the list is read, results in the predetermined order. Moving a portion of said list through an introductory storage location. Itch. 20. 20. A device for managing a connection map used for the telecommunication switch according to claim 19. 21. In the method of updating the data structure,   The structure includes an ordering of the data elements stored in a predetermined order in the memory device. And at least one of the following lists: , Or updating the structure by changing, maintaining the order of the elements, And ensure that reading of the element is not interrupted while the update is being performed A method comprising the steps of: