Method and apparatus for token distribution

• US 20020178250A1
• Filed: 04/03/2002
• Published: 11/28/2002
• Est. Priority Date: 05/22/2001
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Haartsen, Jacobus C.
• Granted Patent: US 6,965,933 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 12/4015 by scheduling the transmission of messages at the communication node
• CPC Class Codes: H04L 12/417 with deterministic access, e.g. token passing
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: Y10S 370/909 Token ring

Abstract

A method and apparatus for token distribution include providing one or more nodes of a plurality of network nodes with a token machine that includes counters associated with each of other network nodes having a token machine. Each time a token possessing network node implicitly or explicitly passes the token to another network node having a token machine, counter values of each of the counters associated with each node having a token machine are adjusted. When a token is passed, the counter value of the receiving node is adjusted based, at least in part, on an initial token interval value, and counter values associated with other nodes are adjusted toward a threshold value. The decision as to where the token is passed may be based, at least in part, on the value of a counter and/or an assigned counter priority level. The system or method also may include priority slots in which the token is unconditionally passed to a node assigned the priority slot, and an ARQ scheme for acknowledgment of transferred information.

Claims

1. A method of arbitrating access to a shared channel of a token-based network communication system including a number, N, of nodes, wherein a token-possessing one of the N nodes is permitted to transmit on the shared channel, and wherein each of a number, L, of the N nodes includes a number, M, of counters, each of the M counters is associated with a respective one of M nodes of the N nodes, and M≦

L≦

N, the method comprising;

a) in each of the L nodes, assigning a priority level to each of the M counters, wherein the assigned priority level for a respective one of the M counters among all of the L nodes is the same, and at least two of the M counters are assigned a different priority level;

b) assigning a corresponding initial count value to each of the M counters;

c) identifying by the token-possessing one of the N nodes one of a remaining number of other nodes of the N nodes for receiving the token based, at least in part, on at least one of relative count values of the M counters in the token possessing node and the assigned priority levels of the M counters in the token possessing node;

d) explicitly or implicitly transferring the token to the identified node;

e) in each of the L nodes, adjusting the count value of the counters associated with each of the M nodes each time the token is transferred; and

f) repeating steps c) through e).

2. The method according to claim 1, wherein transferring the token comprises implicitly transferring the token when one of the identified nodes receives a data packet.

3. The method according to claim 2, wherein the data packet comprises a header and a data payload section.

4. The method according to claim 1, wherein transferring the token comprises explicitly transferring the token when one of the identified nodes receives a data packet.

5. The method according to claim 4, wherein the data packet comprises a header without a payload.

6. The method according to claim 1, wherein M is less than N.

7. The method according to claim 1, wherein at least one of the N nodes is a communication unit.

8. The method according to claim 1, wherein the transmission of the token starts at a boundary of one of a plurality of sequentially occurring time slots.

9. The method according to claim 8, wherein adjusting the count value of the counters comprises:

in each of the L nodes, adjusting by incrementing or decrementing the count value of the counters associated with each of non identified ones of the M nodes by a fixed amount; and

in each of the L nodes, adjusting the count value of the counters associated with the identified node by an amount based, at least in part, on its initial count value.

10. The method according to claim 8, comprising, prior to step c), the step of assigning to at least one of the N nodes a corresponding priority slot that occurs during at least one slot of the plurality of sequentially occurring time slots.

11. The method according to claim 10, wherein if a current time slot coincides with one of the assigned priority slots, then step c) is bypassed and the token is passed to one of the N nodes assigned the coinciding priority slot.

12. The method according to claim 10, wherein M is less than N.

13. The method according to claim 11, further comprising:

determining whether several of the assigned priority slots overlap during a coinciding current time slot; and

transferring the token to one of the several nodes determined to have the overlapping assigned priority slot and an associated highest priority counter.

14. The method according to claim 10, wherein identifying one of a remaining number of other nodes comprises identifying a highest priority one of the nodes associated with the counters having a value that is equal to or has passed a predetermined threshold value.

15. The method according to claim 10, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes whose associated counter count value is closest to a predetermined threshold value.

16. The method according to claim 10, wherein identifying one of a remaining number of other nodes comprises identifying one of the nodes waiting for transfer of information from the token-possessing node and having a highest priority associated counter of the waiting units.

17. The method according to claim 10, further comprising:

generating acknowledgment information in the identified node in response to receiving the token, wherein the acknowledgment information indicates success or failure of at least part of information transferred with the token.

18. The method according to claim 17, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes associated with a highest priority counter waiting for transfer of the acknowledgment information from the token-possessing node.

19. The method according to claim 1, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes having a highest priority associated counter and count value that is equal to or has passed a predetermined threshold value.

20. The method according to claim 1, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes having an associated count value closest to a predetermined threshold value.

21. The method according to claim 1, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes having one of an associated count value equal to a predetermined threshold value and an associated count value at a greatest distance passed the predetermined threshold value.

22. The method according to claim 1, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes waiting for information transfer from the token-possessing node and having an associated highest priority counter of the waiting units.

23. The method according to claim 1, further comprising:

generating acknowledgment information in the identified node in response to receiving the token, wherein the acknowledgment information indicates success or failure of at least part of information transferred with the token.

24. The method according to claim 23, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes associated with a highest priority counter waiting for transfer of the acknowledgment information from the token-possessing node.

25. The method according to claim 23, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes waiting for information transfer from the token-possessing node and having an associated highest priority counter of the waiting units.

26. The method according to claim 23, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes associated with a counter having a count value closest to a predetermined threshold value.

27. The method according to claim 23, wherein identifying one of a remaining number of other nodes comprises identifying one of the M nodes associated with a highest priority counter whose count value closest to a predetermined threshold value.

28. The method according to claim 1, wherein adjusting the count value of the counters comprises:

in each of the L nodes, adjusting the count value of the counter associated with the identified node by an amount based, at least in part, on the initial count value; and

in each of the L nodes, incrementing or decrementing the count value of the M counters by a fixed amount.

29. The method according to claim 1, wherein step b) further comprises staggering the initial count values between at least two of the counters associated with the M nodes using an offset value.

30. A system for arbitrating access to a shared channel in a token-based communication network, comprising:

a shared channel medium; and

a number, N, of nodes, each of the N nodes capable of communicating with another one of the N nodes along the shared channel medium upon receiving a token, wherein each of a number, L, of the N nodes is associated with a token machine, L≦

N, and wherein each token machine comprises;

a number, M, of counters, wherein;

each of the M counters being associated with a corresponding one of a number, M, of the N nodes, and M≦

L; and

each of the M counters is assigned a priority level such that at least two of the M nodes have a different priority level; and

each of the M counters is associated with a respective initial count value; and

a processor for monitoring and controlling the M counters, wherein the processor is configured to select one of the N nodes to which the token is explicitly or implicitly transferred from a token-possessing another one of the N nodes.

31. The system according to claim 30, wherein the processor comprises logic configured to monitor a count value of each of the M counters and generate an address of one of the M nodes to which the token transferred based on the monitored count values.

32. The system according to claim 30, wherein M less than N.

33. The system according to claim 30, wherein at least one of the N nodes is a communication unit.

34. The system according to claim 31, wherein the logic is further configured to adjust the count value of each of its M counters after the token is passed.

35. The system according to claim 31, wherein the logic is further configured to generate the address based on the priority levels of the M counters.

36. The system according to claim 30, wherein the processor comprises logic configured to transfer the token at the start of a slot boundary of sequentially occurring time slots.

37. The system according to claim 36, wherein each of the processors is configured to adjust a count value of each its M counters during each of the sequentially occurring time slots.

38. The system according to claim 36, wherein at least one of the sequentially occurring slots is a priority slot associated with at least one of the N nodes and the processor logic is further configured to pass the token to a highest assigned priority one of the N nodes assigned a current one of the priority slots.

39. The system according to claim 30, wherein the N nodes are capable of using an ARQ scheme.

40. The system according to claim 30, wherein each controller is capable of adjusting a counter associated the selected node by an amount based, at least in part, on the selected node'"'"'s initial value after the token is passed to the selected node.

41. A method of selecting one of a number, N, of communication devices for receipt of a token in a communication system that transmits during individual ones of a number of sequentially occurring transmission events, the method comprising:

assigning a corresponding priority level to each of the N communication devices, wherein at least two of the N communication devices are assigned different corresponding priority levels;

assigning a corresponding count parameter to each of the communication devices, including an own count parameter;

assigning a corresponding initial count value to each of the communication devices, including an own initial count value;

for each of the communication devices, initializing the corresponding count parameter to the corresponding initial count value;

for each successive transmission event, performing;

adjusting each of the count parameters;

determining whether a token has been received;

performing a first operation in response to determining that the token has been received; and

performing a second operation in response to determining that the token has not been received,

wherein the first operation comprises;

readjusting the own count parameter;

selecting one of the N devices based, at least in part, on the count parameters; and

sending the token to the selected one of the N devices; and

wherein the second operation comprises;

determining which of the N devices now has the token;

readjusting the count parameter of the device that now has the token.