US5173897A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of restoring the correct cell sequence, particularly in an atm exchange, and output unit therefor
Assignee: Alcatel Lucent NV
•
Filing: 1990-12-19
•
Granted: 1992-12-22
•
Expires: 2010-12-19
Abstract
Abstract To be able to load an ATM switching network as efficiently as possible, the successive cells of one and the same connection are routed to the output by as many different paths as possible; however, mutual overtaking of successive cells must be avoided or corrected. Each cell is held at the output until it is certain that no older cell can be buffered in the switching network. Before the cell is passed on, a check is made to determine whether the cells received from the switching network later include an older cell which must be passed on before that cell. At the input end, consecutive numbers ("Sequence Numbers") are allocated to the cells. A buffer (1) at the output end is operated, at least in part (1 . . . d), in the manner of a shift register, thereby introducing a predetermined delay. Prior to the output of a cell, at least the shift-register-like portion of the buffer is examined as to whether a cell written in later is to be put out earlier: if so, the two cells are interchanged.
Inventors
- 👤 Karl Schrodi
- 👤 Gert Eilenberger
- 👤 Stefan Wahl
- 👤 Bodo Pfeiffer
- 👤 Bozo Cesar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 09:56
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/30; H04L49/3027; H04L2012/5638; H04L2012/5646; H04L2012/565; H04L2012/5678; H04L2012/5681
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
188 words
Method of restoring the correct sequence of data packets or cells in a packet switching system, wherein, during transmission from an input unit to an output unit, related cells belonging to a single data stream from a specified input unit to a specified output unit of the switching system may overtake each other, said method comprising the steps of: prior to transmission form the input unit, adding a respective sequence label to each of the cells to identify the original transmission order of the cells; upon reception at the output unit, buffering each cell in an output buffer; waiting for at least a predetermined minimum delay time to elapse following the reception of a candidate cell still contained in the buffer; comparing the sequence label of said candidate cell with the corresponding sequence labels of other cells in said output buffer; outputting said candidate cell if the comparison indicated that the candidate cell was originally transmitted before the other cells in the output buffer; and instead of the candidate cell, outputting another cell if the comparison indicated that the other cell was originally transmitted before the candidate cell.
Claim 2
Dependent Claim
188 words
Method of restoring the correct sequence of data packets or cells in a packet switching system, wherein, during transmission from an input unit to an output unit, related cells belonging to a single data stream from a specified input unit to a specified output unit of the switching system may overtake each other, said method comprising the steps of: prior to transmission form the input unit, adding a respective sequence label to each of the cells to identify the original transmission order of the cells; upon reception at the output unit, buffering each cell in an output buffer; waiting for at least a predetermined minimum delay time to elapse following the reception of a candidate cell still contained in the buffer; comparing the sequence label of said candidate cell with the corresponding sequence labels of other cells in said output buffer; outputting said candidate cell if the comparison indicated that the candidate cell was originally transmitted before the other cells in the output buffer; and instead of the candidate cell, outputting another cell if the comparison indicated that the other cell was originally transmitted before the candidate cell.
Claim 3
Dependent Claim
30 words
A method as claimed in claim 1, wherein prior to the output of said other cell, said candidate cell takes the place of the other cell in said output buffer.
Claim 4
Dependent Claim
41 words
A method as claimed in claim 1, wherein numbers formed by counting modulo N are used as the sequence labels, and N is sufficiently large that less than N/2 numbers can be allocated as sequence labels within said predetermined delay time.
Claim 5
Dependent Claim
25 words
A method as claimed in claim 3, wherein for each said connection, the sequence labels are allocated separately to the cells of said each connection.
Claim 6
Dependent Claim
30 words
A method as claimed in claim 3, wherein for all connections routed via one said input unit, the sequence labels are allocated jointly to the cells of said all connections.
Claim 7
Dependent Claim
56 words
A method as claimed in claim 1, wherein a connection label is added to each cell to identify the connection to which the cell belongs, and said other cell is output instead of the candidate cell if and only if the respective connection labels are the same for both said other cell and said candidate cell.
Claim 8
Dependent Claim
33 words
A method as claimed in claim 1, wherein said predetermined minimum delay is realized by operating at least a portion of the buffer as a shift register, thus introducing the predetermined minimum delay.
Claim 9
Dependent Claim
60 words
A method as claimed in claim 1, wherein the predetermined minimum delay is such that if a second cell is transmitted from said input unit more than said predetermined minimum delay after a first cell, the probability that the second cell will be received before the first cell at said output unit is less than a predetermined permissible error probability.
Claim 10
Dependent Claim
123 words
Output unit for restoring the correct sequence of cells at the output of a packet switching system by means of respective sequence labels associated with each of said cells, said output unit comprising: a buffer for buffering cells to be put out; an access means for obtaining access to any cell contained in the buffer; timing means, associated with the access means, for determining the residence time of at least one cell in the buffer; and comparing means for comparing, following a predetermined minimum said residence time of said at least one cell, the respective sequence labels of said at least one cell and any other cell accessed by the access device to thereby determine the order the two cells entered said system.
Claim 11
Dependent Claim
123 words
Output unit for restoring the correct sequence of cells at the output of a packet switching system by means of respective sequence labels associated with each of said cells, said output unit comprising: a buffer for buffering cells to be put out; an access means for obtaining access to any cell contained in the buffer; timing means, associated with the access means, for determining the residence time of at least one cell in the buffer; and comparing means for comparing, following a predetermined minimum said residence time of said at least one cell, the respective sequence labels of said at least one cell and any other cell accessed by the access device to thereby determine the order the two cells entered said system.
Claim 12
Dependent Claim
31 words
An output unit as claimed in claim 9, further comprising interchange is provided by means for selectively replacing one of the two compared cells with the other of said two cells.
Claim 13
Dependent Claim
17 words
The method of claim 1, wherein said packet switching system in an asynchronous transfer mode switching system.
Claim 14
Dependent Claim
18 words
The output unit of claim 9, wherein said packet switching system in an asynchronous transfer mode switching system.
References Cited (Backward Citations)
US4317196A
Cited
JPS55140347A
Cited
US4761781A
Cited
EP0215526A2
Cited
US4894823A
Cited
US5022025A
Cited
EP0333226A2
Cited
EP0336401A2
Cited
US4947388A
Cited
US4956839A
Cited
US4995032A
Cited
US4899335A
Cited
US4937817A
Cited
EP1192298A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-12-22 | 1996-06-22 | 1996-12-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-12-22 | 2000-06-22 | 2000-12-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-12-22 | 2004-06-22 | 2004-12-22 | $7700.00 | Window Closed / Lapsed |