Đang chuẩn bị liên kết để tải về tài liệu:
DESIGN AND ANALYSIS OF DISTRIBUTED ALGORITHMS phần 5

bao gồm cả đường kính của cây và số lượng các hạng mục ban đầu, một thực thể ban đầu (Tập thể dục 4.6.2). 4.2.2 Lặp đi lặp lại xây dựng các bảng định tuyến giải pháp chúng tôi đã thấy được yêu cầu mỗi thực thể có sẵn tại địa phương lưu trữ, đủ để lưu trữ toàn bộ bản đồ của mạng | 228 MESSAGE ROUTING AND SHORTEST PATHS This means that in sparse networks all the routing tables can be constructed with at most O n2 normal messages. Such is the case of meshes tori butterflies and so forth. In systems that allow very long messages not surprisingly the gossip problem and thus the routing table construction problem can be solved with substantially fewer messages Exercises 4.6.3 and 4.6.4 . The time costs of gossiping on a tree depend on many factors including the diameter of the tree and the number of initial items an entity initially has Exercise 4.6.2 . 4.2.2 Iterative Construction of Routing Tables The solution we have just seen requires that each entity has locally available enough storage to store the entire map of the network. If this is not the case the problem of constructing the routing tables is more difficult to resolve. Several traditional sequential methods are based on an iterative approach. Initially each entity x knows only its neighboring information for each neighbor y the entity knows the cost 0 x y of reaching it using the direct link x y . On the basis of this initial information x can construct an approximation of its routing table. This imperfect table is usually called distance vector and in it the cost for those destinations x knows nothing about will be set to TO. For example the initial distance vector for node s in the network of Figure 4.1 is shown in Table 4.2. This approximation of the routing table will be refined and eventually corrected through a sequence of iterations. In each iteration every entity communicates its current distance vector with all its neighbors. On the basis of the received information each entity updates its current information replacing paths in its own routing table if the neighbors have found better routes. How can an entity x determine if a route is better The answer is very simple when in an iteration x is told by a neighbor y that there exists a path n2 from y to z with cost g2 x checks in