FIELD OF THE INVENTION  
         [0001]    The present invention relates generally to data communications forwarding systems and, more particularly, to a data forwarding apparatus capable of exhibiting the functionality of multiple interconnected logical forwarding sub-systems while maintaining efficient usage of its communication interfaces.  
         BACKGROUND OF THE INVENTION  
         [0002]    Modern data communications forwarding systems (e.g., switches and routers) typically have functionality that is partitioned into a “control plane” and a “data plane.” The control plane is typically implemented using hardware that can execute complex software written in general-purpose languages to implement control protocols and operator interfaces. The data plane is implemented in special-purpose hardware, with forwarding and processing decisions implemented in different ways on different systems. Even when the data plane processing is implemented in a general-purpose CPU, the data plane is typically treated as a separate entity and is optimized for efficient forwarding.  
           [0003]    Examples of forwarding systems having functionality partitioned into a control plane and a data plane include IP routers, layer-2 switches of various types (e.g., Ethernet, Frame Relay (FR), Asynchronous Transfer Mode (ATM), Multi-Protocol Label Switching (MPLS)), circuit switches of various types (e.g., DACS, Synchronous Optical Network (SONET) Add-Drop Multiplexers (ADMs), Optical Cross-Connects (OXCs)), wireless telephony equipment, equipment that performs combinations of the above operations and most other programmable communications equipment that performs a forwarding function. Examples of processing accomplished by the data plane include label lookup (MPLS, FR, ATM, X.25), source lookup (Ethernet, Internet Protocol (IP)), destination lookup (Ethernet, IP), egress interface lookup (all switching types), egress sub-interface lookup (most switching types), encapsulation (most switching types), filtering, metering, statistics accumulation and sampling.  
           [0004]    It is often desirable to partition a single physical forwarding system into multiple logical forwarding sub-systems. For example, a service provider may wish to provide a router for each customer without actually installing a separate piece of equipment for each customer. Alternatively, in a forwarding system that performs two functions (e.g., IP routing and Frame Relay switching) it may be easier to implement logically separate control planes for the two functions. In yet another scenario, as in a large IP network, it is desirable to logically partition the network into a hierarchy, with different functionality in the routers within each layer of the hierarchy. When routers of different layers are co-located, it is advantageous to instantiate two or more logical forwarding sub-systems in a single physical forwarding system.  
           [0005]    Existing implementations of multiple logical forwarding sub-systems in the same hardware operate by instantiating a separate instance of the data plane processing for each sub-system. When data must logically be processed sequentially by two or more logical forwarding sub-systems, the data is passed sequentially from the instance of the first data plane to the instance of the next data plane until it reaches the instance of the last data plane. Moreover, a typical implementation divides the ingress and egress interfaces of the physical system among the logical forwarding sub-systems. All input on an ingress that belongs to a particular sub-system is first processed by that sub-system. When a physical port uses a protocol that can differentiate the data in some manner at a low level, (e.g. by TDM or using labels) then the individual data streams may be handled by different logical forwarding sub-systems.  
           [0006]    However, the partitioning of interfaces of the physical forwarding system amongst the logical forwarding sub-systems has a significant drawback. Specifically, since the logical forwarding sub-systems are connected amongst themselves, each such connection will consume a pair of interfaces of the physical forwarding system. Hence, a significant proportion of the interfaces of the physical forwarding system may be taken up by the connections amongst the logical forwarding sub-systems, which results in highly inefficient interface usage. This effectively means that a single physical forwarding system, which is assigned to play the role of a plurality of logical forwarding sub-systems, will need to be over-provisioned at the interface level. This represents an inconvenience to the service provider, at least in the form of added cost.  
         SUMMARY OF THE INVENTION  
         [0007]    The present invention is applicable to forwarding systems of the type where data is logically processed first by the data plane of one of a plurality of logical forwarding sub-systems, and then by the data plane of another of the sub-systems. By extension, the present invention is also applicable when the data planes of three or more logical forwarding sub-systems must sequentially process the same data. The present invention relates to creation of a consolidated mapping function that is based on the individual mapping functions that specify the forwarding behaviour of the individual logical routers. This concept enables efficient shared data-plane operation in a forwarding system that instantiates multiple logical forwarding sub-systems. The efficiency arises when the same data is processed by more than one logical forwarding sub-system in the same physical forwarding system. The concept is applicable to systems with centralized or distributed data planes. It is also applicable to systems with centralized or distributed control planes.  
           [0008]    According to a broad aspect, the invention provides a method of generating a mapping for use by a data forwarding entity having a plurality of communication interfaces. The method includes receiving a first mapping specifying a next hop interface for data elements received at the communication interfaces, wherein at least one next hop interface belongs to a set of logical interfaces. The method also includes receiving a second mapping specifying a second next hop interface for certain data elements for which the next hop interface specified by the first mapping belongs to the set of logical interfaces, wherein at least one second next hop interface belongs to the plurality of communication interfaces. Further, the method includes generating a consolidated mapping from the first and second mappings by replacing each portion of the first mapping that specifies a next hop interface belonging to the set of logical interfaces by a corresponding portion of the second mapping that specifies a second next hop interface.  
           [0009]    According to another broad aspect, the present invention may be summarized as a data forwarding apparatus. The data forwarding apparatus includes a plurality of communication interfaces at which data elements are received by the apparatus, a memory and a processing entity connected to the communication interfaces and to the memory. The memory stores a first mapping, a second mapping and a consolidated mapping. The first mapping specifies a next hop interface for data elements received at the communication interfaces, wherein at least one next hop interface belongs to a set of logical interfaces. The second mapping specifies a second next hop interface for certain data elements for which the next hop interface specified by the first mapping belongs to the set of logical interfaces, wherein at least one second next hop interface belongs to the plurality of communication interfaces. The consolidated mapping specifies a next hop interface for data elements received at the communication interfaces, wherein no next hop interface specified by the consolidated mapping belongs to the set of logical interfaces. The processing entity generates the consolidated mapping from the first and second mappings by replacing each portion of the first mapping that specifies a next hop interface belonging to the set of logical interfaces by a corresponding portion of the second mapping that specifies a second next hop interface. Additionally, the processing entity accesses the consolidated mapping to determine a next hop interface associated with each data element received at the communication interfaces and forwards the received data element to the next hop interface determined at the accessing step.  
           [0010]    According to yet another broad aspect, the present invention may be summarized as a memory for storing data for access by an application program being executed on a data processing system having a plurality of communication interfaces. The memory includes a data structure stored in the memory that includes information regarding a first mapping specifying a next hop interface for data elements received at the communication interfaces, wherein at least one next hop interface belongs to a set of logical interfaces. The data structure also includes information regarding a second mapping specifying a second next hop interface for certain data elements for which the next hop interface specified by the first mapping belongs to the set of logical interfaces, wherein at least one second next hop interface belongs to the plurality of communication interfaces. Additionally, the data structure includes information regarding a consolidated mapping created from the first and second mappings by replacing each portion of the first mapping that specifies a next hop interface belonging to the set of logical interfaces by a corresponding portion of the second mapping that specifies a second next hop interface.  
           [0011]    The present invention is also applicable to a multicast environment and may be summarized as a method of generating a mapping for use by a data forwarding entity having a plurality of communication interfaces. The method includes receiving a first mapping specifying a next hop interface for data elements received at the communication interfaces, wherein at least one of the plurality of next hop interfaces specified for at least one of the certain ones of the received data elements belongs to a set of logical interfaces. The method also includes receiving a second mapping specifying a plurality of second next hop interfaces for certain data elements for which the next hop interface specified by the first mapping belongs to the set of logical interfaces, wherein at least one second next hop interface belongs to the plurality of communication interfaces. Additionally, the method includes generating a consolidated mapping from the first and second mappings by replacing at least one portion of the first mapping that specifies a next hop interface belonging to the set of logical interfaces by a corresponding portion of the second mapping that specifies a plurality of second next hop interfaces.  
           [0012]    The present invention may also be summarized as computer-readable media tangibly embodying a program of instructions executable by a data forwarding apparatus to perform the above described method.  
           [0013]    These and other aspects and features of the present invention will now become apparent to those of ordinary skill in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying drawings. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]    In the accompanying drawings:  
         [0015]    [0015]FIG. 1 shows a pair of routers to be replaced by a single router in accordance with an embodiment of the present invention;  
         [0016]    [0016]FIG. 2A shows a router in accordance with an embodiment of the present invention, which is provided with a pair of mappings;  
         [0017]    [0017]FIG. 2B shows one manner of creating a consolidated mapping from the mappings provided to the router of FIG. 2A;  
         [0018]    [0018]FIG. 2C shows another manner of creating a consolidated mapping from the mappings provided to the router of FIG. 2A;  
         [0019]    [0019]FIG. 3 shows an example physical implementation of a router in accordance with an embodiment of the present invention;  
         [0020]    [0020]FIG. 4A shows a router in accordance with another embodiment of the present invention, which is provided with a pair of mappings;  
         [0021]    [0021]FIG. 4B shows one manner of creating a partial consolidated mapping from the mappings provided to the router of FIG. 4A; and  
         [0022]    [0022]FIG. 4C shows another manner of creating a partial consolidated mapping from the mappings provided to the router of FIG. 4A. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0023]    With reference to FIG. 1, there is shown a cluster of data communications forwarding systems (hereinafter referred to simply as a “cluster”  10 ) to be replaced by a single data communications forwarding system of the present invention. In this example, the cluster  10  includes two data communications forwarding systems, namely a first router R 1  and a second router R 2 . In general, the components of the cluster  10  may be data communications systems other than routers and, furthermore, the number of components may be greater than two, and furthermore, the components need not be of the same type. Specific examples of data communications forwarding systems amenable to be replaced by a single data communications forwarding system of the present invention include IP routers, layer-2 switches of various types (e.g., Ethernet, Frame Relay (FR), Asynchronous Transfer Mode (ATM), Multi-Protocol Label Switching (MPLS)), circuit switches of various types (e.g., DACS, Synchronous Optical Network (SONET) Add-Drop Multiplexers (ADMs), Optical Cross-Connects (OXCs)), wireless telephony equipment, equipment that performs combinations of the above operations and most other programmable communications equipment that performs a forwarding function.  
         [0024]    Also, in the present specification, the term “data element” is intended to encompass an element of packet-switched data (e.g., a packet or datagram) or an element of circuit-switched data (e.g., the data contained in a time slot), depending on the context in which it is described. For its part, the term “packet” is not to be construed in a limitative fashion. Rather, this term is intended to broadly encompass any statistically multiplexed unit of information. Thus, it will be clear that the present invention applies to data forwarding entities that perform either or both packet-switching and circuit-switching functions.  
         [0025]    As can be seen in FIG. 1, the cluster  10  includes a plurality of extra-cluster interfaces x, y, z, w, as well as a plurality of intra-cluster interfaces a, b, c, d. The extra-cluster interfaces x, y, z, w, receive data elements from outside the cluster  10  and also forward routed data elements to destinations outside of the cluster  10 . In this specific example, extra-cluster interfaces x, y, z, w, are connected to destinations 1.3.2.7, 1.5.7.9, 1.2.3.4, 2.4.6.8, respectively. The intra-cluster interfaces a, b, c, d, serve to connect the routers R 1  and R 2  to one another. Specifically, intra-cluster interface a on router R 1  is connected to intra-cluster interface c on router R 2 , while intra-cluster interface b on router R 1  is connected to intra-cluster interface d on router R 2 . The number of extra-cluster interfaces and intra-cluster interfaces is shown by way of illustration only; it should be understood that the data communications forwarding system of the present invention may replace a cluster  10  having a wide range of extra-cluster interfaces and intra-cluster interfaces.  
         [0026]    Each of the routers R 1 , R 2  typically has a control plane for storing a mapping that defines the forwarding behaviour of the particular router in question. In this case, let M 1  and M 2  represent the mappings associated with the routers R 1  and R 2 , respectively. Thus, mapping M 1  will define a mapping amongst the interfaces x, y, a and b, while mapping M 2  will define a mapping amongst the interfaces z, w, c and d. More specifically, mappings M 1  and M 2  will specify a next hop interface for each data element received at one of its interfaces. The next hop interface may be looked up as a function of a source of the data element (identified by an IP address, for example), a destination of the data element (e.g., identified by an IP address, for example), a priority level associated with the data element, the identity of the interface at which the data element arrives, a connection state (e.g., for connection-oriented switching) or some other characteristic of the received data element.  
         [0027]    By virtue of the mappings M 1  and M 2  and the interconnection existing between the routers R 1  and R 2 , a data element arriving at one of the extra-cluster interfaces x, y, z, w will be forwarded either directly out through one of the extra-cluster interfaces on the same router or it will have to travel to the other router of the cluster  10 , from which it will emerge at one of the extra-cluster interfaces of that other router. For example, a data element arriving at interface x will either exit the router R 1  through interface y (or x, although this is rare), or it will travel to router R 2  via one of the intra-cluster interfaces a, b. The data element will then emerge from router R 2  via one of the extra-cluster interfaces z, w. In order for a single router to be able to successfully replace the cluster  10 , the behaviour of data elements from the point of view of entering and leaving the cluster  10  via the extra-cluster interfaces x, y, z, w needs to be replicated.  
         [0028]    With reference to FIG. 2A, there is shown a data communications forwarding system  200  in accordance with an embodiment of the present invention. In this particular example, the data communications forwarding system  200  is a router, although it may assume other roles in accordance with the operational requirements of the invention. Viewed externally, the single router  200  is functionally equivalent to the cluster  10  described herein above with reference to FIG. 1. The routers R 1  and R 2 , although they do not physically exist, are manifested within the router  200  in a logical form and will hereinafter be referred to as “logical routers” for convenience.  
         [0029]    The router  200  has a data plane that receives and forwards data elements in accordance with a mapping maintained in a control plane. Data elements are received on a plurality of communication interfaces x, y, z, w corresponding to the extra-cluster interfaces x, y, z, w, of the cluster  10 . However, the router  200  does not possess any communication interfaces to match the intra-cluster interfaces a, b, c, d of the cluster  10 . Rather, these former intra-cluster interfaces are logical in nature and are denoted Va, Vb, Vc, Vd, in this example. Thus, it will be apparent that the router  200  does not require a greater number of communication interfaces than the number of extra-cluster interfaces of the cluster  10  it is designed to replace.  
         [0030]    From a physical standpoint, as shown in FIG. 3, the communication interfaces x, y, z, w may reside on a plurality of line cards  220 , which include processors and other hardware. The data plane of the router  200  may also physically include a switch fabric  230  to which the line cards  220  connect and which allows data elements to travel (i.e., “hop”) from one line card to another. In this example, the line cards  220  on which are located communication interfaces x and y are associated with logical router R 1  (solid blocks), and the line cards  220  on which are located communication interfaces z and w are associated with logical router R 2  (striped blocks). In other embodiments, the partitioning of physical resources amongst logical routers need not be on a per-line-card basis. In all cases of the router  200 , however, no line cards or other physical resources are associated with the logical interfaces Va, Vb, Vc, Vd.  
         [0031]    With continued reference to FIG. 2A, the control plane of the router  200  of the present invention maintains a mapping M 3  which defines the forwarding behaviour of the router  200 . The control plane may be distributed amongst the line cards  220  or it may be implemented on a set of control cards provided separately within the chassis of the router  200 . The mapping M 3  specifies a next hop interface for each data element received at one of the communication interfaces x, y, z, w. Since the router  200  is designed to replace the routers R 1  and R 2 , the mapping M 3  must bear some relation to the mappings M 1  and M 2 . In fact, mappings M 1  and M 2 , which are provided to the router  200 , contain all of the information needed to create mapping M 3 . However, it is noted that mappings M 1  and M 2  involve the (no longer existent) intra-cluster interfaces and thus the mapping M 3  must differ from the mappings M 1  and M 2 . One way of consolidating the mappings M 1  and M 2  to arrive at the mapping M 3  is now described in greater detail.  
         [0032]    The mapping M 3  is created by a consolidation engine  240 , which may be implemented as a software component of the control plane. Conceptually, the consolidated mapping M 3  specifies a mapping function for the physical data plane function that is equivalent to a “convolution” of the mapping functions specified by the mappings M 1  and M 2 . As a practical matter, the consolidated mapping M 3 , applied once, will have the same result (as far as external operation is concerned) as applying the appropriate individual mappings M 1  and M 2  in the appropriate sequence.  
         [0033]    In the example of FIG. 2A, the forwarding action specified by the mapping M 1  depends on the destination of each data element received at one of the communication interfaces x, y, z, w. The data plane obtains knowledge of the destination of each received data element from a header of that data element. Of interest is the fact that the forwarding action does not depend on the communication interface at which a data element is received, although it should be understood that in other cases (see FIGS. 4A through 4C), the forwarding action may indeed be dependent on the communication interface at which a data element is received and possibly on other characteristics of the received data element, such as its priority level, age, etc.  
         [0034]    More specifically, the mapping M 1  specifies that a data element with destination 1.3.2.7 is to be forwarded to communication interface x, a data element with destination 1.5.7.9 is to be forwarded to communication interface y, a data element with destination 1.2.3.4 is intended to be forwarded to logical interface Va, and a data element with destination 2.4.6.8 is intended to be forwarded to logical interface Vb. Furthermore, the mapping M 2  specifies that a data element with destination 1.2.3.4 is to be forwarded to communication interface z, a data element with destination 2.4.6.8 is to be forwarded to communication interface w, a data element with destination 1.3.2.7 is intended to be forwarded to logical interface Vc, and a data element with destination 1.5.7.9 is intended to be forwarded to logical interface Vd.  
         [0035]    In one example embodiment, the consolidated mapping M 3  can be created by taking a basic portion of the mapping M 1  and consolidating it with an augmented portion of the mapping M 2 . As shown in FIG. 2B, the basic portion of the mapping M 1 , denoted M 1   BASIC  is taken to be the entire mapping M 1 , while the augmented portion of the mapping M 2 , denoted M 2   AUG , refers only to that portion of the mapping M 2  in which a next hop interface is provided for those data elements that would be routed to logical router R 2  by logical router R 1 . Hence, M 2   AUG  includes only the portion of the mapping M 2  that specifies the next hop interface for data elements having a destination 1.2.3.4 or a destination 2.4.6.8, since these are the only data elements that would have been forwarded to logical router R 2  by logical router R 1  if these logical routers were implemented separately. Now, by replacing those portions of M 1   BASIC  which specify a forwarding action towards logical router R 2  with a corresponding portion of M 2   AUG  that continues the forwarding process, one has created the mapping M 3 .  
         [0036]    More specifically, the mapping M 3  specifies that a data element with destination 1.3.2.7 is to be forwarded to communication interface x (as in M 1   BASIC ), a data element with destination 1.5.7.9 is to be forwarded to communication interface y (as in M 1   BASIC ), a data element with destination 1.2.3.4 is to be forwarded to communication interface z (as in M 2   AUG ), and a data element with destination 1.5.7.9 is to be forwarded to communication interface w (as in M 1   AUG ). Of note is the fact that the mapping M 3  is a single-next-hop mapping function, which means that a data element is routed immediately to the same communication interface after one lookup as it would have been routed to if it had followed multiple passes (through the mappings M 1  and M 2 ). Stated differently, the net effect of the mapping M 3  is identical to the net forwarding behaviour of the cluster  10  from the point of view of the communication interfaces x, y, z, w. Furthermore, no communication interfaces need to be reserved for intra-router communications. Moreover, no data element will ever be “forwarded” by the router  200  to a logical interface via the data plane, which is consistent with the notion that the logical interfaces Va, Vb, Vc, Vd do not exist as physical entities.  
         [0037]    Alternately, the consolidated mapping M 3  can be created by taking a basic portion of the mapping M 2  and consolidating it with an augmented portion of the mapping M 1 . As shown in FIG. 2C, the basic portion of the mapping M 2 , denoted M 2   BASIC , is taken to be the entire mapping M 2 , while the augmented portion of the mapping M 1 , denoted MLAUG, refers only to that portion of the mapping M 1  in which a next hop interface is provided for those data elements that would be routed to logical router R 1  by logical router R 2 . Hence, MLAUG includes only the portion of the mapping M 1  that specifies the next hop interface for data elements having a destination 1.3.2.7 or a destination 1.5.7.9, since these are the only data elements that would have been forwarded to logical router R 1  by logical router R 2  if these logical routers were implemented separately. Now, by replacing those portions of M 2   BASIC  which specify a forwarding action towards logical router R 1  with a corresponding portion of M 1   AUG  that continues the forwarding process, one has created the same mapping M 3  as in FIG. 2B.  
         [0038]    A more complex example of a forwarding action specified by the mappings M 1  and M 2  is now described with reference to FIGS. 4A through 4C. Specifically, in FIG. 4A, a mapping M 1 ′ is provided, which specifies a next hop interface to which to forward a received data element based not only on the destination of the data element but also on the basis of the communication interface at which the data element is received. In this particular example, some of the communication interfaces are adapted to communicate with the control plane. This may be useful in operation, administration and maintenance functions. For example, the ability to transmit data elements to the control plane may be used to perform error detection and/or correction or to transmit control information or even changes to the mappings M 1  and M 2 .  
         [0039]    In order to obtain sufficient information to forward each received data element, data plane can obtain, as before, the destination of a received data element from the data element&#39;s header. In addition, the data plane can be assumed to have knowledge of the communication interface at which the data element is received, since it processes incoming data elements. Of course, it will be understood that because the mappings M 1 ′ and M 2 ′ are associated with logical routers R 1  and R 2 , certain portions of each mapping will refer to interfaces that are physically non-existent, namely, logical interfaces Va, Vb, Vc, Vd.  
         [0040]    In this specific example, the mapping M 1 ′ specifies that a data element with destination 1.2.3.4 and received at communication interface x is intended to be forwarded to logical interface Va, a data element with destination 1.2.3.4 and received at communication interface y is intended to be forwarded to logical interface Vb, a data element with destination 1.2.3.4 and “arriving” at logical interface Va is intended to be forwarded to logical interface Vb and a data element with destination 1.2.3.4 and “arriving” at logical interface Vb is intended to be forwarded to logical interface Va. In addition, a data element with destination 1.3.2.7 and received at communication interface y is to be forwarded to communication interface x, a data element with destination 1.3.2.7 and received at communication interface x is to be forwarded to the control plane (because it should never have entered the router  200 ) and a data element with destination 1.3.2.7 and “arriving” at either logical interface Va or logical interface Vb is to be forwarded to communication interface x. Moreover, a data element with destination 1.5.7.9 and received at communication interface x is to be forwarded to communication interface y, a data element with destination 1.5.7.9 and received at communication interface y is to be forwarded to the control plane (because it should never have entered the router  200 ) and a data element with destination 1.5.7.9 and “arriving” at either logical interface Va or logical interface Vb is to be forwarded to communication interface y. Finally, a data element with destination 2.4.6.8 and received at communication interface x is intended to be forwarded to logical interface Va, a data element with destination 2.4.6.8 and received at communication interface y is intended to be forwarded to logical interface Vb, a data element with destination 2.4.6.8 and “arriving” at logical interface Va is intended to be forwarded to logical interface Vb and a data element with destination 2.4.6.8 and “arriving” at logical interface Vb is intended to be forwarded to logical interface Va.  
         [0041]    Furthermore, the mapping M 2 ′ specifies that a data element with destination 1.2.3.4 and “arriving” at logical interface Vc or logical interface Vd is to be forwarded to communication interface z, a data element with destination 1.2.3.4 and received at communication interface w is to be forwarded to communication interface z, a data element with destination 1.2.3.4 and received at communication interface z is to be forwarded to the control plane (because it should never have entered the router  200 ), a data element with destination 1.3.2.7 and arriving at communication interface z is intended to be forwarded to logical interface Vc, a data element with destination 1.3.2.7 and received at communication interface w is intended to be forwarded to logical interface Vd, a data element with destination 1.3.2.7 and “arriving” at logical interface Vc is intended to be forwarded to logical interface Vd, a data element with destination 1.3.2.7 and “arriving” at logical interface Vd is intended to be forwarded to logical interface Vc, a data element with destination 1.5.7.9 and received at communication interface z is intended to be forwarded to logical interface Vc, a data element with destination 1.5.7.9 and received at communication interface w is intended to be forwarded to logical interface Vd, a data element with destination 1.5.7.9 and “arriving” at logical interface 1.5.7.9 is intended to be forwarded to logical interface Vd, a data element with destination 1.5.7.9 and “arriving” at logical interface Vd is intended to be forwarded to logical interface Vc, a data element with destination 2.4.6.8 and “arriving” at logical interface Vc or logical interface Vd is to be forwarded to communication interface w, a data element with destination 2.4.6.8 and received and communication interface z is to be forwarded to communication interface w and a data element with destination 2.4.6.8 and received at communication interface z is to be forwarded to the control plane (because it should never have entered the router  200 ).  
         [0042]    The consolidated mapping M 3 ′ consists of two halves, the first half dealing with data elements received by the router  200  at communication interfaces x and y (resulting in the creation of the mapping M 3 ′→) and the second half dealing with data elements received by the router  200  at communication interfaces z and w (resulting in the creation of the mapping M 3 ′←). The creation of mapping M 3 ′→ is illustrated in FIG. 4B, while the creation of mapping M 3 ′← is illustrated in FIG. 4C. Of course, each of the halves of the consolidated mapping M 3 ′ is itself a consolidated mapping and its construction falls within the scope of the present invention.  
         [0043]    With reference to FIG. 4B, mapping M 3 ′→ is constructed by taking a basic portion of the mapping M 1 ′, denoted M 1 ′→ BASIC , which relates to data elements received at the communication interfaces x and y, and consolidating it with an augmented portion of the mapping M 2 ′, denoted M 2 ′→ AUG , which relates to the portion of the mapping M 2 ′ in which a next hop interface is provided for those data elements that would have been routed to logical router R 2  by logical router R 1 . Hence, M 2 ′ AUG includes only the portion of the mapping M 2 ′ that specifies the next hop interface for data elements “arriving” at logical interface Vc or logical interface Vd, since these are the only data elements that would have been forwarded to logical router R 2  by logical router R 1  if these logical routers were implemented separately. Now, by replacing those portions of M 1 ′→ BASIC  which specify a forwarding action towards logical router R 2  with a corresponding portion of M 2 ′→ AUG  that continues the forwarding process, one has created the mapping M 3 ′→.  
         [0044]    In the result, the mapping M 3 ′→ specifies that a data element with destination 1.2.3.4 and received at communication interface x or communication interface y will be forwarded to communication interface z (combination of M 1 ′→ BASIC  and M 2 ′ →AUG ), a data element with destination 1.3.2.7 and received at communication interface y will be forwarded to communication interface x (as per M 1 ′→ BASIC ), a data element with destination 1.3.2.7 and received at communication interface x will be forwarded to the control plane (as per M 1 ′→ BASIC ), a data element with destination 1.5.7.9 and received at communication interface x will be forwarded to communication interface y (as per M 1 ′→ BASIC ), a data element with destination 1.5.7.9 and received at communication interface y will be forwarded to the control plane (as per M′→ BASIC ) and a data element with destination 2.4.6.8 and received at communication interface x or communication interface y will be forwarded to communication interface w (combination of M 1 ′→ BASIC  and M 2 ′→ AUG ).  
         [0045]    Of note is the fact that the mapping M 3 ′→ is a single-next-hop mapping function, which means that a data element is routed immediately to the same communication interface after one lookup as it would have been routed to if it had followed multiple passes (through the mappings M 1 ′→ BASIC  and M 2 ′→ AUG ). Stated differently, the net effect of the mapping M 3 ′→ is identical to the net forwarding behaviour of the cluster  10  from the point of view of data elements received at the communication interfaces x and y. Furthermore, no communication interfaces need to be reserved for intra-router communications. Moreover, no data element will ever be “forwarded” by the router  200  to a logical interface via the data plane, which is consistent with the notion that the logical interfaces Va, Vb, Vc, Vd, do not exist as physical entities.  
         [0046]    With reference now to FIG. 4C, mapping M 3 ′← is constructed by taking a basic portion of the mapping M 2 ′, denoted M 2 ′← BASIC , which relates to data elements received at the communication interfaces x and y, and consolidating it with an augmented portion of the mapping M 1 ′, denoted M 1 ′← AUG , which relates to the portion of the mapping M 1 ′ in which a next hop interface is provided for those data elements that would have been routed to logical router R 1  by logical router R 2 . Hence, M 1 ′← AUG  includes only the portion of the mapping M 1 ′ that specifies the next hop interface for data elements “arriving” at logical interface Va or logical interface Vb, since these are the only data elements that would have been forwarded to logical router R 1  by logical router R 2  if these logical routers were implemented separately. Now, by replacing those portions of M 2 ′← BASIC  which specify a forwarding action towards logical router R 1  with a corresponding portion of M 1 ′← AUG  that continues the forwarding process, one has created the mapping M 3 ′←.  
         [0047]    In the result, the mapping M 3 ′← specifies that a data element with destination 1.3.2.7 and received at communication interface z or communication interface w will be forwarded to communication interface x (combination of M 2 ′← BASIC  and M 1 ′← AUG ), a data element with destination 1.2.3.4 and received at communication interface w will be forwarded to communication interface z (as per M 2 ′← BASIC ), a data element with destination 1.2.3.4 and received at communication interface z will be forwarded to the control plane (as per M 2 ′← BASIC ), a data element with destination 2.4.6.8 and received at communication interface z will be forwarded to communication interface w (as per M 2 ′← BASIC ), a data element with destination 2.4.6.8 and received at communication interface w will be forwarded to the control plane (as per M 2 ′← BASIC ) and a data element with destination 1.5.7.9 and received at communication interface z or communication interface w will be forwarded to communication interface y (combination of M 2 ′← BASIC  and M 1 ′← AUG ).  
         [0048]    Of note is the fact that the mapping M 3 ′← is a single-next-hop mapping function, which means that a data element is routed immediately to the same communication interface after one lookup as it would have been routed to if it had followed multiple passes (through the mappings M 2 ′← BASIC  and M 1 ′← AUG ). Stated differently, the net effect of the mapping M 3 ′ is identical to the net forwarding behaviour of the cluster  10  from the point of view of data elements received at the communication interfaces z and w. Furthermore, no communication interfaces need to be reserved for intra-router communications. Moreover, no data element will ever be “forwarded” by the router  200  to a logical interface via the data plane, which is consistent with the notion that the logical interfaces Va, Vb, Vc, Vd do not exist as physical entities.  
         [0049]    Of course, it is possible to combine the mappings M 3 ′→ and M 3 ′← into a single mapping M 3 ′, which would specify the same net forwarding behaviour as the cluster  10  from the point of view of data elements received at any of the communication interfaces x, y, z, w.  
         [0050]    Those skilled in the art will appreciate that there are many ways to implement a consolidated mapping that has the same overall effect as multiple mappings for multiple routers, and the utility of the consolidated mapping concept is independent of the precise implementation. The result of applying the consolidated mapping to the physical data plane is that each data element is processed once by the data plane to produce the same result that would be produced if the appropriate logical router mappings were applied sequentially.  
         [0051]    In addition to being forwarded, a received data element may undergo other actions by the router that are composite actions based on actions specified for the two logical routers R 1  and R 2 . In accordance with an embodiment of the present invention, the final action taken by the router  200  with respect to a given data element will be a function of the path through the cluster  10  that would have been followed if the logical routers had been implemented separately. As a practical matter, some actions are independent of subsequent actions, other actions are superseded by subsequent actions, and still other actions are modified by subsequent actions. For example a first action of “encapsulate” and a second action of “de-encapsulate” would result in a final action of “do nothing”. By way of another example, the action “use priority 1” may be superseded by a subsequent action “use priority 2.” 
         [0052]    Those skilled in the art will appreciate that the concept of a consolidated mapping function is useful for any data plane architecture, but it is particularly useful in modern high-speed switching equipment with distributed data plane processing. Note that the partitioning of the physical data plane to permit distribution is independent of the partitioning of the system into logical data communications forwarding systems. The consolidated mapping concept applies to the data plane as a whole. When the consolidated mapping is implemented on a distributed data plane, it is possible to partition the processing to align it to the logical switch partitioning, or to the data plane partitioning, or to both. The precise implementation will depend on the operational requirements of the system, as determined by those of ordinary skill in the art.  
         [0053]    Those skilled in the art will also appreciate that the consolidated mapping concept is useful even when a convolution is not exhaustively applied. For example, in certain architectures it may be necessary to constrain the mapping functions that can be applied to the logical interfaces. This is merely a specific instance of a general phenomenon whereby different interface types have different constraints. To the extent that these capabilities differ from the capabilities of a physical interface between physical switches, the functionality of the physical system instantiating the logical switches will differ from an equivalent collection of interconnected physical switches.  
         [0054]    Moreover, the present invention may be applied to a multicast environment. In the sense of this discussion, the term “multicast” means the receipt of a single unit of data that results in its replication and transmission to more than one egress point. This is a generalization of the way the term is used with respect to the Internet Protocol (IP). For multicast, each mapping function (for each of the logical routers) specifies a one-to-many mapping (a multicast “tree”) of the ingress space, and the consolidated mapping specifies the convolved mapping, which will also be a one-to-many mapping. In order to achieve this, the convolution follows each “branch” of the multicast tree.  
         [0055]    Also, in most practical applications, the control planes of the logical routers R 1  and R 2  (taken from the above-described example) will be implemented separately within the single physical router  200 , with control signaling passing among the individual control planes. However, those skilled in the art will appreciate that the present invention can also be applied to the control planes of the logical routers R 1 , R 2  in addition to being applied to their data planes, which would effectively result in the creation of a single “consolidated” control plane.  
         [0056]    It will be understood that the processors used in the data plane or the control plane may be each implemented as an arithmetic and logic unit (ALU) having access to a code memory (not shown) which stores program instructions for the operation of the ALU. The program instructions could be stored on a medium which is fixed, tangible and readable directly by the processor (e.g., removable diskette, CD-ROM, ROM, or fixed disk), or the program instructions could be stored remotely but transmittable to the processor via a modem or other interface device (e.g., a communications adapter) connected to a network over a transmission medium. The transmission medium may be either a tangible medium (e.g., optical or analog communications lines) or a medium implemented using wireless techniques (e.g., microwave, infrared or other transmission schemes).  
         [0057]    Those skilled in the art should also appreciate that the program instructions stored in the code memory can be compiled from a high level program written in a number of programming languages for use with many computer architectures or operating systems. For example, the high level program may be written in assembly language, while other versions may be written in a procedural programming language (e.g., “C”) or an object oriented programming language (e.g., “C++” or “JAVA”).  
         [0058]    Those skilled in the art should further appreciate that in some embodiments of the invention, the functionality of the processors may be implemented as pre-programmed hardware or firmware elements (e.g., application specific integrated circuits (ASICs), electrically erasable programmable read-only memories (EEPROMs), etc.), or other related components.  
         [0059]    While specific embodiments of the present invention have been described and illustrated, it will be apparent to those skilled in the art that numerous modifications and variations can be made without departing from the scope of the invention as defined in the appended claims.
Generation of a mapping for use by a data forwarding entity having communication interfaces and instantiating multiple logical forwarding sub-systems associated with respective mappings including a first mapping and a second mapping. The first mapping specifies a next hop interface for data elements received at the interfaces, at least one next hop interface belonging to a set of logical interfaces. The second mapping specifies a second next hop interface for certain data elements for which the next hop interface specified by the first mapping belongs to the set of logical interfaces, at least one second next hop interface belonging to the plurality of communication interfaces. A consolidated mapping is created by replacing each portion of the first mapping that specifies a next hop interface belonging to the set of logical interfaces by a corresponding portion of the second mapping that specifies a second next hop interface. Efficiency arises when the same data is processed by more than one logical forwarding sub-system in the same physical forwarding system.