Consider a cognitive overlaid network (CON) that has two tiers with different priorities: a primary tier vs. a secondary tier, which is an emerging network scenario with the advancement of cognitive radio (CR) technologies. The primary tier consists of randomly distributed primary radios (PRs) of density n, which have an absolute priority to access the spectrum. The secondary tier consists of randomly distributed CRs of density m = n^y with y greater than or equal to 1, which can only access the spectrum opportunistically to limit the interference to PRs. In this dissertation, the fundamental limits of such a network are investigated in terms of the asymptotic throughput and packet delay performance when m and n approaches infinity. The following two types of CONs are considered: 1) selfish CONs, in which neither the primary tier nor the secondary tier is willing to route the packets for the other, and 2) supportive CONs, in which the secondary tier is willing to route the packets for the primary tier while the primary tier does not. It is shown that in selfish CONs, both tiers can achieve the same throughput and delay scaling laws as a stand-alone network. In supportive CONs, the throughput and delay scaling laws of the primary tier could be significantly improved with the aid of the secondary tier, while the secondary tier can still achieve the same throughput and delay scaling laws as a stand-alone network. Finally, the throughput and packet delay of a CON with a small number of nodes are investigated. Specifically, we investigate the power and rate control schemes for multiple CR links in the same neighborhood, which operate over multiple channels (frequency bands) in the presence of PRs with a delay constraint imposed on data transmission. By further considering practical limitations in spectrum sensing, an efficient algorithm is proposed to maximize the average sum-rate of the CR links over a finite time horizon under the constraints on the CR-to-PR interference and the average transmit power for each CR link. In the proposed algorithm, the PR occupancy of each channel is modeled as a discrete-time Markov chain (DTMC). Based on such a model, a novel power and rate control strategy based on dynamic programming (DP) is derived, which is a function of the spectrum sensing output, the instantaneous channel gains for the CR links, and the remaining power budget for the CR transmitter. Simulation results show that the proposed algorithm leads to a significant performance improvement over heuristic algorithms.