Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1997-12-30
2001-01-30
Patel, Ajit (Department: 2732)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S448000
Reexamination Certificate
active
06181708
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a network architecture that provides improved aggregation of multiple network devices and a lossless arbitration scheme for Carrier Sense Multiple Access/Collision Detect (CSMA/CD) based Local Area Network (LAN) protocols that has increased bandwidth along with predictable network access.
A device wanting to transmit on a CSMA/CD LAN, such as Institute of Electrical and Electronic Engineers (IEEE) 802.3, first listens to the medium. If the medium is idle, the device begins transmitting immediately. If the medium is not idle, the device waits until the medium becomes idle and remains idle for a defined period of time before beginning transmission. If two or more devices begin transmitting at about the same time, their transmissions collide. The collision is detected and all colliding devices terminate their transmission and wait a random period of time (back off) before attempting to transmit again. Devices attempt repeatedly to transmit each packet until they are either successful or they collide a specified number of times in which case they discard the packet.
The range of times from which the back off time is randomly selected increases after each collision. For example, after a first collision, a device waits either zero or one slot times (an interval of time defined in the 802.3 protocol). After a second collision, the device waits anywhere between zero to three slot times, and so on, up to 1023 slot times.
The protocol has several disadvantages. Bandwidth is wasted each time transmissions collide. Transmission is unreliable as packets that experience an excessive number of collisions ale discarded. Access to the medium can also be quite unfair over short periods of time. Short term access unfairness is the result of the back off algorithm. When the demand for use of the LAN is high and two or more devices collide, the first of the colliding devices to successfully transmit on the medium has an advantage over the other devices in the collision group as the range of times from which the back off time is randomly selected is reset to the minimum each time a device successfully transmits on the medium.
The physical extent of a CSMA/CD LAN is limited by the minimum transmission duration to send a packet. Collisions result in shorter than normal duration transmissions which are called transmission fragments. Transmission fragments are recognized and rejected based on their short duration. The physical extent of a CSMA/CD LAN is limited by the requirement that the propagation delay between any two devices attached to the LAN must be somewhat less than half of the minimum transmission time for a packet.
Connecting devices whose electrical separation is greater than that allowed by a CSMA/CD LAN requires switching and buffering. Such devices are connected to different LANs and the LANs are interconnected with switches which provide the necessary buffering. The switch and packet buffering is complex and expensive to implement.
Accordingly, a need remains for a network architecture and arbitration scheme for CSMA/CD LAN protocols that does not waste bandwidth, is more reliable, provides predictable access and allows devices with greater physical separation to be connected to the same LAN.
SUMMARY OF THE INVENTION
IEEE 802.3 compliant Media Access Controllers (MACs) are combined with a centralized repeater (commonly called a hub) with arbitration and out of band signaling to achieve a lossless LAN that looks like an IEEE 802.3 LAN to attached devices, but has no bandwidth loss due to collisions, no discarded packets due to excessive collisions, predictable access and no short term unfairness.
The lossless network according to the invention includes a hub having multiple inputs that are coupled to individual devices by separate transmit links and outputs that are coupled to the individual devices by either a common or separate receive links. An arbiter controls the hub and forces colliding devices to transmit in a prioritized sequential order. Repeated back offs are eliminated because devices are prevented from colliding more than one time for each packet that the device transmits.
After a collision on a CSMA/CD LAN, a collision signal is asserted to the MACs causing all transmitting devices to back off for 0 to N slot times where N is 1 for the first collision. After they back off, the colliding devices retransmit only when their carrier sense signal is deasserted. The arbiter in the present invention uses out of band signaling to individually control a collision indication signal and a carrier sense signal to each device. The collision indication signal is hidden to the colliding device with the highest priority. Thus, that one device is allowed to continue to transmit. However, the collision indication signal is asserted to other colliding devices causing the other devices to back off. The devices forced to back off will not retransmit until their carrier sense signal is deasserted via the out of band signaling. All devices that are not pall of collision group also have their carrier sense signal asserted. After a device finishes transmitting, its carrier sense signal remains asserted so it does not try to transmit again.
The arbiter deasserts the carrier sense signal to the remaining colliding devices one at a time according to a priority scheme. When the carrier sense signal is deasserted to a device, that device retransmits without the possibility of colliding with other devices. Thus, the devices are allowed to transmit in a fairer and predictable manner. Usable bus bandwidth is also increased because collisions do not cause all devices to stop transmitting.
Two of the lossless networks according to another embodiment of the invention are combined with a full-duplex 802.3 link, two additional IEEE 802.3 receive links and a second MAC on each device to form a network interconnecting two groups of devices in which the physical extent of each group, but not the physical separation of the groups, is limited by the CSMA/CD protocol. The resulting network has the lossless and fairness properties of the lossless networks. And because of the unique architecture, switching and buffering are not required.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention which proceeds with reference to the accompanying drawings.
REFERENCES:
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 4769811 (1988-09-01), Eckberg, Jr. et al.
patent: 5381413 (1995-01-01), Tobagi et al.
patent: 5430726 (1995-07-01), Moorwood et al.
patent: 5912895 (1999-06-01), Terry et al.
patent: 5940399 (1999-08-01), Weizman
patent: 5978383 (1999-11-01), Molle
Chan Roland G.
Chin Hon Wah
Quackenbush William L.
Cisco Technology Inc.
Marger & Johnson & McCollom, P.C.
Nguyen Brian
Patel Ajit
LandOfFree
Lossless arbitration scheme and network architecture for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lossless arbitration scheme and network architecture for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lossless arbitration scheme and network architecture for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2437448