Lossless arbitration scheme and network architecture for collision based network protocols

[0002] 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.

[0003] 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.

[0004] 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.

[0005] 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.

[0006] 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.

[0007] 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.

[0008] 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.

[0009] 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.

[0010] 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.

[0011] 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.

[0012] 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.

[0013] 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.

[0014] 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.

[0015] FIG. 1A is a block diagram of a lossless network according to one embodiment of the invention.

[0016] FIG. 1B is a block diagram of a lossless network with common receive and access control links according to another embodiment of the invention.

[0017] FIG. 2A is a block diagram of two lossless networks connected together by an IEEE 802.3 compliant full-duplex link according to another aspect of the invention.

[0018] FIG. 2B is a block diagram of one lossless network connected to a single remote device by an IEEE 802.3 compliant full-duplex link according to yet another aspect of the invention.

[0019] FIG. 3 is a detailed diagram for one embodiment of the lossless network.

[0020] FIG. 4 is a detailed diagram showing connections between a hub and a medium access controller for the lossless network.

[0021] FIG. 5 is a flow diagram describing a lossless arbitration protocol for the lossless network.

[0022] FIG. 6 is block diagram of a system for processing telephone signals according to yet another embodiment of the invention.

[0023] Referring to FIGS. 1A and 1B, a lossless network 1 according to the invention includes multiple devices 5 coupled to a hub 4 which contains an arbiter. Each device 5 is connected to the hub 4 through a private transmit link 7 and either a private receive link 10 and access control link 9, FIG. 1A, or a shared receive link 10 and access control link 9, FIG. 1B. The receive link 10, along with the transmit links 7, are used to send packets between devices 5. The access control signals 9 are required for the lossless arbitration. The devices 5 comprise systems, such as processing devices, storage devices, etc., that exchange information over the network.

[0024] With the exception of the out of band signals on access control link 9, the lossless network 1 in FIG. 1A appears like a standard CSMA/CD LAN, such as IEEE 802.3, that provides communication between devices 5. However, the lossless network 1 does not suffer bandwidth loss due to collisions, never experiences excessive collisions, and has greater short term access predictability than a standard CSMA/CD LAN.

[0025] The hub 4 uses a fixed priority scheme to determine which one of the devices 5 is allowed to continue to transmit when a collision occurs. The hub 4 drives the access control signals 9 that control the collision signals (CLSN) that notify the MAC 22 (FIG. 3) on each device 5 when a collision has occurred and that control the carrier sense signals (CRS) that the MAC on each device 5 uses to decide when to transmit.

[0026] The CLSN signal is not asserted to the device 5 winning the arbitration. Thus, the winning device 5 keeps transmitting. All other colliding devices 5 of lower priority are notified of the collision via the CLSN signal asserted through the access control signals 9. The losing devices 5 back off from transmitting for either zero or one slot times The CRS signal is then used by the hub 4 to control when each of the colliding devices 5 of lower priority are allowed to retransmit.

[0027] FIG. 2A shows two lossless networks 1A and 1B in combination with an IEEE 802.3 compatible full-duplex link 3 that allows two groups of devices 5A and 5B whose physical separation is greater than that allowed by the IEEE 802.3 protocol to be interconnected without a switch or buffering. A second MAC (FIG. 3) is added to devices in each group to receive transmissions from devices in the other group.

[0028] FIG. 2B shows another embodiment of the invention in which one of the groups is degenerate and contains a single device 2. When a group consists of a single device 2, the MAC on the device can be connected directly to the full-duplex link 3 through a PHY 6.

[0029] In a third embodiment of the invention, each device 5 in FIGS. 2A and 2B contains a single MAC 22. Each device transmits to the hub through a transmit link 7, receives access control signals 9 from the hub and receives data from the remote network or device through remote receive link 8. There is no receive link 10 in this embodiment. Devices attached to one hub can communicate with devices connected to the other hub, but cannot communicate with devices connected to their hub.

[0030] The lossless network 1 allows aggregation of multiple devices 5 on one ell(I or both ends of the full-duplex IEEE 802.3 point-to-point link 3. The devices 5 are aggregated without having to use complex full-duplex switching circuitry or buffering. Due to the lossless arbitration scheme described in further detail below, the lossless network 1 also has increased usable bandwidth and is more predictable than existing CSMA/CD network protocols.

[0031] Roundtrip time is defined as the time from when any one of devices 5 begins to transmit to the time that a collision indication is received back from the hub 4. The lossless network 1 is spatially confined such that the roundtrip time is less than the time required for the device to complete transmitting a minimum sized packet. Thus, the devices 5 will not lose packets from delayed receipt of the collision signal. Because the lossless LAN is spatially constrained, the hub 4 is not required to buffer packets.

[0032] FIG. 3 is a detailed diagram for one embodiment of the lossless network 1. Two independently operating CSMA/CD Media Access Controllers (MACs) 20 and 22 are shown in each device 5. The MAC 20 is refer-red to as a receive MAC (RX MAC) and the MAC 22 is refer-ed to as a transmit MAC (TX MAC). The receive MACs 20 can be excluded from each device when the lossless network 1 is not coupled to an external full-duplex link 3 or when receive link 10 is not implemented. The RX MAC 20 in each device 5 is coupled through the remote receive link 8 to full-duplex link 3. The TX MAC 22 in each device 5 is coupled through one of the transmit links 7 to the hub 4. The transmit links 7 are arranged in a star wired connection that separately connect each one of the TX MACs 22 to the hub 4. The star wired connections 7 allow every TX MAC 22 to transmit packets without corrupting packets transmitted by the other TX MACs 22. Thus, collisions do not result in corrupted packets and a faulty TX MAC on one device does not corrupt packets transmitted by TX MACs on other devices.

[0033] When packets are transmitted between devices 5 within the same lossless network 1, the TX MACs 22 transmit packets to the hub 4 over transmit links 7. The hub 4 then passes the packets back through the receive link 10 to a receive poll on each TX MAC 22. The packets on receive link 10 are received by all the TX MACs 22 but only the device 5 with the corresponding packet address processes the packet.

[0034] The systems shown in FIGS. 2A and 2B can transmit packets to devices outside lossless network 1. The hub 4 passes packets from the TX MAC 22 through PHY 6 and the lull-duplex link 3 to a remote network or device. In one embodiment, the remote network connected to the opposite end of the full-duplex link 3 comprises another lossless network 1 (FIG. 2A). Alternatively, the remote network is a single device 2 (FIG. 2B).

[0035] For packets received from the remote device 2, or from a second group of devices in another lossless network, packets are received from full-duplex link 3. Packets pass from PHY 6 over the remote receive link 8 to one of the RX MACs 20. The RX MACs 20 are dedicated to only receiving packets and transfer the packets to additional device Circuitry (not show). For example, the packets may be passed over a PCI bus 18 to a CPU DRAM (not shown). Because the RX MACs 20 only receive packets, there are no collisions on the remote receive link 8. Thus, any number of devices 5 can be connected to remote receive link 8 without using a arbiter.

[0036] The access control signals 9 are coupled to logic 24 in each device 5. The logic 24 uses the access control signals 9 to control the CLSN and CRS signals on each TX MAC 22. In an alternative embodiment, all of the TX MACs 22 are coupled to the same transmit link 7. A tri-state buffer (not shown) is coupled between each TX MAC 22 and the common transmit link 7. The logic 24 enables the tri-state buffer according to the access control signals 9. In another embodiment of the invention, instead of using common access control signals 9, common receive link 10 and local logic 24 in each device, separate CLSN and CRS lines and receive links 10 are coupled from the hub 4 directly to each TX MAC 22 (FIG. 1A).

[0037] FIG. 4 is a detailed diagram showing MII interconnections between one of the TX MACs 22 and the hub/arbiter 4. Media Independent Interface (MII) is defined in IEEE 802.3u for 100 megabits/second IEEE 802.3 LANs. The MII interconnections include a transmit enable signal TX_EN and transmit data signals TXD sent on the transmit link 7 to the hub 4. Out of band access control signals are sent back from the hub 4 through the logic 24 to the TX MAC 22. The receive link 10 includes a receive data valid signal RX_DV and receive data signals RXD. The hub 4 includes a multiplexer (MUX) 28 having inputs separately coupled to each one of the TX MACs 22 by the transmit links 7 and an output coupled to both the PHY 6 and the receive link 10. The arbiter 17 uses a priority, that may be fixed, and a collision list 26 to determine which input of MUX 28 is enabled.

[0038] Out of Band Signaling

[0039] A novel out of band signaling protocol is used to prevent repeated collisions. The TX MACs 22 assert the TX_EN signal when transmitting valid packets via the TXD signals on their respective transmit link 7. The arbiter 17 checks the priorities when the TX_EN signal is asserted by multiple devices 5. The device 5 with the highest priority is allowed to continue to transmit packets through MUX 28 to the PHY 6 and to receive link 10. The arbiter 17 allows the highest priority device to continue transmitting by not asserting the CLSN signal to that one device 5. The arbiter 17 essentially hides the collision from the one device 5.

[0040] The CLSN/CRS logic 24 assets the CLSN signals to the losing devices 5 according to the access control signals 9. The colliding devices 5, other than the device with highest priority, then back off from transmitting. The logic 24 also activates the CRS signals on all devices 5 indicating another device is currently transmitting. The devices 5 that back off will not try to retransmit while the CRS signal is asserted. In a standard IEEE 802.3 protocol, the CRS signal is deasserted on every device when the LAN becomes idle. This opens up the possibility of multiple devices recolliding. However, the arbiter 17 in the current invention uses the CRS signal to pr-event the devices 5 from going into repeated back off states due to collisions. Controlling individual CLSN and CRS signals for each device 5 out of band allows the arbiter 17 to force the CSMA/CD devices to transmit in a sequential prioritized order.

[0041] Lossless Arbitration Scheme

[0042] Referring to FIG. 5, the lossless arbitration scheme is described in further detail. The priority for the devices can be fixed in any order depending on the importance of the device in quickly completing packet transmissions or it can be variable. For explanation purposes, the lossless arbitration scheme will be described with the first device#1 having highest priority, the second device#2 having second highest priority, and so on. It will also be assumed that device#l through device#3 all attempt to transmit at about the same time.

[0043] The hub 4 receives transmit signals from each device 5 over the transmit links 7 in step 28. If there are no collisions detected in decision step 32, the transmitting device is allowed to transmit data through hub 4 back through receive link 10 and, if applicable, to the full-duplex link 3. If a collision is detected between two or more devices 5, the arbiter 17 allows the highest priority device to keep transmitting in step 34 by hiding the collision from device#1. The hub 4 signals a collision to all the other colliding devices by causing the assertion of their CLSN signals. The arbiter 17 in step 36 keeps a collision list 26 of the devices that collided and were forced to back off.

[0044] If all the devices 5 were on a conventional collision-based LAN, any collision would cause all transmitting devices to back off. Because each device 5 in the network 1 has a separate transmit link 7 to the hub 4, there is no chance that another device 5 will corrupt the data sent by device#1. Thus, the lossless network 1 saves bandwidth in yet another manner by allowing device#1 to continue to transmit without first going through any back off cycle.

[0045] When device#1 finishes transmitting as indicated by an end of frame in decision step 37, the arbiter 17 deasserts the carrier sense signal to the device in the collision list with the next highest priority (e.g., device#2) but keeps asserting the carrier sense signal to all tile other devices 5, including device#1. The CRS signal is deasserted for device#2 in step 38. The devices 5 will not retransmit while the CRS signal is asserted. Thus, all devices, other than device#2, are prevented from transmitting and as a result no collision will occur.

[0046] After receiving the CLSN signal, device#2 backs off either zero or one slot times. When the back off is zero slot times, device#2 completes the back off well before device#1 completes transmitting. When device#2 backs off one slot time, the back off time is longer but still within the time required for device# 1 to transmit one minimum size packet. Specifically, one slot time is equivalent to transmitting 64 bytes of data and the minimum packet is 64 bytes. Thus, device#2 is usually ready to transmit as soon as device#1 completes transmitting.

[0047] If device#2 does not respond after being enabled to transmit (deassertion of CRS), the CRS signal is reasserted to device#2 and the device 5 with the next highest priority is allowed to transmit by deasserting the CRS signal to clevice#3.

[0048] Decision step 42 moves sequentially down the collision list, deasserting the CRS signal one by one from each colliding device 5. After completion of a transmission, the priorities in the collision list are updated in step 44. Devices, other than the original 3 colliding devices, will not be able to transient until the arbiter 17 processes all devices in the collision list. When the last device 5 in the collision list has completed transmitting as indicated by an end of frame in decision step 43, the arbiter 17 deasserts the CRS signal to all the devices 5 in network 1 in step 40 and returns to step 28. Transmission is then reopened to any device 5 and, if necessary, a new collision list is created.

[0049] The devices 5 will never collide more than once for each packet the device transmits. Even when there is a collision, one device 5 is allowed to continue to transmit. Once there is a collision, the devices are forced to transmit in an ordered priority. As a result, there are no lost bus cycles due to repeated back offs from collisions. Further, the arbitration scheme is more predictable than standard CSMA/CD protocols. Because the lossless network looks to attached devices 5 as a conventional CSMA/CD LAN, standard communication circuitry such as IEEE 802.3 compliant MACS can be used in the devices 5.

[0050] Another embodiment of the invention is shown to FIG. 6. A full-duplex IEEE 802.3 point-to-point link 3 is used to pass digital packets between a router 50 and devices in a lossless network 52. Data is transmitted from a telephone company central office (not shown) over telephone lines 53 which are typically cT1 lines or cT3 lines. Data is transmitted on the telephone lines 53 either as ISDN signals or digitized analog modem signals.

[0051] The lossless network 52 has one of more trunk cards 54 coupled to the telephone lines 53. The trunk cards 54 are coupled to modem cards 56 over a Time Division Multiplexed (TDM) bus 58. The trunk cards 54 and modem cards 56 are each separately coupled to the hub 4 on an interface card 59 by transmit links 7. A receive link 10 is coupled between the output of hub 4 and MACs in each modem card 56 and trunk card 54. A remote receive link 8 is coupled between the interface 59 and each modem card 56 and trunk card 54.

[0052] Packets sent over the transmit links 7 to hub 4 can be transmitted back to any one of the modem cards 56 or trunk cards 54 through the receive link 10. Packets sent to router 50 are transmitted by one of the modem cards 56 of trunk cards 54 over the transmit link 7 and through hub 4 to full-duplex link 3. Packets transmitted from router 50 over full-duplex link 3 are received by the modem cards 56 and trunk cards 54 over remote receive link 8.

[0053] The trunk card circuitry, modem card circuitry, and other interface circuitry, other than the new lossless network architecture, is known to those skilled in the art and is therefore not described in further detail.

[0054] For redundancy purposes, a second interface card 60 is incorporated into the lossless network 52. The second interface card 60 is coupled to the router 50 by a separate full-duplex link 64 or coupled to a second router 62 by the full-duplex link 64. The second interface card 60 includes a separate hub (not shown) coupled to the same transmit links 7 coupled to interface card 59. A second receive link 10 is coupled between the hub in interface card 60 and each modem card 56 and trunk card 54. A second remote receive link 8 arc coupled between the interface card 60 and each modem card 56 and trunk card 54.

[0055] Incorporating the lossless network architecture 52 allows aggregation of multiple modern cards 56 and trunk cards 54 using only the simple hub 4 and standard 802.3 compliant communication circuitry.

[0056] Having described and illustrated the principles ol the invention in a preferred embodiment thereof, it should be apparent that the invention can be modified in arrangement and detail without departing from such principles. I claim all modifications and variation coning within the spirit and scope of the following claims.