BACKGROUND

[002] Modular routers comprise external facing line cards (LCs) that are interconnected with a plurality of internal fabric modules (FMs). In a typical implementation, each LC is interconnected with each FM such that a packet received at a given port on a given LC can be passed to any FM and then sent out of, or transmitted from, any port on the given LC or any other LC. In this way, a router can effectively route a packet, using an appropriate forwarding engine or table stored in the respective LCs and/or FMs. That is, when a packet is received at a LC and the packet can be routed based on a routing table in the LC, the packet may be routed locally (i.e., by the receiving LC) and transmitted toward a next hop in a network (e.g., another router or final destination). If the routing table stored in the LC cannot route the packet, the packet may be forwarded to a FM. The fabric module may store its own separate routing tables, where the routing tables stored in the FMs may complement the routing tables stored in the LCs. Once routing is performed on the packet within a FM, the packet may be redirected to a LC for transmission to the next hop.

BRIEF DESCRIPTION OF THE DRAWINGS

[003] FIG. 1 depicts a network topology in which a router configured according to an example embodiment may be deployed.

[004] FIG. 2 depicts a schematic view of a router with modular line cards and fabric modules according to an example embodiment.

[005] FIG. 3 is a table depicting different profiles by which Internet Protocol (IP) v4 and IPv6 forwarding table space can be allocated according to an example embodiment.

[006] FIGs. 4A and 4B depict how the profiles set forth in FIG. 3 can be allocated across the line cards and fabric modules in the modular router according to an example embodiment. [007] FIG 5. depicts another implementation of a router including a fabric module having four separate chips according to an example embodiment.

[008] FIG. 6 depicts the flow of packets through a fabric module having four separate chips according to an example embodiment.

[009] FIG. 7 is a chart depicting how a given packet received at a fabric module may be treated.

[010] FIG. 8 is another example flow chart depicting several operations for performing packet routing according to an example embodiment.

DESCRIPTION OF EXAMPLE EMBOD EVENTS

Overview

[Oil] Aspects of the invention are set out in the independent claims and preferred features are set out in the dependent claims. Features of one aspect may be applied to the aspects alone or in combination with other aspects.

[012] In one embodiment described herein there is provided an apparatus, such as a router, that includes a chassis, a plurality of line cards disposed in the chassis and configured to be in communication with a network, each line card comprising at least two line card processors each comprising a memory storing first routes for routing a packet, and a plurality of fabric modules disposed in the chassis and communicatively coupled to the plurality of line cards, each fabric module comprising at least two fabric module processors each comprising a memory storing second routes for routing the packet, wherein the first routes are different from the second routes.

[013] In another embodiment described herein there is provided a method including receiving a packet at a line card of a router, the packet conforming to one of a first addressing scheme or a second addressing scheme, passing the packet to a fabric module of the router, the fabric module comprising a routing engine, the routing engine comprising a first fabric module processor storing routes to route packets conforming to the first addressing scheme and a second fabric module processor storing routes to route packets conforming to the second addressing scheme; and when the packet conforms to the first addressing scheme and is received at the first fabric module processor, performing routing on the packet by the first fabric module processor and switching the packet to the second fabric module processor for forwarding back to the line card or another line card, and when the packet conforms to the second addressing scheme and is received at the first fabric module processor, switching the packet to the second fabric module processor and performing routing on the packet by the second fabric module processor, and forwarding the packet to the line card or the another line card.

[014] Further systems and apparatus for implementing the methods described herein, including network nodes, computer programs, computer program products, computer readable media and logic encoded on tangible media for implementing the methods are also described.

Example Embodiments

[015] FIG. 1 depicts a network topology in which a router configured according to an example embodiment may be deployed. As shown in the drawing, routers 200 interconnect respective data networks 150, 152, 154. In certain present day implementations, data packets may be communicated from one endpoint to another endpoint using Internet Protocol (IP) addressing. There are currently two "flavors" of the Internet Protocol, namely IPv4 and IPv6. Among other differences, IPv6 has increased address space enabling an increased number of uniquely addressable endpoints compared to the number of uniquely addressable endpoints supported by IPv4. Routers 200 are configured to route or forward both IPv4 and IPv6 packets. As further shown in FIG. 1, a given router 200 may be a modular router comprising a chassis 205 that is configured to host a plurality of physical line cards (LCs) 210 and a plurality of physical fabric modules (FMs) 250.

[016] There are, however, limitations in conventional modular data packet routing and switching technologies. One limitation is that a forwarding engine (comprising routing tables in the FMs and/or LCs) is programmed identically across all cards, and thus a scale of a given router is limited to a table size of the single forwarding engine. Another limitation is that, in network platforms, forwarding tables may be programmed symmetrically on all forwarding engines.

[017] FIG. 2 depicts a router 200 with modular line cards (LCs) 210 and fabric modules (FMs) 250 according to an example embodiment. As shown, each LC 210, in the depicted implementation, includes two separate integrated circuit chips 211 each having, e.g., 32 ports. Each FM 250, in the depicted implementation, also includes two separate integrated circuit chips 251. Each of the integrated circuit chips may include memory 280 integrally fabricated therewith and/or accessible thereto via a bus (not shown). In one implementation, chassis 205 of router 200 includes eight line cards 210 (for a total of 16 LC chips 211) and four FMs 250 (for a total of eight FM chips 251).

[018] LC 211 chips and FM chips 251 depicted in FIG. 2 may be, e.g., BCM56960 application specific integrated circuits (ASICs) chips manufactured by Broadcom, Irving, CA, or any like ASIC or processor with similar functionality and sufficient ports. In the instant implementation, each chip includes 32 ports. In the depicted example embodiment, 16 ports on each LC chip 211 are employed as externally facing ports 230 and interconnect with a given network, e.g., network 150, 152 and/or 154. The other 16 ports on each LC chip 211 are in communication with each of the FMs 250 via links 235. More specifically, as shown in FIG. 2, each LC chip 211 has two ports connected to each FM chip 251 on each FM 250. With four FMs 250, each having two FM chips 251, each LC chip 211 can be connected to each FM chip 251 (2 ports of each LC chip 211 connected to each of the eight FM chips 251). In an embodiment, externally facing ports 230 support 100 gigabit connectivity, and links 235 support 106 gigabit connectivity.

[019] As will be explained more fully below, LC chips 211 and FM chips 251 are loaded with routing or forwarding tables in particular ways to support the routing of IPv4 and IPv6 communications traffic through router 200. At a high level, LC chips 211 and FM chips 251 are configured such that all or most of the IPv4 and IPv6 host address space is loaded or programmed on LC chips 211 and the less precise longest prefix match (LPM) address space for IPv4 and for IPv6 is loaded or programmed on FM chips 251. In this way, when a packet or frame is received at a give LC chip 211, it is possible that the packet or frame can be routed without having to be passed to the FMs 250, thus reducing latency. In addition, to the extent the volume of IPv4 versus IPv6 traffic is known at a given node, it is possible to dedicate certain FMs 250 to predetermined types of traffic. More specifically, selected FMs of the eight FM chips 251 can be assigned to handle either IPv4 or IPv6 traffic exclusively such that one of the following possible IPv4:IPv6 chip ratios results: 1 :7, 2:6, 3 :5, 4:4, 5:3, 6:2 or 7: 1. Knowing a priori the type of traffic that a given router 200 might handle can help to decide which ratio might be most suitable in a given application.

[020] Reference is now made to FIG. 3, which is a table depicting different profiles by which IPv4 and IPv6 forwarding table space can be allocated among the LC chips 211 and FM chips 251 according to an example embodiment. Two profiles are presented, but those skilled in the art will appreciate that other profiles by which IPv4 and IPv6 forwarding table space can be allocated are possible.

[021] As shown in FIG. 3, two types of address spaces are allocated in a particular manner to ensure sufficient routing table space to handle the IPv4 and IPv6 traffic. For example, Profile- 1 allocates traffic as follows: 128k IPv4-LPM (/31) routes (with the "/" slash denoting Classless Inter-Domain Routing (CIDR) notation), 50K IPv4-Host (/32) routes, 84K IPv6-LPM (/64) routes and lk IPv6-Host (/128) routes. The allocations of Profile- 1 are depicted in FIG. 4 A. Note that LC chips and FM chips 251, as a result of memory constraints, can hold up to, e.g., (a) 128K LPM IPv4 routes, (b) 84K IPv6 LPM, or (c) host-entries. As will be seen, since at least some of the profiles have route scales that are larger than the capacity of a given FM chip 251, some part of the routing table is stored in a LC chip 211 that has capacity. One approach in accordance with the embodiments described herein is to place as many LPM routes on the FM chips 251 and keep host routes on the LC chips 211. Thus, in the case of Profile- 1 depicted in FIG. 4A, FM chip 251(1) includes 128K of IPv4 LPM routes, and FM chip 251(2) includes 84K of IPv6 LPM routes. LC chips 221(1) and 211(2) include 50K of IPv4 host routes and lk IPv6 host routes. Additional space is available on LC chips 211(1) and 211(2).

[022] Profile-2 of FIG. 3 is depicted in FIG. 4B. In the case of Profile-2, FM chip 251(1) includes 112K of IPv4 LPM routes, and FM chip 251(2) includes 84K of IPv6 LPM routes. LC chips 221(1) and 211(2) are symmetric and include 45K IPv4 host routes, 59K IPv6 LPM routes and 500 IPv6 host routes. Additional space is available on LC chips 211(1) and 211(2) in the case of the implementation of Profile-3.

[023] Thus, as one of ordinary skill in the art will appreciate, it is possible in accordance with the embodiments described herein to allocate routes across the available chips in LCs 210 and FMs 250 in several different ways. The allocations can be based on a priori knowledge of traffic flows through a given router 200, with a goal being to have most, if not all, IPv4 and IPv6 host routes stored on LCs 211 so that the most direct route for an incoming given frame or packet can be routed without even having to access an FM 250.

[024] And, in an effort to further account for likely traffic flow, and avoid the potential for dropped packets as a result of "hot spots" due to traffic overload, the total of eight FM chips 251 in a given chassis 205 can be separately designated to handle only IPv4 or IPv6 traffic. Specifically, the eight FM chips 251 can be assigned to operate exclusively on IPv4 or IPv6 traffic in the following possible IPv4:IPv6 FM chip ratios: 1 :7, 2:6, 3 :5, 4:4, 5:3, 6:2 or 7: 1. Thus, taking as an example the 1 :7 ratio, one FM chip (out of the eight) can be designated to handle all IPv4 traffic routing, while the other seven FM chips can be designated to route IPv6 traffic.

[025] When given FM chips 251 are dedicated to a given type of traffic, then LCs 210 are configured to determine whether a received packet or frame is IPv4 or IPv6 traffic and accordingly forward that packet or frame to the appropriate dedicated FM chip 251. However, where a give type of traffic begins to overload the dedicated FM chips, packets may be dropped.

[026] FIG. 5 depicts another implementation for components for a router 500 including a fabric module 550 having four separate chips (e.g., ASICs) according to an example embodiment. This embodiment can have the effect of addressing the hot spot issue noted above. More specifically, in accordance with the instant embodiment, each router chassis 205 includes eight LCs 211, each comprising two chips 211(1), 211(2). This is the same LC configuration as shown in, e.g., FIG. 2. Each FM 550, however, comprises four individual chips 551(l)a, 551(l)b, 551(2)a, 551(2)b. As also shown in FIG. 5, the four chips in FM 250 are paired together into two routing engines 555(1), 555(2).

[027] In the depicted embodiment, FM chip 551(l)a stores only IPv4 routes, and FM chip 551 ( 1 )b stores only IPv6 routes. Similarly, FM chip 551(2)a stores only IPv4 routes, and FM chip 551(2)b stores only IPv6 routes. Moreover, in a particular implementation, routing engines 555(1), 555(2) are programmed identically, i.e., the same IPv4 routes are programmed in all chips designated to route IPv4 traffic, and the same IPv6 routes are programmed in all chips designated to route IPv6 traffic. Thus, in the example depicted in FIG. 5, FM chips 551(l)a and 551(2)a store, or are programmed with, the same IPv4 routes, and FM chips 551 ( 1 )b and 551(2)b store, or are programmed with, the same IPv6 routes. Where there are additional routes that cannot fit on the FM chips due to memory constraints, such "spillover" routes may be programmed on LC chips 211(1), 211(2).

[028] LCs 211(1), 211(2) each have 16 externally facing ports in communication with a network, and 16 ports that are respectively communicatively coupled with each FM chip. As in FIG. 2, a given chassis 205 is configured to host four FMs 550. Each FM 550, in the embodiment shown in FIG. 5 includes four FM chips for a total of 16 FM chips. Thus, each LC chip 211(1), 211(2) is connected to each one of the FM chips 551(l)a, 551(l)b, 551(2)a, 551(2)b, etc. via a single respective port.

[029] In the instant embodiment, the paired FM chips in a given routing engine 555(1) or 555(2) are communicatively coupled to one another via a trunk 510(1), 510(2) using each of the remaining 16 ports (i.e., the ports not connected to LC chips 211(1), 21 1(2)). Trunks 510(1), 510(2) may be a high speed 106G links.

[030] FIG. 6 depicts the flow of packets or frames through one routing engine 555(1), which includes FM chips 551(l)a, 551 ( 1 )b according to an example embodiment. FM chips 551 ( 1 )a, 551 ( 1 )b are respectively in communication with LCs 210 via high speed 106G single port links 235. In one implementation, as a result of load balancing techniques, any packet or frame received at a LC 210 can be forwarded to any FM chip. As a result, both IPv4 and IPv6 traffic can be sent to any FM chip. Accordingly, the instant embodiment is configured such that all traffic received at a FM 550 from any LC 210 is passed through both FM chips 551(l)a, 55 l(l)b to ensure that proper routing (e.g., IPv4 or IPv6 as the case may be) can be performed. For example, assume an IPv4 packet is received at FM chip 551(1 )(b) (which stores IPv6 routes). That packet is switched over to FM chip 551(l)a for routing and then passed back to a selected LC 210. If the received packet is an IPv6 packet, then FM chip 551 ( 1 )b will first perform routing for the packet and then pass the packet to FM chip 551(l)a, which will merely pass the packet back to a selected LC 210. FIG. 6 expressly depicts IPv4 traffic passing both ways 610, 620 between FM chips 551(1 )a, 551(1 )b via trunk 510(1). Those skilled in the art will appreciate that IPv6 traffic passes between FM chips 551 ( 1 )a, 551 ( 1 )b in the same manner, and that FM chip 551 ( 1 )b (which stores IPv6 routes) will perform routing for the packet, or will switch an IPv4 packet to FM chip 551(l)a for routing. [031] In sum, and as explained with respect to the first described embodiment, a modular router can be implemented such that all (or most) host routes (both IPv4 and IPv6) are programmed in the LCs, and that all (or most) longest prefix match (LPM) routes (both IPv4 and IPv6) are programmed in the FMs. Such an embodiment enables particular efficiencies in routing, and with two chips available for each FM, expanded routing tables can be achieved.

[032] In the second described embodiment, a further enhancement is made to a hierarchical routing methodology. In this second embodiment, all (or most) host routes are programmed in the LCs as in the first embodiment. However, instead of having two chips or ASICs per FM, four chips or ASICs are provided and pairs of chips are coupled together in series, with each chip programmed with IPv4 (LPM) routes or IPv6 (LPM) routes.

[033] By programming V4-LPM routes on the "a" chips and V6-LPM routes on the "b" chips it is possible to scale up to 3 times the routing space capacity compared to a configuration having only a single chip in a given FM. As explained above, the traffic flow is such that if traffic arrives from LCs to FM chip 551(l)a, it is always forwarded on the inter-connect link to FM chip 55 l(l)b and vice versa. This ensures that there is no traffic over-subscription on the inter-connect links. The lookups will take place as a "bridge/route" or "route/bridge" flow depending on the route being present in the first block or the second block. That is, depending on whether the received traffic is IPv4 or IPv6 and depending at which chip the traffic arrives, the traffic will be routed (using the programmed route tables) then switched (bridged) to the other chip for egress to a LC, or switched (bridged) to the other chip where it will be routed (using the programmed route tables) then sent for egress toward a LC.

[034] It is noted that the foregoing method can be extended by increasing the number of chips in series and programming routes appropriately to have a much larger table capacity.

[035] FIG. 7 is a chart depicting how a given packet received at a fabric module in accordance with the embodiments described herein may be treated. As mentioned, presently, IP traffic comes in two flavors, IPv4 and IPv6, and as explained above, such traffic is handled differently depending on whether it is received at a FM chip that stores IPv4 routes or IPv6 routes. The treatment of a packet or frame by a given routing engine, e.g., 555(1) is set forth in FIG.7. Taking an IPv4 packet first as an example, if such an IPv4 packet arrives at a processor (e.g., FM chip/ASIC) that is programmed to route IPv4 traffic, the packet is routed by that processor and then switched to the processor (FM chip/ASIC) that is programmed to route IPv6 traffic. If an IPv4 packet arrives at a processor that is programmed to route IPv6 traffic, the packet is switched to the processor that is programmed to route IPv4 traffic.

[036] When a packet consistent with IPv6 addressing arrives at a processor that is programmed to route IPv4 traffic, the packet is switched to a processor that is programmed to route IPv6 traffic. If an IPv6 arrives at a processor that is programmed to route IPv6 traffic, the packet is routed and then switched to the processor that is programmed to route IPv4 traffic.

[037] Thus, as can be seen, all traffic that reaches a routing engine, e.g., 555(1) in a FM is passed through each FM chip in that routing engine in a serial manner. One chip (or ASIC/processor) will perform routing on the packet, while the other will merely switch the packet to the other FM chip within the routing engine, or will switch the routed packet to a given LC.

[038] FIG. 8 is an example flow chart depicting several operations for performing packet routing according to an example embodiment. Methodology 800 begins at 810 where a packet or frame is received at a line card. At 812, the line card passes the packet to a first fabric module processor. At 814, it is determined which address is being employed for the packet, e.g., the IPv4 or IPv6 addressing scheme. Assuming the packet is received at a fabric module processor programmed to route IPv4 traffic, at 816, packet routing is performed. At 818, the packet is switched to a paired second fabric module processor (e.g., one programmed to route IPv6 traffic). At 820 the packet is forwarded from the second fabric module processor to either the line card from which the packet was originally received or to another line card.

[039] If, at 814, it was determined that the packet was addressed using the IPv6 addressing scheme, then at 830 the packet is switched to the second fabric module processor and, at 832, the packet routing is performed at the second fabric module processor. The packet is thereafter forwarded from the second fabric module processor to either the line card from which the packet was originally received or to another line card.

[040] In the embodiments described herein the processors 211, 251, 551(l)a, etc. may be, for example, microprocessors or microcontrollers that execute instructions for implementing the processes described herein. Memory 280 may comprise read only memory (ROM), random access memory (RAM), magnetic disk storage media devices, optical storage media devices, flash memory devices, electrical, optical, or other physical/tangible (e.g., non-transitory) memory storage devices. Thus, in general, memory 280 may comprise one or more tangible (non- transitory) computer readable storage media (e.g., a memory device) encoded with software comprising computer executable instructions and when the software is executed (by, e.g., processor 211) is operable to perform the operations described herein.

[041] In sum, there is provided an approach to efficiently program routes on LCs and FMs in a modular router to avoid hot spots and thus avoid undesirable packet loss. There is also provided a unique architecture by which each FM chip or processor is replaced by a pair of FM chips arranged in series. Each FM chip is responsible for routing, e.g., IPv4 or IPv6 traffic. The pair of FM chips communicates with another via a trunk and any packet received at either one of the pair is passed to the other of the pair before being passed back to a line card.

[042] More specifically, an apparatus includes a chassis, a plurality of line cards disposed in the chassis and configured to be in communication with a network, each line card comprising at least two line card processors each comprising a memory storing first routes for routing a packet; and a plurality of fabric modules disposed in the chassis and communicatively coupled to the plurality of line cards, each fabric module comprising at least two fabric module processors each comprising a memory storing second routes for routing the packet, wherein the first routes are different from the second routes. In one implementation, the memory of one of the at least two fabric modules is programmed with only Internet Protocol (IP) v4 routes, and the memory of the other of the at least two fabric modules is programmed with only IPv6 routes.

[043] In another embodiment, a method includes receiving a packet at a line card of a router, the packet conforming to one of a first addressing scheme or a second addressing scheme, passing the packet to a fabric module of the router, the fabric module comprising a routing engine, the routing engine comprising a first fabric module processor storing routes to route packets conforming to the first addressing scheme and a second fabric module processor storing routes to route packets conforming to the second addressing scheme, when the packet conforms to the first addressing scheme and is received at the first fabric module processor, performing routing on the packet by the first fabric module processor and switching the packet to the second fabric module processor for forwarding back to the line card or another line card, and when the packet conforms to the second addressing scheme and is received at the first fabric module processor, switching the packet to the second fabric module processor and performing routing on the first packet by the second fabric module processor, and forwarding the packet the line card or the another line card.

[044] In still another embodiment, there is provided an apparatus including a chassis, a line card, disposed in the chassis, and a fabric module, disposed in the chassis and in communication with the line card, comprising a routing engine including a memory, the routing engine comprising a first fabric module processor storing routes to route packets conforming to a first addressing scheme and a second fabric module processor storing routes to route packets conforming to a second addressing scheme, the fabric module configured to, when a packet received at the line card and passed to the fabric module conforms to the first addressing scheme and is received at the first fabric module processor, perform routing on the packet by the first fabric module processor and switch the packet to the second fabric module processor for forwarding back to the line card or another line card, and the fabric module configured to, when the packet conforms to the second addressing scheme and is received at the first fabric module processor, switch the packet to the second fabric module processor and perform routing on the packet by the second fabric module processor, and forward the packet to the line card or the another line card.

[045] The above description is intended by way of example only. Various modifications and structural changes may be made therein without departing from the scope of the concepts described herein and within the scope and range of equivalents of the claims.