Inferring a Network Congestion Map with Zero Traffic Overhead - PDF

Please download to get full document.

View again

of 10
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report



Views: 4 | Pages: 10

Extension: PDF | Download: 0

Related documents
Inferring a Network Congestion Map with Zero Traffic Overhead Florin Dinu T. S. Eugene Ng Computer Science Department, Rice University Abstract This paper proposes a purely passive method for inferring
Inferring a Network Congestion Map with Zero Traffic Overhead Florin Dinu T. S. Eugene Ng Computer Science Department, Rice University Abstract This paper proposes a purely passive method for inferring a congestion map of a network. The congestion map is computed using the congestion markings carried in existing traffic, and is continuously updated as traffic is received. Consequently, congestion changes can be tracked in a real-time fashion with zero traffic overhead. Unlike active congestion reporting methods, our novel passive method is more robust during periods of congestion because there are no congestion report messages that could be lost and existing congestion is never aggravated. Our solution has several applications ranging from informing IP fast re-route algorithms and traffic engineering schemes to assisting in inter-domain path selection. I. INTRODUCTION Information about congestion is of great importance to a network. Congestion indicates a severe degradation of the service level provided by the network and even a possible danger to the stability of the basic routing functionality [21]. Several distributed router level algorithms can benefit from congestion information. For example, IP fast re-route algorithms are currently ignorant of congestion [18][17][22]. It is important that these algorithm be extended to properly take network congestion into account because their routing decisions could cause congestion and also the efficiency of their decisions is impacted by existing congestion. Automated verification mechanisms that use multiple vantage points to verify the correct functioning of routers [19][15][24] can use congestion information to reason whether packet loss was caused by congestion or by errors in protocol implementations. Distributed traffic engineering algorithms [13] can use congestion information to balance the load in the network. At the inter-domain level, congestion information can be leveraged in the selection of suitable inter-domain routing paths. Our novel proposition is that a congestion map of the network can be locally obtained at any router by processing the congestion information carried in the existing traffic that passes through that router. No extra traffic is added into the network. Our solution combines path level congestion information with routing information. Today, both types of information can be obtained from standardized protocols. First, the explicit congestion notification (ECN) protocol alongside an active queue management (AQM) protocol enables existing traffic to carry aggregate, path level congestion severity information. We present a complete method for inferring path level congestion information by leveraging the congestion markings from ACK and data packets. Subsequently, information from a link-state intra-domain routing protocol can be used to break down the path level congestion information into detailed link level congestion location and severity information. At the inter-domain level our solution allows a local border router to extend its congestion map with aggregate inter-domain path congestion information. In our solution, at a border router, each reachable remote network is abstracted as a virtual link connected to the border router. The congestion inference method for a virtual link is precisely the same method used in the local autonomous system (AS). A congestion map is the union of all the link level and path level congestion information inferred at a router. Our inference method is useful in inter-domain scenarios where, due to administrative boundaries, routers in different ASes cannot be actively queried for their congestion level. In addition, even in the local AS, our method has several important advantages compared to methods that rely on active congestion reporting. First, our method does not aggravate congestion episodes. In contrast, active congestion report messages increase the severity of congestion episodes. Even more, with our solution, routers also have the flexibility to choose different sampling granularities locally without affecting the network traffic. In contrast, to obtain fine-grained real-time congestion information, an active reporting method must resort to increasing the reporting frequency, further increasing the traffic overhead and exacerbating existing congestion. This weakness of active congestion reporting is especially detrimental because precisely during congestion periods fine-grained real-time congestion information is most useful. Second, our method is more robust during congestion periods since there are no report messages that could be lost because of congestion. Third, our method computes a fine-grained congestion map that is continuously updated in real-time as traffic is received, yet incurs zero traffic overhead. We test the accuracy of our method against several important factors using numerical analysis and ns-2 simulations. The factors include sudden variations in the congestion level, the type of AQM used and multiple consecutive congestion points. We also analyze the effect of factors that can distort the sequences of packet markings. Despite the influence of all these factors our solution can infer congestion at a remote link with good accuracy and at fine time scales. The rest of the paper is organized as follows. II describes prerequisites and overviews the solution. III discusses the inference of aggregate path level congestion. IV details the computation of link level estimates. VI and V evaluate the accuracy of our method. VII discusses our solution further, VIII presents related work and IX concludes. II. OVERVIEW Prerequisites: Our solution infers congestion inside a local AS and on the inter-domain paths that take traffic to and away from the AS. For local inference our solution uses the traffic that originates in and is destined to the same AS. For interdomain inference the inter-domain traffic that has either the source or destination in the local AS is used. To have their congestion level inferred by our solution, local routers need an AQM algorithm [12][5][9] and the ECN protocol [2] for explicit congestion marking. The more AQM/ECN enabled routers are present in the network the more complete the inference is. The AS also needs to use a link state intradomain routing protocol (e.g. OSPF). At the inter-domain level, as long as the routers at strategic points most susceptible to congestion (e.g. traffic exchange points) are AQM/ECN enabled, our solution will provide benefit. Background: An AQM enabled router may mark data packets instead of dropping them. Specifically, the AQM algorithm [12][5][9] at a router computes a congestion measure for the router s outgoing links. This measure can be as simple as a function of the router queue size (e.g. RED [12]) or a more complex expression based on incoming traffic rate and available bandwidth (e.g. REM [5]). The router can then mark each outgoing data packet probabilistically, as a function of the congestion measure of the link they are sent on. ECN [2] is the protocol that enables congestion marking. It makes use of four packet header bits: ECN-Echo (ECE) and Congestion Window Reduced (CWR) in the TCP header and ECT (ECN-Capable Transport) and CE (Congestion Experienced) in the IP header. ECN capable data packets have the ECT bit set. Congested routers can mark such packets by setting the CE bit. When receiving a data packet with the CE bit set, a TCP destination sets the ECE bit in the subsequent ACK and continues to do so for all following ACKs until it receives a data packet with the CWR bit set. The CWR bit is set by a TCP source to signal a decrease in the congestion window. This can happen as a result of receiving an ACK with the ECE bit set or for other reasons. The ECN markings on the two halves of a TCP connection are independent. Definitions and notations: We use the term data or forward path to refer to the path taken by data packets and ACK path to refer to the path taken by ACK packets. We call a packet with the ECE bit set a marked ACK packet and a packet with the CE bit set a marked data packet. Unmarked packets do not have those bits set. As explained, a TCP receiver can mark multiple ACKs as a result of receiving one marked data packet. Consequently, the sequence and percentage of the markings in the data packets can be modified when the TCP receiver echoes the markings to the ACKs. We refer to this process as the alteration caused by the TCP receiver. For brevity we use MP to denote marking probability and LMP and PMP to denote link level and path level marking probabilities. A group of unmarked ACKs is a maximal sequence of consecutive unmarked ACKs. A group of unmarked ACKs of size zero is considered to appear whenever the echoing of markings in ACKs finishes but has to resume immediately. This situation arises when a data packet has both the CE and CWR bits set. Overview of the solution: Our solution allows a router to locally infer the congestion severity at other routers and network paths. In this paper we use the MP as the representation of congestion severity because the MP is common to several AQM algorithms. Our solution applies to any network topology on a perpath basis. Routers first analyze the data and ACK markings received on separate network paths. The analysis of data packet markings leverages the percentage of marked data packets and allows congestion inference to be performed on the path taken by the data packets from the source until the analyzing router. The analysis of ACK markings relies on the size of the groups of unmarked ACKs and allows congestion inference on the entire forward path of flows. This path level analysis yields aggregate PMPs. After computing PMPs, a router can leverage link state routing information which is reliably disseminated and is sufficient to allow each router to compute the hop level path that a packet takes from a source to a destination. Using both PMPs and the hop level path description, aggregate PMPs for increasingly shorter paths can be derived. Thus, LMPs can also be computed with this approach. The set of all PMPs and LMPs inferred by a router forms a congestion map. Inter-domain congestion inference: Aggregate congestion information for inter-domain paths can be computed with the same mechanism that applies to the problem of congestion inference for the local AS. Since one AS typically has no topology information about other ASes, we abstract the path from a local border to an external destination as one virtual link connected to the border router. Local border routers obtain aggregate congestion information for these virtual links. In this inter-domain scenario, data packet congestion markings convey congestion information about ingress routes. ACK path congestion markings give the local border routers congestion information about egress routes. The obtained congestion information can be leveraged when selecting good inter-domain paths and when advertising paths to neighbors. One advantage of our solution is that as re-routing occurs outside the local AS on an inter-domain path, our solution always tracks the congestion on the currently used path. Given the large number of destination reachable in the inter-domain, an operator may wish to restrict the number of destinations for which the inference is performed or can perform inference on demand. For the rest of the paper we consider that an AS network topology includes these virtual links. As a result of applying our solution to this topology both the detailed congestion map of the local AS as well as the aggregate inter-domain path congestion information will be obtained. III. INFERRING PATH LEVEL CONGESTION INFORMATION In this section, we describe the initial building block for obtaining a congestion map of the network: the inference of PMPs from packet markings. PMPs can be obtained from either data or ACK markings. However, the analysis of these two types of markings presents different challenges. In this Fig. 1. Sampling and estimation intervals paper we solve the more difficult problem of ACK based inference. ACK based congestion inference is vital because it conveys information about downstream router paths, exactly the paths that carry forwarded traffic. A. Estimation and Sampling Intervals Fig. 2. The computation of a sample Our inference solution uses two parameters: a sampling interval (SI) and an estimation interval (EI). For each SI, a single sample is obtained from all the markings received during the SI. Choosing a very low SI value may result in too few packet markings to compute a meaningful sample. On the other hand, a large SI value biases the sample towards the periods where bursts of packets are received. One cause for these bursts is the burstiness inherent in the use of TCP. We found that an SI on the order of the RTT of the network performs well because it works at the scale of TCP s burstiness while at the same time providing enough packets for the inference. The EI represents the granularity at which inference is performed. The inferred LMPs and PMPs represent congestion at the scale of an EI. Figure 1 depicts the relationship between the EI and the SI. An EI is a multiple of an SI. For each EI, an estimate of the congestion severity is computed by averaging all the samples obtained during the EI. The trade-off present in choosing an EI value will become clear after we describe our solution. B. Data Packet Based Inference The data packet markings are exactly the markings set by routers. They are never altered until the data packets reach the destination. To compute a sample for a path using data packet markings a router counts the total number of data packets and the total number of marked data packets it receives across all flows traversing the path. Using these two counters, the ratio of marked data packets is obtained. This ratio serves as the sample for an SI. C. ACK Packet Based Inference The ACK markings are the result of the echoing performed by the TCP receiver. The challenge is to infer accurate congestion estimates despite the alteration caused by the echoing. At first glance, computing a sample using ACK markings could also leverage the percentage of marked ACKs. On closer inspection, such a solution is unfortunately inadequate because the alteration of the markings can cause a significant overestimation of the MP. In [1] we use a theoretical model that quantifies the effect of the alteration. We find that the overestimation can be severe. For a TCP window of 8 packets and a real MP of.15 the inferred MP overestimates by a factor of 4 [1]. In this section, we present our solution for inference using ACK packets. The key insight is that groups of unmarked packets can be leveraged instead of individual packet markings. Using the groups allows meaningful samples to be computed despite dealing with the altered versions of the initial congestion markings. Figure 2 depicts our congestion inference solution. Routers monitor a limited number of TCP flows for each network path. In the figure, as a simple illustration, 4 out of many flows are monitored. During each SI, the length of each group of unmarked ACKs in each monitored TCP flow is measured. Then, an average group length is computed across all the monitored flows. Let q be this average size, p be the marking probability and n the possible size of groups of unmarked ACKs ranging from to. The relation between q and p is: q = n= n (1 p) n p = 1 p p After q is obtained from counting the groups of unmarked ACKs, the sample p can be derived using equation (1). Monitoring flows: Flows constantly begin and finish, therefore the set of monitored flows needs to be periodically refreshed. In this paper, we refresh the set of monitored flows at the beginning of every new EI by randomly selecting a new set of flows. If desired, other refresh intervals can also be used. For simplicity, in this paper, for every new EI we remove the information computed for the previous EI. A simple extension to our solution can allow information to be shared across EIs for flows that are chosen for monitoring in consecutive EIs. At the beginning of each EI, the first few samples are not computed. Those first few SIs serve only to begin selecting a number of flows to monitor. In our evaluation we find that selecting flows during the first 2 SIs is sufficient for good accuracy. The samples from the subsequent SIs are averaged to obtain the estimate. During these subsequent SIs flows can still be chosen for monitoring until a desired maximum threshold is reached. These flows are used for inference starting with the SI following the SI where they were first encountered. Incomplete groups: Groups of unmarked ACKs can span multiple SIs. During one EI, these groups are counted in the SI where they end. Even so, incomplete groups of unmarked ACKs may be encountered at the start or end of an EI. Such groups begin or end in a different EI. Since we treat each SI separately, the correct size of the incomplete groups cannot (1) be correctly measured and this can skew the results. Thus, incomplete groups are not considered for inference. It should now become clear why choosing very small EI values may impact accuracy. If for example EI = SI, an important percentage of groups will be incomplete and cannot be used by the inference. On the other hand, if the EI contains multiple SIs, fewer incomplete groups will appear since many larger groups will end and will be used for the inference. Identifying groups of size zero: Our solution can leverage groups of unmarked ACKs of size zero. Recall that such groups are considered to appear when the CWR data packet that signals the TCP receiver to stop setting the ECE bit is also marked. To correctly identify groups of size zero a router remembers the sequence numbers of the last byte of the CWR packets it observes in the each of the monitored flows. The ACK corresponding to a CWR packet can be identified by its sequence number which is the first value larger than the remembered value. If both the ACK corresponding to a CWR packet and the previous ACK are marked, this signals the presence of a group of unmarked ACKs of size zero. To ensure that every ACK packet can be checked against its corresponding data packet, for each flow and EI, the sequence number of the first detected data packet is stored and only the ACKs with a greater sequence number are considered. Benefit of groups of size zero: The use of the groups of size zero benefits the accuracy of our solution. As described, to use such groups, routers must be both on the forward and on the ACK path of a flow. However, it is important to note that our solution still works without the groups of size zero. If the groups of size zero are not used, a small change is required to (1). In that case, the MP can be computed as the inverse of the average group size of groups of positive size. The entire derivation is available in [1]. The increase in accuracy when using groups of size zero comes from the fact that in environments with high levels of congestion the number of groups of unmarked ACKs of size greater than zero alone may not provide statistical significance. The reason is that the ratio of groups of size zero is proportional to a path s MP and therefore becomes significant when the MP is large. Using groups of size zero does not, however, strictly require routing to be symmetric. If the first-hop and last-hop router for a flow are unique, as is usually the case, those routers will always be able to take advantage of the groups of size zero, irrespective of the degree of asymmetry of the entire end-to-end path. Storage overhead: The state that routers need to store for our inference solution is small and comprised only of simple counters. For each flow, a counter keeps track of the size of the current group of unmarked ACKs. Over all flows, one counter holds the total size
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks