Home | History | Annotate | Line # | Download | only in quic-design 
      1 QUIC Connection ID Cache
      2 ========================
      3 
      4 The connection ID cache is responsible for managing connection IDs, both local
      5 and remote.
      6 
      7 Remote Connection IDs
      8 ---------------------
      9 
     10 For remote connection IDs, we need to be able to:
     11 
     12 * add new IDs per connection;
     13 * pick a non-retired ID associated from those available for a connection and
     14 * select a connection ID by sequence number and retire that and all older IDs.
     15 
     16 The cache will be implemented as a double ended queue as part of the
     17 QUIC_CONNECTION object.  The queue will be sorted by sequence number
     18 and must maintain a count of the number of connection IDs present.
     19 There is no requirement to maintain a global mapping since remote IDs
     20 are only used when sending packets, not receiving them.
     21 
     22 In MVP, a many-to-1 matching of Connection IDs per Connection object
     23 is required.  Refer third paragraph in [5.1].
     24 
     25 When picking a non-retired connection ID for MVP, the youngest available will
     26 be chosen.
     27 
     28 Local Connection IDs
     29 --------------------
     30 
     31 For local connection IDs, we need to be able to:
     32 
     33 * generate a new connection ID and associate it with a connection;
     34 * query if a connection ID is present;
     35 * for a server, map a connection ID to a QUIC_CONNECTION;
     36 * drop all connection IDs associated with a QUIC_CONNECTION;
     37 * select a connection ID by sequence number and retire that and all older IDs
     38   and
     39 * select a connection ID by sequence number and drop that and all older IDs.
     40 
     41 All connection IDs issued by our stack must be the same length because
     42 short form packets include the connection ID but no length byte.  Random
     43 connection IDs of this length will be allocated.  Note that no additional
     44 information will be contained in the connection ID.
     45 
     46 There will be one global set of local connection IDs, `QUIC_ROUTE_TABLE`,
     47 which is shared by all connections over all SSL_CTX objects.  This is
     48 used to dispatch incoming datagrams to their correct destination and
     49 will be implemented as a dictionary.
     50 
     51 ### Notes
     52 
     53 * For MVP, it would be sufficient to only use a zero length connection ID.
     54 * For MVP, a connection ID to QUIC_CONNECTION mapping need not be implemented.
     55 * Post MVP, funnelling all received packets through a single socket is
     56   likely to be bottleneck.
     57   An alternative would be receiving from <host address, source port> pairs.
     58 * For MVP, the local connection ID cache need only have one element.
     59   I.e. there is no requirement to implement any form of lookup.
     60 
     61 Routes
     62 ------
     63 
     64 A pair of connection IDs identify a route between the two ends of the
     65 communication.  This contains the connection IDs of both ends of the
     66 connection and the common sequence number.  We need to be able to:
     67 
     68 * select a connection ID by sequence number and retire that and all older IDs
     69   and
     70 * select a connection ID by sequence number and drop that and all older IDs.
     71 
     72 It is likely that operations on local and remote connection IDs can be
     73 subsumed by the route functionality.
     74 
     75 ID Retirement
     76 -------------
     77 
     78 Connection IDs are retired by either a [NEW_CONNECTION_ID] or
     79 a [RETIRE_CONNECTION_ID] frame and this is acknowledged by a
     80 RETIRE_CONNECTION_ID or a NEW_CONNECTION_ID frame respectively.
     81 
     82 When a retirement frame is received, we can immediately _remove_ the
     83 IDs covered from our cache and then send back an acknowledgement of
     84 the retirement.
     85 
     86 If we want to retire a frame, we send a retirement frame and mark the
     87 IDs covered in our cache as _retired_.  This means that we cannot send
     88 using any of these IDs but can still receive using them.  Once our peer
     89 acknowledges the retirement, we can _remove_ the IDs.
     90 
     91 It is possible to receive out of order packets **after** receiving a
     92 retirement notification.  It's unclear what to do with these, however
     93 dropping them seems reasonable.  The alternative would be to maintain
     94 the route in a _deletable_ state until all packets in flight at the time
     95 of retirement have been acked.
     96 
     97 API
     98 ---
     99 
    100 QUIC connection IDs are defined in #18949 but some extra functions
    101 are available:
    102 
    103 ```c
    104 /* QUIC connection ID representation. */
    105 #define QUIC_MAX_CONN_ID_LEN   20
    106 
    107 typedef struct quic_conn_id_st {
    108     unsigned char id_len;
    109     unsigned char id[QUIC_MAX_CONN_ID_LEN];
    110 #if 0
    111     /* likely required later, although this might not be the ideal location */
    112     unsigned char reset_token[16];  /* stateless reset token is per conn ID */
    113 #endif
    114 } QUIC_CONN_ID;
    115 
    116 static ossl_unused ossl_inline int ossl_quic_conn_id_eq(const QUIC_CONN_ID *a,
    117                                                         const QUIC_CONN_ID *b);
    118 
    119 /* New functions */
    120 int ossl_quic_conn_id_set(QUIC_CONN_ID *cid, unsigned char *id,
    121                           unsigned int id_len);
    122 
    123 int ossl_quic_conn_id_generate(QUIC_CONN_ID *cid);
    124 ```
    125 
    126 ### Remote Connection ID APIs
    127 
    128 ```c
    129 typedef struct quic_remote_conn_id_cache_st QUIC_REMOTE_CONN_ID_CACHE;
    130 
    131 /*
    132  * Allocate and free a remote connection ID cache
    133  */
    134 QUIC_REMOTE_CONN_ID_CACHE *ossl_quic_remote_conn_id_cache_new(
    135         size_t id_limit   /* [active_connection_id_limit] */
    136     );
    137 void ossl_quic_remote_conn_id_cache_free(QUIC_REMOTE_CONN_ID_CACHE *cache);
    138 
    139 /*
    140  * Add a remote connection ID to the cache
    141  */
    142 int ossl_quic_remote_conn_id_cache_add(QUIC_REMOTE_CONN_ID_CACHE *cache,
    143                                        const QUIC_CONNECTION *conn,
    144                                        const unsigned char *conn_id,
    145                                        size_t conn_id_len,
    146                                        uint64_t seq_no);
    147 
    148 /*
    149  * Query a remote connection for a connection ID.
    150  * Each connection can have multiple connection IDs associated with different
    151  * routes.  This function returns one of these in a non-specified manner.
    152  */
    153 int ossl_quic_remote_conn_id_cache_get0_conn_id(
    154         const QUIC_REMOTE_CONN_ID_CACHE *cache,
    155         const QUIC_CONNECTION *conn, QUIC_CONN_ID **cid);
    156 
    157 /*
    158  * Retire remote connection IDs up to and including the one determined by the
    159  * sequence number.
    160  */
    161 int ossl_quic_remote_conn_id_cache_retire(
    162         QUIC_REMOTE_CONN_ID_CACHE *cache, uint64_t seq_no);
    163 
    164 /*
    165  * Remove remote connection IDs up to and including the one determined by the
    166  * sequence number.
    167  */
    168 int ossl_quic_remote_conn_id_cache_remove(
    169         QUIC_REMOTE_CONN_ID_CACHE *cache, uint64_t seq_no);
    170 ```
    171 
    172 ### Local Connection ID APIs
    173 
    174 ```c
    175 typedef struct quic_local_conn_id_cache_st QUIC_LOCAL_CONN_ID_CACHE;
    176 
    177 /*
    178  * Allocate and free a local connection ID cache
    179  */
    180 QUIC_LOCAL_CONN_ID_CACHE *ossl_quic_local_conn_id_cache_new(void);
    181 void ossl_quic_local_conn_id_cache_free(QUIC_LOCAL_CONN_ID_CACHE *cache);
    182 
    183 /*
    184  * Generate a new random local connection ID and associate it with a connection.
    185  * For MVP this could just be a zero length ID.
    186  */
    187 int ossl_quic_local_conn_id_cache_new_conn_id(QUIC_LOCAL_CONN_ID_CACHE *cache,
    188                                               QUIC_CONNECTION *conn,
    189                                               QUIC_CONN_ID **cid);
    190 
    191 /*
    192  * Remove a local connection and all associated cached IDs
    193  */
    194 int ossl_quic_local_conn_id_cache_remove_conn(QUIC_LOCAL_CONN_ID_CACHE *cache,
    195                                               const QUIC_CONNECTION *conn);
    196 
    197 /*
    198  * Lookup a local connection by ID.
    199  * Returns the connection or NULL if absent.
    200  */
    201 QUIC_CONNECTION *ossl_quic_local_conn_id_cache_get0_conn(
    202         const QUIC_LOCAL_CONN_ID_CACHE *cache,
    203         const unsigned char *conn_id, size_t conn_id_len);
    204 
    205 /*
    206  * Retire local connection IDs up to and including the one specified by the
    207  * sequence number.
    208  */
    209 int ossl_quic_local_conn_id_cache_retire(
    210         QUIC_LOCAL_CONN_ID_CACHE *cache, uint64_t from_seq_no);
    211 
    212 /*
    213  * Remove local connection IDs up to and including the one specified by the
    214  * sequence number.
    215  */
    216 int ossl_quic_local_conn_id_cache_remove(
    217         QUIC_LOCAL_CONN_ID_CACHE *cache, uint64_t from_seq_no);
    218 ```
    219 
    220 ### Routes
    221 
    222 Additional status and source information is also included.
    223 
    224 ```c
    225 typedef struct quic_route_st QUIC_ROUTE;
    226 typedef struct quic_route_table QUIC_ROUTE_TABLE;
    227 
    228 struct quic_route_st {
    229     QUIC_CONNECTION *conn;
    230     QUIC_CONN_ID     local;
    231     QUIC_CONN_ID     remote;
    232     uint64_t         seq_no;        /* Sequence number for both ends */
    233     unsigned int     retired : 1;   /* Connection ID has been retired */
    234 #if 0
    235     /* Later will require */
    236     BIO_ADDR         remote_address;/* remote source address */
    237 #endif
    238 };
    239 
    240 QUIC_ROUTE_TABLE *ossl_quic_route_table_new(void);
    241 void ossl_quic_route_table_free(QUIC_ROUTE_TABLE *routes);
    242 ```
    243 
    244 ### Add route to route table
    245 
    246 ```c
    247 int ossl_route_table_add_route(QUIC_ROUTE_TABLE *cache,
    248                                QUIC_ROUTE_TABLE *route);
    249 ```
    250 
    251 ### Route query
    252 
    253 ```c
    254 /*
    255  * Query a route table entry by either local or remote ID
    256  */
    257 QUIC_ROUTE *ossl_route_table_get0_route_from_local(
    258         const QUIC_ROUTE_TABLE *cache,
    259         const unsigned char *conn_id, size_t conn_id_len);
    260 QUIC_ROUTE *ossl_route_table_get0_route_from_remote(
    261         const QUIC_ROUTE_TABLE *cache,
    262         const unsigned char *conn_id, size_t conn_id_len);
    263 ```
    264 
    265 ### Route retirement
    266 
    267 ```c
    268 /*
    269  * Retire by sequence number up to and including the one specified.
    270  */
    271 int ossl_quic_route_table_retire(QUIC_ROUTE_TABLE *routes,
    272                                  QUIC_CONNECTION *conn,
    273                                  uint64_t seq_no);
    274 
    275 /*
    276  * Delete by sequence number up to and including the one specified.
    277  */
    278 int ossl_quic_route_table_remove(QUIC_ROUTE_TABLE *routes,
    279                                  QUIC_CONNECTION *conn,
    280                                  uint64_t seq_no);
    281 ```
    282 
    283 [5.1]: (https://datatracker.ietf.org/doc/html/rfc9000#section-5.1)
    284 [active_connection_id_limit]: (https://datatracker.ietf.org/doc/html/rfc9000#section-18.2)
    285 [NEW_CONNECTION_ID]: (https://datatracker.ietf.org/doc/html/rfc9000#section-19.15)
    286 [RETIRE_CONNECTION_ID]: (https://datatracker.ietf.org/doc/html/rfc9000#section-19.16)
    287 [retired]: (https://datatracker.ietf.org/doc/html/rfc9000#section-5.1.2)
    288