Methods and apparatus related to scheduling and/or utilization of air link traffic resources are described. A connection identifier is associated with priority with regard to use of an air link resource, e.g., a peer to peer traffic segment which is in contention. A particular connection may acquire and hold one or multiple connection identifiers. In some embodiments, the priority associated with a particular connection identifier is intentionally varied in a set of traffic slots. In some such embodiments, there is priority randomization from slot to slot. In one such implementation there is a statistically uniform average priority between the different connection identifiers over the recurring structure. Such an implementation facilitates access to traffic segments to a wide range of users, yet allows for differentiation with regard to the amount of access as a function of the number of connection identifiers being held by a particular connection.