Method and apparatus for an attribute oriented routing update

A computer implemented method and apparatus for an attribute-oriented routing update is described. The method comprises selecting an updated set of attributes in a routing table before selecting a set of updated destinations associated with the selected set of attributes, wherein the attributes are stored in an attribute table as a portion of the routing table and the attributes do not include the conventional network prefixes. An update message that includes the set of updated destinations for the set of attributes is then generated. The method is also extended to extraction of unreachable destinations by using a dummy attribute in the routing table, wherein the dummy attribute is selected first, followed by extracting the unreachable destinations.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to the field of communication. More specifically, the invention relates to communication networks.

2. Background of the Invention

A router hosts a routing protocol(s) that can include the Routing Information Protocol (RIP), Open Short Path First (OSPF), Intermediate System to Intermediate System (IS—IS), the Border Gateway Protocol (BGP), etc. The router exchanges messages with neighboring routers in accordance with one or more of the hosted routing protocols.

FIG. 1(PRIOR ART) is a diagram illustrating a BGP update message. The BGP update message100includes an attributes section101and a network layer reachability information (NLRI) section103. The attributes section101identifies various attributes defined by “A Border Gateway Protocol 4”, Request for Comments 1771 by Y. Rekhter and T. Li (March 1995) (RFC 1771) that describe a path. These attributes include origin, next hop, autonomous system (AS) path, local preference, etc. The NLRI section103identifies destinations that can be reached via the path described by the attributes in the attributes section101.

When a router that hosts BGP receives a BGP update message from one of its neighbors, the router updates its BGP routing table in accordance with the update message received. The BGP routing table of a router can include a large number of paths.

FIG. 2(PRIOR ART) is a diagram illustrating a BGP table. The BGP table200includes a destination data structure202and an attribute table201. Each element of the destination data structure201identifies a network prefix (e.g., an IP prefix). The element203A is the root of the destination data structure202. The element203C references a linked list of path data structures205A and205B. One of the path data structures205A and205B corresponds to a best path to the destination identified by the element203C. The path data structure205A references the first entry in the attribute table201. The path data structure205B references the second entry in the attribute table201. If the path data structure205B corresponds with the best path to the network prefix identified by the element203C, then the attributes in the second entry of the attribute table described that best path. An element203D references a path data structure205C. The path data structure205C also references the second entry in the attribute table201. An element203B references a path data structure205C, which references the last entry in the attribute table201.

When a BGP update message is built in accordance with Appendix 6.1 of the RFC 1771, a BGP process packs network prefixes into the update message as illustrated inFIG. 1. The RFC 1771 describes address prefix oriented routing update. In other words, the BGP process builds update messages as it processes each network prefix. As each network prefix in the destination data structure202is processed, the BGP process allocates a BGP update message for the corresponding attributes. Each time the BGP process encounters a network prefix that corresponds to attributes of an allocated message, the BGP process appends the network prefix to the message. Each time the BGP process encounters a network prefix that corresponds to attributes that do not have an allocated message, the BGP process allocates a new update message. After the entire BGP table has been scanned, the BGP process transmits the messages and releases resources utilized for the messages.

Assuming changes are detected in the destination data structure202, a router that hosts the BGP table200will begin to build BGP update messages with network prefixes identified by marked elements. Assuming that the elements203B–203D have been marked as changed, a BGP process allocates an update message for the last entry in the attribute table201when the BGP process encounters the element203B of the destination data structure202. The network prefix identified by the element203B is appended to the allocated message. The BGP process continues through the destination data structure202and allocates another update message for the first entry in the attribute table201when the BGP process encounters the element203C. The BGP process allocates a third message for the second entry in the attribute table201when it encounters the path data structure205B, which references the second entry. The BGP process appends the network prefix identified in the element203C in the second and third allocated messages. The BGP process appends the network prefix identified in the element203D to the third allocated message. Once the BGP process completes walking the destination data structure, the BGP process transmits all messages allocated for the routing table200and releases resources (e.g. memory) utilized for the messages.

Several years ago, this method of building BGP update messages was acceptable since a routing table identified a relatively small number of paths (e.g., a few thousand paths). This method is inefficient when applied to a routing table that identifies a very large number of paths (e.g., hundreds of thousands of paths). Allocating resources for a large number of update messages consumes vast amounts of a router's resources, and can possibly deplete its resources.

An alternative approach transmits allocated messages upon reaching a predetermined limit, such as a limit of resources. This alternative approach reduces packing efficiency of update messages. Since allocated messages are transmitted before all network prefixes are processed, the same set of attributes may be identified in multiple update messages. The transmitting network device's resources are still not utilized efficiently. Processor time spent on allocating and transmitting these update messages will increase in relation to the reduction in packing efficiency. Furthermore, resources of network device's that receive these update messages are also utilized inefficiently because of reduced packing efficiency.

BRIEF SUMMARY OF THE DRAWINGS

A method and apparatus for attribute-oriented routing update is described. According to one aspect of the invention, a computer implemented method provides for selecting an updated set of attributes in a routing table before selecting a set of updated destinations associated with the selected set of attributes. In one embodiment, an update message that includes the set of updated destinations is generated for the set of attributes.

These and other aspects of the present invention will be better described with reference to the Detailed Description and the accompanying Figures.

DETAILED DESCRIPTION OF THE DRAWINGS

In the following description, numerous specific details are set forth to provide a thorough understanding of the invention. However, it is understood that the invention may be practiced without these specific details. In other instances, well-known circuits, structures, standards, and techniques have not been shown in detail in order not to obscure the invention.

FIGS. 3A–3Care diagrams illustrating elements of a routing table according to one embodiment of the invention.FIG. 3Ais a diagram illustrating an element of a destination data structure of a routing table according to one embodiment of the invention. InFIG. 3A, an element301of a destination data structure (“destination element”) includes four fields: a destination field303, a chain pointer field307, a modify field308, and a path pointer field309. The destination field303indicates a destination, such as a network prefix (e.g., an IP address prefix). The modify field308is a flag that indicates whether a path of the corresponding destination element301has been modified. The chain pointer field307references another destination element in an attribute-oriented chain that includes the destination element301. An attribute-oriented chain includes a set of destination elements that have a common set of attributes. The path pointer field309references a path data structure.

FIG. 3Bis a diagram illustrating a path data structure of a routing table according to one embodiment of the invention. InFIG. 3B, a path data structure311includes 3 fields: a neighbor field313, a best flag field315, and an attribute pointer field317. The neighbor field313indicates a neighboring network device that advertised a path to a destination indicated in a destination element that references the path data structure311. The best flag field313indicates whether the path represented by the path data structure311is the best path to the destination of the destination element that references the path data structure311. The attribute pointer field317references an element of an attribute table.

FIG. 3Cis a diagram illustrating an element of an attribute table of a routing table according to one embodiment of the invention. InFIG. 3C, an element319of an attribute table (“attribute element”) is comprised of multiple fields that describe a path. The attribute element319illustrated inFIG. 3Cincludes a next hop field321, an origin field322, an AS path field323, and a chain pointer field325. The next hop field321indicates a network device that is the next hop in the path described by the attribute element319. The origin field322indicates the origin of the path information. The AS path field323indicates an AS path attribute. The chain pointer field325references a destination element in the attribute-oriented chain originating from the attribute element319. The attribute element319can optionally include a chain tail field327. The chain tail field327references the tail end of the attribute-oriented chain, thus allowing destination elements to be inserted into the attribute-oriented chain at the head or the tail. Alternative embodiments may implement different data elements in relation to the data structures implemented as described later herein.

Including references to destinations in the attribute table enables attribute-oriented routing update. A routing process may generate updates by scanning the attribute table.

FIG. 4is a diagram of a routing table according to one embodiment of the invention.FIG. 5is a diagram illustrating an exemplary network according to one embodiment of the invention.FIG. 5will be described with reference to the exemplary routing table ofFIG. 4. InFIG. 5, an Internet Service Provider (ISP)501includes a network device503. The network device503acts as a border router for the ISP501. The network device503is coupled with network devices507and509. The network device507is coupled with the destination511B via a network cloud513B. The network device509is coupled with destinations511B and511C via a network cloud513C. The network device509is also coupled with a destination51ID via the network cloud513C, but has lost communication with the destination511D. The network devices507and509transmit update messages to the network device503about paths to the destinations511B,511C, and511D.

FIG. 4illustrates a routing table400hosted on the network device503. The routing table400is modified in accordance with messages received from the network devices507, and509. The routing table400illustrated inFIG. 4includes a destination data structure401and an attribute table405. The destination data structure401includes a root403and destination elements301E,301F, and301P. In this illustration, the destination element301F indicates the destination511B in its destination field303. The destination element301F references a path data structure311A. The path data structure311A indicates the network device509in its neighbor field313. The path data structure311A references an attribute element319A, which indicates attributes describing a path to the destination511B advertised by the network device509. The path data structure311A is linked to a path data structure311B. The path data structure311B indicates the network device507in its neighbor field313. The path data structure311B references an attribute element319B of the attribute table405in its attribute pointer field317. The attribute element319B indicates attributes describing a path to the destination511B advertised by the network device507.

As previously stated, the described embodiments enable a routing process to perform attribute-oriented routing updates. As a routing process encounters updated entries in the attribute table and/or entries in the attribute table associated with updated destinations, the routing process builds an update message with updated destinations associated with the encountered entry. After the routing process has selected all destinations associated with the encountered entry or reached a limit, the routing process can transmit the update message and release resources for the update message. Alternatively, the routing process can reuse the resources for the next encountered entry. Hence, a network device's resources are not consumed by multiple messages for multiple attribute entries. In addition, the network devices that receive these update message do not expend resources looking up the same set of attributes for multiple update messages.

In this illustration, the path data structure311A is indicated as corresponding to the best path by its best flag field315. Since the path data structure311A is indicated as corresponding to the best path, the chain pointer field325of the attribute element319A references the destination element301F. Hence, the destination element301F is in the attribute-oriented chain of the attribute element319A.

The destination element301P references a path data structure311C. The destination element301P indicates the destination511C in its destination field303. The path data structure311C indicates the network device509in its neighbor field313. The path data structure311C references an attribute element319A in its attribute pointer field317. The attribute element319A indicates a set of attributes describing a path to the destination511C advertised by the network device509. The path data structure311C is indicated as corresponding to the best path according to its best flag field315. Since the path data structure311C and the attribute element319A correspond to the best path to the destination511C, the destination element301P is also in the attribute-oriented chain of the attribute element319A. Therefore, the destination element301F, which is the head of the attribute-oriented chain of the attribute element319A, references the destination element301P in its chain pointer field307. The destination element301E indicates the destination511D in its destination field303. The network device509has indicated to the network device503that the destination511D is unreachable. Since the destination511D is unreachable, the destination element301E is inserted into a dummy attribute-oriented chain. A dummy attribute element of the attribute table405references the dummy attribute chain.

While one embodiment is described having particular exemplary data structure, alternative embodiments may use any number of other data structures. For example, in an alternative embodiment of the invention, the destination data structure may be a hash table. In such an embodiment, the indices of the hash table may be destinations. Each hash table index may reference a linked list of path data structures. The chain pointer destination element and each attribute element may identify elements in an attribute-oriented chain by their hash value. Alternatively, the chain pointer may identify elements in an attribute-oriented chain by their address. The described embodiments of the invention are intended to aid in the understanding of the invention and not meant to be limiting upon the invention.

FIG. 6Ais a flow chart for processing an update message indicating reachability according to one embodiment of the invention. At block601, a network device receives an update message indicating reachability. At block603, the network device determines if the attribute set indicated in the update message is in its attribute table. If the network device determines that the attribute set indicated in the update message is not in its attribute table, then at block605the network device creates an attribute element in the attribute table for the attribute set. Control flows from block605to block607. If the network device determines that the attribute set is in its attribute table, then at block606the network device selects the attribute element that indicates the attribute set. At block607, the network device selects a destination indicted in the update message.

At block609, the network device determines if the selected destination exists in its destination data structure. If the network device determines that the selected destination exists in its destination data structure, then control flows to block615. If the network device determines that the selected destination does not exist in its destination data structure, then at block611the network device creates a corresponding destination element that indicates the selected destination and creates corresponding path data structure. The created corresponding path data structure will indicate the network device that transmitted the update message in its neighbor field. At block613the network device links the corresponding path data structure to the attribute element that indicates the attribute set. Control flows from block613to block629.

FIG. 6Bis a flowchart for processing a created destination element according to one embodiment of the invention. At block629, the best flag field of the created path data structure indicates the path data structure as corresponding to the best path. At block631the network device inserts the created destination element into an attribute-oriented chain of the attribute element and marks the created destination element. At block633, the network device determines if all destinations in the update message have been processed. If all the destinations in the update message have been processed, then the process is done at block635. If all destinations indicated in the update message have not been processed, the control flows back to block607.

FIG. 6Cis a flowchart for processing a selected destination of an update message according to one embodiment of the invention. At block615, the network device determines if the neighbor previously advertised the selected destination. If the neighbor had not previously advertised the selected destination, then at block617the network device creates a new path data structure that indicates the neighbor in its neighbor field. Control flows from block617to block619. If the neighbor had previously advertised the selected destination, then at block619the network device links the path data structure corresponding to the neighbor to the selected attribute element. At block621, the network device calculates the best path for the selected destination.

At block623, the network device determines if the best path calculation indicates a change in best path. If the best path calculation does not indicate a change in best path, then control flows to block633. If the best path calculation indicates a change in best path, then at block625the network device removes the selected destination element from the old attribute-oriented chain and marks the selected destination element. At block626the network device determines if there is a new best path. If there is not a new best path, then control flows to block633. If there is a new best path, then at block627the network device inserts the selected destination element into a new attribute-oriented chain corresponding to the selected attribute element. Control flows from block627to block633.

Various embodiments may indicate the best path differently. Alternative embodiments may maintain elements of the path data structure so that the first element is the best path. Hence, the best path calculation at block621results in a reordering of the path data structure. Maintaining the path data structure in this manner allows the network device to select the first element of the best path data structure instead of making a determination. In another embodiment, each element of the destination data structure includes a reference for the element in the path data structure that is currently represents the best path and a separate reference for the path data structure (e.g., a pointer(s) to the first and/or last element of the path data structure, a pointer to the root of the path data structure as a tree, a reference to the location of the path data structure as a hash table. etc.).

FIGS. 7A–7Bare flow charts for processing an update message indicating unreachability according to one embodiment of the invention.FIG. 7Ais a flowchart for processing an update message indicating unreachability according to one embodiment of the invention. At block701ofFIG. 7Aa network device receives an update message indicating unreachability. At block707the network device selects a destination indicated in the update message. At block709, the network device determines if the selected destination exists in its destination data structure. If the selected destination does not exist in the network device's destination data structure, then at block710the process is done. If the selected destination exists in the network devices data structure, then at block711the network device deallocates the path data structure that indicates the neighbor of the update message. At block721the network device calculates a best path for the selected destination.

At block723, the network device determines if the best path calculation indicates a change in best path. If the best path calculation does not indicate a change in best path, then control flows to block733. If the best path calculation indicates a change in best path, then at block725the network device removes the selected destination element from the old attribute-oriented chain and marks the selected destination element. At block726, the network device determines if there is a new best path. If there is not a new best path, then control flows to block733. If a new best path has been selected, then at block727the network device inserts the selected destination element into a new attribute-oriented chain of the attribute element referenced by the path data structure corresponding to the new best path. Control flows from block727to block733.

FIG. 7Bis a continuation of the flowchart illustrated inFIG. 7Aaccording to one embodiment of the invention. At block733the network device determines if all destinations in the update message indicating unreachability have been processed. If all destinations in the update message have been processed, then the process is done at block735. If all destinations in the update message have not been processed, then control flows to block707.

Various embodiments described with respect toFIGS. 6A–6Cmay also be applied toFIGS. 7A–7B.

FIG. 8is a flow chart for generating an update message indicating reachability according to one embodiment of the invention. At block801, the network device selects an attribute element from the attribute table. Various embodiments of the invention may select attribute elements differently. In one embodiment of the invention, the network device walks through the attribute-oriented chain of each attribute element in the attribute table. In another embodiment of the invention, the network device selects marked attribute elements. At block803, the network device creates an update message with attributes of the selected attribute element. At block805, the network device follows the chain pointer of the selected attribute element through its attribute-oriented chain. A block807, the network device adds each encountered destination of the attributed oriented chain that is marked into the message. At block809, the network device transmits the update message after reaching the end of the attribute-oriented chain.

FIG. 9is a flow chart for generating an update message indicating unreachability according to one embodiment of the invention. At block901, the network device identifies an allocated update message as indicating unreachability. At block903, the network device selects the dummy attribute element. At block905, the network device follows the chain pointer of the dummy attribute element through the dummy attribute element's attribute-oriented chain. At block907, the network device adds each encountered destination of the dummy attribute-oriented chain that is marked into the update message. At block909, the network device transmits the update message indicating unreachability after reaching the end of the dummy attribute-oriented chain.

While the flow diagrams in the Figures show a particular order of operations performed by certain embodiments of the invention, it should be understood that such order is exemplary (e.g., alternative embodiments may perform certain of the operations in a different order, combine certain of the operations, perform certain of the operations in parallel, etc.). For example, the described embodiments enable a multiprocessor system to generate update messages for multiple entries of an attribute table while prefix-oriented update does not lend itself to such an implementation.

FIG. 10is a block diagram illustrating the exemplary network device503according to one embodiment of the invention. InFIG. 10, a control card hosts the routing table400. In various embodiments of the invention, the routing table400can be hosted on a co-processor, an ASIC, etc. The control card1003is coupled with a transmission medium cloud1005(e.g., a system bus, point to point connections between line cards, a combination of the above, etc.). The transmission medium cloud1005is coupled with line cards1007A–1007D. The line cards1007A–1007D are coupled to physical interfaces1009A–1009D respectively. The network device503receives updates messages and transmits update messages via the physical interfaces1009A–1009D.

The control card1003and the line cards1007A–1007D illustrated inFIG. 10includes memories, processors, and/or ASICs. Such memories include a machine-readable medium on which is stored a set of instructions (i.e., software) embodying any one, or all, of the methodologies described herein. Software can reside, completely or at least partially, within this memory and/or within the processor and/or ASICs. For the purpose of this specification, the term “machine-readable medium” shall be taken to include any mechanism that provides (i.e., stores and/or transmits) information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium includes read only memory (“ROM”), random access memory (“RAM”), magnetic disk storage media, optical storage media, flash memory devices, electrical, optical, acoustical, or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.), etc.

While the invention has been described in terms of several embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described. Various embodiments of the invention can implement the attribute table differently. One embodiment can implement the attribute table as a tree structure instead of a hash table.

The method and apparatus of the invention can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of limiting on the invention.