Method for determining network congestion and link capacities

#The present invention relates to a scheme for determining congestion conditions in a communication network using characteristics of an invariant distribution of packet round trip times in such a network. Based on these congestion conditions, a control node of the network can be operated in such a way so as to reduce packet loss in the network.

#Many communication networks, such as the Internet, rely on packet switching technologies (e.g., X.25, frame relay, asynchronous transfer mode, etc.) to transport variable or uniform blocks (usually termed packets or cells) of data between nodes. The term packet will be used herein to collectively refer to any such block of information. Such networks generally perform two major functions: routing and congestion control. The object of routing is to deliver, correctly and sometimes in sequence, the packets from a source to a destination. The object of congestion control is to maintain the number of packets within the network (or a region or sub-network thereof) below a level at which queuing delays become excessive. Due to finite resources, packets may be dropped rather than queued.

#In essence, a packet switched network is a network of queues communicatively coupled together by communication links (which may be made up of various physical media). At each network node (e.g., a switch or router), there exist one or more queues of packets for each outgoing link. If the rate at which packets arrive and queue up exceeds the rate at which packets are transmitted, queue size grows without bound and the delay experienced by a packet tends towards infinity.

#The present invention is illustrated by way of example, and not limitation, in the figures of the accompanying drawings in which like reference numerals refer to similar elements and in which:

#FIG. 1 shows the Fourier power spectrum of traffic generated from a Pareto distribution of file sizes that is not subjected to the TCP protocol.

#FIG. 2 shows the Fourier power spectrum of uncongested and under-supplied traffic that is subjected to the TCP protocol.

#A scheme for determining network congestion conditions is disclosed herein. As discussed in greater detail below, the present scheme allows for estimating the particular congestion conditions of downstream communication links as well as the congested bandwidth characteristics, regardless of whether the congestion is self-induced or cross-induced. Although discussed with reference to certain illustrated embodiments, upon review of this specification, those of ordinary skill in the art will recognize that the present scheme may find application in a variety of systems. Therefore, in the following description the illustrated embodiments should be regarded as exemplary only and should not be deemed to be limiting in scope. It should also be noted that as used herein the term “packet” is meant to broadly refer to packets, cells and other forms of information units used to transport data and/or control information within communications infrastructures (e.g., computer networks, telecommunications networks, data communication networks and the like, for example, the Internet) wherein resources are shared among multiple users and multiple information or traffic streams. The present control techniques may be applied at a per connection, per traffic stream or other level.

#Sources of congestion within a network can be understood with reference to FIG. 4. Shown in this illustration is a router (or other network node, such as a switch, bridge, etc.) 10, which is connected in a communication path between a traffic source of interest, such as Web server 16 and one or more clients 201, 202, . . . , 20n. A control or monitoring point 12 (which is discussed in greater detail below) may be connected between the content source 16 and the congested node 10, for example via communication links 14 and 24. In some cases, the functionality of control point 12 may be included within router 10 and/or Web server 16. Communication with the clients 20 from router 10 may be over one or more communication links 22.

#The connections that exist through router 10 generally will not have equal bandwidths. That is, some bandwidth mismatch will often occur at nodes such as router 10. Often the communication link coupling the network node to the content source (i.e., link 24 in this example) will have a greater bandwidth than the communication link coupling the node to a client (i.e., link 22 in this example).