In this dissertation work we focus is on misbehaviours that make the stateless solutions less robust than stateful solutions. In particular, focus was on packet labels being corrupted. We do not explicitly address misbehaviours for which stateful solutions are equally vulnerable, such as IP address spoofing or a user gaining unfair advantage by opening a large number of parallel connections. However, we note that even in the presence of these misbehaviours our solution may perform better than stateful solutions such as Fair Queueing, since by containing the bad flows, it makes more bandwidth available to well-behaved flows. We assume that a flow is defined by a subset of fields in the IP header. Without loss of generality, in this dissertation work, assumption is that a flow is defined by the source and destination IP addresses. This solution has the following goals and properties:
(1) The main goal of a router in real time is to protect the consistent flows, rather than identifying and containing misbehaving flows. This allows us to optimize the algorithms for identifying âlargeâ inconsistent flows which have the most impact on the well-behaved traffic. Catching small inconsistent flows that have a negligible impact on the well-behaved flows is only of secondary importance. In particular, inconsistent flows whose arrivals rate are less than the fair rate have no effect on the other traffic.
(2) In a well-engineered system, access routers end up containing most of the misbehaving flows. This assumes that access routers have enough resources to contain all inconsistent flows. We believe this a reasonable assumption given the fact that access routers have much lower capacity, and are traversed by much fewer flows2 than core routers.
(3) If the number of misbehaving flows traversing a router exceeds the number of flows the router can contain3, the routerâs primary goal is to protect the down-stream traffic. The router may take this action even if this means hurting well-behaved flows that traverse that router. The goal is to protect the rest of the network from a region âinfectedâ with many misbehaving flows.
(4) Once a router identifies an inconsistent flow, it thereafter contains it. The containment procedure is orthogonal to the identification mechanism. For instance, the goal of containment can be to compensate for the extra service received by the inconsistent flow before being caught, or to severely punish the flow to give users incentive to well-behave. At the limit an inconsistent flow can be blocked.
(5) Each router operates independently, and does not make any assumption about the algorithms implemented by other routers. This makes our architecture both robust and incrementally deployable. Given property (2) and that the spectrum of usage in the Internet is heavy-tailed , we expect a core router to be traversed by relatively few âlargeâ inconsistent flows. Since our main focus is to detect and contain these flows, core routers donât need to maintain large amounts of state. Finally, it might be useful to have an additional mechanism that retroactively identifies low-bandwidth/short-live misbehaving flows. This allows us to eventually identify a malicious user, and punish it at a later time (e.g., by administrative means). One way to implement such a mechanism is to inspect traffic logs off-line; however, the design of such mechanisms is orthogonal to this work.
4. SELF-VERIFYING CSFQ (SV-CSFQ)
This chapter presents a solution that addresses the limitations of CSFQ, called self-verifying CSFQ (SV-CSFQ). At the heart of our solution is the router ability to identify and contain inconsistent flows. Since only downward-inconsistent flows can deny service to other flows, our focus is to identify those flows. Unless otherwise specified, in the remainder of this work, we will refer to downward-inconsistent flows simply as inconsistent flows. The ability of identifying inconsistent flows removes the need of trusting the state in the packet headers. Thus, the edge is no longer confined to the trusted boundaries. At the limit, the edge can be pushed all the way to the end-hosts. In this case, our solution no longer differentiates between edge and core routers, so it eliminates the need for router configuration. In addition, the ability to transcend trusted boundaries makes our solution highly scalable, while the flow identification and containment makes it robust.
To identify inconsistent flows, SV-CSFQ routers implement flow verification. Flow verification consists of three phases: (1) randomly select a flow, (2) re-estimate the flowâs rate, and (3) check whether the re-estimated rate is within a predefined threshold from flowâs packet labels. If yes, the flow is declared consistent; otherwise the flow is declared inconsistent. If a flow is declared inconsistent, the router starts to contain that flow. Flow containment involves relabelling the flow packets with a label that exceeds the actual flow rate. This guarantees that a contained flow will receive no more than its fair rate. Containing a flow has two immediate implications. First, the flow will no longer affect consistent traffic at downstream routers. Second, if the flow was contained by a downstream router, that router will eventually release the flow once it notices that the flow has become consistent. As a result, in steady state, only access (edge) routers will maintain state for inconsistent flows.
To see why, consider an inconsistent flow that traverses two routers A and B, in this order. Assume that B identifies the flow first. After some time, A also identifies the flow and contains it. By containing the inconsistent flow, A transforms the inconsistent flow into a consistent one. In turn, as soon as it notices that the flow is no longer inconsistent, B will release the state of the flow. Thus, in the end, A will be the only one to contain and maintain state for the inconsistent flow. The pseudo-code of the flow verification algorithm is shown in Figure 4. Each router maintains two separate tables per output interface: one for the verified flows, called (VerifyTable), and one for the contained flows, called (ContainTable). Upon a packet arrival, the router checks whether the packet belongs to a flow that is already being verified or contained. If not, and if there is room in VerifyTable, the router decides to start verifying the flow with probability p. In our implementation, we set p to 0.5. In practice, every router can choose p independently. This randomness makes it very difficult, if not impossible, for an attacker to evade the verification algorithm. If the router decides to verify a flow, it creates an entry for that flow in VerifyTable.
If the flow is already being verified, the router checks whether the flow is consistent. If yes, the flow is removed from VerifyTable. If the flow is inconsistent, the flow is transferred from VerifyTable to ContainTable.4 Once a flow is contained, the router limits its service rate, and updates the labels in its packets. If a contained flow becomes consistent again, the flow