Ethernet Switch MAC Table

Thread Starter

Meliksen

Joined Sep 21, 2022
8
FPGA üzerinde Ethernet anahtarı üzerinde çalışıyorum. 8192 MAC adresim var, bunları 16-bit Hash algoritmasından geçirerek MAC tablosunu oluşturmaya çalışıyorum. bununla ilgili bir kaç sorum var;

Mac tablosu olarak kullandığım blok RAM'in adres portu olarak hash algoritma sonucunu kullanıyorum. Bu şekilde 1 saat döngüsünde arama işlemini tamamlıyorum ancak 16 bit HASH algoritması için 2^16 = 65536 adreslik çok büyük bir RAM oluşturuluyor.
65536 adresin sadece 8192 adresi kullanılır, gerisi boş kalır. Bunu daha verimli nasıl yapacağımı bilmiyorum. Yardımınız için şimdiden teşekkür ederim.

Please use English text..Mod


I am working on Ethernet switch over FPGA. I have 8192 MAC addresses, I'm trying to build the MAC table by passing them through the 16-bit Hash algorithm. I have a few questions about it;

I am using the hash algorithm result as the address port of the block RAM that I use as the mac table. In this way, I complete the search in 1 clock cycle, but for the 16-bit HASH algorithm, a very large RAM of 2^16 = 65536 addresses is created.
Of the 65536 addresses, only 8192 addresses are used, the rest is left blank. I don't know how to do this more efficiently. Thanks already for your help.
 

cqexbesd

Joined Dec 16, 2017
6
The first thing to note is that the size of a hash table is configurable. You always need to allow for hash collisions anyway (eg chaining or open addressing etc) and reducing the number of buckets just makes them more likely so you have to trade storage space for speed.

I don’t have FPGA experience and there may be something that works well there but in the CPU world, if you still don’t want to use a hash, then the next most obvious thing would be some kind of tree. The exact configuration is again a trade off between space and speed. You could for example have 256 root nodes, each with 256 leaves etc. You wouldn’t have to allocate all the buckets beyond the first level - as presumably many would be empty.

If you used trees you could also use lists because they would be small enough to search very quickly on modern hardware. For more speed you could have, say, two lists at each level and only have to search about half the entries.

As you can see there are many options and scope for optimisation depending on what you value most.
 

michael8

Joined Jan 11, 2015
410
I am working on Ethernet switch over FPGA. I have 8192 MAC addresses,

There are 2**48 Ethernet MAC address (281474976710656) not 8192. I'd guess that you mean
that you have memory for 8192 MAC addresses.

I'm trying to build the MAC table by passing them through the 16-bit Hash algorithm. I have a few questions about it;

I am using the hash algorithm result as the address port of the block RAM that I use as the mac table. In this way,
I complete the search in 1 clock cycle, but for the 16-bit HASH algorithm, a very large RAM of 2^16 = 65536 addresses is created.


As would be expected with a hash to 16 bits. If you only have 8192 address you need to use a 13 bit hash
(or 13 bits of the 16 bit hash?).

Of the 65536 addresses, only 8192 addresses are used, the rest is left blank. I don't know how to do this more efficiently.

What are the constraints? If you do a lookup and that cache memory slot is already occupied what should happen?
a. failure, product isn't considered working?
b. send packet to all ports as don't know which is correct
c. drop packet
d. something else...

Most likely a small ethernet switch won't see even close to 8192 different MAC addresses, however even with
only 2 MAC addresses they could have the same hash. One way this has been avoided in some cache
systems is to split your cache into two 4096 size ones. Given a MAC address you look it up in both
in parallel and do parallel compares to see which it matches. If it matches either one you use that
one. If neither match you replace one of them with this "new" MAC address...

Of course, this takes more FPGA resources... It's all a trade off. And this can be expanded to 4 way instead
of 2 way etc.

Other alternatives might envolve breaking your 1 cycle lookup.
 

Thread Starter

Meliksen

Joined Sep 21, 2022
8
FPGA üzerinden Ethernet anahtarı üzerinde çalışıyorum. 8192 MAC adresim var,

8192 değil 2**48 Ethernet MAC adresi (28147496710656) var.
8192 MAC adresi için hafızanız olduğunu.

Onları 16-bit Hash algoritmasından geçirerek MAC tablosunu oluşturmaya çalışıyorum. bununla ilgili bir kaç sorum var;

Mac tablosu olarak kullandığım blok RAM'in adres portu olarak karma algoritma sonucunu kullanıyorum. Böylece,
Aramayı 1 saat döngüsünde tamamlıyorum ancak 16 bit HASH algoritması için 2^16 = 65536 adreslik çok büyük bir RAM oluşturuluyor.


16 bitlik bir karma ile beklendiği gibi. Yalnızca 8192 adresiniz varsa, 13 bitlik bir karma kullanmanız gerekir.
(veya 16 bitlik karmanın 13 biti?).

65536 adresten sadece 8192 adres kullanılır, geri kalanı boş bırakılır. Bunu daha verimli nasıl yapacağımı bilmiyorum.

Kısıtlamalar nelerdir? Bir arama yaparsanız ve bu önbellek yuvası zaten doluysa ne olmalı?
a. arıza, ürün çalışıyor sayılmaz mı?
b. hangisinin doğru olduğunu bilmediğinden tüm bağlantı noktalarına paket gönder
c. paket bırak
d. başka bir şey...

Büyük olasılıkla küçük bir ethernet anahtarı 8192 farklı MAC adresini bile görmeyecektir, ancak
aynı karmaya sahip olabilecekleri yalnızca 2 MAC adresi. Bazı önbelleklerde bundan kaçınılmasının bir yolu
sistemleri, önbelleğinizi iki 4096 boyutuna bölmek içindir. Bir MAC adresi verildiğinde, her ikisinde de ararsınız
paralel olarak ve hangisinin eşleştiğini görmek için paralel karşılaştırmalar yapın. İkisinden biriyle eşleşirse, onu kullanırsın
bir. Hiçbiri eşleşmezse, bunlardan birini bu "yeni" MAC adresiyle değiştirirsiniz ...

Tabii ki, bu daha fazla FPGA kaynağı gerektiriyor... Hepsi bir takas. Ve bunun yerine 4'e genişletilebilir
2 yol vb.

Diğer alternatifler, 1 döngü aramanızı bozmayı içerebilir.
[/ALINTI]
Örneğin, X adreslerim var. Bu X adresini en kolay ve en hızlı şekilde nasıl bulabilirim ? Cevabınız için teşekkürler.
 
Top