Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-04-11
2004-01-06
Olms, Douglas (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S412000, C710S052000
Reexamination Certificate
active
06674718
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer networks, and more particularly to a method and system for improving control over and resource allocation for a computer network, particularly a computer network capable of providing differentiated services.
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 high-level block diagram of a switch
10
which can be used in a computer network. The switch
10
includes a switch fabric
3
coupled with blades
7
,
8
and
9
. Each blade
7
,
8
and
9
is generally a circuit board and includes at least a network processor
2
coupled with ports
4
. Thus, the ports
4
are coupled with hosts (not shown). The blades
7
,
8
and
9
can provide traffic to the switch fabric
3
and accept traffic from the switch fabric
3
. Thus, any host connected with one of the blades
7
,
8
or
9
can communicate with another host connected to another blade
7
,
8
or
9
or connected to the same blade.
FIG. 1B
depicts a high-level block diagram of one embodiment of a network processor
2
. The network processor
2
includes an ingress switch interface (ingress SWI)
11
, an ingress enqueue/dequeue/scheduling logic (ingress EDS)
12
, an embedded processor complex (EPC)
13
, an ingress physical MAC, multiplexer (ingress PMM)
14
, and egress physical MAC multiplexer (egress PMM)
15
, an egress enqueue/dequeue/scheduling logic (egress EDS)
16
and an egress switch interface (egress SWI)
17
. The network processor
2
may also contain other storage and processing devices. The ingress SWI
11
and egress SWI
17
are coupled with the switch fabric
24
(depicted in
FIG. 1A
) for the switch
10
. Referring back to
FIG. 1B
, the EPC
13
includes a number of protocol processors plus co-processors. The ingress EDS
12
and egress EDS
16
can perform certain enqueuing, dequeuing and scheduling functions for traffic traveling from devices, such as Ethernet devices, to the switch fabric and for traffic traveling from the switch fabric to the devices, respectively. The ingress SWI
11
and egress SWI
17
provide links for connecting to other devices, such as another network processor or switch (not shown in FIG.
1
B). The ingress PMM
14
and egress PMM
15
receive traffic from and transmit traffic to, respectively, physical layer devices.
FIG. 2A
depicts another simplified block diagram of the switch
10
, illustrating some of the functions performed by network processors
2
. Although some of the functions are performed by the same components as shown in
FIG. 1A
, these components may be labeled differently. For example, for the purposes of explaining the path of traffic through the switch
10
, the switch fabric
3
of
FIG. 1A
is depicted as switch fabric
26
in FIG.
2
A. The switch
10
couples hosts (not shown) connected with ports A
18
with those hosts (not shown) connected with ports B
36
. Thus, the switch
10
allows packets of data to be transferred from the source to the destination. Data packets could include a number of different types of data packets. For example, Ethernet packets (usually termed frames), ATM packets (usually termed cells) and IP packets (usually termed packets) will all be packets herein. 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
22
, the switch fabric
26
and the reassembler
30
, respectively. The classifier
22
classifies packets which are provided to it and breaks each packet up into convenient-sized portions, which will be termed cells. The switch fabric
26
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. The classifier
19
may be part of one network processor
1
, while the reassembler
30
may be part of another network processor
5
. The portions of the network processor
1
and the network processor
5
depicted perform functions for traffic traveling from ports A
18
and to ports B
36
, respectively. However, the network processors
1
and
5
also perform functions for traffic traveling from ports B
36
and to ports A
18
, respectively. Thus, each network processor
1
and
5
can perform classification and reassembly functions. Furthermore, each network processor
1
and
5
can be a network processor
2
shown in
FIGS. 1A and 1B
.
Referring back to
FIG. 2A
, 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
20
,
24
,
28
and
34
may be provided. Coupled to the queues
20
,
24
,
28
and
34
are enqueuing mechanisms
19
,
23
,
27
and
32
. The enqueuing mechanisms
19
,
23
,
27
and
32
place the packets into the corresponding queues
20
,
24
,
28
and
34
and can provide a notification which is sent back to the host from which the packet originated. The classification, enqueuing, and scheduling functions are preferably provided by the ingress EDS
12
and egress EDS
16
in the network processor depicted in FIG.
1
B. Referring to
FIGS. 1B and 2A
, the enqueuing mechanisms
19
and
23
, the queues
20
and
24
, the classifier
22
and the schedulers
21
and
25
are controlled using the ingress EDS
12
. Similarly, the enqueuing mechanisms
27
and
32
, the queues
28
and
34
, the reassembler
30
and the schedulers
29
and
35
are controlled using the egress EDS
16
.
Also depicted in
FIG. 2A
are schedulers
21
,
25
,
29
and
35
. The schedulers control the scheduling of individual packets which are to leave the queues
20
,
24
,
28
and
34
, respectively. In general, the concern of the present application is the egress portion of the network processor
2
, depicted by egress PMM
15
, egress EDS
16
and egress SWI
17
in FIG.
1
B. Thus, referring back to
FIG. 2A
, one focus of the present invention includes the scheduler
35
which controls the traffic to ports B
36
. Consequently, for clarity, the function of schedulers is discussed with regard to the scheduler
35
and the queue
34
. Typically, the scheduler
35
is provided with information relating to each packet in the queue
34
. This information may include the type of the packet, such as a real-time packet for which time of transmission is important, or a data packet for which the speed of transmission is not important. Based on this information and other information provided to it, the scheduler
35
determines each individual packet in the queue
34
will be removed from the queue and sent on towards its destination. For example, the scheduler
35
may include one or more calendars (not shown), each including a number of positions, and a weighted fair queuing ring (not shown) including another number of positions. The scheduler
35
may place certain packets in the calendar and other packets in the ring. The scheduler allocates a certain amount of time to each position in the calendar. Each position in the calendar can have a single packet, typically represented by an identifier, or can be empty. When the scheduler reaches a certain position, a packet placed at that position will be retrieved from the queue and sent toward its destination. If, however, the position in the calendar is empty, the scheduler
35
waits until a particular amount of time has passed, then moves to the next position in the calendar. Similarly, the scheduler
35
places other packets in positions of the weighted fair queuing ring of the scheduler
35
.
Heddes Marco C.
Jeffries Clark Debs
International Business Machines - Corporation
Munoz-Bustamante Carlos
Olms Douglas
Phunkulh Bob A.
Sawyer Law Group LLP
LandOfFree
Unified method and system for scheduling and discarding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Unified method and system for scheduling and discarding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unified method and system for scheduling and discarding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222011