A method for requesting a bandwidth by a message having a variable format is disclosed. The method includes determining a bandwidth request type according to a size of an uplink bandwidth requested by a mobile station, generating a bandwidth request message having a header format according to the determined bandwidth request type, and transmitting the bandwidth request message to a base station. The determined bandwidth request type is one of a bandwidth request per connection, a bandwidth request per Quality of Service (QoS), and a bandwidth request per mobile station.