Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-10-15
2003-07-29
An, Meng-Al T. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C370S352000, C370S409000
Reexamination Certificate
active
06601106
ABSTRACT:
BACKGROUND OF THE INVENTION
A network is a communication system that allows a user on a computer to access resources and exchange messages with users on other computers . A network is typically a data communication system that links two or more computers and peripheral devices. It allows users to share resources on their own systems with other network users and to access information on centrally located systems or on systems that are located at remote offices. It may provide connections to the Internet or to the networks of other organizations.
A network typically includes a cable that attaches to a network interface card (NIC) in each of the devices within the network.
Users interact with network-enabled software applications to make a network request, such as to get a file or print on a network printer. An application may also communicate with the network software, and the network software may then interact with the network hardware to transmit information to other devices attached to the network.
A local area network (LAN) is a network located in a relatively small area, such as a department or building. A LAN typically includes a shared medium to which workstations attach and through which they communicate with one another by using broadcast methods. With broadcasting, any device on a LAN can transmit a message that all other devices on the LAN can listen to. The device to which the message is addressed actually processes the message. Data is typically packaged into frames for transmission on the LAN.
FIG. 1
is a block diagram illustrating a network connection between a user
2
and a particular web page
6
. This figure is an example, which may be consistent with any type of network, including a LAN, a wide area network (WAN), or a combination of networks, such as the Internet.
When a user
2
connects to a particular destination, such as a requested web page
6
, the connection from the user
2
to the web page
6
is typically routed through several routers
4
A-
4
D. Routers are internetworking devices, typically used to connect similar and heterogeneous network segments into Internetworks. For example, two LANs may be connected across a dial-up, integrated services digital network (ISDN), or a leased line via routers.
Routers are also found throughout the Internet. End users may connect to local Internet Service providers (ISPs), which are typically connected via routers to regional ISPs, which are in turn typically connected via routers to national ISPs.
To move packets from one network to another, packet processing software is required on each router. Generally, packets received from a network are processed and forwarded to another network, based on information contained in layers
2
and
3
of the ISO 7-layer model.
Layer
2
(L
2
) of the ISO model is commonly referred to as the data-link layer. ethernet, HDLC and PPP are examples of commonly used L
2
protocols. ethernet is commonly used in LANs, while HDLC and PPP are commonly used in WANs.
Layer
3
(L
3
) is commonly referred to as the network layer. Internet Protocol (IP) is the most commonly used L
3
protocol. ARP, SAP and SNAP are IP-related protocols that, although not strictly in layer
2
, are considered to be layer
2
protocols for purposes herein.
Layer
4
(L
4
) is commonly referred to as the transport layer. TCP is the most commonly used L
4
protocol.
Router software designers use the term encapsulation to refer to the layering of protocols. A packet containing TCP, IP and ethernet protocols is said to have an encapsulation of TCP over IP over ethernet. A packet containing TCP, IP and HDLC protocols has an encapsulation of TCP over IP over HDLC.
The proliferation of features and protocols has greatly complicated the software involved in processing packets. Because of this, the software responsible for each layer must examine each packet to determine what the next step is in the handling of the packet.
For example, when a packet is received on an ethernet interface, the ethernet protocol handling software must examine the header, and based on values in the header, determine what to do with the packet. Data contained within a packet, for example, a type or length field in the protocol header, contains information about the next layer of the packet.
A traditional ethernet processing algorithm for this might be:
If type=IP and IP is configured for this interface
Pass packet to IP code
If type=ARP and ARP is configured for this interface
Pass packet to ARP code
If type=RARP and RARP is configured for this interface
Pass packet to RARP code
If type=IPV
6
and IPV
6
is configured for this interface
Pass packet to IPV
6
code
. . .
Each time a new protocol is added, the ethernet code must be modified to handle the new protocol. This may be necessary for each layer every time new features or protocols are added. Router software has grown to the point where maintenance has become very difficult. Each change can cause wide variations in performance. A new method is thus needed to allow growth in features and protocols without affecting the stability of existing software.
SUMMARY OF THE INVENTION
The present invention solves the above problems by logically separating the various packet operations into chain elements. These elements are then dynamically chained together as needed, at runtime, to form encapsulation and decapsulation chains.
The chains can also be dynamically rebuilt upon a change of configuration. Such changes typically come from a customer command line interface, however, in some cases there may be features that are configured after a protocol negotiation.
With the employment of chains, developers of new features do not need to change existing code to introduce the new features. Instead, new chain elements can be developed and inserted into existing chains as necessary.
As a result of the improved modularity, performance is improved for complex operations.
Accordingly, a method for processing packets in a router includes specifying packet processing function elements and linking them together to form chains. Each chain is associated with a unique interface/protocol pair. As used herein, a protocol may be a router-level protocol such as IP, or it may be a bridge-level protocol. Furthermore, the term protocol is meant to encompass the concept of tunneling, where a packet which has already been encapsulated using one protocol is further encapsulated using the same or a different protocol at the same level. In such a case, one or more virtual interfaces may be encountered by a packet which encapsulate and decapsulate the packet according to various protocols. An interface, then, is simply the target of a packet, and may be implemented in hardware, software, or both.
Each processing element within a chain performs at least one function on a packet. An incoming packet is received, and processed, first by a demultiplexor (demux) element which determines the protocol of the next higher level used by the packet. Then, the packet is processed by the elements of a decapsulation (decaps) chain associated with the interface on which the packet was received, and by the elements of an encapsulation (encaps) chain associated with the interface on which the packet is to be transmitted.
In one embodiment, the demultiplexor element or operation passes the packet on to a decapsulation chain associated with the protocol and with the incoming interface, depending on protocol information contained in the incoming packet. The protocol information may be contained, for example, in a type or length field in a header.
Decapsulation and encapsulation chains can be built dynamically, by inserting new and removing old elements as necessary as new protocols are developed and new features added.
In addition to decapsulation, the decapsulation chain can include functions including, but not limited to, decryption, decompression and filtering. Similarly, an encapsulation chain can include, in addition to an encapsulation operation, encryption, compression, flow control and filtering functions, a
Cartee Claude Alan
Leelanivas Manoj
Moberg Kenneth
An Meng-Al T.
Cisco Technology Inc.
Nguyen Dustin
LandOfFree
Packet processing using non-sequential 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 Packet processing using non-sequential encapsulation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet processing using non-sequential encapsulation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3068360