data structure for network protocol
Mark
As a students' project, I need to implement a telecommunications protocol.
The protocol implies preserving lots of IPv4 addresses along with some
additional data in a memory, so my first concern is effective way of storing
IP addresses, which can be considered as 32-bit numbers. The second problem
is fast lookup and retrieval of this information.
As a first thought, I was considering linked lists, but they are probably
not so effectively searching elements. The second option is tree. I'm aware
of binary search tree, radix tree and balanced trees (for example AVL),
though I had experince with BST only. And the last option is perhaps hash
tables (though I'm not so well familiar with them).
I'm not afraid of learning new algorithms and data structures, and I'm ready
to spend time on drilling them.
So, I would like to hear opinions about data structures appropriate to get
the job done.
Thanks in advance.
--
Mark
Richard Heathfield
> Hello
>
> As a students' project, I need to implement a telecommunications
> protocol. The protocol implies preserving lots of IPv4 addresses
> along with some additional data in a memory, so my first concern is
> effective way of storing IP addresses, which can be considered as
> 32-bit numbers. The second problem is fast lookup and retrieval of
> this information.
>
> As a first thought, I was considering linked lists, but they are
> probably not so effectively searching elements.
Right.
> The second option is
> tree. I'm aware of binary search tree, radix tree and balanced trees
> (for example AVL), though I had experince with BST only. And the
> last option is perhaps hash tables (though I'm not so well familiar
> with them).
Well, if all you are storing is IP addresses, a hash table doesn't
sound like such a great idea. But you are storing additional
information associated with the address (I'm guessing that you might
want a socket ID at the very least, *maybe* a port number (which
depends on your application requirements, obviously) and perhaps some
user information.) So a hash table is far from being a non-starter.
But if the IP address is your lookup key, and if many of your IP
addresses will be similar, then a trie seems like a good bet. Not a
typo - a trIe is a special kind of tree. I could go into great detail
but I'm not going to, since you can find very good descriptions in
the literature. Here's one ref to get you started:
http://www.itl.nist.gov/div897/sqg/dads/HTML/trie.html
Other sensible possibilities include all those that you have already
mentioned, except of course for linked lists. B-trees are probably
overkill.
In some applications, you don't particularly need to look up the IP,
because each IP needs to be enquired (even if only to determine that
no packet needs to be sent to that particular IP for that particular
occasion). In such applications, a circular list is often a good bet.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
Ben Pfaff
> As a students' project, I need to implement a telecommunications
> protocol. The protocol implies preserving lots of IPv4 addresses along
> with some additional data in a memory, so my first concern is
> effective way of storing IP addresses, which can be considered as
> 32-bit numbers. The second problem is fast lookup and retrieval of
> this information.
Do you just need to look up a record based on a known IP address?
That's a classic example of a situation where a hash table is
appropriate.
If you tell us more about what you are trying to do, we can
probably provide more help.
--
Ben Pfaff
http://benpfaff.org
robert...@yahoo.com
It depends on what kind of searching you need to do, and for how many
elements. If you just need to find something associated with a
particular IP address, something like a hash table might be a good
choice. The more tree-like structures (can) have guaranteed worst
case behavior, and allow you to consider the list of elements in a
sorted fashion as well, but are likely to be slower and more complex
to implement. If you need to do something like longest prefix
matching (as would a typical router trying to determine which want to
send a packet), something like a Patricia tree might be a good choice.
Moi
> Hello
>
> As a students' project, I need to implement a telecommunications
> protocol. The protocol implies preserving lots of IPv4 addresses along
> with some additional data in a memory, so my first concern is effective
> way of storing IP addresses, which can be considered as 32-bit numbers.
> The second problem is fast lookup and retrieval of this information.
>
> As a first thought, I was considering linked lists, but they are
> probably not so effectively searching elements. The second option is
> tree. I'm aware of binary search tree, radix tree and balanced trees
> (for example AVL), though I had experince with BST only. And the last
> option is perhaps hash tables (though I'm not so well familiar with
> them).
If you don't need range searches, and the maximal size of your table is fixed,
a hash table is the way to go, IMHO.
Otherwise you'll end up with some kind of tree. a judy-tree (difficult
to implement) will probably work well if your keysspace is sparse and
its distrubution is kind of lumpy.
Note: this is the same problem that internet routers, switches and NAT
-boxes have when maintaining their in-core tables. Take a look at IP-tables ...
HTH,
AvK
BGB / cr88192
"Mark" <mark_cruz...@hotmail.com> wrote in message
news:hctko6$d1r$1...@aioe.org...
> Hello
>
> As a students' project, I need to implement a telecommunications protocol.
> The protocol implies preserving lots of IPv4 addresses along with some
> additional data in a memory, so my first concern is effective way of
> storing IP addresses, which can be considered as 32-bit numbers. The
> second problem is fast lookup and retrieval of this information.
>
> As a first thought, I was considering linked lists, but they are probably
> not so effectively searching elements. The second option is tree. I'm
> aware of binary search tree, radix tree and balanced trees (for example
> AVL), though I had experince with BST only. And the last option is perhaps
> hash tables (though I'm not so well familiar with them).
>
in some cases, one can get good performance from a positional insert and a
binary lookup.
this works fairly well if the number of items is not huge, and fits nicely
in an ordinary array (the main cost is that, if the number of items gets
large, than the cost of sliding the array on inserts/deletions can get
expensive).
for very fast insertion and lookups, a hash-table is difficult to beat, but
it has very different behavioral properties than an array.
note that a hash table can be used very effectively (in several different
ways) to speed up accesses to both linked list and array based
representations (such as hitting the hash first, and falling back to a
linked list or array).
an AVL tree is good for both performance and can keep things sorted, and
scales well to a large number of elements, but its main downside is that it
is more awkward to work with than the other options, and has a higher memory
overhead. also, a naive implementation could exhibit major slowdowns during
large numbers of insertions and deletions (mostly related to memory
handling).
its main advantage is when storing items which are already "objects", and
would otherwise likely be handled with a linked list.
my personal preferences for many cases though are the use of hash-tables and
binary-lookups + positional insertion (since these are well suited to very
fast access to smaller numbers of items).
binary lookups/insertions tend to have fairly compact code and generally
good behavior, assuming the number of items is small (< 1000-2000, or much
smaller), where one wants fast access to these items.
a tree structure may be better for fast access to a much larger number of
items (say, > 100k items), but a generally higher overhead (and much worse
performance) for a smaller number of items (for example, you don't really
want to use an AVL tree for fetching items in a tight inner loop with a
small number of items, but you do want it if you are "fairly often"
accessing items in a fairly large pool).
having a high scalability range is a major downside of hash tables, as with
a hash table it is very useful to have an idea of the general range of
expected item counts, as estimating either too high or too low can somewhat
hurt performance and/or cause code to fail (depending on the
implementation).
a major use then of hash tables is using them as a single or multi-step
cache for some other structure, such as a linked list or array, ...
or such...
<snip>
Mark
Let me clarify what exactly I'm trying to do. It will be IGMP snooping (not
exactly a protocol as I've written, sorry) running in a kernel space
(Linux). This function is to listen the IGMP traffic (mainly Join and Leave
messages) between hosts and routers and decides which port must be added to
a list of multicast groups.
Assume that this feature will run on a 24-port Layer 2 switch, where
potentially there might be hundreds of multicast clients behind each port.
Information I will likely need to store is:
* IP address of a host requesting multicast session
* VLAN id to which the host belongs
* ingress port the request arrived from
* may be something else...
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?
--
Mark
BGB / cr88192
if each hash spot goes to a linked list, then hash collision is not much of
an issue (maybe, if too many items use the same spot, performance will
degrade).
otherwise, to effectively use a hash, one would have to hash more info such
that the key is hopefully unique (MultiCast:UniCast), but this would limit
the ability to look up by 1 or another.
another possibility for a hash is to use a hash where one steps between
spots. one idea I often use here is to implement a small PRNG to calculate
the next spot to check (IME this often has fairly good behavior...).
the great problems of lookup hashes of this sort are though:
deletes are problematic, as a delete can potentially break the lookup of
other items (using the NULL=free=end-of-chain trick), so often one has to
mark an item as deleted, and periodically "re-hash" to avoid the table
getting full, ...);
one has to worry about what happens when the table fills (as resizing
requires a rehash, and is awkward to do).
as well, a hash table which works this way can also introduce irregular
delays if capacity becomes an issue.
my primary use of hashes is actually using them as caching hashes, which
usually have a smaller numer of items, and the actual storage for the data
is "elsewhere", in this case, the hash is used simply as a quick lookup, and
not as the actual means of storage.
another advantage is that one can cheaply and easily "flush" the hash
(usually simply setting all spots to NULL or similar), in cases where the
prior state may be invalid.
a sorted array (binary lookup+positional insert) need not require that all
keys be unique, but this is often the case.
note that binary lookup can be combined with a hash, to yeild an average
case lookup of O(1), and a worst case of O(log2 n).
in this case, it works like:
hash IP;
check hash spot to see if it has desired item;
fall back to binary search;
add result to hash at spot.
in this case, the array would presumably hold pointers to structures holding
the info.
an example of a hash function for an IP address could be:
hi=((ip*65521)>>16)&4095;
which would work for a 12-bit hash (by changing the mask, this will work up
to a 16-bit hash, or up to 20 bits by reducing the prime and the shift, say
4093 and 12, ...).
or such...
but, I guess one option is to beat together several possible
implementations, and then to test them and see which delivers the best
performance (with real or simulated loads, ...).
> --
> Mark
James Harris
> Thanks for the comments.
>
> Let me clarify what exactly I'm trying to do. It will be IGMP snooping (not
> exactly a protocol as I've written, sorry) running in a kernel space
> (Linux). This function is to listen the IGMP traffic (mainly Join and Leave
> messages) between hosts and routers and decides which port must be added to
> a list of multicast groups.
> Assume that this feature will run on a 24-port Layer 2 switch, where
> potentially there might be hundreds of multicast clients behind each port.
>
> Information I will likely need to store is:
> * IP address of a host requesting multicast session
> * VLAN id to which the host belongs
> * ingress port the request arrived from
> * may be something else...
So it looks like your number of IP addresses (individual and multicast
if you need to store both) will be very small (< 24,000) and they will
come from limited ranges - i.e. just those IP addresses present on
your subnet.
If so try a trie (as RH suggested). It is simple to implement and
fast. You will need to make a design decision as to where to delimit
the elements but the simple solution may be best. Then it will self-
organise and take up little space.
> 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....
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.
James
James Harris
...
> > 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.
>
> 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.
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
BGB / cr88192
"James Harris" <james.h...@googlemail.com> wrote in message
news:2ff4a346-650f-4c14...@a32g2000yqm.googlegroups.com...
> On 6 Nov, 18:17, James Harris <james.harri...@googlemail.com> 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.
Moi
> "Mark" <mark_cruz...@hotmail.com> wrote in message
> news:hd0oh9$3e6$1...@aioe.org...
>> Thanks for the comments.
>>
>> Let me clarify what exactly I'm trying to do. It will be IGMP snooping
>> (not exactly a protocol as I've written, sorry) running in a kernel
>> space (Linux). This function is to listen the IGMP traffic (mainly Join
>> and Leave messages) between hosts and routers and decides which port
>> must be added to a list of multicast groups.
>> Assume that this feature will run on a 24-port Layer 2 switch, where
>> potentially there might be hundreds of multicast clients behind each
>> port.
If I understood the IGMP protocol correct you need to perform
two kinds of searches:
- one based on multicast address
- one based on "client" address.
Your data structure will need to support both.
(port number and interface number will probably be part of these keys,
but you still will have two "search keys")
The biggest design choice is IMHO if you want the whole "association table"
stored in one table, or if you want to split the thing up: one table per
interface, one table based on multicast address, one table based on
client address.
This will cause some duplication, equivalent to denormalisation in
a database model. (or normalisiation into BCNF/ 4NF)
Some of the protocol's messages contain repeating groups of
addresses; you could choose to store these as (sorted) arrays internally, too.
(merge / delete operations on lists are pretty easy to implement,
and use O(M+N) execution time, where tree/binary search consumes O(M*log(N)),
with bigger O ;-)
The N=24 interfaces seem a good candidate for a bitmask.
> another possibility for a hash is to use a hash where one steps between
> spots. one idea I often use here is to implement a small PRNG to
> calculate the next spot to check (IME this often has fairly good
> behavior...).
>
> the great problems of lookup hashes of this sort are though: deletes are
> problematic, as a delete can potentially break the lookup of other items
> (using the NULL=free=end-of-chain trick), so often one has to mark an
> item as deleted, and periodically "re-hash" to avoid the table getting
> full, ...);
> one has to worry about what happens when the table fills (as resizing
> requires a rehash, and is awkward to do).
>
> as well, a hash table which works this way can also introduce irregular
> delays if capacity becomes an issue.
Linear probing is problematic if you need to do (a lot of) deletes.
Chaining is easier to implement (but has a lousy cache locality)
Chaining will also allow you to implement a 2 way hashtable, which you'll
probably need.
Since memory is (always) limited, you need to choose what to do in
the case of table-full / out-of-memory conditions (probably just send
a protocol-message back to the requester).
I would probably use a fixed size table, with enough slots for
the intended maximal workload.
HTH,
AvK
Musatov
<xs:schema targetNamespace="http://www.meami.org/networking/OneX/v1"
xmlns="http://www.meami.org/networking/OneX/v1"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
elementFormDefault="qualified">
<!-- top-level element -->
<xs:element name="OneX">
<xs:complexType>
<!-- Optional 802.1X settings -->
<xs:sequence>
<!-- the default value is "false" -->
<xs:element name="cacheUserData" type="xs:boolean"
minOccurs="0" />
<!-- the default value is 60 seconds -->
<xs:element name="heldPeriod" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="1" />
<xs:maxInclusive value="3600" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- the default value is 30 seconds -->
<xs:element name="authPeriod" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="1" />
<xs:maxInclusive value="3600" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- the default value is 5 seconds -->
<xs:element name="startPeriod" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="1" />
<xs:maxInclusive value="3600" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- the default value is 3 times -->
<xs:element name="maxStart" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="1" />
<xs:maxInclusive value="100" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- the default value is 3 times -->
<xs:element name="maxAuthFailures" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="1" />
<xs:maxInclusive value="100" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- This setting is applicable only for wired Lan. The
default value is "compliant" -->
<xs:element name="supplicantMode" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="inhibitTransmission" />
<xs:enumeration value="includeLearning" />
<xs:enumeration value="compliant" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- default value is "machineOrUser" -->
<xs:element name="authMode" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="machineOrUser" />
<xs:enumeration value="machine" />
<xs:enumeration value="user" />
<xs:enumeration value="guest" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- Optional Single Sign On parameters for 802.1X -->
<xs:element name="singleSignOn" minOccurs="0">
<xs:complexType>
<xs:sequence>
<!-- Prelogon or Post Logon Integration -->
<xs:element name="type">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="preLogon" />
<xs:enumeration value="postLogon" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- Maximum duration to wait for connection -->
<xs:element name="maxDelay" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="0" />
<xs:maxInclusive value="120" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- whether EAP dialogs can be displayed at logon time.
The default is false -->
<xs:element name="allowAdditionalDialogs"
type="xs:boolean" minOccurs="0" />
<!-- Maximum duration to wait for connection in case UI
is to be displayed -->
<xs:element name="maxDelayWithAdditionalDialogs"
minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="0" />
<xs:maxInclusive value="120" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- whether the network uses different VLANs for
machine and user authentication. The default is false -->
<xs:element name="userBasedVirtualLan" type="xs:boolean"
minOccurs="0" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- mandatory parameter for 802.1X -->
<xs:element name="EAPConfig">
<xs:complexType>
<xs:sequence>
<!-- extension point for other namespaces, especially
for EAPHostConfig: EAP namespece -->
<xs:any namespace="##other" processContents="lax"
minOccurs="1" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- extension point for other namespaces -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
</xs:schema>
<?xml version="1.0" encoding="UTF-8" ?>
<xs:schema targetNamespace="http://www.meami.org/networking/WLAN/
profile/v1"
xmlns="http://www.meami.org/networking/WLAN/profile/v1"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
elementFormDefault="qualified">
<!-- type definition section -->
<xs:simpleType name="nameType">
<xs:restriction base="xs:string">
<xs:minLength value="1" />
<xs:maxLength value="255" />
</xs:restriction>
</xs:simpleType>
<xs:element name="WLANProfile">
<xs:complexType>
<xs:sequence>
<!-- Profile name is required. -->
<xs:element name="name" type="nameType" />
<!-- WLAN network settings -->
<!-- SSID's and connectionType are required. -->
<xs:element name="SSIDConfig" maxOccurs="256">
<xs:complexType>
<xs:sequence>
<!-- In this version, only one <SSID> is supported from
UI -->
<xs:element name="SSID" maxOccurs="256">
<xs:complexType>
<xs:sequence>
<!-- Either Hex or named SSID must be present. -->
<!-- Hex SSID takes precedence over named SSID. --
>
<xs:element name="hex" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:hexBinary">
<xs:minLength value="1" />
<xs:maxLength value="32" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<xs:element name="name" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:minLength value="1" />
<xs:maxLength value="32" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- extension point for other namespaces -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!--
Flag to indicate whether SSIDs within the same
SSIDConfig group will be
broadcasted or not. Default value is "false"
-->
<xs:element name="nonBroadcast" type="xs:boolean"
minOccurs="0" />
<!-- extension point for other namespaces -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<xs:element name="connectionType">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="IBSS" />
<xs:enumeration value="ESS" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!--
Specify connection mode when a network is in range
Default value = "auto"
-->
<xs:element name="connectionMode" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="auto" />
<xs:enumeration value="manual" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!--
Flag to determine roaming behavior when a more preferred
network is in range
Default value = "true"
-->
<xs:element name="autoSwitch" type="xs:boolean" minOccurs="0" /
>
<!-- wireless LAN MSM settings -->
<xs:element name="MSM" minOccurs="0">
<xs:complexType>
<xs:sequence>
<xs:element name="connectivity" minOccurs="0">
<xs:complexType>
<xs:sequence>
<xs:element name="phyType" minOccurs="0"
maxOccurs="4">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="a" />
<xs:enumeration value="b" />
<xs:enumeration value="g" />
<!-- this value is reserved for future use --
>
<xs:enumeration value="n" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- extension point for other namespaces -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- security settings -->
<xs:element name="security" minOccurs="0">
<xs:complexType>
<xs:sequence>
<!-- AuthEncryptions is required except for when
IHV extensibility uses 1X. -->
<xs:element name="authEncryption" minOccurs="0">
<xs:complexType>
<xs:sequence>
<!-- valid authentication methods -->
<xs:element name="authentication">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="open" />
<xs:enumeration value="shared" />
<xs:enumeration value="WPA" />
<xs:enumeration value="WPAPSK" />
<xs:enumeration value="WPA2" />
<xs:enumeration value="WPA2PSK" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- valid encryption methods -->
<xs:element name="encryption">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="none" />
<xs:enumeration value="WEP" />
<xs:enumeration value="TKIP" />
<xs:enumeration value="AES" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- flag indicating use of 802.1X -->
<xs:element name="useOneX" type="xs:boolean"
minOccurs="0" />
<!-- extension point for other namespaces --
>
<xs:any namespace="##other"
processContents="lax" minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- Optional MSM security settings. -->
<!-- there is no default value for shareKey if
absent -->
<xs:element name="sharedKey" minOccurs="0">
<xs:complexType>
<xs:sequence>
<xs:element name="keyType">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="networkKey" />
<xs:enumeration value="passPhrase" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<xs:element name="protected"
type="xs:boolean" />
<xs:element name="keyMaterial"
type="xs:string" />
<!-- extension point for other namespaces --
>
<xs:any namespace="##other"
processContents="lax" minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- the default value is 0 when the shared key is
present -->
<xs:element name="keyIndex" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="0" />
<xs:maxInclusive value="3" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!--
For WPA2, the default value is "enabled"
for all others, the default value is
"disabled"
-->
<xs:element name="PMKCacheMode" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="disabled" />
<xs:enumeration value="enabled" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- the default value is 720 minutes --
>
<xs:element name="PMKCacheTTL" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="5" />
<xs:maxInclusive value="1440" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- the default value is 128 entries -->
<xs:element name="PMKCacheSize" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="1" />
<xs:maxInclusive value="255" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- the default value is "disabled" -->
<xs:element name="preAuthMode" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:string">
<xs:enumeration value="disabled" />
<xs:enumeration value="enabled" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- the default value is 3 times -->
<xs:element name="preAuthThrottle" minOccurs="0">
<xs:simpleType>
<xs:restriction base="xs:integer">
<xs:minInclusive value="1" />
<xs:maxInclusive value="16" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- extension point for other namespaces -->
<!-- this is also the insertion point for OneX
namespace -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- extension point for other namespaces -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- IHV specific settings -->
<xs:element name="IHV" minOccurs="0">
<xs:complexType>
<xs:sequence>
<!--
OUI info of the IHV. Required. First three (3) bytes
represented by eight (6)
hex chars (0-9, A-F)indicates the OUI, the 4th byte
represented by two (2) hex
chars (0-9, A-F) indicates the type of the OUI.
-->
<xs:element name="OUIHeader">
<xs:complexType>
<xs:sequence>
<xs:element name="OUI">
<xs:simpleType>
<xs:restriction base="xs:hexBinary">
<xs:length value="3" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<xs:element name="type">
<xs:simpleType>
<xs:restriction base="xs:hexBinary">
<xs:length value="1" />
</xs:restriction>
</xs:simpleType>
</xs:element>
<!-- extension point for other namespaces -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- Either <connectivity> or <security> must be present
-->
<!-- IHV specific connectivity settings -->
<xs:element name="connectivity" minOccurs="0">
<xs:complexType>
<xs:sequence>
<!-- Must be a single top-level element -->
<xs:any namespace="##other" processContents="lax" /
>
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- IHV specific security settings -->
<xs:element name="security" minOccurs="0">
<xs:complexType>
<xs:sequence>
<!-- Must be a single top-level element -->
<xs:any namespace="##other" processContents="lax" /
>
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- optional flag indicating whether IHV security uses
MS 1X settings (default false) -->
<xs:element name="useMSOneX" type="xs:boolean"
minOccurs="0" />
<!-- extension point for other namespaces -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
<!-- extension point for other namespaces -->
<xs:any namespace="##other" processContents="lax"
minOccurs="0" maxOccurs="unbounded" />
</xs:sequence>
</xs:complexType>
</xs:element>
</xs:schema>
On Nov 11, 12:28 am, Moi <r...@invalid.address.org> wrote:
> On Fri, 06 Nov 2009 08:13:46 -0700, BGB / cr88192 wrote:
> > "Mark" <mark_cruzNOTFORS...@hotmail.com> wrote in message
> AvK-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.12 (GNU/Linux)
iEYEARECAAYFAkrxsK0ACgkQmo2774GZ7qmY4QCePOtEnBkQ+6wwjF9tfMYMhOab
xmIAoJoDosujMwDSTo+XOOIOSmByoQT1
=7v6g
-----END PGP SIGNATURE-----
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.12 (GNU/Linux)
iEYEARECAAYFAkrxsK0ACgkQmo2774GZ7qmY4QCePOtEnBkQ+6wwjF9tfMYMhOab
xmIAoJoDosujMwDSTo+XOOIOSmByoQT1
=7v6g
-----END PGP SIGNATURE-----