Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2000-06-14
2004-05-25
Yao, Kwang Bin (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
C370S249000
Reexamination Certificate
active
06741555
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to congestion control of data networks, and more particularly, relates to a congestion avoidance mechanism for packet-switched networks, especially wireless or mobile networks.
2. Related Art
A data network is a collection of network devices, or nodes interconnected by point-to-point links. Communication links may be wired (i.e., optical fiber) or wireless (i.e., infrared or radio-frequency) for supporting a number of logical point-to-point channels. Each channel may be a bi-directional communication path for allowing commands and message data to flow between two network devices or nodes within the data network. Network devices or nodes may be categorized as either end systems or routers, which are also known as intermediate systems or communication gateways. End systems may include PCs, workstations, mainframes, file servers, storage devices and other types of computers. Router may include a number of communication links for forwarding data arriving over one link onto another link for transmission to an end system or another router.
Generally, end systems both send data to other end stations on the data network and receive data sent by other end systems on the data network. When an end system serves as a sender of data, it is referred to as a source for that data; whereas, when such an end station serves as a receiver of data, it is referred to as a destination for the data. Typically, end systems may act as both sources and destinations depending upon whether they are sending or receiving data. When acting as a source, the end system sends data in the form of messages over a communication link to a router for transferring the messages to an end system or another router.
Each message may comprise a sequence of information bits. Typically, however, the messages sent over the data network are not sent as a continuous, uninterrupted stream of bits. Rather, they are divided up into smaller blocks of information called packets, which are then transmitted individually. Each packet has a predetermined maximum length. In addition to a data field which contains the data to be transferred, a packet also includes a header field which contains control information such as format, identifiers which indicate what portion of the message is contained in the packet, the source of the packet and the intended destination of the packet. When the packets which together contain a message reach the destination, the destination processes them by assembling their data fields into proper order to reconstruct the full message.
One important design objective in data networks is controlling the flow of packets so that such packets may not be transmitted at a faster rate than they can be processed by the routers through which the packets may pass or by the destinations. Even in the simplest data network consisting of two end systems interconnected by a router, for example, the source may flood the destination if it transmits packets faster than they can be processed by the destination. In more complicated networks consisting of many end systems, numerous routers and alternative communication paths between the end systems, the likelihood of problems from excess communication traffic is significantly greater. This becomes especially true as the number of active end systems on the network increases and if communication speeds of the equipment within the network are mismatched. A mismatch may exist if, for example, a router cannot transfer packets as fast as they are being sent to it by the source. A mismatch may also exist between the speed at which the link can transmit packets, namely the link speed, and the rate at which the router can transfer packets. Predictably, as the complexity of the network increases, achieving an acceptable traffic control also becomes more difficult.
On most networks, including TCP/IP packet-switched networks in which Transmission Control Protocol (TCP) [RFC 793, September 1981] may be implemented to ensure high-speed and high-quality data transfer in the Internet, at least two basic mechanisms are normally used for dealing with excess traffic arriving at a destination. One mechanism involves the use of buffers and the other involves flow control. In buffered systems, both the routers and the end systems (i.e., source node and destination node) are provided with buffer memory to handle data overloads. Arriving traffic which exceeds the processing rate of the device is temporarily stored in the buffer memory until the device can process it. Buffers offer a satisfactory solution to excess traffic problems only if the overload is transitory. If the overload persists for too long, the buffers may become full after which the additional packets are rejected or destroyed.
The other mechanism, generally referred to as flow control, deals with the allocation of resources at the destination, such as memory and processing. Generally, in accordance with flow control, the destination sets a limit on the transmission rate at which each source sending data to the destination may transmit that data. The sources and the destinations coordinate the transfer of data by an exchange of messages containing requests and acknowledgments. Before the source starts sending packets, it will send a request to the destination seeking permission to begin transmission. In response to the request, the destination sends a message containing an identification of the number of packets the source may dispatch toward the destination without further authorization. This number is commonly referred to as the window size. The source then proceeds to transmit the authorized number of packets toward the destination and waits for the destination to verify their receipt. After the destination successfully receives a packet, it sends a message back to the source containing an acknowledgment indicating the successful receipt of the packet and, in some cases, authorizing the source to send another packet. In this way, the number of packets on the network traveling from the source toward the destination will never be more than the authorized window size.
Neither of these mechanisms, however, satisfactorily deals with the distribution of traffic within the network. Even with these mechanisms in place, on a busy network it is likely that many sources will simultaneously send traffic over the network to more than one destination. If too much of this traffic converges on a single router in too short a time, the limited buffer capacity of the router will be unable to cope with the volume and the router or communication gateway will reject or destroy the packets. When this happens, the network is said to be congested.
Then the network is congested, network performance degrades significantly. The affected sources have to retransmit the lost or rejected packets. Re-transmissions, however, necessarily use network resources such as buffer storage, processing time and link bandwidth to handle old traffic thereby leaving fewer resources for handling those portions of the messages still waiting to be transmitted for the first time. When that occurs, network delays increase drastically and network throughput drops. Indeed, since some network resources are being dedicated to handling re-transmissions at a time when the network is already experiencing a heavy load, there is a substantial risk of the congestion spreading and locking up the entire network.
A variety of alternative approaches exist for dealing with network congestion. Generally, the approaches fall into two categories. One category involves placing limitations on the amount of traffic which will be permitted on the network at any given time. Examples include the preallocation of buffers at the routers to ensure that memory is available to store arriving packets until they can be forwarded. The other category involves methods of limiting the spread of congestion once it occurs and then extricating the network from its congested state. The second category of approaches for dealing with network co
Cheng Shiduan
Li Xiang
Ma Jian
Wu Jing
Nokia Internet Communictions Inc.
Yao Kwang Bin
LandOfFree
Enhancement of explicit congestion notification (ECN) for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhancement of explicit congestion notification (ECN) for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhancement of explicit congestion notification (ECN) for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3229924