The composer cache greatly speeds up your composer part of the build by only going to Github for new downloads. When combined with test lowest, current, and highest possible on Travis you only reach out to Github for new versions. Most likely to happen during the highest possible set of builds, but also when you've updated composer.*. This normally isn't an issue unless you hit Github's rate limit. And since composer is running on a 'public' travis box with a 'public' IP address that has been use by many builds before it there is a very very high chance it already hit the 60 requests per hour limit.

Obsolete post

Github recently made a change to their API removing the need to do this.

The setup

To counter this problem we have to set a Github authentication token as environment variable in Travis for each project. And update .travis.yml so the token is used by composer.

Obtaining a Github token

To get started log into Github and go to settings:

Once your on your settings page go to Personal access tokens and click the Generate new token button. On the next screen make sure no scope is checked. (As Christophe pointed out in the comments public repositories are readable publicly anyway so no need for any extra scopes.)

Add token to Travis

Now that we have a token go to the project you want to use it with on Travis and open the settings page:

Create a new environment variable named GH_TOKEN and the Github token you generated earlier as its value:

Updated .travis.yml

The last step in this is to add composer config github-oauth.github.com ${GH_TOKEN} to your .travis.yml. For example in my case, I've wrapped it in an if to only set it when the environment variable is present:

## Update composer and run the appropriate composer command
before_script:
  - composer self-update -q
  - if [ -n "$GH_TOKEN" ]; then composer config github-oauth.github.com ${GH_TOKEN}; fi;
  - if [ -z "$dependencies" ]; then composer install; fi;
  - if [ "$dependencies" = "lowest" ]; then composer update --prefer-lowest -n; fi;
  - if [ "$dependencies" = "highest" ]; then composer update -n; fi;
  - composer show -i

Conclusion

Setting up your TravisCI builds with a Github auth token will make sure you can always download the required version of a package. (Unless you manage to make more then 5,000 authenticated requests in an hour.)