Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-11-23
2004-08-03
Nguyen, Brian (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S235000, C370S232000
Reexamination Certificate
active
06771652
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer networks, and more particularly to a method and system for controlling discarding and, therefore, transmission of data packets in a computer network.
BACKGROUND OF THE INVENTION
Driven by increasing usage of a variety of network applications, such as those involving the Internet, computer networks are of increasing interest. In order to couple portions of a network together or to couple networks, switches are often used. For example,
FIG. 1A
depicts a simplified block diagram of a switch
10
which may be used in a computer network. The switch
10
couples hosts (not shown) connected with ports A
12
with those hosts (not shown) connected with ports B
36
. The switch
10
performs various functions including classification of data packets provided to the switch
10
, transmission of data packets across the switch
10
and reassembly of packets. These functions are provided by the classifier
18
, the switch fabric
24
and the reassembler
30
, respectively. The classifier
18
classifies packets which are provided to it and breaks each packet up into convenient-sized portions, which will be termed cells. The switch fabric
24
is a matrix of connections through which the cells are transmitted on their way through the switch
10
. The reassembler
30
reassembles the cells into the appropriate packets. The packets can then be provided to the appropriate port of the ports B
36
, and output to the destination hosts.
Due to bottlenecks in transferring traffic across the switch
10
, data packets may be required to wait prior to execution of the classification, transmission and reassembly functions. As a result, queues
16
,
22
,
28
and
34
may be provided. Coupled to the queues
16
,
22
,
28
and
34
are enqueuing mechanisms
14
,
20
,
26
and
32
. The enqueuing mechanisms
14
,
20
,
26
and
30
place the packets or cells into the corresponding queues
16
,
22
,
28
and
34
and can provide a notification which is sent back to the host from which the packet originated.
Although the queues
16
,
22
,
28
and
34
are depicted separately, one of ordinary skill in the art will readily realize that some or all of the queues
16
,
22
,
28
and
34
may be part of the same physical memory resource.
FIG. 1B
depicts one such switch
10
′. Many of the components of the switch
10
′ are analogous to components of the switch
10
. Such components are, therefore, labeled similarly. For example, the ports A
12
′ in the switch
10
′ correspond to the ports A
12
in the switch
10
. In the switch
10
′, the queue
16
and the queue
22
share a single memory resource
19
. Similarly, the queue
28
and the queue
34
are part of another single memory resource
31
. Thus, in the switch
10
′, the queues
16
,
22
,
28
and
34
are logical queues partitioned from the memory resources
19
and
31
.
Conventional methods have been developed in order to control traffic flowing through the switch
10
or
10
′, thereby improving performance of the network in which the switch
10
or
10
′ is used. In particular, a conventional method known as RED (random early discard or detection) is used.
FIG. 2
depicts the conventional method
50
used in RED. The conventional method
50
is typically used by one of the enqueuing mechanisms
14
,
20
,
26
,
32
,
14
′,
20
′,
26
′ and
32
′ to control the traffic through the corresponding queue
16
,
22
,
28
,
34
,
16
′,
22
′,
28
′ and
34
′ respectively For the purposes of clarity, the method
50
will be explained with reference to the enqueuing mechanism
14
and the queue
16
.
At the end of a short period of time, known as an epoch, a queue level of the queue
16
for the epoch is determined by the enqueuing mechanism
14
, via step
52
. Note that the queue level determined could be an average queue level for the epoch. In addition, the queue level determined could be the total level for the memory resource of which the queue
16
is a part. It is then determined if the queue level is above a minimum threshold, via step
54
. If the queue level is not above the minimum threshold, then a conventional transmission fraction is set to one, via step
56
. Step
56
, therefore, also sets the conventional discard fraction to be zero. The transmission fraction determines the fraction of packets that will be transmitted in the next epoch. The conventional discard fraction determines the fraction of packets that will be dropped. The conventional discard fraction is, therefore, equal to one minus the conventional transmission fraction. A transmission fraction of one thus indicates that all packets should be transmitted and none should be dropped.
If it is determined in step
54
that the queue level is above the minimum threshold, then it is determined whether the queue level for the epoch is above a maximum threshold, via step
58
. If the queue level is above the maximum threshold, then the conventional transmission fraction is set to zero and the conventional discard fraction set to one, via step
60
. If the queue level is not above the maximum threshold, then the conventional discard fraction is set to be proportional to the queue level of the previous epoch divided by a maximum possible queue level or, alternatively, to some other linear function of the queue level, via step
62
. Thus, the conventional discard fraction is proportional to the fraction of the queue
16
that is occupied or some other linear function of the queue level. In step
62
, therefore, the conventional transmission is also set to be proportional to one minus the conventional discard fraction. The conventional transmission fraction and the conventional discard fraction set in step
56
,
60
or
62
are then utilized for the next epoch to randomly discard packets, via step
64
. Thus, when the queue level is below the minimum threshold, all packets will be transmitted by the enqueuing mechanism
14
to the queue
16
during the next epoch. When the queue level is above a maximum threshold, then all packets will be discarded by the enqueuing mechanism
14
during the next epoch or enqueued to a discard queue. When the queue level is between the minimum threshold and the maximum threshold, then the fraction of packets discarded by the enqueuing mechanism
14
is proportional to the fraction of the queue
16
that is occupied or some other linear function of the queue level. Thus, the higher the queue level, the higher the fraction of packets discarded. In addition, a notification may be provided to the sender of discarded packets, which causes the-sender to suspend sending additional packets for a period of time. The individual packets which are selected for discarding may also be randomly selected. For example, for each packet, the enqueuing mechanism
14
may generate a random number between zero and one. The random number is compared to the conventional discard fraction. If the random number is less than or equal to the conventional discard fraction, then the packet is dropped. Otherwise, the packet is transmitted to the queue
16
. This process of discarding packets based on the transmission fraction is continued until it is determined that the epoch has ended, via step
66
. When the epoch ends, the method
50
commences again in step
52
to determine the conventional transmission fraction for the next epoch and drop packets in accordance with the conventional transmission fraction during the next epoch.
Because packets can be discarded based on the queue level, the method
50
allows some control over the traffic through the switch
10
or
10
′. As a result, fewer packets may be dropped due to droptail than in a switch which does not have any mechanism for discarding packets before the queue
16
becomes full. Droptail occurs when packets must be dropped because a queue is full. As a result, there is no opportunity to account for the packet's priority in determining whether
Aydemir Metin
Bass Brian Mitchell
Gallo Anthony Matteo
Jeffries Clark Debs
Rovner Sonia Kiang
International Business Machines - Corporation
Nguyen Brian
Sawyer Law Group LLP
LandOfFree
Method and system for controlling transmission of packets in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for controlling transmission of packets in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for controlling transmission of packets in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3343000