云物流实例资料
Routing Principles
In order to transfer packets from a sending host to the destination host, the network layer must determine the path or route that the packets are to follow. Whether the network layer provides a datagram service (in which case different packets between a given host-destination pair may take different routes) or a virtual circuit service (in which case all packets between a given source and destination will take the same path), the network layer must nonetheless determine the path for a packet. This is the job of the network layer routing protocol.
At the heart of any routing protocol is the algorithm (the "routing algorithm") that determines the path for a packet. The purpose of a routing algorithm is simple: given a set of routers, with links connecting the routers, a routing algorithm finds a "good" path from source to destination. Typically, a "good" path is one which has "least cost," but we will see that in practice, "real-world" concerns such as policy issues (e.g., a rule such as "router X, belonging to organization Y should not forward any packets originating from the network owned by organization Z") also come into play to complicate the conceptually simple and elegant algorithms whose theory underlies the practice of routing in today's networks.
Figure 4.2-1: Abstract model of a network
The graph abstraction used to formulate routing algorithms is shown in Figure 4.2-1. (To view some graphs representing real network maps, see [Dodge 1999] ; for a discussion of how well different graph-based models model the Internet, see [Zegura 1997]). Here, nodes in the graph represent routers - the points at which packet routing decisions are made - and the lines ("edges" in graph theory terminology ) connecting these nodes represent the physical links between these routers. A link also has a value representing the "cost" of sending a packet across the link. The cost may reflect the level of congestion on that link (e.g., the current average delay for a packet across that link) or the physical distance traversed by that link (e.g., a transoceanic link might have a higher cost than a terrestrial link). For our current purposes, we will simply take the link costs as a given and won't worry about how they are determined.
Given the graph abstraction, the problem of finding the least cost path from a source to a destination requires identifying a series of links such that
:
l the first link in the path is connected to the source
l the last link in the path is connected to the destination
l for all i, the i and i-1 st link in the path are connected to the same node
l for the least cost path, the sum of the cost of the links on the path is the minimum over all possible paths between the source and destination. Note that if all link costs are the same, the least cost path is also the shortest path (i.e., the path crossing the smallest number of links between the source and the destination).
In Figure 4.2-1, for example, the least cost path between nodes A (source) and C (destination) is along the path ADEC. (We will find it notationally easier to refer to the path in terms of the nodes on the path, rather than the links on the path).
Classification of Routing Algorithms
As a simple exercise, try finding the least cost path from nodes A to F, and reflect for a moment on how you calculated that path. If you are like most people, you found the path from A to F by examining Figure 4.2-1, tracing a few routes from A to F, and somehow convincing yourself that the path you had chosen was the least cost among all possible paths (Did you check all of the 12 possible paths between A and F? Probably not! ). Such a calculation is an example of a centralized routing algorithm. Broadly, one way in which we can classify routing algorithms is according to whether they are centralized or decentralized:
l A global routing algorithm computes the least cost path between a source and destination using complete, global knowledge about the network. That is, the algorithm takes the connectivity between all nodes and all links costs as inputs. This then requires that the algorithm somehow obtain this information before actually performing the calculation. The calculation itself can be run at one site (a centralized global routing algorithm) or replicated at multiple sites. The key distinguishing feature here, however, is that a global algorithm has complete information about connectivity and link costs. In practice, algorithms with global state information are often referred to as link state algorithms , since the algorithm must be aware of the state (cost) of each link in the network. We will study a global link state algorithm in section 4.2.1.
l In a decentralized routing algorithm, the calculation of the least cost path is carried out in an iterative, distributed manner. No node has complete information about the costs of all network links. Instead, each node begins with only knowledge of the costs of its own directly attached links and then through an iterative process of calculation and exchange of information with its neighboring nodes (I. e., nodes which are at the "other end" of links to which it itself is attached)
gradually calculates the least cost path to a destination, or set of destinations. We will study a decentralized routing algorithm known as a distance vector algorithm . It is called a distance vector algorithm because a node never actually knows a complete path from source to destination. Instead, it only knows the direction (which neighbor) to which it should forward a packet in order to reach a given destination along the least cost path, and the cost of that path from itself to the destination.
A second broad way to classify routing algorithms is according to whether they are static or dynamic. In static routing algorithms, routes change very slowly over time, often as a result of human intervention (e.g., a human manually editing a router's forwarding table). Dynamic routing algorithms change the routing paths as the network traffic loads (and the resulting delays experienced by traffic) or topology change. A dynamic algorithm can be run either periodically or in direct response to topology or link cost changes. While dynamic algorithms are more responsive to network changes, they are also more susceptible to problems such as routing loops and oscillation in routes, issues we will consider in section 4.2.2.
Only two types of routing algorithms are typically used in the Internet: a dynamic global link state algorithm, and a dynamic decentralized distance vector algorithm. We cover these algorithms in section 4.2.1 and 4.2.2 respectively. Other routing algorithms are surveyed briefly in section 4.2.3.
4.2.1 A Link State Routing Algorithm
Recall that in a link state algorithm, the network topology and all link costs are known, i.e., available as input to the link state algorithm. In practice this is accomplished by having each node broadcast the identities and costs of its attached links to all other routers in the network. This link state broadcast [Perlman 1999], can be accomplished without the nodes having to initially know the identities of all other nodes in the network. A node need only know the identities and costs to its directly-attached neighbors; it will then learn about the topology of the rest of the network by receiving link state broadcast from other nodes. (In Chapter 5, we will learn how a router learns the identities of its directly attached neighbors). The result of the nodes' link state broadcast is that all nodes have an identical and complete view of the network. Each node can then run the link state algorithm and compute the same set of least cost paths as every other node.
The link state algorithm we present below is known as Dijkstra's algorithm, named after its inventor (a closely related algorithm is Prim's algorithm; see [Corman 1990] for a general discussion of graph algorithms). It computes the least cost path from one node (the source, which we will refer to as A) to all other nodes in the network. Dijkstra's algorithm is iterative and
has the property that after the kth iteration of the algorithm, the least cost paths are known to k destination nodes, and among the least cost paths to all destination nodes, these k path will have the k smallest costs. Let us define the following notation:
l c(i,j): link cost from node i to node j. If nodes i and j are not directly connected, then c(i,j) = infty. We will assume for simplicity that
c(i,j) equals c(j,i).
l D(v): the cost of path from the source node to destination v that has currently (as of this iteration of the algorithm) the least cost.
l p(v): previous node (neighbor of v) along current least cost path from source to v
l N: set of nodes whose shortest path from the source is definitively known
The link state algorithm consists of an initialization step followed by a loop. The number of times the loop is executed is equal to the numberof nodes in the network.. Upon termination, the algorithm will have calculated the shortest paths from the source node to every other node in the network..
Link State (LS) Algorithm:
1 Initialization:
2 N = {A}
3 for all nodes v
4 if v adjacent to A
5 then D(v) = c(A,v)
6 else D(v) = infty
7
8 Loop
9 find w not in N such that D(w) is a minimum
10 add w to N
11 update D(v) for all v adjacent to w and not in N:
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N
As an example, let us consider the network in Figure 4.2-1 and compute the shortest path from A to all possible destinations. A tabular summary of the algorithm's computation is shown in Table 4.2-1, where each line in the table gives the values of the algorithms variables at the end of the iteration . Let us consider the few first steps in detail:
Table 4.2-1: Steps in running the link state algorithm on network in Figure 4.2-1
l In the initialization step, the currently known least path costs from A to its directly attached neighbors, B, C and D are initialized to 2, 5 and 1 respectively. Note in particular that the cost to C is set to 5 (even though we will soon see that a lesser cost path does indeed exists) since this is cost of the direct (one hop) link from A to C. The costs to E and F are set to infinity since they are not directly connected to A.
l In the first iteration, we look among those nodes not yet added to the set N and find that node with the least cost as of the end of the previous iteration. That node is D, with a cost of 1, and thus D is added to the set N. Line 12 of the LS algorithm is then performed to update D(v) for all nodes v, yielding the results shown in the second line (step 1) in Table 4.2-1. The cost of the path to B is unchanged. The cost of the path to C (which was 5 at the end of the initialization) through node D is found to have a cost of 4. Hence this lower cost path is selected and C's predecessor along the shortest path from A is set to D. Similarly, the cost to E (through D) is computed to be 2, and the table is updated accordingly.
l In the second iteration , nodes B and E are found to have the shortest path costs (2), and we break the tie arbitrarily and add E to the set N so that N now contains A, D, and E. The cost to the remaining nodes not yet in N, i.e., nodes B, C and F, are updated via line 12 of the LS algorithm , yielding the results shown in the third row in the above table.
l and so on …
When the LS algorithm terminates, we have for each node, its predecessor along the least cost path from the source node. For each predecessor, we also have its predecessor and so in this manner we can construct the entire path from the source to all destinations.
What is the computation complexity of this algorithm? That is, given n nodes (not counting the source), how much computation must be done in the worst case to find the least cost paths from the source to all destinations? In the first iteration, we need to search through all n nodes to determine the node, w, not in N that has the minimum cost. In the second iteration, we need to check n-1 nodes to determine the minimum cost; in the third iteration n-2 nodes and so on. Overall, the total number of nodes we need to search through over all the iterations is n*(n+1)/2, and thus we say that the above implementation of the link state algorithm has worst case complexity of order n squared: O(n 2 ) ((A more sophisticated implementation of this algorithm, using a data structure known as a heap, can find the minimum in line 9 in logarithmic rather than linear time, thus reducing the complexity).
Before completing our discussion of the LS algorithm, let us consider a pathology that can arise with the use of link state routing . Figure 4.2-2 shows a simple network topology where link costs are equal to the load carried on the link, e.g., reflecting the delay that would be experienced. In this example, link costs are not symmetric, i.e., c(A,B) equals c(B,A) only if the load carried on both directions on the AB link is the same. In this example, node D originates a unit of traffic destined for A, node B also originates a unit of traffic destined for A, and node C injects an amount of traffic equal to e, also destined for A. The initial routing is shown in Figure 4.2-2a, with the link costs corresponding to the amount of traffic carried.
Figure 4.2-2: Oscillations with Link State routing
When the LS algorithm is next run, node C determines (based on the link costs shown in Figure 4.2-2a) that the clockwise path to A has a cost of 1, while the counterclockwise path to A (which it had been using) has a cost of 1+e. Hence C's least cost path to A is now clockwise .Similarly , B determines that its new least cost path to A is also clockwise, resulting in the routing and resulting path costs shown in Figure 4.2-2b. When the LS algorithm is run next, nodes B, C and D all detect that a zero cost path to A in the counterclockwise direction and all route their traffic to the counterclockwise routes. The next time the LS algorithm is run, B, C, and D all then route their traffic to the clockwise routes.
What can be done to prevent such oscillations in the LS algorithm? One solution would be to mandate that link costs not depend on the amount of traffic carried -- an unacceptable solution since one goal of routing is to avoid highly congested (e.g., high delay) links. Another solution is to insure that all routers do not run the LS algorithm at the same time. This seems a more reasonable solution, since we would hope that even if routers run the LS algorithm with the same periodicity, the execution instants of the algorithm would not be the same at each node. Interestingly, researchers have recently noted that routers in the Internet can self-synchronize among themselves [Floyd 1994], i.e., even though they initially execute the algorithm with the same period but at different instants of time, the algorithm execution instants can eventually become, and remain, synchronized at the routers. One way to avoid such self-synchronization is to purposefully introduce randomization into the period between execution instants of the algorithm at each node.
Having now studied the link state algorithm, let's next consider the other major routing algorithm that is used in practice today - the distance vector routing algorithm.
4.2.2 A Distance Vector Routing Algorithm
While the LS algorithm is an algorithm using global information, the distance vector (DV) algorithm is iterative, asynchronous, and distributed. It is distributed in that each node receives some information from one or more of its directly attached neighbors, performs a calculation, and may then distribute the results of its calculation back to its neighbors. It is iterative in that this process continues on until no more information is exchanged between neighbors. (Interestingly, we will see that the algorithm is self terminating -- there is no "signal" that the computation should stop; it just stops). The algorithm is asynchronous in that it does not require all of the nodes to operate in lock step with each other. We'll see that an asynchronous, iterative, self terminating, distributed algorithm is much more "interesting" and "fun" than a centralized algorithm.
The principal data structure in the DV algorithm is the distance table maintained at each node. Each node's distance table has a row for each destination in the network and a column for each of its directly attached neighbors. Consider a node X that is interested in routing to destination Y via its directly attached neighbor Z. Node X's distance table entry, is the sum of the cost of the direct one hop link between X and Z , c(X,Z), plus neighbor Z's currently known minimum cost path from itself (Z) to Y. That is:
The term in equation 4-1 is taken over all of Z's directly attached neighbors (including X, as we shall soon see).
Equation 4-1 suggests the form of the neighbor-to-neighbor communication that will take place in the DV algorithm -- each node must know the cost of each of its neighbors minimum cost path to each destination Thus, whenever a node computes a new minimum cost to some destination, it must inform its neighbors of this new minimum cost.
Before presenting the DV algorithm, let's consider an example that will help clarify the meaning of entries in the distance table. Consider the network topology and the distance table shown for node E in Figure 4.2-3. This is the distance table in node E once the Dv algorithm has converged.
Let's first look at the row for destination A.
l Clearly the cost to get to A from E via the direct connection to A has a cost of 1. Hence
l Let's now consider the value of -the cost to get from E to A, given that the first step along the path is D. In this case, the distance table entry is the cost to get from E to D (a cost of 2) plus whatever the minimum cost it is to get from D to A . Note that the minimum cost from D to A is 3 -- a path that passes right back through E! Nonetheless, we record the fact that the minimum cost from E to A given that the first step is via D has a cost of 5. We're left, though, with an uneasy feeling that the fact the path from E via D loops back through E may be the source of problems down the road (it will!).
l Similarly, we find that the distance table entry via neighbor B is . Note that the cost is not 15. ( why ?)
仓库规划与布局
仓库规划与布局 仓库规划与设计 一、仓库规划原则 仓库规划方案应能做到以尽可能低的成本，实现货物在仓库内快速、准确地流动。这个目标的实现，要通过物流技术、信息技术、成本控制和仓库的组织结构的一体化策略才能达到。仓储系统的物流规划原则不是一成不变的，要视具体情况而定。在特定场合下，有些原则是互相影响的，甚至互相矛盾。为了做出最好的设计，有必要对这些原则进行选择和修改。 1、系统简化原则 要根据物流标准化做好包装和物流容器的标准化，把杂货、粮食、饮料、食盐、食糖、饲料等散装货物、外形不规则货物的组成标准的储运集装单元，实现集装单元与运输车辆的载重量、有效空间尺寸的配合、集装单位与装卸设备的配合、集装单位与仓储设施的配合，这样做会有利于仓储系统中的各个环节的协调配合，在异地中转等作业时，不用换装，提高通用性，减少搬运作业时间、减轻物品的损失、损坏，从而节约费用，同时也简化了装卸搬运子系统，降低系统的操作和维护成本，提高系统的可靠性，提高仓储作业的效率。 2、平面设计原则
若无特殊要求，仓储系统中的物流都应在同一平面上实现，从而减少不必要的安全防护措施，减少利用率和作业效率低和能源消耗较大的起重机械，提高系统的效率。 3、物流和信息流的分离原则 现代物流是在计算机网络支持下的物流，物流和信息流的结合解决了物流流向的控制问题，提高了系统作业的准确率，从而提高了系统作业效率。如果不能实现物流和信息流的尽早分离，就要求在物流系统的每个分、合节点均设置相应的物流信息识读装置，这势必造成的冗余度，增加系统的成本；如果能实现物流和信息流的尽早分离，将所需信息一次识别出来，再通过计算机网络传到各个节点，即可降低系统的成本。 4、柔性化原则 仓库的建设和仓储设备的购置，需要大量的资金。为了保证仓储系统高效工作，需要配置针对性较强的设备；而社会物流环境的变化，又有可能使仓储货物品种、规格和经营规模发生改变。因此，在规划时，要注意机械和机械化系统的柔性和仓库扩大经营规模的可能性。 5、物料处理次数最少原则 不管是以人工方式还是自动方式，每一次物料处理都需要花费一定的时间和费用，通过复合操作，或者减少不必要的移动，或者引入能同时完成多个操作的设备，就可减少处理次数。
物流中心功能和布局设计
物流供应链管理 ——综合型物流中心功能和布局设计 1.概述 物流中心是从事物流活动的场所或组织，应基本符合下列要求：主要面向社会服务；物流功能健全；完善的信息网络；辐射范围大；少品种、大批量；存储、吞吐能力强；物流业务统一经营、管理。物流中心是综合性、地域性、大批量的物资位移集中地，它集商流、物流、信息流和资金流为一体，是产销企业间的中介。 图1物流中心在供应链中所处位置模型 和物流中心相关的一个概念是配送中心，配送中心是从事配送业务的物流场所或组织，应基本符合下列要求：主要为特定的用户服务；配送功能健全；完善的信息网络；辐射范围小；多品种、小批量；以配送为主、存储为辅。执行实物配送是配送中心的主要功能，简单的讲，配送中心就是从事集货、流通加工、分货、拣选、配货以及组织对用户送货，以高水平实现销售和供应服务的现代物流设施。 总体上，物流中心辐射范围大，处理的对象为大批量、小批次和少品种的商品，配送中心正好相反。从两者在供应链中所处的位置看，物流中心的上游是工厂，下游是配送中心或批发商，而配送中心的上游是物流中心或工厂，下游是零售商或最终用户。 综合型物流中心是指能够储存、加工、分拣与配送多种商品的物流中心，这类物流中心的加工、配送品种多，规模也大，适合各种不同需求用户的服务要求，所以其柔性较大。综合型物流中心在供应链中所处位置模型如图1所示。 本文就综合型物流中心的功能设计和布局设计作一定的探讨。 2综合型物流中心的功能设计 在整个供应链中，作为物流结点的物流中心起着承前启后的重要作用，综合
型物流中心功能设计如图2所示。具体讲一般应具备如下功能： 图2物流中心功能设计图 1）商品的运输集散中心功能。 物流中心需要自己拥有或租赁一定规模的运输工具，物流中心是一个覆盖一定地域地网络。因此物流中心首先应该负责为客户选择满足客户需要的运输方式，然后具体组织网络内部的运输作业，在规定的时间内将客户的商品运到目的地。除交货需要客户参与外，整个过程都由物流中心负责，以提高客户的满意度。所以运输集货功能是物流中心的基本功能之一，特别是在强调差异化营销的时代，商品流通呈现多批次、少批量趋势，生产企业以前的运输功能就必然由物流中心取代，从而使生产企业集中精力于生产，同时这样也降低了生产企业的管理成本，提高物流效率和其利润。 2）商品的分拣、配货中心功能。 随着流通体系的不断完善和营销渠道的进一步细分，在商品、原材料进货或发货方面，越来越显现出多样化、差异化的趋势。在这种趋势下，商品的分拣、配货职能显得日益重要。商品分拣与配货对保证商品的顺利流动，建立合理、高效的物流网络系统具有积极的意义。而物流中心正是专门从事分拣、配货工作的机构或物流据点，通过物流中心把不同企业生产的产品集至物流中心，然后进行不同客户订单处理，按客户要求的种类、数量进行集中配置，再向客户发送货物，这样可以大大节约商品分拣、配货的作业量。对于连锁形式的零售业来讲，利用物流中心的分拣、配送功能直接送货到货架，同样可以节约大量的费用，提高连锁业的竞争力，有利于实施企业整体的发展战略。对整个社会的发展和产业利益来讲，因为商品的分拣和配货工作是集中在物流中心完成而非每个企业单独完成，这就实现了商品配送的集约化，有效避免了分散运输、交叉或迂回运输现象，实现了社会物流成本优化的目标。 3）商品储存中心。 利用物流中心的储存功能，可有效地组织货源，调节商品地生产与消费、进