Projects/Rule based sendto kdc loop

This is an early stage project for MIT Kerberos. It is being fleshed out by its proponents. Feel free to help flesh out the details of this project. After the project is ready, it will be presented for review and approval.

This project is an internal improvement and should have minimal externally visible impact, although it may enable future improvements to the sendto_kdc loop.

Background

The current sendto_kdc loop (as modified by Projects/HTTP_Transport) is defined by a narrative in k5_sendto:

1. Resolve each server and send to each of its addresses using the preferred RFC 4120 transport (unless it's an HTTPS server, in which case use HTTPS). After each request, wait one second for answers.
2. If there is a non-preferred RFC 4120 transport (that is, we are trying both UDP and TCP in some order), re-send to each RFC 4120 server using the non-preferred transport. After each request sent, wait one second for answers.
3. Wait two seconds for answers.
4. For every UDP request we sent, re-send it. After each repeated UDP request, wait one second for answers.
5. Wait four seconds for answers.
6. Repeat steps 4 and 5, except wait eight seconds for answers instead of four.
7. Stop and return failure.

"Wait N seconds for answers" means to select or poll for activity on all outstanding addresses for the desired amount of time, with the following behaviors on events:

• If we receive an answer (and it is not a KDC_ERR_SVC_UNAVAILABLE error), stop and return the answer to the caller.
• If a TCP connection is accepted, extend the waiting time until ten seconds from when the connection was accepted.
• If a TCP connection is writable and we have request data to write, write it.
• If we receive a network error from an address, remove it from the list of outstanding addresses.
• If the list of outstanding addresses becomes empty due to network errors, stop waiting.

(Currently we continue waiting on an address after a KDC_ERR_SVC_UNAVAILABLE error; this is [krbdev.mit.edu #7899]. We should invalidate the address as if we received a network error, and possibly also invalidate other addresses for the same server hostname. That bug should be relatively easy to fix in any expression of the sendto_kdc loop and is orthogonal to the goals of this project.)

This expression has several problems:

• It is an obstacle to providing non-blocking KDC communication APIs, because long linear narratives are more difficult to break down into state machines. (The lack of standard non-blocking DNS on Unix-like platforms and Windows is another obstacle.)

• It behaves suboptimally in some corner cases. For example, if we send to server 1, wait one second, send to server 2, and immediately get a network error from server 2, we continue to wait the rest of the second.

• If we want to preserve any connection state memory across several send operations to the same realm (e.g. fallback-to-master, fallback-to-TCP, or a preauthenticated request), it is difficult to integrate that into a narrative expression of the loop; all we can really do is restart the narrative from step 1 with an adjusted server state.

• The total wait time increases by roughly three seconds per KDC address, which isn't really necessary.

Proposal

The following rules approximate the behavior of the above narrative. These rules apply each time select or poll wakes up.

• Write any pending request data we can. Read any pending data from server addresses. If we receive a complete answer and it is not a KDC_ERR_SVC_UNAVAILABLE error, stop and return the answer. If we encounter a network error on an address, remove it from the list of outstanding addresses.
• If there are still servers or server addresses which we haven't contacted, compute a next request wait time, which is the maximum of:
  • One second from the last time we sent an initial request to an outstanding address
  • Ten seconds from the connection-accept time of an outstanding TCP address
• If the current time exceeds the next request wait time, send an initial request to the next address, and re-compute the next request wait time.
• For each outstanding UDP address with fewer than three transmissions, compute a retransmit wait time, which is two seconds after the first transmission or four seconds after the second. If the current time exceeds the retransmit time, retransmit the request.
• Compute a timeout, which is the maximum across all oustanding addresses of:
  • For UDP addresses with fewer than three transmissions, infinity
  • For UDP addresses with three transmissions, eight seconds from the third retransmission
  • For TCP connections which have not been accepted, fourteen seconds from the connection request
  • For TCP connections which have been accepted, ten seconds from the accept time.
• If the current time exceeds the timeout, stop and return failure.
• Wait for events until the minimum of the next request wait time, the retransmit times, and the timeouts computed above.

The step "send an initial request to the next address" may require resolving a server name. If a server name is to be used for both TCP and UDP, do not contact the less-preferred transport until all servers have been resolved and all of their addresses contacted using the most-preferred transport.

Behavior differences from the narrative expression are relatively slight, but include:

• We begin retransmitting UDP requests before we finish contacting all of the servers. The retransmission schedule for a UDP request does not depend on the number of servers.
• The total wait time only increases by one second per KDC address.
• If we receive a network error on an outstanding address, that address no longer impacts the wait time before contacting a new server or timing out entirely.