Re: data structure for network protocol


"James Harris" <james.harris.1@xxxxxxxxxxxxxx> wrote in message
news:2ff4a346-650f-4c14-a9f4-000dce8816af@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On 6 Nov, 18:17, James Harris <james.harri...@xxxxxxxxxxxxxx> wrote:

...

I think, lookup can be based on a IP address, but the same IP address
may
belong to several multicast group. Will this cause hash collision?

This is more challenging in the general case as there are millions of
potential multicast groups aren't there? However, the switch and
router will have limited memory for recording these and I suspect any
given host will join only one or a handful of groups at a time. The
best solution will depend on your requirements but the 'usual' answer
is to add a level of indirection....

Having read over my comments they may not be too clear. In the
paragraph above in referring to the limited memory of the switch and
router I meant that if they can manage the number of multicast groups
a PC has enough memory to manage the same structures. Some form of
dynamic structure will be needed.


personally, I don't believe a dynamic structure is needed.

a sorted array can have O(log2 n) accesses, and is O(n) for insertions or
deletes (it could be O(log2 n) as well, except that there is need to slide
over all the elements, which is a time cost as the number of elements
becomes large).

however, the overhead is fairly small, making it really good for accessing
things in tight loops (although, as N gets larger, a hash is better, which
is why one could combine them).


however, the memory overhead is somewhat reduced vs that of a binary tree or
similar (where a binary tree needs essentially 2n node structures, each one
often at least 2 or 3 pointers, ...).

as well, a tree may be slightly slower in practice, as pointer deferencing
and looping (or recursion) may be more expensive than loops, additions, and
shifts.


apparently, a variation of the array case (for improved speed of
inserts/deletes) is to split up the array into a number of smaller arrays
(and/or leaving "holes" in the array), allowing for entries to be
added/removed often without having to slide the entire array in the process.

in general though, I think arrays of this sort are better for cases where
inserts/deletes are very rare vs accesses.


another algo I had used in the past for "mixed activity" was to allow the
array to become unsorted during inserts/deletes (adding in entries wherever,
leaving holes, ...), and periodically re-sorting (via a modified quicksort)
when it is needed to put the array back into sorted order.

this variation was better for the case where in "open territory" inserts and
deletes were mixed with accesses, and so a slower algo was used for accesses
at this time, and this sorting would be done prior to high-volume
access-only operation.

another variant would be to use a flag (set when adding/deleting things),
and with the access function checking this flag and possibly re-sorting
as-needed (or a delay of say 2-4 consecutive accesses could be used, at
which point sorting would be forced).

what is best depends highly on the particular usage requirements and
activity patterns.



By the way, since you won't be the switch (the normal IGMP snooper) if
you are to sniff packets you already know you'll need it to forward
relevant packets to your machine. Have you checked you can get things
such as the vlan and the ingres port? I haven't checked but another
option may be to get the data from SNMP.

What I meant above is that the switch may make its internal IGMP data
- including the vlan and port number data that you say you want -
available via SNMP. In fact it's quite likely though you may have to
look in the private mib space.


from what I can infer, he was saying that his stuff would run on the switch.
take note that some routers and switches (such as some of those produced by
Linksys, and possibly others), run Linux internally, so very possibly the
person was talking about writing a kernel module or similar which would work
on one of these routers or switches.

however, as for available processor time, amount of RAM, ...
I don't know, I have not much looked into all of this.


For some SNMP coding/decoding routines see

http://codewiki.wikispaces.com/snmp_asn1

and other places. Also, check out the book series

Internetworking with TCP/IP by Douglas Comer

The chapters apparently vary by edition so if you don't want to buy
the complete set you'll need to check which volume presents the
information but there are chapters on IGMP and SNMP. The books are
excellent in presenting protocols from a programmer's perspective and
including and explaining working code.

James


.

Relevant Pages

  • Re: Controller for Switching current sink
    ... The load, includes ... the switch closed with my monster-FET array. ... So, I'm gonna precharge the cap, then throw the switch at 0v. ...
    (sci.electronics.design)
  • Re: [OT] Funny
    ... >> the NAG compiler does have a switch to allow you to tell it ... or the compiler simply isn't conforming. ... more arithmetic in computing addresses of array elements -- dis- ...
    (comp.lang.fortran)
  • SUMMARY: switch/hub for 3 T3 Raid devices
    ... > host and I want to use all 3 devices on the same host. ... Are there seperate hub and switch type solutions and is ... Loop from one array to another from the host to each array. ...
    (SunManagers)
  • object representation redux (term?)
    ... a suitable number of array locations and not their names. ... allocation itself can be automated altogether: ... need to be resolved for hashes 'somehow', ... array accesses will usually be faster than hash ...
    (comp.lang.perl.misc)
  • Re: Whats the most efficient testing of variables?
    ... >>I need to quickly compare a DWORD with a list of DWORDs to ... >>switch won't work because both are variables. ... >linear search of an array ) will be faster. ... MVP Tips: http://www.flounder.com/mvp_tips.htm ...
    (microsoft.public.vc.mfc)