Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

GUID in RTPSv2.2 #6

Open
ghost opened this issue Apr 27, 2015 · 2 comments
Open

GUID in RTPSv2.2 #6

ghost opened this issue Apr 27, 2015 · 2 comments

Comments

@ghost
Copy link

ghost commented Apr 27, 2015

Dear devs,

I would like to discuss GUID in RTPSv2.2.

Problem: How to generate GuidPrefix value.

in RTPSv1.0 (current ORTE), there is GUID of 12B:
4B: HostId, IP Address used
4B: AppId, port << 8 | (manager)?0x02:0x01 used
4B: ObjectId, some predefined value used

in RTPSv2.2, there is GUID of 16B:
12B: GuidPrefix, where GuidPrefix[0] = vendorId.major, GuidPrefix[1] = vendorId.minor (see 8.3.3.1.3)
4B: EntityId, some predefined value used

In ORTE, GUID is used in AVL tree to store and retrieve objects, which are addressed by HostId, AppId and then ObjectId.

Needed: (see 8.2.4.2, 8.2.4.3)

  1. each participant (application in RTPSv1.0) in domain has unique GUID
  2. endpoints in participant (objects in application in RTPSv1.0) have same GuidPrefix

Proposal:

Naive approach of generating GuidPrefix would be:
2B: vendorId.major, vendorId.minor (by RTPSv2.2)
8B: last 8B of IPv6 OR 0 0 0 0 IPv4
2B: port

Because in AVL tree, the whole GUID should be stored, this approach results to 4 "layers" of AVL tree (vendor, IP, port, entityId) instead of 3 in current ORTE (hostId, appId, objId).

Another approach:
2B: vendorId.major, vendorId.minor (by RTPSv2.2)
2B: port
8B: last 8B of IPv6 OR 0 0 0 0 IPv4

The AVL tree for storing entities would have 3 "layers" (vendor+port, IP, entityId) as in current ORTE. The question is, if this structure is somehow problematic.

Another ideas would be appreciated.

Thanks,
jiri

@ppisa
Copy link
Contributor

ppisa commented Apr 27, 2015

Thanks for discussion opening.

I am not sure what is the right/best GUI construction, but as for the search, if you do not need for some reasons ability to search or iterate in some part of the tree then it is possible to fold more levels into single tree. It is enough to define compare function which compares one part and if it is different returns +/-1 and if it is the same then continues by comparison of other part and returns +/-1 according to ordering or 0 if they are the same.

But if it has for example advantage for performance to limit search only to own GUIDs for given domain then that part of the tree can be separated, rest kept together in another single tree and search can look first in own three then in generic or use prefix to decide in which part to search.

So there are more options and important is which kind of search are needed and which are performance critical. In the long term horizon, it could worth to consider replacement of AVL by HASH table. It provides better performance but requires more complex mechanism to optimize collisions and scale table according to needs. To implement this such way, that it does not block search side during insertion and extension requires complex data structures. And this level of performance tuning is not important for now. So I suggest to stay with AVL and check which kinds of search are used often. As for the iteration over all elements of some subtree, AVL is not ideal for that but implementation has constant overhead per element and it is better than for HASH. On the other hand, if iteration is critical over some subset then it should be interconnected by double linked list to make iteration simpler.

@wentasah
Copy link
Member

Hi all,

sorry for late response.

On Mon, Apr 27 2015, Jiri Hubacek wrote:

Proposal:

Naive approach of generating GuidPrefix would be:
2B: vendorId.major, vendorId.minor (by RTPSv2.2)

OK, this is required in 9.3.1.5.

8B: last 8B of IPv6 OR 0 0 0 0 IPv4

I agree with the IPv4 choice. In case of IPv6 this can easily lead to
collisions. For example, our department's IPv6 subnet has /64 prefix and
the lower 8 bytes are either based on MAC or assigned by the
administrator. In the latter case, it might be easy to have collision
between admin assigned parts in two different subnets.

Therefore I suggest using (IPv6addr[0-7] XOR IPv6addr[8-15]) in this
part of GUID.

2B: port

OK

Because in AVL tree, the whole GUID should be stored, this approach
results to 4 "layers" of AVL tree (vendor, IP, port, entityId) instead
of 3 in current ORTE (hostId, appId, objId).

I think it makes only sense to have two levels in the AVL.
Participant-level and entity-level, i.e. (guidprefix, entityId)

-Michal

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants