Network　Functions　Virtualization　(NFV)　is　a　promising　technology　to　provide　packet　processing　services.　However,　dynamic　capacity　provisioning　to　meet　different　tenants’　time-varying　demands　under　service-level　agreements　is　still　a　challenge　for　NFV　service　providers.　The　existing　works　generally　perform　the　scaling-in/out　actions　for　separate　service　chains　and　cannot　promise　a　guarantee　for　the　total　processing　time.　Therefore,　we　propose　Palm,　a　proactive　auto-scaling　framework　to　minimize　the　resource　consumption　while　enforcing　latency　guarantees　for　multiple　intersecting　service　chains.　We　first　leverage　the　classed　Jackson　network　model　to　analyze　the　packet　processing　latency.　Then,　a　log-linear　Poisson　auto-regression　method　is　employed　to　predict　each　tenant＇s　packet　arrival　rate.　Based　on　the　prediction　result,　we　perform　the　capacity　adjustment　actions　and　update　the　flow　forwarding　policies.　We　formulate　the　capacity　provisioning　task　as　a　nonlinear　integer　programming　problem　and　propose　an　evolution　based　algorithm　to　tackle　it.　To　simplify　the　auto-scaling　problem,　we　develop　an　adaptive　algorithm　to　divide　the　NFV　cloud　into　persistent　and　temporary　layers.　Our　comprehensive　experiments　show　that　Palm　achieves　a　steady　low-latency　performance　at　a　lower　cost　compared　with　the　state-of-the-art　dynamic　scaling　strategies.　©　2020