Subject: [MEXT] Binary Filters and the nature of MIP Re: binary filters draft 0

From: George Tsirtsis <[email-masked]>
Date: Wed, 13 May 2009 09:51:18 -0400

Michael,

Trying to navigate through this thread, on one handle I am puzzled by
the PRI discussion so I am going to ignore it for now, but on the
other hand I now realize a fundamental issue which possibly causes the
difference of opinion on the subject.

You seem to think of MIP and even of Connectivity Managers as a high
level applications that live at user level. This viewpoint alone
pretty much defines your opinion. It is of course true that a lot of
public and research-type implementations of such functions are at user
level, possibly using high level programming languages.

In the real commercial world, however, things are much different. To
put any of this in a real world wireless, highly integrated device
(think of iPhones, BBerrys, other smart phones and even netbooks etc)
Connectivity Managers and Mobile IP will be highly optimized, low
level application in C or even in Assembly. MIPv4 has been integrated
in phones  by Nextel as part of the Direct Connect system, and I have
personally been involved in one assembly implementation of Mobile IP
during my Flarion years, and am now involved with another such low
level implementation in my current company.

I hope this helps you understand where I (and probably others) come
from when they are interested in binary filter rules, and why I keep
saying that it is fine to have text filters too if people really want
them but they cannot possibly be the default format.

George

On Wed, May 13, 2009 at 8:46 AM, Julien Laganier
<[email-masked]> wrote:
> Michael,
>
> On Wednesday 13 May 2009, Michael Eriksson wrote:
>> [...]
>> You are mixing up:
>
> OTOH, I have the impression that you are mixing things up quite a bit
> here. See below -
>
>> 1. Determining the order of the rules. This is done at the MN, and is
>>    independent of the how the rules are expressed (binary or text).
>>    Determining whether the rules overlap or not is not necessary, as
>>    long as you sort them in priority order.
>>
>> 2. Transfering the ORDERED list of rules from the MN to the HA. This
>>    is where there is a difference between the text rules and binary
>>    rules transferred in the flow-binding format.
>>
>>    - For the text format, this is trivial: Just append them in order.
>
> Exactly the same can be done with the binary format: Just append them in
> order in a single BU.
>
> Defining a priority field is an optimization that allows not sending the
> full ruleset in each BU, thus making it possible to order rules that
> were sent in different BUs. You would need exactly the same for your
> text format were you going to provide the same optimization.
>
>>    - For the binary format, you have two choices:
>>
>>      - Send them unordered (FID-PRI=0). Not a good idea, since it is
>>        most likely that the wrong rule will match some flows.
>>
>>      - Enumerate the rules by using the FID-PRI field as a rule
>>        numerator (hence my BASIC remark).
>>
>>      In practice, you will always have to enumerate the rules with
>> the FID-PRI field. This is not very elegant, and adds complexity. For
>> instance, the rules would have to be sorted according to their
>> FID-PRI value after reception, while in the text format they always
>> arrives in correct order.
>
> See above the point that FID-PRI is required only because there's the
> optimization of sending the full ruleset in each BU.
>
> --julien
> _______________________________________________
> MEXT mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mext
>

---

From: "Hannes Tschofenig" <[email-masked]>
Date: Wed, 13 May 2009 17:04:30 +0300

I would like to remind that the representation on the wire has very little
todo with the internal implementations of all sorts of filters. 

Packet filter implementations are very likely to use an virtual machine
alike syntax. A more classical example can be found with the BPF packet
filter:
http://download.at.kde.org/pub/tcpdump/papers/bpf-usenix93.pdf

Ciao
Hannes

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On 
>Behalf Of George Tsirtsis
>Sent: 13 May, 2009 16:51
>To: Michael Eriksson
>Cc: [email-masked]
>Subject: [MEXT] Binary Filters and the nature of MIP Re: 
>binary filtersdraft 0
>
>Michael,
>
>Trying to navigate through this thread, on one handle I am 
>puzzled by the PRI discussion so I am going to ignore it for 
>now, but on the other hand I now realize a fundamental issue 
>which possibly causes the difference of opinion on the subject.
>
>You seem to think of MIP and even of Connectivity Managers as 
>a high level applications that live at user level. This 
>viewpoint alone pretty much defines your opinion. It is of 
>course true that a lot of public and research-type 
>implementations of such functions are at user level, possibly 
>using high level programming languages.
>
>In the real commercial world, however, things are much 
>different. To put any of this in a real world wireless, highly 
>integrated device (think of iPhones, BBerrys, other smart 
>phones and even netbooks etc) Connectivity Managers and Mobile 
>IP will be highly optimized, low level application in C or 
>even in Assembly. MIPv4 has been integrated in phones  by 
>Nextel as part of the Direct Connect system, and I have 
>personally been involved in one assembly implementation of 
>Mobile IP during my Flarion years, and am now involved with 
>another such low level implementation in my current company.
>
>I hope this helps you understand where I (and probably others) 
>come from when they are interested in binary filter rules, and 
>why I keep saying that it is fine to have text filters too if 
>people really want them but they cannot possibly be the default format.
>
>George
>
>> Exactly the same can be done with the binary format: Just 
>append them 
>> in order in a single BU.
>>
>> Defining a priority field is an optimization that allows not sending 
>> the full ruleset in each BU, thus making it possible to order rules 
>> that were sent in different BUs. You would need exactly the same for 
>> your text format were you going to provide the same optimization.
>>

---

From: George Tsirtsis <[email-masked]>
Date: Wed, 13 May 2009 10:05:19 -0400

Hannes,

Just to make sure I am not missing your point this is an argument for
the fact that one can do text based filters at user API level but
still send them binary over the air, right?

George

---

From: Michael Eriksson <[email-masked]>
Date: Wed, 13 May 2009 17:01:05 +0200

> them but they cannot possibly be the default format.

At last some reasonable arguments!

As I have written before, I could live with binary rules. I just want
people to understand that a text-based rule language does have its
advantages.

Some random thoughts:

- I think that we must lift ourselves from native and portable
  assembler (aka C). As I wrote previously, the Android phone (very
  much a commercial product) is already doing all its logic in Java,
  which is a good start.

  I can understand that there are cost reduced products, where things
  have to be done in C. On the other hand, I think that only advanced
  terminals will do flow mobility, and they will/should have the power
  to use better programming languages.

- I think that you are vastly overestimating the implementation cost
  of parsing a text rule format. Lex and yacc compiles a lexical
  scanner and a language grammar into C code, which can then be
  compiled and linked into the final program.

  My complete (nonoptimized) lex+yacc parser for the text format, as
  specified in draft-larsson, is a total of 268 non-empty lines of
  source code, which compile into a total of 10476 bytes of i386
  object code. Sure you have room for that in your target devices?

Regards,
Michael

---

From: "Hannes Tschofenig" <[email-masked]>
Date: Wed, 13 May 2009 19:40:26 +0300

Sorry to be unclear. 

There are two aspects: 

1) How do you encode filters on the wire, i.e., when carried in your
favorite mobility protocol (or other protocol; does not really matter that
much).

2) How are these filters implemented in a particular node? 

Now, for item (2) folks have come up with quite sophisticated mechanisms
(typically dedicated languages that have an assembler like syntax) over time
that are (a) highly efficient and (b) quite compact in the encoding. I
provide a reference to the BSD packet filter system but the work obviously
did not stop in 1992. 

Now, ideally you would want to select a format for (1) that allows easy
conversion to the format used with (2).

The problem now is that different implementations use different languages.
So, it is quite likely that you will have to convert the stuff you get via
(1) anyway to (2). 

So, my conclusion is that the format for (1) does not really matter unless
you get to pick a format that is extremely close or equal to the format used
by (2) for most of the implementations. 

This only matters if the translation from (1) to (2) is performance-wise an
issue. I am not sure it really is and in that case you could as well toss a
coin since it does not matter at all for the format for (1) is. 

Does this description make any sense? 

Ciao
Hannes

PS: Whatever you do it would be nice to have a reference library at the end
that folks could use in their implementation. 

>From: George Tsirtsis [mailto:[email-masked]] 
>Sent: 13 May, 2009 17:05
>To: Hannes Tschofenig
>Cc: Michael Eriksson; [email-masked]
>Subject: Re: [MEXT] Binary Filters and the nature of MIP Re: 
>binary filtersdraft 0
>
>Hannes,
>
>Just to make sure I am not missing your point this is an 
>argument for the fact that one can do text based filters at 
>user API level but still send them binary over the air, right?
>
>George
>
>> I would like to remind that the representation on the wire has very 
>> little todo with the internal implementations of all sorts 
>of filters.
>>
>> Packet filter implementations are very likely to use an virtual 
>> machine alike syntax. A more classical example can be found with the 
>> BPF packet
>> filter:
>>>From: [email-masked] [mailto:[email-masked]] On Behalf 
>>>Of George Tsirtsis
>>>Sent: 13 May, 2009 16:51
>>>To: Michael Eriksson
>>>Cc: [email-masked]
>puzzled by

---

From: "Glen Zorn" <[email-masked]>
Date: Thu, 14 May 2009 10:57:04 +0700

> Does this description make any sense?

Total sense.  I'd just add that if we are to worry about performance issues
at all they should be issues that we have some control over (i.e.,
efficiency on the wire) rather than those we do not (for example, the
algorithms used at either end to create or process the filters).

...

---

From: George Tsirtsis <[email-masked]>
Date: Thu, 14 May 2009 09:43:45 -0400

Agreed, which is again why binary makes sense as the default.

George