Opened 4 years ago

Closed 4 years ago

#16750 closed enhancement (implemented)

Add improved family measure to Onionoo

Reported by: virgilgriffith Owned by:
Priority: Medium Milestone:
Component: Metrics/Onionoo Version:
Severity: Keywords: roster
Cc: saitosean@… Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

This is a follow-up from the graphs I've posted before.  Particularly,

We want the above algorithm implemented in Onionoo.  Here's how it works:

For each entry in the MyFamily list...

  1. truncate all fingerprints to 40 characters
  2. remove all fingerprints <40 characters.
  3. Relays A and B are in the same effective_family if and only if, via *symmetric links only*, A can reach each relay B.  You can use the standard iterative depth-first-search on: https://en.wikipedia.org/wiki/Depth-first_search
  4. Finally, in Onionoo, each relay has a (sorted) list of the fingerprints of its effective_family.

Misc:

  • If the relay's own fingerprint appears as part of its effective_family, remove the fingerprint.
  • As far as I know no one is using the current effective_family measure.  If not, I recommend replacing the previous effective_family with the above.
  • If someone wants to keep the existing effective_family, I suggest doing the above but calling it the "extended_family".  Either is fine by me.

Child Tickets

Attachments (2)

ComputeExtendedFamilies.java (9.5 KB) - added by karsten 4 years ago.
families.json.xz (63.8 KB) - added by karsten 4 years ago.

Download all attachments as: .zip

Change History (8)

Changed 4 years ago by karsten

Changed 4 years ago by karsten

Attachment: families.json.xz added

comment:1 Changed 4 years ago by karsten

Version: Tor: unspecified

Sounds good to me. We should keep the effective_family field, because it might already be in use, and instead add a new extended_family field. We can always remove the effective_family field later if we think we won't need it anymore.

I just wrote a standalone version of the extended_family field that fetches details documents from Onionoo and produces a version that contains the new extended_family field. See attached. Can you please look through the computeExtendedFamily method and through the output file families.json.xz very and tell me whether that's what you want in Onionoo? Changing it now is cheap, changing it later might become (too) expensive. Thanks!

comment:2 Changed 4 years ago by virgilgriffith

Double-checked this. Karsten's "extended_family" field matches 100% with my own computations of the family in the graphs above. All systems go.

comment:3 Changed 4 years ago by karsten

Thanks for looking, virgilgriffith. I have a tested-but-not-reviewed implementation in branch task-16750 in my public repository that produces details documents like the following (pretty-printed using JSONLint):

        {
            "nickname": "torpidsFRovh",
            "fingerprint": "91D23D8A539B83D2FB56AA67ECD4D75CC093AC55",
            "or_addresses": [
                "37.187.20.59:443",
                "[2001:41d0:a:143b::1]:993"
            ],
            "dir_address": "37.187.20.59:80",
            "last_seen": "2015-08-20 07:00:00",
            "last_changed_address_or_port": "2015-08-04 12:00:00",
            "first_seen": "2015-08-04 12:00:00",
            "running": true,
            "flags": [
                "Fast",
                "Guard",
                "HSDir",
                "Running",
                "Stable",
                "V2Dir",
                "Valid"
            ],
            "country": "fr",
            "country_name": "France",
            "latitude": 48.86,
            "longitude": 2.35,
            "as_number": "AS16276",
            "as_name": "OVH SAS",
            "consensus_weight": 16900,
            "host_name": "37-187-20-59.kimsufi.com",
            "last_restarted": "2015-04-27 22:25:33",
            "bandwidth_rate": 6291456,
            "bandwidth_burst": 7340032,
            "observed_bandwidth": 7126582,
            "advertised_bandwidth": 6291456,
            "exit_policy": [
                "reject *:*"
            ],
            "exit_policy_summary": {
                "reject": [
                    "1-65535"
                ]
            },
            "contact": "torpids AT yahoo dot com - 1JYHfzVFVD7n2Sezz3DEHDFgGYjQWpDjqF",
            "platform": "Tor 0.2.6.7 on Linux",
            "family": [
                "$0E3DE4D738C91A8BB56432EF2DA7C28D4108F4A2",
                "$169019BFFECBBB9A35878BCF4C7AE1FF37AD8452",
                "$231C2B9C8C31C295C472D031E06964834B745996",
                "$29FA22A7AEE4D8AAEA5BF9271834642EEDA849D7",
                "$3EE7D6BEAE015552C05E6AA40EBBCC69B251EC23",
                "$4C7AA094EF5072F08C89A72353227FACBE58092F",
                "$4C7BF55B1BFF47993DFF995A2926C89C81E4F04A",
                "$530E1038C3D2F746657B51F97831F9F422747180",
                "$552996B383110A00DE456E010E3E74A4E54E54B0",
                "$580A91DAE04CD402AE70E85E01C3B1FD5BE5136E",
                "$5CC55AF14792CE805CA486A2CA1EC25A4016474A",
                "$6A97482F1B228AF847A8FE83C75F68902C2DCA4D",
                "$6B7191639E179965FD694612C9B2C8FB4267B27D",
                "$7589D87E6669A04EE9EA081342006E2E5571AD43",
                "$79D6A70B5E42DB93563074E8A385EDDB46FBB6DA",
                "$8B3D6AB6A692C8C92AC33E47C6F75C593F5AAF42",
                "$935BABE2564F82016C19AEF63C0C40B5753BA3D2",
                "$93E8D956042F1C3572EFF87313F4794910584D3C",
                "$9643FE742A609FBE332E4D512A88DECF2E5207C2",
                "$A37C47B03FF31CA6937D3D68366B157997FE7BCD",
                "$A55D07F6D78CE790E7D75DE665DF8365866BA870",
                "$A703C8DB0466AB16375403D798005F568372E2D8",
                "$A705EFD586626F690A71A215E6233D7E8581C374",
                "$A99ED2CC51850744D8CFF194CF6B06900B8B13AD",
                "$BD5899EA64D83F7E885B2495DE0842F1A77E99AF",
                "$C9933B3725239B6FAB5227BA33B30BE7B48BB485",
                "$CEDD9C7C371E753CDD14D292BCE1C7B8F4734D25",
                "$E26AFC5F718E21AC502899B20C653AEFF688B0D2",
                "$ECC17C0BA74113FB7A4F58DAF2FF1EE23CE5DF06",
                "$FB40DC3C724E5AA6ECD3EA1F64C0F559B48F21B5",
                "$FC37A7B1C264497BA01A08BF6D2C982A99D5B963"
            ],
            "effective_family": [
                "$169019BFFECBBB9A35878BCF4C7AE1FF37AD8452",
                "$231C2B9C8C31C295C472D031E06964834B745996",
                "$29FA22A7AEE4D8AAEA5BF9271834642EEDA849D7",
                "$3EE7D6BEAE015552C05E6AA40EBBCC69B251EC23",
                "$4C7BF55B1BFF47993DFF995A2926C89C81E4F04A",
                "$6B7191639E179965FD694612C9B2C8FB4267B27D",
                "$935BABE2564F82016C19AEF63C0C40B5753BA3D2",
                "$A37C47B03FF31CA6937D3D68366B157997FE7BCD",
                "$C9933B3725239B6FAB5227BA33B30BE7B48BB485",
                "$CEDD9C7C371E753CDD14D292BCE1C7B8F4734D25",
                "$E26AFC5F718E21AC502899B20C653AEFF688B0D2",
                "$ECC17C0BA74113FB7A4F58DAF2FF1EE23CE5DF06",
                "$FB40DC3C724E5AA6ECD3EA1F64C0F559B48F21B5",
                "$FC37A7B1C264497BA01A08BF6D2C982A99D5B963"
            ],
            "extended_family": [
                "$0B454C7EBA58657B91133A587C1BDAEDC6E23142",
                "$0C77421C890D16B6D201283A2244F43DF5BC89DD",
                "$169019BFFECBBB9A35878BCF4C7AE1FF37AD8452",
                "$231C2B9C8C31C295C472D031E06964834B745996",
                "$29FA22A7AEE4D8AAEA5BF9271834642EEDA849D7",
                "$3EE7D6BEAE015552C05E6AA40EBBCC69B251EC23",
                "$4436A57FFE36F09368718BCFFF750EB86A4E00B9",
                "$4C7BF55B1BFF47993DFF995A2926C89C81E4F04A",
                "$5A551BF2E46BF26CC50A983F7435CB749C752553",
                "$6A29FD8C00D573E6C1D47852345B0E5275BA3307",
                "$6A37488DD4321F0A649F6F3A77E896FAD6930C99",
                "$6B7191639E179965FD694612C9B2C8FB4267B27D",
                "$6D3A3ED5671E4E3F58D4951438B10AE552A5FA0F",
                "$70C55A114C0EF3DC5784A4FAEE64388434A3398F",
                "$75C4495F4D80522CA6F6A3FB349F1B009563F4B7",
                "$8073670F8F852971298F8AF2C5B23AE012645901",
                "$935BABE2564F82016C19AEF63C0C40B5753BA3D2",
                "$A37C47B03FF31CA6937D3D68366B157997FE7BCD",
                "$B35C5739C8C5AB72094EB2B05738FD1F8EEF6EBD",
                "$BAACCB29197DB833F107E410E2BFAE5009EE7583",
                "$C9933B3725239B6FAB5227BA33B30BE7B48BB485",
                "$CEDD9C7C371E753CDD14D292BCE1C7B8F4734D25",
                "$E11B6AE135B5A43244656C27ECEE0C09DE9E286B",
                "$E26AFC5F718E21AC502899B20C653AEFF688B0D2",
                "$E6E18151300F90C235D3809F90B31330737CEB43",
                "$ECC17C0BA74113FB7A4F58DAF2FF1EE23CE5DF06",
                "$FB40DC3C724E5AA6ECD3EA1F64C0F559B48F21B5",
                "$FC37A7B1C264497BA01A08BF6D2C982A99D5B963"
            ],
            "consensus_weight_fraction": 0.00052586454,
            "guard_probability": 0.00086917344,
            "middle_probability": 0.00055606465,
            "exit_probability": 0,
            "recommended_version": true,
            "measured": true
        }

However, I wonder if it wouldn't be smarter to avoid repeating fingerprints to save space. Suggestion:

  • We keep the effective_family field unchanged as the set of relays that are in a direct, mutual family relationship with the relay.
  • We don't add the extended_family field as planned but instead add an indirect_family field (is there a better name?) that only contains relays that are not part of effective_family but that the relay is indirectly connected with by following mutual family relationships. One would simply compute the union of effective_family and indirect_family to obtain the originally proposed extended_family set.
  • We add a new field alleged_family (or is there a better name?) that contains all relays that the relay believes are in its family but which don't believe that it's in their family. This field would also contain nicknames if the relay still uses them to define its family.
  • In two months from now we remove the family field. It will be easy to re-create it by computing the union of effective_family and alleged_family. But we'll have to give Onionoo client developers some time to make this code change.

Here's how the document above would look like if we implemented that suggestion:

        {
            "nickname": "torpidsFRovh",
            "fingerprint": "91D23D8A539B83D2FB56AA67ECD4D75CC093AC55",
            "or_addresses": [
                "37.187.20.59:443",
                "[2001:41d0:a:143b::1]:993"
            ],
            "dir_address": "37.187.20.59:80",
            "last_seen": "2015-08-20 07:00:00",
            "last_changed_address_or_port": "2015-08-04 12:00:00",
            "first_seen": "2015-08-04 12:00:00",
            "running": true,
            "flags": [
                "Fast",
                "Guard",
                "HSDir",
                "Running",
                "Stable",
                "V2Dir",
                "Valid"
            ],
            "country": "fr",
            "country_name": "France",
            "latitude": 48.86,
            "longitude": 2.35,
            "as_number": "AS16276",
            "as_name": "OVH SAS",
            "consensus_weight": 16900,
            "host_name": "37-187-20-59.kimsufi.com",
            "last_restarted": "2015-04-27 22:25:33",
            "bandwidth_rate": 6291456,
            "bandwidth_burst": 7340032,
            "observed_bandwidth": 7126582,
            "advertised_bandwidth": 6291456,
            "exit_policy": [
                "reject *:*"
            ],
            "exit_policy_summary": {
                "reject": [
                    "1-65535"
                ]
            },
            "contact": "torpids AT yahoo dot com - 1JYHfzVFVD7n2Sezz3DEHDFgGYjQWpDjqF",
            "platform": "Tor 0.2.6.7 on Linux",
            "alleged_family": [
                "$0E3DE4D738C91A8BB56432EF2DA7C28D4108F4A2",
                "$169019BFFECBBB9A35878BCF4C7AE1FF37AD8452",
                "$4C7AA094EF5072F08C89A72353227FACBE58092F",
                "$530E1038C3D2F746657B51F97831F9F422747180",
                "$552996B383110A00DE456E010E3E74A4E54E54B0",
                "$580A91DAE04CD402AE70E85E01C3B1FD5BE5136E",
                "$5CC55AF14792CE805CA486A2CA1EC25A4016474A",
                "$6A97482F1B228AF847A8FE83C75F68902C2DCA4D",
                "$7589D87E6669A04EE9EA081342006E2E5571AD43",
                "$79D6A70B5E42DB93563074E8A385EDDB46FBB6DA",
                "$8B3D6AB6A692C8C92AC33E47C6F75C593F5AAF42",
                "$93E8D956042F1C3572EFF87313F4794910584D3C",
                "$9643FE742A609FBE332E4D512A88DECF2E5207C2",
                "$A55D07F6D78CE790E7D75DE665DF8365866BA870",
                "$A703C8DB0466AB16375403D798005F568372E2D8",
                "$A705EFD586626F690A71A215E6233D7E8581C374",
                "$A99ED2CC51850744D8CFF194CF6B06900B8B13AD",
                "$BD5899EA64D83F7E885B2495DE0842F1A77E99AF"
            ],
            "effective_family": [
                "$169019BFFECBBB9A35878BCF4C7AE1FF37AD8452",
                "$231C2B9C8C31C295C472D031E06964834B745996",
                "$29FA22A7AEE4D8AAEA5BF9271834642EEDA849D7",
                "$3EE7D6BEAE015552C05E6AA40EBBCC69B251EC23",
                "$4C7BF55B1BFF47993DFF995A2926C89C81E4F04A",
                "$6B7191639E179965FD694612C9B2C8FB4267B27D",
                "$935BABE2564F82016C19AEF63C0C40B5753BA3D2",
                "$A37C47B03FF31CA6937D3D68366B157997FE7BCD",
                "$C9933B3725239B6FAB5227BA33B30BE7B48BB485",
                "$CEDD9C7C371E753CDD14D292BCE1C7B8F4734D25",
                "$E26AFC5F718E21AC502899B20C653AEFF688B0D2",
                "$ECC17C0BA74113FB7A4F58DAF2FF1EE23CE5DF06",
                "$FB40DC3C724E5AA6ECD3EA1F64C0F559B48F21B5",
                "$FC37A7B1C264497BA01A08BF6D2C982A99D5B963"
            ],
            "indirect_family": [
                "$0B454C7EBA58657B91133A587C1BDAEDC6E23142",
                "$0C77421C890D16B6D201283A2244F43DF5BC89DD",
                "$4436A57FFE36F09368718BCFFF750EB86A4E00B9",
                "$5A551BF2E46BF26CC50A983F7435CB749C752553",
                "$6A29FD8C00D573E6C1D47852345B0E5275BA3307",
                "$6A37488DD4321F0A649F6F3A77E896FAD6930C99",
                "$6D3A3ED5671E4E3F58D4951438B10AE552A5FA0F",
                "$70C55A114C0EF3DC5784A4FAEE64388434A3398F",
                "$75C4495F4D80522CA6F6A3FB349F1B009563F4B7",
                "$8073670F8F852971298F8AF2C5B23AE012645901",
                "$B35C5739C8C5AB72094EB2B05738FD1F8EEF6EBD",
                "$BAACCB29197DB833F107E410E2BFAE5009EE7583",
                "$E11B6AE135B5A43244656C27ECEE0C09DE9E286B",
                "$E6E18151300F90C235D3809F90B31330737CEB43"
            ],
            "consensus_weight_fraction": 0.00052586454,
            "guard_probability": 0.00086917344,
            "middle_probability": 0.00055606465,
            "exit_probability": 0,
            "recommended_version": true,
            "measured": true
        }

Thoughts?

comment:4 Changed 4 years ago by virgilgriffith

My first impression is that this is a little odd, but upon further reflection on space-saving I support this.

comment:5 Changed 4 years ago by karsten

Status: newneeds_review

The suggested new fields are now implemented in branch task-16750-2 in my public repository and deployed on onionoo.thecthulhu.com.

virgilgriffith, please take a look and let me know here how that feature works for you.

comment:6 Changed 4 years ago by karsten

Resolution: implemented
Status: needs_reviewclosed

Merged and deployed on both Onionoo servers. Closing.

Note: See TracTickets for help on using tickets.