US 5,229,993 AGrant
Control of Access Through Local Carrier Sensing for High Data Rate Networks and Control of Access of Synchronous Messages Through Circulating Reservation Packets
Issue Date:1993-07-20
•12 Claims
•6 Drawing Sheets
Abstract
A combination of two new access methods for ring and unidirectional bus networks supports high data rate integrated traffic. The first access method provides access for asynchronous traffic. When a node senses the channel idle, it can begin to transmit. When it senses an incoming signal, it must stop transmitting in order to avoid a collision. But unlike other access protocols which abort the transmission when a collision occurs or is imminent, the process truncates the message in a fashion such that it can be resumed later when the channel again is idle. The system is called Carrier Sensed Multiple Access-Ring Network (CSMA/RN). The second access method provides support for synchronous traffic. This method implements one or more circulating reservation packets which permit a node to have reserved space when the special packet returns. The media access system is called Circulating Reservation Packet (CRP) system. Both access protocols operate simultaneously on the network with minimal interference. The CRP system is preferably used with the CSMA/RN protocol but is applicable to other fixed length, non-corrupting, circulating network structures to enable the nodes in a network to reserve space for synchronous traffic and guaranteed access.
Metadata
Assignees
- Old Dominion University
- Center for Innovative Technology
Inventors
- Edwin Foudriat
- Kurt Maly
- C. M. Overstreet
- Frank Paterra
- Sanjay Khanna
Application Information
Application Number:US 6606644
Filing Date:1991-02-25
Priority Date:1991-02-25
Art Unit:263
Classifications
IPC:
H04J 326
Field of Search:
37034061;85.2;85.3;85.4;85.5;85.15;94.1;94.2825.05
Patent Drawings (6 sheets)
Description
Background of the Invention
1. Field of the Invention
The present invention generally relates to computer communication networks and, more particularly, to a new concepts for controlling access to high data rate ring or unidirectional bus networks. More specifically, the invention is directed to high data rate networks capable of supporting a variety of traffic types, including voice, video and computer data transferred both asynchronously and synchronously with varying bandwidths.
2. Description of the Prior Art
Communication networks have made possible distributed processing between all classes of computers from super computers to personal computers, promoting greater efficiency and productivity. Both baseband and broadband networks have been developed. Various topologies including star, ring and bus based networks have been implemented. Access control to the networks is required to permit a node to transmit its information on to the network without interfering with or corrupting information traveling on the network.
In a parallel development, multi-media systems are gaining increasing adherents. Such systems support high-quality images, audio, animation and full-motion video. Voice annotations added to business presentations and free-form database queries made through a graphic user interface (GUI) are among the many and diverse advantages of multimedia systems. To support multi-media systems, high data rate networks are required for all types of traffic including voice, video and computer data. Voice and video are referred to as synchronous traffic since new data to transmit occurs at a prescribed rate. Computer data is called asynchronous since its time and rate of occurrence are irregular. Synchronous traffic demands a different quality of service than asynchronous traffic because it requires guaranteed access of the network for fixed blocks at a fixed rate.
Mechanisms proposed for supporting integrated traffic within the access protocol can be divided into two basic categories. The first attempts to provide a mechanism within the framework of the access protocol to support synchronous and asynchronous traffic. This usually results in some type of priority or control system which regulates normal access so that all synchronous traffic can be submitted within a limited time scope and repeated periodically. A second type of support for integrated traffic uses two media access mechanisms in a single network. In this class, uniframe techniques have been used almost exclusively to provide for the synchronous traffic. Uniframe is based upon the 125 microsecond (.mu.sec) telephone virtual circuit frame and supplies a fixed number of 8-bit slots. Each slot is reserved for a synchronous call circuit or a video circuit. Asynchronous traffic uses either the empty slots or is provided a space after one uniframe frame has completed and before the next one begins.
More than sixty different media access protocols for networks operating in the range of 50 to 5000 Mbps have been reported by M. Skov in "Implementation of Physical and Media Access Protocols for High Speed Networks", IEEE Communications Magazine, June 1989, pp. 45-53. At 100 Mbps and above, most networks use fiber optical media because of the signal attenuation advantage and the higher data rate capability. Because of the inability to construct low loss taps other than star couplers, fiber optical networks are usually point-to-point. In many cases, this results in networks that are either rings or unidirectional buses with each node containing at least one transmitter and receiver with each node forwarding messages, either those received from other nodes on the network or generated at the node, to the succeeding or a down stream node.
Many of these network systems use demand assignment access protocol. Implementation of the protocol concept can take many forms including token ring, like the Fiber Distributed Data Interface (FDDI), where a node must capture the token before it is allowed to send its messages; slotted ring, such as the Cambridge Ring, where slots are tested for empty or full status; "attempt and defer", as implemented, for example, by Metrocore, where a node starts transmitting while the slot is being tested and aborts if the slot is full; polled access; or a slotted reservation system, such as Distributed Queue, Dual Bus (DQDB), where the need for free slots are sent to the upstream nodes in an effort to maintain fair access for all nodes. One feature of all demand assignment access protocols is that they are contention or collision free; that is, it is known at the time which they start transmitting a queued message that they will not interfere with messages on the network for the period which they are transmitting. For example, in a slotted system, this would be the time period of a slot. Operations for these and related systems are discussed by M. Skov, supra, and other papers including the Cambridge Ring described by M. Zafirovic-Vukotic, I. G. Niemegeers and D. S. Valk in "Performance Analysis of Slotted Ring Protocols in HSLANs", Jour. on Selected Areas in Communications, vol. 6, no. 6, July 1988, pp. 1011-1023; Expressnet and Fastnet described by F. A. Tobaji and M. Fine in "Performance of Unidirectional Broadcast Local Area Networks Expressnet and Fastnet", IEEE Jour. on Selected Areas in Communications, vol. SAC-1, no. 5, Nov. 1983, pp. 913-925; and DQDB (formerly QPSX) described by R. M. Newman, Z. L. Budrikis and J. L. Hullett in "The QPSX Man", IEEE Communications Magazine, vol. 26, no. 4, April 1988, pp. 20-28.
One form of a demand assignment access protocol, the register-insertion system, described by W. Hilal and M. T. Liu in "Analysis and Simulation of the Registration-Insertion Protocol", Proc. of Computer Networking Symposium, Dec. 10, 1982, pp. 91-100, and M. T. Liu, W. Hilal and B. H. Groomes in "Performance Evaluation of Channel Access Protocols for Local Computer Networks", Proc. Computer Networks, Compcon '82, Sept. 2-23, 1983, pp. 417-426, uses a buffer to assist in controlling access. When a node wishes to transmit, it inserts its empty buffer in the incoming stream link so that any incoming message may be saved until it completes transmission of its queued message. It then empties the buffer, forwarding the delayed message. It must have an empty buffer before it can start the transmission process. Buffer size can limit the size of the messages.
In slotted systems, long messages must be broken into slot size proportions contributing to fracture of the message and wasted network capacity, since the slot size selected is always a compromise over the wide range of message traffic size. In addition, slotting or polling causes delay even at low loads because a queued message must wait until the head of a slot or the cessation of the polling before it can start transmitting. The register insertion method can slow travel for messages on the network. Even though demand assignment access protocols provide full utilization at capacity loads, recent studies indicate that reservation systems have fairness difficulties when servicing nodes at the ends of the bus under high load conditions. See K. Maly, L. Zhang and D. Game, "Fairness Problems in High-Speed Networks", Old Dominion University, Computer Science Dept., TR-90-15, Mar. 1990. Other demand access systems may use a token, like FDDI, but waiting for the token to rotate can cause increased access delay, especially in longer length and higher data rate networks. See F. Ross, "FDDI--A Tutorial", IEEE Transactions on Communications, vol. 24, no. 5, May 1986, pp. 10-17, and the draft of the proposed American National Standard entitled "FDDI Token Ring Media Access Control (mac)", asc .times.3t9.5 rev. 10, Feb 28, 1986. Most demand assignment systems can be considered to operate under "attempt and defer" conditions although register-insertion has an "attempt and hold" mode as well.
The adaptive assignment or random access protocols use a somewhat different form of access from contention free protocols. These systems, like contention free protocols, sense the presence or absence of a message on the network. If the network is free, the node can begin to transmit. However, sensing a free network does not assure collision free access for the period of time necessary to transmit the message. If a collision occurs, the information on the network is corrupted. The nodes which have transmitted messages must be able to detect the fact that a collision has occurred and retransmit their messages when the network is again idle. These systems are generally classified as Carrier Sensed Multiple Access (CSMA). Ethernet, a shared channel system, is designed to detect collisions (CD) shortly after they have occurred, allowing the conflicting nodes to quickly abort transmissions and bring the network to idle sooner, thereby reducing wasted capacity. As bandwidth increases, a message spans a smaller portion of the global bus length so network collisions can still reduce throughput significantly, especially at higher loads when collisions are more likely. See W. Bux, "Local Area Subnetworks: A Performance Comparison", IEEE Trans. on Communications, vol. Com-29, no. 10, Oct. 1981, pp. 91-100. The adaptive or random assignment access systems can be considered to be in the class of "attempt and abort".
Some systems avoid collisions by providing a delay line, as described by T. Suda et al. in "Tree LANs with Collision Avoidance: Protocol, Switch Architecture and Simulated Performance", ACM 089791-279-9/88/008/0155, or a buffer, like the register-insertion systems described by Hilal et al. and Liu et al., supra, for alleviating the corruption of data because of simultaneous access. The tree LAN system described by T. Suda et al., supra, uses the concept whereby a node in the tree can switch to one of a number of simultaneous incoming messages and thereby avoid a collision. The unselected messages are aborted, so this system is in the class of "attempt and abort". The messages which are aborted must be retransmitted to the node at a later time.
Systems which use adaptive or random assignment at high data rates usually incorporate a second collision free protocol which is used at high loads to eliminate the capacity reductions due to collisions. Such systems are classified as hybrid systems. For example, systems exist which use CSMA protocol at low loads but switch to a conflict free mode at higher load levels. Systems of this type have been described by M Skov, supra, and A. Bhargava, J. F. Kurose and D. Towsley in "A Hybrid Media Access Protocol for High-Speed Ring Networks", IEEE Jour. on Selected Areas in Communications, vol. 6, no. 6, July 1988, pp. 924-933.
As noted previously, high data rate systems are required to support integrated traffic. Many demand assignment protocol systems use a priority scheme based on upon either timing, rounds or reserved slots. Grow in U.S. Pat. No. 4,445,116 discloses a method for allocating bandwidth based upon target token rotation time (TTRT) and actual token rotation time. M. Zafirovic-Vukotic et al., supra, describe reserved slot and rounds systems for various slotted ring systems, and M Skov, supra, briefly discusses integrated traffic schemes for systems including reserved slots for reservation access in the DQDB system, polled access and slotted ring systems.
The uniframe method for integrated traffic uses assigned slots within a fixed frame. Unreserved slots can be used by a second access protocol such as token ring which is discussed by F. Ross, supra, and the proposed ANSI FDDI specifications. A second method of using uniframe is by limiting the time period of the uniframe to less than a full cycle and allowing a second access protocol to operate in the remaining period. This concept has been employed in a system known as Dynamic Resource Allocation in Metropolitan Area Networks (DRAMA) as described, for example, by K. Maly et al. in "Traffic Placement Policies for a Multi-band Network", ACM SIGCOMM '89 Symposium, Austin, Tex, Sept. 1989, pp. 94-105.
The major deficiency with these schemes is that they require either some form of master controller or an established initiation procedure in order to regulate the system. For instance, in uniframe and some timing and reservation systems, the master controller must assign slots to the synchronous traffic. Thus, a complex protocol must be established so that each node requests and knows not only its slot assignments but all other nodes' slot assignments as well so that reserved slots are not inadvertently corrupted. If a master controller is not used, as in FDDI I, the nodes must negotiate prior to ring operations. Changes to handle unanticipated traffic can not be made without halting and reinitiating ring operation. If nodes are free to reserve slots without a master controller, then capacity may be wasted or a node may hog the network.
Various CSMA collision detection (CSMA/CD) protocols are known in the prior art. See, for example, U.S. Pat. No. 4,707,829 to Pendse which discloses a CSMA/CD system that uses a unidirectional bus which is looped. Stations wait until the channel becomes idle and then transmit at the beginning of the next contention slot. The transmission is accepted if no other upstream station transmits, but if an upstream transmission is detected, the transmission is halted. Other examples of CSMA/CD systems are disclosed in U.S. Pat. No. 4,516,239 to Maxemchuk and U.S. Pat. No. 4,566,097 to Bederman. In the Bederman system, if a message arrives from upstream while a station is transmitting, the station checks priority of the incoming message. If the priority is less than or equal to the station message, the station continues to send its message. If priority is greater, the station aborts its message and forwards the incoming message. The station also aborts its message if it receives a start of a frame message which would contain synchronous data.
U.S. Pat. No. 4,549,292 to Isaman et al. discloses a method of efficiently and simultaneously transmitting both isochronous and nonisochronous data in a computer ring network. The terms "synchronous", "periodic" and "isochronous" may be used interchangeably. "Isochronous" has the additional connotation that the period is 125 microseconds, which corresponds to the frame rate used by commercial telephone systems, although Isaman et al. do not mention, nor does their system strictly require, 125 microsecond intervals. Isaman et al. use a token to designate a single station transmitting asynchronous data. As this packet propagates around the ring, any station with synchronous data may interrupt this message by inserting a control character followed by the message followed by a terminating control character. Stations upstream from the inserting station may add their synchronous data between the control characters. Alternatively, they can add another synchronous data block some other place in the asynchronous message. When the synchronous data block travels to the asynchronous sending station, it must interrupt its transmission and forward the synchronous block. It then resumes its transmission until another data block arrives or it finishes its transmission.
The Isaman et al. system lacks flexibility and limits data rate. Stations do not act independently upon detection of an idle condition on the network but must wait for a token or other control before sending asynchronous data. Other stations must buffer the incoming signal while transmitting synchronous data, and the station transmitting asynchronous data when interrupted by synchronous data must halt and then re-initiate transmission after passage of the synchronous data. The approach taken by Isaman et al. is similar to register-insertion of Hilal et al. and the Tree LAN system of Suda, described above.
A number of reservation access protocol systems have been described in the literature. See, for example, Chapter 3 of A. S. Tanenbaum, Computer Networks, 2nd Ed., Prentice-Hall, 1988. These schemes, which are also in the class of collision free protocols, generally work only for lower data rate systems, do not differentiate between types of traffic, and operate singly. U.S. Pat. No. 4,383,315 to Torng describes the concept of time slots that travel around a ring and are forwarded without interruption from a transmitter to a receiver. For synchronous traffic, time slots are reserved and may be used by the receiver to return data to the transmitter forming a full duplex circuit. For asynchronous data, a complex procedure for seizure and release of non-reserved time slots is invoked by stations having traffic.
Summary of the Invention
It is therefore an object of the present invention to provide a new access control method for ring or unidirectional bus networks that support high data rates of diverse synchronous and asynchronous traffic.
It is another object of the invention to provide a new reservation packet scheme for fixed length, non-corrupting, circulating network structures that enables the nodes in the network to reserve space for synchronous traffic and guarantee access to each node in the network.
According to one feature of the invention, access to the network is controlled by a new process. When the node senses the channel is idle, it can begin to transmit. If it senses an incoming signal, it must stop transmitting. Unlike other adaptive or random assignment access protocols which abort the transmission when a collision occurs or is imminent, this new process truncates the information in a fashion such that it can be resumed later when the channel again becomes idle. The system is called Carrier Sensed Multiple Access - Ring Network (CSMA/RN) and is characterized that rather aborting a transmission upon receipt of an incoming signal, CSMA/RN truncates the message. The stations in the network operate independently, allowing more than one to be transmitting at the same time.
The CSMA/RN protocol may be characterized as an adaptive or random assignment access protocol which uses "attempt and truncate" as opposed to other protocols in the same class which use "attempt and abort" or demand assignment protocols which may use "attempt and defer" and/or "attempt and hold" protocols of the prior art. Truncating alleviates the wasted capacity that exists at high loads in other adaptive or random assignment access protocols.
This new protocol also realizes considerable advantages over prior art systems. First, each node can operate independently, sensing and responding only to incoming messages from its upstream neighbor. This simplifies node operations and logic. Second, the amount of space occupied by a packet decreases as network rate increases. For example, at 100 Mbps, a 2K bit packet occupies a space of approximately 4 km along the network ring, but at 1 Gbps, this space is reduced to 0.4 km. Hence, a 1 Gbps, 10 km network can potentially have twenty-five separate 2K bit packets simultaneously in existence over its span. Thus, as bit capacity of the network increases with data rate, truncating a message when it is about to interfere with a message on the system and resuming it later when free space is available greatly improves the performance of the network. Third, by using the concept of always truncating incoming packets on to the network, messages on the network have absolute priority. This means that travel time for all messages on the network is fixed by their distance, by the speed of energy propagation within the network media and the delay occurring at each station. As a result messages or control packets can circulate around the network with a fixed period. This provides a known synchronism for establishing timing for synchronous traffic.
According to another feature of the invention, further guaranteed (time and bandwidth) access for synchronous traffic is effected by a circulating reservation packet which permits a node to have reserved space when the special packet returns. The Circulating Reservation Packet (CRP) is a new access concept developed for CSMA/RN but applicable to other fixed length, non-corrupting, circulating network structures to enable the nodes in a network to reserve space for synchronous traffic and guaranteed access. The CRP is a small packet or group of packets which circulate continuously around the network. As needed, as when new voice and/or video data or a critical message has arrived, the node captures a free CRP and places its space requirement request into the packet. As the CRP circulates, other nodes free and/or keep free the requested space. When the CRP returns, the node fills the free space behind it. Nodes can share CRPs on a round robin or other controlled basis so that all nodes obtain fair access for their synchronous traffic. Hence, a node is provided guaranteed access regardless of the traffic conditions.
A specific feature of the invention is the combining of the media access protocols, CSMA/RN and CRP, in a single ring network to support integrated traffic. The result is a hybrid protocol system for the purpose of supporting integrated traffic in high data rate networks as opposed to previous hybrid systems used to alleviate capacity degradation due to collisions. Neither protocol is based upon uniframe operations. The synchronous traffic protocol uses the CRP protocol reservation system, while the asynchronous messages use the CSMA/RN protocol. The fact that packets circulate around the network at a fixed period assures that a CRP packet which supports synchronous traffic arrives at a node at periodic intervals. Single or multiple CRPs may be used with the CSMA/RN protocol, although multiple CRPs can improve performance. These dual protocols support integrated traffic in an efficient manner, providing superior performance to either FDDI or DQDB.
Brief Description of the Drawing
The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:
FIG. 1 is a simplified block diagram showing the node access logic according to the invention;
FIG. 2 is a topographical illustration of a ring network illustrating CSMA/RN protocol operations;
FIG. 3 is a topographical illustration of a ring network illustrating CRP protocol operations;
FIG. 4 is a block diagram showing the format of a packet in a preferred embodiment of the invention;
FIG. 5 is a frame format showing a CRP information structure according to a preferred embodiment of the invention;
FIG. 6 is a block diagram showing in more detail the ring station according to a preferred embodiment of the invention; and
FIG. 7 is a block diagram showing an implementation of the receiver and transmitter sections of the ring station according to a preferred embodiment of the invention.
Detailed Description of a Preferred Embodiment of the Invention
Referring now to the drawings, and more particularly to FIG. 1, there is shown the node access controller logic 10. The incoming signal is split into two streams, one through a delay line 12 and the other through a controller 14 via a receiver logic decoder 16. The delay line 12 permits the node logic time to determine an impending collision and to take the actions necessary to truncate any transmit conditions successfully. The delay line 12 can be relatively short if high speed logic is used in the controller logic 10. For example, a 100-bit delay at 1 Gbps is approximately a twenty meter piece of optical fiber and creates a 100 nanosecond delay. The node controller 14, based upon information decoded in the receiver logic 16, is required to make a number of decisions. First, it must detect the presence of incoming data. If incoming data exists, controller 14 connects the input of transmitter 18 to the output of delay line 12 via switch 17. The node must always propagate incoming information as the outgoing signal to the next node on the ring because it would be impossible to recreate the packet unless much larger storage is provided. If no incoming data exists, the node is free to place its own data on the ring via transmitter 18 if its queue is not empty. The controller 14 does this by connecting the input of transmitter 18 to the node queue (not shown) via switch 17. However, if during the time this latter data is being transmitted an incoming packet arrives, then the node, within the time limits dictated by its delay line 12 size, must discontinue its transmission and handle the incoming packet. When truncating a packet, the node places a terminator block at the end to assist the receiving node with re-accumulating fractured massages. Hence, packets once on the ring take precedence over insertion of new packets.
Packets are tested at each node to determine if the incoming packet is destined for this node and should be copied to its receiver data buffer. This the controller 14 does by connecting the output of the delay line 12 to the receiver data buffer (not shown) via switch 19. Alternatively, the information can be transferred directly from the controller logic 10 to the receive data buffer with out using a switch at the end of delay line 12, since address decisions are required by the controller 14. Packets are nominally removed at their destinations since destination removal increases network capacity significantly. As a protection against packets circulating continuously in case of a node failure or address errors, packets are removed by the source after one or more rotations by comparing addresses against an established list or by implementing a packet monitor system.
FIG. 2 illustrates a model of a ring network on which the CSMA/RN protocol is implemented. It shows the events that can occur at each node based upon the travel of empty and full packets of data around the ring as time progresses. The events are those which can occur at a node by the arrival of a message, by the condition that an empty packet is passing the node when a message arrives, by the arrival of an empty packet at a node which has a queued up message, by the arrival of a packet destined for a node and by interrupting a node which is transmitting. It will be observed that although the logic conditions at each node are simple, the logic conditions for the ring become quite complex when it contains a large number of nodes and the decisions at a node eventually influence other nodes on the ring.
In the Circulating Reservation Packet (CRP) protocol, a special small packet, about one hundred bits, circulates continuously around the ring. Synchronous traffic is attached behind this packet. On the cycle prior to the node's need to submit synchronous and/or critical traffic, the node through the packet requests a block of space following the packet be freed for its use on the next cycle. The node is free to set this indicator whenever it has synchronous traffic and the reservation packet's in-use flag is free. When the node makes the reservation, it also sets this flag to busy and, after a complete cycle, the node changes this flag to free and sends its synchronous message(s) in the free space behind the CRP. In most cases, the capacity reduction due to a circulating reservation packet alone is small so that a network can have one or more CRP packets, depending on node count and ring length. The separation of the CRPs will limit the size of regular data packets as well as the size of the synchronous messages a node can send at one time. The block size requested by a CRP depends upon the synchronous traffic bandwidth required and the inter arrival time of the useable circulating packets.
As the CRP circulates around the network, the space behind the CRP is freed as the packets arrive at their designated destinations. Pre-use is available since this space can be used further if the destination node or any subsequent node has a message for any node between and up to the node which has set the CRP flag to busy. In addition, the node controlling the circulating packet does not need to request space to a greater extent than needed. For example, a telephone call which goes into the non-talk mode requires no or only a minimal block of reserved space during this phase. Hence, recovery is automatically provided by nodes tempering their space requests. As a result, the CRP system and handling of synchronous traffic should cause minimal impact on the underlying asynchronous network protocol.
Access is guaranteed one revolution after receipt of the CRP. To guarantee that nodes have access to free circulating packets requires that a node cannot use a circulating packet on a number of successive revolutions. By passing CRPs on, every node will get to see a free CRP within a fixed number of ring revolutions. Alternatively, CRPs can be assigned to particular nodes, with a CRP serving each of its assigned nodes in a round robin fashion. Further, in the case of longer distance rings, each node may have one or more CRPs designated to serve it only. Access time depends upon the conditions established for network operations based upon the number of nodes, the number of CRPs and the ring length.
There is actually no need for a node having new synchronous traffic to establish a call in the general case, since when the node gets its free CRP, it can request additional reserved space within the limit of the space following the CRP. This provides great flexibility but can limit the amount of traffic that a node can send at one point. However, if the node cannot get all its traffic placed or its inter-access time is too long, then it should use or establish another CRP on the network. If a new CRP is to be established by a node, it must coordinate with the other nodes since the placement of a new CRP will affect the other nodes related to both access time and amount of synchronous bandwidth available at the arrival of a free CRP.
FIG. 3 illustrates a model of the ring network on which the CRP protocol is implemented. Two CRPs are shown. One CRP is in use by node A which has requested space to be freed for the next time the CRP arrives at node A. As depicted, some of the space has been freed while other space is still occupied by the messages destined for nodes up to and including node A. With pre-use as described previously, the condition of the space requested by node A can change during the circulation of the CRP. The second CRP is free but has just been used by node B to transmit its synchronous messages. As illustrated, node B used Last Out, First In placement of its synchronous traffic so that the maximum contiguous free space block is created as nodes down stream from node B remove synchronous message traffic. The CRP used by node B is now free for capture by another node. FIG. 3 also illustrates the character of the free space available for asynchronous traffic while CRPs are operating. The space includes space not related to any CRP plus space within the CRP's span which is free in either a normal or pre-use mode.
Because call setup operation is minimal, CRP operations can be used for acknowledge operations and fairness control. For acknowledge, when a node sends a packet for which correct delivery should be assured, it sets an acknowledge flag in the packet header. Upon receipt of the packet, the destination checks the packet for correctness and during its next CRP access, it sends an acknowledge message. The source node has considerable information concerning when this acknowledge should be returned. First, based on distance, it knows when the destination will get the packet to be acknowledged and, based upon CRP usage, when the destination will set its next CRP. Thus, it can predict apriori the interval before the acknowledge arrives so it knows precisely how long that its packet buffer will be occupied.
Fairness control operates in a similar manner. One CRP provides a mechanism for determining the mean wait time per node and mean bit rate per node for the network. When a node fails to obtain access so that its wait time rate becomes too large and/or its bit rate too small, it can use the CRP to reserve space for packets which have waited too long. It knows precisely the maximum wait time before access will be obtained.
The frame format for a data packet, either synchronous or asynchronous, is shown in FIG. 4. The packet is of variable length, depending on the number of bytes of data; however, the header and trailer are of fixed lengths. Specifically, the header comprises an 8-bit preamble for synchronization, four bits for control, sixteen bits for the destination address, sixteen bits for the source address, and four bits for the packet count. The trailer comprises eight bits for the end block and sixteen bits for CRC (cyclic redundancy check) code.
A 5/4 encoding scheme similar to that used in other fiber-optic network systems, as for example FDDI, is assumed. Encoding permits designation of non-data encoded sequences which can be used for header and end blocks and assists in the detection of bit errors in the data stream. The header/preamble consists of two blocks whose encoding is the largest Hamming distance from the idle block and does not represent any valid data blocks. This allows the detection and synchronization in the case of bit errors.
The four control bits allow for ring and message control and comprise an M-bit, a T-bit, an R-bit, an S-bit. The M-bit is used as a monitor system to detect packets which may be in error. All transmitters set the monitor bit. The monitor station resets the bit. If the monitor station detects a packet with its monitor bit reset, it removes the packet from the system. The T-bit is set for ring control or to designate a Circulating Reservation Packet (CRP). It is reset for general data packets. The R-bit is set by the transmitting station if it requests that the receiving station acknowledge (ACK) the receipt of the packet. Note that for ring control packets, the R-bit can be used as an additional signal since these packets are never acknowledged. The S-bit is a spare bit.
The address bits comprise a total of thirty-two bits designating both the destination and source addresses. The destination address is given first to enable the controller logic at a node to have more time. Stations can have multiple addresses in order that multicast and broadcast can be implemented.
The packet count bits enable the receiving station in conjunction with the source address to determine the placement of the packet and hence aids in re-accumulation of a message. The variable data block is encoded in the 5/4 bit encoding scheme to represent valid data only. The encoding further contributes to the reliability of the network since invalid blocks indicate that a bit error has occurred.
Like the preamble, the end block is a unique set of 5/4 encoded bits which are different from any data words and signify the end of the data section. Finally, the CRC bits are calculated by the high speed ring access chip and appended to the back end of the packet. The CRC is not recalculated by the receiving station when the message is being forwarded but only for new messages entering from the transmit queue. An incorrect CRC will cause the receiving buffer to delete the packet it has accumulated and to request the transmit logic section to send a Not Acknowledge (NAK) message to the sender.
FIG. 5 shows a packet frame structure for CRPs. The synchronous header, control, end and CRC blocks are identical in character to those in the data frame. The control bits, M, T, R, and S, are used to designate that the packet is a CRP. The node address is used to show which node has reserved the CRP and is requesting free space. A free CRP is designated by a special node address. The CRP packet number is used if CRPs are assigned to particular nodes so that a node can determine if this is the correct CRP to use. The reservation length contains the free space block requested in bytes for an in-use packet and can be ignored for a free CRP.
The ring controller logic is shown in more detail in FIG. 6. The optical bypass switch system 21 provides a means to maintain network continuity in case the node optical electronic system should fail. It contains an equivalent time delay optical link so that the length of the network remains the same regardless of the node's operational status. The major logic operations occur in the ring access logic system 22 and the ring controller 29. The ring access logic system 22 is composed of three basic units. These are the receiver logic 25, the delay 26 and the transmitter logic 27. The electro-optical receiver 23 provides for the decoding of the 5/4 block structure. The receiver logic 25 provides for the detection of a change between receive the idle state, for parsing the control bit logic and for accumulating the address structure for decision by the address decoder logic 28. The address decoder logic 28 provides further decision signals based upon source and destination addresses. The decisions from both the ring access receiver logic 25 and the address decoder logic 28 are passed to the ring controller system 29 which then establishes the control to be used for this packet and forwards the information to the ring access transmitter logic 27 and the transmit and receive buffer systems 31 and 32.
On the transmitter side, the electro-optical transmitter 24 provides for 5/4 encoding and generating the optical signal. The transmitter logic 27 selects a transmit buffer from which information is to be taken and creates the CRC check sum which is to be appended to the packets. The actual delay 26 in the ring access chip required for the system operations is implemented as a FIFO delay line.
FIG. 7 shows an implementation of the receiver and transmitter sections of the ring station. The received optical signal is converted to an electrical signal in optical receiver module 41 which also recovers clock synchronization and forwards the signals to receiver logic 25 and delay line shift register 42. The optical receiver module may be implemented, for example, using conventional FDDI chip sets marketed by Advanced Micro Devices of Sunnyvale, Calif., or the Cambridge Ring system, as described by D. J. Greaves et al. in The Cambridge Backbone Ring, IEEE Document CH2826-5/90/0000/0008 (1990).
The frame structures, shown in FIGS. 4 and 5 for the data and control frames, are decoded in the receiver logic 25. More specifically, the receiver logic 25 comprises parallel decoders 43, 44 and 45 which receive the input signal from the optical receiver module 41 and decode, respectively, idle, header and end codes. The input signal from the optical receiver module is also supplied to 5/4 decoder 46 which provides an output to control signal decoder 47 in the receiver logic 25.
The idle decoder 43 provides an output to decision logic 48 and to the header decoder 44. The header decoder also provides an output to the decision logic 48 and to the control signal decoder 47. The control signal decoder, in turn, generates an ACK request signal, a CRP signal, a data signal, and a monitor signal, all of which are supplied to the decision logic 48. In addition, the output of the 5/4 decoder 46 and the CRP and data signals from the control signal decoder 47 are supplied to the address logic decoder 28 which supplies destination, source, address and length information to the decision logic 48. The output of the 5/4 decoder 46, the data and monitor outputs from the control signal decoder 47 and the destination signal from the address logic decoder 25 are supplied to the receiver buffer 32 (FIG. 6).
Alternate decoding structures could be used which produce equivalent signals. Actual decoding requires discrimination between bit patterns and can be implemented using a wide variety of logic circuit systems including programmed logic arrays (PLAs), hardwired logic circuits, programmed microprocessors, and the like, all of which are well known to those skilled in the art. Signals from the decoder elements are single line binary signals with the exception of the address and CRP length which are multiple bit parallel signals. Some decoder output signals are used as enabling signals for succeeding frame decoder and receiver buffer elements.
In addition to the signals from the decoders 43, 44, 45, 47, and 28, the decision logic 48 receives signals from the transmitter buffer queue. These various signals contain information concerning message conditions including availability, length, address locations and other conditions. The line count is variable depending upon the manner in which the transmitter queue buffer system is actually implemented. The decision logic 48, operating on combinations of the input signals and based on the protocol operating principals, selects the actual transmitter signal which is to be sent. The selector is diagrammatically illustrated as a switch 50, but it will be understood that solid state switching circuits are actually used to implement the selector. The selection made is from queues which represent various types of node messages that are available in the transmitter system. In actual practice, buffers and information structures relating to their contents may be address pointers or other data structures. The decision logic 48 is also used to regulate the transmitter operations and the transmitter and CRC signal process, as indicated by the dotted line 49.
The transmitter system consists of the transmitter signal process which accepts the message and conditions it for transmission on to the network by adding additional control structure. More specifically, the CRC processor 51 calculates a valid CRC block based upon the actual data signal being transmitted and appends the CRC block on the end of the frame, as shown in FIGS. 4 and 5. The message is then sent to the 5/4 encoder 52 and to the optical transmitter module 53 which selects whether the incoming signal, idle or the message is to be converted and sent. The selected signal is provided to the optical transmitter module 53 which converts the electronic signal into an equivalent optical signal regulated with a clock timer. Suitable hardware for the optical transmitter module 53 exists in the FDDI and Cambridge Ring systems, as noted above.
The circuit components of FIG. 7 are shown in functional block diagram form. Actual logic circuits and specific hardware depend upon the actual bit rate being used and other factors influencing actual circuit designs. These are, however, a matter of design choice and need not be described in more detail.
The unique and novel features of the CSMA/RN access mechanism are:
a. It provides instant access to the network at idle.
b. It eliminates the wasted capacity which occurs in other carrier sensed networks at high load levels since the node does not have to re-transmit the aborted information lost in the collision.
c. It can support multiple messages on the network simultaneously.
d. It can support a wide range of operational conditions, e.g., network lengths, number of nodes, size of messages, etc.
e. It is capable of operating at data rates greater than 10.sup.8 bps. Operational characteristics of this access method should improve as data rate increases.
f. Nodes operate independently on local information only, simplifying the node and network operations and logic systems.
g. There is no limit on useable message length because of protocol operations.
h. Destination removal can be implemented which increases significantly the network performance capacity.
The unique and novel features of the Circulating Reservation Packet (CRP) are:
a. It provides effective guaranteed access for critical and synchronous traffic.
b. All packets on the network related to CRP operation and use appear as data packets to the asynchronous media access protocol. This provides a dual media access protocol system where the synchronous traffic protocol, CRP, creates minimal interference with and impact on the asynchronous traffic protocol system, bit it CSMA/RN or some other access mechanism.
c. It does not interfere with traffic already on the network and its interference with traffic being placed by other nodes is minimal.
d. Only space actually needed by the active synchronous traffic is used. A telephone call in silent mode does not waste space since the node does not need to request space. Hence, no scheme is needed for bandwidth recovery.
e. It is feasible for a group of network systems other than CSMA/RN where information can be made to circulate continuously on a reasonably fixed cycle without interference from nodes accessing the network and corrupting permanent messages.
f. Pre-use can be implemented which significantly increases the network ability to support asynchronous traffic under high synchronous traffic loads.
While the invention has been described in terms of a single preferred embodiment, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims. Specifically, another embodiment of the invention could use virtual circuit concepts which exist in present and future telephone systems as a replacement for the underlying physical optical links and associated connections considered in the disclosed embodiment.
Claims
Having thus described our invention, what we claim as new and desire to secure by Letters Patent is as follows:
1. In a ring or unidirectional bus network having a plurality of nodes to which are connected a plurality of computer stations, a method for efficiently transmitting data on said network allowing multiple messages on the network simultaneously, said method being performed by control logic at each of said nodes and comprising the steps of: sensing a carrier on said network to detect the presence of incoming data at the node; if the incoming data is addressed to the node, receiving the data and removing it from said network; if the data is not addressed to the node, retransmitting the data with fixed delay; if the node is transmitting data at the time of receipt of incoming data and the incoming data is not addressed to the node, truncating the data being transmitted and retransmitting the incoming data; if transmitting data at the time of receipt of incoming data addressed to the node, continuing to transmit data while receiving data.
2. The method recited in claim 1 wherein data transmitted on said network is transmitted in a packet including destination and source addresses further comprising the step of checking incoming data for the node's own source address and removing said data from said network.
3. In a ring or unidirectional bus network comprising a plurality of nodes to which are connected a plurality of computer stations, a method for efficiently transmitting both synchronous and asynchronous data on said network, said method comprising the steps of: circulating a plurality of circulating reservation packets on said network; using a predetermined protocol, accessing by control logic at each of the nodes said network to transmit asynchronous data; when synchronous data is to be transmitted by a respective one of said nodes, setting by the node a flag and space required in one of said circulating reservation packets to reserve space behind said one of said circulating reservation packets for said synchronous data; and upon return to the one said node of said one of said circulating reservation packets, resetting said flag and transmitting said synchronous data in space reserved behind said one of said circulating reservation packets.
4. In a ring or unidirectional bus network having a plurality of nodes to which are connected a plurality of computer stations, a method for efficiently transmitting both asynchronous and synchronous data on said network allowing multiple messages on the network simultaneously, said method comprising the steps of: circulating at least one circulating reservation packet on said network; when synchronous data is to be transmitted by a respective one of said nodes, setting by the node a flag in said circulating reservation packet to reserve space behind said circulating reservation packet for said synchronous data; upon return to said one node of said circulating reservation packet, resetting said flag and transmitting said synchronous data in space reserved behind said circulating reservation packet; sensing by control logic at each node a carrier on said network to detect the presence of incoming data to the node; if the incoming data is addressed to the node, receiving the data and removing it from said network by said node; if the data is not addressed to the node, retransmitting by said node the data with fixed delay; if the node is transmitting asynchronous data at the time of receipt of incoming data and the incoming data is not addressed to the node, truncating the asynchronous data being transmitted and retransmitting the incoming data; and if transmitting data at the time of receipt of incoming data addressed to the node, continuing to transmit data while receiving data.
5. The method recited in claim 4 wherein data transmitted on said network is transmitted in a packet including destination and source addresses further comprising the step of checking incoming data for the node's own source address and removing said data from said network.
6. The method recited in claim 5 wherein a plurality of circulating reservation packets are made to circulate on said network.
7. A ring or unidirectional bus network having a plurality of nodes to which are connected a plurality of computer stations, a control logic at each of said nodes for efficiently transmitting data on said network allowing multiple messages on the network simultaneously, said control logic at each of said nodes and comprising: means for sensing a carrier on said network to detect the presence of incoming data to the node; means for receiving the data at the node and removing it from said network if the incoming data is addressed to the node; means for retransmitting the data with fixed delay if the data is not addressed to the node; means for truncating the data being transmitted and retransmitting the incoming data if the node is transmitting data at the time of receipt of incoming data and the incoming data is not addressed the node; means for continuing to transmit data while receiving data if transmitting data at the time of receipt of incoming data addressed to the node.
8. The network recited in claim 7 wherein data transmitted on said network is transmitted in a packet including destination and source addresses further comprising means for checking incoming data for the node's own source address and removing said data from said network.
9. A ring or unidirectional bus network comprising a plurality of nodes to which are connected a plurality of computer stations, control logic at each of said nodes for efficiently transmitting both synchronous and asynchronous data on said network, said control logic comprising: means for circulating a plurality of circulating reservation packets on said network; means for accessing said network to transmit asynchronous data using a predetermined protocol; means for setting a flag and space required in one of said circulating reservation packets to reserve space behind said one of said circulating reservation packets for said synchronous data when synchronous data is to be transmitted by a respective one of said nodes; and means for resetting said flag and transmitting said synchronous data in space reserved behind said one of said circulating reservation packets upon return to the one said node of said one of said circulating reservation packets.
10. A ring or unidirectional bus network having a plurality of nodes to which are connected a plurality of computer stations, control logic at each of said nodes for efficiently transmitting both asynchronous and synchronous data on said network allowing multiple messages on the network simultaneously, said control logic comprising: means for circulating at least one circulating reservation packet on said network; means for setting by a node a flag in said circulating reservation packet to reserve space behind said circulating reservation packet for said synchronous data when synchronous data is to be transmitted by a respective one of said nodes; means for resetting said flag and transmitting said synchronous data in space reserved behind said circulating reservation packet upon return to said node of said circulating reservation packet; means for sensing a carrier on said network to detect the presence of incoming data to the node; means for transmitting asynchronous data on said network if no incoming data is sensed; means for receiving the data and removing it from said network by said node if the incoming data is addressed to the node; means for retransmitting by said node the data with fixed delay if the data is not addressed to the node; means for truncating the asynchronous data being transmitted and retransmitting the incoming data if the node is transmitting asynchronous data at the time of receipt of incoming data and the incoming data is not addressed to the node; and said means for transmitting continuing to transmit data while receiving data if transmitting data at the time of receipt of incoming data addressed to the node.
11. The network recited in claim 10 wherein data transmitted on said network is transmitted in a packet including destination and source addresses further comprising means for checking incoming data for the node's own source address and removing said data from said network.
12. The network recited in claim 11 wherein a plurality of circulating reservation packets are made to circulate on said network.
Patent Citations (7)
Non-Patent Literature (14)
- "Implementations of Physical and Media Access Protocols for High Speed Networks", M. Skov; IEEE Communications Magazine; Jun. 1989; pp. 45-53.
- "Performance Analysis of Slotted Ring Protocols in HSLANs" G. N. Niemegeers et al; J. on Selected Areas in Communications; vol. 6; No. 7; Nov. 1983; pp. 913-925.
- "Performance of Unidirectional Broadcast Local Area Networks: Expressnet and Fastnet"; IEEE J. on Selected Areas in Communications; vol. SAC 1; No. 5; Nov. 1983; pp. 913-925; F. A. Tobaji et al.
- "The QPSX Man"; IEEE Communications Magazine; R. M. Newman et al.; vol. 26; No. 4; Apr. 1988; pp. 20-28.
- "Analysis and Simulation of the Registration and Insertion Protocol"; W. Hilal et al.; Proc. of Computer Network Symposium; Dec. 10, 1982; pp. 91-100.
- "Performance Evaluation of Channel Access Protocols for Local Computer Networks"; M. T. Liu et al.; Campcon '82; Sep. 2-23, 1983; pp. 417-426.
- "Fairness Problems in High Speed Networks"; K. Maly et al; Old Dominion University; Computer Science Dept.; TR-90-15; Mar. 1990.
- "FDDI--An Overview"; F. Ross; IEEE Transactions on Communications; vol. 24; No. 5; May 1986; pp. 10-17.
- "FDDI Token Ring Physical Layer Medium Dependent (PDM)"; asc X3T9.5/86-71; Jul. 10, 1986.
- "Local Area Subnetworks: A Performance Comparison"; W. Bux; IEEE Transactions on Communications; vol. com-29; No. 10; Oct. 1981; pp. 1465-1473.
- "Tree LANs with Collision Avoidance: Protocol Switch Architecture and Simulated Performance"; T. Suda; ACM 0-89791-279-9/99/008/01555.
- "A Hybrid Media Access Protocol for High Speed Ring Networks"; A. Bhargava et al.; IEEE J. on Selected Areas in Communications; vol. 6; No. 6; Jul. 1988; pp. 924-933.
- "Traffic Placement Policies for Multi-band Network"; K. Maly et al; ACM SIGCOMM '89 Symposium; Austin, Texas; Sep. 1989; pp. 94-105.
- "The Cambridge Backbone Ring"; David J. Greaves et al; IEEE Document CH826-5/90/0000/0008; (1990).