Multiplex communications – Network configuration determination
Reexamination Certificate
2000-02-01
2003-09-02
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Network configuration determination
C370S256000
Reexamination Certificate
active
06614764
ABSTRACT:
FIELD OF THE INVENTION
This application relates to computer communication networks for interconnecting computers and, specifically, to routing in bridged networks.
BACKGROUND OF THE INVENTION
Computer interconnection and communication systems are typically referred to as networks. Networks are generally classified according to their geographical extent as local area networks (LANs), metropolitan area networks (MANs) and wide area networks (WANs).
LANs are commonly used to transmit messages between relatively closely located computers. LANs are characterized by several basic types of organizational architectures including linear, ring and mesh. For example, Ethernet is a widely used linear LAN and FDDI (fiber distributed data interface) is a widely used ring LAN. Unlike linear and ring LANs, mesh LANs have an arbitrary topology. One mesh LAN architecture is described in U.S. Pat. No. 5,088,091, entitled “HIGH-SPEED MESH CONNECTED LOCAL AREA NETWORK,” issued on Feb. 11, 1992 to Michael D. Schroeder et al., and U.S. Pat. No. 5,138,615, entitled “RECONFIGURATION SYSTEM AND METHOD FOR HIGH-SPEED MESH CONNECTED LOCAL AREA NETWORK,” issued on Apr. 11, 1992, to Leslie B. Lamport et al., both of which are hereby incorporated by reference.
A LAN is a shared transmission medium, such as a continuous conductor, that connects some number of addressable devices, such as printers, servers, and workstations. The addressable devices are called stations. Special attention is paid to LANs, such as Ethernet, in which each station has a globally unique and unchanging address, called its unique identifier (UID).
Stations on a LAN communicate by sending and receiving data packets or groups of data packets. In general, a packet contains the station address, UID, of the packet source, the station address UID of the packet destination and a payload. Packets can be distinguished by their destination address type. For example, a unicast packet is a packet with a station address as its destination. Stations on a LAN can also communicate by sending a packet to a group of destinations. In this case the packet has a group address UID as its destination and is called a multicast packet. Typically one bit in the UID is dedicated to distinguish station addresses from group addresses. Typically also one particular group address is dedicated to signify the group of all stations. A multicast packet with a group address of all the stations as its destination is called a broadcast packet.
LANs have basic limitations such as the number of stations, bandwidth and physical extent. A LAN offers, however, a useful high-speed communication service that facilitates data sharing and client-server interactions among its stations. In order to extend the benefits of a LAN beyond the basic limitations of a single LAN, forwarding devices, known as bridges, are used to interconnect LANs to form extended LANs.
An extended LAN is a collection of LANs interconnected by bridges. Bridges are addressable devices that forward packets back and forth between the bridged LANs. An extended LAN architecture with bridged LANs is referred to as a bridged network architecture. Each of the individual component LANs is known as a network segment. The network segment is also simply referred to as the segment.
Since bridges are addressable devices, they are stations on each of their connected LANs. Stations that are not bridges are known as end stations. For simplicity, end stations are also called hosts.
A bridge includes a plurality of bridge ports, each one corresponding to a connection between the bridge and a segment. Bridge functions that pertain to a specific connection between the bridge and a segment are typically described as being performed by the corresponding port.
In general, a single bridge may connect to any number of LANs, although typically a bridge connects to a small number of LANs, say between two and eight. Notwithstanding hosts, an extended LAN consists of segments, bridges and the connections between segments and bridges.
Structurally, an extended LAN can be represented as a graph. A graph is a mathematical object consisting of a set of nodes and a set of edges. Each edge in a graph connects two nodes. In a graph representing the extended LAN, the nodes represent the segments and bridges and the edges represent the connections, in the extended LAN, between the segments and bridges. This graph is called the network topology graph. The network topology graph is also referred to simply as the topology.
Using bridges to create LAN-to-LAN interconnections allows each host on the attached LANs to communicate with the other hosts on the attached LANs as if those hosts were on a same LAN. To emphasize that the interconnection of LANs using a bridge is transparent to hosts communicating across the bridge, this kind of interconnection is also called transparent bridging. An example of a LAN interconnection that is not transparent is IP (Internet protocol) subnet routing.
Transparent bridging requires that the bridges dynamically maintain address information for each of their connected LANs in order to facilitate the routing of packets. Bridges learn about the presence of hosts by listening to packets passing by. From this listening, bridges obtain the addresses of hosts on their connected LANs. Bridges use host addresses to help make forwarding decisions.
In a network with transparent bridging, the forwarded copy of a packet must be bit-for-bit identical with the original packet. Since the forwarded copy of a packet looks just like the original, it is difficult to learn exactly where hosts are located by listening to packets passing by. If a decision is made to allow forwarding of a packet in a loop, the packet would cycle endlessly in the network consuming huge amounts of bandwidth. Therefore the bridges must take care in their packet forwarding decisions never to allow any packet to be forwarded in a loop.
The Institute of Electrical and Electronics Engineering (IEEE) standard for bridged Ethernet (IEEE Std 802.1D-1993) prevents forwarding loops and solves the learning problem by classifying certain connections as active connections and the remainder as standby connections. Host packets travel only on active connections. This means that a bridge never transmits a host packet on a standby connection, and any packet a bridge might receive from a host on a standby connection is ignored. The active connections are selected so as to form a spanning tree in the network topology graph. For control purposes, one bridge is selected as the root of the spanning tree but selection of the root does not affect packet forwarding in any way. In the spanning tree of a network topology graph, for any two segments, S and D, there is exactly one path of active connections from S to D and, hence, only one path that packets from S to D can follow. Multicast packets also follow the spanning tree. When a bridge receives a multicast packet on an active connection it forwards the packet onto all of its other active connections. This results in copies of the multicast packet traveling over all active connections in the network and hence over all segments. This process is called flooding.
As previously mentioned, bridges solve the learning process by listening to packets passing by. The learning problem is solved because any host packets that a bridge hears arriving on an active connection must be from hosts that can be reached only by transmitting back on this active connection. By listening to packets the bridge learns which of its active connections to use to reach a given host. In other words, the bridge learns the direction (in the spanning tree) to a given host. Initially, none of the bridges knows the direction to any host after the bridges have selected the spanning tree. Similarly, when a bridge receives a packet (on an active connection) it may not know yet the direction to the packet's destination host. In this case, it forwards the packet onto all of its other active connections in the same manner as a multicast packet. Thus, when no bridge k
Anderson Darrell
Lillibridge Mark D.
Rodeheffer Thomas L.
Thekkath Chandramohan A.
LandOfFree
Bridged network topology acquisition does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bridged network topology acquisition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bridged network topology acquisition will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3092762