Bridging routed encapsulation

A technique for forwarding packets. An intermediate node assigns a link-layer address to an interface. Packets that specify the link-layer address as the destination address are processed and forwarded over the interface towards a destination. Packets received on the interface are processed including specifying the link-layer address as the source address of the packet and forwarded towards a destination specified in the packet.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to data networks and specifically to the forwarding of packets in computer networks.

2. Background Information

A computer network is a geographically distributed collection of interconnected communication links for transporting data between nodes, such as computers. Types of computer networks range from local-area networks (LANs) to wide-area networks (WANs). LANs are computer networks comprising e.g., Ethernet links that typically connect nodes in the same general physical location, usually within a building or a campus, whereas WANs are computer networks comprising e.g., Asynchronous Transfer Mode (ATM) links that typically connect nodes over a large geographical area.

Communication among the nodes of a network is typically effected by exchanging discrete protocol data units (PDUs), such as packets or frames, between the communicating nodes according to a hierarchical model of predefined protocols. The hierarchical model often used is based on the Open Systems Interconnection (OSI) reference model of hierarchical communication. This model is comprised of seven-layers where each layer is defined by the set of functions it performs and the services it provides.

Nodes within a LAN often communicate with one another at the link layer, which is Layer 2 (L2) of the OSI reference model. The link layer is concerned with physical addressing, network topology, line discipline, link error checking, ordered delivery of link-layer packets (bridged PDUs), and link flow control to ensure the packets are reliably transferred across a link, such as a physical connection between two end nodes. A bridged PDU typically comprises a link-layer header, containing L2 addressing information, and data. LANs are often connected to one another through a bridge, which is a network device that enables packets to be transferred from one LAN to another.

In networks where communication at the link layer may not be possible, nodes often communicate with one another at the network layer or Layer 3 (L3) of the OSI reference model. The network layer provides connectivity and path selection between two end nodes. Routing protocols residing in the network layer select optimal paths through a series of interconnected networks based on the destination network address. Individual network-layer protocols then move data, commonly called network-layer packets (routed PDUs), in accordance with the network-layer protocol along these paths. A routed PDU typically comprises a network-layer header, containing L3 address information, and data. L2 addressing information is typically not included in a routed PDU.

Networks that employ different technologies to effect communication between the nodes in the network are often called hybrid networks. For example, a network that comprises both an ATM infrastructure and an Ethernet infrastructure that are used to effect communication among various nodes in the network is often called a hybrid Ethernet-ATM network. The ability to translate between two or more dissimilar technologies for the purpose of achieving effective interoperability is commonly called interworking. For example, the above-described hybrid Ethernet-ATM network may contain a network device that connects the ATM infrastructure with the Ethernet infrastructure and is configured to interwork the two infrastructures such that data can be exchanged between them.

In some hybrid networks, geographically dispersed LANs are connected to one another through a WAN via a connection, such as an ATM virtual connection (VC). Typically, packets passed over the connection are encapsulated at a sending end (node) of the connection, transferred over the connection in encapsulated form, then decapsulated at a receiving end of the connection, in accordance with an encapsulation protocol. One encapsulation protocol commonly used to encapsulate packets transferred over ATM VCs is the Multiprotocol Encapsulation Over ATM Adaptation Layer 5 protocol described in Request For Comments (RFC) 1483 and RFC 2684 (hereinafter referred to as “RFC 2684”), which is available from the Internet Engineering Task Force (IETF), http://www.ietf.org, and is hereby incorporated by reference as though fully set forth herein. RFC 2684 can be used to encapsulate both bridged and routed PDUs to enable the transfer of link-layer and network-layer packets, respectively. As used herein, bridged and routed encapsulation refers to the technique of encapsulating bridged and routed PDUs, respectively.

FIG. 1is an example of a hybrid network100that employs RFC 2684 routed encapsulation to transfer PDUs from one LAN to another LAN over a VC. Network100comprises two geographically dispersed LANs120a,120binterconnected through intermediate nodes, such as routers130a,130b, and a WAN140comprising a plurality of additional intermediate nodes145that make up e.g., an ATM cloud. In particular, virtual connection (VC)170provides a point-to-point “logical” connection that connects router130awith router130bthrough WAN140. Moreover, routers130aand130bare configured to send and receive packets over VC170in accordance with RFC 2684 encapsulation. For example, a network-layer packet sent from node110ato node110dis forwarded to router130awhich, in turn, encapsulates the packet in accordance with RFC 2684 routed encapsulation, and forwards the encapsulated packet over VC170to router130b. Router130breceives the packet, decapsulates it, and forwards it over LAN120bto node110d. Likewise, a link-layer packet sent from node110ato node110dis handled in a similar manner except that it is processed in accordance with RFC 2684 bridged encapsulation instead of RFC 2684 routed encapsulation.

One problem with many encapsulation techniques is that they are not interchangeable. For example, the bridged and routed encapsulation techniques described in RFC 2684 are not interchangeable in the sense that a packet encapsulated using one technique, e.g., routed encapsulation, cannot be decapsulated using the other technique, e.g., bridged encapsulation. Thus, for example, if routers130aand130bare configured to encapsulate packets according to RFC 2684 routed encapsulation, if either router is reconfigured to encapsulate packets using RFC 2684 bridged encapsulation, the other router must also be reconfigured.

Another problem with some encapsulation techniques is that the encapsulated packet may not contain sufficient information to enable the PDU contained in the packet to be properly forwarded. For example, suppose router130ais reconfigured as an Ethernet attached router adapted to communicate at the link layer via link-layer packets with node145a. In addition, assume that the endpoint of VC170extends from router130b, which is configured as an ATM attached router, to node145a, which is configured as a L2 switch. Moreover, assume router130bhas a routed interface associated with VC170that is configured to handle RFC 2684 routed-encapsulated packets, containing network-layer address information, over the connection. One problem with this configuration is that routed-encapsulated packets originating from router130b, transferred over VC170to L2 switch145aand destined for router130ado not carry the necessary link-layer (L2) address information needed to switch the packets at the L2 switch145ato router130a. One way to deal with this problem is to encapsulate the packets at router130busing RFC 2684 bridged encapsulation, however, doing so would necessitate reconfiguring router130bto handle RFC 2684 bridged encapsulation. In arrangements where the routers are maintained by an entity that is different than the entity providing the wide-area network, such as a customer/service provider arrangement, having to reconfigure both routers may not be desirable.

SUMMARY OF THE INVENTION

Briefly, the present invention relates to a technique for forwarding packets received at an intermediate node over a hybrid network. The intermediate node has a first interface (link-layer connection) connected to e.g., a multi-access network, and configured to accommodate link-layer packets and a second interface (routed-encapsulated connection) connected to e.g., a point-to-point network, and configured to accommodate routed-encapsulated packets. Notably, the intermediate node assigns a link-layer address to the second interface. Preferably, this link-layer address is allocated from a pool of such addresses associated with the second interface. Link-layer packets received by the first interface having a destination address that matches the allocated link-layer address are encapsulated and forwarded over the second interface. Likewise, packets received by the second interface are processed, including decapsulating the packet and placing the allocated link-layer address and a link-layer address associated with the destination in the source address and destination address fields of the packet, respectively. The packet is then forwarded towards its destination.

In the illustrated embodiment, the hybrid network is a hybrid Ethernet-ATM network and the intermediate node is configured to accommodate link-layer and routed-encapsulated packets. A first router of the hybrid network is connected to a second router through a wide-area network (WAN). The intermediate node, which is illustratively a Layer 2 (L2) switch, is connected to the first router via a multi-access link-layer connection and the second router via a point-to-point virtual connection (VC). The first router learns the allocated link-layer address associated with the VC by sending an Address Resolution Protocol (ARP) request message to the switch. The switch, in turn, responds with an ARP reply message containing the allocated link-layer address. The link-layer address is then used by the first router to address packets destined for the second router. Packets received by the switch containing a destination address that matches the allocated is link-layer address are encapsulated according to a routed encapsulation technique and forwarded over the VC to the second router. Likewise, packets received by the switch over the VC from the second router that are destined for the first router are processed, including specifying the allocated link-layer address as the source address of the packet, and forwarded to the first router.

The inventive technique can be used in hybrid networks where a first node is connected to the network at the link layer and a second node is connected to the network at the network layer. The first node sends link-layer packets towards the second node, which is configured to receive and decapsulate packets according to a routed-encapsulated technique. Likewise, the second node sends routed-encapsulated packets not containing L2 addressing information to the first node, which is configured to receive packets at the link-layer. Advantageously, in accordance with the inventive technique, the packets can be transferred between the nodes without having to encapsulate the packets according to a bridged encapsulation technique, thereby, obviating having to reconfigure the second node.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT

FIG. 2is a schematic block diagram of a computer network200that can be used advantageously with the present invention. Network200comprises a collection of local-area networks (LANs)220coupled via a wide-area network (WAN)240. Each LAN220comprises various end nodes210coupled to an intermediate node CPE1, CPE2230a,230bthrough a bus225. Moreover, intermediate nodes230, which are illustratively routers, couple the LANs220to WAN240through multi-access link235and point-to-point link237, which illustratively are Ethernet and Asynchronous Transfer Mode (ATM) links, respectively. WAN240comprises an intermediate node300coupled to an ATM network cloud250. Further, virtual connection (VC)270is a point-to-point virtual connection that couples intermediate node300through the network cloud250with router230b.

FIG. 3is a high-level schematic block diagram of intermediate node (SPE)300, which illustratively is a switch. An example of a switch that may be advantageously used with the present invention is the Cisco 7600 Series Internet Router available from Cisco Systems Incorporated, San Jose, Calif. Operation of SPE300will be described with respect to Internet Protocol (IP) routing and Ethernet bridging of packets, although SPE300may be programmed for other applications, such as encryption.

SPE300comprises a plurality of interconnected components including an arrayed processing engine390, various memories, queuing logic310, and network interface cards (line cards)340. Operations of these components are preferably synchronously controlled by a clock module370although the arrayed elements of the processing engine may be operatively configured to function asynchronously. In the illustrative embodiment, the clock module370generates clock signals at a frequency of, e.g., 200 megahertz (i.e., 5 nanosecond clock cycles), and globally distributes them via clock lines to the components of the intermediate node.

The memories generally comprise random-access memory storage locations addressable by the processing engine and logic for storing software programs and data structures accessed by the components. An operating system, portions of which are typically resident in memory and executed by the arrayed processing engine, functionally organizes the node300by, inter alia, invoking network operations in support of software processes executing on node300. It will be apparent to those skilled in the art that other memory means, including various computer readable media, may be used for storing and executing program instructions pertaining to the inventive technique and mechanism described herein.

A buffer and queuing unit (BQU)310is connected to a packet memory320for storing packets and a queue memory330for storing network-layer and link-layer headers of the packets on data structures, such as linked lists, organized as queues. The BQU310further comprises data interface circuitry for interconnecting the processing engine with a plurality of line cards340via a selector circuit350having an arbiter355. The line cards340may comprise, e.g., Asynchronous Transfer Mode (ATM), Fast Ethernet (FE) and Gigabit Ethernet (GE) ports, each of which includes conventional interface circuitry that may incorporate the signal, electrical and mechanical characteristics, and interchange circuits, needed to interface with the physical media and protocols running over that media. In the preferred embodiment, one of the line cards340ais an ATM OC-12 Optical Services Module (OSM), available from Cisco Systems Incorporated, configured to terminate VC270at node300.

A routing processor360executes conventional routing protocols for communication directly with the processing engine390. The routing protocols generally comprise topological information exchanges between intermediate nodes to determine preferred paths through the network based on, e.g., destination IP addresses. These protocols provide information used by the processor360to create and maintain forwarding tables. The tables are loaded into the external partitioned memories380as forwarding information base (FIB) tables, such as forwarding table386, used by the processing engine to perform, e.g., L2 and L3 forwarding operations. When processing a header in accordance with IP routing, for example, the engine390determines where to send the packet by indexing into the FIB using an IP address of the header. Execution of the forwarding operations results in destination media access control (MAC) addresses of the headers being rewritten by the processing engine to identify output ports for the packets.

The processing engine390may comprise a symmetric multiprocessor system having a plurality of processors (not shown). Each processor is illustratively a pipelined processor that includes, inter alia, a plurality of arithmetic logic units (ALUs) and a register file having a plurality of general purpose registers that store intermediate result information processed by the ALUs. The processors may be arrayed into multiple rows and columns, and further configured as a multi-dimensioned systolic array. In the illustrative embodiment, the processors are arrayed as eight (8) rows and two (2) columns in an 8×2 arrayed configuration that is embedded between an input buffer (not shown) and an output buffer (not shown). However, it should be noted that other arrangements, such as 4×4 or 8×1 arrayed configurations, might be advantageously used with the present invention. As noted herein, a single processor supporting multiple threads of execution can take advantage of the invention.

The processors of each row are configured as a “pipeline” to sequentially execute operations on the transient data, whereas the processors of each column operate in parallel to perform substantially the same operation on the transient data, but with a shifted phase. Each phase comprises a predetermined period of cycles, e.g., 128 cycles. Sequencing circuitry controls the processors of each pipeline by ensuring that each processor completes processing of current transient data before loading new transient data into the pipeline at a new phase. In general, a new phase of processing is started, i.e., a context switch is performed, when all of the processors finish processing their current context and new, incoming context is completely received.

The arrayed processing engine390is coupled to a memory partitioned into a plurality of external memory (Ext Mem) resources380which are preferably organized as one or more banks and implemented using fast-cycle-random-access-memory (FCRAM) devices, although other devices, such as reduced-latency-dynamic-random-access-memory (RLDRAM) devices, could be used. The external memory stores non-transient data organized as a series of data structures for use in processing the transient data. These data structures include forwarding table386and a connection table384. Preferably, each of these data structures is organized as a table comprising one or more entries.

Forwarding table386holds information that is used by processing engine390to identify the interface (e.g., port, virtual connection) through which various nodes can be reached. Each entry contained in forwarding table386is associated with a particular node and contains, inter alia, the network-layer and link-layer address associated with the node, and the interface through which the node can be reached.

The connection table384contains information about connections on node300. Each entry in table384is associated with connections, such as VC270and connection235, and contains information about the connections. In the illustrated embodiment, information contained in this table is pre-configured and the table is indexed by a virtual-channel descriptor (VCD) associated with the connection.FIG. 4is a block diagram of a connection-table entry that can be used with the present invention. Entry400comprises a virtual-link-layer-address field425, a network-layer-address field435, a link-layer-address field440, and a connection-information field495. The connection-information field495holds information associated with the connection, such as, e.g., an ATM port, ATM sub-interface, virtual path identifier (VPI), virtual channel identifier (VCI), and virtual channel descriptor (VCD).

The virtual-link-layer-address field425holds a link-layer address assigned to the routed-encapsulated connection, e.g., VC270. As described below, this link-layer address is used to “spoof” the link-layer address of nodes reachable through the associated connection. Preferably, this address is allocated from a pre-configured pool of link-layer addresses associated with the line card that terminates the connection. The network-layer-address field435holds a network-layer address associated with a node, e.g., CPE2230bthat is reachable via the routed-encapsulated connection and the link-layer-address field440holds a link-layer address of a node, e.g., CPE1230a, reachable through the bridged connection. For example, a connection table entry400associated with VC270and connection235contains a link-layer address associated with VC270in the virtual-link-layer-address field425, the network-layer address associated with router230bin the network-layer-address field435, the link-layer address associated with router230ain the link-layer-address field440, and the ATM port, ATM sub-interface, VPI, VCI, and VCD associated with VC270in the information field495.

Typically, communication between nodes is effected at the link layer using link-layer frames (packets).FIG. 5is a partial schematic block diagram of a link-layer Ethernet frame, in accordance with the Institute of Electronic and Electrical Engineers (IEEE) 802.3 standard available from the IEEE, New York, N.Y., that can be used with the present invention. Frame500comprises a data field540, a frame-check-sequence (FCS) field550, and a link-layer-header field570containing destination address510, source address520, and length530fields. The destination510and source520address fields hold the link layer (MAC) addresses of a destination and source nodes, respectively. The data540and length530fields hold data and the amount of the data contained in the frame, respectively. The FCS field holds a cyclic-redundancy check (CRC) of the contents of the header570and data540fields.

Each node in network200is assigned an IP address and a MAC address that are used to communicate with the node at the network and link layers, respectively. If the IP address of a node is known, the MAC address of that node can be discovered using an address-resolution protocol, such as the Address Resolution Protocol (ARP) defined in Request For Comments (RFC) 826, which is available from the Internet Engineering Task Force (IETF) at http://www.ietf.org and is hereby incorporated by reference as though fully set forth herein. ARP uses broadcast messages to determine the MAC (hardware) address corresponding to a particular IP address. Specifically, a source node discovers the MAC address of a destination node by broadcasting a request ARP message containing the IP address of the destination node. The destination node, in turn, responds to the source node with a reply ARP message that contains the MAC address of the destination node. The source node can then use this MAC address to communicate with the destination node at the link layer.

FIG. 6is a schematic block diagram of an ARP message that can be used with the present invention. Message600comprises a hardware-type field605, protocol-type field610, hardware-address-length field615, protocol-address-length field620, operation field625, source-hardware-address field630, source-protocol-address field635, destination-hardware-address field640, and destination-protocol-address field645. The hardware-type field605holds a value that indicates the type of hardware address, e.g., Ethernet, contained in the source and destination hardware address fields630,640. Likewise, the protocol-type field610holds a value that indicates the type of protocol address, e.g., IP, contained in the source and destination protocol address fields635,645. The hardware and protocol address length fields hold values that indicate the length of the hardware and protocol addresses, respectively. The source hardware and protocol fields hold the link-layer and network-layer addresses of the source node, respectively. Likewise, the destination hardware and protocol address fields hold the link-layer and network-layer addresses of the destination node, respectively.

The present invention relates to a technique for forwarding packets received at an intermediate node over a hybrid network. The intermediate node has a first interface configured to accommodate a L2 connection and a second interface configured to accommodate a L3 connection. The intermediate node assigns a link-layer address to the second interface. Preferably, this link-layer address is allocated from a pool of such addresses associated with the second interface. Illustratively, link-layer packets received by the intermediate node having a destination address that matches the allocated link-layer address are L2 switched to the second interface. The packets are further processed and forwarded over the second interface. Likewise, packets received by the second interface are processed, including determining a destination of the packet and placing the allocated link-layer address in the source address field of the packet. The packet is then L2 switched towards its destination.

FIG. 7illustrates a sequence of steps that can be used to send a packet500from router230a(FIG. 2) to router230bin accordance with the inventive technique. Before router230acan send a link-layer packet to router230b, router230amust learn (discover) router230b's link-layer address. As described below, Steps710through740enable router230ato learn the link-layer address of router230b. It should be noted, however, that other techniques could be used, such as statically configuring router230awith router230b's link-layer address.

The sequence starts at Step705and proceeds to Step710where router (CPE1)230acreates a request message600containing its IP and MAC addresses and the IP address of router (CPE2)230b, and forwards the request message600towards CPE2230b. Next at Step720, SPE300receives and processes request message600including identifying the interface associated with CPE2230bby applying CPE2's230bIP address contained in message600to table384to locate an entry400that contains a network-layer address435that matches the IP address of CPE2230b. SPE300then determines from the matching entry400that CPE2230bcan be reached through interface VC270and places the virtual-link-layer address425associated with VC270contained in the matching entry400into message600and forwards the message600as a reply message towards CPE1230a, as indicated at Steps730and735.

CPE1230areceives the reply message600, places the MAC address of VC270contained in the reply message600into the destination address field510of packet500, and forwards packet500towards CPE2230bas indicated at Step740.

At Step745, SPE300receives packet500, processes it, and forwards it over connection270towards CPE2230b. Specifically, SPE300L2 switches the packet by applying the destination address510in the header570to the forwarding table386to determine the interface (i.e., VC270) where CPE2230bcan be reached. SPE300then removes the link-layer header from the packet, encapsulates the packet in accordance with RFC 2684 routed encapsulation, and forwards the packet over the interface (i.e., over VC270) towards CPE2230b. CPE2230bthen receives the packet and processes it, which may include decapsulating the packet and forwarding the packet onto LAN220b(Step750). The sequence ends at Step795.

FIG. 8is a sequence of steps that can be used to transfer a packet500from CPE2230bto CPE1230ain accordance with the inventive technique. The sequence begins at Step805and proceeds to Step815where CPE2230bprocesses packet500, which includes removing the packet header570and encapsulating the packet in accordance with RFC 2684 routed encapsulation, and forwards the packet over VC270towards CPE2230b. At Step820, SPE300receives the packet and processes it including decapsulating the packet and adding a link-layer header570to the packet. Next at Step825, SPE300locates the connection table entry400associated with VC270and retrieves the link-layer address440for destination node CPE1230aand the virtual-link-layer address425associated with VC270from the entry400and places it in the destination-address field510and source-address field520of the packet, respectively. SPE300then processes the packet and forwards the packet towards its destination, i.e., CPE1230a, as indicated at Step840. Specifically, SPE300L2 switches the packet by applying the destination address510to the forwarding table386to determine the interface235where CPE1230acan be reached and forwards the packet over that interface235. CPE1230areceives the packet and processes it, accordingly, which may include decapsulating the packet and forwarding it onto LAN220a(Step845). The sequence ends at Step895.

The above-described embodiment of the invention of the invention includes a connection table384that contains one or more entries, where each entry400is associated with a connection. Moreover, each entry contains a virtual-link-layer address425associated with the connection. This is not intended to be a limitation of the invention. In other embodiments of the invention, other forms of interfaces are associated with the virtual-link-layer address425. For example, in one embodiment, a physical port is associated with the virtual-link-layer address. Here, packets that specify the virtual-link-layer address as the destination address are forwarded to the port. Likewise, packets received from the port are processed to include the virtual-link-layer address as the source address of the packet.

Also it should be noted that in the above-described embodiment of the invention, information contained in the connection table is pre-configured, however, this too is not is intended to be a limitation of the invention. In other embodiments of the invention, information contained in the connection table is learned and the table is populated with the information, accordingly. For example, in one embodiment of the invention, the link-layer address of the node (e.g., CPE1230a) connected to the bridged connection is learned when the node sends a packet to the intermediate node (e.g., SPE300) configured to implement the present invention.