Modular architecture pet decoder for ATM networks

Details Modular architecture pet decoder for ATM networks Modular architecture pet decoder for ATM networks

1998-09-02

2001-08-14

Patel, Ajit (Department: 2732)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C714S746000, C708S492000, C708S518000

Reexamination Certificate

active

06275495

ABSTRACT:

FIELD OF THE INVENTION
The invention relates in general to digital transmission networks functioning in an Asynchronous Transfer Mode (ATM), and, more particularly, to an error correcting technique for Priority Encoding Transmission (PET).
BACKGROUND OF THE INVENTION
In recent years a widespread use of digital techniques for storing and transmitting information has been witnessed. The success of these techniques is due to the availability of cost effective hardware components. Among network technologies dedicated to the above cited services, the ATM technique (Asynchronous Transfer Mode) permits the transmission of multi-media information in a flexible and efficient manner. The ATM technique was developed to solve all aspects of multi-media applications, video, audio, and data transmissions on a same network, with the same protocol, regardless of the type of network (LAN, MAN or WAN).
The ATM technology provides for a bandwidth with a variable bit-rate that may reach the order of Gigabit/sec and a scalability of the number of network nodes as required by the general architecture of switched networks. Differently from switched circuit networks, the ATM packet-switched network has the advantage of engaging the channel only during the actual transfer of information.
The procedure of traffic control of ATM networks has not yet reached a consolidated standard, with many problems still remaining to be solved. One of the main problems of this technology is the possible loss of packets, which in case of video transmissions may result in a degradation of the images that exceeds acceptable levels. Indeed, in some instances the average loss of packets may reach peaks of about 5%. A loss of packets may occur for different causes:
when the packets arrive after the maximum permitted time delay;
when the buffer overflows, that is, when its filling threshold is exceeded; or
when traffic congestion occurs due to an abrupt variation of the information flow or network hardware problems.
If traffic congestion occurs and some packets are lost, the network is unable to ensure satisfactory service. To provide for adequate bandwidth characteristics, an ATM-base should have the ability to implement a traffic control procedure like, for example, a Call Admission Control (CAC) or of a local control at node level (control of the average and peak number of packets reading the interconnection buffers). Although such procedures may be implemented at their best, packet losses would be in any case inevitable because of the intervention of policing structures through intelligent agents, and in the case of machine malfunctions.
The method developed by Berkeley and referred to as PET (Priority Encoded Transmission)are disclosed in A. Albanese, J. Blömer, J. Edmonds, M. Luby: Priority Encoding Transmission, Technical report, International Computer Science Institute, Berkeley, Calif., August 1994. The method is based on coding the information with different levels of redundancy depending on its importance.
The PET technique is based upon a redundant coding of original information distributed over a plurality of distinct packets. The redundance added during the coding phase is such that, even in case of loss of coded packets, the original information can be fully retrieved from the information existing in the remaining packets.
The PET Coding Algorithm
The PET coding technique as disclosed in M. O. Rabin: Efficient Dispersal of Information for Security, Load Balancing and Fault Tolerance, Journal of the Association for Computing Machinery, Vol. 36, No. 2, April 1989, is an algorithm of information dispersion that includes adding, to the message to be transmitted, a proper redundance, before dividing this encoded message into a plurality of portions which represent the packets that are sent through the transmission medium. Even by receiving only a fraction of the total number of the packets it is possible to reconstruct the original message. See also R. Storn: Modeling and Optimization of PET-Redundancy Assignment for MPEG Sequences, Technical report, International Computer Science Institute, Berkeley, Calif., August, May 1995.
The original information stream is divided into a set of messages, coded independently one from the other, as depicted in FIG.
1
. Hence, each message is divided into segments, each having a certain priority grade. The priority is generally specified in terms of the minimum percentage of packets of the whole message required to correctly decode the segment as disclosed, for example, in A. Albanese, M. Kalfane, B. Lamparter, M. Luby: Application Programmer Interface to PET, Technical report, International Computer Science Institute, Berkeley, Calif., Aug. 25, 1995; and C. Leichner: Hierarchical Encoding of MPEG Sequences using Priority Encoding Transmission (PET), Dissertation, International Computer Science Institute, Berkeley, Calif., November 1994.
The number of blocks for each segment depends on its length and corresponding priority. The priority of a segment is expressed in terms of its blocks' length: the higher the priority the shorter are the blocks, as shown in FIG.
2
. For each segment, the length of the block is the same, because they have the same priority.
The PET coding technique includes considering the m words of the different blocks as the coefficients of a polynomial of order m−1 over a Galois field GF[p], as illustrated in FIG.
3
. The polynomial of order m−1, evaluated at different n points over a Galois field GF[p], is uniformly distributed on n packets.
The current implementation of the PET technique is based on erasure codes and considers the use of integer arithmetic instrumental within the Galois field GF[p] (that is the field of the rest of p modulus), within which all the operations are with modulus p. The original information stream is considered as a sequence of unitary elements (for example, bytes of 8 bits or words of 16 bit), which for simplicity in the ensuing text will be referred to as “words”.
After having divided the messages into segments, the segments are partitioned into blocks, so that all blocks of the same segment have the same length m (represented by the number of words) according to a scheme as that depicted in FIG.
4
. Of course, blocks belonging to different segments may have different lengths.
The m words of each block are considered as the coefficients of a polynomial of order m−1 over the GF[p] field:
 p(x)=a
0
+a
1
x+a
2
x
2
+ . . . +a
m−1
x
m−1
The coding of the block is formed by the sequence of the n words (n≧m) obtained by evaluating the polynomial at n distinct points of GF[p]. These n values are distributed in n packets so that each packet contains only one value of p(x), calculated in a distinct point of GF[p].
The above described algorithm is repeated for each single block of each segment, and the sequence of packets that encode the original message is obtained by grouping within the same packet the polynomial values evaluated for the same point of GF[p] relative to all the segments. In this way, the information relative to each segment is uniformly spread over all the packets.
Of course, when words of 16 bits are mapped over the field GF[2
16
+1], there will be a high probability of not using an element of the Galois field. To avoid possible overflow problems, it is possible to operate always with units of 16 bits (even after the mapping), by eliminating the unused element and keeping its location (which will be referred to as its offset or by the symbol &egr;) properly stored to be able to recover the original value after having completed the execution of the required operations.
Besides the offset of the point at which the polynomial is evaluated, it is necessary to introduce the information relative to the priority of the various segments and to their length, to be able to exactly reconstruct the original message. This information defines a further segment, which in the ens

Affiliated with

Also associated with

Rating

Modular architecture pet decoder for ATM networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Modular architecture pet decoder for ATM networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular architecture pet decoder for ATM networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2523240