Misplaced Pages

#533466

91-406: As the name suggests, STP creates a spanning tree that characterizes the relationship of nodes within a network of connected layer-2 bridges , and disables those links that are not part of the spanning tree, leaving a single active path between any two network nodes. STP is based on an algorithm that was invented by Radia Perlman while she was working for Digital Equipment Corporation . In 2001,

182-1107: A computer monitor or input device, audio hardware and USB interfaces. Many servers do not have a graphical user interface (GUI). They are configured and managed remotely. Remote management can be conducted via various methods including Microsoft Management Console (MMC), PowerShell , SSH and browser-based out-of-band management systems such as Dell's iDRAC or HP's iLo . Large traditional single servers would need to be run for long periods without interruption. Availability would have to be very high, making hardware reliability and durability extremely important. Mission-critical enterprise servers would be very fault tolerant and use specialized hardware with low failure rates in order to maximize uptime . Uninterruptible power supplies might be incorporated to guard against power failure. Servers typically include hardware redundancy such as dual power supplies , RAID disk systems, and ECC memory , along with extensive pre-boot memory testing and verification. Critical components might be hot swappable , allowing technicians to replace them on

273-436: A family of sets , it is possible to construct an infinite graph such that every spanning tree of the graph corresponds to a choice function of the family of sets. Therefore, if every infinite connected graph has a spanning tree, then the axiom of choice is true. The idea of a spanning tree can be generalized to directed multigraphs. Given a vertex v on a directed multigraph G , an oriented spanning tree T rooted at v

364-415: A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G . In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). If all of the edges of G are also edges of a spanning tree T of G , then G is a tree and is identical to T (that is,

455-515: A switching loop resulting in broadcast radiations and MAC table instability. If redundant links are used to connect switches, then switching loops need to be avoided. To avoid the problems associated with redundant links in a switched LAN, STP is implemented on switches to monitor the network topology. Every link between switches, and in particular redundant links, are catalogued. The spanning-tree algorithm then blocks forwarding on redundant links by setting up one preferred link between switches in

546-452: A client. A single server can serve multiple clients, and a single client can use multiple servers. A client process may run on the same device or may connect over a network to a server on a different device. Typical servers are database servers , file servers , mail servers , print servers , web servers , game servers , and application servers . Client–server systems are usually most frequently implemented by (and often identified with)

637-403: A computer program that turns a computer into a server, e.g. Windows service . Originally used as "servers serve users" (and "users use servers"), in the sense of "obey", today one often says that "servers serve data", in the same sense as "give". For instance, web servers "serve [up] web pages to users" or "service their requests". The server is part of the client–server model ; in this model,

728-415: A device used for (or a device dedicated to) running one or several server programs. On a network, such a device is called a host . In addition to server , the words serve and service (as verb and as noun respectively) are frequently used, though servicer and servant are not. The word service (noun) may refer to the abstract form of functionality, e.g. Web service . Alternatively, it may refer to

819-568: A geometric space such as the Euclidean plane . For such an input, a spanning tree is again a tree that has as its vertices the given points. The quality of the tree is measured in the same way as in a graph, using the Euclidean distance between pairs of points as the weight for each edge. Thus, for instance, a Euclidean minimum spanning tree is the same as a graph minimum spanning tree in a complete graph with Euclidean edge weights. However, it

910-595: A number of vendors who sold VLAN capable switches developed their own Spanning Tree Protocol versions that were VLAN capable. Cisco developed, implemented and published the Per-VLAN Spanning Tree ( PVST ) proprietary protocol using its own proprietary Inter-Switch Link (ISL) for VLAN encapsulation , and PVST+ which uses 802.1Q VLAN encapsulation. Both standards implement a separate spanning tree for every VLAN. Cisco switches now commonly implement PVST+ and can only implement Spanning Trees for VLANs if

1001-525: A port can be in has been reduced to three instead of STP's original five: RSTP operational details: STP and RSTP do not segregate switch ports by VLAN. However, in Ethernet switched environments where multiple VLANs exist, it is often desirable to create multiple spanning trees so that traffic on different VLANs uses different links. Before the IEEE published a Spanning Tree Protocol standard for VLANs,

SECTION 10

#1732779589534

1092-411: A server serves data for clients . The nature of communication between a client and server is request and response . This is in contrast with peer-to-peer model in which the relationship is on-demand reciprocation. In principle, any computerized process that can be used or called by another process (particularly remotely, particularly to share a resource) is a server, and the calling process or processes

1183-423: A service for the requester, which often runs on a computer other than the one on which the server runs. The average utilization of a server in the early 2000s was 5 to 15%, but with the adoption of virtualization this figure started to increase to reduce the number of servers needed. Strictly speaking, the term server refers to a computer program or process (running program). Through metonymy , it refers to

1274-431: A single logical entity. Such a multi-chassis link aggregation group works like a normal port trunk , only distributed through multiple switches. Conversely, partitioning technologies compartmentalize a single physical chassis into multiple logical entities. On the edge of the network, loop-detection is configured to prevent accidental loops by users. Spanning tree In the mathematical field of graph theory ,

1365-575: A spanning tree will create a cycle; such a cycle is called a fundamental cycle with respect to that tree. There is a distinct fundamental cycle for each edge not in the spanning tree; thus, there is a one-to-one correspondence between fundamental cycles and edges not in the spanning tree. For a connected graph with V vertices, any spanning tree will have V  − 1 edges, and thus, a graph of E edges and one of its spanning trees will have E  −  V  + 1 fundamental cycles (The number of edges subtracted by number of edges included in

1456-463: A spanning tree. A special kind of spanning tree, the Xuong tree , is used in topological graph theory to find graph embeddings with maximum genus . A Xuong tree is a spanning tree such that, in the remaining graph, the number of connected components with an odd number of edges is as small as possible. A Xuong tree and an associated maximum-genus embedding can be found in polynomial time . A tree

1547-407: A spanning tree; giving the number of edges not included in the spanning tree). For any given spanning tree the set of all E  −  V  + 1 fundamental cycles forms a cycle basis , i.e., a basis for the cycle space . Dual to the notion of a fundamental cycle is the notion of a fundamental cutset with respect to a given spanning tree. By deleting just one edge of the spanning tree,

1638-534: A special case of a class of spanning trees called Trémaux trees , named after the 19th-century discoverer of depth-first search. Spanning trees are important in parallel and distributed computing, as a way of maintaining communications between a set of processors; see for instance the Spanning Tree Protocol used by OSI link layer devices or the Shout (protocol) for distributed computing. However,

1729-508: A switch have the same priority, the port with the lowest number is chosen to forward frames. The root bridge of the spanning tree is the bridge with the smallest (lowest) bridge ID. Each bridge has a configurable priority number and a MAC address; the bridge ID is the concatenation of the bridge priority and the MAC address. For example, the ID of a bridge with priority 32,768 and MAC 0200.0000.1111

1820-445: A topology change, RSTP is typically able to respond to changes within 3 ×  hello times (default: 3 ×  2 seconds) or within a few milliseconds of a physical link failure. The hello time is an important and configurable time interval that is used by RSTP for several purposes; its default value is 2 seconds. RSTP adds new bridge port roles in order to speed convergence following a link failure: The number of switch port states

1911-505: A tree has a unique spanning tree and it is itself). Several pathfinding algorithms, including Dijkstra's algorithm and the A* search algorithm , internally build a spanning tree as an intermediate step in solving the problem. In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in

SECTION 20

#1732779589534

2002-422: Is 32768.0200.0000.1111 . The bridge priority default is 32,768 and can be configured only in multiples of 4096. When comparing two bridge IDs, the priority portions are compared first and the MAC addresses are compared only if the priorities are equal. The switch with the lowest priority of all the switches will be the root; if there is a tie, then the switch with the lowest priority and lowest MAC address will be

2093-426: Is a stack (in the case of depth-first search) or a queue (in the case of breadth-first search). In either case, one can form a spanning tree by connecting each vertex, other than the root vertex v , to the vertex from which it was discovered. This tree is known as a depth-first search tree or a breadth-first search tree according to the graph exploration algorithm used to construct it. Depth-first search trees are

2184-415: Is a connected undirected graph with no cycles . It is a spanning tree of a graph G if it spans G (that is, it includes every vertex of G ) and is a subgraph of G (every edge in the tree belongs to G ). A spanning tree of a connected graph G can also be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices. Adding just one edge to

2275-406: Is a client. Thus any general-purpose computer connected to a network can host servers. For example, if files on a device are shared by some process, that process is a file server . Similarly, web server software can run on any capable computer, and so a laptop or a personal computer can host a web server. While request–response is the most common client-server design, there are others, such as

2366-618: Is a collaborative effort, Open Compute Project around this concept. A class of small specialist servers called network appliances are generally at the low end of the scale, often being smaller than common desktop computers. A mobile server has a portable form factor, e.g. a laptop . In contrast to large data centers or rack servers, the mobile server is designed for on-the-road or ad hoc deployment into emergency, disaster or temporary environments where traditional servers are not feasible due to their power requirements, size, and deployment time. The main beneficiaries of so-called "server on

2457-419: Is a field inside a BPDU packet. It is eight bytes in length. The first two bytes are the bridge priority, an unsigned integer of 0–65,535. The last six bytes are a MAC address supplied by the bridge. Prior to IEEE 802.1D-2004, the first two bytes gave a 16-bit bridge priority. Since IEEE 802.1D-2004, the first four bits are a configurable priority, and the last twelve bits carry the bridge system ID extension. In

2548-427: Is also less of a concern, but power consumption and heat output can be a serious issue. Server rooms are equipped with air conditioning devices. A server farm or server cluster is a collection of computer servers maintained by an organization to supply server functionality far beyond the capability of a single device. Modern data centers are now often built of very large clusters of much simpler servers, and there

2639-457: Is an MST to which several VLANs are mapped, this group of VLANs is called MST instance (MSTI). CSTs are backward compatible with the STP and RSTP standard. A MST that has only one VLAN assigned to it is an internal spanning tree (IST). Unlike some proprietary per-VLAN spanning tree implementations, MSTP includes all of its spanning tree information in a single BPDU format. Not only does this reduce

2730-529: Is an acyclic subgraph of G in which every vertex other than v has outdegree 1. This definition is only satisfied when the "branches" of T point towards v . Server (computing) A server is a computer that provides information to other computers called " clients " on a computer network . This architecture is called the client–server model . Servers can provide various functionalities, often called "services", such as sharing data or resources among multiple clients or performing computations for

2821-405: Is contrasted with "user", distinguishing two types of host : "server-host" and "user-host". The use of "serving" also dates to early documents, such as RFC 4, contrasting "serving-host" with "using-host". The Jargon File defines server in the common sense of a process performing service for requests, usually remote, with the 1981 version reading: SERVER n. A kind of DAEMON which performs

Spanning Tree Protocol - Misplaced Pages Continue

2912-503: Is easy to calculate t ( G ) directly: More generally, for any graph G , the number t ( G ) can be calculated in polynomial time as the determinant of a matrix derived from the graph, using Kirchhoff's matrix-tree theorem . Specifically, to compute t ( G ), one constructs the Laplacian matrix of the graph, a square matrix in which the rows and columns are both indexed by the vertices of G . The entry in row i and column j

3003-409: Is more than one link between two switches, the STP root bridge calculates the cost of each path based on bandwidth. STP will select the path with the lowest cost, that is the highest bandwidth, as the preferred link. STP will enable this preferred link as the only path to be used for Ethernet frames between the two switches, and disable all other possible links by designating the switch ports that connect

3094-472: Is not necessary to construct this graph in order to solve the optimization problem; the Euclidean minimum spanning tree problem, for instance, can be solved more efficiently in O ( n  log  n ) time by constructing the Delaunay triangulation and then applying a linear time planar graph minimum spanning tree algorithm to the resulting triangulation. A spanning tree chosen randomly from among all

3185-427: Is one of the few exceptions. A single spanning tree of a graph can be found in linear time by either depth-first search or breadth-first search . Both of these algorithms explore the given graph, starting from an arbitrary vertex v , by looping through the neighbors of the vertices they discover and adding each unexplored neighbor to a data structure to be explored later. They differ in whether this data structure

3276-497: Is one of three values: The resulting matrix is singular , so its determinant is zero. However, deleting the row and column for an arbitrarily chosen vertex leads to a smaller matrix whose determinant is exactly  t ( G ). If G is a graph or multigraph and e is an arbitrary edge of G , then the number t ( G ) of spanning trees of G satisfies the deletion-contraction recurrence t ( G ) =  t ( G  −  e ) +  t ( G / e ), where G  −  e

3367-615: Is still in use today, in most modern networks its primary use is as a loop-protection mechanism rather than a fault tolerance mechanism. Link aggregation protocols such as LACP will bond two or more links to provide fault tolerance while simultaneously increasing overall link capacity. The need for the Spanning Tree Protocol (STP) arose because switches in local area networks (LANs) are often interconnected using redundant links to improve resilience should one connection fail. However, this connection configuration creates

3458-448: Is the multigraph obtained by deleting e and G / e is the contraction of G by e . The term t ( G  −  e ) in this formula counts the spanning trees of  G that do not use edge  e , and the term t ( G / e ) counts the spanning trees of  G that use  e . In this formula, if the given graph G is a multigraph , or if a contraction causes two vertices to be connected to each other by multiple edges, then

3549-579: The IEEE introduced Rapid Spanning Tree Protocol ( RSTP ) as 802.1w. RSTP provides significantly faster recovery in response to network changes or failures, introducing new convergence behaviors and bridge port roles to do this. RSTP was designed to be backwards-compatible with standard STP. STP was originally standardized as IEEE 802.1D but the functionality of spanning tree (802.1D), rapid spanning tree (802.1w), and multiple spanning tree (802.1s) has since been incorporated into IEEE 802.1Q-2014 . While STP

3640-448: The IEEE introduced Rapid Spanning Tree Protocol (RSTP) as IEEE 802.1w . RSTP was then incorporated into IEEE 802.1D-2004 making the original STP standard obsolete. RSTP was designed to be backward-compatible with standard STP. RSTP provides significantly faster spanning tree convergence after a topology change, introducing new convergence behaviors and bridge port roles to accomplish this. While STP can take 30 to 50 seconds to respond to

3731-704: The Internet is based upon a client–server model. High-level root nameservers , DNS , and routers direct the traffic on the internet. There are millions of servers connected to the Internet, running continuously throughout the world and virtually every action taken by an ordinary Internet user requires one or more interactions with one or more servers. There are exceptions that do not use dedicated servers; for example, peer-to-peer file sharing and some implementations of telephony (e.g. pre-Microsoft Skype ). Hardware requirement for servers vary widely, depending on

Spanning Tree Protocol - Misplaced Pages Continue

3822-409: The publish–subscribe pattern . In the publish-subscribe pattern, clients register with a pub-sub server, subscribing to specified types of messages; this initial registration may be done by request-response. Thereafter, the pub-sub server forwards matching messages to the clients without any further requests: the server pushes messages to the client, rather than the client pulling messages from

3913-514: The request–response model: a client sends a request to the server, which performs some action and sends a response back to the client, typically with a result or acknowledgment. Designating a computer as "server-class hardware" implies that it is specialized for running servers on it. This often implies that it is more powerful and reliable than standard personal computers , but alternatively, large computing clusters may be composed of many relatively simple, replaceable server components. The use of

4004-571: The IEEE and the DEC versions of the Spanning Tree Protocol, but their interworking can create issues for the network administrator. Different implementations of a standard are not guaranteed to interoperate , due for example to differences in default timer settings. The IEEE encourages vendors to provide a Protocol Implementation Conformance Statement , declaring which capabilities and options have been implemented, to help users determine whether different implementations will interoperate correctly. In 2001,

4095-847: The Internet, the dominant operating systems among servers are UNIX-like open-source distributions , such as those based on Linux and FreeBSD , with Windows Server also having a significant share. Proprietary operating systems such as z/OS and macOS Server are also deployed, but in much smaller numbers. Servers that run Linux are commonly used as Webservers or Databanks. Windows Servers are used for Networks that are made out of Windows Clients. Specialist server-oriented operating systems have traditionally had features such as: In practice, today many desktop and server operating systems share similar code bases , differing mostly in configuration. In 2010, data centers (servers, cooling, and other electrical infrastructure) were responsible for 1.1–1.5% of electrical energy consumption worldwide and 1.7–2.2% in

4186-501: The LAN and the same version of STP chosen on each. The administrator may determine which switch will be the root bridge and configure the switches appropriately. If the root bridge goes down, the protocol will automatically assign a new root bridge based on bridge ID. If all switches have the same bridge ID, such as the default ID, and the root bridge goes down, a tie situation arises and the protocol will assign one switch as root bridge based on

4277-429: The LAN where STP is enabled are categorized. When a device is first attached to a switch port, it will not immediately start to forward data. It will instead go through a number of states while it processes BPDUs and determines the topology of the network. The port attached to a host such as a computer, printer or server always goes into the forwarding state, albeit after a delay of about 30 seconds while it goes through

4368-472: The LAN. This preferred link is used for all Ethernet frames unless it fails, in which case a non-preferred redundant link is enabled. When implemented in a network, STP designates one layer-2 switch as root bridge . All switches then select their best connection towards the root bridge for forwarding and block other redundant links. All switches constantly communicate with their neighbors in the LAN using § Bridge protocol data units (BPDUs). Provided there

4459-666: The RSTP protocol as its core spanning-tree protocol, but usage of STP can be forced if the network includes old bridges. More information about configuring VSTP on Juniper Networks switches was published in the official documentation. Cisco also published a proprietary version of Rapid Spanning Tree Protocol. It creates a spanning tree for each VLAN, just like PVST. Cisco refers to this as Rapid Per-VLAN Spanning Tree ( RPVST ). The Multiple Spanning Tree Protocol (MSTP), originally defined in IEEE 802.1s -2002 and later merged into IEEE 802.1Q -2005, defines an extension to RSTP to further develop

4550-599: The United States. One estimate is that total energy consumption for information and communications technology saves more than 5 times its carbon footprint in the rest of the economy by increasing efficiency. Global energy consumption is increasing due to the increasing demand of data and bandwidth. Natural Resources Defense Council (NRDC) states that data centers used 91 billion kilowatt hours (kWh) electrical energy in 2013 which accounts to 3% of global electricity usage. Environmental groups have placed focus on

4641-547: The VLAN with ID 1. PVST+ can tunnel across an MSTP Region. The switch vendor Juniper Networks in turn developed and implemented its VLAN Spanning Tree Protocol (VSTP) to provide compatibility with Cisco's PVST, so that the switches from both vendors can be included in one LAN. The VSTP protocol is only supported by the EX and MX Series from Juniper Networks. There are two restrictions to the compatibility of VSTP: By default, VSTP uses

SECTION 50

#1732779589534

4732-430: The base, and fundamental cutsets are defined in the same way from the dual matroid . A collection of disjoint (unconnected) trees is described as a forest . A spanning forest in a graph is a subgraph that is a forest with an additional requirement. There are two incompatible requirements in use, of which one is relatively rare. To avoid confusion between these two definitions, Gross & Yellen (2005) suggest

4823-592: The case of MST, the bridge system ID extension carries the MSTP instance number. Some vendors set the bridge system ID extension to carry a VLAN ID allowing a different spanning tree per VLAN, such as Cisco's PVST . Spanning tree is an older protocol with a longer convergence time. Improper use or implementation can contribute to network disruptions. Blocking links is a crude approach to high availability and preventing loops. Modern networks can make use of all connected links by use of protocols that inhibit, control or suppress

4914-399: The cost of its own path to the cost received from the neighboring switches to determine the total cost of a given path to the root bridge. Once the cost of all possible paths to the root bridge have been added up, each switch assigns a port as root port which connects to the path with the lowest cost, or highest bandwidth, that will eventually lead to the root bridge. The STP path cost default

5005-480: The depth-first and breadth-first methods for constructing spanning trees on sequential computers are not well suited for parallel and distributed computers. Instead, researchers have devised several more specialized algorithms for finding spanning trees in these models of computation. In certain fields of graph theory it is often useful to find a minimum spanning tree of a weighted graph . Other optimization problems on spanning trees have also been studied, including

5096-475: The edge of an MSTP region connected to either an RSTP or STP bridge or an endpoint are known as boundary ports. As in RSTP, these ports can be configured as edge ports to facilitate rapid changes to the forwarding state when connected to endpoints. IEEE 802.1aq, also known as Shortest Path Bridging (SPB), allows redundant links between switches to be active through multiple equal cost paths, and provides much larger layer-2 topologies, faster convergence, and improves

5187-429: The edges of the graph are assigned random weights and then the minimum spanning tree of the weighted graph is constructed. Because a graph may have exponentially many spanning trees, it is not possible to list them all in polynomial time . However, algorithms are known for listing all spanning trees in polynomial time per tree. Every finite connected graph has a spanning tree. However, for infinite connected graphs,

5278-527: The existence of spanning trees is equivalent to the axiom of choice . An infinite graph is connected if each pair of its vertices forms the pair of endpoints of a finite path. As with finite graphs, a tree is a connected graph with no finite cycles, and a spanning tree can be defined either as a maximal acyclic set of edges or as a tree that contains every vertex. The trees within a graph may be partially ordered by their subgraph relation, and any infinite chain in this partial order has an upper bound (the union of

5369-614: The forwarding state during these situations. There are two types of BPDUs in the original STP specification (802.1D) (the Rapid Spanning Tree (RSTP) extension uses a specific RSTP BPDU). IEEE 802.1D and IEEE 802.1aq BPDUs have the following format: Topology change notification (TCN) BPDU, used to announce changes in the network topology, such as port up or port down. Configuration BPDU (CBPDU), used for spanning tree computation and sent by root bridges to provide information to all switches. The first spanning tree protocol

5460-411: The go" technology include network managers, software or database developers, training centers, military personnel, law enforcement, forensics, emergency relief groups, and service organizations. To facilitate portability, features such as the keyboard , display , battery ( uninterruptible power supply , to provide power redundancy in case of failure), and mouse are all integrated into the chassis. On

5551-436: The listening and learning states. The time spent in the listening and learning states is determined by a value known as the forward delay (default 15 seconds and set by the root bridge). If another switch is connected, the port may remain in blocking mode if it is determined that it would cause a loop in the network. Topology change notification (TCN) BPDUs are used to inform other switches of port changes. TCNs are injected into

SECTION 60

#1732779589534

5642-500: The maximum spanning tree, the minimum tree that spans at least k vertices, the spanning tree with the fewest edges per vertex , the spanning tree with the largest number of leaves , the spanning tree with the fewest leaves (closely related to the Hamiltonian path problem ), the minimum diameter spanning tree, and the minimum dilation spanning tree. Optimal spanning tree problems have also been studied for finite sets of points in

5733-622: The natural behavior of logical or physical topology loops. Newer, more robust protocols include the TRILL (Transparent Interconnection of Lots of Links) protocol, also created by Perlman, and Shortest Path Bridging from the IEEE. Configuring connections between network equipment as layer-3 IP links and relying on IP routing for resiliency and to prevent loops is a popular alternative. Switch virtualization techniques like Cisco Virtual Switching System and Virtual PortChannel and HP Intelligent Resilient Framework combine multiple switches into

5824-411: The neighboring bridge is in the same MST region as itself. MSTP is fully compatible with RSTP bridges in that an MSTP BPDU can be interpreted by an RSTP bridge as an RSTP BPDU. This not only allows compatibility with RSTP bridges without configuration changes but also causes any RSTP bridges outside of an MSTP region to see the region as a single RSTP bridge regardless of the number of MSTP bridges inside

5915-465: The network by a non-root switch and propagated to the root. Upon receipt of the TCN, the root switch will set the topology change flag in its normal BPDUs. This flag is propagated to all other switches and instructs them to rapidly age out their forwarding table entries. Before configuring STP, the network topology should be carefully planned. Basic configuration requires that STP be enabled on all switches in

6006-424: The number of BPDUs required to communicate spanning tree information for each VLAN, but it also ensures backward compatibility with RSTP and, in effect, classic STP too. MSTP does this by encoding an additional region of information after the standard RSTP BPDU as well as a number of MSTI messages (from 0 to 64 instances, although in practice many bridges support fewer). Each of these MSTI configuration messages conveys

6097-426: The other switches in the LAN implement the same VLAN STP protocol. HP provides PVST and PVST+ compatibility in some of its network switches. Some devices from Force10 Networks , Alcatel-Lucent , Extreme Networks , Avaya , Brocade Communications Systems and BLADE Network Technologies support PVST+. Extreme Networks does so with two limitations: Lack of support on ports where the VLAN is untagged/native, and also on

6188-467: The preferred path as root port . After STP enabled switches in a LAN have elected the root bridge, all non-root bridges assign one of their ports as root port. This is either the port that connects the switch to the root bridge, or if there are several paths, the port with the preferred path as calculated by the root bridge. Because not all switches are directly connected to the root bridge they communicate amongst each other using STP BPDUs. Each switch adds

6279-430: The preferred path by configuring the port cost; the lower the port cost the more likely it is that the protocol will choose the connected link as root port for the preferred path. The selection of how other switches in the topology choose their root port, or the least cost path to the root bridge, can be influenced by the port priority. The highest priority will mean the path will ultimately be less preferred. If all ports of

6370-483: The process of finding the minimum spanning tree . The Internet and many other telecommunications networks have transmission links that connect nodes together in a mesh topology that includes some loops. In order to avoid bridge loops and routing loops , many routing protocols designed for such networks—including the Spanning Tree Protocol , Open Shortest Path First , Link-state routing protocol , Augmented tree-based routing , etc.—require each router to remember

6461-401: The redundant edges should not be removed, as that would lead to the wrong total. For instance a bond graph connecting two vertices by k edges has k different spanning trees, each consisting of a single one of these edges. The Tutte polynomial of a graph can be defined as a sum, over the spanning trees of the graph, of terms computed from the "internal activity" and "external activity" of

6552-477: The region itself. In order to further facilitate this view of an MSTP region as a single RSTP bridge, the MSTP protocol uses a variable known as remaining hops as a time to live counter instead of the message age timer used by RSTP. The message age time is only incremented once when spanning-tree information enters an MST region, and therefore RSTP bridges will see a region as only one hop in the spanning tree. Ports at

6643-492: The root) is: The above rules describe one way of determining what spanning tree will be computed by the algorithm, but the rules as written require knowledge of the entire network. The bridges have to determine the root bridge and compute the port roles (root, designated, or blocked) with only the information that they have. To ensure that each bridge has enough information, the bridges use special data frames called bridge protocol data units (BPDUs) to exchange information about

6734-404: The root. For example, if switches A (MAC = 0200.0000.1111 ) and B (MAC = 0200.0000.2222 ) both have a priority of 32,768 then switch A will be selected as the root bridge. If the network administrators would like switch B to become the root bridge, they must set its priority to be less than 32,768. The sequence of events to determine the best received BPDU (which is the best path to

6825-564: The running server without shutting it down, and to guard against overheating, servers might have more powerful fans or use water cooling . They will often be able to be configured, powered up and down, or rebooted remotely, using out-of-band management , typically based on IPMI . Server casings are usually flat and wide , and designed to be rack-mounted, either on 19-inch racks or on Open Racks . These types of servers are often housed in dedicated data centers . These will normally have very stable power and Internet and increased security. Noise

6916-411: The server as in request-response. The role of a server is to share data as well as to share resources and distribute work. A server computer can serve its own computer programs as well; depending on the scenario, this could be part of a quid pro quo transaction, or simply a technical possibility. The following table shows several scenarios in which a server is used. Almost the entire structure of

7007-412: The server's purpose and its software. Servers often are more powerful and expensive than the clients that connect to them. The name server is used both for the hardware and software pieces. For the hardware servers, it is usually limited to mean the high-end machines although software servers can run on a variety of hardwares. Since servers are usually accessed over a network, many run unattended without

7098-425: The spanning tree can only appear in the cutsets of the other edges in the cycle; and vice versa : edges in a cutset can only appear in those cycles containing the edge corresponding to the cutset. This duality can also be expressed using the theory of matroids , according to which a spanning tree is a base of the graphic matroid , a fundamental cycle is the unique circuit within the set formed by adding one element to

7189-609: The spanning tree information for each instance. Each instance can be assigned a number of configured VLANs and frames assigned to these VLANs operate in this spanning tree instance whenever they are inside the MST region. In order to avoid conveying their entire VLAN to spanning tree mapping in each BPDU, bridges encode an MD5 digest of their VLAN to instance table in the MSTP BPDU. This digest is then used by other MSTP bridges, along with other administratively configured values, to determine if

7280-399: The spanning tree protocol, bridge IDs, and root path costs. BPDUs are exchanged regularly (every 2 seconds by default) and enable switches to keep track of network changes and to start and stop forwarding at ports as required. To prevent the delay when connecting hosts to a switch and during some topology changes, Rapid STP was developed, which allows a switch port to rapidly transition into

7371-399: The spanning trees with equal probability is called a uniform spanning tree . Wilson's algorithm can be used to generate uniform spanning trees in polynomial time by a process of taking a random walk on the given graph and erasing the cycles created by this walk. An alternative model for generating spanning trees randomly but not uniformly is the random minimal spanning tree . In this model,

7462-417: The switch MAC addresses. Once the switches have been assigned a bridge ID and the protocol has chosen the root bridge switch, the best path to the root bridge is calculated based on port cost, path cost and port priority. Ultimately STP calculates the path cost on the basis of the bandwidth of a link, however links between switches may have the same bandwidth. Administrators can influence the protocol's choice of

7553-417: The term "full spanning forest" for a spanning forest with the same number of components as the given graph (i.e., a maximal forest), while Bondy & Murty (2008) instead call this kind of forest a "maximal spanning forest" (which is redundant, as a maximal forest necessarily contains every vertex). The number t ( G ) of spanning trees of a connected graph is a well-studied invariant . In some cases, it

7644-495: The tree. Its value at the arguments (1,1) is the number of spanning trees or, in a disconnected graph, the number of maximal spanning forests. The Tutte polynomial can also be computed using a deletion-contraction recurrence, but its computational complexity is high: for many values of its arguments, computing it exactly is #P-complete , and it is also hard to approximate with a guaranteed approximation ratio . The point (1,1), at which it can be evaluated using Kirchhoff's theorem,

7735-408: The trees in the chain). Zorn's lemma , one of many equivalent statements to the axiom of choice, requires that a partial order in which all chains are upper bounded have a maximal element; in the partial order on the trees of the graph, this maximal element must be a spanning tree. Therefore, if Zorn's lemma is assumed, every infinite connected graph has a spanning tree. In the other direction, given

7826-437: The use of the mesh topologies through increased bandwidth between all devices by allowing traffic to load share across all paths on a mesh network. SPB consolidates multiple existing functionalities, including Spanning Tree Protocol (STP), Multiple Spanning Tree Protocol (MSTP), Rapid Spanning Tree Protocol (RSTP), Link aggregation, and Multiple MAC Registration Protocol (MMRP) into a one link state protocol. The bridge ID (BID)

7917-433: The usefulness of VLANs. In the standard, a spanning tree that maps one or more VLANs is called a multiple spanning tree (MST). Under MSTP, a spanning tree can be defined for individual VLANs or for groups of VLANs. Furthermore, the administrator can define alternate paths within a spanning tree. Switches are first assigned to an MST region, then VLANs are mapped against or assigned to this MST. A common spanning tree (CST)

8008-416: The vertices are partitioned into two disjoint sets. The fundamental cutset is defined as the set of edges that must be removed from the graph G to accomplish the same partition. Thus, each spanning tree defines a set of V  − 1 fundamental cutsets, one for each edge of the spanning tree. The duality between fundamental cutsets and fundamental cycles is established by noting that cycle edges not in

8099-574: The word server in computing comes from queueing theory , where it dates to the mid 20th century, being notably used in Kendall (1953) (along with "service"), the paper that introduced Kendall's notation . In earlier papers, such as the Erlang (1909) , more concrete terms such as "[telephone] operators" are used. In computing, "server" dates at least to RFC 5 (1969), one of the earliest documents describing ARPANET (the predecessor of Internet ), and

8190-562: Was invented in 1985 at the Digital Equipment Corporation by Radia Perlman . In 1990, the IEEE published the first standard for the protocol as 802.1D, based on the algorithm designed by Perlman. Subsequent versions were published in 1998 and 2004, incorporating various extensions. The original Perlman-inspired Spanning Tree Protocol, called DEC STP, is not a standard and differs from the IEEE version in message format as well as timer settings. Some bridges implement both

8281-427: Was originally calculated by the formula ⁠ 1 Gbit/s / bandwidth ⁠ . When faster speeds became available, the default values were adjusted as otherwise speeds above 1 Gbit/s would have been indistinguishable by STP. Its successor RSTP uses a similar formula with a larger numerator: ⁠ 20 Tbit/s / bandwidth ⁠ . These formulas lead to the sample values in the table. All switch ports in

#533466