Round-trip delay optimization of multiplexed speech channels

• US 5,936,964 A
• Filed: 04/18/1997
• Issued: 08/10/1999
• Est. Priority Date: 04/18/1997
• Status: Expired due to Term

• Current Assignee: Unwired Planet LLC (JP Morgan Chase & Co)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Westberg, Lars, Valko, Andras
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US08/844,519
• Time in Patent Office: 844 Days
• Field of Search: 370/229, 370/230, 370/231, 370/235, 370/238, 370/447, 370/411, 370/412, 370/468, 370/508, 370/516, 370/517, 370/519, 370/280, 370/252, 370/276, 370/428, 370/429, 370/253 , 370/532, 370/249, 370/437, 370/537, 370/442, 375/371, 375/220, 375/356
• US Class Current: 370/468
• CPC Class Codes: H04J 3/247 ATM or packet multiplexing
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Data packets are transmitted in forward and backward directions via a multiplexed communications medium, wherein each of the data packets is associated with a corresponding one of a plurality of connections. Transmission is performed by, for each connection, assigning a forward delay limit and a corresponding backward delay limit, wherein the sum of the forward and backward delay limits is equal to a round-trip delay bound for the connection. The assigned forward delay limits are used to determine the order in which the data packets supplied by the plurality of connections will be transmitted in the forward direction. Similarly, the assigned backward delay limits are used to determine the order in which the data packets supplied by the plurality of connections will be transmitted in the backward direction. One embodiment accomplishes the forward and backward delay limit assignments by maintaining forward and backward lists of connection identifiers sorted in, for example, ascending order based on time of connection establishment in the forward direction, and in descending order based on time of connection establishment in the backward direction. In another embodiment, transmission order is determined by sorting arriving data packets at the time of their corresponding connection identifiers, wherein the forward and backward sorting rules are selected so that a sum of a forward transmission delay limit and a backward transmission delay limit is less than or equal to a round-trip delay bound for each connection.

Claims

1. A method of transmitting data packets in forward and backward directions via a multiplexed communications medium, wherein each of the data packets is associated with a corresponding one of a plurality of connections, the method comprising the steps of:

for each connection, assigning a forward delay limit and a corresponding backward delay limit, wherein the sum of the forward and backward delay limits is less than or equal to a round-trip delay bound for the connection;

using the assigned forward delay limits to determine the order in which the data packets supplied by the plurality of connections will be transmitted in the forward direction; and

using the assigned backward delay limits to determine the order in which the data packets supplied by the plurality of connections will be transmitted in the backward direction.

2. The method of claim 1, wherein:

for each of the connections, the forward delay limit, d_forward, is in a range

space="preserve" listing-type="equation">d.sub.min ≦

d.sub.forward ≦

d.sub.max

where d_min is a predefined minimum multiplexing delay, and d_max is a predefined maximum multiplexing delay; and

for each of the connections, the corresponding backward delay limit, d_backward, is assigned a value in accordance with

space="preserve" listing-type="equation">d.sub.backward ≦

d.sub.max -d.sub.forward.

3. The method of claim 1, wherein the round-trip delay bound is the same for each of the connections.

4. A method of transmitting data packets in forward and backward directions via a multiplexed communications medium, wherein each of the data packets is associated with a corresponding one of a plurality of connections, the method comprising the steps of:

providing a forward multiplexing list;

providing a backward multiplexing list;

when a connection is established, inserting a corresponding connection identifier at a first position in the forward multiplexing list, and inserting the corresponding connection identifier at a second position in the backward multiplexing list, wherein the distance of the first position from the head of the forward multiplexing list is less than or equal to the distance of the second position from the back of the backward multiplexing list;

in the forward direction, transmitting arriving data packets supplied from the plurality of connections in an order determined by the forward multiplexing list; and

in the backward direction, transmitting arriving data packets supplied from the plurality of connections in an order determined by the backward multiplexing list.

5. The method of claim 4, wherein:

the first position is the head of the forward multiplexing list; and

the second position is the end of the backward multiplexing list.

6. The method of claim 4, further comprising the step of:

if a first data packet that should be transmitted now is not yet available while data packets from other connections are available, then waiting until the first data packet becomes available.

7. The method of claim 4, further comprising the step of:

for the forward direction, if a first data packet that should be transmitted now is not yet available while data packets from other connections are available, then skipping over the first data packet and transmitting a next data packet as determined by the forward multiplexing list.

8. The method of claim 7, wherein the step of skipping over the first data packet and transmitting the next data packet as determined by the forward multiplexing list further comprises the step of:

after transmitting the next data packet as determined by the forward multiplexing list, transmitting the first data packet.

9. The method of claim 8, further comprising the step of:

after transmitting the first data packet, transmitting a next not-yet-transmitted data packet as determined by the forward multiplexing list.

10. A method of transmitting data packets in forward and backward directions via a multiplexed communications medium, wherein each of the data packets is associated with a corresponding one of a plurality of connections, the method comprising the steps of:

in the forward direction, sorting arriving data packets in accordance with a first sorting rule based on connection identifiers of the corresponding connections, and transmitting the arriving data packets in the forward direction in an order based on the forward direction sorting step; and

in the backward direction, sorting arriving data packets in accordance with a second sorting rule based on connection identifiers of the corresponding connections, and transmitting the arriving data packets in the backward direction in an order based on the backward sorting step,

wherein the first and second sorting rules are selected so that a sum of a forward transmission delay limit and a backward transmission delay limit is less than or equal to a round-trip delay bound for each connection.

11. The method of claim 10 wherein:

the first sorting rule is sorting in ascending order; and

the second sorting rule is sorting in descending order.

12. The method of claim 10, wherein the sorting and transmitting steps in the forward direction comprise the steps of:

inserting the arriving data packets into a buffer so that the buffer will contain all data packets that have arrived, wherein the buffer contents are sorted in ascending order; and

transmitting the arriving data packets from a head of the buffer in ascending order.

13. The method of claim 10, wherein the sorting and transmitting steps in the forward direction comprise the steps of:

inserting connection identifiers associated with the arriving data packets into a buffer so that the buffer will contain all connection identifiers associated with data packets that have arrived, wherein the buffer contents are sorted in ascending order; and

transmitting the data packets that have arrived in an order determined by the order of the connection identifiers in the buffer.

14. An apparatus for transmitting data packets in forward and backward directions via a multiplexed communications medium, wherein each of the data packets is associated with a corresponding one of a plurality of connections, the apparatus comprising:

means for assigning, for each connection, a forward delay limit and a corresponding backward delay limit, wherein the sum of the forward and backward delay limits is equal to a round-trip delay bound for the connection;

means for using the assigned forward delay limits to determine the order in which the data packets supplied by the plurality of connections will be transmitted in the forward direction; and

means for using the assigned backward delay limits to determine the order in which the data packets supplied by the plurality of connections will be transmitted in the backward direction.

15. The apparatus of claim 14, wherein:

for each of the connections, the forward delay limit, d_forward, is in a range

space="preserve" listing-type="equation">d.sub.min ≦

d.sub.forward ≦

d.sub.max

where d_min is a predefined minimum multiplexing delay, and d_max is a predefined maximum multiplexing delay; and

for each of the connections, the corresponding backward delay limit, d_backward, is assigned a value in accordance with

space="preserve" listing-type="equation">d.sub.backward ≦

d.sub.max -d.sub.forward.

16. The apparatus of claim 14, wherein the round-trip delay bound is the same for each of the connections.

17. An apparatus for transmitting data packets in forward and backward directions via a multiplexed communications medium, wherein each of the data packets is associated with a corresponding one of a plurality of connections, the apparatus comprising:

a forward multiplexing list;

a backward multiplexing list;

means, responsive to a connection being established, for inserting a corresponding connection identifier at a first position in the forward multiplexing list, and for inserting the corresponding connection identifier at a second position in the backward multiplexing list, wherein the distance of the first position from the head of the forward multiplexing list is less than or equal to the distance of the second position from the back of the backward multiplexing list;

in the forward direction, means for transmitting arriving data packets supplied from the plurality of connections in an order determined by the forward multiplexing list; and

in the backward direction, means for transmitting arriving data packets supplied from the plurality of connections in an order determined by the backward multiplexing list.

18. The apparatus of claim 17, wherein:

the first position is the head of the forward multiplexing list; and

the second position is the end of the backward multiplexing list.

19. The apparatus of claim 17, further comprising:

means, responsive to non-availability of a first data packet that should be transmitted now while data packets from other connections are available, for waiting until the first data packet becomes available.

20. The apparatus of claim 17, further comprising:

for the forward direction, means, responsive to non-availability of a first data packet that should be transmitted now, for skipping over the first data packet and transmitting a next available data packet as determined by the forward multiplexing list.

21. The apparatus of claim 20, wherein the means for skipping over the first data packet and transmitting the next available data packet as determined by the forward multiplexing list further comprises:

means for transmitting the first data packet after transmitting the next data packet as determined by the forward multiplexing list.

22. The apparatus of claim 21, further comprising:

means for transmitting a next not-yet-transmitted data packet as determined by the forward multiplexing list after transmitting the first data packet.

23. An apparatus for transmitting data packets in forward and backward directions via a multiplexed communications medium, wherein each of the data packets is associated with a corresponding one of a plurality of connections, the apparatus comprising:

in the forward direction, means for sorting arriving data packets in accordance with a first sorting rule based on connection identifiers of the corresponding connections, and for transmitting the arriving data packets in the forward direction in an order based on the forward direction sorting operation; and

in the backward direction, means for sorting arriving data packets in accordance with a second sorting rule based on connection identifiers of the corresponding connections, and for transmitting the arriving data packets in the backward direction in an order based on the backward sorting operation,

wherein the first and second sorting rules are selected so that a sum of a forward transmission delay limit and a backward transmission delay limit is less than or equal to a round-trip delay bound for each connection.

24. The apparatus of claim 23 wherein:

the first sorting rule is sorting in ascending order; and

the second sorting rule is sorting in descending order.

25. The apparatus of claim 23, wherein the sorting and transmitting means in the forward direction comprises:

means for inserting the arriving data packets into a buffer so that the buffer will contain all data packets that have arrived, wherein the buffer contents are sorted in ascending order; and

means for transmitting the arriving data packets from a head of the buffer in ascending order.

26. The apparatus of claim 23, wherein the means for sorting and transmitting in the forward direction comprises:

means for inserting connection identifiers associated with the arriving data packets into a buffer so that the buffer will contain all connection identifiers associated with data packets that have arrived, wherein the buffer contents are sorted in ascending order; and

means for transmitting the data packets that have arrived in an order determined by the order of the connection identifiers in the buffer.