Method for translating an ATM switch cell header
Patent ReferencesMethod and data structure for performing address compression in an asynchronous transfer mode (ATM) system Method for reducing the number of bits in a binary word representing a series of addresses Label handling in packet networks Channel identifier generation Method and device for the translation of a cell header applied to the entrance to a node of an asynchronous network for the transmission of data by packets Computer network interface and network protocol with direct deposit messaging Cell routing in ATM networks Method and apparatus for ATM switching Identifier translation apparatus Method and apparatus for full range translation of large external identifier to small internal identifier InventorsApplicationNo. 11119494 filed on 06/12/1998US Classes:370/395.31Including routing tableExaminersPrimary: Pham, ChiAssistant: Phan, Tri H. Attorney, Agent or FirmForeign Patent References
International ClassH04L 12/56DescriptionBACKGROUND OF THE INVENTION1. Field of the Invention The present invention relates to a process for translating a header of a cell applied to the input of a node of an asynchronous packet data transmission network. It applies in particular to the digital data switching and cross-connection equipment making up a network operating in the mode of transmission known by the abbreviation ATM standing for "Asynchronous Transfer Mode". 2. Discussion of the Background The ATM asynchronous transfer mode is mainly defined in the recommendations of the ITU-T (series I), as well as in the work of an industrial grouping dubbed the "ATM Forum". In the ATM asynchronous transfer mode the information to be transmitted is grouped together in the form of packets. Together, header plus data is dubbed a cell. Basically, ATM operates in a connected mode, that is to say it has to establish aroute through the transmission network before being able to transmit the data. This route is termed a "virtual circuit". There are in general numerous virtual circuits which follow the same physical connection between two items of ATM equipment. Themain role of the header of the cells is to allow the identification of the virtual circuits over the link. An example of implementing such a process is known in particular from French Patent Application No. 2 681 164 filed in the name of the Applicant. A virtual circuit is obtained by placing end-to-end virtual communication pathways established between adjacent switches. These pathways are of two types: virtual paths or virtual channels, the virtual channels being regarded as a subdivision ofthe virtual paths. On a given highway, any virtual circuit is fully determined by indicating the identifier of the virtual path (VPI) and that of the virtual channel (VCI) which it follows, in the case of a circuit to be switched in VC mode (VCC), orelse by indicating just the identifier of the virtual path (VPI), in the case of a circuit to be switched in VP mode (VPC). According to this process, each cell to be routed within a network is composed on the one hand of a header making it possible to identify it and guide it through the pathways making up the virtual circuit, and on the other hand, of a partcontaining the information to be conveyed. Routing is effected at the level of each node of the network by extracting from the header the address of a word contained in a first context memory containing the information required for identifying theheader and for guiding the data to be conveyed and by creating a new address on the basis of the word read from the first context memory. This new address serves as a pointer to an area of a second context memory in which there is at least one newheader and one outgoing direction information cue for the cell or cells existing the node. The translation function which is thus carried out makes it possible for each cell to be associated with the information enabling it to undergo the processing operations for which it is intended. The translator which is responsible for executingthis function on each cell which it receives must typically provide information about the validity of the virtual path identifier, the validity of the virtual channel identifier, counting, the list of outgoing directions in which the cell received istransmitted, the new header associated with the cell during its transmission etc. The translator must also execute the processing operations corresponding to the context defined previously for each cell. These processing operations relate in particularto virtual path (VP) switching, virtual channel (VC) switching and the extracting of the maintenance flows. From the structural standpoint the translation function is carried out with the aid of a memory plane addressed by a microprogrammed processing unit. However, this very large memory plane, whose size may contain for example 232 words of 16 bits, is difficult to manage. To alleviate this difficulty, the French Patent Application published under No. 2 726 669 filed by the applicant proposed that the memory space of the node be addressed on the basis of the virtual path number VPI contained in the header of thecell so as to identify in this space a first context area indicating the range of the virtual channels which can be used by the cell for this VPI and that a second context area be addressed on the basis of a virtual channel number VCI contained in theheader of the cell and of a base address read from the first context area so as to obtain the list of directions which the cell must take on exiting the node, as well as the new header. However, this process proves to be poorly suited to the constraints imposed by the new virtual interfaces of switches such as for example the "Virtual UNI" interface specified in chapter A7-4 of the ATM Forum's "UNI signalling version 4.0"specification. It does not for example allow a rearrangement of the translation memory when there is a modification in the number of users who, on one and the same physical interface, are sharing the virtual path capacities. This is manifested through the appearance of gaps in the translation memory which limit the possibilities for utilizing the whole spectrum of possible VPI and VCI values. The purpose of the invention is to alleviate the above-mentioned drawbacks. SUMMARY OF THE INVENTION To this end, the subject of the invention is a process for translating an ATM cell header for the routing thereof on a transmission highway of a communication network via an ATM switch, the header of the cell comprising a first field VPI and asecond field VCI, the first field VPI identifying a virtual path number and the second field VCI selecting a specified virtual channel within the virtual path, characterized in that it consists: in storing indirect addressing context page numbers in afirst major table, in storing context page numbers for the circuits in VP switching mode in a second major table, in storing context page numbers for the circuits in VC switching mode indirect addressing context pages, in addressing the context pages ofcircuits in VC switching mode by way of an indirect addressing context page of the context page numbers on the basis of the first major table and of the second field VCI, and in addressing the context pages of the circuits in VP switching mode on thebasis of context page numbers contained in the second major table. The main advantage of the invention is that it associates the N contexts determined by the available memory size with a number of connection of the same order of magnitude as N, even if the identifiers (VPI, VCI) of its connections describeranges of values which are multiples from among the 228 theoretically possible values. It also allows partial modifications of the configuration of a network consisting for example in modifying a VP switching mode into a VC mode for a specified VPIvalue or else in activating/deactivating a consequent string of VPI values, without impairing the operational functioning involving the VPI and VCI values for which the modification is not relevant. As another advantage the size of the translationmemory is suited to the strict need of a limited number of connections (either VPC or VCC), this number being small relative to the numbers of possible combinations of the VPI/VCI values. On the other hand, the translation operations, especially thosegiving rise to slow memory accesses, are reduced to a minimum number, thereby making it possible to process ATM flows with high bit rates of for example greater than 155 Mbps. Finally, it allows the installation of a temporary bypass to a built-in testprobe in VP switching mode so as to observe the traffic over certain virtual channels VC. BRIEF DESCRIPTION OF THE DRAWINGS Other characteristics and advantages of the invention will emerge from the following description which is given with regard to the appended drawings which represent: FIG. 1 the organization of a translation memory according to the invention. FIGS. 2A and 2B the format of a VPI field of a cell header. FIG. 3 the format of a VCI field of a cell header. FIG. 4 a diagram illustrating the mode of addressing implemented by the invention in order to access contexts in the VP and VC switching modes. FIG. 5 a flow chart representing the sequencing of the various steps according to the invention of the process for addressing the translation memory so as to steer an incoming ATM cell inside a switch. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS According to the embodiment of FIG. 1, the translation memory 1 is structured as a block of general-purpose context pages 2, that is to say pages which are used both in respect of the information relating to the circuits in VP mode, in VC mode,or to contain indirect addressing information. All the pages have an identical size. They contain a number of elementary information cues ("contexts") which depends on the type of page concerned. In this embodiment a page can be addressed on the basisof a first 3 or a second 4 major indexing table which respectively store indexation fields relating to the circuits in VC and VP mode. The tables 3 and 4 are addressed by the high-order bits of the field VPI read from the header of each incoming ATMcell in the switch. In VC switching mode the VPI field is formed of the areas VPI0, VPI1, VPI2 and VPI3 represented in FIG. 2A and in VP switching mode, the VPI field is formed of the areas VPI0, VPI1 and VPI4 represented in FIG. 2B. In FIG. 2B thearea of bits VPI4 has a length equal to the sum of the bit lengths of the areas VPI2 AND VPI3 of FIG. 2A. The field VCI used for switching in VC mode and which is represented in FIG. 3 is formed by the fields, VCI0, VCI1 AND VCI4. The addressing of the context page on the basis of the major tables 3 and 4 takes place in accordance with the diagram of FIG. 4 in which the elements akin to those of FIG. 1 are represented with the same reference. For switching in VC mode themajor table 3 is addressed by the high-order bits VPI1 and VPI2. The word found M1 serves as a pointer to an indirect addressing context page 5 which catalogues the addresses of the context pages of the page block 2. In FIG. 4 the addresses of thecontext pages are situated at the crossovers between rows and columns. The address of a row is obtained by appending at 6 to the page pointer found in the major table 3, the content of the area VPI3 of the field VPI. The word M2 which is thusfound at the address indicated by the areas (M1, VPI3, VCI1) is next used as a pointer to a context page VCC7. The sought-after context area M3 is found inside the context page 7 by appending at 8 to the pointer M2 the content of the areaVCI4 of the field VCI. In VP switching mode, the address of the context page 9 is found by reading the word M4 from the major table for indexing in VP mode at the address supplied by the area VPI1 of the field VPI. The sought-after context areaM5 is next found inside the context page 9 by appending at 10 the content of the word M4 to the content of the area VPI4 of the field VPI. According to one of the characteristics of the invention the size of the VPC and VCC contexts is constant and is determined by the relation TVPC=T.sub.VCC=2M where M is an integer which is independent of the sizes of pages. The size ofan indirect addressing context is TIND=1. Denoting by Np0, Np1, Np2, Np3 and Np4 the numbers of bits making up the areas VPI0, VPI1, VPI2, VPI3 and VPI4 respectively of the field VPI and by Nc0, Nc1 and Nc4 the numbers of bits making up the areas VCI0, VCI1 and VCI4 respectively, thesize of the context pages is defined as follows: size of a VPC context page=2Np4,TVPC size of a VCC context page=2Nc4,TVCC size of a page of indirect addressing contexts=2NP3,2NC1,TIND. Since the size of the pages is constant the above relations make it possible to write Np4=Nc4=Nc1 Np3-M Furthermore, the following relations exist: Np0 Np1 Np2 Np3=P Np2 Np3=Npy Nc0 Nc1 Nc4=C=28-P The sizes of the major tables have respective values 2Np1,2Np2,TIND for the major table (VC mode) 3 and 2NP1,TIND for the major table (VP mode) 4. Taking as parameters P=12, the following relations are obtained. 2Np1=Nc0-Np0 2P M-20 2Nc1=Np0-Nc0-2P M 36 2Np2=Np0-Nc0-2P-M 36 2Nc4=2Np4=20-M-Np0-Nc0 2Np3=2P-16-2Np0 By way of example, a dimensioning with M=5 may be as follows: (Np0,Nc0)=(2,5) bits or (1,4) bits or (1,0) bits Np1=0 or 1 or 4 or 5 bits depending on the number of active bits of the field VCI, and this gives: a block of 255 pages, a major tablefor a VC switching of 64 words of 4 bytes, the size of an input being dependent on the chosen page size, a major table for a VP switching of 16 words of 4 bytes, the size of an input being dependent on the chosen page size, a single size of context of 8words. An algorithm for implementing the addressing process according to the invention is described below with the aid of steps 11 to 21 of the flow chart of FIG. 5. In this flow chart the translation process commences at step 11 with a check of the validity of the virtual circuit identifier by extracting through logical intersection, for example, the bits of the area VPI0. If the identifier is notvalid.Iadd., .Iaddend.the cell is rejected in step 19. If the identifier is validated, step 12 is executed in order to access, in the major table 3, the pointer M1 of an indirect addressing page at the address indicated by the areas VPI1 and VPI2. If the pointer M1 is null, the VP switching mode is selected by fetching in step 13 the word M4 from the major table 4 at the address indicated by the area VPI1. If the content of the word M4 is not null.Iadd., .Iaddend.a VP context isselected in step 14 from the context page M4 of the VP switching mode, at the address indicated by the content of the field VPI4. In the case in which the word M4 is null.Iadd., .Iaddend.the cell is rejected in step 15. If the test performedin step 12 indicates that the content of the pointer M1 is not null, then a VC context page is selected in step 16 at the address indicated by the page pointer M2 found inside the indirect addressing context 5 page M1 at the addressindicated by the fields VPI3 and VCI1. If M2 is null.Iadd., .Iaddend.we return to the VP switching mode and we go to step 13. If M2 is not null, a test is performed in step 17 on the content of the field VCI0. If the later is .Iadd.not.Iaddend.null.Iadd., .Iaddend.a context is selected in step 18 from the VCC context page addressed by the pointer M2 at the address indicated by the content of the field VCI4. If VCI0 is null.Iadd., .Iaddend.the cell is rejected in step 19. Uponthe two cases of error which are identified in this flow chart (15 and 19), specific counters can be incremented. Furthermore, during steps 14 and 18, a check is carried out in the context reached to verify whether the VPC or the VCC concerned is activebefore performing the translation. Variants to this process may be implemented for the addressing of pages, of 16, 32 and 128 contexts. By way of example, the addressing of pages with 16 contexts can take place by performing the following operations referenced from (a to k): a)extract the 2 high-order bits of the field VPI and increment the violations counter if these bits are not null b) take the next 6 bits (VPI1) and address the VPI major table of the VC switching mode. c) read the selected word d) take the next 2 bits(VPI2) and address (in the selected word) the byte designating the page of indirect addressing contexts; e) if the page pointer is null, take the 6 bits from 10 to 4 (VPI1) and address the VPI major table of the VP mode, read the selected VP page pointerif this pointer is not null, the mode of switching is VP then go to the execution of k. else reject the cell (increment a counter) f) Else, take the next 2 bits (that is to say the last 2 bits of the VPI field) (VPI3) and select the indirect addressingcontext from the page. g) take bits 11 to 5 of the VCI field (VCI1) and in the indirect addressing context address the pointer on the VC page. h) if the pointer is not null (VC switching mode), check that there is no violation by comparing the first 5bits of VCI (VCI0) with the null value. If there is violation, increment the violations counter and reject the cell, i) otherwise, select the VC context from the VC page on the basis of the 4 low-order bits of the VCI field (VCI4). test the activityindicator of this VC context before using the information of this context. If the indicator is inactive, reject the cell (increment a counter). j) If this pointer is null, 2 cases may arise: VP mode of switching or VC context inactive in the VCswitching mode: take the 6 bits from 10 to 4 (VPI1) and address the VPI major table of the mode VP of switching in fast memory read the selected VP page pointer if this pointer is not null, the case is a VP switching mode (then go to k) else the case isa VC switching mode with VCC inactive: reject the cell (increment a counter) k) VP mode of switching take the last 4 bits of the VPI field (VPI4) and select the VP context from the selected VP page test the activity indicator of this VP context beforeusing the information of this context. If the indicator is inactive, reject the cell (increment a counter). Similar operations can be executed for the addressing of pages with 32 and 128 contexts. Field of SearchSwitching a message which includes an address headerProcessing of address header for routing, per se Distributed switching Employing logical addressing for routing (e.g., VP or VC) Centralized switching Employing logical addressing for routing (e.g., VP or VC) Message transmitted using fixed length packets (e.g., ATM cells) Connection identifier assignment Including routing table Assembly or disassembly of messages having address headers Address transmitted |
| ||||||||||||||
