Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1998-08-25
2001-11-20
Ton, Dang (Department: 2661)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
Reexamination Certificate
active
06320870
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The invention relates to data communications networks. More particularly, the invention relates to flow control on a switched CSMA/CD network.
2. Description of the Prior Art
Data communication network protocols, such as the Ethernet protocol, are well known. While such protocols were designed during the nascent stages of data networking, the processing speed of modern hosts has increased by several orders of magnitude, to the point where the relative bandwidth of a 10 Mbps Ethernet has fallen from more than adequate to support large enterprise networks, to marginally fast enough to support a single high-performance desktop workstation. At the same time, Ethernet protocols have also evolved to incorporate new technology at the physical layer, including new media, new signaling methods, and support for higher data rates. Unfortunately, such features of Ethernet as the MAC layer protocols have remained essentially unchanged from the early days of undemanding applications running on large numbers of slow hosts.
Ethernet employs a random access MAC layer protocol. A necessary requirement for using such a protocol concerns the problem of stability, i.e. as load on the channel increases, throughput increases or remains constant. If the protocol is not stable, as load increases, wasted channel bandwidth due to collisions increases and throughput drops significantly.
It is known in the art to stabilize such protocols by employing a suitable dynamic control procedure for rescheduling packets after each collision (see for example, G. Fayolle, E. Gelenbe, and J. Labetoulle, Stability and Optimal Control of the Packet Switching Broadcasts Channel, Journal of the ACM 24(3), pp. 375-386 (July
1977).
Thus, many suitable control algorithms have been discussed in the literature (see for example G. A. Cunningham, J. S. Meditch, Distributed Retransmission Controls for Slotted, Non-Persistent, and Ritual Time CSMA, IEEE Transactions on Communications, COM-36(6), pp. 685-691, June 1988; B. Ahjek, T. van Loon, A Decentralized Dynamic Control of a Multiaccess Broadcast Channel, IEEE Transactions on Automatic Control, EC-27(3), pp. 559-569, June 1982; and J. S. Meditch, C. A. Lea, Stability and Optimization of the CSMA and CSMA/CD Channels, IEEE Transactions on Communications, COM-31(6), pp. 763-774, June 1983).
More and more networks are using switching. In some cases, all the connections are dedicated (i.e. between a single node and a switch or between two switches) rather than shared (i.e. more than two nodes attached to the same communications media). When using a switch, a number of nodes may send traffic to the switch destined for the same output port. Also, the ports on the switch may operate at different speeds. For example, some ports may operate at 10 Mb/s and some at 100 Mb/s. Therefore, the total traffic coming into the switch destination may arrive at a faster rate than it can be transmitted out of the port. The switch typically contains storage buffers, e.g. memory, to allow it to store the excess input when this situation occurs. The switch may then wait to transmit such input later. These buffers are finite and fill when the problem situation persists over a period of time. When the buffers are full, incoming traffic must be dropped.
It is desirable to slow or stop the arrival of traffic rather than dropping the excess traffic. Several methods of flow control are either in use or under discussion to implement this. One common method in use on CSMA/CD networks is to generate a collision when a packet arrives at the switch. This may be accomplished in one of two ways:
a) The switch causes a collision whenever traffic arrives and the buffers are full; or
b) The switch starts to receive the packet and examines the destination address. If the destination address indicates that the packet should go to a port with a full buffer, then the switch causes a collision.
In either case, this method has serious limitations. For example, each time a collision occurs while attempting to transmit a packet, the N node chooses a random number of slot times (e.g. 512 bit times) to delay before attempting to transmit again. The range from which the number is chosen is 0 to 2
n-1
where n=min (number of transmit attempts, 10). Thus, once several collisions have occurred, the node is likely to wait for a long backoff time to expire before transmitting again. The switch may have transmitted packets and now have buffer space available, but the node does not transmit to take advantage of this for some time.
The Binary Logarithmic Arbitration Method (BLAM) is a modification of the CSMA/CD access protocol that has been proposed for and is in the process of being added to the IEEE 802.3 Standard. See for example, M. L. Molle, A New Binary Logarithmic Arbitration Method for Ethernet, Computer Systems Research Institute, University of Toronto, Technical Report CSRI-298 (April 1994). BLAM improves the fairness and delay characteristics of the CSMA/CD access protocol by basing the node backoff algorithm on all of the traffic on the network, rather than just the transmissions attempts made by the node itself. As a result, the node resets the backoff to zero when it sees a successful transmission on the network, i.e. successful transmission lasting at least 512 bits after the start of frame delimiter.
Most of the advantages of a protocol, such as BLAM, over other protocols come from deriving more information about the state of the network from the available signals coming into the host interface from the attached medium access unit (i.e. the transceiver). The primary distinction between BLAM and other protocols in terms of signaling is the use of ternary state information about the channel, i.e. idle/success/collision information. Thus, carrier sensing can be used to distinguish an idle channel from a busy channel. Furthermore, if the given host is actively transmitting, then collision detection can be used to distinguish a success from a collision, using either analog voltage levels on shared media (i.e. 10 Base 5 and 10 Base 2), or digital logic on unidirectional point-to-point channels, simultaneous, 9-loop back transmission, and reception on twisted pair or optical fiber). BLAM also demonstrates how a passive absorber can distinguish between a success or collision in which the observer was never involved. Thus, BLAM classifies such a period of activity as a collision if and only if its duration in bits, not counting the preamble and start of frame delimiter. BLAM was designed to reduce latency and increase fairness on a shared network. It does not address congestion and dropping of traffic on a bridged or switched network.
Thus, BLAM mediates backoff time by testing during the backoff for a successful transmission by another node or a collision. If a successful transmission occurs or the backoff time expires with no activity, the node will transmit. If a collision occurs, then the present backoff is abandoned and a new one is implemented. It would nonetheless be desirable for the switch to trigger the node to transmit right away when a buffer becomes available, rather than await expiration of a backoff period.
SUMMARY OF THE INVENTION
The invention provides a method and apparatus for implementing flow control on a switched CSMA/CD network where the network implements the BLAM protocol. The invention exploits to advantage the fact that it is possible for a switch on the network to trigger a node to transmit immediately when buffer space becomes available. In such case, the switch can then send a packet to the port that it was previously holding off with collisions. The packet can be a minimum size (e.g. 64 byte) packet. The packet may also be self-addressed or sent to a null address so that it is not received by any node attached to that port. Such transmission then causes the backoff to be reset to zero, and the node begins transmitting immediately. Alternatively, where a switch has been holding off several ports, the invention herein may be implemented to all
Hewlett--Packard Company
Ton Dang
LandOfFree
Method and apparatus for flow control on a switched CSMA/CD... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for flow control on a switched CSMA/CD..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for flow control on a switched CSMA/CD... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591134