Try   HackMD

802.1D - Spanning Tree Algorithm

課程影片

第 4G 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 7

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

第 4H 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 8

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

三個任務

  1. 任務一：找出 root bridge：也就是找到 BID 最低的 bridge
  2. 任務二：找到自己的 root port。
  3. 任務三：幫一個 LAN 找到 designated port。

這三個任務未必是依照 1~3 的順序決定的。

情報交換的單位 –- BPDU

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

net/bridge/br_private_stp.h 中：

struct br_config_bpdu {
	unsigned int	topology_change:1;
	unsigned int	topology_change_ack:1;
	bridge_id	root;
	int		root_path_cost;
	bridge_id	bridge_id;
	port_id		port_id;
	int		message_age;
	int		max_age;
	int		hello_time;
	int		forward_delay;
};

兩者之間欄位可以由 br_record_config_information() 得知：

static void br_record_config_information(struct net_bridge_port *p,
					 const struct br_config_bpdu *bpdu)
{
	p->designated_root = bpdu->root;
	p->designated_cost = bpdu->root_path_cost;
	p->designated_bridge = bpdu->bridge_id;
	p->designated_port = bpdu->port_id;
	p->designated_age = jiffies - bpdu->message_age;

	mod_timer(&p->message_age_timer, jiffies
		  + (bpdu->max_age - bpdu->message_age));
}

bridge_id –- 自己的 BID

誰發出這個 BPDU。

root –- 發送者認為的 Root BID

也就是發送者目前看過「最小」的 BID。

root_path_cost –- 自己到 Root 的成本

這個 BPDU 中所記錄的的 bridge_id 到所記錄的 root 所需要的成本。

Port 的資料結構 –- struct net_bridge_port

struct net_bridge_port {
	struct net_bridge		*br;
    ...
	/* STP */
	u8				priority;
	u8				state;
	u16				port_no;
	unsigned char			topology_change_ack;
	unsigned char			config_pending;
	port_id				port_id;
	port_id				designated_port;
	bridge_id			designated_root;
	bridge_id			designated_bridge;
	u32				path_cost;
	u32				designated_cost;
	unsigned long			designated_age;
    ...
}

每個 port 中，都會紀錄「這個 port 認為的 root bridge」是誰，以及到這個 root bridge 的成本。最後，還有這個 port 認為的 designated port 是誰。這些成員分別是：

path_cost –- Port 的成本

這就是計算 root_path_cost 時，經過這個端口要加上的那個成本。

designated_root –- 目前看過最小的 BID

這個 port 收到的所以 BPDU 中，出現過的最小的 BID。所以可以想像如果一個 port 的 designated_root 被更新，下一步就是拿回去跟 bridge 目前已知的 root bridge 做比較。

designated_cost –- Port 到 Root Bridge 的最小成本

從這個 port 出發到 root bridge 所需要的最小成本。所以所有的 port 中，具有最小 designated_cost 的那個 port 就會變 root port。

designated_bridge 與 designated_port –- 目前的 Designated Port

designated_bridge 與 designated_port 這兩個成員指得是「目前找到的 designated port 是哪一個 bridge 的哪個 port」。因為 一個 BPDU 會紀錄這個 BPDU 從哪個 Bridge 的哪個 Port 發出，而一個 Port 如果要收到一個 BPDU，就要跟發出 BPDU 的那個 Port 處於同一個 LAN 上。所以藉由比較這個 BPDU 上的 root_path_cost ，就可以知道自己是否要從 designated port 「退位」，讓給那個發出 BPDU 的 port。

因此，對於一個 designated port，看看他的 designated_bridge 與 designated_port 是否恰好就是「自己所屬的 bridge」與「自己的 port ID」，就可以確認自己是不是 designated port。而這也可以在 br_is_designated_port() 的實作中看到：

static inline int br_is_designated_port(const struct net_bridge_port *p)
{
	return !memcmp(&p->designated_bridge, &p->br->bridge_id, 8) &&
		(p->designated_port == p->port_id);
}

觀察：從眾多 Port 中挑出 Root Port

這時可以觀察到：一個 bridge 中的所有 port 中：

  1. 具有最小 designated_root 的那個 port，就會是 root port。
  2. 如果這樣的 port 有很多個，具有最小 designated_cost 的 port 就會是 root port。
  3. 如果這樣的 port 還是有很多個，那麼具有最小 port_id 的，就會是 root port。

Bridge 的資料結構 –- struct net_bridge

每個 bridge 也會維持自己的資料結構。在 net/bridge/br_private.h 中。其中，跟 STP 有關的部分：

struct net_bridge {
    ...
	/* STP */
	bridge_id			designated_root;
	bridge_id			bridge_id;
	unsigned char			topology_change;
	unsigned char			topology_change_detected;
	u16				root_port;
	unsigned long			max_age;
	unsigned long			hello_time;
	unsigned long			forward_delay;
	unsigned long			ageing_time;
	unsigned long			bridge_max_age;
	unsigned long			bridge_hello_time;
	unsigned long			bridge_forward_delay;
	unsigned long			bridge_ageing_time;
	u32				root_path_cost;

	u8				group_addr[ETH_ALEN];

	enum {
		BR_NO_STP, 		/* no spanning tree */
		BR_KERNEL_STP,		/* old STP in kernel */
		BR_USER_STP,		/* new RSTP in userspace */
	} stp_enabled;
    ...

designated_root –- Root Bridge 的 BID

root_port –- 自己的哪個 Port 是 Root Port？

收到 BPDU 時：由 Port 到 Bridge 往上更新

首先，每個 bridge 都往自己的所有端口廣播「Root BID 為自己 BUD」 BPDU，接著開始接收旁邊廣播來的 BPDU。接下來每收到一個 BPDU，就依照現在大家正在「尋找 Root Bridge」「決定 Root Port」「決定 Designated Port」的哪個階段，來決定收到 BPDU 時該做什麼反應。：

void br_received_config_bpdu(struct net_bridge_port *p,
			     const struct br_config_bpdu *bpdu)
{
	struct net_bridge *br;
	int was_root;

	p->stp_xstats.rx_bpdu++;

	br = p->br;
	was_root = br_is_root_bridge(br);

	if (br_supersedes_port_info(p, bpdu)) {
		br_record_config_information(p, bpdu);
		br_configuration_update(br);
		br_port_state_selection(br);

		if (!br_is_root_bridge(br) && was_root) {
			del_timer(&br->hello_timer);
			if (br->topology_change_detected) {
				del_timer(&br->topology_change_timer);
				br_transmit_tcn(br);

				mod_timer(&br->tcn_timer,
					  jiffies + br->bridge_hello_time);
			}
		}

		if (p->port_no == br->root_port) {
			br_record_config_timeout_values(br, bpdu);
			br_config_bpdu_generation(br);
			if (bpdu->topology_change_ack)
				br_topology_change_acknowledged(br);
		}
	} else if (br_is_designated_port(p)) {
		br_reply(p);
	}
}

這是第一次廣播之後開始發生的事情，所以這是最先發生的。如果現在大家正在決定哪一個 bridge 是 root bridge，或者是說大家正在找「哪個 bridge 有最小的 BID」，那麼就會發生以下的事情：

第一關：每個 Port 看看自己有沒有收到有用的情報？

首先，拿到 BPDU 時，會先看看上面是不是個更好的情報來源。這個「更好」包含：

  1. BPDU 上面記錄的 root bridge（BPDU 的 root 成員）是否比自己現在認為的 root（port 自己的 designated_root 成員）還要小。
  2. BPDU 上面記錄的 root BID 相同，但是上面的 root_path_cost 更小。

這個比較發生在 br_supersedes_port_info() 中：

static int br_supersedes_port_info(const struct net_bridge_port *p,
				   const struct br_config_bpdu *bpdu)
{
	int t;

	t = memcmp(&bpdu->root, &p->designated_root, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (bpdu->root_path_cost < p->designated_cost)
		return 1;
	else if (bpdu->root_path_cost > p->designated_cost)
		return 0;

	t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
		return 1;

	if (bpdu->port_id <= p->designated_port)
		return 1;

	return 0;
}

第二關：Port 先把最好的情報收起來

如果發現 BPDU 上面記錄著更好的路徑（也就是上面這個函式回傳 1 時），那麼就把這個 BPDU 上面的資訊更新到這個 port 上，並且叫 bridge 更新自己的 root port。其中，「把 BPDU 更新到 port 上」是由 br_record_config_information() 來做：

static void br_record_config_information(struct net_bridge_port *p,
					 const struct br_config_bpdu *bpdu)
{
	p->designated_root = bpdu->root;
	p->designated_cost = bpdu->root_path_cost;
	p->designated_bridge = bpdu->bridge_id;
	p->designated_port = bpdu->port_id;
	p->designated_age = jiffies - bpdu->message_age;

	mod_timer(&p->message_age_timer, jiffies
		  + (bpdu->max_age - bpdu->message_age));
}

其中，一個 port 的 designated_* 成員，指得是：如果指定從這個 port 送封包給這個 port 所認為的 root，那麼 root_path_cost 是多少？以及這個風包送出去之後，第一個會送給哪個 bridge 的哪個 port？等等。

而更新到 port 上之後，就再看看現在這個 bridge 上的所有 port 中，會不會有更適合的 port 能夠當 root port 或 designted port。這個也就是接下來的 br_configuration_update() 要做的事：

void br_configuration_update(struct net_bridge *br)
{
	br_root_selection(br);
	br_designated_port_selection(br);
}

第三關：從所以 Port 的情報中找出「最好中的最好」的情報

看這個 Port 會不會成為 Root Port –- br_root_selection()

其中，br_root_select() 做的事情就是把 bridge 上的每個 root port 看一遍，看看有哪個比現在的 root port 更好。如果沒有 root port，就表示現在這個 bridge 是 root bridge，所以就把自己變成 root bridge; 反之，就把 bridge 的 root port 設定成剛剛找到的那個 root port：

static void br_root_selection(struct net_bridge *br)
{
	struct net_bridge_port *p;
	u16 root_port = 0;

	list_for_each_entry(p, &br->port_list, list) {
		if (!br_should_become_root_port(p, root_port))
			continue;

		if (p->flags & BR_ROOT_BLOCK)
			br_root_port_block(br, p);
		else
			root_port = p->port_no;
	}

	br->root_port = root_port;

	if (!root_port) {
		br->designated_root = br->bridge_id;
		br->root_path_cost = 0;
	} else {
		p = br_get_port(br, root_port);
		br->designated_root = p->designated_root;
		br->root_path_cost = p->designated_cost + p->path_cost;
	}
}

而從眾多 port 中挑出 root port 的標準，就是看每個 port 的 designated_* 成員。「以一個 port 為出發點，可以走到的最佳路徑」。如果發現從某一個 port 出發到 root 的路徑比現在 bridge 上的路徑更好，那就表示這個 port 應該要成為新的 root port，所以就回傳 1：

static int br_should_become_root_port(const struct net_bridge_port *p,
				      u16 root_port)
{
	struct net_bridge *br;
	struct net_bridge_port *rp;
	int t;

	br = p->br;
	if (p->state == BR_STATE_DISABLED ||
	    br_is_designated_port(p))
		return 0;

	if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
		return 0;

	if (!root_port)
		return 1;

	rp = br_get_port(br, root_port);

	t = memcmp(&p->designated_root, &rp->designated_root, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (p->designated_cost + p->path_cost <
	    rp->designated_cost + rp->path_cost)
		return 1;
	else if (p->designated_cost + p->path_cost >
		 rp->designated_cost + rp->path_cost)
		return 0;

	t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (p->designated_port < rp->designated_port)
		return 1;
	else if (p->designated_port > rp->designated_port)
		return 0;

	if (p->port_id < rp->port_id)
		return 1;

	return 0;
}
  1. 拿到 BPDU 時，看看這個 BPDU 是哪個端口來的。
  2. 檢查「BPDU 上的 root_path_cost」加上「收到端口的成本」，看看跟目前的 root_path_cost 比起來是否更低。如果成本更低，就 root port 更新成現在這個端口。

看看這個 Port 會不會變成 Designated Port –- br_designated_port_selection()

static void br_designated_port_selection(struct net_bridge *br)
{
	struct net_bridge_port *p;

	list_for_each_entry(p, &br->port_list, list) {
		if (p->state != BR_STATE_DISABLED &&
		    br_should_become_designated_port(p))
			br_become_designated_port(p);

	}
}

LAN 上的所有 port 會聽到所有其他 port 送出的 BPDU。如果發現這個「目前聽到所有其他 port 的最小 root_path_cost」比「經過自己會有的 root_path_cost」還要小，那這個 port 就有資格成為 designated port：

static int br_should_become_designated_port(const struct net_bridge_port *p)
{
	struct net_bridge *br;
	int t;

	br = p->br;
	if (br_is_designated_port(p))
		return 1;

	if (memcmp(&p->designated_root, &br->designated_root, 8))
		return 1;

	if (br->root_path_cost < p->designated_cost)
		return 1;
	else if (br->root_path_cost > p->designated_cost)
		return 0;

	t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (p->port_id < p->designated_port)
		return 1;

	return 0;
}

而「成為 designated port」的意思就是「把自己到 root bridge 的成本，從『打聽到的最小值』變成『走自己的 bridge 的成本』」：

void br_become_designated_port(struct net_bridge_port *p)
{
	struct net_bridge *br;

	br = p->br;
	p->designated_root = br->designated_root;
	p->designated_cost = br->root_path_cost;
	p->designated_bridge = br->bridge_id;
	p->designated_port = p->port_id;
}

第四階段：昭告天下

void br_config_bpdu_generation(struct net_bridge *br)
{
	struct net_bridge_port *p;

	list_for_each_entry(p, &br->port_list, list) {
		if (p->state != BR_STATE_DISABLED &&
		    br_is_designated_port(p))
			br_transmit_config(p);
	}
}

在這個過程中，只有 root port 的 BPDU 能夠暢行無阻地一路被所有 Bridge 「複誦」過去。

void br_become_root_bridge(struct net_bridge *br)
{
	br->max_age = br->bridge_max_age;
	br->hello_time = br->bridge_hello_time;
	br->forward_delay = br->bridge_forward_delay;
	br_topology_change_detection(br);
	del_timer(&br->tcn_timer);

	if (br->dev->flags & IFF_UP) {
		br_config_bpdu_generation(br);
		mod_timer(&br->hello_timer, jiffies + br->hello_time);
	}
}

static inline int br_is_root_bridge(const struct net_bridge *br)
{
	return !memcmp(&br->bridge_id, &br->designated_root, 8);
}

任務二：檢查 Root Port 需不需要改變？

如果現在是「所有人正在決定自己的哪個 port 要當 root port」，那麼拿到 BPDU 時，會發生下面的事：

  1. 把帶有新的 root_path_cost 的 BPDU 廣播出去。

把新的 BPDU 廣播出去時，其它收到的 bridge 就繼續做上面這些事。

static int br_should_become_root_port(const struct net_bridge_port *p,
				      u16 root_port)
{
	struct net_bridge *br;
	struct net_bridge_port *rp;
	int t;

	br = p->br;
	if (p->state == BR_STATE_DISABLED ||
	    br_is_designated_port(p))
		return 0;

	if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
		return 0;

	if (!root_port)
		return 1;

	rp = br_get_port(br, root_port);

	t = memcmp(&p->designated_root, &rp->designated_root, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (p->designated_cost + p->path_cost <
	    rp->designated_cost + rp->path_cost)
		return 1;
	else if (p->designated_cost + p->path_cost >
		 rp->designated_cost + rp->path_cost)
		return 0;

	t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
	if (t < 0)
		return 1;
	else if (t > 0)
		return 0;

	if (p->designated_port < rp->designated_port)
		return 1;
	else if (p->designated_port > rp->designated_port)
		return 0;

	if (p->port_id < rp->port_id)
		return 1;

	return 0;
}

static void br_root_selection(struct net_bridge *br)
{
	struct net_bridge_port *p;
	u16 root_port = 0;

	list_for_each_entry(p, &br->port_list, list) {
		if (!br_should_become_root_port(p, root_port))
			continue;

		if (p->flags & BR_ROOT_BLOCK)
			br_root_port_block(br, p);
		else
			root_port = p->port_no;
	}

	br->root_port = root_port;

	if (!root_port) {
		br->designated_root = br->bridge_id;
		br->root_path_cost = 0;
	} else {
		p = br_get_port(br, root_port);
		br->designated_root = p->designated_root;
		br->root_path_cost = p->designated_cost + p->path_cost;
	}
}
Last changed by 
 
0xff07
Mise-en-place for the omnivores!
0
707
Published on HackMD