RFC 2108
Definitions of Managed Objects for IEEE 802.3 Repeater Devices using SMIv2
4. Topology Mapping The network mapping algorithm presented below takes information available from network devices such as repeaters, bridges, and switches, and creates a representation of the physical topology of the network. Networking devices connect to the network via one or more ports. Through these ports, the device is capable of hearing network packets sent by other devices. By looking the source address in the packet, and identifying which port the packet was heard on, the device can provide information to a Network Management System about the location of an address in the network, relative to that device. For devices such as bridges and switches, the association of address to port can be retrieved via the forwarding data base part of the Bridge MIB. For repeaters, the rptrAddrSearchTable may be used to perform the association. Given this information, it would be possible for the NMS to create a topology of the network which represents the physical relationships of the devices in the networks. The following is an example of how this might be done: Assume the network: ============================= | | | | | | d1 d4 d7 / \ | / \ | d2 d3 d5 | | d6 The discovery process would first determine the existence of the network devices and nodes in the network. In the above example, the network devices discovered would be: d1,d2,d3,d4,d5,d6,d7 From this list of discovered devices, select (arbitrarily or via some heuristic) a device as the starting point. From that device, determine where all other devices are located in the network with respect to the selected device.
For example, if d1 is the selected device, the network in relation to
d1 would look like:
d1
/ | \
/ | \
d2 d3 d4,d5,d6,d7
So d1 sees d2 on one port, d3 on another port, and d4, d5, and d6 on
the third port. In other words, using the rptrAddrSearchTable (if d1
is a repeater) or the Forwarding Database (if it is a bridge or a
switch), d1 has located d2 on one port, d1 has located d3 on another
port, and finally, d1 has located d4, d5, d6, and d7 on yet another
port.
After the first step of the algorithm is accomplished, the next and
final step is a recursive one. Go to each of these temporary
'segments' (e.g., the segment connecting d1 and d2, or the segment
connecting d1 and d3, or the segment connecting d1, d4, d5, d6, and
d7) and determine which of these devices really belongs in that
segment.
As new segments are created due to this process, the recursive
algorithm visits them, and performs the exact same process.
In the example, the segments connecting d1 and d2, and connecting d1
and d3, require no further scrutiny, since there are only two nodes
in those segments. However, the segment connecting d1, d4, d5, d6,
and d7 may prove to be one or more segments, so we will investigate
it.
The purpose of this step is to determine which devices are really
connected to this segment, and which are actually connected
downstream. This is done by giving each of the child devices in the
segment (d4, d5, d6, and d7) a chance to eliminate each of the others
from the segment.
A device eliminates another device by showing that it hears the
parent device (in this case, d1) on one port, and the other device on
another port (different from the port on which it heard the parent).
If this is true, then it must mean that that device is _between_ the
parent device and the device which is being eliminated.
In the example, we can see that device d4 can eliminate both d5 and
d6, , but nobody can eliminate d4 and d7, because everybody hears
them on the same port that they hear the parent device (d1). So the
resulting topology looks like:
d1
/ | \
/ | \
d2 d3 d4,d7
|
|
d5,d6
Next the algorithm visits the next segment, which is the one
connecting d4, d5, and d6. Using the process stated above, d5 can
eliminate d6, since it hears d4 on a different port from where it
hears d6. Finally, the topology looks like:
d1
/ | \
/ | \
d2 d3 d4,d7
|
|
d5
|
|
d6
This is actually the topology shown at the beginning of the
description.
With this information about how the network devices are connected, it
is a relatively simple extension to then place nodes such as
workstations and PCs in the network. This can be done by placing the
node into a segment, then allowing the network devices to show that
the node is really not part of that segment.
This elimination can be done because the devices know what port
connects them to the segment on which the node is temporarily placed.
If they actually hear the node on a different port than that which
connects the device to the segment, then the node must be downstream,
and so it is moved onto the downstream segment. Then that segment is
evaluated, and so forth. Eventually, no device can show that the
node is connected downstream, and so it must be attached to that
segment.
For example, assume the network:
=============================
| | |
| | |
d1 d4 d7
/ \ |
/ \ |
d2 d3 d5
| |
| |
e1 d6
In this network, we are trying to place e1 where it belongs. We
begin by placing it arbitrarily into a segment:
==================================
| | | |
| | | |
e1 d1 d4 d7
/ \ |
/ \ |
d2 d3 d5
|
|
d6
In the above case, we would give d1, d4, and d7 a chance to show that
e1 is not really on that segment. d4 and d7 hear e1 on the same port
which connects them to that segment, so they cannot eliminate e1 from
the segment. However, d1 will hear e1 on a different port, so we
move e1 down onto the segment which is connected by that port. This
yields the following:
=============================
| | |
| | |
d1 d4 d7
/ \ |
/ \ |
d2 d3,e1 d5
|
|
d6
Now we give everyone in that segment (besides that parent device, d1)
a chance to eliminate e1. Only d3 can try, and it succeeds, so we
place e1 on segment which is connected by the port on which d3 heard
e1. There is no segment there (yet), so we create one, and end up
with the following:
=============================
| | |
| | |
d1 d4 d7
/ \ |
/ \ |
d2 d3 d5
| |
| |
e1 d6
which is the correct position.
5. Acknowledgements
This document was produced by the IETF Hub MIB Working Group, whose
efforts were greatly advanced by the contributions of the following
people:
Chuck Black
John Flick
Jeff Johnson
Leon Leong
Mike Lui
Dave Perkins
Geoff Thompson
Maurice Turcotte
Paul Woodruff
6. References [1] IEEE 802.3/ISO 8802-3 Information processing systems - Local area networks - Part 3: Carrier sense multiple access with collision detection (CSMA/CD) access method and physical layer specifications, 1993. [2] IEEE 802.3u-1995, "MAC Parameters, Physical Layer, Medium Attachment Units and Repeater for 100 Mb/s Operation, Type 100BASE-T," Sections 21 through 29, Supplement to IEEE Std 802.3, October 26, 1995. [3] IEEE 802.3u-1995, "10 & 100 Mb/s Management," Section 30, Supplement to IEEE Std 802.3, October 26, 1995. [4] de Graaf, K., D. Romascanu, D. McMaster, K. McCloghrie, and S. Roberts, "Definitions of Managed Objects for IEEE 802.3 Medium Attachment Units (MAUs)", Work in Progress. [5] McCloghrie, K., and M. Rose, Editors, "Management Information Base for Network Management of TCP/IP-based internets: MIB-II", STD 17, RFC 1213, Hughes LAN Systems, Performance Systems International, March 1991. [6] SNMPv2 Working Group, J. Case, K. McCloghrie, M. Rose, and S. Waldbusser, "Structure of Management Information for version 2 of the Simple Network Management Protocol (SNMPv2)", RFC 1902, January 1996. [7] SNMPv2 Working Group, J. Case, K. McCloghrie, M. Rose, and S. Waldbusser, "Textual Conventions for version 2 of the Simple Network Management Protocol (SNMPv2)", RFC 1903, January 1996. [8] SNMPv2 Working Group, J. Case, K. McCloghrie, M. Rose, and S. Waldbusser, "Conformance Statements for version 2 of the Simple Network Management Protocol (SNMPv2)", RFC 1904, January 1996. [9] SNMPv2 Working Group, J. Case, K. McCloghrie, M. Rose, and S. Waldbusser, "Protocol Operations for version 2 of the Simple Network Management Protocol (SNMPv2)", RFC 1905, January 1996.
[10] Case, J., M. Fedor, M. Schoffstall, and J. Davin, "Simple Network Management Protocol", STD 15, RFC 1157, SNMP Research, Performance Systems International, MIT Laboratory for Computer Science, May 1990. [11] McMaster, D., and K. McCloghrie, "Definitions of Managed Objects for IEEE 802.3 Repeater Devices", RFC 1516, September 1993. [12] McAnally, G., D. Gilbert, and J. Flick, "Conditional Grant of Rights to Specific Hewlett-Packard Patents In Conjunction With the Internet Engineering Task Force's Internet-Standard Network Management Framework", RFC 1988, August 1996. [13] Hewlett-Packard Company, US Patents 5,293,635 and 5,421,024. [14] McCloghrie, K., and F. Kastenholz, "Evolution of the Interfaces Group of MIB-II", RFC 1573, January 1994. 7. Security Considerations Security issues are not discussed in this memo. 8. Authors' Addresses Kathryn de Graaf 3Com Corporation 118 Turnpike Rd. Southborough, MA 01772 USA Phone: (508)229-1627 Fax: (508)490-5882 EMail: kdegraaf@isd.3com.com Dan Romascanu Madge Networks (Israel) Ltd. Atidim Technology Park, Bldg. 3 Tel Aviv 61131, Israel Phone: 972-3-6458414, 6458458 Fax: 972-3-6487146 EMail: dromasca@madge.com
Donna McMaster Cisco Systems Inc. 170 West Tasman Drive San Jose, CA 95134 Phone: (408) 526-5260 EMail: mcmaster@cisco.com Keith McCloghrie Cisco Systems Inc. 170 West Tasman Drive San Jose, CA 95134 Phone: (408) 526-5260 EMail: kzm@cisco.com