Network Topology Discovery Algorithms

cdpCacheTable, ifTable, ipAddrTable

The whole algorithm is based on cdpCacheTable variable analysis. Once a network device has this variable the following set of instructions is executed for every single row:

1. Get the value of cdpCacheIfIndex and save it as a source interface for potential link;

2. Get the value of cdpCacheDevicePort and save it as a network interface description for potential link;

3. Check the value of cdpCacheAddressType field. If equals 1 (IP address), get the actual address from the field cdpCacheAddress and try to find corresponding network device in the system;

4. If the device is found, check if cdpCacheTable is present;

4.1. If so try to find an IP address of the initial network device in any cdpCacheAddress field of the table. Once found save the value of corresponding cdpCacheIfIndex field as a target interface for potential link;

4.2. Otherwise check the content of ifTable variable. If network interface description (step 2) is present in any ifDescr field of the table use the ifIndex value of the same row as a target interface;

5. If both source and target interfaces are not yet mentioned in any other topology link save the new link with these interfaces.

ipCidrRouteTable (or ipRouteTable), ipAddrTable

All the required information for the algorithm is included in ipCidrRouteTable variable (or ipRouteTable if absent).

1. Get the route type (ipCidrRouteType or ipRouteType). For any value other than 4 (indirect route) go to the next step;

2. Get the source interface (ipCidrRouteIfIndex or ipRouteIfIndex);

3. Get the next hop value (ipRouteIfIndex or ipRouteNextHop);

4. For every single network device in the system check its ipAddrTable variable. If the next hop value (step 3) is present in any ipAdEntAddr field save corresponding ipAdEntIfIndex field value as a target interface;

5. If both source and target interfaces are not yet mentioned in any other topology link save the new link with these interfaces.

lldpRemTable, lldpLocPortTable, ifXTable (or ifTable), lldpLocChassisId, lldpLocChassisIdSubtype

To be processed by the algorithm a network device should have both lldpRemTable and lldpLocPortTable variables. For every such device the following set of instructions is executed:

1. Get chassis type (lldpRemChassisIdSubtype field in lldpRemTable);

2. If the type is 4 (MAC address), get the actual address from lldpRemChassisId field and try to find corresponding network device in the system. If the device is found save it as target device;

3. Get local port number (lldpRemLocalPortNum field in lldpRemTable);

4. Using the port number find corresponding record in lldpLocPortTable (lldpLocPortNum field) and check its port ID subtype (lldpLocPortIdSubtype field);

5. If the subtype is 3 (MAC address) or 7 (local address), get the actual address from lldpLocPortId field and try to find it in ifXTable (or ifTable) variable (ifPhysAddress field) and use corresponding ifIndex field value as a source interface;

6. If there is no suitable record in the table, just use local port number (step 3) as a source interface;

7. Get remote port ID subtype (lldpRemPortIdSubtype field);

8. Using the port subtype calculate a target interface as described in step 5;

9. If still no luck, try to find source device's local chassis ID (lldpLocChassisId variable) in target device's lldpRemTable (lldpRemPortId field). Use the value from lldpRemLocalPortNum field as a target interface;

10. In case it is not possible, get remote port description (lldpRemPortDesc field in lldpRemTable) and try to find the corresponding record in the target device's lldpLocPortTable variable (lldpLocPortDesc field). Use the value from lldpLocPortNum field as a target interface;

11. If both source and target interfaces are not yet mentioned in any other topology link save the new link with these interfaces.

There are two STP modes supported: classic STP and Multiple STP (MSTP)

dot1dStpPortTable, dot1dBaseBridgeAddress, dot1dStpPriority, dot1dBasePortTable, ifXTable (or ifTable)

The algorithm is only suitable for network devices with dot1dStpPortTable and dot1dBaseBridgeAddress variables present.

1. Get the bridge base address (dot1dBaseBridgeAddress);

2. For every single record in dot1dStpPortTable get the neighbour bridge ID (dot1dStpPortDesignatedBridge field), neighbour port ID (dot1dStpPortDesignatedPort field) and neighbour MAC address (the address is extracted from the neighbour bridge ID starting from the 7th character);

3. If the bridge base address and the neighbour MAC address are not equal, go to the next step;

4. Try to find the neighbour switch device in the system. It should contain the neighbour MAC address in its ifXTable (ifPhysAddress field);

5. Get a source port (dot1dStpPort field);

6. Try to find a record in dot1dBasePortTable variable with the source port specified (dot1dBasePort field). If there is such a record, use its dot1dBasePortIfIndex field value as a source interface;

7. Check whether the neighbour device contains dot1dStpPortTable variable;

7.1. If it does, try to find a record in dot1dStpPortTable variable such that its dot1dStpPortDesignatedBridge field value equals the neighbour bridge ID (step 2) and dot1dStpPortDesignatedPort field value equals the neighbour port ID (step 2);

7.1.1. Get the dot1dStpPort field value of the record and convert it as described in step 6. Use calculated value as a target interface;

7.2. Otherwise split the neighbour port ID (step 2) using semicolon (:) as a separator and use the second fragment as a target interface;

8. If both source and target interfaces are not yet mentioned in any other topology link save the new link with these interfaces.

swMSTPMstPortTable, swMSTPPortTable, dot1dBaseBridgeAddress, ifXTable (or ifTable)

The algorithm is only suitable for network devices with swMSTPMstPortTable and dot1dBaseBridgeAddress variables present.

1. Get the bridge base address (dot1dBaseBridgeAddress);

2. For every single entry in swMSTPMstPortTable that is not on "disabled" status (swMSTPMstPortStatus field value not equals 2) get the designated bridge MAC address (the address is extracted from the designated bridge (swMSTPMstPortDesignatedBridge field) starting from the 7th character);

3. If the bridge base address and the designated MAC address are not equal, go to the next step;

4. Try to find the designated switch device in the system. It should contain the designated MAC address in its ifXTable (ifPhysAddress field);

5. Get a source port (swMSTPMstPort field). Use it as a source interface;

6. Check whether the designated device contains swMSTPMstPortTable variable;

7. If it does, try to find a record in swMSTPMstPortTable variable such that its swMSTPMstPortDesignatedBridge field value equals the bridge base address (step 1);

8. Use its swMSTPMstPort field value as a target interface;

9. If both source and target interfaces are not yet mentioned in any other topology link save the new link with these interfaces.

None

1. Try to find direct links;

1.1. For every single switch device in the system iterate through its AFT;

1.2. Get the entry's source interface;

1.3. For every network device, associated with this interface, check whether its AFT contains a counter-link;

1.4. If any counter-links are found, use its interface as a target interface;

1.5. If both source and target interfaces are not yet mentioned in any other topology link save the new link with these interfaces.

2. Try to find links through L1 switches;

Briefly, this step includes an attempt to find a pair of network devices (or several pairs) such that:

2.1. A set of devices associated with some specific network interface of the source device has some elements in common with a set of devices associated with some specific network interface of the target device;

2.2. At the same time a set of devices NOT associated with the same network interface of the source device should not have any elements in common with a set of devices NOT associated with the same network interface of the target device;

2.3. If both conditions are met, check whether source and target interfaces are not yet mentioned in any other topology link and save the new link with these interfaces.

3. Try to guess links. Guessing links is pretty complicated algorithm and won't be explained in this article.

Was this page helpful?

Tell us more

Send

Thank you!