From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oi0-x232.google.com (mail-oi0-x232.google.com [IPv6:2607:f8b0:4003:c06::232]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 496A421F212 for ; Sun, 25 Jan 2015 19:45:09 -0800 (PST) Received: by mail-oi0-f50.google.com with SMTP id h136so5468908oig.9 for ; Sun, 25 Jan 2015 19:45:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=3Xisx1qOF4JYxzdQPCdXpPDe1/FtmAmmt84IKw8avQ4=; b=ccXXGKpoRoUXP/ORBTrSciQzEaX9TgLW87K5kyiKRZRWujp+GxUPkFs3MiWKq3nMyu LkDykesDoVgKlcFXnpXXACfb7kNAUVM8h4C0uF96QEzQ0lzE+5hp+llc7ar9SA3qomEU E2WqvVF118fFmWJTcluerAiZBiXixxBXf5ox9IF9MiJ10yn6ChLg7nOiwreswcRNfjMl J4VderOZvTE4RCoU1YcD4/QS/076juWIXEzBckpHej17x63Vmj0IoXPOx+iSaV15McJ3 fR1OWaZkZwO2+C8o5gTGWQp6rPCvGNa7A66WOqP1axF4OzA/jlnJDqTpty7H6TzZHUEq OQTA== MIME-Version: 1.0 X-Received: by 10.182.51.165 with SMTP id l5mr11689365obo.56.1422243909034; Sun, 25 Jan 2015 19:45:09 -0800 (PST) Received: by 10.202.51.66 with HTTP; Sun, 25 Jan 2015 19:45:08 -0800 (PST) In-Reply-To: <1422242279.46066942@apps.rackspace.com> References: <54B5D28A.3010906@gmail.com> <7B1EA8F0-FCB6-4A37-950F-2558FC751DE8@gmail.com> <54C038D0.1000305@gmail.com> <54C0BD22.3000608@gmail.com> <54C13F47.1010203@gmail.com> <1422111577.328132080@apps.rackspace.com> <1422217048.025611275@apps.rackspace.com> <1422237076.005718796@apps.rackspace.com> <1422242279.46066942@apps.rackspace.com> Date: Sun, 25 Jan 2015 19:45:08 -0800 Message-ID: From: Dave Taht To: David Reed Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Cc: "cerowrt-devel@lists.bufferbloat.net" Subject: Re: [Cerowrt-devel] Recording RF management info _and_ associated traffic? X-BeenThere: cerowrt-devel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: Development issues regarding the cerowrt test router project List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 26 Jan 2015 03:45:38 -0000 On Sun, Jan 25, 2015 at 7:17 PM, wrote: > Looking up an address in a routing table is o(1) if the routing table is = a > hash table. That's much more efficient than a TCAM. My simple example j= ust > requires a delete/insert at each node's route lookup table. Regrettably it is not O(1) once you take into account the cpu cache hierarc= hy, or the potential collisions you will have once you shrink the hash to something reasonable. Also I think you are ignoring the problem of covering routes. Say I have to get something to a.b.c.z/32. I do a lookup of that and find nothing. I then look to find a.b.c.z/31 and find nothing, then /30, then /29, /28, until I = find a hit for the next hop. Now you can of course do a binary search for likely subprefixes, but in any case, the search is not O(1). In terms of cache efficient data structures, a straight hash is not the way to go, of late I have been trying to wrap my head around the hat-trie as possibly being useful in these circumstances. Now, if you think about limiting the domain of the problem to something greater than the typical mac table, but less than the whole internet, it starts looking more reasonable to have a 1x1 ratio of destination IPs to hash table entries for lookups, but updates have to probe/change large segments of the table in order to deal with covering prefixes. > My point was about collections of WLAN's bridged together. Look at what > happens (at the packet/radio layer) when a new node joins a bridged set o= f > WLANs using STP. It is not exactly simple to rebuild the Ethernet layer'= s > bridge routing tables in a complex network. And the limit of 4096 entrie= s > in many inexpensive switches is not a trivial limit. Agreed. But see http://en.wikipedia.org/wiki/Virtual_Extensible_LAN > > > > Routers used to be memory-starved (a small number of KB of RAM was the > norm). Perhaps the thinking then (back before 2000) has not been revised= , > even though the hardware is a lot more capacious. The profit margins have not been revised. I would not mind, incidentally expanding the scope of the fqswitch project = ot try to build something that would scale up at l3 farther than we've ever se= en before, however funding for needed gear like: http://www.eetimes.com/document.asp?doc_id=3D1321334 and time, and fpga expertise, is lacking. I am currently distracted by evaluating a very cool new cpu architecture ( see http://www.millcomputing.com/wiki/Memory ) and even as nifty as that is I foresee a need for a lot of dedicated packet processing logic and memories to get into the 40GBit+ range. > > > Remember, the Ethernet layer in WLANs is implemented by microcontrollers, > typically not very capable ones, plus TCAMs which are pretty limited in > their flexibility. I do tend to think that the next era of SDN enabled hardware will eventuall= y lead to more innovation in both the control and data plane - however it seems we are still in a "me-too" phase of development of openvswitch (btw: there is a new software switch for linux called rocker we should look at, and make sure runs fq_codel), and a long way from flexibly programmable switch hardware in general. http://openvswitch.org/pipermail/dev/2014-September/045084.html > > > > While it is tempting to use the "pre-packaged, proprietary" Ethernet swit= ch > functionality, routing gets you out of the binary blobs, and let's you be= a > lot smarter and more scalable. Given that it does NOT cost more to do > routing at the IP layer, building complex Ethernet bridging is not obviou= sly > a win. SDN is certainly a way out of this mess. Eventually. But I fear we are maki= ng all the same mistakes over again, and making slower hardware, where in the end, it needs to be faster, to win. > > > BTW, TCAMs are used in IP layer switching, too, and also are used in pack= et > filtering. Maybe not in cheap consumer switches, but lots of Gigabit > switches implement IP layer switching and filtering. At HP, their switch= es > routinely did all their IP layer switching entirely in TCAMs. Yep. I really wish big, fat TCAMS were standard equipment. > > > On Sunday, January 25, 2015 9:58pm, "Dave Taht" sai= d: > >> On Sun, Jan 25, 2015 at 6:43 PM, David Lang wrote: >> > On Sun, 25 Jan 2015, Dave Taht wrote: >> > >> >> To your roaming point, yes this is certainly one place where migratin= g >> >> bridged vms across machines breaks down, and yet more and more vm >> >> layers are doing it. I would certainly prefer routing in this case. >> > >> > >> > What's the difference between "roaming" and moving a VM from one place >> > in >> > the network to another? >> >> I think most people think of "roaming" as moving fairly rapidly from one >> piece of edge connectivity to another, and moving a vm is a great deal >> more >> permanent operation. >> >> > As far as layer 2 vs layer 3 goes. If you try to operate at layer 3, y= ou >> > are >> > going to have quite a bit of smarts in the endpoint. Even if it's only >> > connected vi a single link. If you think about it, even if your networ= k >> > routing tables list every machine in our environment individually, you >> > still >> > have a problem of what gateway the endpoint uses. It would have to >> > change >> > every time it moved. Since DHCP doesn't update frequently enough to be >> > transparent, you would need to have each endpoint running a routing >> > protocol. >> >> Hmm? I don't ever use a dhcp-supplied default gateway, I depend on the >> routing >> protocol to supply that. In terms of each vm running a routing protocol, >> well, no, I would rely on the underlying bare metal OS to be doing >> that, supplying >> the FIB tables to the overlying vms, if they need it, but otherwise the >> vms >> just see a "default" route and don't bother with it. They do need to >> inform the >> bare metal OS (better term for this please? hypervisor?) of what IPs the= y >> own. >> >> static default gateways are evil. and easily disabled. in linux you >> merely comment >> out the "routers" in /etc/dhcp/dhclient.conf, in openwrt, set >> "defaultroute 0" for the >> interface fetching dhcp. >> >> When a box migrates, it tells the hypervisor it's addresses, and then th= at >> box >> propagates out the route change to elsewhere. >> >> > >> > This can work for individual hobbiests, but not when you need to suppo= rt >> > random devices (how would you configure an iPhone to support this?) >> >> Carefully. :) >> >> I do note that this stuff does (or at least did) work on some of the ope= n >> source variants of android. I would rather like it if android added ipv6 >> tethering soon, and made it possible to mesh together multiple phones. >> >> > >> > >> > Letting the layer 2 equipment deal with the traffic within the buildin= g >> > and >> > invoking layer 3 to go outside the building (or to a different securit= y >> > domain) makes a lot of sense. Even if that means that layer 2 within a >> > building looks very similar to what layer 3 used to look like around a >> > city. >> >> Be careful what you wish for. >> >> > >> > >> > back to the topic of wifi, I'm not aware of any APs that participate i= n >> > the >> > switch protocols at this level. I also don't know of any reasonably >> > priced >> > switches that can do anything smarter than plain spanning tree when >> > connected through multiple paths (I'd love to learn otherwise) >> > >> > David Lang >> >> >> >> -- >> Dave T=C3=A4ht >> >> thttp://www.bufferbloat.net/projects/bloat/wiki/Upcoming_Talks >> --=20 Dave T=C3=A4ht thttp://www.bufferbloat.net/projects/bloat/wiki/Upcoming_Talks