An optimal circuit allocation problem for all-optical circuit-switched backbone networks with average packet delay cost criterion is considered. Multiple classes of traffic flows arrive at the network edge routers, where they can be queued until an end-to-end optical circuit can be allocated. Assuming fluid traffic and circuit allocation of fixed periods, a lower bound on the optimal average packet delay is derived and the cost of two allocation policies are evaluated exactly. The cost of both policies are demonstrated for a variety of deterministic and random networks and are compared with the lower bound.