ATM adaption layer traffic scheduling

• US 6,392,994 B1
• Filed: 12/11/1998
• Issued: 05/21/2002
• Est. Priority Date: 03/30/1998
• Status: Expired due to Term

• Current Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Original Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Inventors: Dubuc, Ken
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US09/208,982
• Time in Patent Office: 1,257 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/237, 370/387, 370/388, 370/389, 370/391, 370/392, 370/394, 370/395.1, 370/396, 370/401, 370/412, 370/477, 370/536, 370/537, 370/538
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5653 using the ATM adaptation layer [AAL]
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The ATM transmitting apparatus for transmitting messages, such as frame relay packets, associated with a plurality of connections comprises ATM layer transmission equipment for receiving multiple messages, segmenting each received message into a plurality of smaller data units, such as 48 byte AAL SAR protocol data units, and multiplexing such data units into a single stream for transport over a physical interface. A scheduler receives messages from each of the connections and transfers the messages to the transmission equipment. The scheduler can dynamically set a transmission rate for any connection, and allocates each connection whose message is transferred to the transmission equipment a substantially maximal amount of bandwidth at any given time during the transmission of the message, to thereby minimize interleaving of data units from the various connections and reduce the average latency (per unit of message) in transmitting the messages across a network.

Claims

1. Apparatus for transmitting messages associated with a plurality of connections, said apparatus comprising:

transmission equipment for receiving, segmenting and multiplexing multiple messages, receiving each of said multiple messages into one or more data units, multiplexing said data units from various connections into a single stream for transport over a physical interface at an output transmission rate, said transmission equipment comprising a segmentation means for segmenting each of said multiple messages into said data units and a multiplexer means for multiplexing said data units into said single stream;

bandwidth allocation means associated with said transmission equipment for dynamically allocating a portion of said output transmission rate to one of said various connections;

a scheduler, connected to said bandwidth allocation means, for scheduling transfer of said multiple messages to said single stream and for allocating a substantially maximum permissible portion of said output transmission rate to each of said various connections substantially when its message is transferred to said transmission equipment in order to minimize interleaving of said data units from said various connections, said scheduler transferring messages to said single stream by one of (a) receiving said multiple messages directly from said various connections and transferring said multiple messages to said segmentation means which substantially immediately transfers said multiple messages to said multiplexing means,and (b) receiving said data units from said segmentation means and transferring groups of said data units to said multiplexing means, each of said groups corresponding to a message of said multiple messages, said scheduler being enabled to set a transmission rate for each of said various connections whose message is being transmitted to said maximum permissible portion of said output transmission rate when transmitting said message, said maximum permissible portion of said output transmission rate for a given connection at a given time being the lesser of (i) a pre-specified peak transmission rate for said given connection and (ii) all unused bandwidth at said given time allocated to a service class to which said given connection belongs.

2. The apparatus according to claim 1, wherein said transmission equipment applies a round-robin service discipline in multiplexing said data units from said various connections in the process of transmitting messages.

3. The apparatus according to claim 1, wherein said scheduler transfers said multiple messages to said transmission equipment in sequential order per connection.

4. The apparatus according to claim 1, wherein, in the event a sub-plurality of said various connections each have outstanding data requests, said scheduler transfers said multiple messages to said single stream using a first-come, first served service discipline at the point of contention.

5. The apparatus according to claim 4, wherein said scheduler includes starvation prevention means to prevent the service starvation of connections.

6. The apparatus according to claim 5, wherein said starvation prevention means applies a round-robin service discipline to connections having outstanding data requests.

7. The apparatus according to claim 1, wherein in the event a sub-plurality of said various connections have pending data requests, said scheduler transfers said multiple messages to said single stream in order of arrival of said multiple messages at said scheduler.

8. The apparatus according to claim 1, wherein upon reception of a given message associated with a given connection, said scheduler is enabled to transfer said given message to said transmission equipment if free bandwidth is available for said given connection.

9. The apparatus according to claim 8, wherein, in the event no free bandwidth is available for said given connection, said scheduler is enabled to queue said given message at the end of a queue of pending messages.

10. The apparatus according to claim 1, wherein upon reception of a given message associated with a given connection, said scheduler is enabled to transfer said given message to said single stream provided free bandwidth is available for said given connection and provided that said given connection does not have a previous message being transmitted by said transmission equipment.

11. The apparatus according to claim 10, wherein upon reception of a given message associated with a given connection, said scheduler is enabled to queue said given message in the event no free bandwidth is available for said given connection or in the event that said given connection has a previous message being transmitted by said transmission equipment.

12. The apparatus according to claim 1, further including means, connected to said scheduler, for indicating when a last data unit of a transmitted message of said multiple messages for a given connection of said connections has been transmitted by said transmission equipment.

13. The apparatus according to claim 12, wherein upon indication that said transmitted message has been transmitted, said scheduler is enabled to increase the transmission rate of any connection having a message being transmitted by said transmission equipment provided that free bandwidth is available for said any connection.

14. The apparatus according to claim 13, wherein said scheduler increases the bandwidth of transmitting connections in first-come, first-served order.

15. The apparatus according to claim 12, wherein upon indication that said transmitted message has been transmitted, said scheduler is enabled to process a queued message pending transmission as a just-received message.

16. The apparatus according to claim 15, wherein said scheduler services queued messages in first-come, first-served order.

17. The apparatus according to claim 13, wherein upon indication that said transmitted message has been transmitted, said scheduler is enabled to process a queued message pending transmission as a just-received message.

18. The apparatus according to claim 17, wherein said scheduler services queued messages in first-come, first-served order.

19. A data transmission method for transporting multiple messages associated with multiple connections over a network, said method comprising steps of:

segmenting each message of said multiple messages of each connection of said multiple connections into transportable data units;

scheduling transfer of said multiple messages from said multiple connections to a multiplexing step, said scheduling comprising one of;

(i) scheduling the transfer of groups of said data units from said segmenting step to said multiplexing step, each group of said groups of said data units corresponding to a message of said multiple messages, and

(ii) scheduling the transfer of said multiple messages from said multiple connections to said segmenting step, said segmenting step substantially immediately transferring said data units to said multiplexing step;

multiplexing said data units from said multiple connections into a single stream for transport over a transmission media to a destination;

assigning a maximum permissible amount of transmission bandwidth to each connection of said multiple connections when a message thereat substantially begins to be transported over said transmission media, thereby minimizing interleaving of said data units from said multiple connections over said transmission media; and

setting said bandwidth to said maximum permissible amount during transmission of said message, said maximum permissible bandwidth for a given connection at a given time being the lesser of;

(i) a pre-specified peak transmission rate for said given connection; and

(ii) a rate using all unused bandwidth at said given time allocated to a service class to which said given connection belongs.

20. The method according to claim 19, wherein said multiplexing step applies a round-robin service discipline in multiplexing said data units from transmitting connections of said multiple connections.

21. The method according to claim 20, wherein said scheduling step transfers messages to the multiplexing step in sequential order per connection of said transmitting connections.

22. The method according to claim 21, wherein said scheduling step transfers said multiple messages to said multiplexing step using a first-come, first-served service discipline at the point of contention to connections of said transmitting connections having outstanding data requests.

23. The method according to claim 22, further including a starvation prevention step of preventing service starvation of connections.

24. The method according to claim 23, wherein said starvation-prevention step further comprises serving said connections having outstanding data requests in round robin fashion.

25. The method according to claim 19, wherein said scheduling step further comprises transferring messages to said multiplexing step in order of arrival of each of said multiple messages.

26. The method according to claim 19, wherein said assigning step further comprises increasing bandwidth of transmitting connections of said connections upon termination of the transmission of any message of said multiple messages.

27. The method according to claim 26, wherein said assigning step allocates bandwidth to currently-transmitting connections of said connections in order of the relative time at which the currently-transmitting messages thereof were passed to said multiplexing step.

28. The method according to claim 26, wherein upon reception of a particular message of said multiple messages associated with a particular connection of said multiple connections, said scheduling step transfers said particular message to said multiplexing step only if free bandwidth is available for said particular connection.

29. The method according to claim 27, further including a step of queuing said particular message at the end of a queue of pending messages in the event no bandwidth is available for said particular connection.

30. The method according to claim 19, wherein said scheduling step immediately transfers a given received message of said multiple messages to said multiplexing step provided bandwidth is available for an associated connection of said multiple connections with said given received message and provided that said associated connection does not have a previous message being transported over said transmission media.

31. The method according to claim 29, wherein said scheduling step queues said particular message in the event no bandwidth is available for said particular connection or in the event that said particular connection has a previous message being transported over said transmission media.

32. The method according to claim 28, further including a step of processing a queued message of said multiple messages as a just-received message in the event of termination of transmission of another message of said multiple messages.

33. The method according to claim 30, further including a step of processing a queued message of said multiple messages as a just-received message in the event of termination of transmission of another message of said multiple messages.

34. Apparatus for transmitting ATM adaption layer (AAL) service data units (SDUs) associated with a plurality of connections, said apparatus comprising:

segmentation means for segmenting each AAL SDU into one or more AAL segmentation and reassembly protocol data units (SAR PDUs);

ATM layer means for multiplexing said SAR PDUs of various connections of said plurality of connections into a single stream having an output transmission rate;

physical transmission means, connected to said ATM layer means, for transporting said single stream of said SAR PDUs over a physical interface;

bandwidth allocation means for dynamically allocating a portion of said output transmission rate to any connection of said plurality of connections; and

a scheduler, connected to said bandwidth allocation means, for scheduling transfer of said SDUs to said ATM layer means, and for allocating a substantially maximum permissible portion of said output transmission rate to each connection of said various connections substantially at the time its SDU is submitted to said ATM layer means in order to minimize interleaving of said SAR PDUs in said single stream, said scheduler transferring said SDUs to said ATM layer means by one of (a) receiving said SDUs from AAL users and transferring said SDUs to said segmentation means, said segmentation means substantially immediately transferring said SAR PDUs to said ATM layer means; and

(b) transferring groups of said SAR PDUs to said ATM layer means, each group of said groups corresponding to an SDU, said scheduler being enabled to set a transmission rate for a connection to a maximum permissible portion of said output transmission rate during the time an SDU of said SDUs associated with said connection is being transmitted over said physical interface, said maximum permissible portion of said output transmission rate for a given connection of said various connections at any time being the lesser of (i) a pre-specified peak transmission rate for said given connection and (ii) a total amount of free bandwidth at that time for a service class associated with said given connection.

35. The apparatus according to claim 34, wherein said ATM layer means applies a round-robin scheduling discipline in multiplexing SAR PDUs from said various connections to said single stream.

36. The apparatus according to claim 34, wherein in the event a sub-plurality of said various connections each have at least one pending data request, said scheduler transfers said SDUs to said ATM layer means using a first-come, first-served service discipline at the point of contention.

37. The apparatus according to claim 34, wherein said scheduler includes means for preventing service-starvation of a connection.

38. The apparatus according to claim 34, wherein in the event said various connections each have at least one pending data request, said scheduler transfers said SDUs to said ATM layer in order of arrival of said SDUs at said scheduler.

39. The apparatus according to claim 34, wherein upon termination of transmission of an SDU of said SDUs, said scheduler is enabled to increase transmission rate of connections whose SDUs are being transmitted by said ATM layer means, bandwidth being allocated to the currently-transmitting connections in order of the relative time at which currently-transmitting SDUs thereof were passed to said ATM layer means.

40. The apparatus according to claim 34, wherein said scheduler maintains (i) a first queue of connections of said various connections whose SDUs are being transmitted by said ATM layer means, (ii) a second queue of connections of said various connections having pending data requests, and (iii) a third queue for storing unprocessed SDUs of currently transmitting connections of said various connections having pending data requests.

41. The apparatus according to claim 40, wherein upon reception of a given SDU of said SDUs associated with a given connection of said various connections, said scheduler is enabled to place said given connection at the end of said second queue and place said given SDU in said third queue in the event no bandwidth is available to said given connection.

42. The apparatus according to claim 40, wherein upon reception of a given SDU of said SDUs associated with a given connection of said various connections, said scheduler is enabled to place said given SDU in said third queue in the event said given connection is currently transmitting or has a pending data request.

43. The apparatus according to claim 40, wherein upon reception of a given SDU of said SDUs associated with a given connection of said various connections, said scheduler is enabled to transfer said given SDU to said ATM layer means provided bandwidth is available to said given connection and provided that said given connection is not currently transmitting or has no pending data requests.

44. The apparatus according to claim 40, further including SDU transmission indication means for indicating when a last SAR PDU of any one of said SDUs has been transmitted.

45. The apparatus according to claim 44, wherein upon actuation of said SDU transmission indication means, said scheduler is enabled to increase transmission rate of any connection of said various connections having an SDU being transmitted, bandwidth being allocated to amongst currently-transmitting connections of said various connections in order of the relative time at which the currently-transmitting SDUs thereof were passed to one of said ATM layer means and said segmentation means.

46. The apparatus according to claim 44, wherein upon actuation of said SDU transmission indication means, said scheduler is enabled to remove a given connection of said various connections from said first queue, check whether said given connection has any SDUs waiting in said third queue, and if so, place said given connection at the end of said second queue.

47. The apparatus according to claim 46, wherein upon actuation of said SDU transmission indication means, said scheduler is enabled to scan said second queue starting from the head thereof and, provided bandwidth remains available for a particular connection listed therein, remove said particular connection from said second queue, pass an earliest SDU of said particular connection stored in said third queue to one of said segmentation means and said ATM layer means, allocate a maximal amount of bandwidth to said particular connection, and place said particular connection at the end of said first queue.

48. Apparatus for transmitting ATM adaption layer (AAL) service data units (SDUs) associated with a plurality of connections, said apparatus comprising:

segmentation means, for segmenting each SDU of said SDUs into one or more AAL segmentation and reassembly protocol data units (SAR PDUs);

ATM layer means, for multiplexing said SAR PDUs into a single stream having an output transmission rate;

physical transmission means, connected to said ATM layer means, for transporting said single stream of SAR PDUs over a physical interface;

bandwidth allocation means, for dynamically allocating a portion of said output transmission rate to any connection of said plurality of connections; and

scheduling means, connected to said bandwidth allocation means, for scheduling transfer of said SDUs to said ATM layer means, and for allocating a maximal portion of said output transmission rate to a connection of said plurality of connections while an SDU associated with said connection is being transmitted by said ATM layer means, said scheduling means transferring messages relating to said SDUs to said ATM layer means by one of (a) receiving said SDUs directly from AAL users and transferring said SDUs to said segmentation means which substantially immediately transfers said messages to the said ATM layer means, and (b) receiving said SAR PDUs from said segmentation means and transferring groups of said SAR PDUs to said ATM layer means, wherein each group of said groups of said SAR PDUs corresponds to a particular SDU, said maximal portion of said output transmission rate for a given connection of said plurality of connections at any given time being the lesser of (i) a pre-specified peak transmission rate for said given connection and (ii) all unused bandwidth at a given time allocated to a service class to which said given connection belongs.

49. The apparatus according to claim 48, wherein said scheduling means maintains (i) a list of currently transmitting connections of said plurality of connections, (ii) a queue of connections having pending data requests, and (iii) a set of queues for storing unprocessed SDUs of said connections either currently transmitting or having pending data requests.

50. The apparatus according to claim 49, wherein said scheduling means is enabled to place a connection of said plurality of connections at the end of said queue and place an associated SDU with said connection in said set of queues in the event no free bandwidth is available to said connection.

51. The apparatus according to claim 49, wherein said scheduling means is enabled to place a particular SDU of said SDUs in said set of queues in the event an associated connection with said particular SDU is currently transmitting or has a pending data request.

52. The apparatus according to claim 49, wherein the scheduling means is enabled to transfer a particular SDU of said SDUs to said ATM layer means provided bandwidth is available to an associated connection with said particular SDU and provided said associated connection is not currently transmitting or has no pending data requests.

53. The apparatus according to claim 49, further including the SDU transmission indication means for indicating when a last SAR PDU of any SDU of said SDUs has been transmitted.

54. The apparatus according to claim 53, wherein upon actuation of said SDU transmission indication means, said scheduling means is enabled to increase transmission rate of a particular connection of said plurality of connections having an SDU being transmitted, bandwidth being allocated to currently-transmitting connections of said plurality of connections in order of the relative time at which the currently-transmitting AAL SDUs thereof were passed to a SAR service access point.

55. The apparatus according to claim 53, wherein upon actuation of the SDU transmission indication means in respect of a given SDU of said SDUs associated with a given connection, said scheduling means removes said given connection from said list, checks whether said given connection has any SDUs stored in said set of queues, and, if so, places said given connection at the end of a queue of said set of queues.

56. The apparatus according to claim 53, wherein upon actuation of said SDU transmission indication means, said scheduling means is enabled to scan said queue in order starting from the head thereof and, provided unallocated bandwidth remains for a given connection listed therein, remove said given connection from said set of queues, pass an earliest SDU of said given connection stored in said set of queues to said ATM layer means allocate said maximal amount of bandwidth to said given connection, and place said given connection in said first queue.

57. Apparatus for transmitting messages associated with a plurality of connections, said apparatus comprising:

transmission equipment for receiving said messages, segmenting each received message of said messages into one or more data units, and multiplexing said data units from said plurality of connections into a single stream for transport over a physical interface at an output transmission rate;

a bandwidth allocation arrangement associated with said transmission equipment adapted to dynamically allocate a portion of said output transmission rate to one connection of said plurality of connections; and

a scheduler, connected to said bandwidth allocation arrangement, adapted to schedule transfer of said messages to said single stream of said transmission equipment and to allocate a substantially maximum permissible portion of said output transmission rate to a given connection of said plurality of connections when a request for service for said given connection exists and said given connection is not being serviced, said maximum permissible portion of said output transmission rate for said connection at any given time being the lesser of (i) a pre-specified peak transmission rate for said connection and (ii) substantially all available unused bandwidth at the given time allocated to a service class to which said connection belongs.

58. The apparatus according to claim 57, wherein

said transmission equipment comprises

a segmentation arrangement adapted to segmenting each message of said messages into said data units; and

and a multiplexing arrangement adapted to multiplex said each message into said single stream; and

said scheduler transfers said messages to said single stream by one of;

(a) receiving said messages from said connections and transferring said messages to said segmentation arrangement which substantially immediately transfers said messages to said multiplexing arrangement; and

(b) receiving said data units from said segmentation arrangement and transferring groups of said units to the said multiplexing arrangement, wherein each said group of said groups corresponds to one message of said messages.

59. The apparatus according to claim 58, wherein said scheduler is enabled to additionally set a transmission rate for each connection of said plurality of connections whose message is being transmitted to said maximum permissible portion of said output transmission rate.

60. The apparatus according to claim 59, wherein upon completion of transmission of one message of said messages, said scheduler is enabled to increase the transmission rate of any connection of said connections having its message being transmitted by said transmission equipment if bandwidth is available for said any connection.

61. The apparatus according to claim 60, wherein upon reception of a given message associated with a given connection, said scheduler is enabled to queue said given message in a queue of messages pending transmission in the event no free bandwidth is available for said given connection or in the event that said given connection has a previous message being transmitted by said transmission equipment.

62. The apparatus according to claim 61, wherein said scheduler is enabled to process a queued message in said queue of messages pending transmission as a just-received message when transmission of a currently transmitted message of said messages is completed.