The Feedback Control Algorithm

The NBP feedback control algorithm determines how and when feedback packets are exchanged between edge routers. Feedback packets take the form of ICMP packets and are necessary in NBP for three reasons. First, they allow egress routers to discover which ingress routers are acting as sources for each of the flows they are monitoring. Second, they allow egress routers to communicate per-flow bit rates to ingress routers. Third, they allow ingress routers to detect network congestion and control their feedback generation intervals by estimating edge-to-edge round trip times.

Figure 5: Forward and backward feedback packets exchanged by edge routers

The contents of NBP feedback packets are shown in Figure 5. Contained within the forward feedback packet is a time stamp and a list of flow specifications for flows originating at the ingress router. The time stamp is used to calculate the round trip time between two edge routers, and the list of flow specifications indicates to an egress router the identities of active flows originating at the ingress router. (An edge router adds a flow to its list of active flows whenever a packet from a new flow arrives; it removes a flow when the flow becomes inactive.) In the event that the network's maximum transmission unit size is not sufficient to hold an entire list of flow specifications, multiple forward feedback packets are used.

When an egress router receives a forward feedback packet, it immediately generates a backward feedback packet and returns it to the ingress router. Contained within the backward feedback packet are the forward feedback packet's original time stamp, a router hop count, and a list of observed bit rates, called egress rates, collected by the egress router for each flow listed in the forward feedback packet. The router hop count, which is used by the ingress router's rate control algorithm, indicates how many routers are in the path between the ingress and the egress router. The egress router determines the hop count by examining the time to live (TTL) field of arriving forward feedback packets. When the backward feedback packet arrives at the ingress router, its contents are passed to the ingress router's rate controller, which uses them to adjust the parameters of each flow's traffic shaper.

In order to determine how often to generate forward feedback packets, an ingress router keeps, for each egress router, a timer which determines the frequency of forward feedback packet generation. To maintain an adequate and consistent feedback update interval, the timer repeatedly expires after an interval of time known as the base round trip time. The base round trip time for egress router e, denoted e.baseRTT, is defined as the shortest observed round trip time between the ingress router and egress router e, and it generally reflects the round trip time between the two edge routers when the network is not congested. The value e.baseRTT is calculated by estimating the current round trip time from each arriving backward feedback packet and updating e.baseRTT whenever the current round trip time is less.

Egress routers may also generate backward feedback packets asynchronously. If an egress router does not receive a forward feedback packet from an ingress router within a fixed interval of time (denoted AsynchInterval), it generates and transmits a backward feedback packet to the ingress router. Asynchronously generated backward feedback packets are specially marked by the egress router and are not used by the ingress router to update the round trip time measurement. The reason for asynchronous backward feedback packet generation is to prevent the squelching of congestion feedback when forward feedback packets are delayed or dropped by the network. It also ensures that ingress routers receive frequent rate feedback and are able to respond to congestion even when the distance between edge routers is very large.