System and a method for continuously adjustable, splitting group, multi-contention resolution in multi-access computer communication systems

• US 6,181,687 B1
• Filed: 10/22/1998
• Issued: 01/30/2001
• Est. Priority Date: 10/22/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bisdikian, Chatschik
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US09/176,917
• Time in Patent Office: 831 Days
• Field of Search: 370/347, 370/342, 370/348, 370/319
• US Class Current: 370/347
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 12/40163 by assigning priority to messages according to a message field
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 12/44 Star or tree networks

Abstract

The present invention relates to a communication system where tree-search or stack contention-resolution algorithms in hybrid MAC protocols are used by CaTV stations to resolve message transmission collisions. The stations, which are computer communicating devices, communicate by message transmissions over a communications channel where message contents of some of these transmissions are destroyed by collision of those messages sent from different stations. To resolve message transmission collisions, non-overlapping transmission time intervals of variable durations are generated and grouped into clusters of varying number of time intervals and varying time distances between them. Sequences of clusters are formed in which any station transmitting in a particular cluster will learn of the status of its message transmissions before commencement of the next cluster. Collision resolution is performed collectively on all message transmissions in a cluster and along the successive clusters of the same sequence.

Claims

1. A method of communicating in a multi-access computer communication system comprising a plurality of stations and a first communication channel, wherein said stations communicate using messages transmission over said first communications channel, the method comprising:

generating a plurality non-overlapping transmission time intervals of variable durations;

grouping said time intervals into a plurality of clusters, wherein the number of said time intervals and time distances between them varies within each of said clusters;

forming a plurality of sequences of said clusters, wherein the time distance from the end of one of said clusters comprising each sequence to the beginning of the next of said clusters comprising same sequence is such that any of said stations transmitting in said sequence will learn a status information of said message transmission prior to commencement of next of said clusters; and

sending said message transmission from said stations during said time intervals via said first communication channel.

2. The method of claim 1, wherein said time intervals are of a fixed size.

3. The method of claim 1, wherein said time intervals in each cluster of said sequences are in sets of contiguous time intervals.

4. The method of claim 1, wherein the time distance between the beginnings of successive clusters of said sequences is constant.

5. The method of claim 1, wherein different sequences of clusters are identified by a unique sequence id.

6. The method of claim 1, wherein said first communications channel comprises various interconnected communication media.

7. The method of claim 1, wherein said stations are computer communicating devices.

8. The method of claim 7, wherein said status is determined to be not-successful if following said message transmission in a first cluster of a sequence, contents of said message transmission in a first cluster are destroyed by a collision of said message transmission from said stations, and said stations learn that said contents are destroyed prior to a commencement of a second cluster following a first cluster from a same sequence.

9. The method of claim 8, further comprising steps of:

proceeding iteratively along said clusters of one of said sequences, each iteration exclusively pertaining to all said time intervals in one of said clusters and all said message transmission in said time intervals; and

resolving said collision by retransmitting said message transmission that resulted in said collision according to rules for said message transmission until said message transmission is transmitted collision-free.

10. The method of claim 9, wherein rules for said message transmission comprise:

first message transmission rules to regulate a first message transmission by a newcomer station, where said message transmission is waiting to be sent in one of said time intervals.

11. The method of claim 10, wherein rules for said message transmission further comprise:

subsequent transmission rules to regulate a subsequent transmission of collided messages in the future, in said time intervals relative to the one of said time intervals used for said message transmission that resulted in said collision.

12. The method of claim 11, wherein each said newcomer station selects a time interval, a cluster and a sequence, from said time intervals of said clusters of said sequences to execute said message transmission according to said first message transmission rules, and when said message transmission is destroyed by said collision, said station makes subsequent transmission of each said subsequent transmission destroyed by said collision.

13. The method of claim 12, wherein each said subsequent transmission is transmitted in a subsequent time interval to said time interval during which previous transmission occurred, according to said subsequent transmissions rules.

14. The method of claim 13, wherein said subsequent retransmission rules are such that, if a first message transmitted in a first transmission time interval of a first cluster resulted in said collision, and a second message transmitted in a second transmission time interval of a first cluster resulted in said collision, said first message and said second message will not collide with each other in any future transmissions relative to said first cluster.

15. The method of claim 13, wherein said first transmission rules are applicable selectably to different subsets of said time intervals that said newcomer station uses for said first message transmission, said subsets comprising of a partition of said time intervals, and said first transmission rules are applicable identically to all said time intervals in each of said subsets.

16. The method of claim 13, wherein said first transmission rules are applicable identically to all said time intervals that said newcomer station uses for said first message transmission.

17. The method of claim 13, wherein said message transmissions and message retransmissions within different sequences follow independent rules for said message transmissions and said message retransmissions.

18. The method of claim 13, wherein said stations with a plurality of messages waiting to be transmitted execute a plurality of contention resolution methods in parallel in order to transmit said plurality of messages.

19. The method of claim 18, wherein said stations select one out of said plurality of messages waiting to be transmitted at each message transmission opportunity according to a selection rule.

20. The method of claim 19, wherein said selection rule randomly selects any one of said plurality of messages.

21. The method of claim 19, wherein a same contention resolution method of said plurality of contention resolution methods executed in parallel by said stations allows said stations to transmit, said stations will select a same message awaiting said message retransmissions.

22. The method of claim 13, wherein said first transmission rules are applicable separately to each individual of said time intervals that said newcomer station uses for said first message transmission.

23. The method of claim 22, wherein said first transmission rules are applicable to newcomer clusters, where all said time intervals belong to one cluster of said sequences that are designated for said first message transmission by said newcomer stations, said newcomer stations are waiting to transmit said first message transmission.

24. The method of claim 23, wherein said first transmission rules, restrict the number of stations allowed to transmit among said newcomers, according to an admission rule.

25. The method of claim 24, wherein said admission rule allows only a percentile of said newcomer stations to transmit on said time intervals associated with said newcomer stations, and on said time intervals associated with groups of newcomer stations.

26. The method of claim 24, wherein said admission rule allows newcomer stations to transmit only messages generated within a specified time period, on said time intervals associated with said newcomer stations, and on said time intervals associated with said groups of newcomer stations.

27. The method of claim 24, wherein said admission rule further comprises an admission property, said admission rule allows said first message transmission from said newcomer stations only if said contents of said first message transmission satisfy said admission property.

28. The method of claim 27, wherein said admission property distinguishes said messages according to various collision resolution priorities, where resolution of said collision of said message transmission belonging to a higher priority is attempted prior to resolution of said collision of said message transmission belonging tc a lower priority.

29. The method of claim 27, wherein said stations with message transmissions eligible to be transmitted, randomly select said time intervals and transmit in any of said time intervals associated with said newcomer stations, and said time intervals associated with said groups of newcomer stations.

30. The method of claim 13, wherein for each of a plurality of parent collisions in a parent cluster of a resolution sequence, there is a child group of time intervals for a child transmission in a following cluster of said resolution sequence according to said subsequent transmission rules,

said parent cluster is said cluster during which one of said parent collisions occur, and

said resolution sequence is said sequence where said parent cluster belongs.

31. The method of claim 30, wherein each said child group comprises a variable number of said time intervals.

32. The method of claim 31, wherein each said child group further comprises one or more child subgroup of said time intervals, each said subgroup belonging to different future clusters of said resolution sequence.

33. The method of claim 32, wherein the number of child subgroups in a child group changes dynamically based on message transmissions and message transmission outcomes in a subset of said child subgroups.

34. The method of claim 33, wherein said time intervals of said child group are used for a retransmission of said messages destroyed in one of said parent collisions.

35. The method of claim 33, wherein said subsequent transmission rules are applicable separately to each of said time intervals of said child group.

36. The method of claim 33, wherein said subsequent transmission rules are applicable selectably to subsets of said time intervals of said child group, said subsets comprising a partition of the time intervals of said child group, and said subsequent transmission rules are applicable identically to all said time intervals in each said subset.

37. The method of claim 33, wherein said subsequent transmission rules are applicable identically to all said time intervals of said child group.

38. The method of claim 35, wherein said stations transmit said subsequent transmissions in said child group according to said subsequent transmission rules and according to a probability distribution, said probability distribution allows said stations to randomly transmit in the i-th of said time intervals with probability p_i, i=1, . . . k, where said child group consists of k time intervals and p₁+ . . . +p_k=1.

39. The method of claim 35, wherein, said stations transmit said subsequent transmissions in said child group according to said subsequent transmission rules and according to a probability distribution, said probability distribution allows said stations to transmit in the m-th of said time intervals with probability b_m, m=j, . . . , k, where se-id child group consists of k time intervals, b_j+ . . . +b_k=1, and said station has not selected to transmit in any of the first (j−

1) of said transmission time intervals.

40. The method of claim 35, wherein, said Stations transmit said subsequent transmissions in said child group according to said subsequent transmission rules and according to a set of time periods, said station will transmit in the i-th of said time intervals if said contents of said message transmission was generated during a time period t_i of said set of time periods, where said child group consists of k time intervals, the time periods t_i, i=1, . . . , k, are non-overlapping, t₁+ . . . +t_k=t_p, and t_p represents the time period during which all messages in one of said parent collisions were generated.

41. The method of claim 35, wherein said multi-access computer communication system is a wireless-based digital radio network.

42. The method of claim 35, wherein said multi-access computer communication system is a wireline-based data network.

43. The method of claim 35, wherein said multi-access computer communication system is an infrared-based local area network.

44. The method of claim 35, wherein said multi-access computer communication system is a fiber-optic-based data network.

45. The method of claim 35, further comprising a monitor station and a second communication channel, where said monitor station transmits messages to said stations using said second communication channel, which is not shared for said message transmissions by said stations.

46. The method of claim 45, wherein said second communication channel used for said monitor station transmissions is on a different communications medium than said first communication channel used for the station transmissions.

47. The method of claim 45, wherein said second communications channel comprises various interconnected communication media.

48. The method of claim 45, wherein said stations and said monitor station are connected to different communications media.

49. The method of claim 45, wherein said monitor station determines a start and a duration of said time intervals in said first communication channel, and notifies said stations of said start and said duration of said time intervals through said second communication channel.

50. The method of claim 49, wherein said monitor station determines said start and said duration of said time intervals allocated for a first transmission of new messages and notifies said newcomer stations via invitation messages of said time intervals allocated for a first transmission of new messages.

51. The method of claim 50, wherein said monitor station notifies said stations of said first transmission rules, via said invitation messages and within other messages, said first transmission rules to be used by said stations for said first message transmission.

52. The method of claim 51, wherein said monitor station notifies said stations of portions of said first transmission rules not already known to said stations.

53. The method of claim 52, wherein said monitor station monitors said message transmissions by said stations in each of said time intervals and announces to said stations via feedback messages, whether message transmissions in each of said time intervals resulted in a collision.

54. The method of claim 53, wherein said monitor station determines said time intervals allocated in said child group for said subsequent transmissions and notifies said stations via retransmission allocation messages.

55. The method of claim 54, wherein said monitor station notifies said stations whose most recent message transmission was a collision identified by said collision id, of said subsequent transmission rules, via retransmission allocation messages, or within other messages.

56. The method of claim 54, wherein said monitor station notifies said stations of said subsequent transmission rules via retransmission allocation messages and via other messages, said subsequent transmission rules to be used by said stations for said subsequent transmission if a prior message transmission was destroyed by said collision.

57. The method of claim 56, wherein said monitor station notifies stations of portions of said subsequent transmission rules not known to said stations.

58. The method of claim 57, wherein said monitor station notifies said newcomer stations of said admission rule via said invitation messages and within other messages.

59. The method of claim 58, wherein said monitor station

assigns to each said collision a collision id, according to an assignment rule,

announces said collision id to said stations, via said feedback messages and other messages,

said stations storing said collision id to be utilized in the future for retransmission of said message transmission destroyed in a collision.

60. The method of claim 59, wherein said monitor station determines said time intervals of said child group and then notifies said stations having each of said parent collisions assigned a parent collision id, via (re)transmission allocation, said child group is assigned said parent collision id.

61. The method of claim 60, wherein said assignment rule used by said monitor station is such that each said collision is assigned a unique collision id belonging to a list of unassigned collision ids, where said monitor station

places each assigned collision id in a list of assigned collision ids,

removes a collision id from said list of assigned collision ids and places it back into said list of unassigned collision ids after all messages that collided in a parent collision which was assigned same collision id retransmit at least once.

62. The method of claim 61, wherein said monitor station assigns collision ids to each collision from said list of unassigned collision ids in a monotonic first order, either increasing, or decreasing.

63. The method of claim 62, wherein said monitor station associates said collision ids to said child group for said message retransmission in said parent collision having the same collision id assigned to it, in a monotonic second order among the collision ids in said list of assigned collision ids, said monotonic second order running a direction opposite to said monotonic first order.

64. The method of claim 63, wherein high priority message collisions are assigned collision ids larger than lower priority collisions, when said collision ids are assigned in an increasing order.

65. The method of claim 63, wherein high priority message collisions are assigned collision ids smaller than the low priority message collisions when said collision ids are assigned in a decreasing order.

66. The method of claim 57, wherein said stations perform said message transmission and resolving possible collisions according to following steps:

a. setting a COUNT variable to a value k, where k is a result of a function random{0, 1, . . . , M_f−

1} which denotes the uniformly random selection of contents inside curly braces, M_f is an integer signifying the number of said time intervals in a first cluster encountered by said newcomer station, said time intervals are indexed as 0, 1, . . . , M_f−

1;

b. transmitting in said time interval number COUNT of said cluster;

c. following message transmission in said cluster, notifying all stations of the outcome of said transmission via feedback messages from said monitor station;

d. terminates further transmission attempts of said message transmission if said feedback messages indicate that said message transmission in said time interval number COUNT of said cluster was a non-collision;

e. for stations that transmitted in said time interval number COUNT of said cluster, setting said variable COUNT to COUNT <

−

n*col{COUNT}+random{0, 1, . . . , n−

1}, where col{COUNT} is a number of collisions which occured within time intervals number 0, 1, . . . , COUNT−

1 of said cluster, and a parameter n is a variable integer equal to or larger than 2 whose exact value is known to and is the same for all said stations prior to setting said variable COUNT, if said feedback messages indicates that said message transmission in said time interval number COUNT of said cluster was a collision,

f. for stations that did not transmit in any of said time intervals for which said feedback messages were received, setting said variable COUNT to COUNT <

−

n*col{M_b}+COUNT−

M_b, where said parameter n has the same value as in the step (f) and is known to all said stations prior to setting said variable COUNT, M_b is the number of said time intervals in said cluster, and col{M_b} is said number of collisions which occured during all said time intervals of said cluster, following a receipt of said feedback messages;

g. transmitting in said time interval number COUNT of a following cluster of said sequence if said variable COUNT is less than M_c, and refraining from transmitting in said time interval number COUNT of said following cluster if said variable COUNT is equal or larger than M_c, where M_c is the number of transmission time intervals in said following cluster in said sequence; and

h. setting M_b=M_c and continuing to resolve collisions iteratively from step (c) until said message transmissions are successful.

67. The method of claim 66, wherein said parameters M_f, M_b, M_c, and n are determined and said stations participating in said collision resolution are notified by said monitor station, via retransmission allocation messages.

68. The method of claim 66, wherein said parameter n is a known constant integer larger or equal to 2.

69. The method of claim 57, wherein said stations transmit only to said monitor station sharing a common first communication channel, while receiving transmissions only from said monitor station on a second communication channel.

70. The method of claim 57, wherein each successful message transmission by one of said stations in a first of said time intervals, one or more collision-free message transmissions are scheduled for that station in subsequent time intervals, said time intervals being of variable duration and distance between them, and do not belong to any of said sequences of clusters used exclusively for message transmissions that may experience a collision.

71. The method of claim 70, wherein scheduling of future contention-free message transmissions by stations is done by said monitor station, said monitor station determining a start and a duration of said time intervals for contention-free message transmissions, and notifying said stations of said time intervals where said stations will transmit said future contention-free messages.

72. The method of claim 57, wherein said multi-access computer communication system is a satellite-based data network.

73. The method of claim 57, wherein said multi-access computer communication system is a Cable TV-based data network.

74. The method of claim 57, wherein said multi-access computer communication system is a cellular packet-radio-based network.

75. A method of communicating in a multi-access computer communication system comprising a plurality of stations and a plurality of communication channels, wherein for each one of said plurality of communication channels there exists a subset of said stations, wherein said stations communicate by message transmissions over said one communications channel, the method comprising:

generating a plurality non-overlapping transmission time intervals of variable durations;

grouping said time intervals into a plurality of clusters, wherein the number of said time intervals and time distances between them varies within each of said clusters;

forming a plurality of sequences of said clusters, wherein the time distance from the end of one of said clusters comprising each sequence to the beginning of the next of said clusters comprising that sequence is such that any of said stations transmitting in said sequence will learn a status information of said message transmission prior to commencement of next of said clusters, said status identifying said message transmissions as successful and not-successful; and

sending said message transmissions from said stations during said time intervals via said first communication channel.

76. A method of communicating in a multi-access computer communication system comprising

a plurality of stations,

a monitor station,

a plurality of first communication channels, and

a plurality of second communicating channels,

wherein said first communication channels do not comprise said second communication charnels,

said stations transmit on said first communication channels,

said monitor station transmits to the other stations on said second communication channels,

for each one of said first communication channels and of said second communication channels, there exists a subset of said stations that perform message transmissions on one of said first communication channels, receive from said monitor station on one of said second communication channels, the method comprising:

generating a plurality non-overlapping transmission time intervals of variable durations;

grouping said time intervals into a plurality of clusters, wherein the number of said time intervals and time distances between them varies within each of said clusters

forming a plurality of sequences of said clusters, wherein the time distance from the end of one of said clusters comprising each sequence to the beginning of the next of said clusters comprising that sequence is such that any of said stations transmitting in said sequence will learn a status information of said message transmissions prior to commencement of next of said clusters, said status identifying said message transmissions as successful and not successful; and

sending said message transmissions from said stations during said time intervals via said first communication channel.

77. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing communication in a multi-access computer communication system comprising a plurality of stations and a first communication channel, wherein said stations communicate using message transmission over said first communications channel, the computer readable program code means in said article of Manufacture comprising computer readable program code means for causing a computer to effect:

generating a plurality non-overlapping transmission time intervals of variable durations;

grouping said time intervals into a plurality of clusters, wherein the number of said time intervals and time distances between them varies within each of said clusters;

forming a plurality of sequences of said clusters, wherein the time distance from the end of one of said clusters comprising each sequence to the beginning of the next of said cluster, comprising same sequence is such that any of said stations transmitting in said sequence will learn a status information of said message transmission prior to commencement of next of said clusters; and

sending said message transmission from said stations during said time intervals via said first communication channel.

78. An article of manufacture of claim 77, wherein said stations are computer communicating devices.

79. An article of manufacture of claim 78, wherein said status is determined to be not-successful if following said message transmission in a first cluster of a sequence, contents of said message transmission in a first cluster are destroyed by a collision of said message transmission from said stations, and said stations learn that said contents are destroyed prior to a commencement cf a second cluster following a first cluster from a same sequence.

80. An article of manufacture of claim 79, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect:

proceeding iteratively along said clusters of one of said sequences, each iteration exclusively pertaining to all said time intervals in one of said clusters and all said message transmission in said time intervals; and

resolving said collision by retransmitting said message transmission that resulted in said collision according to rules for said message transmission until said message transmission is transmitted collision-free.

81. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing communication in a multi-access computer communication system comprising a plurality of stations and a plurality of communication channels, wherein for each one of said plurality of communication channels there exists a subset of said stations, wherein said stations communicate by message transmissions over said one communications channel, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

generating a plurality non-overlapping transmission time intervals of variable durations;

grouping said time intervals into a plurality of clusters, wherein the number of said time intervals and time distances between them varies within each of said clusters;

forming a plurality of sequences of said clusters, wherein the time distance from the end of one of said clusters comprising each sequence to the beginning of the next of said clusters comprising that sequence is such that any of said stations transmitting in said sequence will learn a status information of said message transmission prior to commencement of next of said clusters, said status identifying said message transmissions as successful and not-successful; and

sending said message transmissions from said stations during said time intervals via said first communication channel.

82. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for communicating in a multi-access computer communication system comprising

a plurality of stations,

a monitor station,

a plurality of first communication channels, and

a plurality of second communicating channels,

wherein said first communication channels do not comprise said second communication channels,

said stations transmit on said first communication channels,

said monitor station transmits to the other stations on said second communication channels,

for each one of said first communication channels and of said second communication channels, there exists a subset of said stations that perform message transmissions on one of said first communication channels, receive from said monitor station on one of said second communication channels, said method steps comprising:

generating a plurality non-overlapping transmission time intervals of variable durations;

grouping said time intervals into a plurality of clusters, wherein the number of said time intervals and time distances between them varies within each of said clusters

forming a plurality of sequences of said clusters, wherein the time distance from the end of one of said clusters comprising each sequence to the beginning of the next of said clusters comprising that sequence is such that any of said stations transmitting in said sequence will learn a status information of said message transmissions prior to commencement of next of said clusters, said status identifying said message transmissions as successful and not successful; and

sending said message transmissions from said stations during said time intervals via said first communication channel.