Leaving data that will be used in a key comparison out of the hash will also cause hash collisions.
On Thu, Jul 05, 2018 at 11:31:06PM +0200, Grzegorz wrote: > Ok, I agree. We don't want to change a hash function but only the input to > it, i.e., we want that hash will be computed based only on label number in > our case in microflow cache. Of course for such the hash the label number > can be used itself as a hash value. > > Regarding proposed mechanism, let say that we have some class of flows that > should be treated in network in same way, i.e., that are directed to the > same point in the network. Please consider such the simple network: > > n1-------| > |------n3-------n4 > n2-------| > > (n1 -> n3, n2->n3, n3->4 if picture is not clear) > > Let's consider a situation when n1 and n2 want to send a packet to n4. So > n1 stores one flow in microcache, n2 stores one flow in microcache, n3 > stores 2 flows in its microcache and same n4. If n1 and n2 (or rather host > connected to them) will generate 3 different flows directed to n4, the > number of flows in each node (switch) will be tripled. > But if all nodes (controlled by OF controller) will use same label to reach > a particular node in the network, the number of flows will be as follows > (in case of 3 flows originated in n1 and n2): > n1: 3 flows, matches based on 5tuple, all with same actions, i.e. MPLS=400, > out=1 > n2: 3 flows, matches based on 5tuple, all with same actions, i.e. MPLS=400, > out=1 > n3: 1 flow, match based on mpls label and proper action to send out to > proper interface. > This is a simple case, but when a network is complicated number of flows in > core (in this case n3) switches may be reduced. > > This approach is used simultaneously with multipath transmission approach. > Please look into figure 2 and section IIB on the page 6 of > https://arxiv.org/pdf/1805.07993.pdf for some explanation. > > > > czw., 5 lip 2018 o 22:59 Ben Pfaff <[email protected]> napisał(a): > > > Typically, changing a hash function in this way will only increase the > > number of hash collisions without reducing the number of hash table > > entries. > > > > On Thu, Jul 05, 2018 at 10:49:03PM +0200, Grzegorz wrote: > > > Sure, but we want to examine how a number of flows is reduced when > > proposed > > > mechanism is implemented. If we use what is now available in ovs, it will > > > still generate thousands of flows (hashes) in Exact Match Cache. Please > > > correct me if I'm wrong > > > > > > czw., 5 lip 2018 o 22:41 Ben Pfaff <[email protected]> napisał(a): > > > > > > > You can match on MPLS flows without needing to modify OVS's kernel flow > > > > table structure. Why do you want to modify it? > > > > > > > > On Thu, Jul 05, 2018 at 09:25:05PM +0200, Grzegorz wrote: > > > > > The goal is to minimize number of flows (aggregate them) in the core > > of > > > > > network using some labeling. In our case MPLS is proposed but any > > other > > > > > technique allowing for labeling may be used, e.g. VLANs. This is > > part of > > > > s > > > > > bigger idea. Details are presented in paper > > > > > https://arxiv.org/pdf/1805.07993.pdf > > > > > > > > > > czw., 5 lip 2018 o 21:15 Ben Pfaff <[email protected]> napisał(a): > > > > > > > > > > > It's an odd change. What's the goal? > > > > > > > > > > > > On Thu, Jul 05, 2018 at 08:27:08PM +0200, Grzegorz wrote: > > > > > > > I'm taking about hash based on which flow table is looked up in > > > > kernel > > > > > > data > > > > > > > path. > > > > > > > > > > > > > > czw., 5 lip 2018 o 20:20 Ben Pfaff <[email protected]> napisał(a): > > > > > > > > > > > > > > > Which hash are you talking about? OVS has lots of hashes all > > over. > > > > > > > > > > > > > > > > On Thu, Jul 05, 2018 at 07:46:57PM +0200, Grzegorz wrote: > > > > > > > > > Hi Ben, > > > > > > > > > You're absolutely right. Thank you! Now I understand how it > > > > works. > > > > > > > > > > > > > > > > > > So having such the knowledge I have another question. In > > order to > > > > > > > > implement > > > > > > > > > other part of our mechanism I need to place in kernel space > > only > > > > > > flows > > > > > > > > that > > > > > > > > > for which mach (hash) is done based only on MPLS label. If I > > > > correct > > > > > > > > > understand how OVS worsk, the hash is done based on all > > header > > > > > > fields. > > > > > > > > So I > > > > > > > > > need to put somewhere in code simple if statement, i.e.: > > > > > > > > > > > > > > > > > > if (packet is tagged with MPLS) > > > > > > > > > hash = label_number > > > > > > > > > else > > > > > > > > > proceed_regular_hash_calculation > > > > > > > > > > > > > > > > > > Could someone point me a place where such the statement > > should be > > > > > > placed > > > > > > > > in > > > > > > > > > the code? Thank you in advance. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > czw., 5 lip 2018 o 18:56 Ben Pfaff <[email protected]> napisał(a): > > > > > > > > > > > > > > > > > > > On Thu, Jul 05, 2018 at 10:32:23AM +0200, Grzegorz wrote: > > > > > > > > > > > We want to make some OSV code modification in order to > > obtain > > > > > > > > > > fuctionality > > > > > > > > > > > desribed in https://arxiv.org/pdf/1805.07993.pdf > > > > > > > > > > > Strictly speaking wa want to implement the part related > > to > > > > > > Figure 4 > > > > > > > > on > > > > > > > > > > page > > > > > > > > > > > 10. In shortcut, the proposed mechanism uses 2 flow > > tables > > > > > > (Detailed > > > > > > > > and > > > > > > > > > > > Coarse Flow Table, DTF and CFT). The first stores exact > > > > 5-tuple > > > > > > > > match, > > > > > > > > > > when > > > > > > > > > > > the latter cotains match based on only destination > > network. > > > > When > > > > > > a > > > > > > > > flow > > > > > > > > > > is > > > > > > > > > > > missed in DFT, the second table is looked up. When the > > match > > > > is > > > > > > > > found in > > > > > > > > > > > CFT, a packated is proccessed according to this much and > > > > > > > > simultaneously > > > > > > > > > > > switch prepares a new match based on this packet 5-tuple > > and > > > > > > acctions > > > > > > > > > > > copied from CFT. Such flow is inserted by switch into DFT > > > > itself. > > > > > > > > > > > > > > > > > > > > This sounds like what OVS already does with its multiple > > > > layers of > > > > > > > > > > caches, or possibly with connection tracking. What's new > > about > > > > > > your > > > > > > > > > > design? > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > _______________________________________________ discuss mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-discuss
