In this paper, we focused on solving the perturbed four-banded linear system derived from the traffic process associated with a Markovian queueing model. Utilizing the spectral decomposition of circulant and skew circulant matrices, we computed the product of Toeplitz inversion and a vector, leading to a decomposition algorithm for perturbed four-banded linear systems. This decomposed Toeplitz system features multiple right-hand terms, significantly reducing computational complexity through Toeplitz inversion. Additionally, we introduced an algorithm based on banded LU decomposition, resulting in a banded linear system with multiple right-hand terms, where the sparsity of the banded LU decomposition is pivotal. To evaluate the algorithm's performance, we presented two examples in numerical simulations.