Methods and apparatus related to a peer to peer wireless communications system supporting the association of multiple connection identifiers with a single connection between a pair of wireless terminals are described. A differentiated quality of service is supported by assigning different numbers of connection identifiers to different connections. The number of connection identifiers assigned to a wireless terminal pair for a connection is a function of one of: data rate, priority information, and quality of service information. Being allocated a higher number of connection identifiers results in being allocated a higher number of traffic transmission request resources, thus increasing the likelihood that the connection is permitted to use a traffic transmission segment. The allocation of connection identifiers is performed in a distributed manner in which handshake signaling occurs between a wireless terminal pair seeking to establish a connection, e.g., as part of a multi-step paging scheme.