CLAIM FOR PRIORITY TO RELATED APPLICATIONS This application claims the benefit of U. S. Provisional Patent Application serial No. 60/356,976, filed on February 14, 2002, entitled"Method for Protecting a Network Site from Denial of Services While Allowing Access by an Authorized Distributed Set of Clients,"which is hereby incorporated by reference in its entirety herein.

COMPUTER PROGRAM LISTING A computer program listing is submitted in the Appendix, and are incorporated by reference in their entirety herein.

COPYRIGHT NOTICE A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by any one of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND OF THE INVENTION Field Of The Invention This invention relates to systems and methods for protecting against denial of services on a network, and more particularly to a system and methods for routing packets between authorized clients and a target while denying access to unauthorized users.

Background The World Wide Web (Web) is increasingly being used for diverse tasks, such as banking, consumer purchasing, stock quotes and trading, and real-time communication. The wide availability of high-quality browsers and servers, as well as programmers'and users'familiarity with the tools and concepts behind web browsing ensure that the more new services and uses will be found. hi the immediate aftermath of the September 11,2001 events in New York City, for example, the Internet was used to facilitate communication between family members, as the phone network was overwhelmed. The Internet may be increasingly used as a communication medium for crisis and emergency response teams, especially when using a wireless network substrate. In particular, the network would be used to protect communications between widely dispersed"static"sites (e. g. , various federal, state, and city agencies) and (semi-roaming) stations and users. The communication path between the various sites and the emergency response teams (ERTs) needs to be kept clear of interference; a denial of service (DoS) attack on such a network could seriously disrupt the rescue and recovery effort, at minimal cost and danger to the attacker.

Thus, the problem arises of securing a communication service on top of the existing IP infrastructure from DoS attacks. A consideration in addressing this problem is that there is a subset of clients scattered throughout the wide-area network who require access to a particular destination that should otherwise be secured. An example of such a destination is a database that maintains timely or confidential information such as building structure reports, intelligence, or strategic information.

Users in the field, e. g. , emergency workers, government agents, police, etc. , should be

able to access this information from any network address, i. e. , any IP address, within the wide-area network, since it is not always possible to predict their locations when emergencies strike.

Another consideration in addressing this problem is that there is a set of users, e. g.,"attackers,"that want to prevent access to this information, and will launch DoS attacks upon any network points to help them achieve this goal. The goal of the attackers is to identify any"pinch"points in the communications substrate and render them inoperable by flooding them with large volumes of traffic. Such DoS attacks may take many forms, depending on the resource the attacker is trying to exhaust. For example, an attacker can try to cause the web server to perform excessive computations, or exhaust all available bandwidth to and from the server. In all cases, the goal of a DoS attack is to deny use of the service to other users. Such an attack can prove particularly damaging to time-or life-critical services (such as, e. g., tracking the spread of a real-world epidemic). For less critical service providers, an attack which persists over several days may nevertheless force a target of an attack out of business.

Of particular interest are link congestion attacks, whereby attackers identify any"pinch"points in the communication substrate and render them inoperable by flooding them with a large volume of traffic. An example of an attack point is the location (network address) of the destination that is to be secured, or the routers in its immediate network vicinity. By sending enough traffic, the last few links to the destination may become congested and drop all other traffic.

One approach for mitigating DoS attacks against information carriers i to massively replicate the content being secured around the entire network. To prevent access to the replicated information, an attacker must attack all replication points throughout the entire network, which is considerably more difficult than attacking a small number of, often co-located, servers. Replication is a promising means to preserve information that is relatively static, such as news articles.

Replication is less promising for data which may be dynamic by its very nature (e. g., live audio or video stream). Another concern is the security of the stored information: engineering a highly-replicated solution without leaks of information is a challenging endeavor.

Other approaches have been proposed to protect against or mitigate the effects of DoS attacks, such as, e. g. J. Ioannidis and S. M. Bellovin,"Implementing Pushback: Router-Based Defense Against DDoS Attacks,"Proceedings of the Network and Distributed System Security Symposium (NDSS), February 2002; D.

Dean, M. Franklin, and A. Stubblefield, "An Algebraic Approach to IP Traceback, Proceedings of the Network and Distributed System Security Symposium (NDSS), pages 3-12, February 2001; and S. Savage, D. WEtherall, A. Karlin, and T. Anderson, "Network Support for IP Traceback,"ACM/IEEE Transactions on Networking, 9 (3): 226-237, June 2001. However, these mechanisms typically focus on detecting the source of DoS attacks in progress, and then countering them, typically by"pushing"some filtering rules on routers as far way from the target of the attack (and close to the source) as possible. Such approaches are accordingly considered "reactive. "These approaches have the advantage that they are conceptually simple to produce a protocol that will be used by a relatively small subset of nodes on the internet, i. e. , ISP routers, as opposed to requiring the introduction of new protocols that must be deployed and used by end-systems. These approaches also have the advantage that these mechanisms are fairly transparent to protocols, applications, and legitimate users.

These reactive approaches by themselves also have several drawbacks.

For example, methods that filter traffic by looking for known attack patterns or statistical anomalies in traffic patterns can be defeated by changing the attack pattern and masking the anomalies that are sought by the filter. Furthermore, statistical approaches will likely filter out some valid traffic as well. Since the internet spans multiple administrative domains and legal jurisdictions, it is often very difficult to shut down an attack by contacting the administrator or the authorities closest to the source. In addition, it may be difficult to deliver such action in a timely fashion.

Even when such time constraints are met, it is sometimes the case that the source of the attack is not the real culprit, but simply a node that has been remotely subverted by an attacker.

The use of a"pushback"mechanism, such as that described in J.

Ioannidis et al. ,"Implementing Pushback: Router-Based Defense Against DDoS Attacks,"discussed above, requires the close cooperation among different service providers. Since most attacks use random source network addresses, and since

ingress filtering is not widely used, the only reliable packet field for filtering is the destination network address (of the target). If filters can only be pushed"halfway" through the network between the target and he sources of the attack, the target runs the risk of voluntarily cutting off or adversely impacting (e. g. , by rate-limiting) its communication with the rest of the internet. The accuracy of such filtering mechanisms improves dramatically as the filters are pushed closer to the actual source of the attacks. Thus, it will be necessary for providers to allow other providers, or even end-network administrators, to install filters on their routers. This approach thus requires a high degree of collaboration, and the possibility of abuse.

Another approach, described in F. Kargl, J. Maier, and M. Weber, "Protecting Web Servers from Distributed Denial of Service Attacks,"World Wide Web, pp. 514-524,2001, proposes using Class-Based Queueing on a web load- balancer to identify misbehaving network addresses and place them in lower-priority queues. However, most distributed denial of service attacks used spoofed network addresses that vary over time, thus defeating classification in some instances. For cases where the network address remains unchanged, the load balancer may need to keep a prohibitive amount of state information. In order to address this demand, the load balancer may be placed closer to the network core. This approach may further compound the"state-explosion"problem, but such detailed filtering and state- management on a per-source network address basis can have performance implications at such high speeds.

Accordingly, an approach for is needed for protection against DoS attacks which is proactive (rather than reactive) and which does not require significant modifications to either servers or browsers for its implementation.

SUMMARY OF THE INVENTION An object of the present invention is to provide a routing technique which applies filtering to the edge of the network, thereby forcing attacks into the core of the network which applies intensive filtering to traffic entering the target area.

Another object of the present invention is to provide a routing technique that provides multiple routes, and a degree of randomness, for packets in the event that certain nodes are disabled by an attack.

A further object of the present invention is to provide a level of indirection in routing, such that the details of the routing are not known to all the nodes.

These and other objects of the invention, which will become apparent with reference to the disclosure herein, are accomplished by a system and method for routing a packet within a computer network between a source and a target. The source havs a permission received from the target to transmit packets to the target.

The system comprises a plurality of first nodes, referred to as secret servlets, associated with the target. A plurality of routers are provided which are configured to route packets to the target only from one of the plurality of first nodes. A plurality of second nodes, referred to as beacons, are configured to store routing information for routing packets from the respective second node to the one of the first nodes for those packets having a representation of the target's network address. A plurality of third nodes, referred to as overlay access point nodes, are configured to accept a packet, to determine whether the source has permission to transmit the packet to the target, and if so, to route the packet to one of the plurality of second nodes by applying a hash function to a representation of the target's network address associated with the packet.

In a preferred embodiment, the plurality of first nodes may be configured to identify each of the second nodes by applying a hash function to a representation of the target's network address. Each of the first nodes may be configured to transmit an indication of the identity and/or location of the respective first node and the target associated therewith to each of the second nodes. In accordance with the invention, the association of the plurality of first nodes with the target is maintained secret. In a preferred embodiment, each of the routers is configured to filter packets approaching the routers. Each of the plurality of third nodes routes the packet from the respective third node to the second node on a route based upon one of a plurality of hash functions. If one of the second nodes fails, the third node may route the packet to another one of the second nodes by applying a second hash function to the representation of the network address of the target associated with the packet.

The plurality of third nodes may use a Chord service to route the packet from the third node to the second node. The plurality of third nodes may not be provided with the identity or location of the plurality of first nodes. In a preferred

embodiment, the plurality of second nodes uses a Chord service to route the packet from the respective second node to one of the first nodes. The source point may be a web browser, and the target may be a web server of an internet service provider (ISP). The packet may be a request from the web browser to the web server.

A method is disclosed herein for routing a packet within a computer network between a source and a target and for source point having a permission to transmit packets to the target. The method comprises identifying, by a plurality of first nodes, a plurality of second nodes by applying a hash function to a representation of the target's network address. A next step comprises providing a plurality of routers configured to route packet to the target only from the plurality of first nodes. The plurality of second nodes store a routing scheme for the routing of packets between the second node and first node. A further step is authenticating the permission of the packet from the source by one of a plurality of third nodes and forwarding the packet to one the plurality of second nodes by applying a hash function to a network address of the packet.

In a preferred embodiment, the method further comprises identifying, by the target, the plurality of first nodes. After the step of authenticating, the method may comprise forwarding the packet from one of the plurality of second nodes to one of the plurality of first nodes. The method may further comprise forwarding the packet from one of the plurality of first nodes to the target via the routers.

The method may further comprise routing the packet to from the respective third node to one of the plurality of second nodes based upon one of a plurality of hash functions. If one of the plurality of second nodes is disabled, the respective third node routes the packet to another of the plurality of second nodes.

The method may further comprise withholding the identity of the plurality of first nodes from the plurality of third nodes In accordance with the invention, the objects as described above have been met, and the need in the art for technique for routing packets through a network which prevents the denial of service, has been satisfied.

BRIEF DESCRIPTION OF THE DRAWINGS Further objects, features and advantages of the invention will become apparent from the following detailed description taken in conjunction with the accompanying figures showing illustrative embodiments of the invention, in which FIG. 1 is a schematic of the architecture of the system in accordance with the present invention.

FIG. 2 is a flow chart of the steps performed in accordance with the present invention.

FIG. 3 is a is a schematic of the architecture of another embodiment of the system in accordance with the present invention.

FIG. 4 is a is a schematic of the architecture of a portion of the embodiment of FIG. 3 in accordance with the present invention.

FIG. 5 is a plot representing the blocking probability for legitimate traffic as a function of attack traffic load.

FIG. 6 is a plot representing the bandwidth gain achieved in accordance with the present invention.

FIG. 7 is a plot representing the randomization gain achieved in accordance with the present invention.

FIG. 8 is a plot representing the likelihood of an attack succeeding by varying the number of attackers and nodes in the system in accordance with the present invention.

FIG. 9 is a plot representing the likelihood of an attack succeeding by varying the number of beacons and secret servlets in accordance with the present invention.

Throughout the figures, the same reference numerals and characters, unless otherwise stated, are used to denote like features, elements, components or portions of the illustrated embodiments. Moreover, while the subject invention will now be described in detail with reference to the figures, it is done so in connection with the illustrative embodiments. It is intended that changes and modifications can be made to the described embodiments without departing from the true scope and spirit of the subject invention as defined by the appended claims.

DETAILED DESCRIPTION OF THE EXEMPLARY EMBODIMENTS The architecture of the system is illustrated in FIG. 1, and generally designated as system or"overlay network"10, including a plurality of nodes. (The terms system, overlay, and overlay network, are used interchangeably throughout.) The system architecture provides communication between a"confirmed"source point 12 and a target 14 through the nodes in the overlay network, while denying access to unauthorized users. As will be used herein, the term"confirmed"refers to a source having a specific user to which the target, or administrator associated with the target, has given prior permission. Thus, this system 10 is useful for the classes of communication where both source and target are known to each other. An example of such use is a mobile emergency response team scenario, as discussed above.

However, the novel approach of the present invention is useful to any environment where both parties have a pre-established relationship, such as, e. g., telecommuting, corporate, intranets, subscribers to a news or financial website, etc. Accordingly, the source 12 must be authenticated and authorized by the system infrastructure before traffic is allowed to flow between itself and the target 14 through the overlay network, as will be described in greater detail herein.

The architecture of system 10 is designed to deny access to attackers, which may exist in the network, are which are interested in preventing traffic from reaching the target 14 by sending multiple requests, as discussed above. These attackers have the ability to launch DoS attacks from a variety of locations around the wide area network (of which the overlay network 10 is a subset), which are referred to as"compromised"locations herein. The number and bandwidth capabilities of these compromised locations determine the intensity with which the attacker can bombard a node with packets.

The set of nodes that participate in the system 10 are known to the public. (As the term is used herein, a"node"shall refer to any computer that is part of the overlay network. ) In effect, no node's identity is kept hidden. However, certain tasks that a node may perform in the delivery of traffic are kept secret from the public.

The specific tasks or modes which certain nodes may undertake, such as, e. g., "overlay access points,""beacons,"or"secret servlets, "etc. , will be described in greater detail herein,

The target nodes 14 receive transmissions of packets, e. g. , requests, from validated sources 12 while being protected from phony, e. g. , un-authenticated, transmissions. Heavy filtering, as indicated by the dashed line 16, is applied in the immediate vicinity of the target 14 by routers or firewalls 15 to protect the target from this unwanted traffic. According to the system 10, attackers do not have access to routers 15 inside the filtered region. Consequently, they cannot observe which source addresses can proceed through the filter. This is considered advantageous since it is substantially more difficult for an attacker to completely take over a router or link in the middle of an ISP's network, than to attack an end-host, given the limited set of services offered by a router, compared to, e. g. , a web server or a desktop computer.

The various components of the system architecture are described herein. A set of nodes, referred to as"secret servlets"18, are nodes that participate on the overlay and act as the only entry points to a target. Their identities are kept as secret as possible. Another set of nodes, referred to as"beacons"20, are nodes that receive traffic destined for a particular target 14, and, after verifying the legitimacy of the traffic, forward it to a secret servlet 18. Hence, beacons 20 are aware of the identities of some of the secret servlets 18 for the targets 14 for which they act as a beacon.

Yet another set of nodes, referred to as overlay access point (OAP) nodes 22, or alternatively Secure Overlay Access Points (SOAP), are nodes that participates on the overlay and accept traffic from"approved"source points that wish to use the overlay to reach a given target 14. The overlay network 10 also includes a plurality of intermediate overlay nodes 24.

The source 12 is a node, e. g. , computer, may be located either on or off the overlay 12. The source 12 wishes to send a legitimate transmission of packets to a target 14. As discussed above, it is assumed that source points 12 have been granted permission by the target 14 during an earlier exchange. For example, the source 12 has been provided with an appropriate certificate through e-mail from the target 14 or administrator associated with the target.

As is used herein, as"attack point, "refers to any node that has been compromised, e. g. , a compromised location, and can be used to launch an attack or snoop the source 12, to observe from where a packet came or the destination to which

a packet is going, e. g., both the immediate subsequent node (the next"hop") and the final destination.

To protect a target 14 from DoS attacks, a filtering mechanism may be deployed at the nodes such that filtering is performed along all paths that lead to the target 14. Filtering is typically performed at a set of high-powered routers 15 in which i) these routers can handle high loads of traffic, making them difficult to attack, and ii) possibly there are several, disjoint paths leading to the target, each of which is filtered independently. Consequently, if one of these paths is brought down, filtered traffic still can traverse the others.

Filtering raises a tradeoff issue in IP networks. By increasing the fraction of network addresses that are suppressed by the filter, one decreases the potential power of DoS attacks, since attackers must guess or somehow infer the source network addresses that are not filtered to mount a meaningful attack. This process also decreases the set of locations from which legitimate transmissions are allowed to originate. When using network overlays, it is still possible for a packet of arbitrary origin to reach the target even when intensive filtering is applied (without spoofing). This is accomplished by forwarding traffic to locations in the overlay whose addresses are permitted to pass through the filter. These locations then forward traffic through the filter.

To provide security, two properties of the transmission are supported by the system: 1) Attackers are not given the identities of the network addresses of the nodes that are permitted to proceed through the filter. Otherwise, an attacker could pass through the filter by simply spoofing the permitted network address.; 2) Legitimate clients at confirmed source points are able to reach the nodes with unfiltered network addresses. Thus, the problem of protecting the target 14 from DoS attacks has been converted to two operations: a) keeping the identities of non-filtered addresses secret, while b) allowing traffic from confirmed sources to reach those non- filtered addresses.

A node Ns is considered a secret servlet 18 for a target node Nt 14, if the filter (e. g. , router) around the target node Nt 14 permits packets whose source address is the network address of secret servlet Ns 18 to pass through the filter. The set of secret servlets Nus 18 used by a given target node Nt 14 is selected by the target node Nt 14 itself. This is a straightforward procedure, since the list of nodes that

participate in the overlay network 10 is available to the public. The target node Nt 14 may notify these nodes (in private) of their role as secret servlets. More particularly, the node is provided with a mode of operation as a secret servlet, as will be described in greater detail with respect to FIG. 4, below. If the target node Nu 14 wishes to alter the set of nodes that act as secret servlets, it may contact the set of new nodes to inform them of their new role, contact the set of nodes currently acting as secret servlets to inform them that they will no longer function as secret servlets, and accordingly adjust the filtering mechanism (routers) that protects it. This process provides several advantages in terms of simplifying the operation of the system. For example, the set of routers that the target 14 needs to notify is fixed, and thus long- tenn arrangements can be made with the operators of these routers, and the types of filtering rules that need to be established are fairly straightforward and can thus be easily verified by these routers. Thus human intervention or complicated resolution mechanisms are avoided. Consequently, if legitimate traffic can find its way onto the system 10, and the overlay is able to direct this traffic to the appropriate secret servlet Ns 18, the traffic can proceed through to the target node Nt 14.

The process by which a request traverses the overlay 10 from the OAP node 22 to the target 14 is referred to herein as"tunneling. "System 10 tunnels traffic from a legitimate client at a confirmed source point 12 to a secret servlet Ns 18 which can then pass the traffic through the filter to the target node Nt 14. However, the legitimate source might not reside at a node which is part of the system 10. An early step is therefore to provide the client access to the system 10. A subset of nodes, e. g., OAP nodes 22, that participate in the system act as access points for legitimate sources. The network addresses of OAP nodes 22 may be made public, or may only be revealed to legitimate clients. The security of the system architecture does not depend on these network addresses being secret.

A legitimate source chooses an OAP node NA 22 from a list of available access points and initiates a secure communication with that node using a security protocol, such as SSL (used in the exemplary embodiment) or IPsec, which is known in the art, and described in greater detail in S. Kent and R. Atkinson, "Security Architecture for the Internet Protocol. Request for Comments (Proposed Standard) 2401,"Internet Engineering Task Force, November 1998. Other communication protocols, such as PPTP, etc., may also be used. Hence, an OAP

node NA 22 confirms both the source's right to communicate with the target node Nt 14 as well as the network address of the source 12. Subsequent traffic between the OAP node NA 22 and the source 12 may be protected (again, by SSL or IPsec).

As an alternative, the source 12 may be given a"cookie"that must be included in any subsequent packets it sends to the OAP node NA 22. The choice between the two mechanisms depends largely on the perceived threat model: if attackers cannot eavesdrop the communication path between access points and sources, then the cookie approach is sufficient. In a more hostile environment, e. g., when using a wireless network to connect to the Internet, a cryptography based mechanism may be used. For additional protection, the cookie or the IPsec state (called"Security Association", or SA) may expire after a certain amount of use, either timed or in terms of the number of packets transmitted. If OAP node NA 22 fails for any reason, such as, e. g. , during a DoS attack upon OAP node NA 22, the legitimate source can simply move to another access point elsewhere in the network to continue transmitting to the target node Nt 14. Thus, a DoS attack that accidentally (or purposely) hits the OAP node NA 22 or a secret servlet NS 18 will not permanently affect communications between the source 12 and the target node Nt 14, as both contact points to the system 10 can be changed.

The above mechanism restricts entry to the system 10 to legitimate traffic from confirmed source points 12 that can be classified per flow, as well as a mechanism that permits traffic to go from specific nodes, secret servlets NS 18, on the system 10, to a target node Nt 14 through heavy filtering.

A technique to route through the system 10 in a manner that makes it difficult to attack the route is described below. Routing used within the system 10 must be robust to attacks upon nodes within the system 10. In particular, if a given set of system nodes is attacked, there must be an efficient transition to an alternative path where no nodes are under attack. In accordance with the invention, system 10 uses the consistent hashing approach used within the Chord service, which is known in the art and described in I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H.

Balakrishnan, "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications,"Proceedings ofACMSIGCOMM'01, San Diego, CA, August 2001.

As implemented herein, Chord is used as a routing service with the following properties: The service is implementable atop the existing IP network structure.

Given a key that relates to some piece of information, typically a file or piece of content, Chord provides a means to map, i. e. , to"hash, "the key to a particular subset of nodes that i) are active members of the system 10 and ii) contain the information that is associated with the key. Each node in the system maintains a list that contains O (log N) identities of other active nodes in the system. (Where N is the number of nodes in the overlay 10. As is known in the art, O (log N) implies that as N grows large, the length of the list grows at a logarithmic rate. The function. gN) is an O (log N) function, there exists constants c and No such that for any N> NosfTKN) < c log N.) Given a key, each node is able to choose a node in its list such that, from an arbitrarily chosen starting node, the destination node to which the key hashes 5 is reached in O (log N) hops. Chord is able to produce multiple destination nodes for a given key using different hash functions. By choosing the right class of hash function, the sequences of nodes used to carry a packet from a node to the destination are independent from one another. Multiple mappings, i. e. , hash functions, may be used to produce different paths to different sets of destination nodes, such that the set of nodes that form paths from a given start node to a given destination (sink) node are independent.

The Chord service is robust to changes in system membership, and provides a technique for adding and removing nodes from the system. Each node's list is adjusted to account for nodes leaving or joining the system such that the above properties continue to hold.

In system 10, the key k to which the hash function is applied may be the network address of the target 14. Thus, Chord can be used to direct a packet from any node in the system 10 to the node that the key k is mapped to. Not all nodes that route a packet within Chord using key k need to know the network address of the final destination to which Chord routes the packet. They only need to know that they are sending the packet to a node on the system that is in the"right direction". In this manner, the Chord service assures that a destination exists that is expecting to be the destination for packets with key k.

For a particular hash function, the beacon 20 is the destination of a route from a node, such as OAP node 22, using a key k formed by hashing upon the target's network address. The beacon 20 is a unique node that will eventually be reached (after possibly several intermediate hops, e. g. , over nodes 24) when Chord, or

an alternative protocol, is applied, regardless of the starting point in the system 10.

When a packet is approved by OAP node NA 22 for transmission, the hash on the network address of the target node Nt 14 is used as the key. Hence, Chord provides a robust and reliable while relatively unpredictable means of routing packets from an access point to one of several beacons 20.

Another aspect of the system 10 is the technique of getting packets from beacons 20 to secret servlets Ns 18. There are several approaches for accomplishing this final step. For example, since any node in the Chord system can route to a beacon 20, it follows that a secret servlet Ns 18 (or the target 14) can also contact a beacon 20 for a particular target node Nt 14, for any hash function applied.

A function of a beacon 20 is to respond to queries, typically transmitted securely over the system, that ask them to identify themselves as a beacon 20 for a given hash function and target location. This technique allows secret servlets N,. 18 to locate beacons 20 for a given hash function and inform those beacons 20 of the identity of the secret servlets Ns 18.

Under the Chord service, all nodes that are beacons 20 under the same hash function can be made aware of each other's existence. (The set of beacons form an ordered list, where each beacon knows the existence of the next beacon on the list.

This relation is made bi-directional for the purposes of exchanging secret servlet information. ) In accordance with the invention, the system 10 utilizes a finite set of possible hash functions per target. Although all beacons 20 need not know about all secret servlets 18, each beacon 20 will know about at least one active secret servlet 18. By spreading the set of usable hash functions across the secret servlets 18, e. g., having each secret servlet 18 inform a beacon 20 for each hash function it contains, and having all beacons 20 under the same hash function share their secret servlet information, all beacons 20 have access to at least one secret servlet 18. Thus, a secure path from the confirmed source point 12 to the target 14 is provided.

Additional features of the exemplary embodiment of the system 10 are provided herein. The system architecture may be implemented in a very straightforward manner, using existing software.

The filtering is provided by routers, such as router 15. High and medium-range routers (both in terms of performance and price), as well as most desktop and server operating systems, typically offer some high-speed packet

classification scheme that can be used to implement the target perimeter filtering. A simplified version, as described in J. Ioannidis and S. M. Bellovin. Implementing Pushback: Router-Based Defense Against DDoS Attacks. In Proc. of the Network and Distributed System Security Syynposium (NDSS), February 2002, can be used by the target 14 to inform its perimeter routers of changes in the set of allowed secret servlets 18.

The OAP nodes 22 perform authentication and authorization of sources. Practically all commercial and free operating systems include an implementation of SSL or IPsec, as discussed above. IPsec is a set of protocols that can be used to establish cryptographic keys and other relevant parameters between a pair of hosts, and then protect (encrypt and integrity-protect) the traffic between them.

As described in M. Blaze, J. loannidis, and A. D. Keromytis, "Trust Management for IPsec,"Proc. of Network and Distributed System Security Symposium (NDSS), pp.

139-151, February 2001, the conditions under which access to the overlay 10 is allowed can be efficiently encoded in public key certificates. The system 10 provisions and manages access control for a large infrastructure with minimal overhead in terms of performance, storage, and synchronization requirements.

More specifically, each authorized source 12 is given a certificate by a target 14 or administrator associated with the target authorizing that source 12 to use the system infrastructure to send packets to the target 14. In the process of authenticating to the access point, e. g. , OAP node 22 (via the IPsec authentication protocol, currently IKE, as described in D. Harkins and D. Carrel, "The Internet Key Exchange (IKE),"Requestfor Comments (Proposed Standard) 2409, Internet Engineering Task Force, November 1998), the source 12 provides this certificate to the access point. The access point can both authenticate the source 12 (by verifying a cryptographic signature) and confirm that the source 12 is allowed to send traffic to the target 14. Access points need not store access control policies. The certificates are used to"remind"access points of the relevant access control policies; once a communication is torn down, the access point can"forget"the relevant policy.

Once traffic has entered the overlay 10, it needs to be forwarded to other nodes towards the beacon 20, and from there to the secret servlets 18. Standard traffic tunneling techniques (See, e. g. , J. Ioannidis. Protocols for Mobile Networking, Ph. D. thesis, Columbia University, New York, 1993, and D. G. Andersen, H.

Balakrishnan, M. F. Kaashoek, and R. Morris, "Resilient Overlay Networks,"Proc. of the 18th Symposium on Operating Systems Principles (SOSP), October 2001) and protocols can be used to this end: IP-in-IP encapsulation (as described in C. Perkins.

IP encapsulation within IP. Request for Comments 2003, Internet Engineering Task Force, October 1996), GRE encapsulation (as described in D. Farinacci, T. Li, S.

Hanks, D. Meyer, and P. Traina, "Generic Routing Encapsulation (GRE),"Request for Comments 2784, Internet Engineering Task Force, March 2000), or IPsec in "tunnel mode. "Furthermore, traffic inside the overlay network can take advantage of traffic prioritization schemes such as MPLS or DiffServ, if they are made available by the infrastructure providers. The routing decisions inside the overlay network are based on a Chord-like mechanism (see, e. g., 1. Stoica et al. ,"Chord : A Scalable Peer- to-Peer Lookup Service for Internet Applications, discussed above.) It is understood that the overlay nodes are a mix of routers and high- speed end systems. In particular, since IP tunneling is a lightweight operation, functionality would be offered by service providers without adversely affecting the performance of their networks. The access points to the overlay network can be a mix of routers and high-speed end systems (with appropriate cryptographic acceleration hardware to boost performance).

As implemented in the system 10 discussed above, the sequence of operations 100 in the system architecture may include the following steps as represented in FIG. 2: As discussed above, the target 14 or administrator provides a certificate or other means of authentication to the source 12. At step 104, the target 14 may install a filter on routers 15 in its immediate vicinity and select a number of nodes to act as secret servlets 18. As discussed above, secret servlets 18 are the only nodes that are allowed to forward traffic through the filter to the target 14.

(According to another embodiment, the secret servlets 18 may be encoded or otherwise hard-wired with their role as secret servlets 18. ) At step 106, routers 15 at the perimeter of the target site 14 are instructed to only allow traffic from these secret servlets 18 to reach the internal of the target site's network. These routers 15 are powerful enough to do filtering using only a small number of rules on incoming traffic without adversely affecting their performance. In order to complicate the attempt to guess the identity of a secret servlet 18 for a particular target 14, the filtering mechanism may use packet fields with potentially high entropy. For

example, filters may only allow GRE packets (as described in D. Farinacci, T. Li, S.

Hanks, D Meyerm and P. Traina, "Generic Routing Encapsulation (GRE),"RFC 2784, Internet Engineering Task Force, March 2000) from a particular source, i. e. , the secret servlet 18, containing a specific 32-bit value in the GRE key field (as described in G. Dommety, "Key and Sequence Number Extensions to GRE,"RFC 2890, Internet Engineering Task Force, September 2000). Thus, an attacker trying to slip attack traffic through the filter must guess not only the current servlet's network address, but the correct 32-bit key as well.

According to a step 108, nodes designated as secret servlets 18 compute the key k for each of a number of well-known consistent hash functions, based on the target site's network address. (Prior to computing the key, the node may verify the authenticity of the request by the target 14. ) Each of these keys k will identify a number of system nodes that will act as beacons 20 for that target site 14.

The secret servlets 18 contact the beacons 20 and notify them of their function as beacons. In other words, the secret servlet 18 provides the beacon 20 with: an indication of the existence of the respective secret servlet 18, an indication of the target 14 associated with the secret servlet 18, and its function as a beacon 20.

At step 110, the beacons 20, after verifying the validity of the request from the secret servlet 18, will store the necessary information to route traffic destined for the associated target site 14 to the appropriate secret servlet 18. Beacons 20 of the same key may share information about the set of available secret servlets 18 for a particular target 14.

Step 112 may occur concurrently with steps 102-110. A source 12 that wants to communicate with the target 14 contacts an OAP node 22. At step 112, the OAP node 22 authenticates and authorizes the request from the source 12. At step 114, the OAP node 22 routes all traffic from the source 12 intended for a target 14 to one of the beacons 20 associated with the target 14. The OAP node 22 (and all subsequent hops on the system 10) can route the packet to an appropriate beacon 20 in a distributed fashion using Chord by using computation of the hash function (s) over the target's address to identify the next hop on the system 10.

At step 116, the beacon 20 routes the packet to a secret servlet 18, based on the routing information stored at step 110, above. At step 118, the beacon 20 routes the packet (through the filtering) to the target 14.

In accordance with the above-described system and methods, this invention is robust against DoS attacks for the following reasons: If an access point, e. g. , OAP node 22, is attacked, the confirmed source point 12 can simply choose an alternate access point by which it enters the system 10. If a node within the system 10 is attacked, the node simply exits the overlay and the Chord service self-heals, providing new paths to (potentially new sets of) beacons 20. Furthermore, no node is considered more important or sensitive than others. Accordingly, even beacons 20 can be attacked and are thus allowed to fail. If a secret servlet 18 is attacked (either due to a lucky random hit or somehow its identity was compromised), the secret servlet 18 (which can still send traffic outward) can notify the target 14 and the target 14 can choose alternate secret servlets. If a secret servlet's identity is discovered and attacks arrive at the target with the source network address of some secret servlet 18, the target 14 can choose an alternate set of secret servlets 18.

The path established from the source 12 to the target 14 may be unidirectional. Traffic in the reverse direction may also traverse the overlay, by reversing the roles of the source and the target. In such a case, the path taken by the requests and the responses may be different. Alternatively, traffic from the target to the source could be sent directly, as will be described in greater detail below.

An exemplary embodiment of the invention, referred to as system 200, will be defined herein and illustrated in FIG. 3. System 200 is substantially identical to system 10, with the differences noted herein. According to system 200, special purpose web proxies are used as the system nodes. These proxies implement the following functions: The proxies receive SSL connections from other proxies; both sides are mutually authenticated using public key certificates issued by the administrator of system 200. Proxy HTTP (or HTTPS) requests are received over these SSL connections to other nodes, again over SSL. System 200 accepts SSL connections from browsers, verifies the client certificate received over the SSL exchange, and proxies the HTTP or HTTPS request to other nodes. The Chord routing algorithm is implemented, as discussed above. The routing table constructed using Chord is used to determine the next proxy to which an HTTP/HTTPS request is forwarded.

Beacon functionality, as discussed above, is implemented.

Accordingly, each node must maintain a table associating web server network

addresses to secret servlet network addresses. If a proxy request for a web server in this table is received, the connection is proxied to the associated secret servlet 218.

Secret servlet functionality, also as discussed above, is implemented.

If a request is received for a target 214 (e. g. , a web server) for which the node receiving the request is the secret servlet, the connection is forwarded directly to the target (e. g. , web server). Furthermore, authorized targets are allowed to notify a system node that is a secret servlet for that target. The node must verify the certificate presented by the target in the authentication process, e. g. , SSL exchange, and then notify the beacon 220, that the node is the new secret servlet 218 for that target 214.

If the source 212 (e. g. , web browser) is performing end-to-end SSL (to the target 214), the encrypted link may be super-encrypted with SSL, or some other security protocol, on the link between the source 212 and the OAP node 222, and between each system node, e. g. , intermediate nodes 224. SSL may be used in the intermediate nodes 224 to prevent an attacker from inserting traffic in the system through IP spoofing. SSL may also be used as an admission-control mechanism to the system. In the exemplary embodiment, OAP nodes 222 perform the admission control function. No special functionality is required by the proxies to perform these tasks; the source 212 is provided with the appropriate public key certificate from the system administrator at the target 214.

In system 10, the path established from the source 12 to the target 14 may be unidirectional. System 200 may operate using an asymmetric approach such that traffic from the target 214 to the source 212 is sent directly (without using the techniques described herein). This approach may be advantageous, since most communication channels are full duplex and, in the event of a DoS attack, typically only the downstream portion, i. e. , to the target, is congested. An additional benefit of this asymmetric approach used in system 200 is reduced latency, especially considering that most target-to-source traffic, e. g. , client/server traffic (especially in the web environment) is highly asymmetric, in which case clients receive significantly more information than they transmit. This implementation may be made because routing decisions in system 200 are preferably made on a per-packet basis.

The operation of the system 200 is identical to the sequence of functions 100 described above and illustrated in FIG. 2 for system 10, with the differences noted herein.

The use of GRE, as discussed above, for encapsulating the traffic between the secret servlet 218 and the filtering router 215 can offer an additional benefit of asymmetric routing, if, e. g. , the system 200 uses transparent proxies and IPsec for packet encapsulation between the proxies (as described in S. Kent and R.

Atkinson,"Security Architecture for the Internet Protocol,"RFC (Proposed Standard) 2401, Internet Engineering Task Force, Nov. 1998. ) rather than SSL. In the above- described embodiment, as far as the target is concerned, the HTTP/HTTPS connection from the source may be received directly. Thus, any return TCP traffic will be sent directly to the source's network address. The asymmetric connection routing may considerably improve the end-to-end latency and reduce the load on the overlay network.

Further details of the implementation of system 200 are described herein. Each of the nodes in the system 200 that serve as the secret servlets 218, the beacons 220, and the OAP nodes 222 are substantially identical. Thus the general architecture of the secret servlets 218, the beacons 220, and the OAP nodes 222 is designated 300 and is illustrated in FIG. 4. Each node 300 may include three modules, e. g. , a communications module 302, a routing module 304, and an overlay routing module 306, all of which run on each node in the system 200.

The communication module 302 is responsible for forwarding HTTP requests and responses among the nodes in the system 200. When a new proxy request, e. g. , in the form of a TCP connection, is received, the communications module 302 calls the routing module 304 (as indicated by arrow 310) with the target's destination address to obtain the address of the next hop, i. e. , the next node, within the system 200. The communications module 302 then opens a new TCP connection to that next node and relays the received HTTP request (as indicated by arrow 312).

Any traffic received in the opposite direction, e. g. , the HTTP response and web , content, are relayed back to the source 212. According to the exemplary embodiment, authentication of the requesting node by the OAP node 222 and by internal nodes 224 is accomplished through SSL. Authorized users and system nodes may be issued X. 509 certificates (as described in CCIT, X509. She Directory of SutAzenticatio7 Framework (Internal Communications Union) Geneva, 1989), signed by the system certificate authority. It is understood that other security protocols, such as KeyNote credentials may be used to describe access rights of each user.

When a request is issued by the source 212, it is tunnelled through a series of nodes (e. g., OAP nodes 222, beacon 220, and secret servlet 218, and intermediate nodes 224) which may be SSL-encrypted, to the target 214, allowing the entire transmission between the source 212 and the target 214 to be encrypted. These SSL connections between system nodes are dynamically established, as new requested are routed. Web browsers typically do not provide support for the actual proxy requests to be encrypted. Accordingly, a novel port forwarder runs on the user's system, accepts plaintext proxy requests locally, and forwards them using SSL to the access point, e. g., OAP node 222. In the exemplary embodiment, the port forwarder is a stand-alone program, which is provided in the Appendix. It is understood that alternative approaches may be used, such as a Java applet that runs inside the browser itself. According to this alternative embodiment, an authorized user accesses any OAP node 222, downloads the applet, and sets the browser's proxy settings to the local host.

The routing module 304 receives requests from the communications module 302 and responds with the network address of the next node in the system to which the request should be forwarded. This routing module 304 first checks whether the current node serves a specific purpose, i. e. , whether it is acting as a beacon or a secret servlet for that target. If the node serves no such purpose, the module 304 calls the overlay routing module 306 (as indicated by arrow 314) to determine the next hop in the system and passes the reply onto the communications module 302 (arrow 310).

In the exemplary embodiment, the routing module 304 is initialized with configuration data at startup indicating which nodes serve specific purposes. It is understood that an administrative module may be provided which increases flexibility of the nodes and avoids the static designation of the nodes.

The overlay routing module 306 is a general routing algorithm for the overlay networks. An implementation of Chord was used in the exemplary embodiment, an provided in the Appendix. However, it is understood that this module may be replaced with any other routing algorithm, e. g. , CAN (as described in S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker,"A Scalable Content- Addressable Network,"Proceedings of ACMSIGCOMM, San Diego, CA, August 2001)

EXAMPLE Analytical models that describe DoS attacks, and how the system architecture of the present invention helps prevent the possibility of successful DoS attacks is described. DoS attacks are launched through compromised nodes across the network. Nodes can be compromised, for instance, by an email virus, such that the attack is triggered at a later point in time (e. g. , when a compromised node executes the attack code via an email client). While the spread of the virus can be modeled as an epidemiological process, the launch of the attack by these compromised nodes can be viewed as independent events across compromised clients. An attack is examined from two directions. First, attack severtity is analyzed, i. e. , the effect that a certain level of attack traffic has on a node's ability to withstand attack as a function of the node's capacity and processing power. By protecting the edge via filtering, the system forces attacks into the core of the network. The amounts of traffic needed to bring down a node increase significantly as a result. Next, the attack success rate is analyzed. Because the system can quickly switch a path from a set of attacked nodes to a set of un-attacked nodes, an attacker must successfully attack a very large set of nodes in order to successfully shut down communication to the target. Accordingly, unless the attacker can shut down a very large set of nodes, the likelihood of a successful attack is slim. From these two properties of the system, it follows that bringing down a target protected by the system is made unlikely.

Attack severity is measured in a scenario in which several compromised zombie nodes, distributed over the network, launch attacks on a target node. Attacks that start at random times may overpower routers with low bandwidth capabilities much easier than those with high bandwidth capabilities.

As a simple first approximation, the arrival of the attack traffic from such clients is modeled as Poisson process, with an arrival rate ka attacks per unit time. Each attacking client is assumed to use up ba units of resources (typically bandwidth) from a target while the attack is in progress. The duration of attacks from such clients is assumed to be exponentially distributed, with mean 1/, ua. The attacks could tenninate for a number of reasons, for instance, discovery and shutdown of compromised clients by users/local system administrators or discovery by some trace- back mechanism and shutdown by access network filtering. Legitimate traffic is

assumed to arrive at the node with rate #l, requiring bl units of resource and mean holding time l/, ul The target node is assumed to have Ct units of resource available.

When all the resources get tied up, arriving requests, either legitimate or attack, are denied service. Under such circumstances, a DoS attack is considered to be successful.

The system model is abstracted into a Stochastic Knapsack framework (see, e. g. , Keith W. Ross. Multiservice Loss Models for Broadband Telecommunication Networks. Springer-Verlag, 1995). In a Stochastic Knapsack, Ct is the total amount of resources available at the server, and each arriving connection is mapped into an arriving call of class m with resource requirement bm and mean holding time l/, um. Calls in each class arrive at a rate Am. The knapsack always admits an arriving object when there is sufficient room. In the model described herein, the probability of a successful DoS attack is the blocking probability corresponding to the class of legitimate traffic.

Let n,, denote the number of class-m objects in the knapsack. Then the total amount of resource utilized by the objects in the knapsack is b n, where b: = (bl, b2,... bM) and n := (n1, n2, ... nM). The process is defined in terms of the state space of the different class-m objects, i. e. , let K : = {n Eln': bn<Ct} Formally, the knapsack admits an arriving class-m object if bm < Ct- b-n. Let Km be the subset of such states, i. e., K"l : = {nEK : n<Ct-bm} The blocking probability B,, for a class-m call under Poisson arrival assumption is then given by the following equation:

As an illustrative example, where there are only two classes of customers, one corresponding to the DoS attacks and the other to legitimate traffic.

(According to a generalized model, the various clients may be classified according to their bandwidth capabilities, more specifically their network access types like DSL, Cable, T1, Dialup, etc. This would not change the nature of the results. ) It is assumed that an individual call in each class uses up the same amount of bandwidth (motivated by the idea that the compromised clients come from the same population as the legitimate users). For a DoS attack to be successful, the load level (py) for the class attack has to be significantly higher than that of legitimate traffic. Accordingly, a test scenario is constructed in which the target node has 20 units of resource available, and both the attack and legitimate traffic utilize one unit of resource and kI, u (p) for the legitimate traffic is 1. In FIG. 5, the probability 402 that a legitimate connection is denied service is plotted as a function of load level p 404 of attack traffic. Under the test scenario, where p = 200 for the attack traffic will cause 90% of the legitimate traffic to be denied service. Under a massive attack, if the attack load rises to 10000,99. 8% of legitimate traffic is denied service.

Next, the effects of two key features of the system architecture are considered. First, when the attack point perimeter is pushed into the interior of the core, then the traffic handling capability of the attacked node increases. (As a result, core routers, which can handle OC192 line speeds per interface are utilized, rather than typical high speed edge routers, having a capability of 155Mbps. ) The case is considered where the attack traffic load in the test scenario is 200, and the blocking probability for legitimate traffic is re-computed as the capacity of the node is increased by a factor r, i. e., CtlleW = r x Ct,, Id. The ratio of the old blocking probability with the new blocking probability is denoted as the Bandwidth Gain (BG) of the system. In Figure 6, the BG 502 of the system is plotted as a function of r 504. As can be observed, a bandwidth increase by a factor of 12 brings about a reduction in the blocking probability by three orders of magnitude.

The effects of anonymizing the attacked node are analyzed. Thus, if the attacker does not know the identity of the secret servlet for a particular target, then the attacks would be launched randomly onto the overlay. Only a fraction of those attacks would reach the target servlet. Thus, the effective arrival rate of the attacks

would become X. a X/where/is the fraction of the secret servlets in the system for a particular node. The ratio of the old probability with the new blocking probability is computed and denoted as the Randomization Gain (RG) of the system. In Figure 7, the RG 602 of the system is plotted as a function of the number of nodes 604 in the overlay. As the number of nodes in the overlay increase from left to right, a smaller and smaller fraction of the traffic reaches the target node. Placing the target node randomly in a group of 30 brings down the probability of attack by 4 orders of magnitude.

The preceding analysis demonstrates that bringing down targeted nodes in the system architecture becomes very difficult for a potential attacker.

However, an attacker might decide to attack an arbitrary node (or nodes) on the overlay with the intention of a random DoS attack. Although the difficulty of bringing down even a single (high capacity) node on the over-lay down is considerable, in the next section it is explained how the redundancy of SOS helps in preventing such random attacks.

The likelihood that an attacker (or set of attackers) is able to prevent communication between a particular pair of (arbitrarily chosen) client and target is analyzed, i. e. , the attack success rate. Two fundamental scenarios are investigated.

First, in the"static"case, it is assumed that an attacker chooses a fixed set of nodes within the overlay upon which it will launch an attack. This analysis allows the client's communication path to adapt to these attacks and find a route if one indeed exists. The results are shown below where the flow is considered in isolation, where an attacker brings down a subset of nodes, and it is analyzed whether this prevents communication.

Second, in the"dynamic"case, it is assumed that when an attacker attacks a node, the self-healing properties of the system (e. g. , using Chord) are able to repair the attack, forcing the attacker to then look elsewhere.

The analysis in the static case considers the following problem: suppose some subset of nodes in the overlay are able to take on specific tasks for a given target, T. Let IS, (T), S2 (T)..., S5 (T)} be the set of secret servlets with Us = | {Ss (T) l, {Al (S),.., Aa (S)} be the set of access points that can be used by source point S with Uo = ItAi (S) II, and {Bl (T),..., Bb (T)} be the set of beacons used to

receive transmissions from S headed toward T : Ub = {Bi (T)} | is a function of the number of hash functions issued by T as well as the amount of redundancy implemented within Chord for each hash function.

For the initial analysis, a session between S and T is assumed to proceed so long as there exists an available access point, an available beacon, and an available secret servlet. This further assumes that all beacons are aware of all secret servlets. The analysis is easily extended for the case where this assumption does not hold. A further assumption is that the selection of nodes to perform various duties is done independently, such that a node could simultaneously act as any combination of access point, beacon, and secret servlet. Another assumption is that all nodes implement (and hence can be part of the path) of the Chord routing service. Thus, Chord will be able to route effectively even if only one node remains in the overlay, though the node would have to simultaneously be the access point, beacon, and secret servlet.

Let P,, (a, b, c) be the probability that a set of b nodes selected at random from a > b nodes contains a specific subset of c < b nodes. It may be shown (This follows form an algebraic reduction of Let 7la be the number of nodes that the attacker attacks. Let Us, T be a random variable that equals 1 if S Can reach T during an ongoing attack and 0 otherwise. The likelihood of an attack succeeding is expressed by the following equation: Pr [UT S = 1] = (1-Ph(N,na, Us))# (1-Ph(N, na, Ub))#(1-Ph(N,na,U0)) FIGS. 8-9 plot the likelihood of an attack succeeding at shutting down access to a site in the static case. hi FIG. 8, Us Ub, and UO are fixed at 10 and vary na along the x-axis 702. These numbers are conservative: the source's entry is restricted to only 10 possible access points and at most 10 beacons and 10 secret servlets are allowed to service its needs. An increase in any of these numbers decreases the probability of a successful attack. The y-axis 704 plots the probability of a successful attack, with the different curves representing different values of N, the total number of

nodes in the overlay system. (Accordingly, curve 706 represents 100 nodes in the system; curve 708 represents 1000 nodes; curve 710 for 100,000 nodes; and curve 712 for 1,000, 000 nodes. ) In FIG. 9, the number of nodes in the system N is held fixed at 10,000 and/ is fixed at 1000. The value of Ub along the x-axis 802, and the probability of a successful attack is plotted on the y-axis 804. The different curves represent the probabilities for different values of Us, where f = Us/Ub.. (Accordingly, curve 806 representsf=0. 01 ; curve 808 representsf=0. 1; curve 810 for f 1 ; and curves 812 and 814 (which are nearly coincident) forf=10 andf=100, respectively. ) From these figures, the likelihood of an attack successfully terminating communication between S and T is negligible unless the attacker can simultaneously bring down a significant fraction of nodes in the network. For instance, FIG. 8 demonstrates that when only ten nodes act as beacons, ten nodes act as secret servlets, and ten nodes act as access points, for an attack to be successful in one out of ten thousand attempts, approximately forty percent of the nodes in the overlay must be attacked simultaneously. Similarly, FIG. 9 shows that the likelihood of a successful attack is significant only when either the number of secret servlets or the number of beacons is small, but the numbers needed to force attacks to be successful beneath miniscule probabilities are quite small. In summary, long-term static attacks upon a moderately-provisioned system in accordance with the present invention are unlikely. hi the dynamic case, the attacker is assumed to have enough bandwidth resources to bring down A'nodes. The attacks proceed in the following manner: The attacker attacks anodes, Chord self-heals after an exponentially distributed time lo,,,, the attacker realizes that such self-healing has taken place, and launches an attack on another node. The launch of the subsequent attacks is modeled as a Poisson process with rate attack. This system is modeled as a classical M/M/#//K queuing system, i. e. , one with a finite number of (K) customers and an infinite number of servers. The average number of customers actively receiving service at any time, N, is given by the following equation: <BR> <BR> <BR> N = KXaUack/eal (2<BR> <BR> <BR> 1 + iattack/» eal

Now N is strictly less than K. In FIG. 10, the effect of the self- healing process is plotted. The effective K (N) 902 is plotted as a function of) J, heai 904. (Curve 906 represents K=10 ; curve 908 for K=20 ; curve 910 for K=40.) The faster the self-healing process as compared to attack arrivals, the lower N. N represents the average number of nodes under attack at any given time. Thus, the effectiveness of the attacker is reduced considerably by the self-healing properties of Chord as fewer nodes come under simultaneous at-tack. The faster Chord self-heals, the more ineffective the attack is.

An exemplary implementation of system 200 is now described. In order to quantify the overhead imposed by the system 200 architecture, an exemplary topology is created which runs on the local network (100 Mbit fully-switched Ethernet). In this embodiment, 10 commodity PCs were used, running Linux Redhat 7.3. The time to completion of HTTPS requests were measured. In particular, the elapsed time was measured starting when the browser initiates the TCP connection to the destination or the first proxy, to the time all data from the remote web served has been received. This test was run by contacting three different SSL-enabled sites: login. yahoo. com, www. verisign. com, and the Columbia University course bulletin board web service (https.://wwwl. columbia. edulseclbboard). For each of these sites, the time-to-completion was measured for a different number of overlay nodes between the browser and the target (remote web server).

The browser was located in a separate network and connected to the Internet over a cable modem. This configuration introduced some latency in the first hop connection (from the browser (source) to the SOAP or OAP node), thus simulating (albeit using a real network) the environment where the browsers have slower access links to the SOAPS, relative to the links connecting the overlay nodes themselves (which may be co-located with core routers). By locating all the overlay nodes in the same location, the aggregate overhead of the system nodes can be measured in the optimal case (from a performance point of view).

Table 1 illustrates the results for the case of 0 (browser contacts the remote server directly), 1, 4,7, and 10 overlay nodes. The times reported are in seconds, and are averaged over several HTTPS GET requests of the same page, which was not locally cached. For each GET request, a new TCP connection was initiated by the browser. The row labeled"Columbia BB (2nd) "shows the time-to-completion of an HTTPS GET request that uses an already established connection through the overlay to the web server, using the HTTP 1. 1 protocol.

Server Direct 1 node 4 nodes 7 nodes 10 nodes Yahoo! 1.39 2.06 2. 37 2.79 3.33 Verisign 3. 43 4.22 5.95 6.41 9.01 Columbia BB 0.64 0. 86 1.06 1.16 1.21 Columbia BB (2nd) 0.14 0.17 0.19 0.20 0. 25 TABLE 1 As the table shows, system 200 increases the end-to-end latency between the browser and the server by a factor of 2 to 3. These results are consistent with the system 10 in an ISP topology, where the latency between the different overlay nodes would be small. The increase in latency can be primarily attributed to the network-stack processing overhead and proxy processing at each hop.

Table 2 shows the same experiment using PlanetLab (as discussed in L. Peterson, D. Culler, T. Anderson, and T. Roscoe, "A Blueprint for Introducing Disruptive Technology into the Internet,"Proceedings of the 1st Workshop on Hot Topics in Networks (HotNets-I) October 2002), a wide area overlay network testbed.

The PlanetLab nodes are distributed over academic institutions over the United States, and are connected over the Internet. The system 200 proxies were deployed on PlanetLab and the same tests were run. As expected, the direct-connect case remains the same. The time-to-completion increases by a factor of 2 to 10, depending on the number of nodes in the overlay. In each case, the increase in latency over the local- Ethernet configuration can be directly attributed to the delay in the links between the system nodes. Server Direct 1 node 4 nodes 7 nodes 10 nodes Yahoo ! 1. 39 3.15 5.53 10.65 14. 36 Verisign 3. 43 5.12 7.95 14. 95 22. 82 Columbia BB 0. 64 1.01 1.45 3.14 5.07 Columbia BB (2nd) 0. 14 0.23 0. 28 0. 57 0.72 TABLE 2

The PlanetLab tests represent a worst-case deployment scenario for the system 200: typically, the system 200 may be implemented as a server by an ISP (Internet Service Provider), with the majority of system nodes located near the core of the network. Using PlanetLab, the nodes are distributed in end-sites.

It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention.

APPENDIX A computer program listing is submitted in the Appendix, and are inco7porated by reference in their entirety hereija.

A portion of the disclosure of this patent document contains material which is subject to copyright protection. Tlae copyright owner has no objection to tlaefacsinaile reproduction by anay one of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.

CHORD ALGORITHM 1) Introduction This is the README for SOS-Chord version 1.0, developed at Columbia University CS Department as part of the Secure Overlay Services (SOS) Project.

2) What is SOS-Chord :- SOS-Chord is a self-healing routing protocol based on the Chord routing protocol (http://www. pdos. lcs. mit. edu/chord/) 3) Usage :- A Chord node uses a U DP port on the machine on which it resides.

A Chord node can be run as: ./sos-chord IPl : portl-j IP2: port2 Here IP1 should be the IP address of the machine on which this chord node resides and portl would be the UDP port on which this node will listen.

IP2: port2 is the bootstrap node. It would be another chord node which would help this node to join the Chord Network.

For the first node to join the network, the bootstrap node would be itself.

4) Stabilize Period :- Each chord node runs the Stabilize function periodically.

In order that the stabilize may not overwhelm the network, each chord-node adapts its stabilize-period depending on the recent state of the network.

CURRSTABILIZETIMER is the current stabilize period.

In case no changes occur in the Finger Table because of the Stabilize function, CURR STABILIZE TIMER doubles.

It can go upto a maximum of MAXSTABILIZETIMER.

In case, something changes in the Finger Table during Stabilize, the CURRSTABILIZETIMER is reset to MIN STABILIZE TIMER.

Hence the Stabilize period adapts itself.

5) Communication with SOS Administrative module :- Each chord node also listens on a Unix Domain Socket...

Currently its path is"/tmp/kamra/sos-path"in the filesystem.

This may have to be manually configued before a test-run.

Care should be taken that it doesn't reside on a NFS partition, orelse all chord nodes may fight for it.

An administrative module"node"can periodically send queries to the corresponding chord node to ask for the nextHop.

The query input would be a string which'11 be the IP address of the target and the output from the chord node would be another string which'11 be the IP address of the nextHop.

In case the IP returned is the same as the IP address of the administrative"node", then the administrative node is the BEACON for that target.

The Chord-node will create the unix domain socket and will be responsible for"unlink"-ing it.

The administrative node will just open this"socket file" as it may open any other file and use calls such as read and write to communicate with the chord node..

So the administrative module has just to do something like this: #define UDSPATH"/tmp/kamra/sos-path" int uds fd ; char inputIP [MAX_LEN] ; char outputIP [MAX_LEN] ; //Suppose input IPaddress is in inputIP //This should be done only once... udsfd = open (UDSPATH, 0RDWR) ; //And then call GetNextHop (inputIP, outputIP); //whenever it wants the nexthop from chord...

//The nextHop IP would be in outputIP void GetNextHop (char input[], char output []) { write (uds_fd, inputIP, strlen(inputIP)); int len = read (uds_fd, outputIP, MAXLEN) ; outputIP [len] = 0 ; } 6) Node Joining and Leaving :- The SOS-Chord code works fine with arbitrary sequence of Node joins and removals..

Since for each administrative-node, there is a corresponding chord-node, it is imperative that they should start and end simultaneously, so that the chord routing correctly reflects the routing between the administrative nodes.

6.1) Join The administrative node and the chord node can join the network together just by starting them

up together, i. e. from shell prompt or a script.

6.2) Removal In case the administrative node decides to go down, or we want to stop it for testing purposes, it should inform the corresponding chord-node so that it can go down too.

This can be accomplished if the administrative node sends a nextHop query to the chord-node with the input IPaddress as 0.0. 0.0 Note that this would be a write of 7 bytes from the administrative node.

The chord-node on getting this IP would exit.

So, we can add an interrupt-handler in the administrative module which'11 send this packet to the chord-node on getting a Ctrl-C. void SendQueryData (struct Query q) { struct sockaddr in dst addr ; bzero ( (char *) &dstaddr, sizeof (dst addr)) ; dst addr. sin family = AF_INET ; dstaddr. sinaddr. saddr = q. To. ip. s-addr ; dst_addr. sin-port = htons (q. To. port) ; sendto (chord socket, (char *) &q, sizeof (q), 0, (struct sockaddr *) &dst_addr, sizeof (dst addr)) ; //printf ("Sent Query of type = % d, to ip=% s, port=% d\n", q. QueryType &-ResponseMask, inetntoa (q. To. ip), q. To. port) ; } void ForwardPacket (struct Query *q_response) { struct Query newquery ; UINT nextHop = GetNextHop (q_response->FinalDst. id) ; newquery = *response ; newquery. From = GetMyLocation () ; newquery. To = GetLocation (nextHop) ; SendQueryData (newquery) ;//Forward the packet to the nextHop } void HandleResponse (struct Query *q_response) { int index ; if ( ! StabilizeWakeUp (qresponse)) { switch (q_response->QueryType &-ResponseMask) I case QueryType AskPredecessor : //printf ("Response to AskPredecessor, but didn't wakeup any thread... \n") ;

//printf ("Probably had a timeout and now here I am.. unable to fo anything... \n") ; break ; case QueryType FindSuccessor : UpdateLocation (qresponse->ResponseData) ; index = GetFingerIndex (q_response->QueryData. id) ; SetFinger (index, q_response->ResponseData. id) ; break ; default : fprintf (stderr,"ERROR : Unknown QueryType found\n") ; exit (-3) ; break ; } void HandleQuery (struct Query *query) { UINT start, myID, mySucc ; switch (query->QueryType) { case QueryType AskPredecessor : struct Query response ; q response = MakeStandardQuery (query->OrigSrc. id, query- >OrigSrc. id, QueryType AskPredecessor ResponseMask) ; q-response. QueryID = query->QueryID ; response. QueryData = query->QueryData ; q-response. ResponseData = GetLocation (GetMyPredecessor ()) ; SendQueryData (q_response) ; break ; case QueryTypeNotify : UpdateLocation (query->QueryData) ; //UpdatePredecessor (query->QueryData. id) ; SetPredecessor (query->QueryData. id) ; break ; case QueryType FindSuccessor : start = query->QueryData. id ; myID = GetMyID (.) ; mySucc = GetMySuccessor () ; if (Belongs (start, GetIthStart (0), mySucc, 1, 1, FALSE)) { struct Query response = MakeStandardQuery (query- >OrigSrc. id, query->OrigSrc. id, QueryType FindSuccessor I ResponseMask) ; q-response. QueryID = query->QueryID ; response. QueryData = query->QueryData ; response. ResponseData = GetLocation (mySucc) ; SendQueryData (q_response) ; else { UINT nextNode = GetClosestPrecedingFinger (start) ; if (nextNode == myID) fprintf (stderr,"ERROR : Finger Table bad\n") ; struct Query forward = *query ; forward. From = GetMyLocation () ; forward. To = q_forward. FinalDst = GetLocation (nextNode) ;

SendQueryData(q_forward); } break; default : fprintf (stderr, "ERROR : Unknown QueryType found\n") ; exit (-2); break; void *RecvThread (void *arg) /* struct Thread Input TI;//This is for passing the thread index and the query to the thread which'11 //handle this query.. We assume that the thread will quickly copy this data into its local space, //so that this structure becomes redundant before we overwrite it at next packet recieve.

*/ char buf [MAXBUF] ; struct sockaddr *src_addr ; socklen_t srclen; while (TRUE) { struct Query *q_response; int datalen = recvfrom (chord socket, buf, MAXBUF, 0, srcaddr, &srclen); if (datalen <= 0) continue; //printf ("YO ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! Recieved A Packet of length % d\n", datalen); if (datalen < sizeof (struct Query)) { printf ("Error: Insufficient Data recieved\n"); exit (-2) ; //Process Data response = (struct Query *) buf; //Validate (qresponse, srcaddr) ; //printf ("Updating From and OrigSrc in the HashTable\n"); UpdateLocation (qresponse->From) ; UpdateLocation (q_response->OrigSrc) ; //printf ("Finished Updating From and OrigSrc in the HashTable\n"); //Now there can be 3 possible type of packets we can recieve //1) Those for which FinalDst. id is not our ID.

//In this case we just have to forward the packet to the appropriate nexthop //2) A response to one of our earlier queries //In this case we store the query response and wake up the appropriate thread

//3) A query for us to respond //In this case we start a new thread to handle this query..

//Case 1: FinalDst. id ! = if(q_response->FinalDst.id != GetMyID()) { // printf ("To be forwarded\n"); ForwardPacket (q_response) ; /* int thread index = FindAndLockThread (); TI. index = thread index; TI. query = *response ; pthreadcreate (&Threads [threadindex]. thread, NULL, ForwardPacket, &TI); WaitAMoment ();//Wait to give this thread a chance to copy TI to its local space..

*/ continue; // Get back to recieving packets } // Case 2: A Response to one of our earlier queries if (q_response->QueryType & ResponseMask) { // printf("A Response to our query, type=% d\n", q_response->QueryType &-ResponseMask) ; //A response to one of our queries...

HandleResponse (q_response) ; /* int Qid = q_response->QueryID ; int sem index = CopyResponseData (Qid, q response) ; if (sem_index >= 0) sem_post (&sems [sem index]. sem); */ } else { // A Query for us to respond !!!! //printf ("A Query for us to respond, type=%d\n", q_response->QueryType) ; HandleQuery (q_response) ; /* int thread index = FindAndLockThread (); printf ("Found % d thread free\n", thread_index) ; TI. index = thread index ; TI. query = *response ; pthreadcreate (&Threads [threadindex]. thread, NULL, RespondToQuery, &TI); */ } } } struct Query MakeStandardQuery (UINT to, UINT finaldst, int QueryType) struct Query query; query. From = query. OrigSrc = GetMyLocation ();

query. To = GetLocation (to); query. FinalDst. id = finaldst; query. QueryID = GetNewQueryID (); query. QueryType = QueryType; return query; } struct Query SendQueryAndGetResponse (struct Query query) struct Query q-response ; Stabilize_SetupSleep (query. QueryID); //Let send the query SendQueryData (query); for (int time_slept=O ; time_slept < MAX_POLL_TIME ; time_slept += MIN POLL TIME) { usleep (MIN_POLL_TIME) ; if (Stabilize_CheckForResponse()) { q_response = Stabilize_GetResponse (); return q_response; } } q_response. ResponseData.id = UINT_ERROR; return response ; UINT RemoteAskPredecessor (UINT helper_id) { //printf ("Sending AskPredecessor query to % d\n", helper_id) ; struct Query query, response; query = MakeStandardQuery (helper_id, helperid, QueryType AskPredecessor) ; query. QueryData = GetLocation (helper_id) ; response = SendQueryAndGetResponse (query); //Now we have the data in response struct location result = response. ResponseData; if (result. id ! = UINT_ERROR) UpdateLocation (result); return result.id; } void Remote Notify (UINT successor) { struct Query query, response; query = MakeStandardQuery (successor, successor, QueryTypeNotify) ; query. QueryData = GetMyLocation (); //Send this notification packet..

SendQueryData(query); } void *SOS_Helper(void *arg) { struct sockaddrin myaddr;

struct sockaddr remote addr ; socklen t remote len ; char buffer [MAXBUF] ; bzero ( (char *) &myaddr, sizeof (my-addr)) ; //************************** Start of changes for interface to route module int rtemodsock ; my_addr.sin_family = AF_INET ; my_addr.sin_addr.s_addr = htonl (INADDRANY) ; my_addr.sin_port = htons (RTE_MOD_PORT) ; if ((sos_socket = socket (AF_INET, SOCK_STREAM, 0) ) < 0) { perror ("communciation module socket error"); exit (-4); } /* bind server port */ if (bind(sos_socket, (struct sockaddr *) &myaddr, sizeof (myaddr)) <0) { perror ("cannot bind port") ; exit (-5); } /* listen */ if (listen (sos_socket, 5) < 0) { perror ("communication module listen error") ; exit (1); } /* accept connection */ remote len = sizeof (remote addr) ; if ((rte_mod_sock = accept (sos socket, (struct sockaddr *) &remoteaddr, &remotelen)) < 0) { perror ("communication module accept error") ; exit (1) ; } while (TRUE) { int datalen = recv (rte mod sock, buffer, MAXBUF, 0); if (datalen <= 0) ; {perror ("recvfrom error") ;} char result [MAXBUF]; //Change by Sharat if (buffer) { FindNextHop (buffer, result); // strcpy (result, buffer);//for testing //printf ("Got nextHop IP = %s\n", result); if (send (rte mod sock, result, strlen (result), 0) < 0) {perror ("sendto error") ;} } }//end of while } //******** END OF CHANGES FOR ROUTE MODULE INTERFACE /* UINT Remote_FindSuccessor (UINT helper_id, UINT id) {

printf ("Sending Find Successor query for % d to % d\n", id, helper id) ; struct Query query, response ; query = MakeStandardQuery (helper_id, helper-id, QueryType_FindSuccessor) ; query. QueryData. id = id ; response = SendQueryAndGetResponse (query) ; //Now we have the data in response struct location result = response. ResponseData ; UpdateLocation (result) ; return result. id ; } UINT RemoteFindMySuccessor (UINT helper_id) return Remote FindSuccessor (helper id, GetMyID ()) ; UINT RemoteFindPredecessor (UINT helper_id, UINT id) { struct Query query, response ; query = MakeStandardQuery (helper_id, helper_id, QueryType_FindPredecessor) ; query. QueryData. id = id ; response = SendQueryAndGetResponse (query) ; //Now we have the data in response struct location result = response. ResponseData ; UpdateLocation (result) ; return result. id ; } UINT RemoteFindMyPredecessor (UINT helper_id) return Remote FindPredecessor (helper_id, GetMyID ()) ; } void RemoteUpdateFingerTable (UINT dst, int k) { struct Query query ; query = MakeStandardQuery (dst, dst, QueryType_UpdateFingerTable) ; query. QueryData. id = k ; SendQueryData (query) ; UINT RemoteAskFingerEntry (UINT helper-id, int k) - struct Query query, response ; query = MakeStandardQuery (helperid, helperid, QueryTypeAskFingerEntry) ; query. QueryData. id = k ; response = SendQueryAndGetResponse (query) ; //Now we have the data in response struct location result = response. ResponseData ; UpdateLocation (result) ; return result. id ;

UINT Remote_FindMyFingerEntry (UINT helper_id, int k) { if(k == 1) printf ("\n\n\n@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@\n\n") ; return RemoteFindSuccessor (helperid, GetIthStart (k) ) ; void Remote-Notify (UINT successor) { struct Query query, response; query = MakeStandardQuery (successor, successor, QueryTypeNotify) ; query. QueryData = GetMyLocation () ; //Send this notification packet..

SendQueryData (query); } struct Query SendQueryAndGetResponse (struct Query q) { //Steps //1) Find a semaphore which is free and lock it //2) Send the query data through the global socket //3) Wait on the semaphore //4) Now copy the result from the query struct in your semaphore structure //5) Unlock the semaphore //6) Return the local query structure struct Query response; //Step 1: int sem index = FindAndLockSemaphore (q. QueryID); if (sem index < 0) { printf ("Error : No. of threads exceeded MAX-THREADS\n") ; exit (-1); } // Step 2: SendQueryData (q); //Step 3: sem wait (&sems [semindex]. sem); //Step 4: response = GetResponseData (sem_index) ; //Step 5: UnlockSemaphore (sem_index) ; //Step 6: return response; }

void SendQueryData (struct Query q) { struct sockaddr in dst addr ; bzero ( (char *) &dst_addr, sizeof (dst addr)) ; dstaddr. sinfamily = AF_INET ; //dstaddr. sinaddr. saddr = htonl (q. To. ip. s_addr) ; dst_addr. sin_addr. s_addr = q. To. ip. s addr ; //dstaddr. sinaddr. saddr = htonl (INADDRANY) ; //inetpton (AFINET,"127. 0. 0. 1", &dstaddr) ; dstaddr. sinport = htons (q. To. port) ; sendto (sock fd, (char *) &q, sizeof (q), 0, (struct sockaddr *) &dstaddr, sizeof (dst addr)) ; printf ("Sent Query of type = % d, to ip=% s, port=% d\n", q. QueryType &-ResponseMask, inet-ntoa (q. To. ip), q. To. port) ; I UINT Find Predecessor (UINT id) { if (id == GetMyID ()) return GetMyPredecessor () ; printf ("Outside id=% d, start=% d, end=% d\n", id, GetIthStart (0), GetMySuccessor ()) ; if (Belongs (id, GetIthStart (0), GetMySuccessor (), 1, 1).) { printf ("Inside id=% d, start=% d, end=% d\n, id, GetIthStart (0), GetMySuccessor ()) ; return GetMyID () ; I else { UINT nexthop = GetNextHop (id) ; printf ("nexthop = % d\n", nexthop) ; return RemoteFindPredecessor (nexthop, id) ; } */ //added for SOSHelper function-interface to route-module #define RTE MOD PORT 3456 //-----end of changes struct location { UINT id ; struct in-addr ip ; in_port_t port ; } ; struct Query { //The original sender of this query

//If I have the answer to this query then I will respond to OrigSrc, else I'll send the query to the appropriate node struct location OrigSrc ; //Myself, when I am sending the packet, or the previous hop when I recieve the packet struct location From ; //Next Hop or myself when I'm recieving this packet struct location To ; //Final Destination for this packet //Usually the ip and port in this wont be filled because the OrigSrc doesn't know them, //otherwise it could've sent the packet directly struct location FinalDst ; //QueryID : unique for a query for a node UINT'QueryID ; //Type of query UINT QueryType ; struct location QueryData ; struct location ResponseData ; } i void SendQueryData (struct Query q) ; void ForwardPacket (struct Query *q_response) ; void HandleResponse (struct Query *q_response) ; void HandleQuery (struct Query *query) ; void *RecvThread (void *arg) ; struct Query MakeStandardQuery (UINT to, UINT finaldst, int QueryType) ; struct Query SendQueryAndGetResponse (struct Query query) ; UINT RemoteAskPredecessor (UINT helper_id) ; void Remote-Notify (UINT successor) ; int HashTable : : hash (UINT id) { return (id+MAXHASH) % MAXHASH ; } void HashTable : : Update (UINT id, struct in-addr ip, in_port_t port) { int index = hash (id) ; struct mapping *tmp ; //printf ("In Update id=% d, ip=% d, port=% d, index=% d\n", id, ip, port, index) ;

for (tmp = Hash [index] ; tmp ! = NULL ; tmp = tmp->next) { if (tmp->id == id) break ; ) if (tmp == NULL) { //New Entry tmp = Hash [index] ; Hash [index] = (struct mapping *) malloc (sizeof (struct mapping)) ; Hash [index]->id = id ; Hash [index]->sinaddr = ip ; Hash [index]->sin_port = port ; Hash [index]->next = tmp ; } else \//Entry already exists tmp->sinaddr = ip ; tmp->sin_port = port ; } void HashTable : : Delete (UINT id) { int index = hash (id) ; struct mapping *tmp, *prev ; for (prev = tmp = Hash [index] ; tmp ! = NULL ; tmp = tmp->next) { if (tmp->id == id) break ; prev = tmp ; } if (tmp ! = NULL) if (tmp == Hash [index]) Hash [index] = tmp->next ; else prev->next = tmp->next ; } UINT HashTable : : FindLowestNode () { UINT myID = GetMyID () ; int curr min = MAXN ; UINT curr lowest = myID ; struct mapping *tmp ; for (int i=O ; i<MAX HASH ; i++) { for (tmp = Hash [i] ; tmp ! = NULL ; tmp = tmp->next) int new min = (tmp->id + MAXN-myID) % MAXN ;

if ( (new min < currmin) && (new min > o)) { currmin = new min ; curr_lowest = tmp->id ; return currlowest ; } void HashTable : : Update (struct location loc) { Update (loc. id, loc. ip, loc. port) ; I struct in-addr HashTable : : strTOip (char *IPStr) { struct in_addr ip ; inet aton (IPStr, &ip) ; return ip ; } inportt HashTable : : strTOport (char *PortStr) in_port_t port= atoi (PortStr) ; //printf ("% s : string=<% s>, port=% d\n", FUNCTION, PortStr, port) ; return port ; } UINT HashTable : : ParseAndAddLocation (char *str) { //The string is of the form IP : port //Add this location in the hashtable and return the ID printf ("Parsing String <% s>\n", str) ; char *colon = strchr (str,' :') ; if (colon == NULL) return UINT ERROR ; colon [ol = 0 ; colon++ ; //Get IP struct in-addr ip = strTOip (str) ; //Get port in_port_t port = strTOport (colon) ; //Get chordID UINT id = ChordHash (ip, port) ; //Add to Hash Table Update (id, ip, port) ; //Return ID return id ; } struct location HashTable : : GetLocation (UINT id) f //printf ("GetLocation called for ID % d\n", id) ; int index = hash (id) ;

struct mapping *tmp ; struct location loc ; for (tmp = Hash [index] ; tmp ! = NULL ; tmp = tmp->next) if (tmp->id == id) break ; if (tmp == NULL) printf ("Error : Location not found for id = % d\n", id) ; //Error : entry for id not found loc. id = UINT ERROR ; } else loc. id = id ; loc. ip = tmp->sinaddr ; loc. port = tmp->sin_port ; //printf ("And I found id=% d, ip=% s, port=% d\n", id, inetntoa (loc. ip), loc. port) ; } return loc ; void HashTable : : GetIPFromID (UINT id, char resultIP []) for (int i=o ; i < MAXHASH ; i++) { for (struct mapping *tmp=Hash [i] ; tmp ! = NULL ; tmp = tmp- >next) if (tmp->id == id) { sprintf (resultIP, inetntoa (tmp->sinaddr)) ; return ; } } UINT HashTable : : GetIDFromIP (char inputIP []) struct in addr IPaddr ; inetaton (inputIP, &IPaddr) ; for (int i=O ; i < MAXHASH ; i++) for (struct mapping *tmp=Hash [i] ; tmp ! = NULL ; tmp = tmp- >next) if (tmp->sinaddr. saddr == IPaddr. saddr) return tmp->id ; } return UINT ERROR ; }

//Hash Table to store chordID to IP: port mappings struct mapping { UINT id; struct in addr sin addr ; in_port_t sin_port ; struct mapping *next ; } ; #define MAX HASH 100 class HashTable { // The hash table key would be the chord ID //and this will be an open hash table struct mapping *Hash [MAXHASH] ; public: HashTable () { for (int i=0 ; i<MAX HASH ; i++) Hash [i] = NULL; } int hash (UINT id); void Delete (UINT id); UINT FindLowestNode () ; void GetIPFromID (UINT id, char resultIP []) ; UINT GetIDFromIP (char inputIP []) ; void Update (UINT id, struct in-addr ip, in_port_t port); void Update (struct location); struct in-addr strTOip (char *IPStr); in_port_t strTOport (char *PortStr); UINT ParseAndAddLocation (char *str); struct location GetLocation (UINT); }; HashTable *hashtable; <BR> <BR> <BR> <BR> <BR> <BR> <BR> ==============================================<BR> &num include "main.h" void usage (char *str) { fprintf (stderr, "usage: %s <MyIP:port> -j <HelperIP : port>\n", str); exit (-1); } void InitSocket ()

struct sockaddrin myaddr; struct location address = GetMyLocation () ; bzero ( (char *) &my_addr, sizeof (my_addr)) ; my_addr.sin_family = AF_INET ; my_addr.sin-addr.s_addr = address. ip. s-addr ; my_addr. sin_port = htons (address. port); chord-socket = socket (AFINET, SOCKDGRAM, 0); if (chord sockt <= 0) { perror ("socket error"); exit (-7); } //printf ("Trying to bind socket=% d, ip=% d, port=% d\n", chord_socket, address. ip. s_addr, address. port); if (bind (chord_socket, (struct sockaddr *) &myaddr, sizeof (my_addr)) < 0) perror ("bind error") ; exit (-8); } } void InitSemaphores() { seminit (&tablesem, 0,1) ; seminit (&hashsem, 0,1) ; seminit (&mutexsem, 0, 1) ; ) void Initialize (int myID, int helper_id) { mytable = new MyTable (myID, helper_id); InitSocket () ; pthreadcreate (&recvthread, NULL, RecvThread, NULL); pthreadcreate (&sosthread, NULL, SOSHelper, NULL); } void StabilizeSuccessor () UINT myID = GetMyID (); UINT newSucc ; UINT mySucc ; while (TRUE) mySucc = GetMySuccessor () ; if (mySucc ! = myID) newSucc = RemoteAskPredecessor (mySucc); } else newSucc = GetMyPredecessor () if (newSucc == UINT ERROR) {

//printf ("RemoteAskPredecessor Failed\n"); ResetStabilizeTimer (); if (SetNextSuccessor (mySucc)) { mySucc = GetMySuccessor(); Remote-Notify (mySucc); } else break; } else { if (Belongs (newSucc, myID, mySucc, 0, 0, TRUE)) { ResetStabilizeTimer (); SetFinger (0, enwSucc); } break; } } mySucc = GetMySuccessor (); Remote Notify (mySucc); } void FindSuccessor (UINT start) { UINT myID = GetMyID(); UINT mySucc = GetMySuccessor(); if (Belongs(start, GetIthStart(0), mySUcc, 1, 1, FALSE)) { int index = GetFingerIndex (start); SetFinger (index, mySucc) ; else else UINT nextNode = GetClosestPrecedingFinger (start); if (nextNode == myID) fprintf (stderr, "ERROR : Finger Table bad\n"); struct Query q = MakeStandardQuery (nextNode, nextNode, QueryType_FindSuccessor) ; q. QueryData. id = start; SendQueryData (q); } } void FixFingers() UINT myID = GetMyID (); UINT mySucc = GetMySuccessor (); if (myID == mySucc) return; for (int i=l ; i < LOGN ; i++) { //This should be non-blocking....

FindSuccessor (GetIthStart(i)); } } void Stabilize() {

//Stabilizing thread... while (TRUE) { PrintFingerTable (CURRSTABILIZETIMER) ; CURRSTABILIZETIMER *= 2 ; CURR STABILIZE TIMER = (CURR STABILIZE TIMER > MAXTIMER) ? (MAXTIMER) : (CURRSTABILIZETIMER) ; StabilizeSuccessor () ; FixFingers () ; usleep (CURRSTABILIZETIMER) ; } void JoinNetwork (UINT helper_id) { //UINT myID = GetMyID () ; //FindSuccessor (myID) ; UINT mySucc = GetMySuccessor () ; Remote-Notify (mySucc) ; } main (int argc, char *argv []) { if (argc < 4) usage (argv [0]) ; hashtable = new HashTable () ; InitSemaphores () ; //printf ("Lets Parse the locations\n") ; UINT myID = ParseAndAddLocation (argv [1]) ; if (strcmp (argv [2],"-j") ! = 0) usage (argv [0]) ; UINT helper_id = ParseAndAddLocation (argv [3]) ; //Initialize the data structures and start the recieving thread.. Initialize (myID, helper-id) ; //Lets Join the network if (myID ! = helper_id) JoinNetwork (helper_id) ; //Turn into a stabilizing routine... Stabilize () ; } #include <stdio. h> #include <stdlib. h> #include string. h> #include <ctype. h> #include <unistd. h> #include <sys/socket. h> #include <arpa/inet. h>

#include <netinet/in. h> #include <netdb. h> #include <sys/un. h> #include"pthread. h" #include"semaphore. h" #define UINT unsigned int #define BOOL char #define TRUE 1 #define FALSE 0 #define UINT ERROR 12345678 //Query Types #define ResponseMask 0x10000000 #define QueryType AskPredecessor 1 #define QueryTypeNotify 2 #define QueryType-FindSuccessor 3 //#define QueryType_FindPredecessor 4 //&num define QueryType_AskFingerEntry 5 //#define QueryType_UpdateFingerTable 6 inline void ASSERT (BOOL a) { if (!a) { fprintf (stderr, "ASSERT FAILED at LINE % d, function %s\n", LINE, FUNCTION) ; } static int pow(int a, int b) { if (b == 0) return 1; else return a * pow (a, b-1); } const int LOGN = 5; const int MAXN = pow (2, LOGN); //Default Target Port for nextHop queries from the SOS administrative module //This can be arbitrary.... const int DEFAULT_TARGET_PORT = 80; //Minimum Stabilize timer value in microseconds.. const int MIN_TIMER = 1000000; //Maximum Stabilize timer value in microseconds.. const int MAXTIMER = 4000000; //Current Frequency of Stabilizing Thread int CURRSTABILIZETIMER = MIN_TIMER ;

//Minimum Poll time for Successor update const int MIN POLL TIME = 10000 ; //Maximum Poll time for Successor update const int MAXPOLLTIME = 10 * MIN POLL TIME ; //Buffer size for socket communications const int MAXBUF = 512 ; //Main UDP socket to communicate with other chord nodes.. int chord-socket ; //Unix Domain Socket to communicate with SOS administration module int sossocket ; //Socket name for Unix Domain Communication with SOS communication module #define UDSPATH"/tmp/kamra/sos-path" //Threads and Semaphore Declarations... thread recvthread ; pthreadt sosthread ; sem t table sem ; sem-t hash-sem ; semt mutexsem ;//Generally used for all kinds of mutual exclusion... #include"hash. h" #include"table. h" #include"comm. h" //Utility Functions... void ResetStabilizeTimer () { CURRSTABILIZETIMER = MINTIMER ; } UINT ChordHash (struct in-addr ip, in_port_t port) I I return (ip. s addr + port) % MAXN ; } void LockFingerTable () { sem wait (&tablesem) ; } void UnLockFingerTable () I sem_post (&table_sem) ; } void LockHashTable () f semwait (&hashsem) ; }

void UnLockHashTable() { sem_post (&hash_sem); } void PrintFingerTable (int curr_timer) { LockFingerTable () ; mytable->print (currtimer) ; UnLockFingerTable () ; } void SetFinger (int index, UINT id) { LockFingerTable () ; mytable->SetFinger (index, id); UnLockFingerTable () ; } void SetPredecessor(UINT id) { LockFingerTable(); mytable->SetPredecessor (id); UnLockFingerTable () ; } UINT GetMyID() { LockFingerTable(); UINT myid = mytable->GetMyID () ; UnLockFingerTable () ; return myid; } UINT GetIthStart (UINT myID, int k) UINT start = (myID + pow (2, k) + MAX_N) % MAX_N ; return start; } UINT GetIthStart(int k) { UINT myID = GetMyID () ; return GetIthStart (myID, k); } /* UINT GetIthEnd (int k) UINT id = GetMyID () ; UINT end = (id-pow (2, k) + MAX_N) % MAX_N ; return end; */ UINT GetIDFromIP(char inputIP[]) { LockHashTable(); UINT id = hashtable->GetIDFromIP (inputIP);

UnLockHashTable () ; return id; } void GetIPFromID(UINT id, char result[]) { LockHashTable(); hashtable->GetIPFromID (id, result); UnLockHashTable(); } UINT GetFinger(int k) { LockFingerTable () ; UINT finger = mytable->GetFinger (k); UnLockFingerTable () ; return finger; } UINT GetMySuccessor() { return GetFinger(0); } void DeleteFromCache(UINT id) ( LockHashTable () ; hashtable->Delete (id); UnLockHashTable(); } UINT FindLowesFromHash() { LockHashTable(); UINT next = hashtable->FindLowestNode () ; UnLockHashTable () ; return next; } void ReplaceFingerEntries(UINT prev, UINT replacement) { LockFingerTable () ; mytable->ReplaceFingerEntries (prev, replacement); UnLockFingerTable(); } BOOL SetNetSuccessor(UINT start_id) //Step 1: Delete start_id from the Cache... (Hash Table) //Step 2: Find the lowest node greater than MyID in the Cache...

//Step 3: Check all entries in the Finger Table and the Predecessor and replace all //occurances of start id with this new node...

//Step 4.1 : If this lowest node is == myID return FALSE..

//Step 4.2 : return TRUE //Step 1: DeleteFromCache (starting) ;

//Step 2: UINT newsucc = FindLowestFromHash () ; //Step 3: ReplaceFingerEntries (startid, newsucc) ; //Step 4: if (newsucc == GetMyID ()) return FALSE; else return TRUE; } UINT GetMyPredecessor() { LockFingerTable(); UINT pred = mytable->GetPredecessor () ; UnLockFingerTable() ; return pred; void UpdatePredecessor(UINT newpred) { LockFingerTable(); mytable->UpdatePredecessor (newpred); UnLockFingerTable(); } BOOL Belongs (UINT mid, UINT start, UINT end, int LeftInclusive, int RightInclusive, BOOL ShouldContain) { if(!LeftInclusive && (mid == start)) return FALSE; if ( ! RightInclusive && (mid == end)) return FALSE; //Returns true if mid lies between start and end inclusive in circular order BOOL flag; if ((end == start) && ( ! ShouldContain)) flag = (end >= start); } else flag = (end > start); if (flag) if ( (mid >= start) && (mid <= end)) return TRUE; else { if ( (mid >= start) ll (mid <= end)) return TRUE; return FALSE; }

UINT ParseAndAddLocation(char *ipStr) { LockHashTable(); UINT id = hashtable->ParseAndAddLocation (ipStr) ; UnLockHashTable () ; return id; } struct location GetLocation(UINT id) { LockHashTable () ; struct location loc = hashtable->GetLocation (id); UnLockHashTable () ; return loc; } struct location GetMyLocation() { return GetLocation(GetMyID()); } void UpdateLocation(struct location loc) { LockHashTable(); hashtable->Update (loc); UnLockHashTable(); } UINT GetNextHop(UINT id) { LockFingerTable () ; UINT nextHop = mytable->GetNextHop (id); UnLockFingerTable () ; return nextHop ; } int GetFingerIndex (UINT start) { UINT myID = GetMyID () ; int power2 = (start + MAXN-myID) % MAXN ; int index = 0; while (power2 > 1) index++; power2/= 2; } return index; } UINT GetClosestPrecedingFinger(UINT id) LockFingerTable () ; UINT nextHop = mytable->GetClosestPrecedingFinger (id); UnLockFingerTable () ; return nextHop ; } int GetNewQueryID () { static int currid=12 ;

return ++currid ; } void FindNextHop (char input [], char output []) { struct in-addr ip ; if (strcmp (input,"0. 0. 0. 0") == 0) { fprintf (stderr,"Got request from the administrative module to exit\nComplying... \n") ; exit (-6) ; } inetaton (input, &ip) ; //UINT dst = GetIDFromIP (input) ; UINT dst = ChordHash (ip, DEFAULT TARGET PORT) ; UINT nextHop = GetNextHop (dst) ; GetIPFromID (nextHop, output) ; } /* void WaitAMoment () { usleep (100000) ; */ #define FREE 0 #define WAITING 1 #define ZOMBIE 2 int Stabilize Qid ; int Stabilize Status ; struct Query Stabilize Response ; BOOL StabilizeWakeUp (struct Query *q response) BOOL flag = FALSE ; semwait (&mutexsem) ; if (Stabilize_Qid == q_response->QueryID) ASSERT (Stabilize Status == WAITING) ; Stabilize Status = ZOMBIE ; Stabilize-Response = *response ; flag = TRUE ; sem_post (&mutex-sem) ; return flag ; ) void Stabilize_SetupSleep (int qid) { semwait (&mutexsem) ; ASSERT (Stabilize Status == FREE) ;

Stabilize-Qid = qid ; Stabilize Status = WAITING ; sem_post (&mutex sem) ; } BOOL StabilizeCheckForResponse () { BOOL flag = FALSE ; semwait (&mutexsem) ; ASSERT (Stabilize Status 1= FREE) ; if (Stabilize Status == ZOMBIE) { Stabilize Qid = 0 ; Stabilize Status = FREE ; flag = TRUE ; } sem_post (&mutex_sem) ; return flag ; } struct Query StabilizeGetResponse () { struct Query response ; semwait (&mutexsem) ; response = Stabilize Response ; sem_post (&mutex sem) ; return response ; } #include"table. cc" #include"hash. cc" #include"comm. cc" all : all : gcc-o sos-chord main. cc-lpthread 2>&1 |more ; ctags-R. clean : rm-f sos-chord *. o void SendQueryData (struct Query q) { struct sockaddr in dst addr ; bzero ( (char *) &dst_addr, sizeof (dst addr)) ; dstaddr. sinfamily = AF-INET ; dst_addr. sin_addr. s_addr = q. To. ip. s addr ; dst_addr. sin_port = htons (q. To. port) ; sendto (chord socket, (char *) &q, sizeof (q), 0, (struct sockaddr *) &dstaddr, sizeof (dst_addr)) ;

//printf ("Sent Query of type = % d, to ip=% s, port=% d\n", q. QueryType &-ResponseMask, inetntoa (q. To. ip), q. To. port) ; I void ForwardPacket (struct Query *q_response) struct Query newquery ; UINT nextHop = GetNextHop (q_response->FinalDst. id) ; newquery = *response ; newquery. From = GetMyLocation () ; newquery. To = GetLocation (nextHop) ; SendQueryData (newquery) ;//Forward the packet to the nextHop } void HandleResponse (struct Query *q_response) int index ; if (lStabilize_WakeUp (q_response)) { switch (qresponse->QueryType &-ResponseMask) case QueryType AskPredecessor : //printf ("Response to AskPredecessor, but didn't wakeup any thread... \n") ; //printf ("Probably had a timeout and now here I am.. unable to fo anything... \n") ; break ; case QueryType FindSuccessor : UpdateLocation (q_response->ResponseData) ; index = GetFingerIndex (q_response->QueryData. id) ; SetFinger (index, q_response->ResponseData. id) ; break ; default : fprintf (stderr,"ERROR : Unknown QueryType found\n") ; exit (-3) ; break ; } } void HandleQuery (struct Query *query) UINT start, myID, mySucc ; switch (query->QueryType) f case QueryType AskPredecessor : struct Query q-response ; response = MakeStandardQuery (query->OrigSrc. id, query- >OrigSrc. id, QueryType_AskPredecessor | ResponseMask) ; q-response. QueryID = query->QueryID ; response. QueryData = query->QueryData ; q-response. ResponseData = GetLocation (GetMyPredecessor ()) ;

SendQueryData (q_response) ; break; case QueryTypeNotify : UpdateLocation (query->QueryData); //UpdatePredecessor (query->QueryData. id); SetPredecessor (query->QueryData. id); break; case QueryType FindSuccessor : start = query->QueryData. id; myID = GetMyID () ; mySucc = GetMySuccessor () ; if (Belongs (start, GetIthStart (0), mySucc, 1,1, FALSE) ) struct Query q response = MakeStandardQuery (query- >OrigSrc. id, query->OrigSrc. id, QueryType FindSuccessor ResponseMask); q-response. QueryID = query->QueryID q response. QueryData = query->QueryData q-response. ResponseData = GetLocation (mySucc); SendQueryData(q_response); } else { UINT nextNode = GetClosestPrecedingFinger (start); if (nextNode == myID) fprintf (stderr,"ERROR : Finger Table bad\n") ; struct Query forward = *query; forward. From = GetMyLocation () ; q-forward. To = q-forward. FinalDst = GetLocation (nextNode) ; SendQueryData(q_forward); } break; default: fprintf (stderr, "ERROR : Unknown QueryType found\n") ; exit (-2); break; } } void *RecvThread (void *arg) /* struct Thread_Input TI; // This is for passing the thread index and the query to the thread which'li //handle this query.. We assume that the thread will quickly copy this data into its local space, //so that this structure becomes redundant before we overwrite it at next packet recieve.

*/ char buf [MAXBUF] ; struct sockaddr *src_addr ; socklen t srclen; while (TRUE) { struct Query *response ; int datalen = recvfrom (chord-socket, buf, MAXBUF, 0, srcaddr, &srclen); if (datalen <= 0)

continue ; //printf ("YO ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! Recieved A Packet of length % d\n", datalen) ; if (datalen < sizeof (struct Query)) { printf ("Error : Insufficient Data recieved\n") ; exit (-2) ; } //Process Data q-response = (struct Query *) buf ; //Validate (q_response, srcaddr) ; //printf ("Updating From and OrigSrc in the HashTable\n") ; UpdateLocation (qresponse->From) ; UpdateLocation (q_response->OrigSrc) ; //printf ("Finished Updating From and OrigSrc in the HashTable\n") ; //Now there can be 3 possible type of packets we can recieve //1) Those for which FinalDst. id is not our ID. //In this case we just have to forward the packet to the appropriate nexthop //2) A response to one of our earlier queries //In this case we store the query response and wake up the appropriate thread //3) A query for us to respond //In this case we start a new thread to handle this query.. //Case 1 : FinalDst. id ! = myID if (q_response->FinalDst. id ! = GetMyID ()) { //printf ("To be forwarded\n") ; ForwardPacket (q_response) ; /* int thread index = FindAndLockThread () ; TI. index = thread index ; TI. query = *response ; pthreadcreate (&Threads [threadindex]. thread, NULL, ForwardPacket, &TI) ; WaitAMoment () ;//Wait to give this thread a chance to copy TI to its local space.. */ continue ;//Get back to recieving packets } //Case 2 : A Response to one of our earlier queries if (q_response->QueryType & ResponseMask) { //printf ("A Response to our query, type=% d\n", q_response->QueryType &-ResponseMask) ; //A response to one of our queries... HandleResponse (q_response) ;

/* int Qid = q_response->QueryID ; int sem index = CopyResponseData (Qid, response) ; if (sem_index >= 0) sem_post (&sems [semindex]. sem); */ } else //A Query for us to respond !!! ! //printf ("A Query for us to respond, type=% d\n", q_response->QueryType) ; HandleQuery (q_response) ; /* int thread index = FindAndLockThread () ; printf ("Found % d thread free\n", thread_index) ; TI. index = thread index TI. query = *response ; pthreadcreate (&Threads [threadindex]. thread, NULL, RespondToQuery, &TI); */ } struct Query MakeStandardQuery(UINT to, UINT finaldst, int QueryType) { struct Query query; query. From = query. OrigSrc = GetMyLocation (); query. To = GetLocation (to); query. FinalDst. id = finaldst; query. QueryID = GetNewQueryID (); query. QueryType = QueryType; return query; } struct Query SendQueryAndGetResponse (struct Query query) { struct Query response ; Stabilize_SetupSleep (query. QueryID) ; //Let send the query SendQueryData (query); for (int time_slept=O ; time_slept < MAXPOLLTIME ; time_slept += MIN POLL TIME) { usleep (MIN_POLL_TIME) ; if (Stabilize_CheckForResponse()) { q_response = Stabilize_GetResponse(); return q_response; } } q_response.ResponseData.id = UINT_ERROR;

return q_response; } UINT Remote AskPredecessor(UINT helper id) { //printf ("Sending AskPredecessor query to % d\n", helperid) ; struct Query query, response; query = MakeStandardQuery (helperid, helperid, QueryType AskPredecessor) ; query. QueryData = GetLocation (helperid) ; response = SendQueryAndGetResponse (query); //Now we have the data in response struct location result = response. ResponseData; if (result. id! = UINT ERROR) UpdateLocation (result); return result.id; } void Remote Notify(UINT successor) { struct Query query, response; query = MakeStandardQuery (successor, successor, QueryType_Notify) ; query. QueryData = GetMyLocation () ; //Send this notification packet..

SendQueryData(query); } void *SOS_Helper(void *arg) struct sockaddr_un my_addr ; struct sockaddr remote addr ; socklen t remote len ; char buffer [MAXBUF] ; bzero ( (char *) &myaddr, sizeof (myaddr)) ; myaddr. sunfamily = AFUNIX ; sprintf (my_addr. sun_path, UDS_PATH) ; //Lets create the socket sossocket = socket (AFUNIX, SOCKDGRAM, 0); if (sossocket < 0) { perror ("UDS socket error") ; exit(-4); } // Unlink just in case it already exists... unlink (my_addr. sun_path) ; //printf ("Trying to bind socket=% d at path = <% s>\n", sos_socket, UDS_PATH) ; if (bind (sossocket, (struct sockaddr *) &myaddr, sizeof (my_addr)) < 0) { perror ("UDS bind error") ; exit (-5);

} while(TRUE) { int datalen = recvfrom(sos_socket, buffer, MAXBUF, 0, &remoteaddr, &remotelen) ; if(datalen <= 0) { perror("recvfrom error"); continue; } char result [MAXBUF] ; //printf ("Got query IP = % s\n", buffer); FindNextHop (buffer, result); //printf ("Got nextHop IP = % s\n", result); if (sendto (sos_socket, result, strlen (result), 0, (struct sockaddr *) &remote addr, sizeof (remote addr)) < 0) perror ("sendto error"); <BR> <BR> <BR> <BR> <BR> <BR> <BR> <BR> }<BR> } <BR> /* UINT Remote_FindSuccessor(UINT helper_id, UINT id) { printf("Sending Find_Successor query for %d to % d\n", id, helperid) ; struct Query query, response; query = MakeStandardQuery (helper_id, helper_id, QueryType_FindSuccessor) ; query. QueryData. id = id; response = SendQueryAndGetResponse (query); //Now we have the data in response struct location result = response. ResponseData; UpdateLocation (result); return result.id; } UINT Remote_FindMySuccessor(UINT helper_id) { return Remote_FindSuccessor(helper_id, GetMyID()); } UINT Remote_FindPredecessor(UINT helper_id, UINT id) { struct Query query, response; query = MakeStandardQuery (helper-id, helper_id, QueryType_FindPredecessor) ; query. QueryData. id = id; response = SendQueryAndGetResponse (query); //Now we have the data in response struct location result = response. ResponseData; UpdateLocation (result); return result.id; } UINT Remote_FindMyPredecessor(UINT helper_id)

return Remote_FindPredecessor (helper_id, GetMyID ()) ; void RemoteUpdateFingerTable (UINT dst, int k) { struct Query query; query = MakeStandardQuery (dst, dst, QuryType_UpdateFingerTable) ; query. QueryData. id = k; SendQuryData(query); } UNIT Remote_AskFingerEntry (UINT helper_id, int k) structiquery query, response; query = MakeStandardQuery (helperid, helperid, QueryTypeAskFingerEntry) ; query. QueryData. id = k; response = SendQueryAndGetResponse (query); //Now we have the data in response struct location result = response. ResponseData; UpdateLocation (result); return result.id; } UINT Remote_FindMyFingerEntry(UNIT helper_id, int k) if (k == 1) printf ("\n\n\n@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@\n\n") ; return Remote_FindSuccessor (helper_id, GetIthStart(k)); } void Remote Notify(UNIT successor) { struct Query query, response; query = MakeStandardQuery (successor, successor, QueryTypeNotify) ; query. QueryData = GetMyLocation () ; //Send this notification packet..

SendQueryData(query); } struct query SendQueryAndGetResponse(struct Query q) { // Steps //1) Find a semaphore which is free and lock it //2) Send the query data through the global socket //3) Wait on the semaphore //4) Now copy the result from the query struct in your semaphore structure //5) Unlock the semaphore //6) Return the local query structure

struct Query response ; //Step 1 : int sem index = FindAndLockSemaphore (q. QueryID) ; if (sem-index < 0) { printf ("Error : No. of threads exceeded MAX-THREADS\n") ; exit (-1) ; } //Step 2 : SendQueryData (q) ; //Step 3 : semwait (&sems [sem index]. sem) ; //Step 4 : response = GetResponseData (sem-index) ; //Step 5 : UnlockSemaphore (sem-index) ; //Step 6 : return response ; } void SendQueryData (struct Query q) { struct sockaddr in dst addr ; bzero ( (char *) &dst_addr, sizeof (dst addr)) ; dstaddr. sinfamily = AF_INET ; //dstaddr. sinaddr. saddr = htonl (q. To. ip. s_addr) ; dst_addr. sin_addr. s_addr = q. To. ip. s addr ; //dstaddr. sinaddr. saddr = htonl (INADDRANY) ; //inetpton (AF_INET,"127. 0. 0. 1", &dst_addr) ; dst-addr. sin_port = htons (q. To. port) ; sendto (sockfd, (char *) &q, sizeof (q), 0, (struct sockaddr *) &dstaddr, sizeof (dst addr)) ; printf ("Sent Query of type = % d, to ip=% s, port=% d\n", q. QueryType &-ResponseMask, inet ntoa (q. To. ip), q. To. port) ; I UINT Find Predecessor (UINT id) { if (id == GetMyID ()) return GetMyPredecessor () ; printf ("Outside id=% d, start=% d, end=% d\n", id, GetIthStart (0), GetMySuccessor ()) ; if (Belongs (id, GetIthStart (0), GetMySuccessor (), 1, 1)) { printf ("Inside id=% d, start=% d, end=% d\n", id, GetIthStart (0), GetMySuccessor ()) ; return GetMyID () ; I else

{ UNIT nexthop = GetNextHop(id); printf ("nexthop = #d/n",nexthop); return Remote_findPredecessor(nexthop, id); <BR> <BR> }<BR> <BR> <BR> <BR> <BR> } */ ============================================================ == ---------- void MyTable::SetFinger(int index, UINT id) { if ((index < LOGN) && (Finger[index] != id)) { Finger[index] = id; ResetStabilizTimer(); } } void MyTable::SetPredecessor(UINT id) { if (Predecessor != id) { Predecessor = id; ResetStabilizeTimer (); } } UINT MyTable::GetNextHop (UINT id) { if (id == MyID) return MyID; for (int i=LOGN - 1;i >= 0;i--) { if (Belongs (Finger[i], MyID, id, 0, 1, FALSE)) return Finger[i]; } // Error !!!! id is between MyID and MySucessor printf("Strange Error: Finger Table not good\n"); } UINT MyTable::GetClosestPrecedingFinger(INT id) { for (int i=LOGN - 1;i >= 0;i--) { if(Belongs(finger[i], MyID, id, 0, 0, TRUE)) return Finger[i]; } // Error !!!! // id is between MyID and MySuccessor printf ("Strange Error: Finger Table not good\n"); exit (-1); }

void MyTable :: UpdatePredecessor (UINT newpred) if ( (Predecessor == MyID) ||Belongs (newpred, Predecessor, MyID, 0,0, FALSE) ) { Predecessor = newpred; } } void MyTable::print (int4 curr_timer) { system ("clear"); printf ("&num &num &num &num &num &num &num &num &num &num &num &num &num &num &num &num &num &num &num &num &num My Finger Table ####################\n"); printf ("Current Stabilize TIMER is %. 2f ms\n", (float) curr_timer/1000. 0); printf ("Me = % d, Pred = % d\n", MyID, Predecessor); for (int i=0; i < LOGN;i++) { UINT start = GetIthStart (MyID, i); <BR> <BR> UINT end = (GetIthStart (MyID, i+1)-1 + MAXN) % MAXN;<BR> <BR> <BR> <BR> printf ("Finger % d: Range (% d, % d) = % d\n", i, start, end, Finger [i]) ; class MyTable class MyTable { private: UINT MyID ; //My Chord ID UINT Predecessor ;//My Predecessor node UINT Finger [LOGN] ;//Finger Table entries...

// Finger[i] stores the first existing node starting from MyID + pow (2, i) //Finger [0] == MySuccessor public: MyTable (UINT id, UINT helper_id) MyID = id; Predecessor = helper-id ; for (int i=0 ; i < LOGN; i++) <BR> <BR> Finger [i] = helperid ;<BR> <BR> <BR> <BR> } UINT GetSuccessor() { return Finger[0]; } UINT GetMyID() { return MyID; }

UINT GetFinger (int k) { if (k < LOGN) return Finger [k] ; return 0 ; } UINT GetPredecessor () { return Predecessor ; } void SetFinger (int index, UINT id) ; void SetPredecessor (UINT id) ; void UpdatePredecessor (UINT newpred) ; UINT GetNextHop (UINT id) ; UINT GetClosestPrecedingFinger (UINT id) ; void ReplaceFingerEntries (UINT prev, UINT replacement) { if (Predecessor == prev) Predecessor = replacement ; for (int i=O ; i < LOGN ; i++) if (Finger [i] == prev) Finger [i] = replacement ; } void print (int) ; } ; MyTable *mytable ;//My Global Finger Table Object ! TAG FILE FORMAT 2/extended format ;--format=1 will not append ;"to lines/ ! TAG FILE SORTED 1/0=unsorted, 1=sorted/ ! TAG PROGRAM AUTHOR Darren Hiebert /dhiebert@users. sourceforge. net/ ! TAG PROGRAM NAME Exuberant Ctags// ! TAG PROGRAM URL http ://ctags. sourceforge. net/official site/ !-TAG PROGRAM-VERSION 5. 2. 2// ASSERT main. h/'inline void ASSERT (BOOL f BOOL main. h 17 ;" d Belongs main. h/BOOL Belongs (UINT mid, UINT start, UINT end, int LeftInclusive, int RightInclusive, BOOL ShouldContain) $/ ;" f CURR STABILIZE TIMER main. h/int CURRSTABILIZETIMER = MIN TIMER ; $/ ;" v ChordHash main. h/^UINT ChordHash (struct in-addr ip, in_port_t port) $/ ;" f DEFAULT TARGET PORT main. h/const int DEFAULT TARGET PORT = 80 ; $/ ;" v Delete hash. cc/^void HashTable : : Delete (UINT id) $/ ;" f class : HashTable DeleteFromCache main. h/^void DeleteFromCache (UINT id) $/ ;" f

FALSE main. h 20 ;" d FREE main. h 390 ;" d FinalDst comm. h struct location FinalDst ; $/ ;" m struct : Query FindLowestFromHash main. h/"UINT FindLowestFromRash () $/;" f FindLowestNode hash. cc/UINT HashTable : : FindLowestNode () $/;" f class : HashTable FindNextHop main. h/void FindNextHop (char input [], char output []) $/ ;" f FindSuccessor main. cc/'void FindSuccessor (UINT start) $/ ;" f Finger table. h/ UINT Finger [LOGN] ; \/\/Finger Table entries... $/ ;" m class : MyTable FixFingers main. cc/Avoid FixFingers () $/ ;" f ForwardPacket comm. cc/^void ForwardPacket (struct Query *q_response) $/ ;" f ForwardPacket orig_comm. cc/^void ForwardPacket (struct Query *q_response) $/ ;" f From comm. h/A struct location From ; $/ ;" m struct : Query GetClosestPrecedingFinger main. h/"UINT GetClosestPrecedingFinger (UINT id) $/ ;" f GetClosestPrecedingFinger table. cc/"UINT MyTable : : GetClosestPrecedingFinger (UINT id) $/ ;" f class : MyTable GetFinger main. h/"UINT GetFinger (int k) $/ ;" f GetFinger table. h/A UINT GetFinger (int k) $/ ;" f class : MyTable GetFingerIndex main. h/int GetFingerIndex (UINT start) $/ ;" f GetIDFromIP hash. cc/"UINT HashTable : : GetIDFromIP (char inputIP []) $/ ;" f class : HashTable GetIDFromIP main. h/"UINT GetIDFromIP (char inputIP []) $/ ;" f GetIPFromID hash. cc/^void HashTable : : GetIPFromID (UINT id, char resultIP []) $/ ;" f class : HashTable GetIPFromID main. h/void GetIPFromID (UINT id, char result []) $/ ;" f GetIthStart main. h/UINT GetIthStart (UINT myID, int k) $/ ;" f GetIthStart main. h/^UINT GetIthStart (int k) $/ ;" f GetLocation hash. cc/Astruct location HashTable : : GetLocation (UINT id) $/ ;" f class : HashTable GetLocation main. h/^struct location GetLocation (UINT id) $/ ;" f GetMyID main. h/"UINT GetMyID () $/ ;" f GetMyID table. h/A UINT GetMyID () $/;"f class : MyTable GetMyLocation main. h/struct location GetMyLocation () $/;" f GetMyPredecessor main. h/"UINT GetMyPredecessor () $/ ;" f GetMySuccessor main. h/"UINT GetMySuccessor () $/ ;" f GetNewQueryID main. h/int GetNewQueryID () $/ ;" f GetNextHop main. h/"UINT GetNextHop (UINT id) $/ ;" f GetNextHop table. cc/UINT MyTable : : GetNextHop (UINT id) $/ ;" f class : MyTable GetPredecessor table. h/"UINT GetPredecessor () $/ ;" f class : MyTable GetSuccessor table. h/UINT GetSuccessor () $/;"f class : MyTable HandleQuery comm. cc/"void HandleQuery (struct Query *query) $/ ;" f

HandleQuery orig comm. cc/void HandleQuery (struct Query *query) $/ ;" f HandleResponse comm. cc/void HandleResponse (struct Query *qresponse) $/ ;" f HandleResponse orig_comm. cc/^void HandleResponse (struct Query *q_response) $/ ;" f Hash hash. h/^ struct mapping *Hash [MAXHASH] ; $/ ;" m class : HashTable HashTable hash. h HashTable () $/ ;" f class : HashTable HashTable hash. h/^class HashTable$/ ;" c InitSemaphores main. cc/void InitSemaphores () $/ ;" f InitSocket main. cc/void InitSocket () $/ ;" f Initialize main. cc/void Initialize (int myID, int helper_id) $/; t f JoinNetwork main. cc/void JoinNetwork (UINT helperid) $/ ;" f LOGN main. h/const int LOGN = 5 ; $/ ;" v LockFingerTable main. h/'void LockFingerTable () $/;"f LockHashTable main. h/^void LockHashTable () $/;"f MAXBUF main. h/const int MAXBUF = 512 ; $/ ;" v MAXHASH hash. h 15 ;" d MAXN main. h/const int MAXN = pow (2, LOGN) ; $/ ;" v MAXPOLLTIME main. h/const int MAX_POLL_TIME = 10 * MINPOLLTIME ; $/ ;" v MAXTIMER main. h/const int MAXTIMER = 4000000 ; $/ ;" v MIN POLL TIME main. h/const int MIN POLL TIME = 10000 ; $/ ;" v MIN TIMER main. h/const int MIN TIMER = 1000000 ; $/ ;" v MakeStandardQuery comm. cc/struct Query MakeStandardQuery (UINT to, UINT finaldst, int QueryType) $/ ;" f MakeStandardQuery orig_comm. cc/"struct Query MakeStandardQuery (UINT to, UINT finaldst, int QueryType) $/ ;" f MyID table. h/UINT MyID ; \/\/My Chord ID$/ ;" m class : MyTable MyTable table. h/MyTable (UINT id, UINT helper_id) $/ ;" f class : MyTable MyTable table. class MyTable$/ ;" c OrigSrc comm. h/^ struct location OrigSrc ; $/ ;" m struct : Query ParseAndAddLocation hash. cc/UINT HashTable : : ParseAndAddLocation (char *str) $/ ;" f class : HashTable ParseAndAddLocation main. h/UINT ParseAndAddLocation (char *ipStr) $/ ;" f Predecessor table. h/UINT Predecessor ; \/\/My Predecessor node$/ ;" m class : MyTable PrintFingerTable main. void PrintFingerTable (int currtimer) $/ ;" f Query comm. h/^struct Query$/;"s QueryData comm. h/^ struct location QueryData ; $/ ;" m struct : Query QueryID comm. h/^ UINT QueryID ; $/ ;" m struct : Query QueryType comm. h/A UINT QueryType ; $/ ;" m struct : Query QueryType AskPredecessor main. h 27 ;" d QueryType_FindSuccessor main. h 29 ;" d QueryType_Notify main. h 28 ;" d RTE MOD PORT comm. h 3 ;" d RecvThread comm. cc/^void *RecvThread (void *arg) $/ ;" f RecvThread orig_comm. cc/"void *RecvThread (void *arg) $/ ;" f Remote AskPredecessor comm. cc/UINT Remote AskPredecessor (UINT helper_id) $/ ;" f

Remote_AskPredecessor orig_comm.cc /^UINT RemoteAskPredecessor (UINT helper_id)$/;" f Remote_Notify comm.cc /^void Remote_Notify (UINT successor) $/ ;" f Remote_Notify orig_comm.cc /^void Remote_Notify (UINT successor) $/ ;" f ReplaceFingerEntries main. h/void ReplaceFingerEntries (UINT prev, UINT replacement) $/ ;" f ReplaceFingerEntries table. h void ReplaceFingerEntries (UINT prev, UINT replacement) $/ ;" f class: MyTable ResetStabilizeTimer main. h /^void ResetStabilizeTimer()$/;" f ResponseData comm. h/^ struct location ResponseData; $/ ;" m struct: Query ResponseMask main. h 26 ;" d SOSHelper comm. cc /^void *SOS_Helper (void *arg) $/ ;" f SOS_Helper orig_comm.cc /^void *SOS_Helper (void *arg) $/ ;" f SendQueryAndGetResponse comm. cc /^struct Query SendQueryAndGetResponse (struct Query query) $/ ;" f SendQueryAndGetResponse orig_comm.cc /^struct Query SendQueryAndGetResponse (struct Query query) $/ ;" f SendQueryData comm.cc /^void SendQueryData(struct Qury q)$/;" f SendQuryData orig_comm.cc /^void SendQueryData (struct Qury )$/;" f SetFinger main.h /^void SetFinger(int index, UINT id)$/;" f SetFinger table. cc /^void MyTable: : SetFinger (int index, UINT id) $/ ;" f class: MyTable SetNextSuccessor main. h/^BOOL SetNextSuccessor (UINT startid) $/ ;" f SetPredecessor main. h/^void SetPredecessor (UINT id) $/ ;" f SetPredecessor table. cc /^void MyTable: : SetPredecessor (UINT id) $/ ;" f class: MyTable Stabilize main. cc /^void Stabilize()$/;" f StabilizeSuccessor main. cc /^void StabilizeSuccessor()$/;" f Stabilize CheckForResponse main. h/BOOL Stabilize_CheckForResponse()$/;" f Stabilize GetResponse main. h/struct Query Stabilize_GetResponse()$/;" f Stabilize_Qid main. h /^int Stabilize Qid ; $/ ;" v Stabilize Response main. h/struct Query Stabilize Response ; $/ ;" v Stabilize SetupSleep main. h /^void St4abilize SetupSleep (int qid) $/ ;" f Stabilize_Status main. h/Aint Stabilize-Status ; $/ ;" v StabilizeWakeUp main. h/ABOOL StabilizeWakeUp (struct Query *q_response) $/ ;" f TRUE main. h 19 ;" d To comm. h /^ struct location To; $/ ;" m struct: Query UDS PATH main. h 82 ;" d UINT main. h 16 ;" d UINT ERROR main. h 22 ;" d UnLockFingerTable main. h/^void UnLockFingerTable()$/;" f UnLockHashTable main. h /^void unLockHashTable()$/;" f Update hash. cc /^void HashTable :: Update (UINT id, struct in-addr ip, in_port_t port) $/ ;" f class: HashTable Update hash. cc /^void HashTable: : Update (struct location loc) $/ ;" f class: HashTable

UpdateLocation main. h /^void UpdateLocation (struct location loc) $/ ;" f UpdatePredecessor main. h/Avoid UpdatePredecessor (UINT newpred) $/ ;" f UpdatePredecessor table. cc /^void MyTable: : UpdatePredecessor (UINT newpred) $/ ;" f class: MyTable WAITING main. h 391 ;" d ZOMBIE main. h 392 ;" d chord-socket main. h/^int chord-socket ; $/ ;" v hash hash. cc /^int HashTable: : hash (UINT id) $/ ;" f class: HashTable hash sem main. h /^sem_t hast_sem ; $/ ;" v hashtable hash. h /^HashTable *hashtable; $/ ;" v id comm. h /^ UINT id; $/ ;" m struct: location id hash. h /^ UINT id; $/ ;" m struct: mapping ip comm. h/^ struct in_addr ip;$/;" m struct: location location comm. h /^struct location$/;" s main main. cc /^Dmain (int argc, char *argv []) $/ ;" f mapping hash. h /^struct mapping$/; s mutex sem main. h /^sem_t mutex_sem ; \/\/Generally used for all kinds of mutual exclusion... $/ ;" v mytable table. h /^MyTable *mytable; \/\/My Global Finger Table Object$/;" v next hash. h/^ struct mapping *next; $/ ;" m struct: mapping port comm. h /^ in_port_t port ; $/ ;" m struct: location pow main. static int pow (int a, int b) $/ ;" f print table. cc /^void MyTable :: print (int currtimer) $/ ;" f class: MyTable recvthread main. h /^pthread_t recv_thread ; $/ ;" v sinaddr hash. h/^ struct inaddr sinaddr ; $/ ;" m struct: mapping sin_port hash. h /^ in_port_t sin_port ; $/ ;" m struct: mapping sos socket main. h /^int sos_socket ; $/;" v sosthread main. h /^pthread_t sos_thread ; $/ ;" v strTOip hash. cc /^struct in_addr HashTable: : strTOip (char *IPStr) $/ ;" f class: HashTable strTOport hash. cc /^in_port_t HashTable: : strTOport (char *PortStr) $/ ;" f class: HashTable table sem main. h/^sem_t table_sem ; $/ ;" v usage main. cc /^void usage (char *str) $/ ;" f

COMMUNICATION MODULE public class NextDestination { String hostname; int port; boolean direct; public NextDestination (String h, int p, boolean d) { hostname = h; port = p; direct = d; } } ================================================ There was no readme file with the code.

The following are from an email in January.

----------------------------------- Instructions for use of current version of WebSOS 1. Set browser proxy to point at localhost, port 10000.

2. Start JavaForward (port forwarder) by using command: java JavaForward (Right now the initial target is hard coded in ClientThread. java; it should probably be changed to allow that to be specified at command (Right now the initial target is hard coded in ClientThread. java; it should probably be changed to allow that to be specified at command line.) 3. Start up the Comm. module on each machine by using the command "./sosctl start". You can stop it by using"./sosctl stop".

You need a machine with the java security libraries. Also, you need certs that you can specify by setting"javax. net. ssl. XXXXX" properties. You should not need to anything beyond changing the call to the routing module.

&num !/usr/bin/perl # sosctl.pl - used to start and stop WebSOS &num $hostname ='hostname' ; chop ($hostname); $pid file pid"; # file name to save both pids &num start the processes if ($ARGV [0] eq"start") { if (-e $pid-file) file) die"sos. pid already exists-is WebSOS running ?" ; # start the processes (open is used because it is only way to get pid) # the classpath is set up to have sosProxy in the sosProxy directory $pid = open JF,"java-classpath $CLASSPATH :. : sosProxy/ sosProxy|"; print"$result\n" ; # record the pids in a file open (PIDFILE,">$pidfile") ; print PIDFILE"$pid\n" ; } # stop the processes elsif ($ARGV [0] eq"stop") { # does the pid file exist ? # get the pids from the file open (PIDFIZE, <$pid file') or die"$pidfile not found ; Is WebSOS running ?" ; @pids = <PIDFILE> ; $first_pid = $pids [0] ; chop ($first_pid) ; # $secondpid = $pids [1] ; # chop ($secondpid) ; # kill each pid} system ("kill $first_pid) ; ; # print"$second_pid\n"; # delete the pid file unlink"$pidfile" ; } else { print"Usage : sosctl startistop\n" ; } import java. io. * ; import java. net. * ; import java. util. * ; import java. security. * ; import javax. net. ssl. * ; import javax. net. * ; public class sosProxy { public static final boolean DEBUG = false ; static int port = 18080 ; SSLSocketFactory sslFact ; static int routingPort = 4567 ; Socket rModule ; BufferedReader br = null ; BufferedWriter bw = null ; public static void main (String [] args) {

if (args. length > 0) { port = Integer. parseInt (args [0]) ; I sosProxy sp = new sosProxy (port) ; sp. begin () ; } public sosProxy (int port) this. port = port ; } public void begin () { String KEYSTORE ="server. key" ; char [] KEYSTOREPW ="password". toCharArray () ; char [] KEYPW ="password". toCharArray () ; System. setProperty ("javax. net. ssl. trustStore","server. key") ; System. setProperty ("javax. net. ssl. trustStorePassword", "password") ; int threads = 10 ; boolean requireClientAuthentication = false ; /* start worker threads for efficiency */ try { /* for the children to connect out */ sslFact= (SSLSocketFactory) SSLSocketFactory. getDefault () ; /* create socket for the requests to the routing module */ rModule = new Socket ("localhost", routingPort) ; InputStream is = rModule. getInputStream () ; InputStreamReader isr = new InputStreamReader (is) ; br = new BufferedReader (isr) ; OutputStream os = rModule. getOutputStream () ; OutputStreamWriter osw = new OutputStreamWriter (os) ; bw = new BufferedWriter (osw) ; /* await connections to port */ KeyStore keystore = KeyStore. getInstance ("JKS") ; keystore. load (new FileInputStream (KEYSTORE), KEYSTOREPW) ; KeyManagerFactory kmf = KeyManagerFactory. getInstance ("SunX509") ; kmf. init (keystore, KEYPW) ; SSLContext sslc = SSLContext. getInstance (''SSLv3ll) ; sslc. init (kmf. getKeyManagers (), null, null) ; ServerSocketFactory ssf = sslc. getServerSocketFactory () SSLServerSocket ss = (SSLServerSocket) ssf. createServerSocket (port) ; ss. setNeedClientAuth (requireClientAuthentication) ; System. out. println ("Server live...") ; /* assign incoming connection to a worker */ while (true) { SSLSocket s = (SSLSocket) ss. accept () ;

System. out. println ("accepted connection") ; sosProxyWorker spw = new sosProxyWorker (s, this) ; spw. start () ; catch (Exception e) { e. printStackTrace () ; } public NextDestination testNextHop (String dest, int destPort) { String localstr try { InetAddress local = InetAddress. getLocalHost () ; localstr = local. getHostName () ; } catch (Exception e) { e. printStackTrace () ; System. out. println (localstr) ; if (localstr. equals ("tehran. clic. cs. columbia. edu")) { return new NextDestination (dest, destPort, true) ; } else if (localstr. equals ("cairo. clic. cs. columbia. edu")) { return new NextDestination ("tehran", 18080, false) ; } else if (localstr. equals ("bern. clic. cs. columbia. edu")) { return new NextDestination ("cairo", 18080, false) ; I else if (localstr. equals ("amman. clic. cs. columbia. edu")) { return new NextDestination ("bern", 18080, false) ; I else if (localstr. equals ("brasilia. clic. cs. columbia. edu")) { return new NextDestination ("amman", 18080, false) ; } else if (localstr. equals ("copenhagen. clic. cs. columbia. edu")) { return new NextDestination ("brasilia", 18080, false) ; } else if (localstr. equals ("baghdad. clic. cs. columbia. edu")) { return new NextDestination ("copenhagen", 18080, false) ; I else if (localstr. equals ("algiers. clic. cs. columbia. edu")) { return new NextDestination ("baghdad", 18080, false) ; else if (localstr. equals ("budapest. clic. cs. columbia. edu")) { return new NextDestination ("algiers", 18080, false) ; I else return new NextDestination ("budapest", 18080, false) ; } public NextDestination nextHop (String dest, int hops) { NextDestination ret = null ; try { /* convert dest into an ip address */ InetAddress destAddr = InetAddress. getByName (dest) ; String destIP = destAddr. getHostAddress () ; /* br and bw are from the socket to routing module *

/* note : need to revive the socket if it fails */ bw. write (destIP +","+ hops +"\n") ; bw. flush () ; String response = br. readLine () ; int dell = response. indexOf (',') ; int del2 = response. indexOf (',', dell+1) ; System. out. println (dell +""+del2) ; String nextAddr = response. substring (0, dell) ; int nextPort = Integer. parseInt (response. substring (dell+1, del2)) ; hops = Integer. parseInt (response. substring (del2+1, response. length ())) ; System. out. println ("nextAddr :"+ nextAddr) ; System. out. println ("nextPort :"+ nextPort) ; System. out. println ("hops :"+ hops) ; /* need to compare dest and actual destination */ boolean connectDirect = false ; if (nextAddr. equals (destIP)) { connectDirect = true ; I ret = new NextDestination (nextAddr, nextPort, connectDirect) ; } catch (Exception e) { e. printStackTrace () ; return ret ; } return ret ; import java. io. * ; import java. net. * ; import java. util. * ; import javax. net. ssl. * ; public class sosProxyWorker extends Thread { public static final boolean DEBUG = true ; sosProxy parent ; Socket s ; ArrayList requestStrs ; ArrayList requestStrs2 ; public sosProxyWorker () { s = null ; requestStrs = new ArrayList () ; requestStrs2 = new ArrayList () ; } public sosProxyWorker (SSLSocket s, sosProxy p) { this. s = s ; this. parent = p ; requestStrs = new ArrayList () ;

requestStrs2 = new ArrayList () ; I public synchronized void run () { handleClient () ; } public void handleClient () { try { System. out. println ("handling client") ; InputStream is = s. getInputStream () ; InputStreamReader isr = new InputStreamReader (is) ; BufferedReader br = new BufferedReader (isr) ; OutputStream os = s. getOutputStream () ; OutputStreamWriter osw = new OutputStreamWriter (os) ; BufferedWriter bw = new BufferedWriter (osw) ; /**** store the request headers in the ArrayList **/ String str ; while ( (str = br. readLine ()) ! = null) { if (str. equals (""))//by http spec break ; requestStrs. add (str) ; if (DEBUG) System. out. println (str) ; } /**** parse the connect request **/ str = (String) requestStrs. get (0) ; StringTokenizer st = new StringTokenizer (str, String method = st. nextToken () ; if ( ! (method. equals ("CONNECT"))) { invalidRequest (bw, 400) ; return ; } String destRaw = st. nextToken () ; String httpVersion = st. nextToken () ; StringTokenizer st2 new StringTokenizer (destRaw, String hostname = st2. nextToken () ; int port = 0 ; try { port = Integer. parseInt (st2. nextToken ()) ; } catch (Exception e) { invalidRequest (bw, 400) ; return ; } if (DEBUG) System. out. println (method +","+ hostname +","+ port + ""+ httpVersion) ; /* reply to connect */ bw. write ("HTTP/1. 1 200 Connection established\n") ; bw. write ("Proxy-agent sosProxy/0. 1") ; bw. newLine () ; bw. newLine () ; bw. flush () ; /* determine the next step */ //use method from sosProxyWorker

NextDestination next = parent. nextHop (hostname, 1) ; InputStream nis ; OutputStream nos ; /* We need to connect through a proxy */ if (! next. direct) { //open ssl socket to next proxy SSLSocket nextProxy = (SSLSocket) parent. sslFact. createSocket (next. hostname, next. port) ; InputStream npis = nextProxy. getInputStream () ; InputStreamReader npisr = new InputStreamReader (npis) ; BufferedReader npbr = new BufferedReader (npisr) ; OutputStream npos = nextProxy. getOutputStream () ; OutputStreamWriter nposw = new OutputStreamWriter (npos) ; BufferedWriter npbw = new BufferedWriter (nposw) ; //send connect request npbw. write ("CONNECT"+ hostname +" :" + port +""+ httpVersion +"\n") ; npbw. write ("User-Agent : sosProxy\n") ; npbw. write ("Host :"+ hostname) ; npbw. newLine () ; npbw. newLine () ; npbw. flush () ; //receive ok, continue with opening socket while ( (str = npbr. readLine ()) ! = null) { if (str. equals (""))//by http spec break ; requestStrs2. add (str) ; if (DEBUG) System. out. println (str) ; str = (String) requestStrs2. get (0) ; if (! str. equals ("HTTP/1. 1 200 Connection established")) { System. out. println ("error") ; invalidRequest (npbw, 0) ; }. nis = npis ; nos = npos ; } /* connect direct */ else { /* open simple socket to the destination port */ Socket dest = new Socket (hostname, port) ; if (true) { System. err. println ("Opened socket to" +hostname+" :"+port) ; } nos = dest. getOutputStream () ; nis = dest. getInputStream () ; } /* start flow */ StreamBridge clientToServerBridge =

new StreamBridge (is, nos,"client <--server") ; StreamBridge serverToClientBridge = new StreamBridge (nis, os,"client--> server") ; clientToServerBridge. join () ; serverToClientBridge. join () ; System. err. println ("Done with client') ; } catch (Exception e) { e. printStackTrace () ; } public void invalidRequest (BufferedWriter bw, int type) { try { bw. write ("HTTP/1. 1 400 Bad Request\n") ; bw. write ("Server : sosProxy/0. 1\n") ; bw. write ("Connection : close\n") ; bw. write ("Content-Type : text/html\n\n") ; bw. write ("< ! DOCTYPE HTML PUBLIC \"-//IETF//DTD HTML 2. 0//EN\">\n") ; bw. write ("<html><head><title>400 Bad Request</title></head>\n") ; bw. write ("<body><hl>400 Bad Request</hl>") ; bw. write ("<p>This proxy server only handles CONNECT (https) "+ "requests. </p></body></html>") ; bw. close () ; ) catch (Exception e) { e. printStackTrace () ; } /* /* * NetCallback-forwarding TCP ports behind a firewall * Copyright (C) 2001 Alexander V. Konstantinou <akonstan@acm. org> * * This program is free software ; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation ; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY ; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program ; if not, write to the Free Software

* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111- 1307 USA */ import java. net. * ; import java. io. * ; /** * Asynchronous bridging of traffic between an input and and output stream. * */ public class StreamBridge extends Thread { /** byte input stream */ protected final InputStream istream ; /** byte output stream */ protected final OutputStream ostream ; /** true if the bridge is active, false if it should terminate */ protected boolean active ; /** * Constructs a new asynchronous bridge by spawning a thread copying * traffic from the input stream to the output stream. * <p> * When the source of the input stream is a network socket, and in order to * detect the end of stream expiration in a timely manner, the socket * timeout must be set to a reasonable value (e. g. 1 second) * * @param istream-the input stream * @param ostream-the output stream * @param description-a string describing the connection (used to name the * thread) */ public StreamBridge (InputStream istream, OutputStream ostream, String description) super (description) ; if (istream == null) throw new NullPointerException ("null istream argument") ; if (ostream == null) throw new NullPointerException ("null ostream argument") ; this. istream = istream ; this. ostream = ostream ; active = true ; start () ; } /**

* Request asynchronous termination of the stream bridge */ public void terminate () { active = false; interrupt () ; /** * Thread copying bytes from the input stream and writing them to the * output stream until the end of file.

*/ public void run () { try { byte [] buffer = new byte [4096] ; int size = 0; while ( (active) && (size != -1) ) { if (size > 0) { ostream. write (buffer, 0, size) ; ostream.flush(); } try { size = istream. read (buffer); } catch (InterruptedIOException e) { size = e. bytesTransferred ; } catch (IOException e) //expected catch (Throwable e) { //unexpected e. printStackTrace (); finally try { ostream. close (); } catch (Throwable e) { e.printStackTrace (); try { istream. close (); } catch (Throwable e) {e. printStackTrace ();} } End of Netcallback ================== import java.io.*; import java. net. *; public class stringtest { public static void main (String [] args) { try { /* for the requests to the routing module */ Socket rModule = new SocketC'localhost", 5060);

InputStream is = rModule. getInputStream () ; InputStreamReader isr = new InputStreamReader (is) ; BufferedReader br = new BufferedReader (isr) ; OutputStream os = rModule. getOutputStream () ; OutputStreamWriter osw = new OutputStreamWriter (os) ; BufferedWriter bw = new BufferedWriter (osw) ; /* br and bw are from the socket to routing module */ /* note : need to revive the socket if it fails */ bw. write ("www. yahoo. com" +","+"5"+"\n") ; bw. flush () ; String response = br. readLine () ; int dell = response. indexOf (',') ; int del2 = response. indexOf (',', dell+1) ; System. out. println (dell +""+del2) ; String nextAddr = response. substring (0, dell) ; int nextPort = Integer. parseInt (response. substring (dell+1, del2)) ; int hops = Integer. parseInt (response. substring (del2+1, response. length ())) ; System. out. println ("nextAddr :"+ nextAddr) ; System. out. println ("nextPort :"+ nextPort) ; System. out. println ("hops :"+ hops) ; } catch (Exception e) { e. printStackTrace () ; } }

ROUTING MODULE Instructions for route module All java programs were tested using version 1.4 To test with the routing module: start the modules in the following order: CHORD (can use rtealg. java if CHORD is not available) route-module communications module (can use iftest_crm. java for this) ****************** If using the communications module, route module, and rte_alg. java (in place of CHORD) read the example at the end of this file for how to set up a hardcoded route using the initialization files ****************** rte_alg. java is a test program to substitute for CHORD if CHORD is not available. It reads in a file containing to and from addresses (in name format). Refer to the instructions in the top of the program for the file format.

The route module will send an IP address to it and receive an IP address back.

To compile: javac rtealg. java To run: java rte_alg [file] [port] [debug_level 0 or 1] example file: 1 lima@clic. cs. columbia. edu: peru@clic. cs. columbia ; (blank line at end) NOTE: rte alg converts all urls into lowercase before looking for a match in the initialization data so use all lowercase in the initialization file.

****************** iftest_crm. java is a test program to substitute for the communications module if the communications module is not available.

It just sends a target ip address to the route module and will receive and print the response from the route module. The target ip address is hard coded.

Edit the"String dest ="line near the beginning if you want to change this.

To compile: javac iftest_crm. java To run: java iftestcrm [port to use with route module (optional) ] The port defaults to 4567 if not provided ***************** route module. java is the routing module It uses Overlay Node. java and Hop_Info. java To compile: javac Hop Info. java Overlay Node. java route module. java To run: java route module [initialization file] [portl] [port2] [debug level] where portl = port to use with iftestcrm

port2 = port to use with CHORD (I hardcoded this as 3456 in the comm. h file for CHORD) debug level = 0 (print statements ignored) or 1 (prints what program is doing) the initialization file contains int = # of targets this node is an access point for int = # of targets this node is a servlet for int = 1 if beacon and ip address if servlet is listed below, 0 otherwise ip addresses of targets this node is an access point for ip addresses of targets this node is a servlet for ip address of servlet if this node is a beacon (this line is omitted if the above value is 0) blank line There are sample initialization files in the directory (files names with"init") Example file: 1 1 0 128.59. 16.49 128.59. 16.51 (blank line must be at the end) ****************** When using communications module, route-module and rte alg. java (in place of CHORD), a path through the overlay is"hardcoded"via the initialization files as follows: pick one node for each of the beacon and servlet. The target may be a node in the overlay or may be outside the overlay. let ap denote the access point node b denote the beacon s denote the servlet t denote the target let nl, n2, n3 denote 3 other overlay nodes not serving any of the above functions. (3 is used for example only, more or less may be used.) let the path be set as ap to nl to n2 to n3 to b to s to t on every node except the target set the initialization files for the route-module and rte_alg let init rm denote the initialization file for the route module let initra denote the initialization file for the rte_alg these will differ for each node. on ap: initrm must indicate the node is the access point for the target's ip and does not serve any other purpose initra must contain targeturl : nlurl ; on b: initrm must indicate the node is the beacon for the target's ip and does not serve any other purpose

init_ra may contain anything, rte_alg should not be called, to be safe include targeturl : servleturl ; on s: init_rm must indicate the node is the servlet for the target's ip and does not serve any other purpose init_ra may contain anything, rte_alg should not be called, to be safe include targeturl : targeturl ; on nx for x = 1,2 or 3: initrm should be set so nx serves no special purpose (is ap, b, s for 0 targets) init ra must contain nx url : nx+1_ur1 ; i. e. nl will have n1_ur1 : n2_ur1 ; ------------------------------------------------------------ -- /* class Hop_Info helper object stores information about hop : port and address of next node, number of hops, integer flag used to indicate how next hop was obtained */ import java. util. * ; public class Hop_Info String addr ;//IP address of next hop int port ;//port to use to contact next hop int num-hop ; number of hops so far in path int result ;//indicates function of current node (beacon, servlet etc) //constructor Hop_Info (String a, int p, int h, int r) { addr = a ; port = p ; num hop = h ; result = r ; } //accessors public String get_addr () {return addr ;} public int get_port () {return port ;} public int get_num_hop () {return num_hop ;} public int get_result () {return result ;} //update all parameters public void set_params (String a, int p, int h, int r) { addr = a ; port = p ; nus-hop h ; result = r ; )

( /end of Hop-Info import java. io. * ; import java. net. * ; import java. util. * ; public class iftest_crm { public static void main (String [] args) { int port = 4567 ; Socket rModule ; BufferedReader br = null ; BufferedWriter bw = null ; //String dest ="135. 14. 160. 51" ; //String dest ="150. 135. 65. 2" ; String dest ="128. 2. 198. 188" ; int hops = 2 ; if (args. length > 0) { port = Integer. parseInt (args [0]) ; } try { rModule = new Socket ("localhost", port) ; InputStream is = rModule. getInputStream () ; InputStreamReader isr = new InputStreamReader (is) ; br = new BufferedReader (isr) ; OutputStream os = rModule. getOutputStream () ; OutputStreamWriter osw = new OutputStreamWriter (os) ; bw = new BufferedWriter (osw) ; for (int i=0 ; i<10 ; i++) { bw. write (dest +","+ hops +"\n") ; bw. flush () ; String response = br. readLine () ; System. out. println (response) ; int dell = response. indexOf (',') ; int del2 = response. indexOf (',', dell+1) ; System. out. println (dell +""+del2) ; String nextAddr = response. substring (0, dell) ; int nextPort = Integer. parseInt (response. substring (dell+1, del2)) ; hops = Integer. parseInt (response. substring (del2+1, response. length ())) ; System. out. println ("nextAddr :"+ nextAddr) ; System. out. println ("nextPort :"+ nextPort) ; System. out. println ("hops :"+ hops) ; Thread. sleep (5000) ; System. out. println ("Woke up.") ; } bw. close () ; osw. close () ; os. close () ; br. close () ; isr. close () ; is. close () ; rModule. close () ; )

catch (Exception e) { e. printStackTrace () ; }//end of main }//end of class /* Overlay Node object containing data for a node node's IP address servlet's address if node is a beacon list of targets for which node is an access point list of targets for which node is a servlet */ import java. util. * ; public class Overlay Node { static int def sz = 10 ; String my_address ; String servlet ;//if node is a beacon, servlet's IP address Vector access_pt_for ;//targets for which node is an access point Vector servlet for ;//targets for which node is a servlet //constructor Overlay Node (String my_addr) my_address = my_addr ; servlet access_pt_for = new Vector (defsz) ; servlet for = new Vector (defsz) ; } //update servlet public void set servlet (String s) {servlet = s ;} //add target to list of nodes for which node is an access point public void add target ap-list (String target) { access_pt_for. addElement (target) ; } //add target to list of nodes for which node is a servlet public void addtargetservletlist (String target) servlet-for. addElement (target) ; } //remove a target to the list of node for which node is an access point public boolean remove_target_ap_list (String target) { boolean flag = access_pt_for. removeElement (target) ; return flag ; } //remove a target to the list of node for which node is a servlet public boolean removetarget servletlist (String target) { boolean flag = servlet-for. removeElement (target) ; return flag ;

} // get node's IP address public String get my address () {return my_address:} //return true if node is access point for target; false otherwise public boolean isaccesspoint (String target) { boolean flag = false; //determine if target is an element of access_pt_for flag = access_pt_for. contains (target); return flag; //return true if node is servlet for target; false otherwise public boolean in servlet (String target) { boolean flag = false; //determine if target is an element of servlet_for flag = servlet_for. contains (target); return flag; } public String getservletaddr (String beacon) {return servlet ;} }//end of class overlay node //usage : //java route-module [init file] [port # for comm module] // [port &num for basic routing algorithm module i. e. CHORD] [debug flag 0 or 1] //all arguments are required /* Routing Module for SOS Debbie Cook Columbia Univeristy 1/3 */ //need to create a log file, and define sos_port as static variable //error handling needed: currently will print exception and stop import java. io. *; import java. util. *; import java. net. *; public class route-module private static Hop_Info get next hop (Overlay Node node, String target, int overlay_hop_cnt, Hop_Info hop_info, BufferedReader br, BufferedWriter bw, int debug) { try { int sos_port = 18080; int result =-1; String next addr ; int nextport = 0; String response; //if current node is access point, set hop count to 0 regardless of what value was //passed from the communications module

if (node. is access_point (target)) { if (debug > 0) {System. out. println ("Node is access point.") ;} overlay_hop_cnt = 0 ; } //if current node is servlet, next hop is target if (node. in servlet (target)) { if (debug > 0) {System. out. println ("Node is servlet for target. t) ;} next addr = target ; next_port = sos_port ; ++overlayhopcnt ; result = 3 ; } //if current node is the target, done else if (target. equals (node. get my address ())) { if (debug > 0) {System. out. println ("Node is target.") ;} next addr = target ; result = 4 ; } //else use the basic overlay routing algorithm //send target's address else { if (debug > 0) {System. out. println ("Calling basic routing algorithm.") ;} String tar = target. concat ("\n") ; System. out. print (tar) ; bw. write (tar) ; bw. flush () ; //read response if (debug > 0) {System. out. println ("Waiting for response.") ;} next addr = br. readLine () ; //if received own ip address, current node is beacon, next hop is servlet if (next-addr. equals (node. get_my_address ())) { next addr = node. get servlet addr (next addr) ; next_port = sos_port ; ++overlay_hop_cnt ; result = 2 ; } //else next node is an intermediate node in the overlay else { next_port = sos_port ; ++overlay_hop_cnt ; result = 1 ; } }//end of else call to basic routing algorithm //return next address, port hop count and result if (debug > 0) { System. out. println ("Returning :"+ next_addr +""+ next_port +""+ overlay_hop_cnt +""+ result) ;

hop_info. set_params (next_addr, next_port, overlayhopcnt, result) ; } catch (Exception e) {System. out. println (e) ;} return (hop_info) ; }//end of get next hop public static void main (String args []) { try { int loop = 0; //String host_ip = (InetAddress. getLocalHost ()). toString () ; InetAddress lh = InetAddress. getLocalHost() ; String host_ip = lh. getHostAddress() ; String host = "localhost"; int comport ; //port to use for communications module int rte_alg_port ; //port to use for basic routing algorithm module int debug = 0 ; //debug level String init file ; //initialization file String log-1 = "route_mod_log.txt"; // log file String request ="xxx";//holds request from communications module String reply ;//reply to communications module String target ;//ip address of target String tmpstr ;//temp storage int hop_cnt = 0 ;//&num of hops Hop_Info hop_info = new Hop_Info("0", 0,0, 0); int res = 0; Overlay Node node = new Overlay Node (host ip) ; if (args. length < 3)) args. length > 4) { System. out. println ("Invalid number of arguments.") ; System.exit(1); } init_file = args[0]; comm_port = Integer. valueOf (args [1]). intValue () ; rte_alg_port = Integer. value0f (args [2]). intValue () ; if (args. length == 4) {debug = Integer. valueOf (args [3]). intValue () ;} if (debug > 0) {System. out. println ("Node's ip address :"+ host_ip) ;} //read in initialization data if (debug > 0) {System. out. println ("Reading in initialization data.") ;} FileReader fr = new FileReader (args [0]) ; BufferedReader init br = new BufferedReader (fr); int szl = Integer. parseInt(init_br.readLine()) ; int sz2 = Integer. parseInt(init_br.readLine()) ; int sz3 = Integer. parseInt (initbr. readLine ()) ; if (szl < 0 # sz2 < 0 11 sz3 < 0) System. out. println ("Error within first 3 lines of initialization file.") ; System.exit(1); }

//targets for which node is access point for (int i = 0; i < szl ; ++i) { node. add_target_ap_list(init_br.readLine()) ; } //targets for which node is a servlet for (int i = 0; i < sz2; ++i) { node. add_target_servlet_list(init_br.readLine()) ; } //if node is beacon, servlet (this should not be init data in long term) if (sz3 > 0) {node. set_servlet (initbr. readLine ()) ;} //close init file init br. close () ; fr. close () ; if (debug > 0) {System. out. println ("Done reading in initialization data.") ;} //open socket to communications module if (debug > 0) {System. out. println ("Opening socket to communications module. T) ;} ServerSocket ss = new ServerSocket (comm_port) ; Socket comm sock = ss. accept () ; InputStream is = commsock. getInputStream () ; InputStreamReader isr = new InputStreamReader (is); BufferedReader comm br = new BufferedReader (isr); OutputStream os = commsock. getOutputStream () ; OutputStreamWriter osw = new OutputStreamWriter (os); BufferedWriter comm bw = new BufferedWriter (osw) ; //open socket to basic routing algorithm module if (debug > 0) {System. out. println ("Opening socket to basic routing algorithm module.") ;} Socket ralg_sock = new Socket ("localhost", rte_alg_port) ; InputStream is2 = ralg-sock. getInputStream () ; InputStreamReader isr2 = new InputStreamReader (is2); BufferedReader ralg_br = new BufferedReader (isr2); OutputStream os2 = ralg_sock. getOutputStream () ; OutputStreamWriter osw2 = new OutputStreamWriter (os2); BufferedWriter ralg_bw = new BufferedWriter (osw2); //loop forever, reading in requests from communications module //the communication module blocks until a response is received so threads //were not used here while (true) { //clear storage request ="0"; hop_info. set_params ("0", 0,0, 0); //receive request in format target, hop count try { request = commbr. readLine () ; } catch (Exception e) {request ="xxx";} if (debug > 3) {System. out. println ("Request"+ request) ;} try {

request. length () ; } catch (Exception el) {request ="xxx";} if (request. length () < 7) {}//do nothing else {//***** //parse buffer into target's ip address and hop count int tmp_ind = request. indexOf (",") ; target = request. substring (0, tmp_ind) ; hop_cnt = Integer. parseInt (request. substring (tmp_ind+1)) ; if (debug > 0) {System. out. println ("target and hop count" + target +""+ hop_cnt) ;} //determine next address hop info = getnexthop (node, target, hopcnt, hopinfo, ralgbr, ralgbw, debug) ; res = hop_info. get_result () ; if (debug > 0) {System. out. println ("result from determining next hop :"+ res) ;} if (res < 1 I res > 4) { System. out. println ("Error when determining the next hop.") ; if (debug > 0) { if (res == 1) {System. out. println ("Stat : normal overlay routing.") |X) ;} else if (res == 2) {System. out. println ("Stat : current node was beacon.") ;} else if (res == 3) {System. out. println ("Stat : current node was servlet.") ;} else if (res == 4) {System. out. println ("Stat : current node was target.") ;} } //return next address, port and hop count to communications module Integer tmp_port = new Integer (hop_info. get_port ()) ; Integer tmphcnt = new Integer (hopinfo. getnumhop ()) ; tmpstr = (hop_info. get addr ()). concat (","). concat (tmp_port. toString ()) ; reply = tmpstr. concat (","). concat (tmphcnt. toString ()). concat ("\n") ; if (debug > 0) {System. out. println ("Reply to communications module :"+ reply) ;} comm bw. write (reply) ; commbw. flush () ; }//end of else ***** }//end of while //close datastreams and sockets /* comm br. close () ; comm bw. close () ; isr. close () ; is. close () ; osw. close () ; os. close () ; comm sock. close () ; ss. close () ; ralg_br. close () ; ralg_bw. close () ;

isr2. close () ; is2. close () ; osw2. close () ; os2. close () ; ralg_sock. close () ; */ } catch (Exception e) {System. out. println (e) ;} }//end of main }//end of class route-module /* for testing in place of CHORD: receives ip address from route module and returns ip address of next hop reads in initialization file that lists pairs of possible names corresponding to IP addresses thhat could be received from the route module and what name is the next hop file format: int sz= # of entries in file name: nexthopname ; (sz such entries, be in lower case) blank line example: 1 lima. clic. cs. columbia. edu: peru. cs. columbia. edu; */ import java. io. *; import java. net. *; import java. util. *; public class rte_alg public static int def-sz = 20; public static String sep =" :" ; public static void main (String [] args) { int port = 3456; ServerSocket ss; Socket rModule ; BufferedReader br = null; BufferedWriter bw = null; Vector query addr = new Vector (defsz) ; Vector return addr = new Vector (defsz) ; int debug = 0; int sz = 0 ; int ind = 0 ; String tmp_line ; String eol =" ;" ; String resp_name ; String resp_name_tmp ; String resp_ip ; String request="xxx" ; String request name ; InetAddress resp_inet_addr ; InetAddress request_inet_addr ;

//default : return node's own ip address if error occurs try { InetAddress lh = InetAddress. getLocalHost () ; String defaultrespip = lh. getHostAddress () ; //check number of command line arguments if (args. length ! = 3) { System. out. println ("Usage : file port debug.") ; System. out. println ("debug = 0 or 1.") ; System. exit (1) ; debug = Integer. parseInt (args [2]) ; port = Integer. parseIntlargs [1]) ; //read in initialization data in form //number of entries in file (sz) //list of sz entries in format query address : return address if (debug > 0) {System. out. println ("Reading in initialization data.") ;} FileReader fr = new FileReader (args [0]) ; BufferedReader init br = new BufferedReader (fr) ; sz = Integer. parseInthinit_br. readLine ()) ; for (int i = 0 ; i < sz ; ++i) { tmp-line = initbr. readLine () ; ind = tmp_line. indexOf (sep) ; query_addr. addElement (tmp_line. substring (0, ind)) ; return addr. addElement (tmp_line. substring (ind+l, tmpline. length ())) ; I //close init file init br. close () ; fr. close () ; //open socket to route module if (debug > 0) {System. out. println ("Creating socket to route module.") ;} ss = new ServerSocket (port) ; rModule = ss. accept () ; if (debug > 0) {System. out. println ("Creating data streams.") ;} InputStream is = rModule. getInputStream (); InputStreamReader isr = new InputStreamReader (is) ; br = new BufferedReader (isr) ; OutputStream os = rModule. getOutputStream () ; OutputStreamWriter osw = new OutputStreamWriter (os) ; bw = new BufferedWriter (osw) ; int cnt = 0 ; int ind2 = 0 ; ind = 0 ; while (true) //receive request from route module try { request = br. readLine () ; } catch (Exception e) {request ="xxx";} try { request. length () ; } catch (Exception el) {request ="xxx" ;} if (request. length () < 7) {}

else {//****** request_inet_addr = InetAddress. getByName (request) ; request name = (request_inet_addr. getHostName ()). toLowerCase () ; if (debug > 0) {System. out. println ("request"+ request +" "+ request name) ;} //find index of request in vector of query addresses ind = queryaddr. index0f (requestname) ; if (ind < 0) { System. out. println ("Invalid query address : no known destination.") ; System. out. println ("Returning default address of self.") ; resp_ip = defaultrespip ; else { //next hop is address at index ind in Vector of return addresses resp_name_tmp = (String) return-addr. elementAt (ind) ; //extra space is returned at end of string ind2 = resp name_tmp. indexOf (eol) ; resp_name = respnametmp. substring (0, ind2) ; respinetaddr = InetAddress. getByName (resp_name) ; resp_ip = resp_inet_addr. getHostAddress () ; if (debug >0) { System. out. println ("Response name and address :"+ respname +""+ respip) ; //send ip address to route module bw. write (resp_ip +"\n") ; bw. flush () ; ++cnt ; }//end of else ***** end of while } catch (Exception e) { e. printStackTrace () ; I }//end of main }//end of class