The Deforestation of L2

Speaker: Mingjie Zhao 

Co-authors: James McCauley, Ethan J. Jackson, Barath Raghavan, Sylvia Ratnasamy, Scott Shenker 

Motivation

Spanning Tree Protocol of level 2 was designed in the 80s as a plug and play protocol and has worked well through decades of network evolution. However it has two important drawbacks: 

1) It reduces the bisection band- width of the network to that of a single link

2) When a link on the spanning tree fails, the entire tree must be reconstructed 

In this paper the authors present a new approach to L2, called the All conneXion Engine or AXE, that retains the original goal of plug-and-play, but can use all network links while providing extremely fast recovery from failures.

GOALS

The speaker started by stating the goals of the paper as:

1. Be plug and play
2. Use all links for shortest path
3. Have fast recovery from failure with no control plane

The authors make the assumptions that failure direction can be fast, there’s still market for flood and learn L2 and everything is point to point. 

With these assumptions, AXE attempts to strike a balance between shortest path and fast recovery, while keeping things as simple as possible. AXE follows a basic flood/learn approach where:

• When you see a packet, learn
• When you don’t know what to do, flood

Approach

AXE does not need a tree to deal with loops which means flooding works with handling failure. The author explained that the treeless flooding is done by duplicate packet deletion. There are multiple ways of doing this, but the authors use hash-based duplication detection. This make learning and responding to failures more subtle. This is done by extending the packet header by adding a per-switch sequence number, hop count (protect from loop), flooded flag and learnable flags. In addition, switches will have two separate queues: a normal queue and a queue for flood packets for higher priority to deliver them quickly (to stop flooding quickly).

Algorithm

The speaker explained the algorithm as having two main steps:

1. learning (port or HC to src) and unlearning phase (if path corrupted)
2. output phase which does the following:

• drop duplicate
• flood if unknown
• forward packet otherwise

For the rest of the talk, the speaker showcased that AXE actually works by showing result for:

• On a campus network and a cluster showing not much flooding are caused by failures 
• The duplication filter can be very small (1000 entries is enough)
• Does it recover from overload? AXE is designed to handle overload (speaker referred the audience to the paper)

Q&A

Q: Can you prove the correctness of your protocol?

A: I am not sure how to do the formal proof, but we did things through experiment

Q: what’s the overhead of extending the header?

A: we think the overhead is not much cause what we add is very small

Q:Wha's the percentage of the overhead?

A: We haven’t tested that

Q:You assume that you know there is a failure. What happens if a link fails, and you don’t have keep-alive because you don;t have control packets, how do you detect the failure and recover?

A:We can recompute the topology after failures (they decided to take the discussion offline)