TEXAS STATE UNIVERSITY

Assignment 1
Distributed Computing
Harshit Pandey 6/19/2010

ID- 589246

1. (15 pts) (1) Describe two issues that are common to both distributed systems and computer networks. (2) Describe two issues that exist only in distributed system.

SOLUTION: ANSWER 1 As the definition says, the distributed computing comprise of multiple autonomous computers that communicate through networks. These computers communicate with each other to achieve the common goal. Hence distributed computing and computer networks most of the common problems altogether. 1. Some of the issues that are common to both distributed computing and computer networks are enlisted below (a) Interdependency and loosely coupled system. Loosely coupled systems (system with least interdepency among components) ensure efficient and healthy system state. The low interdepency among components mitigates the risk of complete system failure. In general, the bigger the network or DS, the higher the resources required to manage and hence increased complexity. Furthermore, in a tightly- coupled system, one component failure could significantly affect the working of the other part of system or end up with complete failure of system. (b) Security Issues: Security is the prime issue in both the Distributed Computing (DS) and computer networks. Considering the situation that require transfer of confidential information (example: Financial Information, Personal Information, Official Information) needs a suitable system that ensure safe and secured data movement across the system. Failing to provide required security anticipate crucial loss of information among the system. Integrity of the information which covers information alteration or un-authorized access is the major possible flaw. (c) Increased cost with the scalable system: The cost of setting up large network of distributed system requires more consumption of resources and hence significant increase setup cost and maintenance. Large network requires move investment of time and money for wear-tear and maintenance of the system and expensive the process gets into. Scalable system requires effective processing state even on significant increment of resources involved. 2. The issues that are specific to Distributed Computing are discussed here: (a) Interference & lack of concurrency: In the case of the distributed computing the individual components should be well under stood and the combinational behavior requires proper coordination. The interface of one component interfering onto the task assigned to other component could result into halting of the system. Similarly, the data transmission in the large

network required well-coordinated structure. Increased network size brings more complexity in data communication and message exchange. Each thread and process has to have an access clock to synchronize the procedural working of system. (b) Intercommunication: The intercommunication among the distributed components plays prime importance to maintain healthy and effective state of the system. The intercommunication require rigorously worked algorithm which ensure the loosely coupled system each working individually and helping corresponding bit for problem resolution. Bottlenecks, thread locking, halting, catch22 are often seen in resolving a common problem while using distributed system.

(c) Expensive Processing: Due the large level engagement of systems, the more processers are involved to resolve a problem. Increased involvement of resources forestalls complexity and brings increased maintenance cost. (d) Data Redundancy: Since the satellite processors work remotely, so each process (proxies) possibly own its personalized cached copy of shared data. The multiple cached copies can result in clustering of dataset and un-organized data replication problem.

Question 2: (15 pts.) For the transaction shown in Figure 1 please write a program that uses fork and join constructs to implement the transaction.

ANSWER 2 :
cnt6:= cnt6-1; if cnt6 !=0 then quit; cnt7:=cnt7-1; if cnt7 !=0 then quit; cnt6:=2; cnt7:=2; S1; FORK (L1); S2; S4; FORK (L6); GOTO L5; L1:S3; L6: JOIN (cnt6); S6; GOTO L7; L5: S5; L7: JOIN (cnt7); S7;

3. (15 pts. Problem 3.2, p.128) The Internet is far too large for any router to hold routing information for all destinations. How does the Internet routing scheme deal with this issue?
ANSWER: 3 To answer this question let us discuss in brief detail about how routing is made through Router. WHAT IS ROUTING? Routing is the act of moving information across an internetwork from a source to a destination. Along the way, at least one intermediate node typically is encountered. Routing is often contrasted with bridging, which might seem to accomplish precisely the same thing to the casual observer. The primary difference between the two is that bridging occurs at Layer 2 (the link layer) of the OSI reference model, whereas routing occurs at Layer 3 (the network layer). This distinction provides routing and bridging with different information to use in the process of moving information from source to destination, so the two functions accomplish their tasks in different ways. ROUTING COMPONENTS Routing involves two basic activities: determining optimal routing paths and transporting information groups (typically called packets) through an internetwork. In the context of the routing process, the latter of these is referred to as switching. Although switching is relatively straightforward, path determination can be very complex. PATH DETERMINATION A metric is a standard of measurement, such as path length, that is used by routing algorithms to determine the optimal path to a destination. To aid the process of path determination, routing algorithms initialize and maintain routing tables, which contain route information. Route information varies depending on the routing algorithm used.

ROUTING ALGORITHMS Routing algorithms ll routing tables with a variety of information. Destination/next hop associations tell a router that a particular destination can be gained optimally by sending the packet to a particular router representing the next hop on the way to the nal destination. When a router receives an incoming packet, it checks the destination address and attempts to associate this address with a next hop. Figure 1 depicts a sample destination/next hop routing table.

FIGURE 1: DESTINATION/NEXT HOP ASSOCIATIONS DETERMINE THE DATA S OPTIMAL PATH .

Routing tables also can contain other information, such as data about the desirability of a path. Routers compare metrics to determine optimal routes, and these metrics differ depending on the design of the routing algorithm used. A variety of common metrics will be introduced and described later in this chapter. Routers communicate with one another and maintain their routing tables through the transmission of a variety of messages. The routing update message is one such message that generally consists of all or a portion of a routing table. By analyzing routing updates from all other routers, a router can build a detailed picture of network topology. A link-state advertisement, another example of a message sent between routers, informs other routers of the state of the senders links. Link information also can be used to build a complete picture of topology to enable routers to determine optimal routes to network destinations. SWITCHING Switching algorithms are relatively simple and are basically the same for most routing protocols. In most cases, a host determines that it must send a packet to another host. Having acquired a routers address by some means, the source host sends a packet addressed specically to a routers physical (Media Access Control [MAC]-layer) address, this time with the protocol (network layer) address of the destination host. As it examines the packets destination protocol address, the router determines that it either knows or does not know how to forward the packet to the next hop. If the router does not know how to forward the packet, it typically drops the packet. If the router knows how to forward the packet, it changes the destination physical address to that of the next hop and transmits the packet. The next hop may, in fact, be the ultimate destination host. If not, the next hop is usually another router, which

executes the same switching decision process. As the packet moves through the internetwork, its physical address changes, but its protocol address remains constant, as illustrated in Figure 2.

ROUTING ALGORITHMS Routing algorithms can be differentiated based on several key characteristics. First, the particular goals of the algorithm designer affect the operation of the resulting routing protocol. Second, various types of routing algorithms exist, and each algorithm has a different impact on network and router resources. Finally, routing algorithms use a variety of metrics that affect calculation of optimal routes. The following sections analyze these routing algorithm attributes.

DESIGN GOALS Routing algorithms often have one or more of the following design goals: Optimality Simplicity and low overhead Robustness and stability Rapid convergence Flexibility Optimality refers to the capability of the routing algorithm to select the best route, which depends on the metrics and metric weightings used to make the calculation. For example, one routing algorithm may use a number of hops and delays, but it may weigh delay more heavily in the calculation. Naturally, routing protocols must define their metric calculation algorithms strictly. Routing algorithms also are designed to be as simple as possible. In other words, the routing algorithm must offer its functionality efficiently, with a minimum of software and utilization overhead. Efficiency is particularly important when the software implementing the routing algorithm must run on a computer with limited physical resources. Routing algorithms must be robust, which means that they should perform correctly in the face of unusual or unforeseen circumstances, such as hardware failures, high load conditions, and incorrect implementations. Because routers are located at network junction points, they can cause considerable problems when they fail. The best routing algorithms are often those that have withstood the test of time and that have proven stable under a variety of network conditions.

In the routing loop displayed in Figure 3, a packet arrives at Router 1 at time t1. Router 1 already has been updated and thus knows that the optimal route to the destination calls for Router 2 to be the next stop. Router 1 therefore forwards the packet to Router 2, but because this router has not yet been updated, it believes that the optimal next hop is Router 1. Router 2 therefore forwards the packet back to Router 1, and the packet continues to bounce back and forth between the two routers until Router 2 receives its routing update or until the packet has been switched the maximum number of times allowed.

FIGURE 3 SLOW CONVERGENCES AND ROUTING LOOPS CAN HINDER PROGRESS Routing algorithms should also be flexible, which means that they should quickly and accurately adapt to a variety of network circumstances. Assume, for example, that a network segment has gone down. As many routing algorithms become aware of the problem, they will quickly select the next-best path for all routes normally using that segment. Routing algorithms can be programmed to adapt to changes in network bandwidth, router queue size, and network delay, among other variables. ALGORITHM TYPES Routing algorithms can be classified by type. Key differentiators include these: Static versus dynamic Single-path versus multipath Flat versus hierarchical Host-intelligent versus router-intelligent Intradomain versus interdomain Link-state versus distance vector

ROUTING METRICS Routing tables contain information used by switching software to select the best route. Routing algorithms have used many different metrics to determine the best route. All the following metrics have been used: Path length

 Reliability Delay Bandwidth Load Communication cost I find that all these are the important factors taken in consideration while making routing decision that help intelligently and efficiently routing which worry about all the information of destination addresses.

4. (10 + 20 = 30 pts) (1) What is the most important factor that acts the accuracy of Christians Algorithm? Explain your answer. (2) provide two examples that show how Christians algorithm works.

(3) Will Christians algorithm work in asynchronous distributed environment? Please briefly justify your answer

ANSWER: 4 (A) CHRISTIAN ALGORITHM: It is used to synchronize the local clock with an external authoritative time source (server). The accuracy of the synchronization depends on the message transmission delay and how it is handled. If the transmission delay is large, it is hard to have an accurate synchronization. Thus it is more suitable to be used in LAN

F ACTORS

AFFECTING ACC URACY :

1. Suppose in a message passed by server at particular time t then to ensure

2. The total round trip time (Tround as declared above) which stands for time
required for request to response, if the request and response is made on same server which mean to same LAN, the higher accuracy can be achieved else if heterogeneous or remote networks comes into th e scene the higher imprecision could be anticipated.

(B) E XAMPLES OF W ORKING

OF

C HRISTIAN A LGORITHM

I.

Christians algorithm is well suited to systems in which one machine (time server) has a WWV receiver and other machines stay synchronized with it. For every /2p seconds, clients send request to time servers asking for current time and when the servers respond, the clients adjust their timings.

II.

As an example given the class, in general the make command used by UNIX systems uses the clock to determine the source which is supposed to be compiled. In case, if the source file is not on the same LAN or server, the make program may produce in correct results.

III.

Christians Algorithm is a method for clock synchronization which can be used in many fields of distributive computer science but is primarily used in low-latency intranets. Cristian observed that this simple algorithm is probabilistic, in that it only achieves synchronization if the roundtrip time (RTT) of the request is short compared to required accuracy. It also suffers in implementations using a single server, making it unsuitable for many distributive applications where redundancy may be crucial.

5. (25 pts. Problem 11.4, p.465) A client attempts to synchronize with a time server. It records the round-trip times and timestamps returned by the server in the table below. Which of these items should it use to set its clock? To what time should it set it? Estimate the accuracy of the setting with respect to the server's clock. If it is known that the time between sending and receiving a message in the system concerned is at least 8 ms, do your an swers change? Round-trip (ms) Time (hr:min:sec) ___________________________ 22 10:54:23.674 25 10:54:25.450 20 10:54:28.342

ANSWER: 5 (a) Clearly according to question given in the table Since the systems are remotely connected then as discussed in the previous question we consider the round trip time as one of the primary issue for the measuring the accuracy of the clock. Now according the table, first column indicated the round trip time while the other time is the time stamp. Furthermore, The least round is taken into the consideration for measuring the accuracy.

When P receives the message, it should set its time to t+Ttrans, where Ttrans is the time to transmit the message. Ttrans Tround /2, where Tround is the round-trip time ACCURACY Let min be the minimum time to transmit a message one-way. Then P could receive Ss message any time between [t+min, t+ Tround - min]

So accuracy is (Tround /2 - min)

Now considering the third attempt, we notice that the round-trip time is reduced to minimum that is (20 secs) which make it obvious to be taken into consideration. Also according the formula We have, Accuracy factor as: (Tround /2 - min) Therefore, the accuracy of the setting is: +/- (20/2-min) = +/- (10-min)

(b). Looking at the answer 4, we discussed that the time at which server enter the value in message play one of the primary role in effecting the delay and here in the question as given that if it is known that the time between sending and receiving a message in the system concerned is at least 8 ms. Then it is clear and obvious that my answer will change.