Method for associating data with ATM cells

Details Method for associating data with ATM cells Method for associating data with ATM cells

1998-02-02

2001-06-12

Chin, Wellington (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S252000, C711S216000, C714S781000

Reexamination Certificate

active

06246686

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a process for associating data with ATM cells reaching an item of ATM network equipment via virtual connections.
It is known that in ATM (“asynchronous transfer mode”) technology, virtual connections are established between the items of equipment attached to the network, within the physical links which exist between these items of equipment. Each virtual connection is designated by a pair of identifiers which are retrieved from specified fields of the header of each cell transmitted over this virtual connection:
a virtual path identifier, or VPI, which generally designates resources allocated in a semi-permanent manner;
a virtual channel identifier, or VCI, which designates resources allocated dynamically within the virtual paths.
The switching equipment of the ATM network carries out the routing of each packet, or cell, on the basis of one or other (or both) of the VPI-VCI identifiers read from its header.
According to the applicable standards (ITU-T Recommendation I.361), the VCI is composed of L
c
=16 bits, and the VPI is composed of L
p
=8 bits at a user-network interface (UNI) and of L
p
=12 bits at a network node interface (NNI). ITU-T Recommendation I.361 further prescribes, in paragraphs 2.2.3 and 2.3.2, that:
the bits of the VPI field that are used be contiguous;
the bits of the VPI field that are used be the least significant bits of the VPI field (starting from bit 5 of byte 2 of the cell header);
the bits of the VCI field that are used be contiguous;
the bits of the VCI field that are used be the least significant bits of the VCI field (starting from bit 5 of byte 4 of the cell header);
the non-assigned bits, that is to say those not used by the user or by the network in the 28-bit routing field, be set to 0.
The coding of the VPI-VCI pairs permits the differentiation of 2
28
, i.e. more than two hundred and sixty million virtual connections within each physical link. In practice, operators only use a much smaller number of virtual connections (typically of the order of 4,000).
Since the cells pertaining to the established virtual connections reach the equipment of the network randomly and at a very high rate, this equipment must be capable, on the basis of the VPI-VCI pairs read from the header of the cells, of very rapidly associating data with cells so as to adopt an appropriate response.
The simplest way of doing this would be to use a random access memory (RAM) where the data would be stored at addresses specified by the VPI-VCI pairs. However, the cost of the memory with a 28-bit index would be prohibitive for a derisory return when only a few thousand virtual connections are active.
Another approach is to use a dichotomy search, requiring a search loop, whose execution time is logarithmic as a function of the number of records, in a table in which the records are ranked in increasing or decreasing order of the VPI-VCI keys. In the context of ATM network equipment, this approach requires extremely fast electronics.
It is also possible to envisage using, as in EP-A-0 600 683, associative or contents-addressable memories (CAM). This solution has the drawback of being bulky and very expensive.
Within the realm of computer programming, a hashing technique is commonly used for the fast lookup of translation tables, as for example for databases or language compilers (see Knuth: “The Art of Computer Programming”, Vol. 3, Addison-Wesley 1973, pages 506-542). This technique relies on the use of a hash function which randomly reduces the long access key into a shorter code, termed the H code. The purpose of this random function is to spread the H codes evenly over a reduced random access range. One example, derived from the cyclic code technique, of a usable function relies on polynomial division (see R. Jain: “A Comparison of Hashing Schemes for Address Lookup in Computer Networks”, IEEE Trans. on Communications, Vol. 40, No. 10, October 1992, pages 1570-1573). Conflicts arise when the same H code is associated with several different access keys. These conflicts are resolved by a routine for searching through secondary overflow strings, which makes it possible to retain a very short mean execution time for the search. However, as noted in the aforesaid work by Knuth (page 540), hashing methods are only efficient on average, and the search time may be very long in unfavourable cases. This is due to the fact that the duration of a search through the secondary strings in the case of conflict is not bounded. These methods therefore appear to be unusable for the problem of the real-time association of data with ATM cells, since the execution time for the search must remain less than a cell time in order for the bit rate specifications to be complied with.
An object of the present invention is to propose an efficient and economic search procedure for associating data with ATM cells.
SUMMARY OF THE INVENTION
The invention proposes a method for associating data with ATM cells reaching an item of ATM network equipment via virtual connections. The process comprises, when establishing each of the virtual connections, the adoption of a pair of identifiers comprising a virtual path identifier of L
p
bits and a virtual channel identifier of L
c
bits, and the storage, in a table of the item of equipment, of data relating to said virtual connection in relation to its identifier pair. The method further comprises, at the arrival of each ATM cell whose header includes the identifier pair of one of the virtual connections, the reading from the table of data relating to said virtual connection. According to the invention, the table includes p.2
m
storage areas organized as 2
m
rows and p columns, m and p being integers at least equal to 1, and the data relating to a virtual connection are stored in an area of the table whose row is labelled by an m-bit index calculated by applying a systematic cyclic code, the generating polynomial of which is of degree m, to a binary word of L bits (L≦L
p
+L
c
) extracted from a sequence of L
p
+L
c
bits which consists of the bits of one of the identifiers of the pair adopted in respect of said virtual connection, arranged in order of decreasing significance, followed by the bits of the other identifier of said pair, arranged in order of increasing significance.
The calculation of the index by means of a systematic cyclic code is comparable to a hashing function. However, the two-dimensional organization of the table makes it possible to bound the execution time for a search. It is not organized as a dynamic overflow table as in the software hashing technique. If p pairs VPI-VCI having the same index are already active and if a (p+1)th pair (VPI-VCI) giving rise to the same index happens to be envisaged in respect of a new virtual connection to be established, then this (p+1)th pair will be rejected. An appropriate dialogue with the item of equipment located at the other end of the virtual connection will then enable another pair to be chosen. The probability of occurrence of such a rejection can be made very small through appropriate dimensioning of the table.
Moreover, in a large number of cases no conflict at all will occur. The ordering of the bits of the VPI and VCI identifiers makes it sufficient to take p=1 for no conflict to arise up to a number of established connections equal to 2
m
when the assigning of these identifiers obeys the rules stated in paragraphs 2.2.3 and 2.3.2 of ITU-T Recommendation I.361. This absence of conflicts results from the properties of the cyclic codes.
The table may also be composed of p=2
s
columns, with s≧1. The data relating to a virtual connection may then be stored without any risk of conflict (up to 2
m+s
connections if the rules of ITU-T Recommendation I.361 are complied with) in an area of the table whose column is labelled by an index defined by s bits with specified positions of the identifier pair of this connection. These s bits (typically s=1 or 2) make it possible

Affiliated with

Also associated with

Rating

Method for associating data with ATM cells does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for associating data with ATM cells, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for associating data with ATM cells will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2467550