Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-10-15
2004-02-24
Dharia, Rupal (Department: 2141)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S236000, C709S244000, C370S351000, C370S384000, C370S388000, C370S464000, C340S870030
Reexamination Certificate
active
06697872
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to computer networks, and more particularly, to processing packets within a network.
A network is typically a data communication system which links two or more computers and peripheral devices to allow a user on a computer to access resources and exchange messages with users on other computers. Internetworking is the process of establishing and maintaining communications between and transferring data among multiple local networks in a distributed network system. The network allows users to share resources on their own systems with other network users and to access information on centrally located systems or on systems which are located at remote offices.
A network system typically includes a plurality of routing domains which are each collections of networks under a common administration which share a common routing strategy. Each routing domain includes one or more local networks which are attached to one or more routers. The local network in a routing domain may be a local area network (LAN), metropolitan area network (MAN), or wide area network (WAN), for example. The system includes source and destination nodes (end systems) which are typically computers (e.g., workstations and servers) but may be any type of device which includes a network interface card (NIC).
The routers within the routing domain manage communications among local networks within their domain and communicate with each other using an intradomain routing protocol. The routers transfer information to and from the end systems and among themselves along communication links in formatted packets. When an originating end system wants to transmit information to a destination end system, it generates a packet header in an appropriate format which includes the address of the destination end system, and then fills the remainder of the packet with the information to be transmitted. When a router receives a data packet, it reads the packet's destination address from the packet header and then transmits the packet on the link leading most directly to the packet's destination. Along the path from source to destination, the packet may be transmitted over several links and pass through several routers.
The routers typically utilize three layers (physical, data link, and network) of an OSI protocol stack to forward data packets to the next router or destination end node. The protocol stacks are physically connected through communication channels at the physical layer. The physical layer is directed to the physical and electrical specifications of a physical link, such as a bus which couples the computers of a network to one another. It controls bit transmissions through the link so that a series of bits of a data packet can be communicated from one computer on the network to another computer on the network. The physical layer transmits a raw data bit stream over a communication channel, while the data link layer manipulates the bit stream and transforms it into a data stream. The data link layer is directed to the packaging or framing of bits received in a data transmission into a defined packet which is free of transmission errors. It creates and recognizes boundaries between bits to define bit fields. The data link layer also ensures orderly coordination of the use of shared media, and handles addressing when multiple systems are reachable.
The network layer enables any pair of systems in the network, such as a source node and a destination node, to communicate with each other. The network layer is directed to the control of routing information required to direct a message from a source computer to a destination computer of the network. Also included in the OSI protocol stack is a transport layer, session layer, presentation layer, and application layer.
Data transmission over the internetwork consists of generating data in, for example, a sending process executing on the source node, and passing that data to the application layer and down through the layers of the protocol stack where the data is sequentially formatted as a packet for delivery onto the channel as bits. Those packet bits are then transmitted to the protocol stacks of the routers, and finally to the stack of the destination node, where they are passed up to a receiving process.
Routers are typically configured to handle either a single protocol such as Transmission Control Protocol/internet Protocol (TCP/IP), or multiple protocols. Packets are routed across routers configured for different protocols by using encapsulation, which is the insertion of one protocol's packet into another protocol's packet. For example, it is possible to encapsulate NetWare Internetworking Packet Exchange (IPX) packets into TCP/IP packets and transmit them over a TCP/IP network. The routers are used to decapsulate and encapsulate the packets.
As can be observed from the foregoing, a central processing unit of the router must perform a large number of functions, in addition to performing routing functions. Processing of the additional functions reduces the time available for routing calculations and related functions.
Furthermore, the router software is not easily modified to add new protocols and features. Each time a new protocol is added, the code must be modified to handle the new protocol.
There is, therefore, a need for a router which allows for the updating of router features and protocol without affecting existing software and which can distribute the handling of packets over multiprocessors to provide more efficient performance of routing calculations.
SUMMARY OF THE INVENTION
A router and method for processing packets are disclosed. The router distributes the handling of packet operations between a primary processor and one or more secondary processors to provide for quicker routing calculations on the primary processor. The packet operations are logically separated into chain elements which are then dynamically chained together as needed at runtime, to form encapsulation and decapsulation chains. The chains allow for new chain elements to be inserted into existing chains without changing existing code to introduce new features.
A method for processing packets generally comprises building a primary chain of function elements on a primary processor and a secondary chain of function elements on a secondary processor. Each element is operable to perform an operation on a packet. The method further comprises selecting one of the primary processor, secondary processor, and combination of the primary and secondary processors to perform a packet-processing function of each of the elements. The packets are processed by walking through the elements on the primary and secondary chains.
Each of the function elements in the primary chain may correspond to one of the function elements in the secondary chain to form function element pairs. The operation of one function element of the pair may be to pass the packet to the other processor, while the operation of the other function element may be to perform the packet-processing.
A router of the present invention includes a primary processor having a first chain generator operable to generate a primary chain of function elements and a secondary processor having a second generator operable to generate a secondary chain of function elements. Each function element is capable of performing an operation on a packet. Each of the function elements of the primary chain corresponds to one of the function elements of the secondary chain to form a pair of function elements. At least one function element of each pair is configured to perform a packet processing function.
The primary processor may be a route processor and the secondary processor may be a line card processor. The router may also include more than one line card processor.
The above is a brief description of some deficiencies in the prior art and advantages of the present invention. Other features, advantages, and embodiments of the invention will be apparent to those skilled in the art from the f
May William
Moberg Kenneth
Robins Kristen Marie
Cisco Technology
Dharia Rupal
Pollack Melvin H.
Ritter Lang & Kaplan LLP
LandOfFree
Distributed packet processing using encapsulation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed packet processing using encapsulation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed packet processing using encapsulation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3316901