Simple topology transparent zoning in network communications

An autonomous system (AS) comprising a topology transparent zone (TTZ) comprising a plurality of TTZ nodes, wherein the plurality of TTZ nodes includes an edge node and an internal node, wherein each of the plurality of TTZ nodes is configured to connect to another TTZ node via an internal link, and a plurality of neighboring external nodes connected to the TTZ edge nodes via a plurality of external links, wherein no link state advertisements (LSAs) describing the internal links are distributed to the neighboring external nodes.

Not applicable.

REFERENCE TO A MICROFICHE APPENDIX

Not applicable.

BACKGROUND

As more and more nodes (e.g., routers) are added into a conventional communications network, the size of the network increases, and issues such as scalability and slow convergence may arise. In communication networks such as the Internet, an autonomous system (AS) may have a common routing policy (either in a single network or in a group of networks) that is controlled by a network administrator (or group of administrators on behalf of a single administrative entity, such as a university, a business enterprise, or a business division). Within the Internet, an AS comprises a collection of routers exchanging routing information via a common routing protocol. Each AS on the Internet may be assigned a globally unique number, which is sometimes called an AS number (ASN).

In a network comprising a single autonomous system (AS) with a single area, each node needs to be aware of the positional relationships (i.e., adjacencies) of all other nodes, such that all nodes may build a topological map of the AS. Nodes may learn about one another's adjacencies by flooding link-state information throughout the network according to one or more interior gateway protocols (IGPs) including, but not limited to, open shortest path first (OSPF) or intermediate system (IS) to IS (IS-IS). Specifically, nodes engaging in IGPs may distribute their own link state advertisements (LSAs) describing their own adjacencies to all their neighboring nodes, which may forward the received LSAs to all their neighboring nodes (except the node from which the LSA was received). This may allow the LSA to be distributed throughout the network such that all network nodes become aware of one another's adjacencies, thereby allowing the various nodes to build topology graphs (e.g., link state databases (LSDBs)). LSAs may be flooded upon network initialization as well as whenever a network adjacency changes (e.g., a node is added/removed or a node/link fails). A network change may lead to every node in the network to re-compute a shortest path to each destination, to update its routing information base (RIB) and its forwarding information base (FIB). Consequently, as more nodes are added to a network, link state distributions and shortest path computations may begin to consume more and more network resources, such as bandwidth and/or processing time.

A prior art technique for addressing scalability and performance issues in large networks is to define smaller areas of IGP (e.g., OSPF areas or IS-IS areas/levels) in an attempt to reduce the number of LSAs that are flooded throughout the network. This technique has been described by various publications, such as the Internet Engineering Task Force (IETF) publication request for comments (RFC) 2328 entitled “OSPF Version 2” (describing OSPF areas in an AS) and IETF publication RFC 1142 entitled “Open Systems Interconnection (OSI) IS-IS Intra-domain Routing Protocol” (describing IS-IS areas/levels in an AS). Specifically, each OSPF/IS-IS area comprises a number of interconnected routers, including both area border routers (ABRs) and internal routers. An ABR may be distinguished from an internal router in that the ABR may be connected to routers in two or more OSPF/IS-IS areas, while an internal router in an OSPF/IS-IS area may be connected only to other routers within the OSPF/IS-IS area. In most applications, the ABRs and internal routers will execute a normal link state distribution (e.g., according to an IGP) within their respective local OSPF/IS-IS areas, thereby allowing the ABRs to collect and summarize topology information (e.g., construct summary LSAs) describing their local OSPF/IS-IS area. Thereafter, the ABRs may distribute these summary LSAs to other ABRs on a backbone, thereby allowing the ABRs in external domains to develop a complete or partial topological understanding of the OSPF/IS-IS areas along the backbone. Depending on the network configuration, these summarized LSAs for an OSPF/IS-IS area may or may not be distributed to internal routers within the other OSPF/IS-IS areas.

Through splitting a network into multiple areas, the network may be further extended. However, there are a number of issues when splitting a network into multiple areas. For example, dividing an AS into multiple ASs or an area into multiple areas may involve significant network architecture changes. For another example, it may be complex to setup a multi-protocol label switching (MPLS) traffic engineering (TE) label switching path (LSP) crossing multiple areas. In general, a TE path crossing multiple areas may be computed by using collaborating path computation elements (PCEs) through the PCE communication protocol (PCEP), which may not be easy to configure by operators since manual configuration of the sequence of domains is required. Further, the current PCE method may not guarantee that the path found would be optimal. For yet another example, some policies may need to be reconfigured on ABRs for reducing the number of link states such as summary link-state advertisements (LSAs) to be distributed to other routers in other areas.

Furthermore, route convergence may be slower. A router in an OSPF area may see all other routers in the same area. A link-state change anywhere in an OSPF area may be populated everywhere in the same area, and may even be distributed to other areas in the same AS indirectly. For instance, all the routers and links in a point-of-presence (POP) in an OSPF area may be seen by all the other routers in the same area. Any link state change in the POP may be distributed to all the other routers in the same area, and may also be distributed to routers in other areas indirectly. A link state change in an area may lead to every router in the same area to re-calculate its OSPF routes, update its RIB and FIB. It may also lead to a number of link state distributions to other areas, which may trigger routers in other areas to re-calculate their OSPF routes, and update their RIBs and FIBs. Consequently, route convergence may become slower. As such, a simple and efficient scheme to address the above issues (e.g., in large networks) may be desired.

SUMMARY

In one embodiment, the disclosure includes an AS comprising a topology transparent zone (TTZ) comprising a plurality of TTZ nodes, wherein the plurality of TTZ nodes comprises an edge node and an internal node, wherein each of the plurality of TTZ nodes is configured to connect to another TTZ node via an internal link, and a plurality of neighboring external nodes connected to the TTZ edge nodes via a plurality of external links, wherein no link state advertisements (LSAs) describing the internal links are distributed to the neighboring external nodes.

In another embodiment, the disclosure includes a method of configuring a TTZ in an area of an AS, the method comprising assigning a TTZ identifier (ID) to a plurality of internal links that interconnect a plurality of TTZ nodes located within the TTZ, wherein each of the plurality of internal links interconnects a pair of the plurality of TTZ nodes, wherein the plurality of TTZ nodes includes at least one edge node and at least one internal node, sending a LSA from each of the at least one edge node via a plurality of external links to each of a plurality of neighboring external nodes located in the area, wherein each neighboring external node is connected to at least one of the edge nodes via at least one of the external links, and updating topology graphs in the neighboring external nodes based on each LSA, wherein the topology graphs do not contain any information regarding the at least one internal node or the plurality of internal links.

In yet another embodiment, the disclosure includes a router used in an area of an AS comprising a first port configured to connect to a first neighboring router via a first link, a second port configured to connect to a second neighboring router via a second link, and a topology graph configured to store information regarding the first and second neighboring routers, and the first and second links, wherein the first neighboring router and the second neighboring router are located within the area, wherein the first neighboring router does not contain any information regarding the second neighboring router or the second link, and wherein the second neighboring router contains information regarding the first neighboring router and the first link.

DETAILED DESCRIPTION

It should be understood at the outset that, although an illustrative implementation of one or more embodiments are provided below, the disclosed systems and/or methods may be implemented using any number of techniques, whether currently known or in existence. The disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims along with their full scope of equivalents. While certain aspects of conventional technologies have been discussed to facilitate the present disclosure, applicants in no way disclaim these technical aspects, and it is contemplated that the present disclosure may encompass one or more of the conventional technical aspects discussed herein.

FIG. 1illustrates an AS100comprising a single area101. The area101comprises a plurality of nodes110-158that may collectively engage in a common link state distribution. For example, the nodes110-158may include a source node110, a plurality of intermediate nodes112-156, and a destination node158, which are interconnected to form part of the internal architecture or topology of the AS100. The nodes110-158may be devices (e.g., transceivers, routers, modems, etc.) capable of switching data in a deterministic manner throughout the AS100. Each node may comprise one or more tables (e.g., LSDB, RIB and FIB tables) containing link state information that describes the topology of the AS100. A LSP (indicated by solid arrows) may be established across the AS100, which may allow traffic to be transported in a deterministic manner from one end of the AS100to the other. As shown, the LSP may extend from a source node110to a destination node158via one or more of the intermediate nodes112-156.

As the AS100grows larger and larger (e.g., comprising more and more nodes), scalability issues may arise, which may result from, for example, the inability of a large network to quickly compute a shortest path to every destination on each node, efficiently manage or distribute network topology information. For instance, the processing and storage capabilities of an individual node (e.g., node132) may practically limit the size of the AS100. Additionally, the ability to distribute link state information in a timely manner may be directly related to the number of nodes in which LSAs need to be exchanged/flooded. Consequently, larger networks may suffer from slower convergence. For example, larger networks may require a longer period required to build or update topology graphs, during which time data may be misdirected or lost.

Re-convergence in large networks may also be an issue, as the inability to timely recover from a fault in a node/link (or some other condition that changes a network adjacency subsequent to initialization) may disrupt network services, such as the traffic transported from node110to node158along the shortest path as shown inFIG. 1in the network. For example, in the event of a fault in the network, it may be necessary to flood LSAs throughout the AS100to inform each of the nodes110-158of the change in network topology. As used herein, the length of time required to distribute the topology information throughout the network (and update the appropriate RIB/FIB tables in the relevant nodes) may be referred to as a re-convergence period (or a convergence period if occurring during network initialization).

Re-convergence periods may significantly impact the ability to timely recover from faults in a path, and therefore affect the maximum Quality of Service (QoS) level supported by the network. Specifically, a network fault may affect one or more paths, which may be broken until a recovery procedure can be completed. For instance, a fault in the node134or the link between the nodes132and134may cause the path (solid arrows) to be temporarily broken. In response to detecting the fault, one or more of the nodes110-158may flood LSAs throughout the network to inform the other nodes of the topological change (i.e., that the adjacency between the nodes132and134no longer exists, or is temporarily unavailable). Subsequently, one or more of the nodes110-158may recompute a shortest path to every destination, update the RIB and FIB. Only after every node in the network receives the LSAs about the fault, recomputed the shortest path to every destination, and update the RIB and FIB, can transportation of the network traffic resume to normal. Hence, re-convergence periods directly affect the ability to timely recover from faults, and therefore substantially affect the ability of networks to meet QoS requirements of their various service agreements.

As discussed above, prior art techniques for dealing with scalability/convergence issues in large networks involve defining a plurality of OSPF/IS-IS areas within an AS.FIG. 2Aillustrates an AS200comprising a single area201, which may be similar to the area101inFIG. 1except that the area201may comprise a relatively higher number of nodes.FIG. 2Billustrates the AS200, originally comprising one area201, divided into a plurality of areas (e.g., OSPF/IS-IS areas). After division, the AS200may comprise a plurality of areas210,230,250,270, and290. Although five areas210,230,250,270, and290are depicted, those of ordinary skill in the art will understand that the AS200may comprise any number of areas. The area210may be a backbone area, while the other areas230,250,270, and290may be non-backbone areas. The backbone area (sometimes referred as area0) may serve as a center or backbone of the AS200, and may be coupled to all other non-backbone areas (sometimes referred as areas1,2, . . . n, where n is an integer). Note thatFIG. 2Bonly provides an example of dividing an area to a plurality of areas, thus it does not indicate that the number of nodes in an area has to surpass a certain threshold before the area can be divided.

The area210may comprise a plurality of area border nodes212,214,216,218,220, and222, each of which may, for example, be an area border router (ABR). The area210may further comprise one or more internal nodes224,226,227, and228. Each area border node (e.g., node212) is connected to nodes in at least two areas (e.g., node240in area230and node224in area210), while each internal node (e.g., node224) is connected only to nodes inside an area (e.g., nodes224and222inside area210). The area border nodes212and214may also serve as area border nodes of the area230, which shares the nodes212and214with the area210. The area230may further comprise a plurality of internal nodes232,234,236, and238, which may be configured similar to the internal nodes224-228in the area210. The other areas250-290may each comprise a plurality of border nodes as well as a plurality of internal routers, and the configuration of the areas250-290is similar to the area230. For example, the area250may comprise the area border node216and a plurality of internal nodes252,254,256,258, and260.

LSAs comprising local link state information relevant to the area210may be distributed (e.g., flooded) to all the nodes212-228within the area210, but not to internal nodes located in other areas, such as the nodes232-242in the area230. Accordingly, the area border nodes212-222may collect and summarize the local link state information in area210into a summary LSA, and subsequently forward the summary LSA to relevant external nodes. For example, the area border nodes212and214may forward the summary LSA to the internal nodes232-242in the area230. The other border nodes, such as node216, may flood the summarized LSAs throughout their relevant area(s), such as the area250.

As shown inFIG. 2B, dividing the area201into the areas210,230,250,270, and290may decrease link state distributions in the AS200, thereby saving network resources (e.g., bandwidth) in comparison to the single area201inFIG. 2A. However, a link state distribution in the area210nevertheless triggers at least some link state distributions throughout the AS200, which may cause other nodes (e.g., nodes232-242) to re-calculate their OSPF or IS-IS routes, update their RIB and FIB tables, or take other actions that consume network resources (e.g., bandwidth and processor resources). Hence, while the prior art technique of dividing one OSPF/IS-IS area into a plurality of OSPF/IS-IS areas may partially address scalability/convergence issues, it fails to fully localize the distribution of local link state information within the OSPF/IS-IS area.

Further, as the number of nodes in an AS, such as the AS200which already comprises a plurality of areas, continues to grow, the AS may need to be divided into a plurality of autonomous systems (ASs).FIG. 3Aillustrates an AS300comprising a plurality of areas310,330, and350. The backbone area310may be configured similar to the backbone area210inFIG. 2, while the non-backbone areas (e.g., the area330) may be configured to similar to the non-backbone areas (e.g., the area230) inFIG. 2.

More nodes may be added into the AS300and form additional areas370and390, as shown inFIG. 3B. After addition of the areas370and390, the AS300becomes an even larger AS360. If the size of the AS360continuously increases, issues such as slow convergence may eventually become too severe. In this case, the AS360may need to be separated into a plurality of ASs. For example, each of the additional areas370and390may be configured into a separate AS. Since nodes located in different ASs may not share routing information, an overall number LSAs may decrease. However, to incorporate multiple ASs into a network which originally comprises one AS, the network architecture may need to be changed significantly, and service interruption may occur during transition.

Disclosed herein are systems and methods for creating one or more topology transparent zones (TTZs) in an AS to better address issues such as scalability and slow convergence, while maintaining simplicity of implementation. Specifically, a TTZ disclosed herein may be configured in an area of the AS. The TTZ may comprise a plurality of TTZ nodes including at least one edge node and at least one internal node. The disclosed TTZ may further comprise a number of internal links between internal and/or edge nodes. The edge nodes may be connected to a number of nodes outside the TTZ, which are herein referred as external nodes, via a number of external links. The links discussed herein may be any type of electrical or optical link for transporting data. Information regarding the external nodes and the external links are distributed or flooded to each TTZ node. In an embodiment, information regarding the internal nodes and the internal links may only be distributed within the TTZ via LSAs. Consequently, link state distributions throughout the AS may be reduced. In practice, implementation of one or more TTZs may be more effective in reducing link state distributions than networks implementing OSPF/IS-IS areas, while being less complex than networks implementing PCE Communication Protocol (PCEP) for computing a path for Multi-Protocol Label Switching Traffic Engineering LSP (MPLS TE LSP) crossing multiple areas or ASs. Further, nodes within the TTZ have a topological understanding of the AS as a whole. Consequently, LSPs can be computed without relying on intermediaries (e.g., PCEs). As such, the TTZ techniques described herein may allow for improved network performance, including increased scalability, faster re-convergence, better performance, and reduced processing consumption, while still allowing paths for LSPs to be computed simply.

FIGS. 4A and 4Billustrate an embodiment of an AS400comprising an area401in which embodiments of a TTZ may be implemented. The area401may comprise a plurality of nodes411-431and a topology transparent zone (TTZ)460. The nodes411-431may be configured similar to the nodes110-158inFIG. 1, and may share link state information with one another (as well as with the TTZ460) via an appropriate IGP (e.g., OSPF, IS-IS, etc.).

The TTZ460may comprise a plurality of TTZ nodes including a number of TTZ edge nodes461,463,465and467, and a number of TTZ internal nodes470,472,474,476,478, and480. As used herein, both TTZ edge nodes and TTZ internal nodes may be referred to as TTZ nodes. Each of the TTZ edge nodes461,463,465and467may be connected to at least one node outside of the TTZ460. For instance, the TTZ edge node461may be connected to the node415. The TTZ internal nodes from470to480may not be directly connected to any node outside of the TTZ460. For instance, the TTZ internal node472is directly connected to TTZ nodes461,465,476, and480, but not to any node outside the TTZ460.

Link state information relevant only to the inner-topology of the TTZ460(e.g., concerning internal links or adjacencies between pairs of TTZ nodes) may be flooded only within the TTZ460(i.e., not distributed to nodes outside the TTZ460). Information regarding the inner-topology may be stored in topology graphs. Hence, the nodes411-431may not receive LSAs describing the TTZ's460inner-topology, and as a result may not be able to see or perceive the TTZ's460inner-topology. Instead, as shown inFIG. 4B, the TTZ460may be transparent or hidden to the nodes411-431, which view the edge nodes461,463,465and467as normal nodes that are similar to the nodes411-431. As used herein, a topology graph/table may correspond to any table (e.g., LSDB, RIB, or FIB) used to describe the topology of a corresponding network, AS, area, or TTZ.

The TTZ460may be assigned a TTZ identifier (ID), which may be similar to a router ID. The TTZ460may be formed after every link inside the TTZ460is configured with the same TTZ ID (e.g., the nodes on both sides of each internal link associate the link with the TTZ ID). For instance, as shown inFIG. 4A, there may be a link between edge nodes461and465, a link between edge node461and internal node472, a link between internal nodes472and476, etc. Once the links have been configured with the TTZ ID corresponding to the TTZ460, then the TTZ's460inner-topology may be defined by the TTZ nodes461-480, as well the links extending between them.

As shown inFIG. 4B, from the perspective of the external nodes411-431, the TTZ460may be “seen” (e.g., viewed, perceived, or otherwise recognized) as a plurality of normal routers, which includes the edge nodes461,463,465, and467. In an embodiment, each of the edge nodes461,463,465, and467may be seen as being directly connected to each of the remaining edge nodes. That is, from the perspective of the external nodes411-431, the edge nodes461-467may be seen as fully connected. Further, each of the edge nodes461-467may be directly connected to at least one of the external nodes411-431. For instance, there may be a link between the edge node461and the external node415.

In an embodiment, each of the edge nodes461,463,465, and467may be seen as being directly connected to a pseudo node. That is, from the perspective of the external nodes411-431, the edge nodes461-467may be seen as all connected to the pseudo node. In addition, each of the edge nodes461-467may be directly connected to at least one of the external nodes411-431.

From the perspective of an edge node or router, such as the edge node461, the edge router may be regarded as connected to each of a plurality of neighboring routers via a link, wherein the plurality of routers comprises a first neighboring router (i.e., an external router) and a second neighboring router (i.e., an internal router). The edge router may comprise a first port configured to connect to the first neighboring router via a first link, and a second port configured to connect to the second neighboring router via a second link. The edge router may further comprise a topology graph/table configured to store information regarding the first and second neighboring routers, and the first and second links. In an embodiment, a topology graph/table stored in the first neighboring router does not contain any information regarding the second neighboring router or the second link, which is an internal link. On the other hand, a topology graph/table stored in the second neighboring router may contain information regarding the first neighboring router and the first link, which is an external link.

Further, the edge router may be configured to generate a first LSA to describe the first link and the second link, and send the first LSA to the second neighboring router. The edge router may be further configured to generate a second LSA to describe the first link and one or more additional links between the edge router and other edge routers of the TTZ460. Some or all of the additional links may be virtual links, each of which indicates an indirect connection between two edge routers, such as the edge node461and the edge node467(not directly connected). In one embodiment, a cost of a link between two edge routers may be the cost of the shortest path between the two edge routers. The edge router may be configured to send the second LSA to the first neighboring router. In another embodiment, a forwarding adjacency may be established between every two edge routers (i.e., a pair of edge routers), and a cost of a link between the two edge nodes may be set to a predetermined or fixed value, such as one.

Incorporating a TTZ into an area may help improve availability of the area. Suppose, for example, an internal link between two internal nodes472and480become broken or faulty. In this case, since external nodes (i.e., outside the TTZ460) may not have any information regarding the internal nodes472and480, the external nodes may not need to update or recalculate their routing tables (e.g., RIB and/or FIB) due to the broken link between the internal nodes472and480. Instead, only nodes within the TTZ460may recalculate their routing tables. As a result, the scale of routing table recalculation may become smaller. Although a broken link is described as an example, it should be noted that a broken internal node (e.g., the node472) may also only lead to updating of routing tables within the TTZ460.

One application of the TTZ techniques described herein may be to configure a point-of-presence (POP) (e.g., a floor or a room of routers) as a TTZ, in which case the entire POP may behave as a plurality of edge routers (i.e., the internal routers/links in the POP are hidden from external nodes). As is the case with other implementations, the TTZ approach described herein may allow for greater scalability (e.g., backbone/non-backbone areas and TTZ as opposed to just backbone/non-backbone areas), simpler computation/establishment of LSPs, faster routing re-convergence (e.g., after a fault or a broken link or node), improved performance, and higher availability in POP applications.

FIG. 5illustrates an embodiment of an AS500comprising a single area501, in which a plurality of TTZs510may be established. Each of the TTZs510may be configured similarly to the TTZ460inFIG. 4. Although four TTZs510are shown in the area501as an illustrative example, any other number of TTZs may be established. Each TTZ510in the area501may have any appropriate number of edge routers and/or internal routers, and its inner-topology may be configured flexibly.

FIG. 6illustrates an embodiment of an AS600comprising a plurality of areas601,620,630,640, and650. The area601may be configured as a backbone area being coupled with all other non-backbone areas620,630,640, and650. In at least one of the plurality of areas601,620,630,640, and650, one or more TTZs may be established. For example, as shown inFIG. 6, the area601may contain four TTZs612, the area620may not contain any TTZ, the area630may contain three TTZs632, the area640may contain four TTZs642, and the area650may contain two TTZs652. Each of the shown TTZs may be configured similarly to the TTZ460inFIG. 4. For example, each TTZ in the AS600may have any appropriate number of edge routers and/or internal routers, and its inner-topology may be configured flexibly.

In an area comprising one or more disclosed TTZs, conventional functionalities such as end-to-end traffic engineering (TE) label switched path (LSP) may be setup without any added complexity.FIGS. 7A and 7Billustrate an exemplary scheme700of setting up a LSP in the area401(previously described inFIG. 4).FIG. 7Arepresents the architecture of the TTZ460as seen by external node411-431, whereasFIG. 7Brepresents the architecture of the TTZ460as seen by the TTZ node460-480. In the exemplary scheme700, the LSP is computed from the node411to the node431(note that other LSPs in the area401may be similarly set up). Since the nodes411and431are located outside the TTZ460, they may not be aware of the presence of the TTZ460. Instead, the nodes411and431perceive the edge nodes461,463,465, and467as normal routers that are no different from themselves. As shown inFIG. 7A, in connecting the nodes411and431, the LSP may first route from node411to node417, then to node465, then to node467, then to node427, and then to node431. Since the edge nodes465and467may not be directly connected via an internal link (as seen by the node411) within the TTZ460, when a signaling protocol, such as a resource reservation protocol—traffic engineering (RSVP-TE) path message arrives at the node465from the node411through417, the node465may compute or determine a path segment for the LSP to the node467, e.g., via the internal node474. Thus, the LSP may be set up in a normal way as if the TTZ460is not present.

As mentioned previously, in a conventional network, as the number of nodes in an area continuous to grow (e.g., as illustrated inFIG. 2), the area may need to be divided into multiple areas, which may lead to structural change of the network and interruption of service. The introduction of one or more disclosed TTZs may help prevent division of one area into multiple areas.FIGS. 8A and 8Billustrate an embodiment of an AS800comprising an area801, which includes a relatively large number of nodes. As shown inFIG. 8A, part of the nodes in the area801are configured into a plurality of TTZs including a TTZ860, while other nodes remain as external nodes. The TTZ860may be configured similar to the TTZ460as described above. For example, the TTZ860may comprise a plurality of TTZ nodes including a number of TTZ edge nodes861,863,865and867, and a number of TTZ internal nodes870,872,874,876,878,880,882,884, and886. Internal links may be formed to connect some or all of the nodes in the TTZ860. AlthoughFIG. 8Ashows each TTZ with a similar inner-topology, it should be understood that each TTZ may have any inner-topology, e.g., any number of nodes and any internal link structures.

In practice, each node in the area801may build or compute a shortest path first (SPF) tree using topology it sees or perceives. From the perspective of an external node (e.g., the node817), each of the plurality of TTZs (e.g., the TTZ860) may simply behave as a collection of normal nodes (e.g., the nodes861-867), as shown inFIG. 8B. Since internal nodes and internal links are eliminated from the topology graphs/tables stored in each external nodes, these internal nodes and internal links may be virtually non-existent to the external nodes. In addition, an internal or edge node located in one TTZ may not be aware of an internal node located in a different TTZ. As a result, the number of nodes/links that need to be stored in each node in the area801may be reduced. Effectively, from routing point of view, the number of nodes in the801may be reduced. Thus, despite possibly having a large number of nodes, the area801may remain as a single area instead of being divided into smaller areas (as shown inFIG. 2). Since no inter-area communication is needed, architectural change in the AS800may be reduced (e.g., no need to separately define backbone area and non-backbone areas), which leads to faster convergence and a more stable network. Further, functionalities such as end-to-end TE LSP across multiple TTZs may still be set up readily.

Similarly, the incorporation of one or more TTZs may also help avoid separation of one AS into multiple ASs.FIG. 9illustrates an AS900comprising a plurality of areas910,930, and950, as well as a plurality of TTZs970and990. Compared with a conventional AS, such as the AS300described inFIG. 3B, the AS900may comprise an equally large or larger number of nodes without needing to be separated into multiple ASs. Instead, nodes added into the AS900may simply be configured into TTZs. As described previously, only edge nodes are visible to external nodes, thus the number of added nodes into the AS may be increased. The capability to maintain a single AS900may lead to various benefits. For example, major network architectural change and service interruption, which may occur during the AS splitting process, is avoided. Further, it may be relatively easier to operate and manage a network with a single AS than a network with multiple ASs. It may be relatively easier for applications/software to be aware of drive and/or control schemes within a single AS. Moreover, services such as inter-cloud networking may be made easier.

FIG. 10illustrates an embodiment of a node or router LSA1000comprising a LSA header field1020, a Flags field1030, a Number of Links field1040, and a plurality of Router Link fields1051. The LSA header field1020may include a link state (LS) Age field1001, an Options field1003, a LS-Type field1005, a Link State ID field1007, an Advertising Router field1009, a Link state Sequence Number field1011, a Link State Checksum field1013, and a Length field1015. In an embodiment, the LS Type field1005may be set to a predetermined value (e.g., one) to indicate that the LSA1000is a router LSA.

The Flags1030may indicate the characteristics of a router that originates the LSA1000, and may comprise a virtual link (V) bit1031, an External (E) bit1032, and a Border (B) bit1033. The V bit1031may be set to a predetermined value (e.g., one) to indicate that the source router is an endpoint of one or more fully adjacent virtual links. The E bit1032may be set to a predetermined value (e.g., one) to indicate that the source router is an AS boundary router. The B bit1033may be set to a predetermined value (e.g., one) to indicate that the source router is an ABR. The Number of Links field1040may be a 16-bit number and may indicate the number of router links that are described in the Router Links fields1051. The Router Links fields1051may comprise a Router Link field for each of the router links in the source router's area (e.g., the TTZ). Each Router Link field1051may describe an individual router link in the TTZ.

FIG. 11illustrates an embodiment of a link type1100, which may be incorporated into a Router Link field1051. The link type1100comprises a bit flag1111(denoted as an I bit flag) and a Type-1 field1115. The link type1100may be an 8-bit octet, with the I bit flag1111occupying one bit and the Type-1 field1115occupying 7 bits. The I bit flag1111may indicate whether the link is an internal link (i.e., a link inside a TTZ) or an external link (i.e., a link outside the TTZ), and the Type-1 field1115may be set to predetermined values, such as one, two, three, or four, to indicate that the kind of link being described is a point-to-point (P2P) connection to another router, a connection to a transit network, a connection to a stub network, or a virtual link (respectively).

In an embodiment, the I bit flag1111may be set to about one to indicate that the link is an internal link in a TTZ, or to about zero to indicate that the link is an external link. Consequently (in such an embodiment), the link type1100may have the same value as a conventional link type, e.g., when the link is an external link (i.e., a link outside the TTZ) and the I bit flag field1111is set to zero. Additionally, the link type1100may have a value that is one bit different from the conventional link type, e.g., when the link is an internal link (i.e., a link inside the TTZ) and the value of the I bit flag field1111is set to one.

In an alternative embodiment, the I bit flag1111may be set to about zero to indicate that the link is an internal link in a TTZ, or to about one to indicate that the link is an external link. Consequently (in such an embodiment), the link type1100may have the same value as a conventional link type when the link is an internal link, or a value that is one bit different from the conventional link type when the link is an external link. As a further alternative, a new field for a TTZ ID may be added into a router link to indicate which TTZ the link belongs to. The new field may be set to about zero to indicate that the corresponding link is a link connecting to a node outside of the TTZ, or to a non-zero value (e.g., a TTZ ID corresponding to a TTZ) to indicate that the link belongs to which TTZ.

FIGS. 12A-12Cillustrate examples of router LSAs (with the format of the router LSA1000) generated by different nodes or routers. In an embodiment, a router LSA1210, as shown inFIG. 12A, may be generated by an edge node (the edge node461inFIG. 4Ain this example for illustration) and distributed within a TTZ itself (e.g., the TTZ460). In the router LSA1210, the Link State ID and the Advertising Router fields may be used to identify the edge node461, wherein the router LSA is generated. Since the edge node461is connected to the external node415via an external link, to the edge node465via an internal link, to the internal node470via another internal link, and to the internal node472via yet another internal link, four Router Link fields may be used to indicate all links associated with the edge node461. Further, in the Router Link fields, the I bit flag may be set to one if the link is internal, or otherwise set to zero if the link is external. After the router LSA1210is generated, it may be distributed or flooded to every other node in the TTZ460but not to any node outside of the TTZ460.

In an embodiment, another router LSA1230, as shown inFIG. 12B, may be generated by the edge node461, which may then be distributed to external routers. In the router LSA1230, the Link State ID and the Advertising Router fields may be used to identify the edge node461. From the perspective of an external node, the edge node461may be connected to nodes415,463,465, and467via normal links (as shown inFIG. 4B). Note that some links between the edge nodes (e.g., between nodes461and467) may be virtual links. Accordingly, four Router Link fields may be used to indicate all links associated with the edge node461. Further, in all the Router Link fields, the I bit flag may be set to zero. After the router LSA1230is generated, it may be flooded to all external nodes in the area401.

In an embodiment, yet another router LSA1250, as shown inFIG. 12C, may be generated by an internal node (the internal node472in this example for illustration) and flooded to the TTZ460itself. In the router LSA1250, the Link State ID and the Advertising Router fields may be used to identify the internal node472. Since the internal node472is connected to the internal nodes476and480, and the edge nodes461and465via four internal links, four Router Link fields may be used to indicate all internal links associated with the internal node472. Further, in the Router Link fields, the I bit flag may be set to one. After the router LSA1250is generated, it may be distributed or flooded to every other node in the TTZ460but not to any node outside of the TTZ460.

FIG. 13illustrates an embodiment of a method1300for configuring a disclosed TTZ in an AS. The method1300may begin in step1310, where a TTZ ID may be assigned to each node in the TTZ. In some embodiments, the TTZ edge nodes and/or internal nodes may perform an intermediate step of exchanging hello packets with TTZ IDs to establish their own adjacencies after the step1310. The method1300may then proceed to step1320, where an internal TTZ link state distribution may be performed. Specifically, the internal TTZ link state distribution may comprise constructing and flooding LSAs describing each TTZ node's adjacencies to all of the TTZ nodes and to all of the neighboring external nodes. Appropriate I bit flags (e.g., set to one for internal links, and zero for external links) may be assigned to each LSA. The TTZ edge nodes may include descriptions of their external links (i.e., links between the TTZ edge node and an external node) in the LSAs they construct, thereby allowing the other TTZ edge nodes (as well as the TTZ internal nodes) to develop a topological understanding of the external nodes/links. As a result of the internal TTZ link state distribution, every TTZ node may derive a topological understanding of the TTZ's inner-topology (i.e., the positional relationship of the TTZ nodes with respect to one another including the internal links) as well as an understanding of the TTZ's adjacencies (i.e., the positional relationship of the TTZ edge nodes to their neighboring external nodes including identification of the external links).

Next, the method1300may proceed to step1330, where each TTZ edge node may independently construct a router LSA describing each of the external links, and distribute the router LSA to the neighboring external nodes to which it is interconnected. The router LSA may specify a router ID of the originating router. Next, the method1300may proceed to step1340, where the TTZ edge nodes may flood any LSAs received from the neighboring external nodes throughout the TTZ, thereby allowing the TTZ nodes to develop a topological understanding of the AS topology. In some embodiments, the TTZ edge nodes may also distribute LSA received from neighboring external nodes to other neighboring external nodes as may be consistent with the IGP implemented in the AS. AlthoughFIG. 13describes the TTZ edge nodes as receiving LSAs describing the AS topology as occurring after the steps1310-1330, those of ordinary skill in the art will recognize that such LSAs may be received intermittently during the performance of the method1300.

Next, the method1300may proceed to step1350, where LSDBs describing the TTZ's inner-topology and the AS topology may be built in each of the TTZ nodes, thereby allowing the TTZ nodes to develop a topological understanding of the both TTZ's inner-topology and the AS topology. Finally, the method may proceed to step1360, where each of the TTZ nodes computes the shortest path to each of the destinations, which include destinations in the TTZ and destinations outside of the TTZ.

FIG. 14illustrates an embodiment of a node or a router1400, as described above within a network or system. The node1400may comprise a plurality of ingress ports1410and/or receiver units (Rx)1412for receiving data from other nodes, a processor1420to process data and determine which node to send the data to, a memory1422, and a plurality of egress ports1430and/or transmitter units (Tx)1432for transmitting data to the other nodes. Although illustrated as a single processor, the processor1420is not so limited and may comprise multiple processors. The processor1420may be implemented as one or more central processing unit (CPU) chips, cores (e.g., a multi-core processor), field-programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and/or digital signal processors (DSPs), and/or may be part of one or more ASICs. The processor1420may be configured to implement any of the schemes described herein, such as the method1300. The processor1420may be implemented using hardware, software, or both. The memory1422may be configured to store routing tables, forwarding tables, or other tables or information disclosed herein. Although illustrated as a single memory, memory1422may be implemented as a combination of read only memory (ROM), random access memory (RAM), or secondary storage (e.g., one or more disk drives or tape drives used for non-volatile storage of data).

The schemes described above may be implemented on any general-purpose network component, such as a computer or network component with sufficient processing power, memory resources, and network throughput capability to handle the necessary workload placed upon it.FIG. 15illustrates a schematic diagram of a general-purpose node or router1500suitable for implementing one or more embodiments of the methods disclosed herein, such as the method1300. The general-purpose network component or computer system1500includes a processor1502(which may be referred to as a central processor unit or CPU) that is in communication with memory devices including secondary storage1504, ROM1506, RAM1508, input/output (I/O) devices1510, and network connectivity devices1512. Although illustrated as a single processor, the processor1502is not so limited and may comprise multiple processors. The processor1502may be implemented as one or more CPU chips, cores (e.g., a multi-core processor), FPGAs, ASICs, and/or DSPs, and/or may be part of one or more ASICs. The processor1502may be configured to implement any of the schemes described herein, including the method1300. The processor1502may be implemented using hardware, software, or both.

The secondary storage1504is typically comprised of one or more disk drives or tape drives and is used for non-volatile storage of data and as an over-flow data storage device if the RAM1508is not large enough to hold all working data. The secondary storage1504may be used to store programs that are loaded into the RAM1508when such programs are selected for execution. The ROM1506is used to store instructions and perhaps data that are read during program execution. The ROM1506is a non-volatile memory device that typically has a small memory capacity relative to the larger memory capacity of the secondary storage1504. The RAM1508is used to store volatile data and perhaps to store instructions. Access to both the ROM1506and the RAM1508is typically faster than to the secondary storage1504. At least one of the secondary storage1504or RAM1508may be configured to store routing tables, forwarding tables, or other tables or information disclosed herein.