Congestion avoidance in high-speed network carrying bursty traffic.

BACKGROUND OF THE INVENTION

0001This invention generally relates to data communication networks, and more particularly to congestion avoidance in networks having links exhibiting long propagation delay and having bursty data flow.

0002Broadband ISDN (integrated services digital network) systems are prone to severe buffer overflow problems at intermediate nodes. Data is thus lost and must be retransmitted, reducing the reliability and capacity of the system. These losses are referred to as congestion loss, but this is not the result of an under-engineered network. Instead, this type of congestion is an inevitable result of the bursty nature of data in asynchronous (packetized) information transfer.

0003In narrowband packet networks, feedback control mechanisms are able to manage the traffic load so that buffer overflow can be mostly avoided, or at least controllable. For example, networks based upon the so-called X.25 protocol provide two levels of flow control; one controls all traffic across the physical link, and another layercortrols traffic across one virtual circuit. Each layer's protocol provides both a window-based flow manager and a stop/go control mechanism. That is, a node having data to send is allocated a window of fixed time, per unit time, and, in addition, the node can be shut off for a time period when capacity is all allocated.

0004Connectionless networks, such as those using certain DECnet and DDN Internet Protocol, do not have positive controls as in X.25, but still provide positive feedback mechanisms. For example, "implicit" feedback mechanisms focus on sequence numbers in the packets; if a packet is dropped (as may be inferred from a gap in acknowledged sequence numbers) it may be determined that congestion is severe and so the sender drastically reduces its sending rate (as by reducing the window size). Or, "explicit" mechanisms provide warning of incipient congestion, so that senders can usually reduce their rate before any packets are lost; thus there is still feedback, but the data terminals are more responsible for responding to it

0005Broadband asynchronous transfer mode (ATM) networks often have links that span large distances, thousands of miles in many cases. Here the propagation delay is too long to allow feedback to be effective. The delay from the time a packet is sent to the time it is received at the destination is much longer than the time during which congestion can cause buffers to fill in intermediate nodes, so data is lost By the time the loss is recognized and a feedback signal sent back to the sender, it is too late to alter the sending rate or otherwise change the input to prevent congestion.

0006It is not sufficient to use any of the common feedback schemes, including credit managers, windows, etc., across long-delay ATM networks. While some of these techniques are quite appropriate for short-haul ATM applications, they lose effectiveness when the buffer fill time falls well below the propagation delay in the link. The exact point at which feedback delay becomes unacceptable depends upon the degree of burstiness of the traffic; if the bulk of traffic is constant, then a somewhat longer delay can be tolerated before loss occurs. Highly bursty traffic is more sensitive.

0007In a typical network, therefore, at least two types of bandwidth allocation are needed. A simple credit- based buffer allocation scheme is likely to be quite adequate for certain applications - those links that have short propagation delay. The receiving end of each link monitors the buffers available to each virtual path and/or virtual channel and grants credits to the sending end. This may be somewhat cumbersome when the number of virtual paths is quite high, but in practice credits are allocated back to each virtual path or channel based upon availability of buffers for the links going out of the node. Some amount of receive buffer may be useful in order to permit a node to accept all traffic arriving at one incoming link when there is a disparate buffer fill situation at its outgoing links. Nonetheless, this transmission discipline is simply a form of conventional hop-by-hop management, and is not dis-similar from what is found on conventional connection-oriented packet networks. These links may not need a more complex scheme such as is described below. A more complex discipline is only required when the dimensions of the network cause propagation delays to become longer than allowable feedback times.

0008There are two causes of congestion loss, funnelling and mismatch. A packet-switched network can lose its protocol data units (cells, frames or packets) when the arrival rate at any given point exceeds the departure rate for a long enough period of time that a buffer overflows. This can occur for either of two separate and identifiable reasons. Funnels occur when several different paths converge on a single buffer, and traffic bursts arrive closely spaced in time, such that overflow occurs. Funneling is generally transient. Mismatch occurs when sustained demand for a given facility exceeds its capacity; for example, when a high-speed link meets a lower-speed link, or when an additional virtual circuit is created over a busy facility. A congestion management scheme must be able to handle both mismatch and funneling. However, defe- rent techniques tend to be more effective for one or the other. Admission control policies, coupled with stringent network-wide resource allocation and a minimum of oversubscription, can minimize mismatch. Connectionless networks require feedback to control mismatch loss, as they rarely if ever provide rate-based control. Traditional packet networks are usually rathertolerant offunneling loss. An occasional dropped packet can be recovered. ATM networks, however, may use protocols that are prone to loss multiplication; a single dropped cell can corrupt an network having multiple nodes, comprising the steps of: a) sending from a first of said nodes to a first intermediate one of said nodes a request for an allocation of bandwidth for a transmission of a quantity of data from said first node to a second one of said nodes via said first intermediate node and a second intermediate node; characterized by: b) comparing said request in said first intermediate node with capacity at said first intermediate node to meet said request, and generating a modified request to reduce said allocation if necessary; c) sending said modified request from said first intermediate node to said second intermediate node; d) comparing said modified request in said second intermediate node with capacity at said second intermediate node to meet said modified request, and generating a second modified request to reduce said allocation if necessary; e) sending said second modified request back to said first node; and f) transmitting said quantity of data from said first node to said second node using the bandwidth specified in said second modified request.

0009The invention also consists in a communications network having multiple nodes, comprising: a) a transmitter sending from a first of said nodes to a first intermediate one of said nodes a request for an allocation of bandwidth for a data transmission from said first node to a second one of said nodes via said first intermediate node and a second intermediate node; b) means for comparing said request in said first intermediate node with capacity at said first intermediate node to meet said request, and for generating a modified request to reduce said allocation if necessary, said modified request being sent from said first intermediate node to said second intermediate node; c) means for comparing said modified request in said second intermediate node with capacity at said second intermediate node to meet said request, and for generating a second modified request to reduce said allocation if necessary, said second modified request being sent back to said first node; d) said transmitter sending data from said first node to said second node using the bandwidth specified in said second modified request.

0010In accordance with one embodiment of this invention, a data communication network of the type subject to bursty traffic and having long-delay links employs an asynchronous transfer mode in which small, fixed-length blocks of information (cells) are transferred at very high speed. The network employs a bandwidth allocation scheme to avoid congestion. When a source node has a burst of traffic to send, it first sends a bandwidth request message through the network from source to destination. At each intermediate node, this bandwidth request is examined and the node determines how much of the requested traffic level it will be able to support by reservation at a time in the future of one round-trip interval hence, and this node either grants the request or marks down the request to a level that it can support, then passes it on. When the request reaches the destination, it is returned along the same path to the source, and the source then employs the marked-down allocation to select the rate used to send the burst of data. The allocation for this source node remains in effect for a limited time, depending upon the amount of data to be sent in the burst, then returns to a -residual- level.

BRIEF DESCRIPTION OF THE DRAWINGS

0011The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as other features and advantages thereof, will be best understood by reference to the detailed exemplary description of specific embodiments which follows, when read in conjunction with the accompanying drawings, wherein: <ul id="ul0001" list-style="none"><li>Figure 1 is an electrical diagram in block form of a communica- tions network in which one embodiment of the invention may be utilized;</li><li>Figure 2 is an electrical diagram in block form of one of the nodes in the network of Figure 1;</li><li>Figure 3 is a diagram of the format of a packet which may be employed in some links of the network of Figure 1;</li><li>Figure 4 is a timing diagram of the format of a frame or synchronized loop which may be employed in a long-delay link of the network of Figure 1, according to the PTM technique;</li><li>Figure 5 is a diagram similar to Figure 1 of a part of a network having two long-delay links; and</li><li>Figure 6 is a timing diagram of a series of the frames of Figure 4 transmitted by one node of Figure 5 and received by another node;</li><li>Figure 7 is a timing diagram of an allocation request message used in the network of Figure 1 or 5, according to a feature of the invention; and</li><li>Figure 8 is a diagram of message traffic as a function of time in a system of Figures 1 or 5.</li></ul>

DETAILED DESCRIPTION OF SPECIFIC

EMBODIMENT

0012Referring to Figure 1, a communications network is illustrated having a communications link 10 between a pair of nodes 11 and 12. The link 10 is a trunk facility, where the link 10 must carry traffic between a large number of nodes 13 connected to the node 11 by links 14 and a large number of nodes 15 connected to the node 12 by links 16. In turn, the nodes 13 and 15 are connected to other nodes 17 and 18. Thus, because of the fan-in of a number of nodes to the nodes 11 and 12, the link 10 must have much greater capability than the link 19 between nodes 13 and 17, for example. The link 10 may be a satellite link, orfibre optic link, which may span hundreds or thousands of miles, and would have a speed of perhaps 600- as a transmit buffer 33 for the outgoing line 20 of the link 10. Although shown as separate transmit and receive buffers, these functions may be combined. The controllers 28 or 29 are responsive to decoded command information in signals, cells or packets on the incoming lines 25 or 21 to activate the receivers 27 or 23 to start loading the respective buffers 30 or 31 with the incoming data, as well as to route the received data to be transmitted at one of the other ports. As seen in Figure 3, a cell 34 by which information may be conveyed from a node 13 to the node 11 is illustrated. This cell 34 is delineated by the underlying service, or by some element within the header (i.e., the header checksum). The cell begins with a header 35 which includes a virtual channel identifier 36, a control area 37 and a header checksum 38 used to verify the integrity of the header and of the framing. The payload field 39 is the major part of the cell 34. The controller 28 for a port to a link 14 is responsive to thevirtual channel identifier36to control the routing of the incoming cell through the switching network 43 to attempt to pass the cell from one port to another in order to effect the virtual channel between source and destination. When there is a difference in bandwidth between the links 14 and the link 10, for example, the switching network 43 may include a multiplexer 44 to allow more than one link 14 to funnel into the link 10; likewise, a multiplexer 45 may allow simultaneous delivery of data from link 10 to more than one of the links 14. Similarly, the ports for links 14 may have multiplexers 46 and 47 so that data from or to multiple ports may be interleaved. Alternatively, the data may be interleaved by merely reading and writing between buffers 30-33 one word at a time via the switching circuit 43. In any event, a message frame is made up in transmit buffer 33, for example, by the controller 29, and this frame may contain interleaved packets or cells from many different terminals 17, going to many different terminals 18.

0013Referring to Figure 4, a message frame 50 used in the PTM technique is illustrated. This frame 50, employed for transmission on the link 10 in one example, is of fixed length 51 and is made up of a large number of slot cells 52. In an exemplary embodiment, the slot cells 52 each contain fifty-three octets (424-bits), and there are 2119 cells in a frame 50 of 6- millisecond length 51, transmitted at a rate of about 150-Mbps. A slot cell 52 contains a data field 53 of 48- octets and a header 54 of five octets; the header includes a channel identifying number associated with a particular transmission from a source to a destination node. The first two cells of the frame 50 are sync cells 55; these sync cells delimit each frame 50 which is sent during a loop control period. At least two sync cells 55 are sent at the beginning of each frame. Sync cells are identified by a specific header address, and each contains a pointer to the first slot in the control period (i.e., the first data cell 52 in the frame) which follows sync and slip cells. (The second sync cell contains a pointer value of one lower than the first sync cell.) At least one slip cell 56 follows the sync cells; a slip cell contains no information, other than a header address identifying it as a slip cell. These slip cells exist only to be added or discarded, as required, to synchronize the two sides of a loop (in node 11 and node 12, for example) when they are not running at identical speeds. Typically one slip cell 56 is sent after the sync cell 55, but a second will be added, orthe one will be deleted, as required. The slot cells 52 are the ones assigned to carry slotted traffic, each having a valid virtual channel identifier in its header 54. Slot cells are carried with priority over free cells, and are allocated using control cells. A free cell 57 is an unallocated cell, and may be empty, in which case its header carries a virtual channel identifierforan empty cell, or may carry traffic for which no slot is assigned; this unallocated traffic is carried on a best-effort basis and may be discarded in favor of slot cells when allocated traffic appears. Finally, a control cell 58 is one that carries information (control signals, commands, etc.) between the two ends of the loop, e.g., from node 11 to node 12. A control cell 58 is identified by a specific virtual channel identifier in its header 59 (which may be locally assigned). Control cells carry messages that indicate that a given time slot within the basic control period of the frame 50 has been assigned to carry traffic on behalf of a given virtual channel, or has been freed. A protocol is defined for sending these messages in control cells, and the controller 29 generates these cells for sending via transmitter 22.

0014The frames 50 are timed by a separate dock 60 in each node 11 or 12. These docks are stable crystal oscillators which maintain sufficient accuracy to synchronize the repetition of frames 50 at each end of a link 10. Since the time period 51 of a frame 50 is some multiple of 6-millisecond, this level of accuracy is well within that of currently-available crystal oscillators, or other methods of establishing a stable time reference. The bit rate, about 150-Mbps (or 600-Mbps, depending upon the network), is established by the oscillator 60, and the octet, cell and frame rates may be obtained by counting down from the bit rate clock, or from external synchronization sources, i.e., a network master clock.

0015Referring to Figure 5, an example of connection establishment is illustrated where a seven-hop connection (including two local loops) is shown between two of the terminals 17 and 18, labelled Y and Z in this example. Nodes 11, 11a and 12 are of the type shown in Figures 1 and 2, using the framing loops of Figure 4 in links 10 and 10a the link 10 is assumed to have an 11-millisecond one-way propagation delay, synchronized at four base periods or 24-ms. with 8192 slots 52 in a frame 50, while link 10a is assumed to have a 2-ms. one-way propagation delay, synchronized at one base period of 6-ms with 2048 network. The BWquo field 67 is the bandwidth extension quota, which is the amount that the network actually grants. This value is initially set by the originating terminal 13 to be equal to BWext but may be lowered by any of the intermediate nodes 11,11a,12, etc., before being returned to the originator by the network. The duration field 68 is the amount of time that the descriptor should remain in effect, which is ideally expressed as a number of cells. While a time-based descriptor could be used, it would have to be extended by the network if the request BWextwere reduced to a lower BWquo, since it would take longer to send the pending traffic.

0016Every node within a network such as that of Figure 5 also determines, at connection establishment, the total end-to-end transit delay across the network and its own relative position within the link (i.e., how many ms. from each end). When a message or bandwidth request descriptor or cell 64 is issued, this procedure is followed: (1.) The originator (e.g., node 13) sends a bandwidth descriptor 64 across the link towards the destination terminal Z. This cell 64 is identified as a user-to-network cell by its header 69. (2.) As the cell 64 travels towards the destination (using the transport mechanism of Figure 5, for example), each node 11, 11a 12, etc., determines how much of the requested bandwidth in BWext it can provide exactly one round-trip interval hence. If it cannot provide at least as much as the current BWquo in field 67 (which is being marked down as the descriptor 64 travels towards the destination), it puts a new value in BWquo field 67. No node may raise the value in BWquo field 67 as the cell 64 traverses the network. (3.) At the egress node (E in Figure 5), the descriptor 64 is returned along the same path by which it arrived. Each node (12,11 a, 11, etc.) on the return path notes the remaining (marked down) value of the BWquo field 67, but does not further change it; this value is stored in a table of all current traffic, identified by the channel number in the field 65, so that the controller 29 can check subsequent slotted cells for validity and also keep track of allocated capacity when making allocation for subsequent requests 64. (4.) When the descriptor 64 returns to its originator node 13, the bandwidth described in BWquo field 67 becomes available for immediate use by the terminal Y, for the time period of the duration field 68.

0017The concept of a virtual path instead of a virtual channel may be used to minimize node complexity. The total number of virtual channels between any two nodes such as Y and Z in a network is likely to frequently exceed one, e.g., when more than one message is pending. Some economization may take place by allocating bandwidth descriptors 64 to virtual paths instead of virtual channels. There can be only one virtual path between two nodes Y and Z. A virtual path, in this case, is a special form of channel that contains within itself multiple user virtual channels. The total number of virtual paths within a network is thus limited to the square of the number of nodes, regardless of the number of virtual channels requested by users. Access nodes can map each virtual channel into the appropriate virtual path, and intermediate nodes need only keep track of virtual paths (as well as any virtual channels that are locally terminated).

0018Referring to Figure 8, a chart of the allocated traffic in one link 10, for example, as a function of tine, shows that as the number of requested allocations from the remote nodes changes the allocated traffic level follows a line 71, rising and falling as the requests ebb and flow. A line 72 represents the limit imposed by the capacity of the link, determined by the physical construction, software, etc. During a peak in traffic, when the requested allocations from the remote terminals tend to exceed the limit 72 to follow the line 73, the controller imposes reduced (instead of requested) allocations on all remotes so the real traffic follows the line 74, below the limit 72, instead of the line 73. All network traffic is at a lower level than requested for a time period 75, until the line 76 rejoins the request curve 77 when all delayed requests have been made up. In this manner, network congestion during the peak period 75 is merely exhibited to the remote terminals as a slowing of the apparent response of the network, rather than as loss of data requiring retransmitting sequences of messages. Retransmission occurrences not only markedly reduce the apparent speed of the network from the terminals standpoint, but also reduce the real capacity of the network since traffic is transmitted more than once.

0019While this invention has been described with reference to specific embodiments, this description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiments, as well as other embodiments of the invention, will be apparent to persons skilled in the art upon reference to this description. It is therefore contemplated that the appended claims will cover any such modifications or embodiments as fall within the true scope of the invention.