Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus interface architecture
Reexamination Certificate
1999-11-29
2002-11-19
Thai, Xuan M. (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus interface architecture
C710S052000
Reexamination Certificate
active
06484224
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of computer systems for data communications networks. More particularly, the present invention relates to a symmetric multiprocessor system having a plurality of interface devices, and a method for operating the system.
2. The Background
Routers are an essential element of internetworks, an example of which is the Internet. Routers allow (or deny, if necessary) communications between LANs (local area networks) and WANs (wide area networks). Routers transfer packets of data from one network to another and one major task of routers is the switching and forwarding of data packets. A router receives many packets through its multiple interfaces, and a network input/output (NetIO) process (program) and/or port ASIC (application specific integrated circuit) handles incoming packets received on inbound interfaces and outgoing packets sent to outbound interfaces. A router also performs other processes such as configuration, management, maintenance and updating of the system.
Recent rapid expansion of data communications networks has brought pressure for higher performance in network devices such as routers and switches in order to handle the increasing network traffic load. One solution for realizing improved performance of a computer system or a network device, such as a router, is to provide the system with a plurality of microprocessors (CPUs) that execute individual processes simultaneously. Such a microprocessor system, in which a number of microprocessors share memory, I/O (input/output) devices, and other resources, is called a symmetric multiprocessing (SMP) system. A SMP system typically uses a single operating system (OS) to control the microprocessors and a high-speed bus to provide communication among the components of the SMP system. Any idle processor in a SMP system can be assigned any task or process and additional microprocessors can be added to improve the performance of and deal with increased loads on the SMP system. The task of parceling out processes to each component microprocessor of the SMP system may be handled by the OS of the system or by an application program running outside the OS. Although symmetric multiprocessing can produce significant performance gains under ideal conditions, the resources of the system must be allocated to the concurrently running processes in a reasonable manner. In addition, overhead increases as more microprocessors are added to the system.
Multithreading of a process (or task) also generally provides improved performance of a computer system. Multithreading allows different parts (threads) of a single program or process to be executed simultaneously. A thread is a portion of a program or process that can operate independently of other portions of the program or process. In a multithreaded application, all the threads can run at the same time without interfering with one another, if so programmed. In a multiprocessor system, the OS, which is capable of executing such a multithreaded program, allots the threads of the program to the microprocessors. However, it is often difficult to divide a program in such a way that separate microprocessors can execute different portions of it without interfering with one another.
If a router utilizes a SMP system (without multithreading), the processes performed by the router can be executed concurrently by several microprocessors. For example, a NetIO process may run on one microprocessor, while other processes may run on other microprocessors. However, if the NetIO process restricts itself to single-threaded operation, its input/output performance is limited by the microprocessor executing NetIO process. The process drops packets when it is overloaded despite the fact that there may be a number of idle microprocessors in the SMP system which could, but are not adapted to handle the load. Alternatively, the NetIO process can be multithreaded so that each thread is processed by an available microprocessor. For instance, a first packet received on an interface is handled by a first microprocessor, the following packet is handled by a second microprocessor while the first microprocessor is busy processing the first packet, and so forth.
In this scenario of a multithreaded NetIO process, each interface of the router can be used by any of the available microprocessors at any time. A NetIO forwarding process typically receives a packet on an inbound interface, switches the packet based on its destination address, and sends the packet to an outbound interface. Thus, one switching and forwarding process for a packet usually involves an inbound and an outbound interface, the result being that each of the microprocessors executing the NetIO process may have to access any interface of the router. Therefore, it is necessary to adopt some measure such as a mutex or scheduler to prevent more than one microprocessor from accessing the same interface at the same time. That is, the “right to use” each interface device must be dynamically allocated among the microprocessors and must not overlap. For example, using a scheduler, a process thread on each microprocessor is “awakened” when the interface becomes available to that microprocessor. However, this approach has the undesirable effect of dramatically slowing the router's switching performance.
Moreover, the multithreaded NetIO process may cause another problem known as “packet reordering” when successive packets arriving at an interface constitute a unit of information such as a single data file or an audio or video stream. When the first arriving packet is handled by a first microprocessor and the following packet by a second microprocessor, the second microprocessor may reorder the packets either because it thinks that the second packet should have arrived before the first packet or simply because it completes its task before the first microprocessor. When the reordered packet arrives on the interface, a third microprocessor, rather than the second microprocessor, may handle that third packet, resulting in another potential packet reordering. If the NetIO process is to avoid having more than one microprocessor handle the different interfaces, it is required to perform context switching (forcing one microprocessor to handle a particular packet stream so as to maintain packet ordering within the stream). Such context switching also significantly increases overhead and thus lowers the observed performance of the router or switch.
BRIEF DESCRIPTION OF THE INVENTION
A symmetric multiprocessor system includes a first processor and a second processor for executing a multi-threaded process on packets, a first inbound interface and a first outbound interface associated with the first processor, a first task queue accessible for reading by the first processor, a second inbound interface and a second outbound interface associated with the second processor, and a second task queue accessible for reading by at least the first processor. The first inbound interface receives incoming packets and has a first input buffer maintaining a first input queue of the packets for processing by the first processor. The first outbound interface receives packets from the first processor and transmits outgoing packets. The first task queue receives packets output from at least the second processor and maintains another input queue of the packets for processing by the first processor and which are outgoing from the first outbound interface. The second inbound interface receives incoming packets and has a second input buffer maintaining a second input queue of the packets. The second outbound interface receives packets from the second processor and transmits outgoing packets. The second task queue receives packets output from at least the first processor and maintains another input queue of the packets for processing by the second processor and which are outgoing from the second outbound interface. The first processor executes a process thread on packets by requesting the packets from
Kon Ronnie B.
Robins Kristen Marie
Ando Masako
Cisco Technology Inc.
Thai Xuan M.
Thelen Reid & Priest LLP
LandOfFree
Multi-interface symmetric multiprocessor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-interface symmetric multiprocessor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-interface symmetric multiprocessor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2992514