Method and apparatus for managing the statistical multiplexing of data in digital communication networks

• US 5,689,499 A
• Filed: 08/04/1995
• Issued: 11/18/1997
• Est. Priority Date: 03/26/1993
• Status: Expired due to Term

• Current Assignee: QPSX Developments 5 PTY Limited
• Original Assignee: Curtin University of Technology
• Inventors: Budrikis, Zigmantas Leonas, Cantoni, Antonio, Hullett, John Leslie
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US08/500,844
• Time in Patent Office: 837 Days
• Field of Search: 370/17, 370/60, 370/60.1, 370/94.1, 370/94.2, 370/108, 370/229, 370/230, 370/235, 370/236, 370/395, 370/397, 370/399
• US Class Current: 370/235
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5648 Packet discarding, e.g. EPD, PTD
• CPC Class Codes: H04L 2012/5662 Macrocells or frames
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/1553 Interconnection of ATM switching modules, e.g. ATM switching fabrics
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/501 Overload detection
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An apparatus and method are provided for supporting a plurality of virtual channel (VC) connections within a single virtual path (VP) in a digital communications network operating in the Asynchronous Transfer Mode (ATM). The apparatus (56) is combined with the cross-connected part of a conventional VC switch (54) to form a Data Switch (40). A VP switch (42) switches and terminates incoming bandwidth-resourced VPs on lines (48), some of which are carrying non-bandwidth-resourced VCs and switched onto lines 50 on the output side of VP switch 42. VPs on lines (50) are switched and multiplexed by the Data Switch (40). Buffers (66) store cells and a VP rate server. The buffers (66) are significantly larger than in a conventional VC switch to enable smoothing of data flow peaks associated with data flowing from multiple bandwidth resourced VP tributaries into single resourced VP tributaries. Despite the large buffers in the Data Switch (40) congestion may result when data bursts occur on several converging streams. When buffer overflow is threatened, Data Switch (40) discards whole frames, i.e., whole VPI-VCI sequences marked with an end of transmission delimiter in the PTI, rather than individual cells originating from different frames as with normal ATM cell multiplexing.

Claims

1. A method for supporting a plurality of virtual channel connections within a single virtual path in a digital communications network operating in the Asynchronous Transfer Mode (ATM), where said virtual channel connections have no guarantees of rate at which cells on that connection can be transmitted, but also have no constraint on said rate save that inherent on said virtual path connection, said method comprising the steps of:

storing cells arriving for transmission on said virtual path in a buffer for transmission of cells on said virtual path in conformance with said constraint on said rate;

detecting whether buffer overflow is threatened by the storage of further cells arriving for transmission on said virtual path; and

,

while buffer overflow is threatened, admitting for storage in said buffer cells only on such of said virtual channel connections on which the previous cell admitted was not indicated by the header of said previous cell as being end of transmission on said virtual channel; and

,

at all times not admit for storage in said buffer any cells on said virtual channel connections for which since the previous indication of said end of transmission on said virtual channel connection there has been any rejection of cells for storage.

2. A method according to claim 1, wherein the detection of threatened buffer overload is made on the assessment of the number of unoccupied locations in said buffer at the time of arrival of a cell for said transmission.

3. A method according to claim 2, wherein buffer overload is deemed to be threatened when the number of unoccupied locations in said buffer at the time of arrival of a cell for said transmission is less than a threshold level.

4. A method according to claim 3, wherein said threshold level dynamically varies dependent on the rate of cells incoming for said transmission and the rate of reading cells out of said buffer.

5. A method for supporting a plurality of virtual paths on a single physical cell transmission system in a digital communications network operating in the Asynchronous Transfer Mode (ATM), each virtual path supporting a plurality of virtual channel connections, where each said virtual path has an individual rate constraint, the method comprising steps of:

storing cells arriving for transmission on any one of said virtual paths in a common buffer for transmission on said physical cell transmission system;

scheduling the stored cells for transmission on said physical cell transmission system at time instants that conform with said individual rate constraints on said virtual paths, and preserving the order of transmission cells on a said virtual path to the order of arrival for said path;

detecting whether buffer overflow is threatened by the storage of further cells for transmission on any of said virtual paths, and detecting whether said scheduling on a particular virtual path is over a specified limit; and

for any cell arriving for transmission on a given virtual path,

while buffer overflow is threatened or the scheduling for said virtual path is over the specified limit, admitting for storage in said buffer and scheduling for transmission cells only on such of said virtual channel connections on which the previous cell admitted was not indicated by a header of said previous cell as being an end of transmission on said virtual channel; and

,

at all times not admit for storage in said buffer any cells on said virtual channel connections for which since the previous indication of said end of transmission on said virtual channel connection there has been any rejection of cells for storage.

6. A method according to claim 5, wherein the detection of scheduling on a virtual path being over the limit is made on the assessment of time delay on said virtual path.

7. A method according to claim 6, wherein scheduling on a virtual path is deemed as over the limit if at the time of arrival of a cell the last scheduled cell on said virtual path is for a time later than said arrival time plus a fixed threshold level.

8. A method according claim 5, further comprising the step of forming an admit list (AL) and a reject list (RL) on the basis of cells arriving for transmission for determining on which virtual channel connections cells are to be admitted or rejected for storage in said buffer, said lists being formed by reading the identifier information and end transmission information in the header of a cell, and said AL and RL carrying entries of said identifier information however applicable, and in the event of a cell arriving for transmission and not marked a end of transmission, then if said identifier information of said cell matches that on said RL, the cell is rejected;

if it does not match any on said RL and if it does match on said AL, the cell is admitted;

if it matches neither said RL nor AL and if buffer overflow is threatened or the scheduling for said virtual path is over the limit, the cell is rejected and entered on said RL, and otherwise the cell is admitted and entered on said AL; and

in the event a cell arrives with end of transmission indicated, then if said identifier matches said RL then the cell is rejected and its identifier is cleared from said RL, and if its identifier does not match said RL and matches said AL, the cell is admitted and its identifier cleared from the said AL; and

if the identifier does not match either said RL or said AL, the cell is admitted or rejected depending on the state of buffer and scheduling of the virtual path without being entered in either said RL or said AL.

9. A method according to claim 8, wherein said identifier information consists of a Virtual Path Identifier and Virtual Channel Identifier and said end of transmission information is a unique code point of a Payload Type Identifier of a cell.

10. A method according to claim 5, wherein said constraint on said virtual path connection is in terms of specified shortest allowed time interval between successive cells on said virtual path.

11. An apparatus for supporting a plurality of virtual channel connections within a single virtual path in a digital communications network operating in the Asynchronous Transfer Mode (ATM), where said virtual channel connections have no guarantees of rate of which cells on that connection can be transmitted, but also have no constraint on said rate save that inherent on said virtual path connection, where said constraint on said virtual path connection is in terms of a specified shortest allowed time interval between successive cells on said virtual path, said apparatus comprising:

means for storing cells arriving for transmission on said virtual path in a buffer for transmission of cells on said virtual path in conformance with said constraint on said rate;

means for detecting whether buffer overflow is threatened by the storage of further cells arriving for transmission on said virtual path; and

,

means for admitting for storage in said buffer while buffer overflow is threatened cells only on such of said virtual channel connections on which the previous cell admitted was not indicated by the header of said previous cell as being the end of transmission on said virtual channel, and wherein said admitting means at all times does not admit for storage in said buffer any cells on said virtual channel connections for which since the previous indication of said end of transmission on said virtual channel connection there has been any rejection of cells for storage.

12. An apparatus according to claim 11, wherein the detection of threatened buffer overload is made on the assessment of the number of unoccupied locations in said buffer at the time of arrival of a cell for said transmission.

13. An apparatus according to claim 12, wherein buffer overload is deemed to be threatened when the number of unoccupied locations in said buffer at the time of arrival of a cell for said transmission is less than a threshold level.

14. An apparatus according to claim 13, wherein said threshold level dynamically varied dependent on the rate of cells incoming for said transmission and the rate of reading cells out of said buffer.

15. An apparatus for supporting a plurality of virtual paths on a single physical cell transmission system in a digital communications network operating in the Asynchronous Transfer Mode (ATM), each virtual path supporting a plurality of virtual channel connections, wherein each virtual path has an individual rate constraint said apparatus comprising:

means for storing cells arriving for transmission on any one of said virtual paths in common buffer for transmission on said physical cell transmission system;

means for scheduling the stored cells for transmission on said physical cell transmission system at time instants that conform with said individual rate constraints on said virtual paths, and preserving the order of transmission of cells on a said virtual path to the order of arrival for said path;

means for detecting whether buffer overflow is threatened by the storage of further cells for transmission on any said virtual paths, and detecting whether said scheduling on a particular virtual path is over a specified limit; and

,

means for admitting for storage in said buffer and scheduling for transmission while buffer overflow is threatened or the scheduling for said virtual path is over the specified limit, cells only on such of said virtual channel connections on which the previous cell admitted was not indicated by a header of said previous cell as being an end of transmission on said virtual channel, and wherein said admitting means at all times does not admit for storage in said buffer any cells on said virtual channel connections for which since the previous indication of said end of transmission on said virtual channel connection there has been any rejection of cells for storage.

16. An apparatus according to claim 15, wherein the detection of scheduling on a virtual path being over the limit is made on the assessment of time delay on said virtual path.

17. An apparatus according to claim 15, wherein scheduling by said scheduling means on a virtual path is deemed as over the limit if at the time of arrival of a cell the last scheduled cell on said virtual path is for a time, later than said arrival time plus a fixed threshold level.

18. An apparatus according to claim 15, further comprising means for forming an admit list (AL) and a reject list (RL) on the basis of cells arriving for transmission for determining on which virtual channel connections cells are to be admitted or rejected for storage in said buffer, said lists being formed by reading the identifier information and end of transmission information in a cell, and said AL and RL carrying entries of said identifier information, and in the event of a cell arriving for transmission and not marked as end of transmission, then if said identifier information of said cell matches that on said RL, the cell is rejected;

if it does not match any on said RL and if it does match on said AL, the cell is admitted;

if it matches neither said RL nor said AL and if buffer overflow is threatened or the scheduling for said virtual path is over the limit, said cell is rejected and entered on said RL, and otherwise said cell is admitted and entered on said AL; and

in the event a cell arrives with end of transmission indicated, then if said identifier matches said RL then said cell is rejected and its identifier is cleared from said RL, and if its identifier does not match said RL and matches said AL, said cell is admitted and its identifier cleared from said AL; and

if the identifier does not match either said RL or said AL, the cell is admitted or rejected depending on the state of buffer and scheduling of the virtual path without being entered in either said RL or said AL.

19. An apparatus according to claim 18, wherein said identifier information consisting of Virtual Path Identifier and Virtual Channel Identifier and said end of transmission information being unique code point of Payload Type Identifier of a cell.