Local area network with carrier sense collision avoidance

• US 4,661,902 A
• Filed: 03/21/1985
• Issued: 04/28/1987
• Est. Priority Date: 03/21/1985
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Kenyon, Lawrence A. Jr., Sidhu, Gursharan S., Oppenheimer, Alan B., Hochsprung, Ronald R.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/715,065
• Time in Patent Office: 768 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 370/448
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]

Abstract

A local area network is disclosed including apparatus and methods for transferring data between a plurality of data processing resources ("agents") coupled to a cable. In the preferred embodiment, a plurality of agents are coupled to a common cable for data transmission and reception. An agent newly coupled to the cable dynamically assigns itself a unique address on the cable to which other agents may send data. Once an agent has been assigned a final address, it may then transmit to, and receive data from, other agents on the cable. An agent desiring to send data to a receiving agent follows a three step handshake, wherein the sending agent transmits an "RTS" signal and within a predetermined time must receive a "CTS"signal from the receiving agent. The sending agent then transmits a data frame within a predetermined time after the CTS signal is received. The failure to detect a return CTS signal within the predetermined time denotes a collision condition. Re-transmission is attempted using a linear back off method which is adjusted based on previous cable traffic history.

Claims

1. A communication medium for transferring data between a plurality of data processing devices ("agents") including a sending agent and a receiving agent, comprising:

sensing means coupled to said sending agent for therein if said medium is currently carrying data of another agent and is thereby in use;

timing means coupled to said sending agent for timing a first predetermined waiting period once said medium is idle and available for use;

first random number generating means coupled to said sending agent for generating a random number within a predefined range corresponding to a second waiting period prior to transmittng data on said communication medium to said receiving agent;

first signal generation means coupled to said sending agent for generating a first signal and transmitting said signal to said receiving agent;

signal receiving means coupled to said sending agent for receiving a signal transmitted from said receiving agent to said sending agent within a second predetermined time (IFG) after said sending agent has transmitted said first signal;

data transmission means coupled to said sending agent for transmitting data to said receiving agent within said IFG time after receiving said signal from said receiving agent;

whereby data is transferred between said sending and receiving agents coupled to said communication medium.

2. The communication system as defined by claim 1, further including collision assumption means coupled to said sending agent for producing a collision signal in the absence of the receipt of said signal from said receiving agent by said signal receiving means within said IFG time.

3. The communication system as defined by claim 2, wherein said random number (R) is generated by said random number generating means such that:

space="preserve" listing-type="equation">R=rΛ

L

where;

r=a random number within said predefined range;

Λ

denotes a logical AND operation;

L=a Local variable representative of the collision and deferral history of said sending agent for said data to be sent.

4. The communication system as defined by claim 3, further including a global mask variable G which is representative of the collision and deferral history of said sending agent for all previous data transferred, said variable G being adjusted prior to the initiation of each new data transfer.

5. The communication system as defined by claim 2, wherein said sensing means includes pulse detection means for detecting a synchronization pulse on said communication medium, said synchronization pulse preceeding other signals transmitted by agents coupled to said communication medium.

6. The communication system as defined by claim 5, wherein said synchronization pulse preceeds said other signals by at least 2 bit times.

7. The communication system as defined by claim 5, wherein said first signal comprises an RTS frame including at least one sychronization flag byte having a predefined bit sequence and a type field containing an RTS byte.

8. The communication system as defined by claim 7, wherein said sensing means includes means for sensing said flag byte, the sensing of said flag bytes denoting that said medium is in use.

9. The communication system as defined by claim 8, wherein said signal received from said receiving agent by said receiving means comprises a CTS frame including at least one synchronization flag byte and a type field containing a CTS byte.

10. The communication system as defined by claim 9, wherein said data transmitted by said sending agent is in the form of a data frame including a plurality of data bytes preceded by at least one synchronization flag byte, a destination address and a source address byte.

11. The communication system as defined by claim 10, wherein said data frame further includes a frame check sequence (FCS) and an abort sequence of bits following said plurality of data bytes.

12. The communication system as defined by claim 11, wherein said IFG time is generally 200 microseconds.

13. The communication system as defined by claim 12, wherein said sensing means includes a Z8530 SCC serial communication controller device.

14. The communication system as defined by claim 11, wherein said communication medium comprises a twisted pair cable.

15. The communication system as defined by claim 14, wherein said twisted pair cable is terminated by 100 Ohm resistors.

16. The communication system as defined by claim 11, wherein said data transfers on said communication medium are separated by a third predetermined time (IDG).

17. The communication system as defined by claim 16, wherein said third predetermined time is generally 400 microseconds.

18. The communication system as defined by claim 17, wherein said signals are transmitted on said communication medium using FM-0 encoding.

19. A method for transferring data on a data communication medium between a plurality of data processing devices ("agents"), including a sending agent and a receiving agent, comprising the steps of:

sensing said medium to determine if said medium is currently carrying data of another agent and is thereby in use;

waiting a first predetermined time after sensing that said medium is idle and available for use;

generating a random number within a predefined range corresponding to an additional waiting time prior to transmitting data on said communication medium to said receiving agent;

transmitting a first signal to said receiving agent coupled to said communication medium;

receiving a signal transmitted from said receiving agent to said sending agent within a second predetermined time (IFG) after said sending agent has transmitted said first signal;

transmitting data to said receiving agent within said IFG time after receiving said signal from said receiving agent;

whereby data is transferred between said sending and receiving agents coupled to said communication medium.

20. The method as defined by claim 19, further including the step of producing a collision signal in the absence of the receipt of said signal from said receiving agent within said IFG time.

21. The method as defined by claim 20 wherein said step of generating a random number (R) for said additional waiting time includes the calculation:

space="preserve" listing-type="equation">R=rΛ

L

where;

r=a random number within said predetermined range;

Λ

denotes a logical AND operation;

L=a local variable representative of the collision and deferral history of said sending agent for said data to be sent.

22. The method as defined by claim 21, wherein said random number generating step includes:

a global mask variable G which is representative of the collision and deferral history of said sending agent for all previous data transferred, said variable G being adjusted prior to the initiation of each new data transfer.

23. The method as defined by claim 22, wherein G is comprised of 4 bits and variables C and D are defined wherein C is composed of bits representative of the number of collisions assumed for prior attempts to transmit said data, and D is comprised of bits representative of the number of deferrals for prior attempts to send said data.

24. The method as defined by claim 23, wherein said variable G is adjusted such that if the number of bits in C equal to 1 is greater than 2, then:

(a) the bits comprising G are shifted 1 bit toward the most significant bit (MSB);

(b) set G₀ =1;

(c) set all C bits=0.

25. The method as defined by claim 24, wherein G is adjusted such that if the number of bits set equal to 1 in D is less than 2 then:

(a) the bits of G are shifted one bit toward the least significant bit (LSB);

(b) set G₃ =0;

(c) set D=255.

26. The method as defined by claim 25, wherein in the event said collision signal is generated:

(a) C₀ =1 (LSB of C);

(b) bits comprising L are shifted 1 bit toward MSB;

(c) L₀ =1

(d) N_C =N_C +1,

where N_C = number of collisions for prior attempts to transmit said data.

27. The method as defined by claim 26, wherein in the event of a deferral, D is adjusted such that:

(a) D₀ =1;

(b) L₀ =1;

(c) N_D =N_D +1,

where N_D =number of deferrals for prior attempts to transmit said data.

28. The method for transferring data as defined by claim 20, wherein said sensing step includes detecting a synchronization pulse on said communication medium, said synchronization pulse preceeding other signals transmitted by agents coupled to said bus.

29. The method for transferring data as defined by claim 28, wherein said synchronization pulse preceeds said other signals by at least 2 bit times.

30. The method for transferring data as defined by claim 28, wherein said first signal comprises a RTS frame including at least one synchronization flag byte having a predefined bit sequence and a type field containing an RTS byte.

31. The method for transferring data as defined by claim 30, wherein said sensing step senses said flag byte, the sensing of said flag byte denoting that said medium is in use.

32. The method as defined by claim 31, wherein said signal received from said receiving agent comprises a CTS frame including at least one synchronization flag byte and a type field containing a CTS byte.

33. The method as defined by claim 32, wherein said data transmitted by said sending agent is in the form of a data frame including a plurality of data bytes preceeded by at least one synchronization flag byte, a destination address and a source address byte.

34. The method as defined by claim 33, wherein said data frame further includes a frame check sequence (FCS) and abort sequence of bits following said plurality of data bytes.

35. The method as defined by claim 34, wherein said data IFG time is generally 200 microseconds.

36. The method as defined by claim 35, wherein said data transfers on said communication medium are separated by a third predetermined time (IDG).

37. The method as defined by claim 36, wherein said signals are transmitted on said communication medium using FM-0 encoding.

38. A data processing device coupled to a communications medium having a number of other devices coupled thereto, the devices each responding to an address, the medium for transferring data between the device and one of the other devices wherein the device is addressable by the other devices coupled to the medium in response to a unique self assigned address, the self assigned address determined by the device transmitting a first tentative address on the medium and, if no other device responds, assigning the tentative address as its address, if another device does respond transmitting other tentative addresses until one is not responded to and assigning that tentative address as its address.