WO1998003034A1 - Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante - Google Patents
Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante Download PDFInfo
- Publication number
- WO1998003034A1 WO1998003034A1 PCT/FR1997/001286 FR9701286W WO9803034A1 WO 1998003034 A1 WO1998003034 A1 WO 1998003034A1 FR 9701286 W FR9701286 W FR 9701286W WO 9803034 A1 WO9803034 A1 WO 9803034A1
- Authority
- WO
- WIPO (PCT)
- Prior art keywords
- operator
- shift
- sequence
- exponential
- exponential mean
- Prior art date
Links
- 238000000034 method Methods 0.000 title claims abstract description 14
- 238000004364 calculation method Methods 0.000 claims description 10
- 230000005540 biological transmission Effects 0.000 description 3
- 238000001914 filtration Methods 0.000 description 2
- 230000010355 oscillation Effects 0.000 description 2
- 230000006870 function Effects 0.000 description 1
- 230000007774 longterm Effects 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L12/5602—Bandwidth control in ATM Networks, e.g. leaky bucket
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04Q—SELECTING
- H04Q11/00—Selecting arrangements for multiplex systems
- H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
- H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
- H04Q11/0478—Provisions for broadband connections
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5625—Operations, administration and maintenance [OAM]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5629—Admission control
- H04L2012/5631—Resource management and allocation
- H04L2012/5632—Bandwidth allocation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5638—Services, e.g. multimedia, GOS, QOS
- H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
- H04L2012/5652—Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
Definitions
- the present invention relates to an approximate calculation method of the exponential average of a series of numbers coded in the floating-point format used to convey certain bit rate information in packet data transmission networks known by the English abbreviation. "Asynchronous transfer mode" ATM.
- ATM networks provide several categories of data transmission service, including one known by the abbreviation ABR "available bit rate”. This latter service allows the user to use the bandwidth available on the route of a previously established connection without requiring him to make a static reservation of resources when establishing the connection. In return for this flexibility, the two ends of the connection must adapt their speed to the available bandwidth.
- specific ATM cells called RM cells, where RM is the English abbreviation for “resource management”, make it possible to inform the ends of a connection about the availability of resources in the network. and processed in real time by the end devices attached to the network, as well as by the ATM switches which form the nodes of the network, include fields intended to convey bit rate information.
- These fields represent for example, the current authorized bit rate from the source - which is known by the abbreviation Anglo-Saxon CCR “current cell rate” -, or the speed advised by the network at the source - which is known by the Anglo-Saxon abbreviation from ER “explicit cell rate”
- These fields are the subject of a particular floating point coding characterized by a nullity bit, 5 exponent bits and 9 mantissa bits.
- Switches which have this capacity calculate the ER rate and enter it in the RM cells
- a family of algorithms implements a calculation of the "exponential average" of the CCR rates conveyed by the RM cells
- the "exponential average” n is nothing other than the result of a linear filtering obtained at the output of a digital filter of the first order with discrete time.
- the sequence x thus represents a kind of instantaneous more or less long term average of the values entered u n .
- the calculation of the "exponential average” is an operation which must be done very quickly, typically during the switching time of an ATM packet (cell). For example, for a 155 Mbit / s network route, the switching time of a cell in a switch connected to this route is approximately 2.8 microseconds. Given the encoding of the up data in floating format and the relative complexity of processing these two multiplications followed by an addition, it is almost essential to use a microprocessor endowed with the capacity to perform arithmetic operations in this type of floating point coding. However, these processors are not very cheap at the moment.
- the invention also relates to a device for implementing the method.
- the main advantage of the method and the device according to the invention is that they make it possible to quickly obtain an approximate value of the exponential average by direct manipulation of the code words, in whole arithmetic and without passing through the fixed-point format, this which puts computation within the reach of current microprocessors.
- the method according to the invention consists in replacing in the relation (1) which defines the equation of a first order filter, the sequence of input values u ⁇ with the sequence of code words U n .
- the values obtained for X n are then code words associated with values very close to the exponential average and are then perfectly suitable for the calculation of the ER flow rates. This simplification eliminates the need to decode code words.
- Xn + 1 ((Xp “4) -X n + U n )” 4 (5) where the signs “and” designate operators in left or right binary shift as in C language. Comparable results can also be obtained with other remarkable values of a, such as for example (2 r - 2 s ) / 2 r -
- FIG. 1 A corresponding device for implementing the method according to the invention is shown in FIG. 1.
- an addition operator 1 receiving on a first operand input the code words U ⁇ and on a second operand input the output of a subtractor operator 2.
- It also includes a first shift operator 3 which is coupled to the output of the adder operator 1 to supply the sequence of code words X n .
- the output of the first shift operator 3 is coupled to a first operand input marked "+" of the subtractor operator 2 via a second shift operator 4 and a delay circuit 5 connected in series .
- a fourth shift operator 6 ensures the transmission of the code words U n on the first operand input of the addition operator 1.
- the second operand input marked "-" of the subtractor operator 2 is coupled to the output of the delay circuit 5 via a third shift operator.
- the first shift operator 3 shifts r bits to the right
- the second shift operator 4 shifts r bits to the left
- the third operator 6 and the fourth shift operator 7 perform an offset of s bits to the left.
- FIG. 2b A comparison of the results obtained by the approximate calculation method of an exponential average according to the invention with the non-approximate calculation method is represented in FIG. 2b, for a series of the values of the code u n represented in FIG. 2a and obtained by superimposing a low frequency harmonic oscillation, a higher frequency harmonic oscillation and a random component.
- x n represents the exact exponential mean obtained
- F (X n ) is the approximate exponential mean obtained by applying the relation (5), F being the function which associates a value of the code with a code word.
- FIG. 2c shows the differences between the two curves of FIG. 2b by giving a representation of the relative error which is made by replacing x n by F (X n j. It should be noted that this error is higher for the low values of x n .
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
Description
Claims
Priority Applications (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
EP97933718A EP0910926A1 (fr) | 1996-07-12 | 1997-07-11 | Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante |
US09/147,512 US6144978A (en) | 1996-07-12 | 1997-07-11 | Method and device for the approximative computation of the exponential mean of a sequence of coded numbers in floating point format |
Applications Claiming Priority (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
FR96/08735 | 1996-07-12 | ||
FR9608735A FR2751105B1 (fr) | 1996-07-12 | 1996-07-12 | Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante |
Publications (1)
Publication Number | Publication Date |
---|---|
WO1998003034A1 true WO1998003034A1 (fr) | 1998-01-22 |
Family
ID=9493990
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
PCT/FR1997/001286 WO1998003034A1 (fr) | 1996-07-12 | 1997-07-11 | Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante |
Country Status (5)
Country | Link |
---|---|
US (1) | US6144978A (fr) |
EP (1) | EP0910926A1 (fr) |
CA (1) | CA2260084A1 (fr) |
FR (1) | FR2751105B1 (fr) |
WO (1) | WO1998003034A1 (fr) |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US6741565B1 (en) | 2000-07-06 | 2004-05-25 | Telefonaktiebolaget Lm Ericsson (Publ) | System and method for estimating cell rate in an ATM network |
Families Citing this family (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
FR2751160B1 (fr) | 1996-07-12 | 1998-10-30 | Thomson Csf | Procede de detection de congestion amont au sein d'un commutateur atm a architecture repartie et memorisation en entree |
FR2751108B1 (fr) * | 1996-07-12 | 1998-10-30 | Thomson Csf | Procede et dispositif de mesure de la proportion de cellules atm satisfaisant a un critere determine en un point quelconque d'un flot de cellules atm |
FR2770070B1 (fr) | 1997-10-20 | 2000-02-04 | Thomson Csf | Procede de controle de flux au sein d'un commutateur atm a architecture repartie |
FR2811179B1 (fr) * | 2000-06-30 | 2002-09-27 | Thomson Csf | Procede de routage de trame ip entre les usagers d'un reseau a graphe variable |
Citations (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US4774685A (en) * | 1985-01-31 | 1988-09-27 | Analog Devices, Inc. | Approximation system |
US4815354A (en) * | 1984-10-30 | 1989-03-28 | Nippon Gakki Seizo Kabushiki Kaisha | Tone signal generating apparatus having a low-pass filter for interpolating waveforms |
US5258938A (en) * | 1990-11-30 | 1993-11-02 | Norio Akamatsu | Interpolating method using bit-shift and addition/subtraction operations |
Family Cites Families (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US3619586A (en) * | 1968-11-25 | 1971-11-09 | Research Corp | Universal digital filter for linear discrete systems |
US5824936A (en) * | 1997-01-17 | 1998-10-20 | Crystal Semiconductor Corporation | Apparatus and method for approximating an exponential decay in a sound synthesizer |
-
1996
- 1996-07-12 FR FR9608735A patent/FR2751105B1/fr not_active Expired - Fee Related
-
1997
- 1997-07-11 EP EP97933718A patent/EP0910926A1/fr not_active Withdrawn
- 1997-07-11 US US09/147,512 patent/US6144978A/en not_active Expired - Lifetime
- 1997-07-11 CA CA002260084A patent/CA2260084A1/fr not_active Abandoned
- 1997-07-11 WO PCT/FR1997/001286 patent/WO1998003034A1/fr not_active Application Discontinuation
Patent Citations (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US4815354A (en) * | 1984-10-30 | 1989-03-28 | Nippon Gakki Seizo Kabushiki Kaisha | Tone signal generating apparatus having a low-pass filter for interpolating waveforms |
US4774685A (en) * | 1985-01-31 | 1988-09-27 | Analog Devices, Inc. | Approximation system |
US5258938A (en) * | 1990-11-30 | 1993-11-02 | Norio Akamatsu | Interpolating method using bit-shift and addition/subtraction operations |
Non-Patent Citations (2)
Title |
---|
KAI-YEUNG SIU ET AL: "INTELLIGENT CONGESTION CONTROL FOR ABR SERVICE IN ATM NETWORKS", COMPUTER COMMUNICATIONS REVIEW, vol. 24, no. 5, 1 October 1994 (1994-10-01), pages 81 - 106, XP000501061 * |
PRYCKER, MARTIN DE: "Asynchronous transfer mode : solution for broadband ISDN", 1995, PRENTICE HALL INTERNALIONAL (UK) LIMITED, GREAT BRITAIN, XP002028512 * |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US6741565B1 (en) | 2000-07-06 | 2004-05-25 | Telefonaktiebolaget Lm Ericsson (Publ) | System and method for estimating cell rate in an ATM network |
Also Published As
Publication number | Publication date |
---|---|
FR2751105A1 (fr) | 1998-01-16 |
US6144978A (en) | 2000-11-07 |
CA2260084A1 (fr) | 1998-01-22 |
EP0910926A1 (fr) | 1999-04-28 |
FR2751105B1 (fr) | 1998-12-18 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
EP0493286B1 (fr) | Système de transmission par paquets à compression de données, procédé et équipement correspondant | |
EP0321318B1 (fr) | Procédé et dispositif de codage et de décodage pour la transmission d'images à travers un réseau à débit variable | |
US6678709B1 (en) | Digital filter with efficient quantization circuitry | |
EP0318538A1 (fr) | Procede de demodulation utilise dans des systemes de transmission numeriques avec propagation a passages multiples | |
EP0081437B1 (fr) | Systéme annuleur d'écho | |
FR2880482A1 (fr) | Dispositif de conversion d'un signal transmis en un signal numerique | |
EP0796031A2 (fr) | Interfonctionnement de large bande/étroite bande | |
WO1998003034A1 (fr) | Procede et dispositif de calcul approche de la moyenne exponentielle d'une suite de nombres codes dans le format a virgule flottante | |
US6256323B1 (en) | Method and apparatus for efficiently transporting asynchronous characters over an ATM network | |
EP0020220A1 (fr) | Dispositif de décodage binaire et système de transmission comportant un tel dispositif | |
EP1445882B1 (fr) | Trame de transmission de données, et procédé et dispositif d'émission et de réception d'une telle trame | |
EP0869476B1 (fr) | Dispositif de génération de bruit de confort | |
WO1999050739A1 (fr) | Procede et appareil de mise en oeuvre d'une technique de division de mots courts dans un contexte de conversion a modules multiples | |
EP0723355A1 (fr) | Système de transmission à compression de données | |
EP0030194B1 (fr) | Etage prédicteur pour système de compression de débit numérique | |
Boucheret et al. | A new algorithm for nonlinear estimation of PSK-modulated carrier phase | |
EP0910911B1 (fr) | Procede et dispositif de mesure de la proportion d'un flot de cellules atm satisfaisant a un critere determine | |
FR2747489A1 (fr) | Procede et dispositif pour le calcul approche dans des reseaux atm du produit de mots de code d'information codes dans un format a virgule flottante | |
EP0011014B1 (fr) | Dispositif de mesure de la qualité d'une liaison numérique et équipements de transmission comportant un tel dispositif | |
FR2811169A1 (fr) | Procede et dispositif de decodage et systemes les mettant en oeuvre | |
EP0288353A1 (fr) | Procédé de commutation de signaux numériques asynchrones, et dispositif pour la mise en oeuvre de ce procédé | |
EP0444993B1 (fr) | Dispositif de quantification à débit de codage numérique variable | |
EP0589768A1 (fr) | Dispositif de filtrage pour égaliseur à estimation de séquence | |
WO1995003673A1 (fr) | Procede et dispositif d'estimation d'un budget de bits pour encodeurs a longueur de mot variable | |
Sunwoo et al. | Performance analysis of FIR ADM digital filters |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
AK | Designated states |
Kind code of ref document: A1 Designated state(s): CA IL JP US |
|
AL | Designated countries for regional patents |
Kind code of ref document: A1 Designated state(s): AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE |
|
DFPE | Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101) | ||
121 | Ep: the epo has been informed by wipo that ep was designated in this application | ||
WWE | Wipo information: entry into national phase |
Ref document number: 1997933718 Country of ref document: EP |
|
ENP | Entry into the national phase |
Ref document number: 2260084 Country of ref document: CA Ref country code: CA Ref document number: 2260084 Kind code of ref document: A Format of ref document f/p: F |
|
WWE | Wipo information: entry into national phase |
Ref document number: 09147512 Country of ref document: US |
|
WWP | Wipo information: published in national office |
Ref document number: 1997933718 Country of ref document: EP |
|
NENP | Non-entry into the national phase |
Ref country code: JP Ref document number: 1998505679 Format of ref document f/p: F |
|
WWW | Wipo information: withdrawn in national office |
Ref document number: 1997933718 Country of ref document: EP |