Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1999-04-15
2003-03-25
Vu, Huy D. (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
C370S230000, C370S395430, C370S462000, C709S226000, C709S235000
Reexamination Certificate
active
06538990
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer networks, and more particularly, to a method and system for improving congestion flow control in such networks.
BACKGROUND OF THE INVENTION
Ethernet local area network (LAN) technology was developed as an inexpensive way to permit network stations to directly exchange data with one another on a peer-to-peer basis; that is, without routing the data through a host computer. The term “stations” is a generic one that applies to workstations, data storage servers, printer servers or virtually any other network-attached device capable of sending and receiving data. In a single Ethernet LAN, every station is connected to a shared bus and decides independently whether it can begin to transmit data to the shared bus.
An Ethernet station makes a transmit decision by applying an algorithm known as a carrier sense multiple access/collision detect (CSMA/CD) algorithm, defined in detail in a published IEEE 802.3 standard. In the simplest terms, an Ethernet station that has data to send on the shared bus attempts to “acquire” the bus by first monitoring or listening to the bus to see if it is currently busy (that is, one of the other stations is already transmitting data) or currently quiet (no other station is currently transmitting data). If the bus is busy, the station will wait for a predetermined period of time before again attempting to acquire it. If, however, the bus is quiet, the station initiates transmission of data. Even after initiating transmission, a station continues to listen to the bus.
Because every station attached to the shared bus acts independently in deciding when to transmit, there is a risk that two or more stations with data to transmit will each begin listening to the bus at substantially the same time, will each find the bus to be quiet and will each begin transmitting data at substantially the same time. Under these conditions, the data from the transmitting stations is said to “collide” on the bus, resulting in a garbled data stream. The data collision is detected when a transmitting station detects a mismatch between the data it is transmitting and the data actually being carried on the bus. When a collision is detected, the detecting station stops transmitting data and sends a jamming signal to the bus. The jamming signal is intended to assure that other transmitting stations will promptly detect a collision and will stop transmitting. Every station that detects a collision waits for a predetermined time before again invoking the CSMA/CD algorithm in an attempt to acquire the bus.
Is The original Ethernet technology (10 BaseT) supported a bus speed of 10 Mbps. Fast Ethernet (100 BaseT) is a more recent high speed local area network (LAN) technology that offers increased bandwidth to individual stations on the LAN by supporting a bus speed of 100 Mbps. Fast Ethernet uses the existing IEEE 802.3 CSMA/CD specification originally adopted for the 10 Mbps Ethernet technology while increasing the clock speed by a factor of ten. Consequently, 100 BaseT uses the same frame format, frame size and error detection mechanism as adopted for 10 Mbps systems.
Fast Ethernet hubs are network devices that provide a simple yet high performance solution to the bandwidth bottleneck of small and medium-sized legacy local area networks (LANs). Fast Ethernet hubs provide a number of 100 BaseT ports along with a port for connection to a 100 BaseT Ethernet network. 10 BaseT, AUI and coax port connections are provided for connection to the slower speed Ethernet network. Different manufacturers use different names for this port, including Fast Expansion Module (FEM), Network Interconnect Port or Network Expansion Module. In the remainder of this specification, the port will generally be referred to as a network interconnect (NI) port.
The network interconnect port acts as a LAN bridge between the high speed (100 Mbps) Ethernet network implemented in the hub and a low speed (10 Mbps) Ethernet network.
Congestion occurs on the LAN bridge when there is too much traffic that needs to be bridged from the 100 Mbps Ethernet to the slower 10 Mbps Ethernet. Different processes can be implemented to detect the presence of congestion at the hub. One well known process requires that the hub monitor the occupancy level of input buffer memories used to temporarily store data intended for the network interconnect port. The hub is said to be congested when the occupancy level of the buffer memories exceeds a predetermined percentage of their capacity.
To solve this congestion problem, a Fast Ethernet hub typically implements a feature called a back pressure function. Simply stated, the back pressure congestion control method requires that jamming signals be generated on the 100 Mbps side of the network to stop the transmission of any frames through the LAN bridge in an attempt to let the 10 Mbps side catch up with its frame processing. A jamming signal indicates that the network is busy to all of the stations on the fast Ethernet network. No stations can transmit or receive data while the jamming signal persists. The flow control mechanism of the back pressure function is a simple extension of the existing CSMA/CD contention algorithm.
There is a severe problem with this back pressure function. Every station on the 100 Mbps side of the network interconnect port is adversely affected if congestion occurs in the 10 Mbps network interconnect port since every 100 Mbps station will be prevented from transmitting or receiving as a result of the generated jamming signal. Since all stations experience a disruption when the back pressure algorithm generates the collisions, the existing back pressure solution is non-deterministic. No attempt is made to determine and isolate the 100 Mbps station or stations actually causing the congestion in the network interconnect port.
There is a need for an improved flow control mechanism that provides an improved contention algorithm suitable for a high speed LAN connection to a slower speed LAN.
SUMMARY OF THE INVENTION
The invention solves the problem of congestion that can arise at a high speed LAN/low speed LAN bridge. When congestion is detected at a hub port, a port to station address mapping is initiated to classify the station attached to a hub port. Each station is classified either as a local, a remote or a network management station (NMS). A remote station is one that is currently communicating with other stations on the low speed side of the LAN bridge. Remote stations are disabled during periods of LAN bridge congestion. Local stations, those that are not currently communicating with low speed stations over the LAN bridge, are not ordinarily disabled. Stations that are disabled is a result of a congestion condition are re-enabled after a predetermined period of time.
In accordance with a further aspect of the invention, ports on the managed hub that are connected to a network management station are protected by exempting those ports from any flow control action. This exemption, which assures continued availability of the network management station during most congestion situations, is justified by the fact that network management traffic is generally afforded a high priority. In accordance with another aspect of the invention, only stations making heavy use of the LAN bridge are disabled during periods of LAN bridge congestion.
REFERENCES:
patent: 5274644 (1993-12-01), Berger et al.
patent: 5276681 (1994-01-01), Tobagi et al.
patent: 5291481 (1994-03-01), Doshi et al.
patent: 5345447 (1994-09-01), Noel
patent: 5351241 (1994-09-01), Yehonatan
patent: 5404353 (1995-04-01), Ben-Michael et al.
patent: 5434860 (1995-07-01), Riddle
patent: 5491801 (1996-02-01), Jain et al.
patent: 5544323 (1996-08-01), Heaton et al.
patent: 5568476 (1996-10-01), Sherer et al.
patent: 6035333 (2000-03-01), Jeffries et al.
patent: 6049528 (2000-04-01), Hendel et al.
patent: 6052734 (2000-04-01), Ito et al.
patent: 6094435 (2000-07-01), Hoffman et al.
patent: 6170022 (2001-01-01), Linville et al.
patent: 6212164 (2001-04-
Phan M.
Vu Huy D.
Woods Gerald R.
LandOfFree
Method and system for congestion flow control in a high... 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 system for congestion flow control in a high..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for congestion flow control in a high... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3074776