Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1997-03-13
2001-01-09
Kizou, Hassan (Department: 2738)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S448000
Reexamination Certificate
active
06172983
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to methods and systems for managing data transmissions within a network and more particularly to methods and systems for managing data collisions and retransmissions within a network having a number of terminals connected to a common hub.
DESCRIPTION OF THE RELATED ART
A local area network (LAN) permits data communications among a number of interlinked terminals, typically computers. The control of a LAN may be centralized or distributed. Centralized control typically includes a single device that manages data communications among the terminals. On the other hand, in a distributed control network, the terminals cooperatively control the operation of the network. The software and hardware for governing transmissions and receptions of messages in the form of data packets are included in each of the terminals that form the network. An advantage of the distributed control scheme is that adding or removing a terminal from the network can be easily accomplished.
There are a number of different configurations (i.e., topologies) for LANs. In a mesh network, all of the terminals are connected to all other terminals. In comparison, a ring network connects the terminals one-by-one to form a continuous loop. Another alternative is a star-configured network in which all of the terminals are connected at a “center”. The interconnection at the center may be simplified by using a hub. The hub may be a switching hub that routes data packets only to the terminal or terminals for which the data packets are intended. Each packet has a header that identifies the destination terminal. The switching hub determines the destination of a data packet from its header and routes the packet to the appropriate destination. Switching hubs are particularly suited for networks in which performance requirements require that only selected terminals receive data packets.
Most LANs that include a hub do not utilize a switching hub. Instead, a common bus is formed within the hub. Data packets are transmitted to all of the terminals within the network. That is, each terminal is a “destination terminal,” but may not be the intended terminal. When a packet is received at a terminal, the header of the packet is read to determine whether the terminal is the intended terminal. An intended terminal reads and processes the data packet, while the other terminals discard the packet. The intended terminal may transmit an acknowledgment (ACK) signal to the originating terminal, since the originating terminal would retransmit the data packet if the ACK signal were not received.
Within a LAN having a hub that forwards the data packets to the various terminals, there must be a protocol for determining accessibility to the hub. The protocol within an Ethernet network is referred to as a Carrier Sense Multiple Access (CSMA) protocol. A terminal that is prepared to transmit a data packet “listens” to determine whether the network is free or is being used by another terminal. Typically, all of the terminals have equal priority and begin transmitting if the network is free. Once the transmission is initiated, the other terminals in the network will sense that the network is busy, and will refrain from initiating a transmission. However, there are times at which two terminals will begin transmitting simultaneously, causing a transmission collision. Therefore, the Ethernet network typically includes CSMA with Collision Detection (CSMA/CD).
U.S. Pat. No. 4,536,903 to Yang et al. describes the CSMA/CD protocol. If two terminals, or “nodes”, initiate transmissions and detect a collision of the data packets, the terminals terminate the transmissions. At each terminal, a back-off time is calculated. The calculation is provided by a back-off algorithm that is the product of a slot time of 51.2 &mgr;s times a number within a defined range. The range depends upon the number of collisions encountered by a particular data packet. If the data packet encounters repeated collisions, it is assumed that the workload is high and that the average back-off time should be greater.
FIG. 1
is a table of the back-off calculations executed in an Ethernet network.
One concern in the application of the back-off algorithm of
FIG. 1
is that one terminal may “capture” the network. The capture effect is identified in Yang et al. If two terminals initiate transmissions simultaneously, a first collision will occur. As shown in the table of
FIG. 1
, each terminal will select a back-off time of either 0 or 1 times the slot time of 51.2 &mgr;s. If a first terminal selects 0 back-off time and the second terminal selects 1 slot time as its back-off time, the first terminal will successfully transmit its first packet. Assuming that the first terminal has a second data packet to transmit, the two terminals will again contend for access to the network after completion of the first successful transmission. A collision will again occur. However, the data packet of the first terminal will encounter a first collision, while the data packet of the second terminal will encounter its second collision. As a result, the first terminal will be selecting within the range of 0 to 1, while the second terminal will be selecting within the range of 0 to 3, as shown in FIG.
1
. Clearly, the first terminal is more likely to be successful. The likelihood increases if the first terminal is successful and the same two terminals contend for access following the second transmission by the first terminal. The data packet of the second terminal will encounter a third collision and the second terminal will be selecting within the range 0 to 7. If the process continues 16 times, the data packet of the second terminal will be discarded. Thus, a data packet will be lost because the first terminal was able to capture the network.
Yang et al. describes a method of reducing the adverse effects of the capture effect. The Ethernet standard of determining back-off calculations, as shown in
FIG. 1
, is modified in the event that a terminal captures the network communication channel. Upon detecting such an event, the method provides a less aggressive, i.e. longer, back-off time before at least the first retransmission attempt made by a node that has captured the channel. In addition, a stopped back-off algorithm may be used to reduce the adverse effects of a capture condition. The method operates well for its intended purpose, but under certain conditions implementing the less aggressive back-off calculation and/or providing the stopped back-off algorithm may increase the latency of the network.
Another method of reducing the likelihood that one terminal will capture the network to the exclusion of other terminals is to minimize or eliminate collisions between data packets. Networks designed for collision-free communications are described in U.S. Pat. Nos. 5,546,385 to Caspi et al. and 4,998,247 to Irvine-Halliday et al. The Caspi et al. network utilizes a switched hub for selectively routing the data packets to intended terminals. The use of switched hubs to avoid collisions is described above and is known in the art. The network includes communication ports that determine a destination port for each incoming communication and then perform interleaved transfers of the packets to a set of virtual transmit first-in-first-out (FIFO) memories that buffer the packets for outbound transfer. Irvine-Halliday et al. describes a network that utilizes a controller hub as an alternative to CSMA/CD processing. The controller hub immediately relays a data packet from one of the terminals to a desired destination terminal when the packet is the only packet received by the controller hub. However, when a number of packets are simultaneously received by the controller from different terminals, the controller immediately relays a selected packet, while temporarily storing the other packets for subsequent transmission. If more than one terminal is intended for reception of a packet, the transmission of the packet is made to all of the intended terminals simulta
Shaffer Shmuel
Weiss David
White Charles Marcus
Elallam Ahmed
Kizou Hassan
Siemens Information and Communication Networks Inc.
LandOfFree
Hub dominated method and system for managing network collisions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hub dominated method and system for managing network collisions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hub dominated method and system for managing network collisions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2529018