Congestion avoidance on communications networks

Details Congestion avoidance on communications networks Congestion avoidance on communications networks

1998-11-30

2002-08-06

Yao, Kwang Bin (Department: 2664)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

Reexamination Certificate

active

06430155

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention is directed to communications networks. It particularly concerns congestion avoidance.
Internetwork communications are based on operations of routers, which are network devices that determine, on the basis of destination information in packets that they receive, where to forward the packets so that they are likely to reach the intended destinations.
Router configurations vary widely, but
FIG. 1
depicts a typical approach. Router
10
includes a plurality of communications interfaces
12
,
14
, and
16
, which send and receive communications packets to and from remote locations. When one of the interface modules receives an incoming packet, it places header information from that packet onto an internal communications bus
18
by which it communicates with a forwarding engine
20
, typically a high-performance processor and associated storage circuitry, that determines where the packet should be sent. Once the decision has been made, an output packet is formed from the input packet by packet-assembly circuitry that may reside in one or more of the interface modules and/or the forwarding engine, and the forwarding engine causes another interface to send the output packet to a further remote location.
FIG. 2
depicts the router
10
in a local-network environment in which it communicates through one of its interfaces with a local-area-network bus
22
. There are typically a number of network devices, such as network devices
24
,
26
,
28
, and
30
, that receive the resultant signals, but the packet is not usually intended for all of them. To enable its various network devices to distinguish the packets they should read from the ones they should not, a system may employ a packet format such as the Ethernet format that FIG.
3
's second row depicts. An Ethernet frame's link-layer header
32
includes, among other fields, one that contains a link-layer destination address, as FIG.
3
's first row indicates. Any network-device interface whose link-layers address does not match the pocket's destination-address field will ignore the packet.
For present purposes, we will assume that FIG.
2
's router
10
intends for a further router
30
to receive the packet, so the link-layer header's destination-address field contains the link-layer address of router
30
's interface with network link
22
. That interface accordingly reads the remainder of the packet, verifying that the packet and its cyclicredundancy-code (“CRC”) trailer's contents are consistent. Router
30
then proceeds to process the link-layer packet's payload
36
in accordance with a protocol that the link-layer header's type field specifies.
In the illustrated case, the type field specifies that the link-layer packet's payload is an Internet Protocol (“IP”) datagram, which is a network-layer protocol data unit (“PDU”) that consists of an IP header and payload. The IP header is similar to the Ethernet header in the sense that it has source- and destination-address fields. But the destination-address field in this case does not identify the next network node to handle the packet. Instead, it contains a route identifier in the form of the network address of the destination node to which the packet should ultimately be forwarded. That is, a router to which the Ethernet (or other link-level) header directs the packet will read the IP header's destination-address field and identify, on the basis of that field's contents, the “next-hop” router to which forwarding the packet will advance it toward that ultimate destination. Similarly, the IP header's source address does not identify the forwarding router but rather the node that was the IP datagram's initial source.
The IP protocol provides for what is termed an “unreliable” delivery. That is, there is nothing in the protocol itself to ensure that the host with which the packet's internetwork address is associated will actually receive that packet. For various reasons, routers along the way to the destination may not be able to forward that particular packet, so the packet will not reach its destination. The IP datagram's payload may therefore include information that source- and destination-host processes can use to ensure proper information delivery, i.e., to determine whether the destination has received all the source's transmissions and cause the source to re-send any that are missing.
One way to achieve this result is to employ a reliable transport protocol, such as the Internet community's Transmission Control Protocol (“TCP”). Specifically, if the IP header's protocol field contains the code that specifies TCP, the ultimate-destination host will use its TCP process to deal with the IP payload. FIG.
3
's third, fourth, and fifth rows show how the TCP process interprets that payload. Specifically, the IP datagram's payload is considered to be a TCP segment, consisting of a TCP header and a TCP payload. Among its other fields, the TCP header includes source- and destination-address fields, which specify by “port numbers” the host applications that send and receive the TCP payload.
Of particular interest in connection with the transmission's reliability are the TCP header's sequence-number and acknowledgment-number fields. A sequence of TCP segments sent from one port of one node to the same or another port of another node are considered to constitute a single session. If set, a “SYN” flag in FIG.
3
's fifth row indicates that TCP segment containing it is the first in a session. TCP segment containing a set “FIN” flag is the session's last. The sequence-number field in a segment carrying the SYN flag contains a number arbitrarily assigned to the first byte of that session's data. Beginning with that number, the TCP process increments an internal count for each byte sent in each of the same session's (multiple-byte) segments. Each segment's sequence number field contains the sequence number thereby assigned to that segment's first byte.
The receiving TCP process is expected to acknowledge each received segment, and a set “ACK” flag in a segment from the receiving process indicates that the segment's acknowledgment-number field is the next-numbered byte that it expects. Such an acknowledgment means that the receiving process has received bytes associated with all sequence numbers from the SYN-segment sequence number to the number just before the current segment's acknowledgment number.
By its response, a receiving TCP process controls the rate at which the sending process transmits data to it. Specifically, it places in the TCP header's window-size field an indication of the number of bytes the sender can transmit before it has to stop to wait for an acknowledgment. If the receiving TCP process has two kilobytes of capacity left in its input buffer, for instance, it may specify a window size of two kilobytes to ensure that the sending TCP process transmits no more bytes than that before it receives further acknowledgment. If the receiving TCP process acknowledges received bytes only after it has removed them from its input queue, the sender process will not sent the receiver more bytes than its queue can handle. A relatively slow receiving TCP process can thereby prevent a higher-capacity sending TCP process from overwhelming it with data.
But this does not prevent an intervening router from being overwhelmed by the resultant flow or, more typically, by that flow in combination with the others that the router must handle. When a router is overwhelmed, it typically simply discards the excessive IP packets. This discarding does not impair the TCP processes' reliability, because a sending TCP process re-transmits bytes that have remained unacknowledged for more than a predetermined time interval. But discarding packets and re-sending them wastes bandwidth.
To avoid such waste-causing congestion, a TCP sending process often employs what is known as a “slow sta

Affiliated with

Also associated with

Rating

Congestion avoidance on communications networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Congestion avoidance on communications networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Congestion avoidance on communications networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2911051