Re: data structure for network protocol
- From: "BGB / cr88192" <cr88192@xxxxxxxxxxx>
- Date: Sat, 7 Nov 2009 07:15:54 -0700
"James Harris" <james.harris.1@xxxxxxxxxxxxxx> wrote in message
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
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
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
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
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
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
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.
- Prev by Date: Re: How to choose a Data-Structure for a Priority Queue ?
- Next by Date: Re: How to choose a Data-Structure for a Priority Queue ?
- Previous by thread: Re: data structure for network protocol
- Next by thread: How to choose a Data-Structure for a Priority Queue ?