EP0702473A1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method and an apparatus for shaping the output traffic in a fixed length cell switching network node
Assignee: International Business Machines Corp
•
Filing: 1994-09-19
•
Granted: —
•
Expires: 2014-09-19
Abstract
Abstract An method and an apparatus implementing a shaping function in a fixed length cell switching network node (5) adapter supporting output lines (25); the invention uses a Time Division Multiplexing (TDM) table (270) where each entry is a pointer to a the first cell of a queue (240) of cells of a given traffic; When a new traffic is established, the TDM table is updated; placement device (250) performs the pre-computation of the best placement of the entries reserved for one traffic in the TDM table (270) minimizing the Cell Delay Variation as computed by the GCRA policer (ITU standard organization). The Cell Delay Variation (CDV) defined as the deviation of the placement of the cells in the output stream from their ideal position which is when the entries are spaced with an interval corresponding to the period of traffic negociated at traffic establishment time. The preferred embodiments includes a scheduler (280) able to read the TDM table and to fetch the corresponding cell in the storage (230) to send it onto the output line via the line interface adapter.
Inventors
- 👤 Aline Fichou
- 👤 Claude Galand
- 👤 Pierre-André Foriel
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-03 15:11
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/50; H04L49/505; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L49/501; H04L49/503; H04L2012/5614; H04L2012/5615; H04L2012/5616; H04L2012/5619; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5636; H04L2012/5638; H04L2012/5646; H04L2012/5649; H04L2012/5678; H04L2012/5679; H04L2012/568; H04L49/30
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
316 words
A method for shaping the output traffic in the transmit part (20) of a fixed length cell switching network node (5) supporting a transfer of traffic between a source unit and a destination unit; said source unit sending to the network node a parameter, R, qualifying the traffic rate to be supported by the network; said transmit part of the network node including a memory wherein queues of cells are assigned to each transfer of traffic; said method being characterized in that it provides a Time Division Multiplexing (TDM) table of N entries, each entry representing the position of one cell in the output cell stream which will be sent onto one output line of the network node; said method consisting in updating and reading the TDM table and comprising the following steps: 1- at each new traffic accepted by the network node, computing the period T of said traffic and the number S of positions to be reserved for said traffic in the TDM table; T being the period corresponding to the ideal traffic flow required; 2- for each possible placement in the TDM table of the entries corresponding to said traffic, computing an estimation of the Cell Delay Variation defined as the deviation of the placement of the cells in the output stream from their ideal position which is when the entries are spaced with an interval of T; and storing the placement corresponding to the smallest CDV; 3- according to the placement stored, writing in the TDM table, for each entry corresponding to said traffic, a pointer pointing to the first cell of the queue of cells stacked in the memory for said traffic; 4- reading the TDM table and for each entry dequeueing the 'first in' cell from said queue and send it onto the output line; once the last entry in the TDM table is read, restart from the first one.
Claim 2
Dependent Claim
215 words
The method of claim 1 where the step 2 for the computation of the placement in the TDM table of the entries for said traffic is characterized in that it comprises the following steps: A- for each possible placement to be reserved in the TDM table, said placement being characterized by the first entry, n, reserved among N entries, computing the number of collisons, y(n) between the entries already reserved in the TDM table for the other traffics and the entries which should be reserved for said traffic according to the ideal placement; said number of collisons, y(n), being a rough approximation of the CDV; y(n) being computed as follows: x(n),(0≦n≦N), being a binary sequence representing the TDM table with the following convention: x(n)= 1 if the entry is already assigned to another traffic = 0 if the entry is not assigned to another traffic s(n)(0≦n≦N), being a binary sequence of the positions of the entries of said traffic ideally spaced in a time window of length N, according to the peak rate R with the following convention: s(n)= 1 if n = [kTi] (k=0, ...Si-1) = 0 otherwise; where A + B N denotes the sum of A and B modulo N operator. B- storing the placement corresponding to the smallest number of collisions.
Claim 3
Dependent Claim
105 words
The method of claim 1 or 2 where in the step 2 the computation of the placement in the TDM table of the entries for said traffic characterized by the following steps: A- for each possible placement to be reserved in the TDM table for said traffic, computing the number of collisions y(n) and a function w(n) characterizing the Cell Delay Variation induced by the moving of entries reserved for said traffic from their ideal position; B- storing the placement corresponding to the smallest CDV tolerance and if more than one placement have the same CDV, store the placement having the smallest number of collisions.
Claim 4
Independent Claim
37 words
The method of any claim from 1 to 3 characterized in that, in step 2, if the number of collisions is zero, the corresponding placement is the one to be stored, the anlysis of placements is stopped.
Claim 5
Independent Claim
54 words
The method of any claim from 1 to 4 characterized in that each time the CDV is computed for one placement, the placement is stored in a placement table with S entries and once the placement with the minimum CDV is identified, the placement is read in the placement table and no more recomputed.
Claim 6
Independent Claim
43 words
The method of any claim from 1 to 5 characterized in that the network node is a connection oriented ATM network node and the traffic established between a source unit and a destination unit is a Virtual Connection or a Virtual Path connection.
Claim 7
Dependent Claim
246 words
The method of claim 6 where the function used in step 2 as an estimation of the CDV is an estimation of the CDV tolerance as defined for the GCRA policing algorithm proposed as a standard by the ITU (International Telecommunications Union) described in details in the ATM Forum, "ATM User-Network Interface Specification", Version 3.0, 1994.: it is estimated as the minimal value of the sum of the maximum move to left plus the maximum move to Right of the entries when moved because of collisions from their ideal positions: n being the first entry for the placement of the S entries of the connection, n being an integer chosen at random between 0 and N, the other ideal positions of the cells being w Left max being the maximal advance, for the final placement having n as the first entry, if compared to the ideal placement n(k) (k=0, ...S-1); w Right max being the maximal delay, for the final placement having n as the first entry, if compared to the ideal placement n(k) (k=0, ...S-1); the integers u and v being the number of entries of the moving: expression 1 and expression 2 being computed until the two first non-assigned entries are found. w Left max = max {wk Left } if wk Right > wk Left > 0 w Right max = max {wk Right} if wk Left ≧ wk Right > 0 In fine: w(n) = w Right max + w Left max
Claim 8
Dependent Claim
83 words
The method of claim 6 or 7, characterized in that in step 1, for one given connection, C being the speed of said output line, the number of cells S to be placed are computed in step 1- as follows: where X denotes the nearest integer greater than, or equal to X; the period T = N/S is computed using floating point operations and [kT], used for the computation of the number of collisions, y(n), is also computed using the floating point operations.
Claim 9
Dependent Claim
93 words
The method of claim 6 or 7, characterized in that for one given connection the period T and the number of cells S to be placed are computed as follows: the placement method of step 2 is run twice for each connection , with , for each computation, a number of slots S(k), k=1,2 and an associated period T(k), k=1,2 such that: S = S(1) + S(2) with and where X denotes the nearest integer greater than, or equal to X and X denotes the nearest integer less than, or equal to X;
Claim 10
Dependent Claim
41 words
The method of claim 6 or 7, characterized in that for one given connection, C being the speed of said output line, the period T and the number of cells S to be placed are computed in step 1- as follows:
Claim 11
Dependent Claim
80 words
The method of claim 2, 3, 4, 5, 6, or 7 characterized in that: the S iterations of step 2 may be stopped before completion if w is found greater than a w min previously found and thus, the previous value of n0* is kept; at the end of step 2, at each iteration an added step being: if the CDV tolerance computed is larger than the minimum CDV tolerance found for a previous position, stopping the current position computation.
Claim 12
Dependent Claim
24 words
The method of claim 1 to 11, where the parameter R qualifying the traffic rate and provided by the source is the peak rate.
Claim 13
Dependent Claim
31 words
The method of claim 6, 7, 8, 9, 10 or 11, where the parameter R qualifying the traffic rate and sent by the source unit is the Sustainable Cell Rate (SCR).
Claim 14
Independent Claim
30 words
The method of any claim from 1 to 13 where the number of placements tested in step 2 is limited to any integer between 2 and N instead of N.
Claim 15
Independent Claim
355 words
An apparatus implementing a shaping function in a fixed length cell switching network node (5) adapter supporting output lines (25); said apparatus comprising: - first means for storing (230) queues (240) of cells, one per output connection; - second means for storing (245) in each entry, an output connection identifier, the connection period T and a number of cells S; - means for computing with the information read in the connection establishment messages the period T and said number of cells S associated to a given output connection; writing in each entry of said second storing means (245), the output connection identifier, said period T and said number of cells S; - third means for storing (270) in each entry a connection identifier; - means (250) for continuously reading an entry in said second storing means (245) including a connection identifier i, the parameters T and S and computing the placement of the S cells in the third storing means (270) as follows: for each possible placement in the third storing means (270), of the S entries for a given connection, computing an estimation of the Cell Delay Variation (CDV) defined as the deviation of the placement of the cells in the output stream from their ideal position which is when the entries are spaced with an interval of the connection period T; in each of the S entries of said third storing means (270) according to the placement having the smallest CDV, writing the connection identifier i; - means for scheduling (280) the departure of cells by reading, in sequence, when a request for cell is received on the link means (282), the current entry of the third storing means (270) containing a connection identifier and reading in said second storing means (230), the first cell of the queue (240) corresponding to the connection identifier; - means for interfacing (290) the adapter with one output lines (25); said means receiving one cell on a first link means (283) and sending it onto the output link means and then, sending a request for cell to the scheduling means (280), via a second link means 282.
Claim 16
Dependent Claim
69 words
The apparatus of claim 15 characterized in that the means (250) comprises for computing the placement of the S cells in the third storing means (270): - floating point processing means (260) sending via the link means (262) the integer the nearest to kT (k=0, ...S-1), T being the period of one connection, when receiving, via the same link means (262), the parameter kT sent by said means (250).
References Cited (Backward Citations)
FR2694671A1
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.