Subject: Re: [armd] For your consideration: SEATTLE

From: Changhoon Kim <[email-masked]>
Date: Sun, 31 Jul 2011 18:03:15 -0700

Hi,

I'd like to add a minor correction to the original email about SEATTLE.

- "For example, for ARP queries, the key is an IP address and the value
includes the IP address and the host’s location". We meant "For example, for
ARP queries, the key is an IP address and the value includes the _MAC_
address and the host’s location".

Also, for those who are interested in the implementation details of SEATTLE,
we have another write-up that include a full section explaining our
prototype SEATTLE switch.

http://www.cs.princeton.edu/~chkim/papers/seattle_tocs11.pdf

Thanks.

-- Chang

On Fri, Jul 29, 2011 at 4:42 AM, Matthew Caesar <[email-masked]>
wrote:
>
> Hi,
>
> I've been watching this list with a lot of interest. We wanted to post for
your consideration a protocol called SEATTLE we've been developing, which
targets large improvements in scalability of layer-2 in the context of data
centers/cloud computing by eliminating the need for broadcasts. We think
SEATTLE addresses some of the goals in ARMD's charter. More details below,
but we'd be quite interested to discuss/answer questions if there's
interest.
>
> SEATTLE achieves the same configuration-free properties as Ethernet
bridging yet scales to large networks. Unlike other proposals (e.g., TRILL,
Rbridges, Viking, SmartBridges), SEATTLE completely eliminates the need for
network-wide broadcasting, achieving data-plane control overheads that grow
logarithmically with network size. SEATTLE is backwards-compatible with
existing Ethernets, simplifying incremental deployment, and supporting
existing Ethernet functions (e.g., VLANs and host bootstrapping). SEATTLE
also supports more advanced (optional) features, such as the ability to
search and look up services based on text strings, more flexible routing and
more control over layer-2 routing policies, and the ability to anycast and
load balance directly over named services. SEATTLE has two main features:
>
> Distributed in-network directory service: The switches collectively run a
directory service that handles ARP and DHCP requests, as well as packets
sent to unknown destination addresses. The directory service leverages
consistent hashing and the link-state routing protocol to form a one-hop
distributed hash table. The directory is a key-value store, where the hash
of the key determines the switch(es) responsible for storing the
information. For example, for ARP queries, the key is an IP address and the
value includes the IP address and the host’s location. When an ingress
switch cannot handle an ARP/DHCP request or a data packet directly, the
switch computes the hash and directs the packet through the responsible
intermediate switch. The intermediate switch can response to ARP and DHCP
queries, and direct data packets onward to their egress switch while
returning the destination host’s location to the ingress switch.
>
> Reactive caching and invalidation: To minimize the portion of traffic
directed over longer paths, an ingress switch reactively caches the
responses from the intermediate switch. For example, while an intermediate
switch may handle an ARP query, the data packets typically flow directly
along the shortest path. In addition, other hosts connected to the same
ingress switch benefit from the cached information. However, the cached
information becomes stale if a host moves to a new location. SEATTLE
includes an efficient cache invalidation protocol that reactively updates
the stale cache entries when a packet wrongly travels to the old egress
switch.
>
> The first feature leads to good performance (by keeping traffic in the
data plane, and avoiding broadcast) and self scaling (by having the
directory service naturally scale with the size of the network), and the
second ensures fast recovery after failures and migration.
>
> Our writeup on SEATTLE:
>
> http://www.cs.princeton.edu/~jrex/papers/seattle08.pdf
>
> presents more details on this protocol, our experiences designing and
implementing a system prototype, and a performance evaluation of the
protocol through simulations and deployment in a testbed.
>
> -- Matt
>
>
> _______________________________________________
> armd mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/armd

---

From: Linda Dunbar <[email-masked]>
Date: Tue, 02 Aug 2011 14:19:48 +0000

Kim and Mattew,

Thank you very much for posting the SEATTLE detail to the ARMD list.
SEATTLE does present a possible approach to scale address resolution scheme for Large Layer 2 network.
ARMD WG is currently chartered to identify the Address Resolution issues in Data Center network, document best practices and workaround for Address Resolution scaling issues. At the last week's ARMD WG session, many Address Resolution scaling issues were discussed.
Many people do feel that it is more productive for the WG to focus on a subset of problems which are solvable, so that the WG won't  waste energy on too broad issues associated with Data Center.

Is it be possible for you to write an IETF draft to describe the SEATTLE approach for next IETF?

Thanks,
Linda Dunbar

From: [email-masked] [mailto:[email-masked]] On Behalf Of Changhoon Kim
Sent: Sunday, July 31, 2011 8:03 PM
To: [email-masked]
Subject: Re: [armd] For your consideration: SEATTLE

Hi,

- "For example, for ARP queries, the key is an IP address and the value includes the IP address and the host's location". We meant "For example, for ARP queries, the key is an IP address and the value includes the _MAC_ address and the host's location".

Also, for those who are interested in the implementation details of SEATTLE, we have another write-up that include a full section explaining our prototype SEATTLE switch.

Thanks.

-- Chang

On Fri, Jul 29, 2011 at 4:42 AM, Matthew Caesar <[email-masked]<mailto:[email-masked]>> wrote:
>
> Hi,
>
> I've been watching this list with a lot of interest. We wanted to post for your consideration a protocol called SEATTLE we've been developing, which targets large improvements in scalability of layer-2 in the context of data centers/cloud computing by eliminating the need for broadcasts. We think SEATTLE addresses some of the goals in ARMD's charter. More details below, but we'd be quite interested to discuss/answer questions if there's interest.
>
> SEATTLE achieves the same configuration-free properties as Ethernet bridging yet scales to large networks. Unlike other proposals (e.g., TRILL, Rbridges, Viking, SmartBridges), SEATTLE completely eliminates the need for network-wide broadcasting, achieving data-plane control overheads that grow logarithmically with network size. SEATTLE is backwards-compatible with existing Ethernets, simplifying incremental deployment, and supporting existing Ethernet functions (e.g., VLANs and host bootstrapping). SEATTLE also supports more advanced (optional) features, such as the ability to search and look up services based on text strings, more flexible routing and more control over layer-2 routing policies, and the ability to anycast and load balance directly over named services. SEATTLE has two main features:
>
> Distributed in-network directory service: The switches collectively run a directory service that handles ARP and DHCP requests, as well as packets sent to unknown destination addresses. The directory service leverages consistent hashing and the link-state routing protocol to form a one-hop distributed hash table. The directory is a key-value store, where the hash of the key determines the switch(es) responsible for storing the information. For example, for ARP queries, the key is an IP address and the value includes the IP address and the host's location. When an ingress switch cannot handle an ARP/DHCP request or a data packet directly, the switch computes the hash and directs the packet through the responsible intermediate switch. The intermediate switch can response to ARP and DHCP queries, and direct data packets onward to their egress switch while returning the destination host's location to the ingress switch.
>
> Reactive caching and invalidation: To minimize the portion of traffic directed over longer paths, an ingress switch reactively caches the responses from the intermediate switch. For example, while an intermediate switch may handle an ARP query, the data packets typically flow directly along the shortest path. In addition, other hosts connected to the same ingress switch benefit from the cached information. However, the cached information becomes stale if a host moves to a new location. SEATTLE includes an efficient cache invalidation protocol that reactively updates the stale cache entries when a packet wrongly travels to the old egress switch.
>
> The first feature leads to good performance (by keeping traffic in the data plane, and avoiding broadcast) and self scaling (by having the directory service naturally scale with the size of the network), and the second ensures fast recovery after failures and migration.
>
> Our writeup on SEATTLE:
>
> presents more details on this protocol, our experiences designing and implementing a system prototype, and a performance evaluation of the protocol through simulations and deployment in a testbed.
>
> -- Matt
>
>
> [email-masked]<mailto:[email-masked]>

---

From: "Shah, Himanshu" <[email-masked]>
Date: Tue, 2 Aug 2011 12:23:09 -0400

Linda -

I specifically asked the question at the mike about solutions related work, in the last week's WG meeting,
and if you recall, Ron Bonica, said EXPLICITLY that solutions CAN NOT BE discussed in this WG
as this WG belongs to OPS area, and only requirement related discussions are in charter.

Has the scope of WG charter changed after the meetings were over??

Thanks,
himanshu

From: [email-masked] [mailto:[email-masked]] On Behalf Of Linda Dunbar
Sent: Tuesday, August 02, 2011 10:20 AM
To: Changhoon Kim; [email-masked]; Matthew Caesar
Subject: Re: [armd] For your consideration: SEATTLE

Kim and Mattew,

Thanks,
Linda Dunbar

Hi,

Thanks.

-- Chang

---

From: Linda Dunbar <[email-masked]>
Date: Tue, 9 Aug 2011 14:51:00 -0500

Matthew,

Questions on the details:

1. Distributed in-network directory service: when Ingress switch receives a
data packet with unknown, you stated that the ingress switch will send the
packet to the Intermediate switch based on the hashing value. How does
"intermediate switch" know if a received data packet is relayed from another
switch or sent directly by hosts? If the "intermediate switch" still doesn't
have forwarding entry for the destination address in the data packet, it
will do a "hashing" and send to another "intermediate switch. This
forwarding can form a loop. How does SEATTLE mitigate the loop issue?

2. Reactive caching and invalidation: Your brief description sounds a lot
like the scheme described in "(
https://datatracker.ietf.org/doc/draft-shah-armd-arp-reduction/". Can you
elaborate the major differences?

Thank you very much.

Linda Dunbar

On Fri, Jul 29, 2011 at 6:42 AM, Matthew Caesar <[email-masked]>wrote:

> The first feature leads to good performance (by keeping traffic in the data
> plane, and avoiding broadcast) and self scaling (by having the directory
> service naturally scale with the size of the network), and the second
> ensures fast recovery after failures and migration.
>
> Our writeup on SEATTLE:
>
> http://www.cs.princeton.edu/~**jrex/papers/seattle08.pdf<http://www.cs.princeton.edu/~jrex/papers/seattle08.pdf>
>
> ______________________________**_________________
> armd mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/armd<https://www.ietf.org/mailman/listinfo/armd>
>

---

From: Changhoon Kim <[email-masked]>
Date: Tue, 9 Aug 2011 14:55:26 -0700

Linda,

On your question 1, SEATTLE uses a particular encapsulation format (EtherIP
in our current prototype) to deliver packets from an ingress to an
intermediate (resolver) switch. Hence, an intermediate switch can recognize
relayed packets w/o ambiguity because those packets will be destined to the
intermediate switch _*and*_ delivered in the particular encap format.

When an intermediate switch receives relayed packets from another ingress,
and the intermediate switch doesn’t have a forwarding entry for the actual
destination MAC address, the intermediate switch discards the packet. We do
not propose rehashing the packet and forwarding it to another intermediate
exactly because of the concern you have: a forwarding loop.

On your question 2, I took a look at the draft you mentioned
(draft-shah-armd-arp-reduction-01.txt) and found out that the draft does not
propose any cache update protocol that works among ToR switches. They
propose the existing aging-based timeout along with gratuitous ARP (which
essentially is a host-driven broadcast-based update that works only for host
arrival, but not for host departure or failure).

In contrast to this, SEATTLE adopts an explicit, unicast-based
host-information update mechanism triggered by switches. Suppose a host (h)
moves from an old switch (X) to a new switch (Y) due to mobility. Another
switch (Z) in the network may still have a forwarding entry for host h
associated with host h’s old location (i.e., X) and hence keep forwarding
packets destined to h to X via encapsulation. To update the stale forwarding
entry in switch Z, the old switch X directly sends an “host-not-available”
message to the ingress switch (Z) whenever it receives packets destined to h
from Z. Since this is done via unicast and only when the stale entry is
actually used for packet forwarding, the cache-update overhead in SEATTLE is
very low. For details, please take a look at Section 4.3, “Ensuring Seamless
Mobility” in the following write-up (page 16).

Thanks.

-- Chang

---

From: Linda Dunbar <[email-masked]>
Date: Wed, 10 Aug 2011 21:23:24 +0000

Himanshu,

ARMD WG's current charter is to document scaling issues in data center networks and requirement.
However, having some high level solution drafts can definitely help the WG to focus on the subset of problems which are solvable. At the ARMD WG discussion, some people stated that Address Resolution scaling is too big an issue if the desire is to build fat&big Layer 2. Therefore, it is beneficial to have a high level solution draft so that we know that the problem is solvable. You are welcome to initiate some discussion on the email list of the scheme proposed by your draft and present it at the next WG session if time allows.
But we want to make sure that the Problem statement and requirement is  #1 priority, and solution drafts are to scope the problems and details are to be addressed at the next stage.

Linda

From: Shah, Himanshu [mailto:[email-masked]]
Sent: Tuesday, August 02, 2011 11:23 AM
To: Linda Dunbar; Changhoon Kim; [email-masked]; Matthew Caesar
Subject: RE: [armd] For your consideration: SEATTLE

Linda -

Thanks,
himanshu

[ciena logo]

Kim and Mattew,

Thanks,
Linda Dunbar

Hi,

Thanks.

-- Chang

---

From: Ping Pan <[email-masked]>
Date: Wed, 10 Aug 2011 17:02:27 -0700

It sounds to achieve the goal, we need two things (a) tunneling between two
nodes, and (b) some mechanism to resolve MAC.

Curious, doesn't TRILL ESADI suppose to be doing this too? Or am I missing
something here.

Regards,

- Ping

On Tue, Aug 9, 2011 at 2:55 PM, Changhoon Kim <[email-masked]>wrote:

>> 1. Distributed in-network directory service: when Ingress switch receives
>> a data packet with unknown, you stated that the ingress switch will send the
>>> I've been watching this list with a lot of interest. We wanted to post
>>> for your consideration a protocol called SEATTLE we've been developing,
>>> which targets large improvements in scalability of layer-2 in the context of
>>> data centers/cloud computing by eliminating the need for broadcasts. We
>>> think SEATTLE addresses some of the goals in ARMD's charter. More details
>>> below, but we'd be quite interested to discuss/answer questions if there's
>>> interest.
>>>

---

From: Changhoon Kim <[email-masked]>
Date: Thu, 11 Aug 2011 15:56:26 -0700

Ping,

Yes, as far as I understand, the TRILL ESADI protocol offers an
optional mechanism for RBrides to exchange end-station information (address,
vlan id, and location) explicitly, in addition to learning from the data
plane. The key differences between SEATTLE and ESADI are as follows.

   - In ESADI, every RBridge in a VLAN learns the whole end-station
   information announced by other RBridges in the same VLAN. In SEATTLE, each
   switch learns only a fraction of end-station information in a network (or a
   VLAN). Doing so reduces control-plane overhead needed to maintain a large
   amount of end-station information (e.g., memory foot-print of the
   host-information table, such as ARP and L2 forwarding table) consistently
   and timely.
   - ESADI uses multicast for end-station information dissemination. In
   contrast, SEATTLE switches register and resolve end-station information
   (between ingress and relay) via unicast, conducive to reliable
   delivery. Thanks to this reliability, SEATTLE switches never flood unicast
   frames.
   - Because SEATTLE switches disseminate end-station information only when
   and where it is needed, SEATTLE switches can update stale end-station
   information (due to mobility or failure) more efficiently and rapidly.

In summary, while ESADI is similar to the control-plane functions of
SEATTLE, it doesn't particularly address the scalability problems that can
arise in a large cloud DC where number and sizes (in terms of # of member
end stations) of VLANs are huge, and, furthermore, lots of VLANs can
potentially overlap even at leaf switches.

-- Chang

On Wed, Aug 10, 2011 at 5:02 PM, Ping Pan <[email-masked]> wrote:

>> On your question 1, SEATTLE uses a particular encapsulation format
>> (EtherIP in our current prototype) to deliver packets from an ingress to an
>> On Tue, Aug 9, 2011 at 12:51 PM, Linda Dunbar <[email-masked]>wrote:
>>
>>> Matthew,
>>>
>>> https://datatracker.ietf.org/doc/draft-shah-armd-arp-reduction/". Can
>>> you elaborate the major differences?
>>>
>>> Thank you very much.
>>>
>>> Linda Dunbar
>>>
>>>> Distributed in-network directory service: The switches collectively run
>>>> a directory service that handles ARP and DHCP requests, as well as packets