Method and apparatus for an OFDMA parallel architecture scheduler

1. A method comprising:

receiving, at a wireless communication device, a plurality of requests from a plurality of users for allocation of orthogonal frequency division multiple access (OFDMA) sub-channels;

obtaining a channel quality index for each of said users over each sub-channel of the OFDMA system;

calculating an optimization of sub-channels based on said channel quality indices, wherein calculating the optimization includes determining a first graph including a first user node corresponding to a first user of said users and a first sub-channel node corresponding to a first sub-channel of said sub-channels, adding to the first graph a second user node corresponding to a second user of said users and a second sub-channel node corresponding to a second sub-channel of said sub-channels, determining a second graph based at least on said first graph, and determining a maximum weight path from said second user node to said second sub-channel node in the second graph; and

allocating, by said wireless communication device, said plurality of OFDMA sub-channels to said plurality of users based on said maximum path weight.

2. The method of claim 1 , further comprising communicating with each of said users over said allocated sub-channel.

3. The method of claim 1 , wherein calculating the optimization comprises:

combining said maximum path weight with a channel quality index for the second sub-channel.

4. The method of claim 1 , wherein calculating the optimization includes:

calculating a first edge of said first graph from a first matching calculated from said first user node and said first sub-channel node;

calculating a second edge from a second matching calculated from said second user node and said second sub-channel node,

wherein determining said second graph includes determining said second graph based at least on said first graph, said second edge, said second user node, and said second sub-channel node.

5. The method of claim 4 , wherein calculation of said optimization further comprises:

subtracting said second user node and said second sub-channel node from said second graph;

modifying said second user node;

adding the modified second user node and said second sub-channel node to said second graph;

calculating a third matching from said modified second user node and said second sub-channel node;

calculating a third edge from said third matching;

calculating a third graph from at least said second graph; and

calculating a maximum weight path from said modified second user node to said second sub-channel node within said third graph.

6. The method of claim 1 , wherein said first graph and said second graph are bipartite graphs.

7. The method of claim 1 , further comprising storing said first graph and said second graph in a memory.

8. The method of claim 1 , wherein said OFDMA system is a wireless network system.

9. The method of claim 1 , wherein said allocation further comprises allocation of two or more sub-channels to each of one or more of said users, based on admission control requests of said users.

10. The method of claim 1 , wherein said allocation further comprises allocation of one or more sub-channels to one or more null users, based on said optimization.

11. A system comprising:

a wireless server adapted to communicate with a plurality of users using an Orthogonal-Frequency-Division-Multiple-Access (OFDMA) protocol, wherein the wireless server is adapted to receive from said users a plurality of channel quality indices relating to a quality of communication for the users over plurality of sub-channels,

wherein said wireless server comprises an allocation unit to calculate optimal allocation of the sub-channels to said users based on said channel quality indices, wherein said allocation unit comprises:

a plurality of processing units to generate a plurality of path-weight outputs corresponding to said plurality of said sub-channels, respectively, wherein a processing unit corresponding to a sub-channel of said sub-channels is connected to receive an output of every other processing unit of said processing units, and wherein the processing unit is to determine a plurality of path weights based on channel quality indices for the users over said sub-channel and based on path-weight outputs of other sub-channels, to select a maximum path weight of said plurality of path weights, and to generate a path-weight output corresponding to said sub-channel by combining said maximum path weight with a channel quality index for the sub-channel.

12. The system of claim 11 , further comprising a transmitter connected to said server to communicate with said users over the allocated sub-channels.

13. The system of claim 11 , wherein said allocation unit is to determine a first graph including a first user node corresponding to a first user of said users and a first sub-channel node corresponding to a first sub-channel of said sub-channels, to add to the first graph a second user node corresponding to a second user of said users and a second sub-channel node corresponding to a second sub-channel of said sub-channels, to determine a second graph based at least on said first graph, to determine a maximum weight path from said second user node to said second sub-channel node in the second graph, and to allocate said plurality of sub-channels to said plurality of users based on said the maximum path weight.

14. The system of claim 13 , wherein said first graph and said second graph are bipartite graphs.

15. The system of claim 13 , wherein said server further comprises a memory to store said first graph and said second graph.

16. The system of claim 13 , wherein said allocation unit is to calculate the optimal allocation by:

subtracting said second user node and said second sub-channel node from said second graph;

modifying said second user node;

adding a modified second user node and said second sub-channel node to said second graph;

calculating a matching from said modified second user node and said second sub-channel node;

calculating an edge from said matching;

calculating a third graph from said second graph; and

calculating a maximum weight path from said modified second user node to said second sub-channel node within said third graph.

17. The system of claim 16 , wherein said second user node is a calculated from a null user.

18. The system of claim 11 , wherein said allocation unit is to calculate the optimal allocation by allocation of two or more sub-channels to each of one or more of said users, based on admission control requests of said users.

19. The system of claim 11 , wherein said allocation unit is to calculate the optimal allocation by allocation of one or more sub-channels to one or more null users based on said optimization.