Traffic scheduling method, system and article of manufacture for a wireless access to an asynchronous transfer mode network

• US 6,141,336 A
• Filed: 11/13/1997
• Issued: 10/31/2000
• Est. Priority Date: 12/13/1996
• Status: Expired due to Term

• Current Assignee: Wistron Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Passas, Nikos, Merakos, Lazaros, Marmigere, Gerard, Bauchot, Frederic
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US08/970,048
• Time in Patent Office: 1,083 Days
• Field of Search: 370/461, 370/462, 370/321, 370/322, 370/329, 370/326, 370/337, 370/345, 370/346, 370/347, 370/348, 370/449, 340/825.07, 340/825.08
• US Class Current: 370/348
• CPC Class Codes: H04L 2012/5607 Radio
• CPC Class Codes: H04W 72/1221 based on age of data to be sent
• CPC Class Codes: H04W 74/02 Hybrid access
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02
• CPC Class Codes: H04W 92/02 Inter-networking arrangements

Abstract

A method, system and article of manufacture for exchanging data between an asynchronous network and a synchronous network is presented. Data is exchanged between the networks in a sequence of time frames which are partitioned into downlink, uplink and contention periods. These downlink, uplink and contention periods are further divided into time slots, each of which carries either data or control cells between the networks. Cells of data are allocated to the time slots according to their cell deadlines which are proportional to the transmission delay of the network connection over which the cells are to be carried. This cell allocation is then stored in a slot map and communicated to all nodes within the networks in order to facilitate the data transmission.

Claims

1. A method comprising the steps of:

defining a sequence of time frames for exchanging data between nodes in an asynchronous network and nodes in a synchronous network;

dividing each of the defined time frames into a plurality of time slots;

requesting time slots within a time frame for carrying data cells over connections between the synchronous and asynchronous networks;

allocating slots within a time frame to the requests for time slots according to cell deadlines which are proportional to a transmission delay of the connection over which the data cells are to be carried, said allocation proceeding in order of a connection priority and continuing until one of an exhaustion of all requests for time slots and an exhaustion of all time slots within the time frame occurs;

partitioning each time frame into a down period for contention-free downlink transmission of data from the asynchronous network to the synchronous network,

an up period for contention-free uplink transmission of data from the synchronous network to the asynchronous network, and

a contention period for contention-based uplink transmission of data from the synchronous network to the asynchronous network;

generating slot maps describing the partitioning of time frames into up, down, and contention periods and describing the allocation of time slots within the time frames; and

exchanging data between the synchronous and asynchronous networks in time frames according to each time frame'"'"'s slot map.

2. The method according to claim 1, wherein in said exchanging step at least one of the nodes in the synchronous network is a concentrator point interfacing the synchronous network with a second asynchronous network.

3. The method according to claim 1, wherein said step of allocating slots comprises the steps of

determining whether a request for a time slot within a time frame for a cell c_n (i) of a group of cells c_n requesting time slots for a connection C_n is a first request for the connection C_n in the time frame, and if so

determining whether the number of free slots E_n in an interval, where 1 is a slot following a frame header for the time frame and where D_n is a slot corresponding to an earliest deadline of all deadlines for the group of cells c_n, is greater than a number of time slots Φ

reserved for the transmission of a header which together with at least one cell of the group of cells c_n forms a data unit for the connection C_n, and if so

shifting any data units allocated to slots to the left of D_n but not occupying D_n (Φ

+1) positions to the left to leave (Φ

+1) empty slots as close to D_n as possible, then

allocating one of the emptied slots to the cell c_n (i) and the remaining Φ

emptied slots to the header forming a data unit for the connection C_n in the time frame.

4. The method according to claim 3, wherein if the number of free slots E_n in the interval [1, D_n ] is less than or equal to Φ

, said step of allocating slots further comprises the steps of

determining if the number of free slots in an interval [1, (D_n +Δ

_n ], where (D_n +Δ

_n) is a slot corresponding to a maximum authorized deadline for the group of cells c_n is greater than Φ

, and if so

determining whether shifting any data units allocated to slots to the right of D_n but not occupying D_n (Φ

+1-E_n) slots to the right will exceed an maximum authorized deadline associated with the data units to be shifted, and if it does not

shifting an data units allocated to slots to the left of D_n and an data unit occupying D_n E_n slots to the left, then shifting any data units allocated to slots to the right of D_n but not occupying D_n (Φ

+1-E_n) slots to the right, so as to leave (Φ

+1) empty slots as close to D_n as possible, then

allocating one of the emptied slots to the cell c_n (i) and the remaining Φ

emptied slots to the header forming a data unit for the connection C_n in the time frame.

5. The method according to claim 4, wherein if the request for a cell c_n (i) is not a first request for the connection C_n in the time frame, said step of allocating slots further comprises the steps of

determining if there is at least one empty slot to the left of the data unit for the connection C_n in the time frame, and if so shifting any data units allocated to slots between an empty slot nearest and to the left of the data unit for the connection C_n and the data unit for the connection C_n itself one slot to the left, then allocating the cell c_n (i) to the now empty slot following the data unit for the connection C_n,

determining whether the slot following the data unit for the connection C_n is empty when there are no empty slots to the left of the data unit for the connection C_n in the time frame, and if so allocating cell c_n (i) to the empty slot following the data unit for the connection C_n unless doing so will cause the allocation of cell c_n (i) to exceed the maximum authorized deadline for the group of cells c_n.

6. The method of claim 5, wherein if there are no empty slots to the left of the data unit for the connection C_n and if the slot following the data unit for connection C_n is not empty, said step of allocating slots further comprises the steps of

determining if any cells allocated to slots up to a first empty slot following the frame header have reached their respective maximum authorized deadlines, and if they have not

shifting one position to the right any allocations between the data unit for the connection C_n and the first empty slot following the frame header, so as to leave empty the slot following the data unit for the connection C_n, then

allocating cell c_n (i) to the empty slot following the data unit for the connection C_n.

7. The method of claim 1, wherein in said partitioning step, the time frames are further partitioned into additional interleaved down and up periods for contention-free downlink and uplink transmission, the additional interleaved periods being followed by a contention period for contention-based uplink transmission.

8. The method of claim 7, wherein the asynchronous networks are ATM networks and the synchronous network is a wireless network.

9. The method of claim 1, wherein in said requesting step, requests for time slots for sending data cells from the asynchronous network to the synchronous network correspond to the arrival time at an access point linking the synchronous and asynchronous networks of cells sent from nodes in the asynchronous network.

10. The method of claim 1, wherein in said requesting step, requests for time slots for sending data cells from the synchronous network to the asynchronous network are derived at an access point linking the synchronous and asynchronous networks from a service class of the connection over which the data cells are to be carried.

11. The method of claim 1, wherein in said requesting step, requests for time slots for sending data cells from the synchronous network to the asynchronous network are carried in data units sent from nodes in the synchronous network and received at an access point linking the synchronous and asynchronous networks.

12. The method of claim 9, wherein in said allocating step, deadlines for cells requesting time slots for transmission from the asynchronous network to the synchronous network are derived from the arrival time of the cells at the access point.

13. The method of claim 10, wherein in said allocating step, deadlines for cells requesting time slots for transmission from the synchronous network to the asynchronous network are derived from an arrival time of a cell preceding a request for a time slot derived at the access point.

14. The method of claim 11, wherein in said allocating step, deadlines for cells requesting time slots for transmission from the synchronous network to the asynchronous network are derived from an arrival time of a cell preceding a request for a time slot carried in a data unit and received at the access point.

15. The method of claim 11, wherein in said allocating step, deadlines for cells requesting time slots for transmission from the synchronous network to the asynchronous network are derived from an arrival time of the cells in an output queue of the nodes of the synchronous network, the arrival time being stored in a time stamp and carried in a reservation request sent from the synchronous network to the access point.

16. The method of claim 1, wherein said partitioning step comprises the steps of

packing all allocations between the frame header and a left-most uplink data unit as close to the beginning of the time frame as possible;

determining if the number of empty time slots N immediately preceding the left-most uplink data unit is greater than or equal to a number of time slots P reserved for a period overhead;

reserving P slots immediately preceding the left-most uplink data unit for the period overhead if P is greater than or equal to N;

reallocating (P-N) slots immediately preceding the left-most uplink data unit to the period overhead if N is less than P, and if said reallocating results in a data unit having Φ

slots or less, then deallocating that data unit from the time frame;

packing downlink data units allocated to slots to the right of the period overhead and any portions of data units greater than Φ

slots allocated thereto into any empty slots immediately preceding the period overhead;

packing all allocations between the period overhead and any downlink data unit following the period overhead as close to the period overhead as possible, then deallocating any such downlink data unit following the period overhead; and

reserving a plurality of slots following the last uplink data unit in the time frame for contention-based uplink transmission of data from the asynchronous network to the synchronous network.

17. A system comprising:

an asynchronous network including at least one asynchronous node;

a synchronous network including a plurality of synchronous nodes;

means for defining a sequence of time frames for exchanging data between nodes in the asynchronous network and nodes in the synchronous network;

means for dividing each of the defined time frames into a plurality of time slots;

means for requesting time slots within a time frame for carrying data cells over connections between the synchronous and asynchronous networks;

means for allocating slots within a time frame to the requests for time slots according to cell deadlines which are proportional to a transmission delay of the connection over which the data cells are to be carried, said allocation proceeding in order of a connection priority and continuing until one of an exhaustion of all requests for time slots and an exhaustion of all time slots within the time frame occurs;

means for partitioning each time frame into a down period for contention-free downlink transmission of data from the asynchronous network to the synchronous network, an up period for contention-free uplink transmission of data from the synchronous network to the asynchronous network, and a contention period for contention-based uplink transmission of data from the synchronous network to the asynchronous network;

means for generating slot maps describing the partitioning of time frames into up, down, and contention periods and describing the allocation of time slots within the time frames; and

means for exchanging data between the synchronous and asynchronous networks in time frames according to each time frame'"'"'s slot map.

18. An article of manufacture, comprising:

a processor usable medium having a readable program embodied therein for exchanging data between a synchronous network and an asynchronous network, wherein the processor readable program when executed on the processor causes the processor to

define a sequence of time frames for exchanging data between nodes in an asynchronous network and nodes in a synchronous network;

divide each of the defined time frames into a plurality of time slots;

request time slots within a time frame for carrying data cells over connections between the synchronous and asynchronous networks;

allocate slots within a time frame to the requests for time slots according to cell deadlines which are proportional to a transmission delay of the connection over which the data cells are to be carried, said allocation proceeding in order of a connection priority and continuing until one of an exhaustion of all requests for time slots and an exhaustion of all time slots within the time frame occurs;

partition each time frame into a down period for contention-free downlink transmission of data from the asynchronous network to the synchronous network, an up period for contention-free uplink transmission of data from the synchronous network to the asynchronous network, and a contention period for contention-based uplink transmission of data from the synchronous network to the asynchronous network;

generate slot maps describing the partitioning of time frames into up, down, and contention periods and describing the allocation of time slots within the time frames; and

exchange data between the synchronous and asynchronous networks in time frames according to each time frame'"'"'s slot map.

19. The article of manufacture of claim 18, wherein the processor readable program when executed on the processor further causes the processor to

determine whether a request for a time slot within a time frame for a cell c_n (i) of a group of cells c_n requesting time slots for a connection C_n is a first request for the connection C_n in the time frame, and if so

determine whether the number of free slots E_n in an interval [1, D_n ], where 1 is a slot following a frame header for the time frame and where D_n is a slot corresponding to an earliest deadline of all deadlines for the group of cells c_n, is greater than a number of time slots Φ

reserved for the transmission of a header which together with at least one cell of the group of cells c_n forms a data unit for the connection C_n, and if so

shift any data units allocated to slots to the left of D_n but not occupying D_n (Φ

+1) positions to the left to leave (Φ

+1) empty slots as close to D_n as possible, then

allocate one of the emptied slots to the cell c_n (i) and the remaining Φ

emptied slots to the header forming a data unit for the connection C_n in the time frame.

20. The article of manufacture of claim 19, wherein if the number of free slots E_n in the interval [1, D_n ] is less than or equal to Φ

, the processor readable program when executed on the processor further causes the processor to

determine if the number of free slots in an interval [1, (D_n +Δ

_n)], where (D_n +Δ

_n) is a slot corresponding to a maximum authorized deadline for the group of cells c_n, is greater than Φ

, and if so

determine whether shifting any data units allocated to slots to the right of D_n but not occupying D_n (Φ

+1-E_n) slots to the right will exceed any maximum authorized deadline associated with the data units to be shifted, and if it does not

shift any data units allocated to slots to the left of D_n and any data unit occupying D_n E_n slots to the left, then shifting any data units allocated to slots to the right of D_n but not occupying D_n (Φ

+1-E_n) slots to the right, so as to leave (Φ

+1) empty slots as close to D_n as possible, then

allocate one of the emptied slots to the cell c_n (i) and the remaining Φ

emptied slots to the header forming a data unit for the connection C_n in the time frame.

21. The article of manufacture of claim 20, wherein if the request for a cell c_n (i) is not a first request for the connection C_n in the time frame, the processor readable program when executed on the processor further causes the processor to

determine if there is at least one empty slot to the left of the data unit for the connection C_n in the time frame, and if so shifting any data units allocated to slots between an empty slot nearest and to the left of the data unit for the connection C_n and the data unit for the connection C_n itself one slot to the left, then allocating the cell c_n (i) to the now empty slot following the data unit for the connection C_n,

determine whether the slot following the data unit for the connection C_n is empty when there are no empty slots to the left of the data unit for the connection C_n in the time frame, and if so allocating cell c_n (i) to the empty slot following the data unit for the connection C_n unless doing so will cause the allocation of cell c_n (i) to exceed the maximum authorized deadline for the group of cells c_n.

22. The article of manufacture of claim 21, wherein if there are no empty slots to the left of the data unit for the connection C_n and if the slot following the data unit for connection C_n is not empty, the processor readable program when executed on the processor further causes the processor to

determine if any cells allocated to slots up to a first empty slot following the frame header have reached their respective maximum authorized deadlines, and if they have not

shift one position to the right any allocations between the data unit for the connection C_n and the first empty slot following the frame header, so as to leave empty the slot following the data unit for the connection C_n, then

allocate cell c_n (i) to the empty slot following the data unit for the connection C_n.

24. The article of manufacture of claim 18, wherein the processor readable program when executed on the processor further causes the processor to

further partition the time frames into additional interleaved down and up periods for contention-free downlink and uplink transmission, the additional interleaved periods being followed by a contention period for contention-based uplink transmission.

23. The article of manufacture of 18, wherein the processor readable program when executed on the processor further causes the processor to

pack all allocations between the frame header and a left-most uplink data unit as close to the beginning of the time frame as possible;

determine if the number of empty time slots N immediately preceding the left-most uplink data unit is greater than or equal to a number of time slots P reserved for a period overhead;

reserve P slots immediately preceding the left-most uplink data unit for the period overhead if P is greater than or equal to N;

reallocate (P-N) slots immediately preceding the left-most uplink data unit to the period overhead if N is less than P, and if said reallocating results in a data unit having Φ

slots or less, then deallocating that data unit from the time frame;

pack downlink data units allocated to slots to the right of the period overhead and any portions of data units greater than Φ

slots allocated thereto into any empty slots immediately preceding the period overhead;

pack all allocations between the period overhead and any downlink data unit following the period overhead as close to the period overhead as possible, then deallocating any such downlink data unit following the period overhead; and

reserve a plurality of slots following the last uplink data unit in the time frame for contention-based uplink transmission of data from the asynchronous network to the synchronous network.