Electrical computers and digital processing systems: multicomput – Network-to-computer interfacing
Reexamination Certificate
2000-01-07
2004-12-14
Jaroenchonwanit, Bunjob (Department: 2143)
Electrical computers and digital processing systems: multicomput
Network-to-computer interfacing
C370S395420
Reexamination Certificate
active
06832265
ABSTRACT:
BACKGROUND OF THE INVENTION
A typical network router receives and transmits packets in order to transfer these packets along paths within a network. Generally, such a router receives a packet from one portion of the network through a first network interface (i.e., a network port, link, interface device, etc.), and transmits that packet through another network interface to another portion of the network based on routing information associated with that packet, in order to forward or “route” that packet from its source towards its intended destination.
Some network routers receive and transmit packets using interrupts.
FIG. 1
illustrates such a router
20
. The router
20
includes interfaces
22
(e.g.,
22
-
1
, . . . ,
22
-G) and an interconnection mechanism
24
. Each interface
22
includes a receive circuit RC which receives packets
25
from a network (not shown) and a transmit circuit TM which transmits packets
25
to the network. Each receive circuit RC includes a receive queue
32
and a receive interrupt status flag (or bit)
34
. Each transmit circuit TM includes a transmit queue
36
and a transmit interrupt status flag (or bit)
38
. Typically, the transmit queue
36
is smaller than the receive queue
32
. For example, in a Weighted Fair Queuing implementation, the transmit queue
36
may be capable of holding only one or two packets while the receive queue
32
is capable of holding several packets. In other configurations, the transmit queue
36
may be configurable and not necessarily capable of only holding one or two packets.
It should be understood that the respective receive and transmit circuits RC, TM of each interface
22
typically reside together, e.g., as a single device or on a single printed circuit board (PCB). As such, the pair of receive and transmit interrupt status flags
34
,
38
, which belong to the receive and transmit circuits RC, TM of a particular interface
22
, typically reside together in a single memory location or register (e.g., an interrupt status register) which is readable by a single read operation.
The interconnection mechanism
24
includes memory
26
and a processor or central processing unit (CPU)
28
. The memory
26
stores an operating system
30
and software queues
40
which are respective extensions of the transmit queues
36
of the transmit circuits TM. For example, a first software queue
40
temporarily stores packets
25
to be transmitted by a transmit circuit
22
-
1
-TM of a first interface
22
-
1
, a second software queue
40
temporarily stores packets
25
to be transmitted by a transmit circuit
22
-
2
-TM of a second interface
22
-
2
, and so on.
When the router
20
is in a normal operating mode, the operating system
30
directs the processor
28
to perform a procedure
50
to fully attend to each interface
22
in a round robin manner. That is, the operating system
30
directs the processor
28
to select an interface
22
(e.g., interface
22
-
1
), handle any transmit interrupts for the selected interface
22
by moving any packets
25
which are ready for transmission from that interface's software queue
40
to that interface's transmit queue
36
, subsequently handle any receive interrupts for the selected interface
22
by processing packets
25
from that interface's receive queue
32
, and then proceed to handle the next interface
22
(e.g., interface
22
-
2
) in a similar manner. When the processor
28
processes a packet
25
from a receive queue
32
, the processor typically (i) identifies an interface
22
through which to transmit that packet
25
based on routing information associated with that packet
25
(e.g., a destination address residing in the header of that packet), and (ii) moves that packet
25
to the transmit queue
36
of the identified interface
22
if that transmit queue is not full, or to the software queue
40
associated with the identified interface
22
if that transmit queue
36
is full. It should be understood that the processor
28
may or may not be able to respond immediately to the receive and transmit interrupts depending on whether there exists any higher priority tasks or interrupt handlers.
FIG. 2
illustrates further details of this procedure
50
. In step
52
, the processor
28
selects an interface
22
. To this end, the processor
28
reads the contents of a memory location of the selected interface
22
containing the receive and transmit interrupt status flags
34
,
38
of that interface
22
.
In step
54
, if the transmit interrupt status flag
38
of the selected interface
22
indicates that a transmit interrupt is pending for the transmit circuit TM of the selected interface
22
, the processor
28
proceeds to step
56
. Otherwise, the processor
28
proceeds to step
58
.
In step
56
, the processor
28
handles the pending transmit interrupt of the selected interface
22
. Typically, step
58
involves the processor
28
executing a transmit interrupt handler (part of the operating system
30
) for the selected interface
22
. The transmit interrupt handler directs the processor
28
(i) to reset the transmit interrupt status flag
38
of that interface
22
, and (ii) to move any packets
25
residing in a software queue
40
associated with that interface
22
from that software queue
40
to the transmit queue
36
of the transmit circuit TM of that interface
22
.
In step
58
, if the receive interrupt status flag
34
of the selected interface
22
indicates that a receive interrupt is pending for the receive circuit RC of the selected interface
22
, the processor
28
proceeds to step
60
. Otherwise, the processor
28
proceeds to step
62
.
In step
60
, the processor
28
handles the receive interrupt of the selected interface
22
. Typically, in step
60
, the processor
28
executes a receive interrupt handler (part of the operating system
30
) for that interface
22
. The receive interrupt handler directs the processor
28
(i) to reset the receive interrupt status flag
38
of that interface
22
, and (ii) to move any packets
25
residing in the receive queue
32
of the receive circuit RC of that interface
22
to their appropriate software queue
40
.
In step
62
, the processor
28
determines whether it should continue normal operation, i.e., continue to attend to the interfaces
22
. If the processor
28
determines that it should terminate normal operation (e.g., if the processor
28
receives a shutdown or reset command), the processor
28
terminates the procedure
50
. Otherwise, step
62
proceeds to step
64
.
In step
64
, the processor
28
selects another interface
22
. Step
64
then proceeds back to step
54
for another pass of steps
54
through
62
.
It should be understood that each pass of steps
54
through
62
forms a larger step
66
of handling any transmit and receive interrupts for the currently selected interface
22
. Each time the processor
28
performs step
64
, the processor
28
selects a different interface
22
until the processor
28
has selected each interface
22
. Accordingly, the operation of the router
20
essentially involves the steps of selecting an interface
22
, handling any transmit and receive interrupts for that interface
22
, and then repeating these steps for the remaining interfaces
22
to continuously attend to the interfaces
22
such that the processor
28
selects and attends to the interfaces
22
in a round robin manner.
SUMMARY OF THE INVENTION
Historically, a common belief is that a conventional router's processor or CPU is not a major source of performance difficulties. That is, it is commonly believed that the processor is not a bottleneck and that packets do not have a tendency to accumulate within the router. Under this belief, it is viewed that, as fast as the packets arrive at the router, the router selects interfaces and transmits the packets through the selected interfaces. This may be true if the router's packet forwarding paths are simple to determine. For example, this may be true if the router operates accordi
Agasaveeran Saravanan
Gannu Satish
Ma Qingming
Chapin & Huang LLC
Cisco Technology Inc.
Huang, Esq. David E.
Jaroenchonwanit Bunjob
LandOfFree
Methods and apparatus for moving data elements within a data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for moving data elements within a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for moving data elements within a data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3278178