KR20040102029A - A method for providing topology awareness information within an ip network - Google Patents

Abstract

The present invention relates to a method, a unit and a computer program product for providing topology awareness information in an IP network comprising a central node and a plurality of routers, wherein the probe is implemented in a router in the IP network and the probe belongs to a topology aware system. Means for the unit to obtain and maintain relationships with other probes in an IP network, to collect information about other network components, such as routers and switches, and to send and receive topology information with a central node of a topology aware system. Means for obtaining the information related to the local resource on the router on which the probe is executed.

Description

A METHOD FOR PROVIDING TOPOLOGY AWARENESS INFORMATION WITHIN AN IP NETWORK}

Many communication networks are evolving with the goal of an All-IP Solution. As the variety of applications based on IP networks increases, the need for sophisticated control management systems increases. IP networks are inherently decentralized. Each network node, or router, can operate individually without central authority control. In some applications where centralized control is advantageous, network operators often want to use one centralized operations center to control their networks. In other words, applications or systems that require information on how routers interconnect and how to route traffic between them are becoming increasingly common.

Here, all systems that provide desired topology information are represented as topology recognition systems.

State of the technology

There are several approaches to gathering topology information, some of which are outlined here. The following capabilities are common to all topology recognition systems.

Pass topology information to the central node. The central node can use this information for a variety of purposes, for example, for network visualization and graphical management interfaces. General topology aware services, such as path search, may also be provided by the system.

Collect routing information, information about the router interface, and information about what is recognized as metadata about the router (eg, the original representation of the node name or other readable one).

In the following, some known methods for topology recognition are described. The strengths and weaknesses of each approach are provided simultaneously. This is to highlight the problems solved by the present invention.

Probe all routers

IP routers are commonly referred to via the Standardized Network Management Protocol (SNMP), as defined in Case J., Fedor M., Schoffstall M. Davin J., A Simple Network Management Protocol (SNMP), IETF, RFC1157. Provides access to a variety of information. This information, accessible via SNMP, is stored in Management Information Bases (MIBs). In particular, the information required for topology recognition is already available in a standardized jointly supported MIB.

The topology recognition system can connect to the MIB to find out the topology. In the description of the present invention, the term 'probing' is used when connecting to a MIB on a router (or for connecting to another system supporting SNMP for this) to obtain topology information. A known direct topology recognition method based on SNMP probing is described in US Pat. No. 5,185,860. The solution according to the US patent finds which routers are neighboring and directly connected to the first router and probes the neighboring routers starting from the first router. For each new router found to be neighboring, the probing process must be extended to another hop to reach beyond the newly discovered router. This process is applied repeatedly until no more routers are found. Other algorithms for topology recognition based on SNMP probing can of course be applied as well. The common denominator is that all routers must be routed for all information.

Topology recognition systems based on this approach may be implemented in a single node or in a distributed system having multiple probes and a central node.

strength

One obvious advantage of the SNMP-based approach is that it is independent of the routing protocol in use in the domain. Similar approaches have the following advantages.

Information is accessible within a standardized MIB.

The tools needed to build such a system are readily available and easy to use.

Weakness

There are several potential problems with the SNMP-based approach. Two fundamental problems are that the amount of signaling is very high and the SNMP protocol is known to be unreliable (this is based on Postel J., User Datagram Protocol, IETF, and UDP described in RFC768 transmissions that do not guarantee delivery). Topology-aware systems based solely on SNMP must collect large amounts of data, which can be problematic.

Another problem that can be most fatal for certain types of topology aware systems is the lack of support for dynamic transport for change. There are two major alternatives for implementing dynamic topology awareness based only on SNMP. These are as follows.

Use periodic polling to ensure that all changes are clearly detected. There is a trade-off between signaling overhead and the time it takes to find a change. Frequent polling introduces a lot of signaling overhead, but rare polling does not accurately represent a topology within a topology aware system.

Rely on SNMP traps, which are unnecessary SNMP messages initiated by routers at certain events. In this way, at least in theory, the router can inform the topology aware system about the topology change. Some of the problems with this approach are that it can be lost because of the incredible nature of SNMP, and the flexibility with which traps are configured is limited. Not all router events can be combined with SNMP traps.

Link-State Routing Protocol

There is a group of routing protocols known as link-state protocols. The most common link-state protocols are OSAN described in Oran D., OSI IS-IS Intra-domain Routing Protocol, IETF, IS-IS and Moy J. described in RFC11428, OSPF Version 2, IETF, RFC2328. The link-state protocol is based on the principle that all routers keep up-to-date database of all routers in the domain. This routing protocol is designed to maintain a database of individual routers that are synchronized at the same time.

In domains where this kind of routing protocol is deployed, topology aware systems can take advantage of the link-state principle and know about all routers in the topology from routing protocol messages. Protocol messages can be accessed by actively participating in a routing protocol (eg, by functioning as a router) or by passively peeking over the network.

In any case, topology aware systems based on the link-state principle learn about all routers and their routing information without explicit signaling. It is important to note that this also involves change. In addition to the information available in the link-state database, SNMP can be used to probe individual routers for other data.

strength

Knowing the entire topology (router and routing data) without explicitly signaling individual routers is a significant improvement compared to SNMP-based systems. Another important strength is that changes in routing are readily available through routing protocols. Not needed by routers for polling or traps.

Weakness

If other information is needed in the topology aware system beyond the range available in the link-state database, the link-state principle must be combined with other mechanisms such as SNMP probing. This means that some data may still have to be collected from individual routers.

Another potential problem with this approach is that the reliability and performance of the topology aware system depends very much on the behavior of the router near the probe. For example, if a node participating in a routing protocol on behalf of a topology aware system is directly connected to a single router and the router's routing protocol process fails, topology awareness will be lost.

Topology-aware component within every router

One approach to topology awareness is that all routers have custom components designed to provide the topology information needed for a centralized system. These parts can use SNMP locally, take advantage of routing protocol messages, use specific Application Programming Interfaces (APIs) platforms to obtain information, or use a combination of these methods. have.

strength

Local placement of topology-aware components in all routers reduces the need for a mechanism to know routers and their routing data. The inherent problems of other methods are somewhat overcome. This means that the mechanism by which the topology information is collected can be rescued much more reliably and robustly.

Weakness

This method assumes that all routers have topology aware components. This means that domains must not be heterogeneous for routers to function properly with this approach. If not all routers support topology aware components, there will be holes in topology awareness.

Another problem is transmitting information to the central node of the topology aware system. If all routers establish a connection to the central node, this node can become overloaded with just managing all connections.

Summary of Topology Aware Options

The approach described in "All Router Probing" and "Link-State Routing Protocol" is suitable for implementation in a hierarchical fashion in which probe nodes are placed in a network to collect topology awareness information and central nodes store and process the information. Do. One example of this is shown in FIG. 1. The squares denoted by R are regular routers, and the circles denoted by P are called unit probes that perform topology recognition.

The probe P is connected to the central node of the topology recognition system, and the central node 100 is arranged at the management site. In some networks, deploying additional nodes within the network is undesirable in terms of deployment costs and management. In this case, it would be more advantageous if the topology recognition function could be placed within the router itself as described in "Topology Recognition Components in All Routers". One example of this approach is shown in FIG. 2 (central node not shown).

In FIG. 2, the topology recognition unit, or probe, may be implemented on a router with a circular dot in the lower left corner. Every router in the domain runs a probe except one. Thus, as discussed in "Weaknesses" in "Topology Recognition Components in All Routers", there will be holes in the topology recognition system. Basically, if all the topologies need to be fully discovered, there should be additional functionality.

Problems in the Technical Field

Next, three problems in the art will be discussed, which are signaling overhead, robustness, and management of a large set of topology aware probes.

Signaling overhead

The signaling required for topology aware systems using probes is divided into two categories.

A. Signaling required for the network plane to collect topology information from probe to router or from probe to probe

B. Signaling involved in transmitting topology information from the probe to the central node of the topology aware system

Depending on the topology awareness solution, the signaling overhead will vary somewhat in the two categories.

A. Network Plane Signaling

Some solutions that use SNMP to gather information will require quite a bit of signaling. If one (or several) topology probes are operating within a domain, the probe must use SNMP to route many hops. The unreliable feature of SNMP implies that retransmissions on the application layer will be required. Systems that must be very fast will incur a lot of signaling overhead, but systems that do not have to be so fast will be less.

In a solution that works on most routers, but not all of the topology-aware components, the amount of overhead signaling can be very overwhelming if you want complete topology awareness. If the topology and routing information must be constantly updated as the routing changes, more signaling will be required.

All compliant routers, i.e. routers with topology-aware units (e. G. Probes), will minimize all routers directly neighboring, and if there are non-compliant routers in the duplex, more probing is needed. As soon as a noncompliant router is found, the probing of that router will be ready. The compliant router will probe all of the direct neighboring noncompliant routers.

An example signaling is shown in FIG. 3, where routers R ₁ to R ₃ implement a topology aware component but are not routers R ₀ . Router R ₁ will probe the neighboring router and find that it is a noncompliant router. To ensure that there are no more noncompliant routers, router R ₁ probes the neighboring routers of router R ₀ on interfaces a, c, d and e (b skips when R1 is connected). At interface c and d router R ₁ will know that there are compliant routers, ie routers R ₂ and R ₃ . For interfaces a and e, probing may have to continue depending on what neighboring router is. It should be taken into account that routers R ₂ and R ₃ should perform similar steps as they would know about router R ₀ and its neighboring routers. This creates a fairly large number of probing messages.

If there is one (or a few) fully SNMP-based probes, the signaling may be reduced by placing the probes in most routers, which largely avoids the multi-hop SNMP problem that is difficult to solve. Let's do it.

If most routers have probes, signaling can be reduced if new functionality is added such that the probes implementing the router share the burden.

B. Send topology information

There is a balance between the processing power required at the central node and the bandwidth used between the probe and the central node of the system. There are two approaches.

Minimize bandwidth Allows the probe to collect and transmit a graphical representation of the topology, and allows the central node of the system to perform calculations on the graph to provide topology awareness. This uses a lightweight representation of the network, but the central node of the system needs to perform custom calculations to find the shortest path each time a router is found.

Minimize processing at the central node of the system. Allows the probe to collect (or calculate) routing items and send them to a central node of the system. Representing a network as a routing item requires more transmission bandwidth and storage memory, but is more efficient in terms of the processing of the central node of the system.

In any of the models described above, there is much room for optimizing bandwidth usage by reducing signaling overhead.

Robustness

If a topology aware system is an important part of a larger system, there may be more stringent requirements for robustness. Robustness in topology recognition relates to how accurate the topology recognition system is and how quickly changes are detected and propagated. The link-state based approach mentioned in the "Link-State Routing Protocol" is very good performance characteristic and is excellent at keeping accurate and up-to-date representation. Only slight problems in the routing process of link-state based topology aware probes and adjacent probes will have a significant impact on the topology representation. This problem requires a solution that allows some topology aware probes to collaborate to provide the necessary information.

Managing a large set of topology aware probes

The routing domain can grow with a fairly large number of routers. It is common for a routing domain to have hundreds of routers. The future goal for router implementation may be to use more domains. If topology awareness runs on all routers in a large domain, managing connections to all probes becomes complicated. Systems that provide layers and sets would be useful to solve this problem.

Accordingly, an object of the present invention is to provide a method, topology, which helps to efficiently obtain topology information in an IP network, that is, reduce signaling overhead, increase robustness, and manage a large set of topology aware probes. It is to provide a recognition unit and a computer program product.

The present invention relates to an Internet Protocol (IP) network.

More specifically, the present invention relates to a method, a topology recognition apparatus and a computer program product for providing a topology recognition system in an IP network.

1 shows a standalone topology aware probe.

2 shows a probe implemented on a router.

3 illustrates a signaling scenario.

4 illustrates an interface of a topology aware probe in accordance with the present invention.

5 shows a topology recognition system according to the present invention.

6A illustrates probe registration, a signaling scenario in accordance with the present invention.

6B illustrates registration via redirection, which is a signaling scenario in accordance with the present invention.

7 shows an example synchronization according to the invention.

8 illustrates a probe topology sample and adjacency tree in accordance with the present invention.

The above mentioned problem is solved by the present invention according to the independent claims.

Preferred embodiments are set forth in the dependent claims.

An advantage of the present invention is to provide a topology recognition system usable in heterogeneous IP networks.

Another advantage is to provide a topology aware system that is flexible, scalable and provides high performance and accuracy.

Another advantage of the present invention is that the probe can be configured to perform light operation to minimize the adverse effect on the router's performance, and the probe can take more workload if many routers are present in the resource.

The topology recognition system according to the present invention has been devised to overcome the problems listed above. Accordingly, the topology recognition system 500 according to the present invention shown in FIG. 5 provides the following.

Mechanisms to maintain probe adjacency (covers signaling issues)

How topology-aware probes automatically configure themselves in a hierarchical fashion and run a set of connections (which addresses robustness and manages many router problems)

A protocol mechanism for transmitting topology state in an efficient manner (covers the signaling issues mentioned above);

A system combining the above to provide robust and efficient topology recognition

Topology recognition system 500 is shown in FIG. The system 500 includes a central node 502 and a topology recognition unit P that operates on one or more routers 504 in the domain, referred to as probes. There is no limit to the number of routers in the domain where the topology awareness probe P should be executed. Probes can exist in any number of routers in a domain, from one single router to all routers. However, it is desirable that most routers 504 in the domain include a topology aware probe P. Routers that do not include probe P (ie, noncompliant routers) are indicated at 506. The central node 502 is connected to one or more routers 504 that include a probe P. Moreover, routers are connected to other routers, and some of the routers including the probe P are suitable as aggregation points. The topology recognition probe P is a unit capable of obtaining topology information from another unit in the IP network, and is executed by software operating in another general router. Topology information is accessible via SNMP and stored in the MIB. The MIB is located in the router.

Topology information is sent from the probe P to the central node 502, which may use this information for various purposes, for example, for network visualization and graphical management interfaces. Therefore, central node 502 stores and processes topology information. The central node 502 of the system may use, for example, a statically constructed address or a spare anycast address in the managed routing domain (ie, the anycast address is contacted, and the anycast address is one or more in a group). Can be combined with more computers, and one of the computers in the group responds).

The function of probe P is described by its interfaces, topology aware system interface 402, local resource interface 406, network interface 404 and probe adjacency interface 408, as shown in FIG. 4. The topology aware system interface is hereinafter referred to as the system interface 402. Detailed descriptions of each interface are provided in the following subareas. In general, the function of each interface is as follows.

Topology recognition system interface 402: The topology recognition probe is part of a topology recognition system. The system includes a central node and additional probes. Topology information is sent from the probe to the central node via this interface.

Network interface 404: The probe collects information via this interface about other network components that do not include topology aware probes (e.g. routers and switches). In the current Internet standard, SNMP is the common protocol used for this interface.

Local Resource Interface 406: Since the probe is running on another generic router, there is topology information to obtain locally on the router.

Probe Neighbor Interface 408: Each probe maintains a relationship with an adjacent probe to minimize signaling through the network interface and the topology aware system interface.

By using a topology aware probe P that includes a topology aware system interface 402, the topology information is transmitted efficiently by optimizing the signaling. Robustness and management of a large set of topology aware probes is achieved by registering probes at the central node and guiding aggregation points. Thus, the system can be configured automatically.

By using a topology aware probe P that includes a probe adjacency interface 408, topology information signaling is reduced using path signaling to obtain topology information from a domain having a noncompliant router. Thus, data transmission over topology aware system interfaces and network interfaces is minimized. These interfaces provide enhanced robustness by being adjacent, i.e., supervising each other. Probe P can thus be dynamically configured automatically using probe registration and aggregation points. Network plane signaling is reduced using probe jurisdiction for minimized probing, that is to say that no overlap operation is performed on the network interface. Therefore, signaling through the system interface and the network interface is minimized, which means that the problem shown in FIG. 3 is avoided.

Network interface 404 collects information from non-compliant routers, that is, routers without probes, thereby reducing network plane signaling.

Local resource interface 406 reduces network plane signaling by using locally available resources for topology information. As a result, you get enhanced overall performance when this interface is used.

The topology aware probe P may include the topology aware system interface 402 in combination with the other three interfaces (ie, probe proximity interface 408, network interface 404, or local resource interface 406). Preferably, the probe includes all four interfaces to provide robust and efficient topology recognition.

The interface is described in the subsections below using the signaling diagram and description thereof. Note that the exact details of the message, the message being exchanged or formatted, and the content of each message are not precise. This is to provide enough information to understand all the functions, not to reveal details for implementation.

Topology-aware system interface

In a first embodiment of the invention, the topology aware probe P comprises a system interface 402.

If most routers in a large domain have probes, connection management and message multiplexing are complex issues. Connecting the topology aware probes to the rest of the topology aware system is handled by this interface, and the remainder of the topology aware system 500 includes a central node 502 and an additional topology aware probe P.

Probe Registration and Aggregation Points

The topology aware probe P registers with the central node 502 of the system at startup. The start of registration is with the probe P. When a registration message is received at the central node 502 of the system, the identifier of the probe P is added to the list of known probes stored in the central node 502. It is then determined whether to accept the probe connection as is (2a), use the probe as the aggregation point (2b), or redirect the probe to the previously selected aggregation point (2c). A signaling alternative according to the first preferred embodiment is shown in Fig. 6a.

In the case of 2a, the probe will maintain its relationship to the central node 502 of the system and will pass all of its topology information directly. In the case of 2b, the probe P will receive topology information from another probe P and pass this information along with its topology information to the central node 502 of the system. In the case of 2c, the probe will tear down its relationship to the central node of the system and establish a new relationship with the set point recognized in the redirect message.

It should be noted that the detailed description of how to make the aggregation decision is not within the scope of the present invention. However, this may be useful to inform the probe that it is ready to be a collection point, that is, to send topology information from another probe in addition to its own information, which may be included in the determining algorithm. It is clear that both memory and processing requirements will be greater in the aggregate probe P than in the normal probe P.

The signaling scenario in which the redirect-message is used according to the first preferred embodiment of the present invention is shown in FIG. 6B. The original registration message 1 arrives at the central node 502 of the system, and the central node 502 issues a redirect message 2. The redirect message includes information about where to redirect (AP) and information that can be attached to the new registration message for authentication purposes. In this example, the token is issued by the central node 502 of the system. This token is sent along with the registration message when the probe registers the aggregation point. This enables registration authentication and authorization at the aggregation point. Note that the token is an example. When implementing this system, other means can be used for trust. Upon receipt of the registration message, the set point responds with a keep going message.

An important feature of the method is that the set point (ie probe P) allows to introduce additional layers if desired. In the example of FIG. 6B, there is a general probe P at the lowest level, the next aggregation point, and the central node 502 of the system at the top. If for some reason the aggregation point wants to introduce an additional layer, the aggregation point will send a redirection message to the probe P instead of the persistent message used in this example. Used to determine whether and when to introduce an additional layer. There are many options for the algorithm that is used. A simple example may be based on the number of connections to the low-level probe P.

In general, every aggregate relationship in a system will have parent and child nodes. At the highest level, the central node P of the system is the parent and all the collection points are children.

The registration process (including redirection, etc.) is continuously performed (eg, periodically or irregularly) so that all probes (P) acting as aggregation points (including the central node of the system and all other aggregation points) can reassess their status. At intervals). This interval should be sparse to keep signaling overhead to a minimum.

If the relationship between the aggregation parent probe P and the child probe P is lost due to a stop in the network, the parent may issue an aggregation message that is not required for any probe set that previously received the registration message. In connection with this aggregation message, there will also be a series of redirect messages to recognize the new aggregation point. This means that all aggregate parents maintain the state of the received registration message.

Send topology information

The amount of information needed to represent the details of a large topology is important. There is a need for a method to minimize the amount of information transferred between a parent and a child in a set relationship.

In order to achieve both robustness and low signaling overhead, a scheme in which information is based on update is used in conjunction with a synchronization method in which it is continuously (eg periodically) repeated. Probe P sends an unsolicited update message when detecting a change in topology. Well-behaved probes run filters to avoid sending updates as a result of periodic routing protocol updates. The update message only needs to be sent if a substantial change has occurred in the topology.

The format of the topology information message is not required in the present invention. It is necessary to transmit the information in delta form, where each information inserts, changes or removes some of the information. If there is a change in existing data, the change command is used for updating. The remove command is sent for information that is no longer relevant.

In addition to the update messages described above, there is a synchronization structure (continuously repeated) designed to detect mismatches in the parent and child probes of an aggregate relationship. Iteratively, using sparse spacing, the probe sends a compressed representation of its topology information to its set parent.

In Fig. 7, two synchronization scenarios according to the first embodiment of the present invention are shown. First, the child probe P sends a synchronization message that contains a compressed representation of its state (ie, topology information). The set parent receives this message and compares it with the state for the current child. It may be calculated on demand and may be kept in memory at all times. In the case of 2a, the parent finds that the state is matched and returns it back. In the case of 2b, a state mismatch is found (in this case the parent lacks subset-X significantly differently from the child), so the parent requests an update to subset-X of the information from the child. However, it is also possible to initiate synchronization by having the parent send a synchronization message instead of the child, which child receives the message and compares it with the state for the current parent. Note that the aggregate parent can also be the central node.

The compressed representation of the topology information of the probe can be, for example, a series of checksums or periodic addition checks. Algorithm selection is left for implementation. The basic optimization to be considered by the implementation is the ability to recognize a smaller subset of information that the state mismatches. This makes it more precise when the parent requests for renewal. If this mechanism is lacking, the child's overall state should be sent when a state mismatch is found.

Probe Adjacency Interface

In a second preferred embodiment of the invention, the probe comprises a probe adjacency interface 408.

Probes use on-demand protocols to establish and maintain proximity to each other. The basic function of this protocol is to let the probes know about each other. More advanced features of this protocol are designed to allow probes to know each other about their environment (i.e. directly connected neighbors) and to allow the probes to agree on what to do with a probe.

The following explains how adjacency is established. The next section describes two different modes of operation for the protocol after proximity is established. In the "Probe Jurisdiction for Minimized Probing" section, a mode of use for general purpose topology recognition systems is provided, and the "Path Signaling to Avoid Probing" section provides a model for more specialized applications.

Adjoining

For each probe, a tree structure view of the network is maintained to determine which other probes are adjacent. Each probe keeps itself at the root of the tree. There will be one branch for each interface on the probe router. A branch may or may not include one or more noncompliant routers as intermediate nodes and adjacent probes as leaves. One example is shown in FIG. 8.

In Fig. 8, routers A, E and F, indicated by circular dots, activate the topology awareness probe. Routers B, C and D are non-compliant. In terms of router A, the adjacency tree first contains two main branches, as shown on the right side of the figure. Looking closer at the branches, router A finds that router E appears more than once as a leaf, which means that some can be pruned. Router A chooses to prun the longer branch in front of the shorter branch, which means that routers A, B, C, and E will be pruned. When this step is performed, router A is likewise pruned branches of routers A, B and E because router E is likewise found via router D. The routers A, D, * are kept because both routers E and F are reached in this way. Briefly, the probe strives to keep as few and as short branches as possible in its proximity tree. In conclusion, the router A will maintain its proximity to the routers E and F connected to the router D through its branches. Note that branches do not have to be the same as actual routing and are logical. For example, a packet from router A to router E may be routed through router B in a real network, where the adjacency tree will use router A, D, E branches. This means that when two or more probes are present each probe has at least one contiguity. This also means that all compliant routers are logically connected through a series of endless adjacencies. Each adjacency is kept alive using messages, preferably small messages that are repeatedly sent by each router to all adjacent routers. This means that lost probes can be found using intermediate breaks of adjacent probes. Note that all probes perform tree building and pruning to establish their adjacency. It is speculated that there is a decisive way to determine whether a router is compliant by trying its proximity to itself. The present invention does not require a special solution, but uses a spare transport protocol port number as an example. In this way, when the probe examines its proximity (see section "Network Interface"), the probe may attempt to establish proximity with itself to determine whether it is compliant. If adjacency is lost by a defective probe, the process of building the adjacency tree and pruning some branches must be completed again. Note that if some additional state is maintained, the probe may know which of its tree branches should follow the adjacency again.

Probe jurisdiction for minimized probing

Probe jurisdiction defines the noncompliant router in which the probe is responsible for probing. If the method for topology awareness is to actively probe all routers, the probe jurisdiction can be used to optimize signaling through the probe's network interface. In this way, there should be no overlap in the probe jurisdiction. In other words, each noncompliant router belongs to only one probe jurisdiction. This section describes how probe proximity is used to create non-overlapping jurisdictions. In establishing probe proximity, each probe will observe a series of noncompliant routers. The probe maintains a list of noncompliant routers and metrics, and a probe identifier is coupled to each of these probes. The metric is a one-dimensional indication of how far apart the noncompliant router is. For example, the metric can be the number of hops between the probe and the noncompliant router. The probe identifier is set to recognize a probe with a router in its jurisdiction. Initially, the probe requires all noncompliant routers that appear to belong to its jurisdiction.

For each pair of adjacent probes, there is one master and one slave. The master-slave relationship is determined at the time of establishment of proximity, and may be based on, for example, what probes are based on preconfigured probe priorities or are the beginning of proximity. However, the slave sends a subset of its list of noncompliant routers to the master. The subset is a list of routers in the original adjacency tree branch between the two probes before pruning is performed. Upon receiving a list of routers from a slave, the master compares it to its list. Each item that appears in both the master and slave lists is compared. No matter which probe has a smaller metric associated with a router, it has that router in its jurisdiction. If the metrics of the two probes are the same, the master probe is determined using different deterministic methods. For example, it can be determined by the master-slave relationship. Starting with a large jurisdiction, each probe will try to make its jurisdiction as small as possible.

Path signaling to avoid probing

The model described in this section is not directly applicable to general purpose topology recognition systems. In applications where probes can be strategically placed at specific locations in the network, this model works well. Under this mode of operation, the probe avoids obstructive probing of noncompliant routers for topology data. Instead, the probe relies on inner-probe signaling to know the routing for the noncompliant router. By default, each probe knows its local routing data through the local interface and uses the network interface to know the paths of all neighboring probes. Send to all adjacent probes. This means that the central node of the system must run an algorithm similar to that used by the link-state router to compile a complete map of the topology. For every local interface to which a noncompliant router is connected, the probe does the following:

Probe the route to all probes accessible through the outgoing interface. The difference with the adjacency tree is that the actual path taken by the packet is examined here, not the logical branch.

The probing described above is different from that used in the previous section. In this mode of operation, probing refers to tracing a route with a tool such as a traceroute or ping program rather than examining the node with SNMP.

Note that the path can only be found if there is a probe at both ends. This is a serious obstacle if the application is a general purpose topology aware system. However, if your application has specific requirements, this method is very useful. One example is for path-response resource management where probes are placed at inlet and outlet nodes of a network requiring management.

Network interface

In a third preferred embodiment of the present invention, the topology aware probe comprises a network interface.

By using the network interface of FIG. 4, the probe can probe non-compliant routers to know topology information that is not available locally. Methods of probing routers for topology information are known. Most of the relevant information is available from standardized MIBs and can be accessed via SNMP. Existing methods are used for this interface. One or more of the following events may begin the process of gathering information from non-compliant routers, ie routers that do not include topology aware probes that conform to the rest of the probes in the topology aware system.

Start-up. When the probe first starts up, it should perform a collection of information.

-Routing protocol events. If events in the routing protocol can be monitored, they can also be interpreted from the probe and used to start collecting information. One example where this is useful is when a change is found dynamically, in which case a routing protocol event is a signal that something has changed and that information should be collected.

Periodic Event: To verify that the probe's status is correct, the probe may use periodic polling of the information.

Explicit instructions from network components, eg SNMP traps from routers.

Local resource interface

In a fourth preferred embodiment of the invention, the topology aware probe comprises a local resource interface.

Depending on the router platform, different resources may be available. In general, there will be some kind of core API that allows some piece of software on the router to access routing and interface information. Another approach to local resources is to use SNMP locally to obtain the required information. An example of a core API available locally for routing information is the manual page for 'route' in the fourth section of the FreeBSD manual page (the FreeBSD core interface manual family of routines available on BSD-based routers). The root described.

In domains where link-state routing is used, probes can access a link state database managed by routing protocol software to obtain topology information. Using a local interface has the following advantages:

Avoid network signaling overhead.

More reliable than using SNMP over a network.

Dynamic topology awareness can be achieved through inexpensive polling, or by receiving unsolicited callbacks (eg, signals or interruptions) from other software components in the router if the local interface provides such a mechanism.

The topology aware probe according to the invention comprises at least a system interface. However, in addition to the system interface, the present invention may include the above-described interface (ie, network interface, local resource interface, and probe neighbor interface) in any combination.

The method for obtaining a topology recognition system according to the invention described above can be implemented by a computer program product comprising software code means for performing the steps of the method. The computer program product may be operated on a processing unit at a router in an IP network. The computer program may be loaded directly or from a computer usable medium such as a floppy disk, CD, Internet, or the like.

The invention is not limited to the preferred embodiments described above. Various alternatives, modifications, and equivalents may be used. Therefore, the above-described embodiments should not be used for the purpose of limiting the scope of the present invention, which is defined by the appended claims.

Claims (27)

10. A method for providing topology awareness information in an IP network, the IP network comprising a central node 502 of a topology aware system 500 adapted to store and process topology information, wherein the central node 502 is configured to store the topology information. Connected to one or more topology aware units (P) implemented in a router 504 in an IP network, the units comprising the functionality of a topology aware system interface 402, wherein the method for providing topology awareness information, Sending a registration message from one of the topology recognizing units (P) to the central node (502); Adding, at the central node (502), an identifier of the unit (P) to a list of known units (P); And Sending a response message from the central node 502 to the unit P, The response message causes at least the unit P to: If the current relationship between the unit (P) and the central node (502) is accepted, let the central node (502) maintain the current relationship; If the central node (502) determines that the unit (P) will be used as an aggregation point, let it gather; or A method of providing topology awareness information, having the ability to instruct to redirect to a previous aggregation point if there is a suitable aggregation point. The method of claim 1, When the unit P is instructed to maintain a current relationship with the central node 502, further comprising transferring the topology information from the unit P to the central node 502. How to Provide. The method of claim 1, Receiving topology information from another unit (P); And And when said unit (P) is commanded to aggregate, forwarding said topology information to said central node (502) together with topology information of said router. The method of claim 1, Tearing down a current relationship from the unit (P) to the central node (502); And And when the unit (P) is instructed to redirect, establishing a new relationship between the unit and the aggregation point identified in the response message. The method according to any one of claims 1 to 4, And the step is repeated continuously. The method according to any one of claims 1 to 5, And wherein every aggregate relationship includes a parent node and one or more child nodes. The method of claim 6, wherein the step, If the relationship between the parent aggregation unit (P) and one or more child aggregation units (P) is lost, sending an unsolicited aggregation message from the unit (P) to a particular set of units that previously had a parent relationship ; And And sending an additional message from said unit (P) containing information about a new aggregate relationship. The method of claim 1, wherein the method is Sending an unsolicited message from the unit (P) when a topology change is detected in the network; And And further comprising filtering the unsolicited message by the unit P to avoid sending only a message as a result of the actual change of the network topology and sending a message as a result of repeated update. How to Provide Information. The method of claim 6, wherein the method is Compare the compressed representation of the first unit to the second unit (or the compressed representation of the topology information of the first unit with a corresponding compressed representation for the second unit (or the central node 502). Or, transmitting to the central node (502). The method of claim 9, wherein the method is When a difference between the compressed representation of the first unit P and the compressed representation of the second unit (or the central node 502) is detected, the first unit P and the first And performing synchronization between the two units (or the central node (502)). The method according to any one of claims 1 to 10, The topology recognizing unit P comprises the function of the network interface 404, The method, Collecting topology information from the non-compliant router (506). The method of claim 11, The collecting step is performed using a simple network management protocol (SNMP), topology recognition information providing method. The method according to any one of claims 1 to 12, The topology recognition unit P comprises the functionality of the probe proximity interface 408, The method further includes maintaining a tree-structured view of the network, each unit P retains itself as the root of the tree, and each branch of the tree is a noncompliant router 506. ) As a central node and adjacent units as leaves. The method of claim 13, And each adjacent pair of units (P) has one single relationship. The method according to any one of claims 1 to 14, wherein the method And maintaining the adjacency alive by transmitting messages from each unit (P) to substantially all adjacent units (P), respectively. The method of claim 13, wherein the method comprises Defining a jurisdiction of noncompliant router 506 in which unit P is responsible for probing, each noncompliant router 506 belonging to a particular jurisdiction; Maintaining a list of all noncompliant routers 506 belonging to the jurisdiction of the unit P, each router having a metric indicating a distance from the unit P to the noncompliant router; Combined with an identifier of said unit (P). The method of claim 16, There is one master node and one slave node for each pair of adjacent units P, the master and slave relationships are determined at the establishment of the adjacency, and the method is Transmitting a subset of the noncompliant router (506) list from the slave unit to a different master unit; And Comparing each router metric in the slave list with a corresponding router metric in the master list, occurring in both the slave list and the master list, wherein the router has a minimum metric associated with the router 506. And a unit (P) obtains the router (506) in its jurisdiction. The method of claim 13, wherein the method comprises Obtaining local routing data by the unit (P) via a local interface; And Acquiring route information to an adjacent unit using the network interface 404 by the unit, wherein the unit P is configured to display its local routing table and a representation of the route in the topology aware system interface ( Transmitting the topology recognition information to its neighboring unit (P) through 402. The method according to any one of claims 1 to 18, The topology recognizing unit P comprises the function of the local resource interface 406, The method, Obtaining topology information using locally available resources at the router when the unit (P) is executed. The method of claim 19, And the resource is kernel application programming interfaces (kernel APIs). The method of claim 19, The resource is accessed using a Simple Network Management Protocol (SNMP), topology recognition information providing method. 22. A computer program product directly mountable in an internal memory of a router in an IP network, comprising a software code area for performing the steps of claims 1-21. A computer program product stored on a medium usable in a computer comprising a readable program for causing a router in an IP network to control the execution of the steps of claims 1 to 21. A topology recognition unit P for providing topology recognition information in an IP network, wherein the topology recognition unit P is executed in the router 504 of the IP network, the unit comprising an additional topology recognition unit P and Belonging to a topology recognition system 500 comprising a central node 502, the unit P being a function of the topology recognition system interface 402, namely: Means for sending a registration message to the central node (502); And Means for receiving a response message from the central node 502, The response message causes at least the unit P to: If the current relationship between the unit (P) and the central node (502) is accepted, let the central node (502) maintain the current relationship; If the central node (502) determines that the unit (P) will be used as an aggregation point, let it gather; or Topology Recognition Unit (P) having the ability to instruct to redirect to the previous aggregation point, if there is a suitable aggregation point. The method of claim 24, The unit (P) comprises a function of a network interface (404), ie means for collecting topology information from the non-compliant router (506). The method of claim 24 or 25, The unit P comprises a function of the probe adjacency interface 408, i.e. a means of maintaining a tree-structured view of the network, wherein each unit P maintains itself as the root of the tree and the angle of the tree Branch recognition unit (P), which comprises a non-compliant router 506 with the branch as an intermediate node as a leaf The method according to any one of claims 24 to 26, The unit functions of the local resource interface 406, namely: Means for acquiring topology information using locally available resources at said router (504) while said unit (P) is running.