Method for detecting collisions on and controlling access to a transmission channel

• US 5,390,181 A
• Filed: 06/04/1993
• Issued: 02/14/1995
• Est. Priority Date: 06/04/1993
• Status: Expired due to Term

• Current Assignee: Illinois Institute of Technology
• Original Assignee: Illinois Institute of Technology
• Inventors: Campbell, Graham M., Xu, Wenxin
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US08/073,206
• Time in Patent Office: 620 Days
• Field of Search: 370/85.2, 370/85.3, 370/85.1, 370/85.6, 370/110.1, 370/93
• US Class Current: 370/444
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]

Abstract

A method for controlling multiple access of a transmission channel wherein a plurality of different patterns are assigned to a plurality of sending stations so that each sending station corresponds to a unique pattern, preferably a pattern represented by a Binomial coefficient. Each unique pattern is transmitted from a corresponding sending station to the transmission channel by way of a control minislot. Ternary feedback is received from the control minislot. A summation of different patterns within each control minislot are analyzed to detect whether a collision exists between the different patterns within each control minislot.

Claims

1. A method for detecting a collision in a transmission channel, the method comprising the steps of:

(a) assigning a plurality of different patterns to a plurality of stations so that each said station corresponds to a unique pattern of a different Binomial coefficient C(n,k) representing One of a number of ways that k distinct objects can be selected from a set of n elements;

(b) transmitting at least one of said unique patterns to the transmission channel via a control minislot;

c) analyzing a summation of said unique patterns within said control minislot to detect whether a collision exists between said different patterns within said control minislot; and

(d) each said station receiving ternary feedback from said control minislot.

2. A method according to claim 1 wherein n is in a range from 3 to 40, inclusive.

3. A method according to claim 1 wherein n is in a range from 4 to 15, inclusive.

4. A method according to claim 1 wherein n=2k.

5. A method according to claim 1 wherein detecting whether said collision exists further comprises using said ternary feedback to differentiate between an absence of said pattern, a presence of a single said pattern and a presence of a plurality of said patterns within said control minislot.

6. A method according to claim 1 wherein each said unique signal pattern is represented by a unique binary value.

7. A method according to claim 1 wherein upon detection of said collision, data to be transmitted from each said station is prioritized according to a protocol.

8. A method according to claim 7 wherein said protocol functions according to data transmission rules (DTR), request transmission rules (RTR), and queueing discipline rules (QDR).

9. A method according to claim 8 wherein according to said data transmission rules (DTR), if the length of a data transmission queue (TQ) at a time (t) is equal to zero and the length of a collision resolution queue (RQ) at said time (t) is equal to zero, then said [sending]stations having a data message arriving in a current enable transmission interval (ETI) transmit said data message in a data slot of said transmission channel at said time (t).

10. A method according to claim 8 wherein according to said data transmission rules (DTR), if a data transmission queue (TQ) at a time (t) has a length greater than zero, then the one of said stations having the first entry of a message in said data transmission queue (TQ) transmits said message in a data slot of said transmission channel at said time (t).

11. A method according to claim 8 wherein according to said request transmission rules (RTR), if the length of a collision resolution queue (RQ) at a time (t) is equal to zero, then said stations having a message arriving in a current enable transmission interval (ETI) each transmits a request at said time (t).

12. A method according to claim 8 wherein according to said request transmission rules (RTR), if a collision resolution queue (RQ) at a time (t) has a length greater than zero, then said stations having a first entry of a message in said collision resolution queue (RQ) transmit a request at said time (t).

13. A method according to claim 8 wherein according to said queueing discipline rules (QDR), each said station increments the length of a data transmission queue (TQ) by one for each ternary feedback signal of said control minislot indicating a presence of a single said different pattern within said minislot.

14. A method according to claim 8 wherein according to said queueing discipline rules (QDR), each said station decrements the length of a data transmission queue (TQ) by one for a message transmission commencing before a time (t).

15. A method according to claim 8 wherein according to said queueing discipline rules (QDR), if the length of a collision request queue (RQ) at a time (t) is equal to zero, then each said station increments the length of said collision request queue (RQ) by a number n, where said number n is equal to a number of collisions detected within said control minislot.

16. A method according to claim 8 wherein according to said queueing discipline rules (QDR), if a collision request queue (RQ) at a time (t) has a length greater than zero, then each said station increments the length of said collision request queue (RQ) by a number n-1, where said number n-1 is equal to one less than a number of collisions detected within said control minislot.

17. A method according to claim 8 wherein according to said queueing discipline rules (QDR), each said station learns a corresponding position of said station in one of a data transmission queue (TQ) and a collision request queue (RQ) and accordingly adjusts a pointer to one of said data transmission queue (TQ) and said collision request queue (RQ).