§
Luxuse
Patent Intelligence
Sign In
← Back to Patent Explorer
EP0405844A2 Expired / Lapsed EP ⏱️ 0.0 years remaining

Congestion control in computer networks

Assignee: Compaq Computer Holding Ltd
•
Filing: 1990-06-21
•
Granted: —
•
Expires: 2010-06-21
📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

Abstract A known congestion avoidance system for computer networks detects conges­tion at a node output port if the average queue length (integral) over the last congestion cycle plus the current (incomplete) cycle exceeds a fixed constant (taken as 1). (A congestion cycle is a period for which the queue length is 1 or more plus the following period for which the queue length is 0.) The time of arrival or departure of a message is stored at 21, the interval from the previous event is calculated at 22 and 23, the length of the current cycle is incremented at 25 by adding in the interval just determined, and the queue length at 26 is incremented or decremented by 1. The running integral for the current cycle is updated by having added into it the product formed at 27 of the inter­val since the last event (stored at 23) and the current queue length. The inte­grals for the current and previous cycles (stored at 24 and 30) are added and the lengths of those two cycles (stored at 29 and 31) are added, and the first sum divided at 34 by the second to obtain a grand average queue length. If that exceeds a preset value, then a congestion bit is set in messages leaving that node output port. In the present system, the running queue length average (in 29′) is main­tained by adding (at 28′) the queue length (in 26′) into the average at regular intervals determined by timer ticks (from 60) (thus using integer addition instead of integer multiplication), and the grand average compared with the preset value by comparing (at 61) the total of the queue length averages with the total of the cycle periods (thus using integer addition and comparison instead of floating point operation).

Inventors

  • 👤 Stewart Frederick Bryant
  • 👤 Michael John Seaman

Bibliographic Details

Application Number —
Jurisdiction EP
Data Source google_patents
Last Synchronized 2026-10-27 08:39
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/26; H04L47/263; H04L47/12; H04L47/30

Claims Analysis

Total Claims: 8
Claim 1
Independent Claim 131 words
1 Congestion monitoring means for a port of a node (11) in a computer net­work (Fig. 1), comprising means (Fig. 3A; Fig. 4A) for determining, for the current congestion cycle, a running cycle length (24, 25; 24′) and a running queue length average (29; 29′) (the queue length being the number (at 26; 26′) of messages stored (at 16) in the node awaiting transmission through that port and a conges­tion cycle being a period between two successive changes of queue length from 0), and means (32-34; 61) for determining the grand average of queue lengths to queue periods, characterized by timer means (60) generating pulses at regular intervals, and adding means (28′) for adding the queue length into the average at the timer intervals to maintain the running queue length average.
Claim 2
Dependent Claim 131 words
1 Congestion monitoring means for a port of a node (11) in a computer net­work (Fig. 1), comprising means (Fig. 3A; Fig. 4A) for determining, for the current congestion cycle, a running cycle length (24, 25; 24′) and a running queue length average (29; 29′) (the queue length being the number (at 26; 26′) of messages stored (at 16) in the node awaiting transmission through that port and a conges­tion cycle being a period between two successive changes of queue length from 0), and means (32-34; 61) for determining the grand average of queue lengths to queue periods, characterized by timer means (60) generating pulses at regular intervals, and adding means (28′) for adding the queue length into the average at the timer intervals to maintain the running queue length average.
Claim 3
Dependent Claim 29 words
2 Congestion monitoring means according to claim 1, characterized in that the adding means (28′) add a multiple of the queue length into the average on the timer pulses.
Claim 4
Dependent Claim 31 words
3 Congestion monitoring means according to either previous claim, character­ized by means for storing the cycle length (at 30′) and queue length average (at 31′) for at least one previous cycle.
Claim 5
Dependent Claim 23 words
4 Congestion monitoring means according to any previous claim, characterized in that the means for determining the grand average comprise a comparator (61).
Claim 6
Dependent Claim 36 words
5 Congestion monitoring means according to claim 4, characterized in that the or each cycle length and corresponding queue length are stored in combined form by a single register the contents of which represent their difference.
Claim 7
Dependent Claim 48 words
6 Congestion monitoring means according to any previous claim, characterized by an arrivals counter which counts the total number of arrivals during a timer interval and means for adding a predetermined fraction thereof into the running queue length on the timer pulse at the end of the interval.
Claim 8
Dependent Claim 28 words
7 Congestion monitoring means according to any one of claims 1 to 6, charac­terized by means for adjusting the running queue length immediately on an arrival or departure.

References Cited (Backward Citations)

No citation records indexed.

USPTO Annuity & Maintenance Windows

Maintenance schedule is calculated for granted US utility patents.

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag