In this paper, we consider bidirectional relay networks in which two users exchange information only via a relay node, i.e., a direct link between both users is not present. We assume that channel state information at the transmitter is not available and/or only one coding and modulation scheme is used due to complexity constraints. Thus, the nodes transmit with a fixed predefined rate regardless of the channel state. In general, the nodes in the network can assume one of three possible states in each time slot, namely, the transmit, the receive, and the silent state. Most of the existing bidirectional relaying protocols assume a prefixed schedule for the sequence in which the states of the nodes are used. In this paper, we abandon the restriction of having a fixed and predefined schedule and consider the selection of the states of the nodes as a degree of freedom that can be exploited for performance optimization. To this end, the relay has to be equipped with two buffers for storage of the information received from the two users. In Part I of this paper, we propose a delay-unconstrained protocol that, based on the qualities of the involved links, selects the optimal states of the nodes in each time slot such that the sum throughput is maximized. In Part II, several delay-constrained protocols are proposed and analyzed. Numerical results show that the proposed protocols significantly outperform the existing bidirectional relaying protocols in the literature.